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.

Quote:

---

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.

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
}

---

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;
     
    }

---

>>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?

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.