Optimization: Speeding up terrain occlusion check

First, I'd like to thank Ben Garney and Nicolas Quijano who have volunteered to help me get several of the optimizations I mentioned in my .plan file into resources. These enhancements will get to the community much quicker due to their efforts.

On to business...

The trick to optimizing the occlusion check is to take advantage of the fact that if the check indicated that an object was occluded last time it will probably work the same this time (the camera didn't move that much) and if it didn't occlude last time it probably won't this time either. We will keep a counter on each object that constantly runs down. When it gets to zero, we will perform the occlusion check. If the check is succesful, we keep the counter at zero. If it isn't, then we reset the counter to some preset value (15 by default, but can be changed by setting $pref::SceneGraph::occlusionCount to some other value). This way, occluded objects are re-checked every frame, non-occluded objects are only re-checked occassionally.

Note that because the counter is not reset when the object is out of view, once one has done a 360 from a given location, the occluded items will continue to be checked when they are in view again. Similarly, when in a valley, objects outside the valley will be appropriately check as long as you stay in the valley.

This optimization saved us about 5% in ThinkTanks. If you have around 100 objects on your terrain, it might do the same for you.

In sceneGraph.h, right after "static F32 smVisibleDistanceMod;" add this line:
   static S32 smOcclusionCount;

In sceneObject.h, right after "U32 mContainerSeqKey;" add this line:
   S32 mOcclusionCount;

In SceneObject.cc, right after the line "Polyhedron sBoxPolyhedron;" add this line:
   S32 gOcclusionStagger = 0;

In SceneObject.cc, inside "SceneObject::SceneObject()" add:
   mOcclusionCount = ++gOcclusionStagger & 0x1F;

In SceneObject.cc, inside "void SceneObject::consoleInit()" add:
   Con::addVariable("pref::SceneGraph::occlusionCount", TypeS32,&SceneGraph::smOcclusionCount);

In SceneTraversal.cc, after the #include's, add:
   S32 SceneGraph::smOcclusionCount = 15;

In SceneTraversal.cc, in the "void SceneGraph::treeTraverseVisit()" method, between the SECOND occurrence of the line:
   obj->setTraverseColor(SceneObject::Black);
and the FIRST (only) occurrence of the line:
   obj->prepRenderImage(state, stateKey, 0xFFFFFFFF);
replace what is there with:

   if (getCurrentTerrain() != NULL && obj->getWorldBox().min.x > -1e5)
   {
      if (obj->mOcclusionCount==0)
      {
         bool doTerrCheck = true;
         SceneObjectRef* pRef = obj->mZoneRefHead;
         while (pRef != NULL)
         {
            if (pRef->zone != 0)
            {
               doTerrCheck = false;
               break;
            }
            pRef = pRef->nextInObj;
         }

         if (doTerrCheck == true && terrCheck(getCurrentTerrain(), obj, state->getCameraPosition()) == true)
         {
            // Note: leave obj->mOcclusionCount at 0 so we check next time (it was a good thing this time)
            return;
         }
         // don't check for a number of frames
         obj->mOcclusionCount = smOcclusionCount;
      }
      else
         // don't check this frame, but later...
         --obj->mOcclusionCount;
   }

A second optimization of this code is to re-write the terrCheck routine itself. If you look at what is happening there I think you will conclude, like I did, that it is indirect and maybe even a bit odd. I replaced it with the following straightforward code and found that I was able to occlude 15% more items (occluding more items is good, as long as they aren't false occlusions, which they didn't seem to be). It may be that with very large objects my new terrCheck routine will falsely occlude objects that the original won't. It warrants testing. Here is the code:

bool terrCheck(TerrainBlock* pBlock,
               SceneObject*  pObj,
               const Point3F camPos)
{
   Point3F localCamPos = camPos;
   pBlock->getWorldTransform().mulP(localCamPos);
   F32 height;
   pBlock->getHeight(Point2F(localCamPos.x, localCamPos.y), &height);
   bool aboveTerrain = (height <= localCamPos.z);

   if (!aboveTerrain)
      // Don't occlude if we're below the terrain.  This prevents problems when
      //  looking out from underground bases...
      return false;

   const Box3F& oBox = pObj->getObjBox();
   F32 minSide = getMin(oBox.len_x(), oBox.len_y());
   if (minSide > 85.0f)
      // too big to occlude (imagine big interior at the end
      // of a narrow valley).
      return false;

   const Box3F& rBox = pObj->getWorldBox();
   RayInfo rInfo;

   Point3F ul(rBox.min.x, rBox.min.y, rBox.max.z);
   pBlock->getWorldTransform().mulP(ul);
   if (!pBlock->castRay(localCamPos,ul,&rInfo))
      // didn't hit any terrain, we can see this
      return false;

   Point3F ur(rBox.min.x, rBox.max.y, rBox.max.z);
   pBlock->getWorldTransform().mulP(ur);
   if (!pBlock->castRay(localCamPos,ur,&rInfo))
      // didn't hit any terrain, we can see this
      return false;

   Point3F ll(rBox.max.x, rBox.min.y, rBox.max.z);
   pBlock->getWorldTransform().mulP(ll);
   if (!pBlock->castRay(localCamPos,ll,&rInfo))
      // didn't hit any terrain, we can see this
      return false;

   Point3F lr(rBox.max.x, rBox.max.y, rBox.max.z);
   pBlock->getWorldTransform().mulP(lr);
   if (!pBlock->castRay(localCamPos,lr,&rInfo))
      // didn't hit any terrain, we can see this
      return false;

   Point3F center = ul + lr;
   center *= 0.5f;
   if (!pBlock->castRay(localCamPos,center,&rInfo))
      // didn't hit any terrain, we can see this
      return false;

   // all five rays collided...consider this occluded
   return true;
}

Note that if all your objects were small (no interiors) one could
simplify this a bit more by reducing the number of terrain checks,
getting rid of the size restriction (85 meters, copied from the
original terrCheck routine) and even get rid of the aboveTerrain
restrictions.  But the above is meant to be the general case.