Solution to culling issues?

This is a discussion on Solution to culling issues? within the Game Programming forums, part of the General Programming Boards category; Many of you have seen my terrain examples and you know it was plagued with culling problems. I think I've ...

  1. #1
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,597

    Solution to culling issues?

    Many of you have seen my terrain examples and you know it was plagued with culling problems.

    I think I've come up with a reason for the algorithm failing.

    The frustum is computed by combining the matWorldView and matWorldProj matrices. This means the frustum is being computed in world space. So if I just send the vertex positions of the terrain to the cull function, it won't be correct.

    Here is why. The terrain is not transformed into world space. It is assumed to always lie at 0,0,0 or the center of the entire world. I assumed this meant the terrain vertices were in world space when in fact they are in object space, not world space. It would be no different than having a huge flat grid and not transforming it to world space.

    So how do I transform the terrain vertices to world space w/o always having the terrain centered around the camera at the same place? Also since the terrain is the world, is there a need to transform the terrain to world space and then can I assume my vertices are in world space?

    The clipping still causes issues at the edges of the screen with viewing changes of 20 degrees or more on any axis. This is not desireable but all the sources I've checked state the algo I'm using should actually still render those objects which may actually lie outside of the frustum.

    My culling algo is too perfect and needs some work. Any help or ideas is greatly appreciated. I've downloaded over 30 documents concerning this, bought 3 new books, and still having problems.

    Sites to check out:
    http://www.realtimerendering.com/
    http://www.geometrictools.com/Intersection.html
    http://www.toymaker.info/Games/html/..._faq.html#D3D6
    http://www.flipcode.com/articles/art...mculling.shtml
    http://www.lighthouse3d.com/opengl/viewfrustum/
    http://research.microsoft.com/~hoppe/
    http://www.vterrain.org/
    http://personal.inet.fi/atk/cxengine/docs/issue2.html

    This was taken from an article explaining how to extract the planes for the frustum in D3D w/o using D3DXPLANE. I have another source that explains how to do it using D3DXPLANE.

    Until now we have assumed that both, the world and the view matrix are identity matrices. However, the goal
    obviously is to make the algorithm work for an arbitrary view. This is, in fact, so easy that itís almost unbelievable.
    If you think about it for a moment then youíll immediately understand it, and thatís why we are not going to explain
    this in any great detail. All we are giving to you is this:
    1. If the matrixMis equal to the projection matrix P (i.e., = M P), then the algorithm gives the clipping planes
    in view space (i.e., camera space).
    2. If the matrixMis equal to the combined view and projection matrices, then the algorithm gives the clipping
    planes in world space (i.e., = ⋅ M V P, where V is the view matrix, and P is the projection matrix).
    3. If the matrix Mis equal to the combined world, view, and projection matrices, then the algorithm gives the
    clipping planes in object space (i.e., = ⋅ ⋅ M W V P, where Wis the world matrix, V is the view matrix, and
    P is the projection matrix).
    4. and so on...
    The only code I can come up with to perform this operation is:

    Code:
    void Terrain::Render(float fTimeDelta,D3DXVECTOR3 vecCameraPos,D3DXMATRIX &matView,D3DXMATRIX &matProj)
    {
      D3DXMATRIX matTrans;
    
      D3DXMatrixTranslation(&matTrans,-vecCameraPos.x,-vecCameraPos.y,-vecCameraPos.z);
    
      m_pDevice->SetTransform(D3DTS_WORLD,&matTrans);
    
      m_pFrustum->Compute(&matView,&matProj);
      RenderNodes(m_pRoot);
    }
    
    
    void Terrain::RenderNodes(TerrainNode *pNode)
    {
      static bool bCullCheck=true;
    
      int iResult=CULL_IN;
    
      if (bCullCheck) iResult=m_pFrustum->CullAABB(pNode->vecMin,pNode->vecMax);
    
      //Bail on this branch if out
      if (iResult==CULL_OUT) return;
    
      if (iResult==CULL_IN || iResult==CULL_INTERSECT)
      {
         if (pNode->m_iType==QUAD_LEAF)
         {
            //Render geometry
            bCullCheck=true;
         }
         else
         {
            //If parent is in, children are definitely in
              
            if (iResult==CULL_IN) 
            {
               bCullCheck=false;
            } else bCullCheck=true;
            RenderNodes(pNode->UL);
            RenderNodes(pNode->UR);
            RenderNodes(pNode->LL);
            RenderNodes(pNode>LR);
         }
      }
    }
    This does not check to see if the camera is inside of the frustum and does not check to see if the frustum can actually contain the bounding volume.
    Last edited by VirtualAce; 03-10-2006 at 05:31 AM.

  2. #2

    Join Date
    May 2005
    Posts
    1,041
    If I recall correctly the box in frustum test you are using uses the minimum and maximums of the bounding box to compute the effective offset against each frustum plane, which, when dotted with each frustum plane normal gives the effective 'radius' of the bounding box. Try using this method, it's a bit more towards brute force/uglier (manually tests all eight points on the bounding box), but just give it a shot.

    Also, I know that you've got the theory down correctly for computing the frustum planes, but what about the frustum plane distances?

    Note that this doesn't differentiate between 'cull_out' (when the box is totally outside the frustum) and 'intersect' (when the box may span one or more frustum planes).

    I'm guessing that the generation of the AABB for the terrain nodes is so trivial that that could not possibly be the problem.

    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
    }
    Last edited by BobMcGee123; 03-10-2006 at 07:07 AM.
    I'm not immature, I'm refined in the opposite direction.

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,597
    The way I'm creating the bounding volumes is a bit strange because while creating the quadtree, I do not know the exact lowest Y value and exact highest Y value.

    So I use FLT_MAX and FLT_MIN for those nodes. For a leaf node I do this:

    Code:
    float fMinY=FLT_MAX;
    float fMinX=FLT_MIN;
    
    for (int z=...;...;...)
    {
      for (int x=...;...;...)
      {
         ...
         if (Vertices[dwOffset].y<fMinY) fMinY=Vertices[dwOffset].y;
         if (Vertices[dwOffset].y>fMaxY) fMaxY=Vertices[dwOffset].y;
    
       }
    }
    
    pNode.vecMax=D3DXVECTOR3(EndX,fMaxY,EndZ);
    pNode.vecMin=D3DXVECTOR3(StartX,fMinY,StartZ);
    The only problem is this:

    In Direct3D, up on the screen is positive Y and into the screen is positive Z. Therefore the max Y is really the top and the min Y is really the bottom. As well the min Z is really the far Z of the quad and the min Z is the near Z of the quad.

    This may be causing problems, but my frustum computation should still work considering I'm computing the frustum from matrices that exhibit this very same behavior.

    Code:
    void Compute(D3DXMATRIX *matProj,D3DXMATRIX *matView)
        {
          D3DXMATRIX matComb;
          D3DXMatrixMultiply(&matComb, matView, matProj);
    
          // Left clipping plane
          m_Planes[0].m_Normal.x = matComb._14 + matComb._11; 
          m_Planes[0].m_Normal.y = matComb._24 + matComb._21; 
          m_Planes[0].m_Normal.z = matComb._34 + matComb._31; 
          m_Planes[0].m_fDistance = matComb._44 + matComb._41;
    
          // Right clipping plane 
          m_Planes[1].m_Normal.x = matComb._14 - matComb._11; 
          m_Planes[1].m_Normal.y = matComb._24 - matComb._21; 
          m_Planes[1].m_Normal.z = matComb._34 - matComb._31; 
          m_Planes[1].m_fDistance = matComb._44 - matComb._41;
    
          // Top clipping plane 
          m_Planes[2].m_Normal.x = matComb._14 - matComb._12; 
          m_Planes[2].m_Normal.y = matComb._24 - matComb._22; 
          m_Planes[2].m_Normal.z = matComb._34 - matComb._32; 
          m_Planes[2].m_fDistance = matComb._44 - matComb._42;
    
          // Bottom clipping plane 
          m_Planes[3].m_Normal.x = matComb._14 + matComb._12; 
          m_Planes[3].m_Normal.y = matComb._24 + matComb._22; 
          m_Planes[3].m_Normal.z = matComb._34 + matComb._32; 
          m_Planes[3].m_fDistance = matComb._44 + matComb._42;
    
          // Near clipping plane 
          m_Planes[4].m_Normal.x = matComb._13; 
          m_Planes[4].m_Normal.y = matComb._23; 
          m_Planes[4].m_Normal.z = matComb._33; 
          m_Planes[4].m_fDistance = matComb._43;
    
          // Far clipping plane 
          m_Planes[5].m_Normal.x = matComb._14 - matComb._13; 
          m_Planes[5].m_Normal.y = matComb._24 - matComb._23; 
          m_Planes[5].m_Normal.z = matComb._34 - matComb._33; 
          m_Planes[5].m_fDistance = matComb._44 - matComb._43; 
    
          //Normalize only if ever testing spheres
          //Disabled for now -> using TEST_AABB
          if ((m_iTestMode && TEST_SPHERE)==TEST_SPHERE)
          {
            for (int i=0;i<6;i++)
                   m_Planes[i].Normalize();
          }
          
          vMin.x=m_Planes[LEFT_PLANE].m_Normal.x;
          vMin.y=m_Planes[TOP_PLANE].m_Normal.y;
          vMin.z=m_Planes[FAR_PLANE].m_Normal.z;
          
          vMax.x=m_Planes[RIGHT_PLANE].m_Normal.x;
          vMax.y=m_Planes[BOTTOM_PLANE].m_Normal.y;
          vMax.z=m_Planes[NEAR_PLANE].m_Normal.z;
          
        }

    Then, instead of testing all eight corners of the box I use the P and N vertices method.

    Code:
    WORD CullBox(D3DXVECTOR3 &min,D3DXVECTOR3 &max)
        {
          
          bool bIntersect=false;
    
          WORD result=CULL_IN;
          
          D3DXVECTOR3 n;//(max.x,max.y,max.z);
          D3DXVECTOR3 p;//(min.x,min.y,min.z);
                
          for (WORD i=0;i<6;i++)
          {
          
            if (m_Planes[i].m_Normal.x >= 0.0f)
            {
              n.x = min.x;
              p.x=  max.x;
       
            }
            else
            {
              n.x=max.x;
              p.x=min.x;
            }
    
            if (m_Planes[i].m_Normal.y >= 0.0f)
            {
              n.y=min.y;
              p.y=max.y;
            }
            else
            {  
              n.y=max.y;
              p.y=min.y;
            }
    
            if (m_Planes[i].m_Normal.z >= 0.0f)
            {
              n.z=min.z;
              p.z=max.z;
              
            }
            else
            {
              n.z=max.z;
              p.z=min.z;
            }
       
            if (m_Planes[i].DistanceToPoint(&p) < 0.0f) return CULL_OUT;
            
            if(m_Planes[i].DistanceToPoint(&n) <= 0.0f) 
              result= CULL_INTERSECT;
            
          }
    
          return result;
          
        }
    Last edited by VirtualAce; 03-11-2006 at 12:16 AM.

  4. #4

    Join Date
    May 2005
    Posts
    1,041
    >>I do not know the exact lowest Y value and exact highest Y value.

    Something to do with the heightmap I'm guessing?

    >>Then, instead of testing all eight corners of the box I use the P and N vertices method.

    I know that, but I wanted you to try testing all 8 corners (just convert the code I posted) to see if it exhibits the exact same behavior.

    You really should normalize the frustum all of the time, and when you call m_Planes[i].Normalize() does it also divide the plane distance by the length of the normal vector?
    Last edited by BobMcGee123; 03-11-2006 at 08:57 AM.
    I'm not immature, I'm refined in the opposite direction.

  5. #5

    Join Date
    May 2005
    Posts
    1,041
    I am curious to find out if you've fixed the problem. In hindsight, I suspect the problem is just because you weren't normalizing the frustum.
    I'm not immature, I'm refined in the opposite direction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 'Solution' and 'Project' usage in VC++
    By C+/- in forum C++ Programming
    Replies: 2
    Last Post: 01-13-2007, 09:50 AM
  2. Solution to earlier quad-tree culling
    By VirtualAce in forum Game Programming
    Replies: 3
    Last Post: 08-10-2006, 09:04 PM
  3. anyone know the solution?
    By heeroyung in forum C Programming
    Replies: 15
    Last Post: 09-30-2005, 07:46 AM
  4. My Unix/Linux SECURITY SOLUTION - pls read
    By bjdea1 in forum Linux Programming
    Replies: 3
    Last Post: 04-11-2004, 10:28 PM
  5. Replies: 11
    Last Post: 03-25-2003, 05:13 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21