Thread: Frustum cull is too accurate

  1. #1
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607

    Frustum cull is too accurate

    I finally have some frustum culling code working but it is very accurate. It's so accurate that when you move or make changes to the frustum, some of the edge triangles disappear. Quite odd.

    Is there a way to fix this? It's only during movement this happens. On the next frame, the frustum is restored and everything looks fine.

    The culling works very good, however.

    Code:
    WORD Cull(D3DXVECTOR3 &min,D3DXVECTOR3 &max)
        {
          
          bool bIntersect=false;
    
          WORD result=0;
          
          D3DXVECTOR3 n(min.x,min.y,min.z);
          D3DXVECTOR3 p(min.x,min.y,min.z);
                
          for (WORD i=0;i<6;i++)
          {
          
            if (m_Planes[i].m_Normal.x <= 0)
            {
              n.x = max.x;
              p.x=  min.x;
       
            }
            else
            {
             n.x=min.x;
             p.x=max.x;
            }
    
            if (m_Planes[i].m_Normal.y <= 0)
            {
              n.y=max.y;
              p.y=min.y;
            }
            else
            {  
              n.y=min.y;
              p.y=max.y;
            }
    
            if (m_Planes[i].m_Normal.z <= 0)
            {
              n.z=max.z;
              p.z=min.z;
              
            }
            else
            {
              n.z=min.z;
              p.z=max.z;
            }
       
            if (m_Planes[i].DistanceToPoint(&p) < 0)
            {
              
              return CULL_OUT;
            }
    
            if (m_Planes[i].DistanceToPoint(&n) >= 0) 
            {
              bIntersect=true;
            }
          
          
          }
    
          if (bIntersect)  
          {
            return CULL_INTERSECT;
          } else return CULL_IN;
          
          
        }
    This is a modification of some code I found on the net that wasn't working correctly. So I fixed it and it works very well. If you understand the theory I'm simply finding the positive and negative vertices of an axis-aligned bounding box in world space. If the positive vertex of the AABB is on the wrong side of the frustum plane, then I do an early out since this box is outside of the frustum.

    In my code I found it takes more time to actually clip and intersected volume than it does just to send the vertices to the hardware and let it clip them. So if the result is CULL_IN or CULL_INTERSECT, I simply draw the object. For a quad tree terrain system I'm working on if the result is CULL_INTERSECT then I will recurse deeper into the tree and test each child node until I reach a leaf at which point the vertices in the leaf will be drawn.

    But this issue of watching tri's disappear while moving toward the terrain in the vertical, or yawing left or right is not cool. It does not happen when you are moving away from the terrain in the vertical.

    The current system is not using the quadtree, but it is ready for it.

    This system can do sphere intersection tests, AABBs (and soon OB's using a nice transform from Moller and Haines), and points.
    This terrain is culling on per-cell basis or two triangles at once. Perhaps that is why it is getting fragged at the edges?

  2. #2
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    As you can see though, the terrain culls correctly which I'm quite happy with.

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    And this one is looking nearly straight down. Check out the number of triangles as opposed to the previous pic.

    Unfortunately with this non-quadtree system shown here, I can't take advantage of vertex buffers and index buffers because I don't know how many vertices will be in any one frame.

    This terrain is drawn with DrawPrimitiveUP with the following vertex structure.

    Code:
    struct TerrainVertex
    {
      D3DXVECTOR3   Pos;
      D3DCOLOR      Diffuse;
      D3DCOLOR      Specular;
    
      float         TextureU,TextureV;
      float         DetailTexU,DetailTexV;
      float         LightU,LightV;
      
      
    
      static const DWORD FVF;
    
      TerrainVertex(void):Pos(D3DXVECTOR3(0.0f,0.0f,0.0f)),
                              TextureU(0.0f),TextureV(0.0f),
                              DetailTexU(0.0f),DetailTexV(0.0f),
                              LightU(0.0f),LightV(0.0f) {}
      TerrainVertex(D3DXVECTOR3 pPos,float u,float v,
                    float du=0.0f,float dv=0.0f):
                    Pos(pPos),TextureU(u),TextureV(v),
                    DetailTexU(du),DetailTexV(dv) {}
      TerrainVertex(float x,float y,float z,float tu,float tv):
                    Pos(D3DXVECTOR3(x,y,z)),TextureU(tu),TextureV(tv) {}
    
    };
    The lightmap is pre-computed by the program based on the heightmap.
    Last edited by VirtualAce; 01-23-2006 at 12:10 PM.

  4. #4

    Join Date
    May 2005
    Posts
    1,042
    You can only totally cull a box (and its subsequent contents) when *all* of the points on the box lay behind the *same* plane.

    Code:
    int		Frustum::BBInFrustum(Vector3	&mins, Vector3	&maxs)
    {
    	for(int i = 0; i < 6; i++)
    	{
    		if((mFrustum[i].Normal.x * mins.x + mFrustum[i].Normal.y * mins.y + mFrustum[i].Normal.z * mins.z)>=mFrustum[i].Dist) continue;
    		if((mFrustum[i].Normal.x * maxs.x + mFrustum[i].Normal.y * mins.y + mFrustum[i].Normal.z * mins.z)>=mFrustum[i].Dist) continue;
    		if((mFrustum[i].Normal.x * mins.x + mFrustum[i].Normal.y * maxs.y + mFrustum[i].Normal.z * mins.z)>=mFrustum[i].Dist) continue;
    		if((mFrustum[i].Normal.x * maxs.x + mFrustum[i].Normal.y * maxs.y + mFrustum[i].Normal.z * mins.z)>=mFrustum[i].Dist) continue;
    		if((mFrustum[i].Normal.x * mins.x + mFrustum[i].Normal.y * mins.y + mFrustum[i].Normal.z * maxs.z)>=mFrustum[i].Dist) continue;
    		if((mFrustum[i].Normal.x * maxs.x + mFrustum[i].Normal.y * mins.y + mFrustum[i].Normal.z * maxs.z)>=mFrustum[i].Dist) continue;
    		if((mFrustum[i].Normal.x * mins.x + mFrustum[i].Normal.y * maxs.y + mFrustum[i].Normal.z * maxs.z)>=mFrustum[i].Dist) continue;
    		if((mFrustum[i].Normal.x * maxs.x + mFrustum[i].Normal.y * maxs.y + mFrustum[i].Normal.z * maxs.z)>=mFrustum[i].Dist) continue;
    		return 0; //box is completely behind a single frustum plane and should not be drawn
    	}
    	
    	return 1; //enough (or all) of the box is in frustum and should be drawn
    }
    I update the frustum planes by taking the matrix product between the modelview matrix and the projection matrix (I do some hacks to make it faster but that is the basic theory).
    I'm not immature, I'm refined in the opposite direction.

  5. #5
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    What your seeing is a correct result of your implementation (as Bob pointed out). Because 1 or more vertex is outside the frustum, the entire triangle is not rendered.

    An alternative is to clip the bordering triangles against the plane of the frustum, but Bob's suggestion is much more simple (its the approach I take as well)

  6. #6

    Join Date
    May 2005
    Posts
    1,042
    The screenshots look good by the way. Keep up the good work.

    Upon re-reading your post, I don't think our posts actually helped any (I'm waiting for your update). You say you are doing the drawing when it is intersected or cull in, which is the way it should be done to get proper results.

    I looked over the code, and I understand what is going on (it achieves the same results as what I posted, but it's just basically more efficient).

    Also, about using that code above for doing an oriented bounding box: if you have the orientation matrix of the box, you can just apply its inverse to the box (returning it to an AABB) and to the frustum planes. I'm not sure if/how a 4x4 homogenous matrix would take care of the frustum plane distances, so you might have to recompute the frustum plane distances (perspective would probably know the exact answer to this).

    EDIT:
    Erm, I think you'd just have to plug in <0, 0, 0, -1> in the fourth column (fourth row for you assbackwards Direct3D people) for the translational component of the inverse matrix, and apply it to the <X,Y,Z, d> of each frustum plane.
    Last edited by BobMcGee123; 01-23-2006 at 04:32 PM.
    I'm not immature, I'm refined in the opposite direction.

  7. #7
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    /applaud

    Are you using normal maps on the terrain?

  8. #8
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Well I've thought about this a lot and perhaps culling based on 3D bounding volumes for simple terrain triangles and/or quads is overkill. Since a terrain is simply composed of triangles which are composed of 3 points then the following is true.

    Since any three points in space are guaranteed to be co-planar, it would make more sense to send the three vertices of the triangle to the cull system, only use the point-in-frustum code instead of the box in frustum code. I would simply test the 3 vertices which would reduce the computations by at least 50% for all triangles. After all a bounding box test is ideally used when more complex geometry is contained in the volume. Thus if the volume is rejected, then so are the 10000 triangles inside of it. But my bounding boxes do not contain large amounts of vertices.

    I will change the code to test the 3 vertices for each triangle. As Bob pointed out the system I'm using is a fast way to determine if a volume is inside, intersecting, our completely out of the frustum. It is not necessary to test all 8 corners at all times. If the positive vertex (the one in the direction of the normal) is out, then the box is out. There is another faster method using a huge inequality and testing against all 6 planes in one if(). However, I've not implemented it yet.

    The big slow down right now is iterating through the vertices. But my approach is unique in that these vertices are NOT pre-created. They are created on the fly which enables me to use a quad tree to simply narrow in on the world coordinate "area" that the camera is in, create the vertices and tri's and then cull those against the frustum. Using this and using the camera Z as the back side of the 'area' should result in 60% of the geometry as being always inside of the frustum and about 40% guaranteed to be out.

    As always I'm looking for speed here and I'm finding out, as always, that this really isn't as hard as people made it. In fact, once you have a good culling system down pat, adding objects to your world is rather simple. I could see how a game could be made provided you had all the foundations laid correctly.

    Amazing that these few lines of code are so powerful. They really make a difference in the performance of the engine.

    No I'm not using a normal map, I'm pre-computing a light map based on the height map. Once you set the height map, it then creates a light map to go along with it based on the light direction you pass to the function. I'm also looking at creating a pre-computed shadow map. I've tested the system by continally updating the light map every frame and it actually worked very well. So I could still do real-time lighting because the sun or light source does not move very fast. So when it does move, re-calc the light map and the shadow map for the current terrain section and wallah - real time, pixel-perfect lighting.
    The computation of the light map as it is now is extremely fast.
    Also if I was doing this for a game, I would fire off a thread to update the light and shadow maps. It might cause a problem say if the player was firing a projectile at another object/player, but the lag time would be very minimal.

    I can't believe how fast these computers are. My code is doing about 30000 multiplies and 15000 adds and it just screams. We've come a long way eh?
    Last edited by VirtualAce; 01-24-2006 at 12:17 AM.

  9. #9

    Join Date
    May 2005
    Posts
    1,042
    >> Well I've thought about this a lot and perhaps culling based on 3D bounding volumes for simple terrain triangles and/or quads is overkill.

    Why? This is what a quad tree does, you just need to balance the proper number of polygons per leaf node


    >> only use the point-in-frustum code instead of the box in frustum code.
    No, all of the points can be outside the frustum, but the triangle can still intersect the volume and be visible...per polygon culling is *def* overkill

    >>So when it does move, re-calc the light map and the shadow map for the current terrain section and wallah - real time, pixel-perfect lighting.

    cool



    >>I can't believe how fast these computers are. My code is doing about 30000 multiplies and 15000 adds and it just screams. We've come a long way eh?

    Yeah, I remember my first computer (pentium MMX 166MHz with like 4mb integrated video, 32mb system ram *upgraded* to 64mb!!!! holy ........!!!).
    I'm not immature, I'm refined in the opposite direction.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Ok totally new render system.

    Culling terrain exactly is too time consuming. So here is what I'm going to do.

    Since the hardware can cull faster than I can at the triangle level I'll let it do just that.
    When I create the terrain from a huge heightmap i will recursively divide it into smaller sections. However the main mesh will be a simple ID3DXMesh interface. The other meshes will be a part of this mesh, but they will only need to store their subset value. Each section of terrain will have a bounding volume to cull it against the frustum. If the terrain is visible or intersecting I just call TerrainMesh->DrawSubset(CurSubset). Each terrain section has a position in world space and the main mesh has a D3DXVECTOR3 wrap vector. This wrap vector will enable me to repeat the terrain infinitely so you never fall off the world.

    This method does not provide CLOD but I would like to get it working before I tackle the CLOD.

  11. #11

    Join Date
    May 2005
    Posts
    1,042
    I'm getting confused, you are just talking about implementing some sort of spatial partitioning right? (what you are describing doesn't seem different from quad/octree culling, unless i'm totally missing something here)


    Just as long as you get it to work and run fast. Keep us updated, seems like you're figuring things out on your own.

    By the way, I sent you another PM a couple days ago, dunno if you received it or not.

    g'luck
    I'm not immature, I'm refined in the opposite direction.

  12. #12
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Well I'm sort of figuring it out as I go along. The system I was describing was not a quad tree in the literal sense. But it does the same thing. However I cannot create one large terrain in a mesh. There is a limit to how many vertices you can store in a mesh. So I will move to a pure quadtree setup where each node has a bounding volume and an ID3DXMesh which represents that portion of terrain. It is a major pain in the rump doing it this way because I must keep track of both the world space coords as well as the map space when I do the quad tree.

    And I have another issue. When I create these little zones of terrain, should I set the vertices in the zone to be centered around 0,0,0 in it's local space, or should I set them to world coordinates?

    For instance for local space:

    Code:
    void CreateTree(TerrainNode *pNode,float World[4],int Map[4],float fDesiredSize)
    {
      TerrainNode *newNode=new TerrainNode;
      newNode->pParent=pNode;  
    
      float fWorldMidX=(World[0]-World[2])*0.5f;
      float fWorldMidZ=(World[1]-World[3])*0.5f;
    
      //Set bounds
      ...
    
      //Check for leaf condition
      if (World[2]-World[0]>=fDesiredSize)
      {
       newNode->iType=QUAD_LEAF;
    
        float fLocalX=World[0]-fWorldMidX;
        float fLocalZ=World[1]-fWorldMidZ;
        float fLocalX2=World[2]-fWorldMidX;
        float fLocalZ2=World[3]-fWorldMidZ;
    
        //Generate vertices from fLocalX,fLocalZ to fLocalX2,fLocalZ2
        ...
        return;
      }
    
      newNode->iType=QUAD_NODE;
    
      ...
      ...
    };
    And then I would translate this zone of terrain using:

    Code:
    ....
    D3DXMATRIX trans;
    D3DXMatrixTranslation(&trans,Zone[i].Pos.x,Zone[i].Pos.y,Zone[i].Pos.z);
    
    Render(Zone[i]);

  13. #13

    Join Date
    May 2005
    Posts
    1,042
    >>When I create these little zones of terrain, should I set the vertices in the zone to be centered around 0,0,0 in it's local space, or should I set them to world coordinates?

    Now keep in mind I've only actually implemented working binary space partitioning, which is typical for indoor stuff, but the concept is the same or similar when you've worked with any spatial partitioning system in depth. I see no reason to store anything but the world coordinates. The only purpose for creating the tree is so you know what leaf node the vertices belong to, so that you can cull stuff. This includes the mins/maxs of the bounding volumes.

    It seems like you mostly know what you are doing anyway, and if not you know what to try.
    I'm not immature, I'm refined in the opposite direction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quadtree and Frustum in OpenGL
    By sarah22 in forum Game Programming
    Replies: 2
    Last Post: 05-13-2009, 10:51 PM
  2. Screen Flicker
    By BobMcGee123 in forum Game Programming
    Replies: 9
    Last Post: 04-03-2007, 05:52 AM
  3. Replies: 11
    Last Post: 03-25-2003, 05:13 PM
  4. How do I create an accurate timer?
    By Quin in forum C Programming
    Replies: 1
    Last Post: 01-06-2002, 02:28 AM
  5. VERY accurate timing
    By Gherkin in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 09-28-2001, 04:30 PM