0
105 Dec 05, 2007 at 15:00

This is a function i have spent quite a lot of time to fine tune, it is an exact frustum / AABB culling function.
You can substitute Node->BoxP1 , Node->BoxP2 with Min and Max of your aabb ,
this functions needs some external data, you can easily replace , and frustum planes
need to be computed before calling it.
I have yet to find some case this function doesn’t catch.

Note:
it uses an external class called Vec3f , which supports vector operations
Pts is a vector of 8 integers
d is a vector of 8 floats storing signs
P is a vector of 8 Vec3f classes

functions returns
0 -> box is out
1 -> box is in
2 -> box is intersecting the frustum

int CullAABB2( CNode *Node )
{
/////////////////////////////////////
// exact frustum culling
// by point decimation

///////////////////////////////////////
// if observer is inside box ,
// surely it intersects it

if ( Pos[0]>Node->BoxP1[0] && Pos[0]<Node->BoxP2[0] )
if ( Pos[1]>Node->BoxP1[1] && Pos[1]<Node->BoxP2[1] )
if ( Pos[2]>Node->BoxP1[2] && Pos[2]<Node->BoxP2[2] )
return 2;

/////////////////////////////////
// fill vertex cache

P[0].set( Node->BoxP1[0]-Pos[0],Node->BoxP1[1]-Pos[1],Node->BoxP1[2]-Pos[2]);
P[1].set( Node->BoxP2[0]-Pos[0],Node->BoxP1[1]-Pos[1],Node->BoxP1[2]-Pos[2]);
P[2].set( Node->BoxP1[0]-Pos[0],Node->BoxP2[1]-Pos[1],Node->BoxP1[2]-Pos[2]);
P[3].set( Node->BoxP2[0]-Pos[0],Node->BoxP2[1]-Pos[1],Node->BoxP1[2]-Pos[2]);
P[4].set( Node->BoxP1[0]-Pos[0],Node->BoxP1[1]-Pos[1],Node->BoxP2[2]-Pos[2]);
P[5].set( Node->BoxP2[0]-Pos[0],Node->BoxP1[1]-Pos[1],Node->BoxP2[2]-Pos[2]);
P[6].set( Node->BoxP1[0]-Pos[0],Node->BoxP2[1]-Pos[1],Node->BoxP2[2]-Pos[2]);
P[7].set( Node->BoxP2[0]-Pos[0],Node->BoxP2[1]-Pos[1],Node->BoxP2[2]-Pos[2]);

d[0]=dot ( P[0] ,frustum[4] );
d[1]=dot ( P[1] ,frustum[4] );
d[2]=dot ( P[2] ,frustum[4] );
d[3]=dot ( P[3] ,frustum[4] );
d[4]=dot ( P[4] ,frustum[4] );
d[5]=dot ( P[5] ,frustum[4] );
d[6]=dot ( P[6] ,frustum[4] );
d[7]=dot ( P[7] ,frustum[4] );

Pts[0]=0;

//////////////////////////////////////////////
// if a point is on the positive side
// of near plane , store it in the
// point list

if ( d[0]>0 ) P[ Pts[0]++ ].set( P[0][0],P[0][1],P[0][2] );
if ( d[1]>0 ) P[ Pts[0]++ ].set( P[1][0],P[1][1],P[1][2] );
if ( d[2]>0 ) P[ Pts[0]++ ].set( P[2][0],P[2][1],P[2][2] );
if ( d[3]>0 ) P[ Pts[0]++ ].set( P[3][0],P[3][1],P[3][2] );
if ( d[4]>0 ) P[ Pts[0]++ ].set( P[4][0],P[4][1],P[4][2] );
if ( d[5]>0 ) P[ Pts[0]++ ].set( P[5][0],P[5][1],P[5][2] );
if ( d[6]>0 ) P[ Pts[0]++ ].set( P[6][0],P[6][1],P[6][2] );
if ( d[7]>0 ) P[ Pts[0]++ ].set( P[7][0],P[7][1],P[7][2] );

/////////////////////////////////////
// box is outisde near , plane
// no need to go further

if ( Pts[0]==0 )
return 0;

//////////////////////////////////
// now check for points which
// didn't pass the near plane test
// for each point check its sign
// if positive , store in the
// point list and repeat for
// each frustum plane
// in an unrolled loop

///////////////////////////////////
// left

register int  i;

for ( i=0;i<Pts[0];i++)
d[i]=dot ( P[i] ,frustum[0] );

Pts[1]=0;

for ( i=0;i<Pts[0];i++)
if ( d[i]>0 )
P[ Pts[1]++ ].set( P[i][0],P[i][1],P[i][2] );

//////////////////////////////
// bottom

for ( i=0;i<Pts[1];i++)
d[i]=dot ( P[i] ,frustum[1] );

Pts[2]=0;

for ( i=0;i<Pts[1];i++)
if ( d[i]>0 )
P[ Pts[2]++ ].set( P[i][0],P[i][1],P[i][2] );

////////////////////////////////////////
// right

for ( i=0;i<Pts[2];i++)
d[i]=dot ( P[i] ,frustum[2] );

Pts[3]=0;

for ( i=0;i<Pts[2];i++)
if ( d[i]>0 )
P[ Pts[3]++ ].set( P[i][0],P[i][1],P[i][2] );

/////////////////////////////
// top

for ( i=0;i<Pts[3];i++)
d[i]=dot ( P[i] ,frustum[3] );

Pts[4]=0;

for ( i=0;i<Pts[3];i++)
if ( d[i]>0 )
P[ Pts[4]++ ].set( P[i][0],P[i][1],P[i][2] );

///////////////////////////////////////
// now we count how many points survided
// the las frustum plane check
// note that i don't use far plane

///////////////////////////////////////
// box is entirely inside frustum

if ( Pts[4]==8)
return 1;

//////////////////////////
// box is intersecting

if ( Pts[4]>0 )
return 2;

/////////////////////////////////////////////
// if we get here, we still need to check
// if frustum intersects the box
// we are going to use frustum directions
// you can extract from the multiplications
// of modelview and projection matrix

float px,py,pz,t;

for ( i=0; i<5; i++ )
{

t=(-Node->BoxP1[1]+Pos[1])/ProjDir[i][1];

if ( t>0.0f  )
{
// compute intersection

px=Pos[0]-t*ProjDir[i][0];

// if intersection is inside the plane
// go ahead and test other component

if ( px>Node->BoxP1[0] &&
px<Node->BoxP2[0] )
{
pz=Pos[2]-t*ProjDir[i][2];

// ok, frustum intersects the box

if  ( pz>Node->BoxP1[2] &&
pz<Node->BoxP2[2]  )
return 2;
}
}

//////////////////////
same as above but for top box plane

t=(-Node->BoxP2[1]+Pos[1])/ProjDir[i][1];

if ( t>0.0f  )
{
px=Pos[0]-t*ProjDir[i][0];

if ( px>Node->BoxP1[0] &&
px<Node->BoxP2[0] )
{
pz=Pos[2]-t*ProjDir[i][2];

if(  pz>Node->BoxP1[2] &&
pz<Node->BoxP2[2]  )
return 2;
}
}

////////////////////////////
// left box plane

t=(-Node->BoxP1[0]+Pos[0])/ProjDir[i][0];

if ( t>0.0f  )
{
py=Pos[1]-t*ProjDir[i][1];

if ( py>Node->BoxP1[1] &&
py<Node->BoxP2[1] )
{
pz=Pos[2]-t*ProjDir[i][2];

if ( pz>Node->BoxP1[2] &&
pz<Node->BoxP2[2]  )
return 2;
}
}

/////////////////////////
// right box plane

t=(-Node->BoxP2[0]+Pos[0])/ProjDir[i][0];

if ( t>0.0f  )
{
py=Pos[1]-t*ProjDir[i][1];

if ( py>Node->BoxP1[1] &&
py<Node->BoxP2[1] )
{
pz=Pos[2]-t*ProjDir[i][2];

if( pz>Node->BoxP1[2] &&
pz<Node->BoxP2[2]  )
return 2;
}
}

///////////////////////////
// near box plane

t=(-Node->BoxP1[2]+Pos[2])/ProjDir[i][2];

if ( t>0.0f  )
{
px=Pos[0]-t*ProjDir[i][0];

if ( px>Node->BoxP1[0] &&
px<Node->BoxP2[0] )
{
py=Pos[1]-t*ProjDir[i][1];

if( py>Node->BoxP1[1] &&
py<Node->BoxP2[1]  )
return 2;
}
}

/////////////////////////
// far box plane

t=(-Node->BoxP2[2]+Pos[2])/ProjDir[i][2];

if ( t>0.0f  )
{
px=Pos[0]-t*ProjDir[i][0];

if ( px>Node->BoxP1[0] &&
px<Node->BoxP2[0] )
{
py=Pos[1]-t*ProjDir[i][1];

if( py>Node->BoxP1[1] &&
py<Node->BoxP2[1]  )
return 2;
}
}
}

//////////////////////////////////
// box is out

return 0;

}


#### 4 Replies

0
105 Dec 05, 2007 at 17:51

errate corrige :

for ( i=0; i<5; i++ )

is

for ( i=0; i<4; i++ )

0
101 Dec 05, 2007 at 20:27

It sounds awfully complicated. Especially with the divides. Why not use a seperating axis test, together with some precomputed values of the frustum (tightest aabb around the frustum, the crossproduct of each frustum edge with each basis vector, projection distances of the frustum on it’s planes and those vectors)? You’ll only need 23 planetests in the worst case, with lots of early out oppertunities if they don’t intersect.

0
101 Nov 11, 2008 at 14:20

Sounds like a lot of work. Check out Mark Morley’s page on frustum culling. His site is down these days but you can see a copy on http://www.racer.nl/reference/vfc_markmorley.htm for example.

These days I’m using bits to get 2\^3 directions for the box (AABB) I want to test; I then only check the 2 outer vertices on the AABB versus each of the 6 planes. Slightly faster.

0
101 Nov 11, 2008 at 15:07

If you use all the 6 planes you only need to test 1 vertex per plane, not 2. But it is not exact, which is what the topicstarter wanted.