D3DSmartCulling: An alternative technique for culling meshes

Started by
9 comments, last by duhroach 19 years, 1 month ago
Hi, The SDK Cull sample presents a nice technique to check if bounding boxes are outside the view frustum. But sometimes, using bounding boxes may not be a good solution. This happens, mainly, when you have a large, irregular and detailed mesh. So, I decided to implement a new technique to get more flexibility. D3DSmartCulling class has a precision method to check if any mesh is inside/outside or intercepting the view frustum. So, you could create a low polygon mesh around the detailed mesh for the culling check. Compare the bounding geometries in the following figure: bound.jpg The "insight" of the D3DSmartCulling is to work on the projection space (instead of working on the world space). I will explain the theory behind D3DSmartCulling: You can transform any vertice from the world space to the projection space by applying: vertex = vertex * (world matrix) * (view matrix) * (projection matrix) The following figure illustrates this transformation: transformvert.gif After the transformation, the vertex will have a z value = 1, and if the x and y values are inside the [-1,1] interval, then the vertex will be inside the viewport (on the projection surface, the left-top and right-bottom corner positions of the viewport are (-1,1,1) and (1,-1,1), respectively). Also, note that the projection surface is the plane z = 1 (relative to the projection coordinate system). Well, if the x and y components of the one projected vertex of the mesh are in [-1,1], then the mesh is inside or intercepting the frustum. But, even if all the projected vertices are outside the viewport, the mesh still can interpect the frustum egdes. Look at the following figure: rays.gif We solve that by emitting rays (on the viewport corners) in the z direction and checking if they intercept some projected face. Now take the candy[smile]: The complete D3DSmartCulling code for you:

struct VERT_FROM_FACE
{
    D3DXVECTOR3 v1;
    D3DXVECTOR3 v2;
    D3DXVECTOR3 v3;
};


//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// D3DSmartCulling class
//
// Desc: Shows a technique for culling meshes or bounding 
//       boxes that are outside the view frustum.
//
// Developed by Adriano José Marques Ribeiro
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
class D3DSmartCulling  
{
    public:
        D3DSmartCulling(LPDIRECT3DDEVICE9 device, LPD3DXMESH pMeshIn, BOOL createBoundBox);
        BOOL CheckCulling( LPDIRECT3DDEVICE9 device );
    virtual ~D3DSmartCulling();
		
    private:
        LPD3DXVECTOR3 vert;
        LPD3DXVECTOR3 vertMesh;
        DWORD NumVertices;

        VERT_FROM_FACE *vertMeshFace;
        VERT_FROM_FACE *vertFace;
        DWORD NumFaces;
};




