More frustum cull methods

[devsh]

box vs. frustum is really THE Optimal Way

since:
-SIMD you can do all the min/max and comparisons in less ops than working out lengths of 3D vectors and comparing
-Translates better into Hi-Z buffer culling
-Spheres don't tessellate so any hierarchical culling approach is not really too feasible
-Calculating a new BBox for a set of points is faster than sphere calc
-Boxes usually turn out to be more close fitting to regular scene geometry/meshbuffers
+If someone finally made the fix where matrix multiplications and etc. would be optimized (cached) then you wouldnt have the overhead of "getTransformedBoundingBox"

[hendu]

-SIMD you can do all the min/max and comparisons in less ops than working out lengths of 3D vectors and comparing

Numbers, please.

-Spheres don't tessellate so any hierarchical culling approach is not really too feasible

What? It's a mathematical sphere defined by center and radius. Only the visualization is tessellated.

[luthyr]

One optimization we did locally for EAC_FRUSTUM_BOX was create a new function that passed in an inverse transposed matrix for transforming a plane, since it was needlessly doing it 6 times.

Here is that patch:
https://mega.co.nz/#!HQcHTD4L!ypvmUz9Vh ... C6mMKkRtsE

[devsh]

-SIMD you can do all the min/max and comparisons in less ops than working out lengths of 3D vectors and comparing

Numbers, please.

Building a bounding box from vertices:

Code: Select all

 
Box.Max = firstVertex.Pos;
Box.Min = firstVertex.Pos;
// 2 assigns
for (each vertex)
{
   Box.Max = simd_max(Box.Max,vertex.Pos); //SSE2+assign
   Box.Min = simd_min(Box.Max,vertex.Pos); //SSE2+assign
} 
 

Runs in O(v) time where v is num of verts

However EXACT bounding sphere runs in O(v^2)
https://en.wikipedia.org/wiki/Bounding_ ... Algorithms

Approximate bounding sphere runs O(v^2+epsilon*v^2)



What I meant by tessellate, not geometry but there isn't a SparseOctree or other good/widely used space partitioning algos for spheres (there is for boxes)

[hendu]

Oh you meant the sphere creation. My patch uses an approximate bounding sphere, created from the bounding box in O(1) time. So in essence we get the sphere for free.

What I meant by tessellate, not geometry but there isn't a SparseOctree or other good/widely used space partitioning algos for spheres (there is for boxes)

Agreed, but that's not really related to this topic. I'm not changing the default or removing the box choice, I'm adding two new frustum culling choices, which the users can choose based on their requirements.

[Adversus]

Code: Select all

    // can be seen by cam pyramid planes ?
    if (!result && (node->getAutomaticCulling() & scene::EAC_FRUSTUM_BOX))
    {
        SViewFrustum frust = *cam->getViewFrustum();
 
        core::vector3df edges[8];
        core::aabbox3d<f32> box = node->getBoundingBox();
        node->getAbsoluteTransformation().transformBox(box);
        box.getEdges(edges);
        
        for (s32 i=0; i<scene::SViewFrustum::VF_PLANE_COUNT; ++i)
        {
            bool boxInFrustum=false;
            for (u32 j=0; j<8; ++j)
            {
                if (frust.planes[i].classifyPointRelation(edges[j]) != core::ISREL3D_FRONT)
                {
                    boxInFrustum=true;
                    break;
                }
            }
 
            if (!boxInFrustum)
            {
                result = true;
                break;
            }
        }
    }

I simplified the code for the box frustum culling and it's much faster and seems to work perfectly so if that's the fix you refer to then there its is.

However I would still like to see Hendu's cone culling. Do you have a .patch file for that? I can merge it manually if needed.

[hendu]

I haven't bothered to make a SVN patch, due to the effort needed it would have been pointless. You can dig the code out of my branch if interested:
github.com/clbr/seirr

[Adversus]

Thanks Hendu. That's easier

[Nadro]

Patch applied into trunk. Sorry for a delay with that, but I totally forgot about it.