More frustum cull methods

Discuss about anything related to the Irrlicht Engine, or read announcements about any significant features or usage changes.
devsh
Competition winner
Posts: 2057
Joined: Tue Dec 09, 2008 6:00 pm
Location: UK
Contact:

Re: More frustum cull methods

Post by 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
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: More frustum cull methods

Post by 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
Posts: 69
Joined: Wed Dec 30, 2009 5:47 pm

Re: More frustum cull methods

Post by 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
Competition winner
Posts: 2057
Joined: Tue Dec 09, 2008 6:00 pm
Location: UK
Contact:

Re: More frustum cull methods

Post by 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
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: More frustum cull methods

Post by 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
Posts: 128
Joined: Sun Oct 05, 2008 10:58 pm
Contact:

Re: More frustum cull methods

Post by 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
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: More frustum cull methods

Post by 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
Posts: 128
Joined: Sun Oct 05, 2008 10:58 pm
Contact:

Re: More frustum cull methods

Post by Adversus »

Thanks Hendu. That's easier :-)
Nadro
Posts: 1648
Joined: Sun Feb 19, 2006 9:08 am
Location: Warsaw, Poland

Re: More frustum cull methods

Post by Nadro »

Patch applied into trunk. Sorry for a delay with that, but I totally forgot about it.
Library helping with network requests, tasks management, logger etc in desktop and mobile apps: https://github.com/GrupaPracuj/hermes
Post Reply