//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// Class constructor: Initializations 
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
D3DSmartCulling::D3DSmartCulling(LPDIRECT3DDEVICE9 device, LPD3DXMESH pMeshIn, BOOL createBoundBox)
{
    LPD3DXMESH pMesh = NULL;

    DWORD FVF(D3DFVF_XYZ);

    pMeshIn->CloneMeshFVF(D3DXMESH_MANAGED, FVF, device, &pMesh);


    D3DXVECTOR3 *pVertices;
    WORD        *pIndices;

    pMesh->LockIndexBuffer(D3DLOCK_READONLY, (VOID**)&pIndices);
    pMesh->LockVertexBuffer(D3DLOCK_READONLY,(VOID**)&pVertices);								
	
    NumVertices = pMesh->GetNumVertices();
    NumFaces    = pMesh->GetNumFaces();


    // Computing a bounding box
    if ( createBoundBox == TRUE )
    {
        D3DXVECTOR3 vMin;
        D3DXVECTOR3 vMax;

        D3DXComputeBoundingBox( pVertices,
                                NumVertices,
                                D3DXGetFVFVertexSize(FVF),
                                &vMin,
                                &vMax );

        vertMesh = new D3DXVECTOR3[8];
		
        // Storing the vertex positions of the bounding box
        vertMesh[0] = D3DXVECTOR3( vMin.x, vMin.y, vMin.z );
        vertMesh[1] = D3DXVECTOR3( vMax.x, vMin.y, vMin.z );
        vertMesh[2] = D3DXVECTOR3( vMin.x, vMax.y, vMin.z );
        vertMesh[3] = D3DXVECTOR3( vMax.x, vMax.y, vMin.z );
        vertMesh[4] = D3DXVECTOR3( vMin.x, vMin.y, vMax.z );
        vertMesh[5] = D3DXVECTOR3( vMax.x, vMin.y, vMax.z );
        vertMesh[6] = D3DXVECTOR3( vMin.x, vMax.y, vMax.z );
        vertMesh[7] = D3DXVECTOR3( vMax.x, vMax.y, vMax.z );


        vertMeshFace = new VERT_FROM_FACE[12];

        // Generating an indexed bounding box
        vertMeshFace[0].v1 = D3DXVECTOR3( vMin.x, vMin.y, vMin.z );
        vertMeshFace[0].v2 = D3DXVECTOR3( vMin.x, vMax.y, vMin.z );
        vertMeshFace[0].v3 = D3DXVECTOR3( vMax.x, vMin.y, vMin.z );

        vertMeshFace[1].v1 = D3DXVECTOR3( vMax.x, vMin.y, vMin.z );
        vertMeshFace[1].v2 = D3DXVECTOR3( vMin.x, vMax.y, vMin.z );
        vertMeshFace[1].v3 = D3DXVECTOR3( vMax.x, vMax.y, vMin.z );

        vertMeshFace[2].v1 = D3DXVECTOR3( vMin.x, vMax.y, vMin.z );
        vertMeshFace[2].v2 = D3DXVECTOR3( vMin.x, vMax.y, vMax.z );
        vertMeshFace[2].v3 = D3DXVECTOR3( vMax.x, vMax.y, vMin.z );

        vertMeshFace[3].v1 = D3DXVECTOR3( vMin.x, vMax.y, vMax.z );
        vertMeshFace[3].v2 = D3DXVECTOR3( vMax.x, vMax.y, vMax.z );
        vertMeshFace[3].v3 = D3DXVECTOR3( vMax.x, vMax.y, vMin.z );

        vertMeshFace[4].v1 = D3DXVECTOR3( vMax.x, vMax.y, vMax.z );
        vertMeshFace[4].v2 = D3DXVECTOR3( vMin.x, vMax.y, vMax.z );
        vertMeshFace[4].v3 = D3DXVECTOR3( vMin.x, vMin.y, vMax.z );

        vertMeshFace[5].v1 = D3DXVECTOR3( vMin.x, vMin.y, vMax.z );
        vertMeshFace[5].v2 = D3DXVECTOR3( vMax.x, vMin.y, vMax.z );
        vertMeshFace[5].v3 = D3DXVECTOR3( vMax.x, vMax.y, vMax.z );

        vertMeshFace[6].v1 = D3DXVECTOR3( vMax.x, vMin.y, vMin.z );
        vertMeshFace[6].v2 = D3DXVECTOR3( vMax.x, vMin.y, vMax.z );
        vertMeshFace[6].v3 = D3DXVECTOR3( vMin.x, vMin.y, vMax.z );

        vertMeshFace[7].v1 = D3DXVECTOR3( vMin.x, vMin.y, vMax.z );
        vertMeshFace[7].v2 = D3DXVECTOR3( vMin.x, vMin.y, vMin.z );
        vertMeshFace[7].v3 = D3DXVECTOR3( vMax.x, vMin.y, vMin.z );

        vertMeshFace[8].v1 = D3DXVECTOR3( vMax.x, vMax.y, vMin.z );
        vertMeshFace[8].v2 = D3DXVECTOR3( vMax.x, vMax.y, vMax.z );
        vertMeshFace[8].v3 = D3DXVECTOR3( vMax.x, vMin.y, vMax.z );

        vertMeshFace[9].v1 = D3DXVECTOR3( vMax.x, vMin.y, vMax.z );
        vertMeshFace[9].v2 = D3DXVECTOR3( vMax.x, vMin.y, vMin.z );
        vertMeshFace[9].v3 = D3DXVECTOR3( vMax.x, vMax.y, vMin.z );

        vertMeshFace[10].v1 = D3DXVECTOR3( vMin.x, vMax.y, vMax.z );
        vertMeshFace[10].v2 = D3DXVECTOR3( vMin.x, vMax.y, vMin.z );
        vertMeshFace[10].v3 = D3DXVECTOR3( vMin.x, vMin.y, vMax.z );

        vertMeshFace[11].v1 = D3DXVECTOR3( vMin.x, vMax.y, vMin.z );
        vertMeshFace[11].v2 = D3DXVECTOR3( vMin.x, vMin.y, vMin.z );
        vertMeshFace[11].v3 = D3DXVECTOR3( vMin.x, vMin.y, vMax.z );

        NumVertices = 8;
        NumFaces    = 12;
    }

    // Considering all the vertices from the mesh for the culling check
    else
    {
        vertMesh = new D3DXVECTOR3[NumVertices];

        for ( DWORD i = 0 ; i < NumVertices ; i++ )
            vertMesh = pVertices;


        vertMeshFace = new VERT_FROM_FACE[NumFaces];
	
        for ( DWORD face = 0; face < NumFaces ; face++ )
        {	
            vertMeshFace[face].v1 = pVertices[pIndices[3*face+0]];
            vertMeshFace[face].v2 = pVertices[pIndices[3*face+1]];
            vertMeshFace[face].v3 = pVertices[pIndices[3*face+2]];
        }
    }

    pMesh->UnlockVertexBuffer();
    pMesh->UnlockIndexBuffer();	

    pMesh->Release();

    vert     = new D3DXVECTOR3[NumVertices];
    vertFace = new VERT_FROM_FACE[NumFaces];
}




//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// Class destructor: Delete the arrays
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
D3DSmartCulling::~D3DSmartCulling()
{
    delete[] vert;
    delete[] vertMesh;

    delete[] vertFace;
    delete[] vertMeshFace;
}




//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// CheckCulling function: Checks if meshes or bounding boxes are outside the view frustum
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
BOOL D3DSmartCulling::CheckCulling( LPDIRECT3DDEVICE9 device )
{
    D3DXMATRIX matWorld, matView, matProj, matFinal;

    // Getting the transformation state matrices
    device->GetTransform( D3DTS_WORLD, &matWorld );
    device->GetTransform( D3DTS_VIEW, &matView );
    device->GetTransform( D3DTS_PROJECTION, &matProj );


    // Extracting zn and zf from the matProj matrix
    FLOAT zn = - matProj._43 / matProj._33;
    FLOAT zf = matProj._43 / (1.0f - matProj._33);
	
    BOOL outZnZf = TRUE;
	
    D3DXMatrixMultiply( &matFinal, &matWorld, &matView );

    for ( DWORD i = 0 ; i < NumVertices ; i++ )
    {
        D3DXVec3TransformCoord( &vert, &vertMesh, &matFinal );

        if ( vert.z >= zn && vert.z <= zf )
        {
            // There is at least one vertex between zn and zf view-planes
            outZnZf = FALSE;
            break;
        }
    }

    if ( outZnZf == TRUE )
        return FALSE;


    D3DXMatrixMultiply( &matFinal, &matFinal, &matProj );

	
    for ( i = 0 ; i < NumVertices ; i++ )
    {
        D3DXVec3TransformCoord( &vert, &vertMesh, &matFinal );

        // Checking if some vertex is inside the frustum
        if ( vert.x >= -1.0f && vert.x <= 1.0f &&
             vert.y >= -1.0f && vert.y <= 1.0f )
        {
            // There is at least one vertex inside the frustum
            return TRUE;
        }
    }

    for ( DWORD face = 0; face < NumFaces ; face++ )
    {
        D3DXVec3TransformCoord( &vertFace[face].v1, &vertMeshFace[face].v1, &matFinal );
        D3DXVec3TransformCoord( &vertFace[face].v2, &vertMeshFace[face].v2, &matFinal );
        D3DXVec3TransformCoord( &vertFace[face].v3, &vertMeshFace[face].v3, &matFinal );

        // Checking intersection at left-bottom edge of the frustum
        if ( D3DXIntersectTri( &vertFace[face].v1,
                               &vertFace[face].v2,
                               &vertFace[face].v3,
                               &D3DXVECTOR3( -1.0f, -1.0f, -10.0f ),
                               &D3DXVECTOR3( 0.0f, 0.0f, 1.0f ),
                               NULL, NULL, NULL ) == TRUE )
            return TRUE;
	
        // Checking intersection at left-top edge of the frustum
        if ( D3DXIntersectTri( &vertFace[face].v1,
                               &vertFace[face].v2,
                               &vertFace[face].v3,
                               &D3DXVECTOR3( -1.0f, 1.0f, -10.0f ),
                               &D3DXVECTOR3( 0.0f, 0.0f, 1.0f ),
                               NULL, NULL, NULL ) == TRUE )
            return TRUE;
		
        // Checking intersection at right-top edge of the frustum
        if ( D3DXIntersectTri( &vertFace[face].v1,
                               &vertFace[face].v2,
                               &vertFace[face].v3,
                               &D3DXVECTOR3( 1.0f, 1.0f, -10.0f ),
                               &D3DXVECTOR3( 0.0f, 0.0f, 1.0f ),
                               NULL, NULL, NULL ) == TRUE )
            return TRUE;
		
        // Checking intersection at right-bottom edge of the frustum
        if ( D3DXIntersectTri( &vertFace[face].v1,
                               &vertFace[face].v2,
                               &vertFace[face].v3,
                               &D3DXVECTOR3( 1.0f, -1.0f, -10.0f ),
                               &D3DXVECTOR3( 0.0f, 0.0f, 1.0f ),
                               NULL, NULL, NULL ) == TRUE )
            return TRUE;
    }

    // The mesh is completely outside view the frustum
    return FALSE;
}


