Table of Contents

Culling & Population Structures

Forest Library

SpeedTree uses a grid/cell-based culling system that is very efficient at culling very large forests (millions of instances). There are three steps involved in forest-level culling: i) setting the correct camera view, ii) calling the cull function which will provide the cull results, iii) reporting the tree instances that appear in the provided cells.


Start With the Camera

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.


Base Trees and Instances

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 class for instances called CInstance, which is used as a base class for both tree and grass instances. It contains most the important per-instance data like position, orientation, and scalar values. Note that a trade-off is offered in the Forest.h header file. CInstance stores an instance's orientation as two 3D vectors: up and right. If SPEEDTREE_COMPRESS_INSTANCE_VECTORS is #defined, each vector is stored in three bytes. When undefined, each vector is stored as a Vec3, or twelve bytes, four times the space. When millions of instances are in play, this eighteen-byte difference can grow large. The trade-off however, is reduced performance when streaming instance lists on the fly, particularly the billboards. The instance vertex buffers expect full-sized floats there and the added conversion on the fly takes its toll.






CTreeInstance derives directly from CInstance, adding a few culling mechanisms needed just for 3D trees. CGrassInstance is identical to CInstance, not needing to add anything (in fact, it's typedef'd to CInstance in Forest.h).

Note: Be sure to call SetInstanceOf() on each of your CInstance (or derived) objects as some of its functions depend on being able to query parameters from the base tree. The SDK source has assertions where the instance's base tree's pointer is used.

Cells

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 cellls 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 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 and are used to house tree and grass instances. Each cell has its own extents and set of culling functions. CCell::AppendTreeInstances 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::AppendTreeInstances(). Specifically, the cell needs:

Structure SCellKey SCellKey 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.


Class CVisibleInstances

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.










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).


Structure S3dTreeInstanceLod

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.





Member variable descriptions: