Page 2 of 2
Re: More frustum cull methods
Posted: Wed Mar 12, 2014 10:49 pm
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"
Re: More frustum cull methods
Posted: Thu Mar 13, 2014 9:04 am
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.
Re: More frustum cull methods
Posted: Thu Mar 13, 2014 3:58 pm
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
Re: More frustum cull methods
Posted: Thu Mar 13, 2014 4:18 pm
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)
Re: More frustum cull methods
Posted: Thu Mar 13, 2014 7:33 pm
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.
Re: More frustum cull methods
Posted: Wed Mar 19, 2014 2:22 pm
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.
Re: More frustum cull methods
Posted: Wed Mar 19, 2014 6:56 pm
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
Re: More frustum cull methods
Posted: Thu Mar 20, 2014 12:41 pm
by Adversus
Thanks Hendu. That's easier
Re: More frustum cull methods
Posted: Tue Sep 16, 2014 6:47 pm
by Nadro
Patch applied into trunk. Sorry for a delay with that, but I totally forgot about it.