How to use D3DSmartCulling: 1) Declare your bounding mesh. For example: D3DSmartCulling *BoundMesh = NULL; 2) In initalizations: BoundMesh = new D3DSmartCulling( pDevice, mesh, TRUE ); If the 3th parameter were TRUE, D3DSmartCulling will generate a bounding box for the culling check. If it were FALSE, D3DSmartCulling will consider the mesh for the culling check. 3) Finally, call: BoundMesh->CheckCulling(pDevice); immediately before rendering the mesh. CheckCulling function will return FALSE if the BoundMesh is outside the view frustum (othewise, it will return TRUE). Also, you can apply any transformation (translation, rotation and scaling) on your mesh or on your camera, because the culling check considers the transformed objects. You can download a simple sample here. After downloading the file, please change its extension from "js" to "zip". Cheers.
Advertisement
Great! Nice work. Make sure that you wrap this post up into a page on your website, so that people know exactly how to use it, and why it works.

A couple weeks or so ago, I was developing a culling method called "projection occlusion". It was like D3DSmartCulling in that it projected the bounding box of an object into screen-space. However, it took it farther and used this data to test against the other bounding boxes, in screen-space. In this sense, it was a really quick occlusion culling, and no software rasterization (like HOM) was necessary.

However, I stumbled because I couldn't find a suitable method to tell if a convex mesh is completely inside of another convex mesh. A simple box test will not work, because when the vertices are projected to screen-space, the back end of each bounding box shrinks. Perhaps some quick per-triangle collision detection will work. Any other ideas?

