Fastest way to cull bounded box in frustrum

I have a very large dataset that I have partitioned with a BSP. Each partition is axis aligned with the graphics coordinate system and its volume is defined in terms of a centroid and two vertices representing the maximum and minimum coordinates in graphics space.

I grab the viewing frustum from the m/p matrices at the start of each frame and store it in the form of 6 plane equations. I am successfully using it to do point and sphere culling. However, I also need to cull the partitions …

Now, I have considered just using the vertices at each corner and the centroid in a point culling algorithm (5 point tests). I have also considered just using a sphere test in which the culling radius was based on the maximum dimension of the partitions. I tossed the sphere idea since the dimensions of the partitions varied considerably giving rise to a spherical volume much larger than the partition. I am considering using plane/line intersection testing to do the job also.

I need to make this portion of code as fast as I possibly can since there may be hundreds of partition volumes in the scene.

My question is this … Has anyone done any testing to benchmark the performance of plane/line intersection testing versus say 5 point tests?

[This message has been edited by pleopard (edited 01-22-2002).]

There is a faster way; transform the plane equations of the frustum into world space, then cull test the cube to these. If you want to speed things up you might want to consider a sphere test followed by an optional box test. If there is sometimes more visible than culled you might want a bound sphere test followed by an optional minimally enclosed sphere test followed by an optional bound box test.

If you want even faster culling then consider a hierarchy with the typical accept all, reject all or descend & test further heuristic.

Hi,

this is the algo I use, it looks like it does much less job than what you mentionned and works pretty well.

credits for the algorithms should go, from what I remember, to David H. Eberly on comp.graphics.algorithms…

bool ConvexVolume: utside(BoundingBox const& box) const
{
Point3d const& bc = box.getCenter();
Vector3d const& be = box.getExtent();

for (unsigned i=0; i<m_numPlanes; i++)
{
register Plane3d const& plane = m_planes[i];

  Vector3d n = plane.n;

  float dist = plane.distance( bc );

  n.x = mgd::abs(n.x);
  n.y = mgd::abs(n.y);
  n.z = mgd::abs(n.z);
  
  float safe = be*n;

  if (dist < -safe)
  	return true;

}

return false;
}

Hope this helps.

Nicolas.

Humf, funny that smilies get into “CODE” sections

There is a method to compare only two points against the plane. You select the two where the points are on either side of the bounding box. The two points to consider at those which create a vector that is most parallel to the normal of the plane. Then test to see which side each point is on, both in-front then the box is in front, both behind then the box is behind, etc.

Neil Witcomb

Thanks for the help there Nicholas but I already have that working. I can cull by testing for a single point in the view frustum, doing a sphere cull, or doing a box cull. All three are highly optimized and working well.

I did some testing this afternoon on the three methods for a 100x100 partition set and found that my framerate was somewhat effected in going from the point test to sphere test (went from 210 FPS to 203 FPS). Comparing the sphere test to the box test didn’t make much of a difference (~ 2 FPS on average). Getting 200 FPS is actually quite a feat since each partition (100,000 of them) is drawn as a wireframe box with line smoothing on, blending on, and the centroid displayed as a point with a 12 pixel size. I also have a ground grid displayed that encompasses 60x40 quads as lines also smoothed. The partition display is a runtime option toggled with F8. Turning it off (just the display, not the culling logic) ups my framerate to around 980 FPS.

Dorbie, I am looking for references on the “typical accept all, reject all or descend & test further heuristic” you spoke of. As you can see, my culling logic (without drawing the culling partitions) lowers my framerate from 980 to 200 FPS. I have realized that my percieved definition of a BSP was incorrect. Forgive me, I am learning this stuff on my own and still have quite a way to go. What I am using is called a directed acyclic graph. Nodes in the graph are linked together as either siblings or children. For this operation, I am not using siblings at all therefore the render update must do the culling test for every single node all the way down the list for every frame.

I am looking into using an Octree, having found Dan Ginsburg’s excellent paper on it in “Game Programming Gems”. I understand that there are higly efficient ways to use an octree (depending on how smart you are when you build the tree) and I suspect that I can use one to pare down the number of partitions I have to check each frame.

Wish me luck and keep the great comments coming …

>>Dorbie, I am looking for references on the “typical accept all, reject all or descend & test further heuristic” you spoke of. As you can see, my culling logic (without drawing the culling partitions) lowers my framerate from 980 to 200 FPS. I have realized that my percieved definition of a BSP was incorrect. Forgive me, I am learning this stuff on my own and still have quite a way to go. What I am using is called a directed acyclic graph. Nodes in the graph are linked together as either siblings or children. For this operation, I am not using siblings at all therefore the render update must do the culling test for every single node all the way down the list for every frame.<<

