The SceneTree and the SpatialGraph

The SceneTree

That's the hierarchical representation of the scene, in the form of a simple tree, one 'node' have a exactly one parent, and any number of children. This is the structure which manage the hierarchical transformation (position and orientation) of "objects", and their animation.

In FlExtEngine, the CSceneNode class has an "update(...)" function which bring the transformation of the node up to date. It also has an 'accept' method, so that the Visitor Pattern might be used, for better extendability.

The SpatialGraph

This is the spatial representation of the scene, in the form of a Directed Acyclic Graph, dividing the world into regions in which objects will be stored, for efficient visibility culling.

The CSpatialNode class have a "cull(...)" function which handle visibility determination. It also has an 'accept' method, so that the Visitor Pattern might be used, for better extendability.

For the Visitor to be able to make the difference between the spatial subdivision structure and the objects stored within, the CSpatialNode class is specialized in a CSpatialBranch, which is the base class of all nodes, and a CSpatialLeaf, which is the base class of objects stored in the SpatialGraph.

There is a number of spatial subdivision algorithms, I'll do a quick tour of the most popular:

The octree

Click for a bigger version

Octree: the octo-tree, starts with a node encompassing the whole world, which is then split in the middle along the X, Y and Z axis, making eight sub nodes, and that recursively until a given level is reached. Usually an object is only stored in the node completely encompassing it, making the structure move a lot of objects to one (or more) level higher (of bigger size) than it should, such reducing the structure efficiency at culling. A workaround that problem is the Loose Octree, which, instead of having the exact size of the upper level node split in eight, is slightly inflated (likely by 10-25%); That way, a node is more likely to store an object that didn't previously fit by only a small margin.

The Octree has been used in Unreal Tournament to store the player's characters.

The quadtree

Quadtree: like its 3D cousin the Octree, the Quadtree starts with a node encompassing the whole world, which is then split only by two axes (the axis indicating the height isn't used). The Quadtree is often used to split a terrain into chunks, but it can also be used like an Octree (only in 2D compared to the Octree).

The Quadtree has been used in Unreal 2 to store terrain.

The BSP tree

Click for a bigger version

BSP: the binary space partitioning tree, starts with a single arbitrary plane splitting the world in two, and then recursively for each side of that plane, until a node only contains a given number of triangles. Usually, and unlike the Quadtree and Octree, only leaf nodes do contains triangles.

The BSP has been used in many iD software titles, such as Quake, Quake II, and Quake III Arena, to store world geometry.

The kD tree

kD-Tree: k is the dimension of the tree, which tells along how many axis the kD-Tree will generate split planes. While the BSP does have arbitrary planes which subdivide the world, the kD-Tree only generate split planes parallel to one of the k axes.

Sectors and portals

Sector/Portal: that scheme divides the world into convex Sectors, which are connected (one or two way) with Portals. The Sectors are to be convex for the system to work best, as then, there's the guarantee that from any point inside the Sector, any other point might be visible.

The Sector and Portal scheme has been used along with a BSP in Doom III and Quake IV.

The adaptive binary tree

ABT: the Adaptive Binary Tree is somewhat similar to the BSP, except this one is updated real-time, when a branch contains a node/item ratio too small, the branch is recomputed to best fit the items stored within it.

The Adaptive Binary Tree is being used at vTales Graphics (3).