Again, good job, I'm interested to see the next installment of the D3D series [smile]
Dustin Franklin ( circlesoft :: KBase :: Mystic GD :: ApolloNL )
Hi Dustin,
Very interesting... I had not thought in checking bounding box collision on the screen-space.

Quote:However, I stumbled because I couldn't find a suitable method to tell if a convex mesh is completely inside of another convex mesh. A simple box test will not work, because when the vertices are projected to screen-space, the back end of each bounding box shrinks. Perhaps some quick per-triangle collision detection will work. Any other ideas?

For bounding boxes, I have an idea [smile]:

When you generate the bounding box, store a copy of its vertices in an array. For example: V[0],v[1],...,v[7].

Now, based on the way how you labeled the vertices, define a left-handed coordinate system for the bounding box. For example:

origin = V[0]
X-axis = V[1] - V[0] // Well, this is just a example. The axes could be defined by
Y-axis = V[2] - V[0] // other vertices. As I said, it depends on the way you labeled them.
Z-axis = V[3] - V[0] // In this sample, you don't need to normalize the axes.

Keep this order in mind (note the origin is at a corner of the bound. box).

At each frame, transform the vertices of the other bounding boxes to the space of the current bounding box. For that, you could take advantage of the D3DXMatrixLookAtLH function.

For example:

D3DXMATRIX mat;
D3DXMatrixLookAtLH( &mat, &V[0], &[3], &(V[2]-V[1]) );

(Notice that the vectors passed in D3DXMatrixLookAtLH respect the order defined for the coord. system)

To facilitate the explanation, let's labeled the current bounding box as A and another bounding box as B. So, transforming the vertices:

D3DXVec3TransformCoord( &W[0], &W[0], &mat ); // W[0] represents a vertex from B

Now check if W[0] is inside the A:

if ( W[0].x < D3DXVec3Length( &(V[1]-V[0]) ) && W[0].x > 0.0f
&& W[0].y < D3DXVec3Length( &(V[2]-V[0]) ) && W[0].y > 0.0f
&& W[0].z < D3DXVec3Length( &(V[3]-V[0]) ) && W[0].z > 0.0f )
{
// W[0] is inside the A
}

Repeat this check with the other vertices from B. If all the vertices from B are inside the A, then the B bounding box is completely inside the A bounding box.

Well, I didn't test that. But I think it works [wink].
is casting rays from the corners of the view frustum really any faster than the 'already pretty damn fast' frustum checks that we have?

Or is the purpose of your point to demonstrate that we can do frustum culling on actual meshes, rather than their assoicative (sometimes grossly off base) bounding containers?

~Min
==Colt "MainRoach" McAnlisGraphics Engineer - http://mainroach.blogspot.com
A friendly tip... why use a lowpoly mesh, that feels like a lot of overhead CPU-usage... as probably 80-90% of all the points will never matter as other points has already made their existence meaningless.

When I want more accurate culling I simply extend the box by 8 additional points or so... that is all it takes to get a very accurate culling... E.g. your 2D-ship down there can easily be done in 6 points and get 95% of your accuracy.

And with my AMD 2400XP+ I can check about 30-40 million points per second.

And isn't vertex and matrix transformations pretty costy?

Great initiative either way, thumbs up!


Your post assumes that the bounding boxes are already transformed into screen-space, correct? I've made a little diagram just so we can establish how my vertices are ordered:



Would our matrix be:
D3DXMatrixLookAtLH( &mat, &V[0], &V[5], &(V[2]-V[3]))?
Dustin Franklin ( circlesoft :: KBase :: Mystic GD :: ApolloNL )
Quote:is casting rays from the corners of the view frustum really any faster than the 'already pretty damn fast' frustum checks that we have?