ouch! painful heres why (for an octree) each node has 8 siblings say the depth goes 4 deep
thus there are 8x8x8x8(4096) bounding boxes of the smallest size (leaves)
test the mother BB (which contains all 4096 BB’s) against the viewfrustums planes
3 posible results
*inside - all 4096 are also inside
*outside - everything is outside
*straddles the border (test its 8 children against the biewplanes)
as u can see this is gonna be much cheaper

Here’s some code I found in an NVidia demo (but I can’t figure out where exactly); The code was changed a little to match my classes’ definitions, but I’m confident you’ll make that out.

  // plans de clipping AABB
  D3DXPLANE m_fClipPlanes[6];

u8 wdCameraCtrlEx::CheckAABBVisible(P3f &_rLowerBound,P3f &_rUpperBound)
{
D3DXVECTOR3 vecMinPt;
D3DXVECTOR3 vecMaxPt;

mcBool bIntersecting=false;

// récupérer les plans de clipping si la caméra a bougé
if (m_bChanged)
{
// récupération des plans de clipping
// ----------------------------------

  D3DXMATRIX matView;
  D3DXMATRIX matProjection;
  D3DXMATRIX matViewProjection;

  m_GraphicCamera.GetMatView(*((mmMatrix44*)&matView));
  m_GraphicCamera.GetMatProj(*((mmMatrix44*)&matProjection));

  D3DXMatrixMultiply(&matViewProjection,&matView,&matProjection);
  D3DXMatrixTranspose(&matViewProjection,&matViewProjection);

  D3DXVECTOR4	tmpVec;
  D3DXVECTOR4 Columns[4];
  Columns[0] = D3DXVECTOR4(matViewProjection(0, 0), matViewProjection(0, 1), matViewProjection(0, 2), matViewProjection(0, 3));
  Columns[1] = D3DXVECTOR4(matViewProjection(1, 0), matViewProjection(1, 1), matViewProjection(1, 2), matViewProjection(1, 3));
  Columns[2] = D3DXVECTOR4(matViewProjection(2, 0), matViewProjection(2, 1), matViewProjection(2, 2), matViewProjection(2, 3));
  Columns[3] = D3DXVECTOR4(matViewProjection(3, 0), matViewProjection(3, 1), matViewProjection(3, 2), matViewProjection(3, 3));
  
  tmpVec=Columns[3]-Columns[0];
  *((D3DXVECTOR4*)&m_fClipPlanes[0])=-tmpVec;

  tmpVec=Columns[3]+Columns[0];
  *((D3DXVECTOR4*)&m_fClipPlanes[1])=-tmpVec;

  tmpVec=Columns[3]-Columns[1];
  *((D3DXVECTOR4*)&m_fClipPlanes[2])=-tmpVec;

  tmpVec=Columns[3]+Columns[1];
  *((D3DXVECTOR4*)&m_fClipPlanes[3])=-tmpVec;

  tmpVec=Columns[3]-Columns[2];
  *((D3DXVECTOR4*)&m_fClipPlanes[4])=-tmpVec;

  tmpVec=Columns[3]+Columns[2];
  *((D3DXVECTOR4*)&m_fClipPlanes[5])=-tmpVec;

  m_bChanged=false;

}

for (int i=0;i<6;i++)
{
for (int j=0;j<3;j++)
{
if (m_fClipPlanes[i][j]>=0.0f)
{
vecMinPt[j]=_rLowerBound[j];
vecMaxPt[j]=_rUpperBound[j];
}
else
{
vecMinPt[j]=_rUpperBound[j];
vecMaxPt[j]=_rLowerBound[j];
}
}

  float fMinDistance=D3DXPlaneDotCoord(&m_fClipPlanes[i],&vecMinPt);
  if (fMinDistance>0.0f) { return 0; }

  float fMaxDistance=D3DXPlaneDotCoord(&m_fClipPlanes[i],&vecMaxPt);
  if (fMaxDistance>=0.0f) { bIntersecting=true; }

}

return (bIntersecting?(u8)1:(u8)2);
}

Hope that helps anybody…

Thanks for the effort Jehan but again, I have the culling algorithms working and optimized.

Ok, I am experimenting with an Octree now and I a little unsure about the decision heuristic to use. Since my questions are evolving away from the original question in this thread, I am starting a new thread in order to minimize any confusion …

See the following if you are interested …
http://www.opengl.org/discussion_boards/ubb/Forum3/HTML/005347.html

Thanks!
Paul