Exact aabb vs frustum culling

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 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

Please log in or register to post a reply.

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Dec 05, 2007 at 17:51

errate corrige :

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

is

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

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 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.

C84a6523bb5572109fc16796c5fd19b2
0
rvangaal 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.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 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.