Or is the purpose of your point to demonstrate that we can do frustum culling on actual meshes, rather than their assoicative (sometimes grossly off base) bounding containers?

Hi duhroach,
The purpose was just to demonstrate a way to compute frustum culling using irregular meshes. I don't know how fast are those rays, mainly because the D3DXIntersectTri computes more stuffs than I need. That is, I just need to check the ray-tri intersection (not the barycentric coordinates, nor the intersection distance). Personally, I think the SDK Cull method is faster. In fact, D3DSmartCulling was not optimized. But if we use it moderately, it can be very useful for some irregular meshes. And why not to combine both methods?![wink]

Note:
Mathematical calculations are tremendously fast. Unless we check a lot of "heavy" meshes, the consumed time is not very significant.


Quote:A friendly tip... why use a lowpoly mesh, that feels like a lot of overhead CPU-usage... as probably 80-90% of all the points will never matter as other points has already made their existence meaningless.

When I want more accurate culling I simply extend the box by 8 additional points or so... that is all it takes to get a very accurate culling...

Hi Syranide,
It depends of your application. Last year, I built a scenery composed by many irregular trees and, definitively, using bounding boxes was not a good idea (even combining them). Also, if you have a thin model that is not aligned with an world axis, the bounding boxes generated by Direct3D could not be appropriate, since it considers the min and max coordinates in world space. In this case, it would be better to model the bounding box.

Quote:E.g. your 2D-ship down there can easily be done in 6 points and get 95% of your accuracy.

That spaceship is 3D. Sorry, I was lazy to draw a 3D bounding mesh [embarrass]. It was just an illustration example. Well, I have to disagree you can get 95% of accuracy with only 6 points. Think in a big model, 10-20% percentage could represent an important blank space.

Quote:And isn't vertex and matrix transformations pretty costy?

Vertex and matrix transformations are linear operations, and can be processed very quickly. They are "nothing" compared to big textures, alpha-blending, antialiasing processing.

[Edited by - adriano_usp on March 3, 2005 12:49:21 PM]
Quote:Your post assumes that the bounding boxes are already transformed into screen-space, correct?

Not exactly. Since the boxes have few vertices, I thought to make this test as being the first test (just to check if there is a bounding box completely inside another). The other tests are made into screen-space.

The vertex coordinates of B bounding box are initially expressed relative to the world coordinate system. What that code does is to express these coordinates relative to the coordinate system from A bounding box. It would be, more or less, as A bounding box becomes a "frustum" with an ortho projection, and you test if B is completely inside this "frustum".

Quote:Would our matrix be:
D3DXMatrixLookAtLH( &mat, &V[0], &V[5], &(V[2]-V[3]))?


Yes, but pEye parameter must be V[1]:

D3DXMatrixLookAtLH( &mat, &V[1], &V[5], &(V[2]-V[3]) )

pEye = origin = V[1]
pLookAt = target = V[5]
pUp = Y-axis = V[2]-V[3] = V[0]-V[1] = V[4]-V[5] = V[6]-V[7]
Quote:Original post by adriano_usp
...
The "insight" of the D3DSmartCulling is to work on the projection space (instead of working on the world space). ...


Can you explain what makes this faster than checking for intersection in world space? Mathematically, the process looks the same to me.
John BoltonLocomotive Games (THQ)Current Project: Destroy All Humans (Wii). IN STORES NOW!
Quote:Original post by JohnBolton
Quote:Original post by adriano_usp
...
The "insight" of the D3DSmartCulling is to work on the projection space (instead of working on the world space). ...


Can you explain what makes this faster than checking for intersection in world space? Mathematically, the process looks the same to me.


Sorry my English... it is really horrible. I didn't want to say that it is faster than checking for intersection in world space, but I think it is easier, at least to understand how the method works. See my reply for duhroach.
It is not my intention to substitute the SDK method, but to complement it in some cases.

This topic is closed to new replies.

Advertisement