SpeedTree uses a grid/cell-based culling system that is efficient at culling very large forests (millions of instances). There are three steps involved in forest-level culling: i) set the correct camera view, ii) call the cull function which will provide a list of visible cells, iii) reporting the tree instances that appear in the provided cells as well as their LOD values based on the camera position.

During a SpeedTree integration, a common problem is getting the application's view matrices to work 100% with what the SDK expects. This where the CView class comes in. Once this class has been set up correctly, the rest of the culling procedures should fall into place. Details on the CView class are here.

There are two important types of objects at the forest level: base trees and instances. Base trees can also be referred to simply as “trees”. Base trees correspond to an SRT file loaded by the Core library. Instances are simply placements of a base tree. A base tree typically has multiple instances (in the hundreds or thousands is common). Each instance has a unique position, scale, and orientation (up and right vectors), but everything else is defined by the base tree.

Instances

The Forest library defines a structure for instances called SInstance, which is designed to house per-instance data for 3D tree instances, grass instances, and billboard instances as well match the format of the instance vertex buffer data for efficient CPU-to-GPU copying. It contains typical instance data like position, scale, and orientation, but it also contains two SpeedTree-specific LOD values.

struct SInstance
{
    // matches float4 ATTRO in instance vertex decl
    Vec3               m_vPos;      // default to (0.0f, 0.0f, 0.0f)
    st_float32         m_fScalar;   // 1.0 = no scale
 
    // matches float4 ATTR1 in instance vertex decl
    Vec3               m_vUp;
    st_float32         m_fLodTransition;
 
    // matches float4 ATTR2 in instance vertex decl        
    Vec3               m_vRight;
    st_float32         m_fLodValue;
};

STreeInstance derives directly from SInstance, adding a few culling mechanisms needed just for 3D trees.

The SpeedTree SDK organizes the world as a series of cells. Think of the ground as an evenly spaced orthographic grid. As the camera moves, grid cells go in and out of visibility. As cells become visible, the SDK will provide a list of these cells that need to have their populations streamed in. Hence, the SDK will perform most efficiently when the client has its tree instances already organized by cells so that the data might be efficiently passed into the SDK without further on-the-fly processing.

The CCell class in the Forest library encapsulates these cells. They are primarily defined by (row,col) pairs (stored by the structure SRowCol, defined in Forest.h) and are used to house tree and grass instances. Each cell has its own extents and set of culling functions.

CCell::SetTreeInstances()
Once a cell has been determined to be newly visible via CVisibleInstances (detailed below), the client app needs to populate the cell with the base trees and instances located there. This is done via CCell::SetTreeInstances(). Specifically, the cell needs:

• An array of base tree pointers (CTree*) representing the base trees with instances residing in this cell.

• An array of instance pointers (not instance objects). The SDK needs just the pointers. Two important notes about this array:
  
  
  • The instances are passed as pointers to the app-side instance objects and are passed as a single array where the instances for the various base trees are concatenated.
    
    
  • The instances must be concatenated in the same order as the base tree pointers are passed to CCell::SetTreeInstances().
    
    

Structure SRowCol
SRowCol is a structure commonly used to look up or otherwise reference cells. It's simply a (row,col) pair encapsulation. A good example of its use in the app-side code is in MyPopulate.h/cpp in the reference application.

CVisibleInstances is the central class for managing instance streaming and culling. It contains the functions necessary to determine which cells are visible, instance culling, and 3D instance LOD computations. A simplified listing of the CVisibleInstances declaration appears below.

class CVisibleInstances
{
public:
        // init
virtual void                          SetHeapReserves(const SHeapReserves& sHeapReserves);
        void                          SetCellSize(st_float32 fCellSize);
 
        st_bool                       RoughCullCells(const CView& cView, st_int32 nFrameStamp, st_float32 fLargestCellOverhang);
        void                          FineCullTreeCells(const CView& cView, st_int32 nFrameStamp);
        void                          FineCullGrassCells(const CView& cView, st_int32 nFrameStamp, st_float32 fLargestCellOverhang);
 
virtual void                          Cull3dTreesAndComputeLod(const CView& cView);
 
static  st_bool                       InstanceIsVisible(const CView& cView, const CTreeInstance& cInstance);
 
        // cell queries
        TCellArray&                   RoughCells(void);
        const TCellPtrArray&          VisibleCells(void) const;
        TCellPtrArray&                NewlyVisibleCells(void);
 
        // other
        void                          GetExtentsAsRowCols(st_int32& nStartRow, st_int32& nStartCol, st_int32& nEndRow, st_int32& nEndCol) const;
virtual void                          NotifyOfPopulationChange(void);
        const T3dTreeInstLodArray2D&  Get3dInstanceLods(void) const;
 
private:
        // (private section omitted for brevity)
};

The general culling procedure is detailed on this page. Determining the visible cells is a two-stage process: determining a longer, rough list of visible cells, then determining a shorter, more accurate list of cells (called the “fine cull”). This structure provides functions for performing these cull stages (RoughCullCells(), FineCullTreeCells(), and FineCullGrassCells()) as well as accessing their results (RoughCells(), VisibleCells(), NewlyVisibleCells()).

After LOD is computed for the visible 3D trees (as opposed to those in billboard LOD state), the SDK function CCell::GetTreeInstances() provides an array of S3dTreeInstanceLod pointers. Think of them as CTreeInstances with extra LOD data. This structure, below, adds several view-specific LOD details to an instance that cannot be stored with the instance itself. To better understand why this is necessary, consider a scene with a split view, with each camera looking at the same trees but from completely different locations. The instances are the same but the LOD details about each are different, which the S3dTreeInstanceLod structure facilitates.

///////////////////////////////////////////////////////////////////////  
//  Structure S3dTreeInstanceLod
 
struct S3dTreeInstanceLod
{
    const CInstance* m_pInstance;
    st_float32       m_fDistanceFromCameraSquared;
    st_float32       m_fLod;
    st_float32       m_fLodTransition;
    st_int32         m_nLodLevel;
};

Member variable descriptions:

• m_pInstance: The instance this SInstanceLod object is storing LOD info for.

• m_fDistanceFromCameraSquared: Distance squared from the camera (or LOD reference point) at cull time.

• m_fLod: [-1.0, 1.0] value indicating the overall LOD state of the instance. More on the meaning of this range here.

• m_nLodLevel: Which discrete LOD level is currently being rendered. Level 0 is the highest detail, going up to (N-1), the lowest, where N is found in CCore::SGeometry::m_nNumLods.

• m_fLodTransition: [0.0, 1.0] value, indicating how far between discrete LOD states the instance is. 1.0 indicates that the discrete level m_nLodLevel (above) is being rendered with no LOD scales or transitions. As it approaches 0.0, the LOD effects begin to transition into the next lower LOD (e.g. smaller branches begin to scale away, some leaves shrink away while others grow). Once it reaches 0.0, the next discrete LOD becomes active (m_nLodLevel + 1) and m_fLodTransition becomes 1.0 again.