Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
Octree Partitioning Techniques
arrowPress Releases
January 18, 2020
Games Press
View All     RSS







If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 

Octree Partitioning Techniques


August 12, 1997 Article Start Page 1 of 2 Next
 

Octree Space Partitioning (OSP) algorithms are used for the correct representation of solid objects in a 3D environment, and are the basis for many modeling and rendering systems. The primary objective of the OSP is to reduce the number of comparisons required to determine which surfaces in a scene need to be processed for ray tracing, collision detection, visibility determination, or similar calculations. Although primarily used in static environments, they can also be used in dynamic environments with a few modifications. Octrees can provide a significant reduction in the time needed to sort polygons in a scene for proper display and are ideal for high-performance games that consist primarily of empty space where the objects within this space show large variations in relative size (for example, flight simulators).

In this discussion, we will review the two canonical forms of the OSP:

1. OSPs that operate on objects in the scene.
2. OSPs that operate on the volume of space comprising the scene.

Both types of octree algorithms store their data in a tree structure made up of three or more child nodes per branch. The resulting data structure can be traversed in three dimensions, unlike the Binary Space Partition (BSP), which can only be traversed in one (for more information on Binary Space Partition trees, see "Advanced Binary Space Partition Techniques," Game Developer, October/November 1996).

In contrast to the construction of a binary tree (where the surfaces in the scene are inspected and assigned to either the left or right node, depending upon which side of the partition plane they are located), with octrees you assign to the nodes of a tree not the surfaces themselves, but the volumes of space that contain surfaces.

Hierarchical Bounding Volumes

The hierarchical bounding volume form of the OSP algorithm stores its data in an n-tree structure. An n-tree differs from a binary tree in that its parent nodes have varying numbers of child nodes, rather than having either zero or two child nodes. The root node of the tree contains all of the objects in the scene. Each branch node going away from the root contains fewer and fewer objects, until you reach leaf nodes, which contain only a single object or surface. Figures 1 through 3 illustrate the steps to the construction of the tree and is explained in the following text. The purpose of this algorithm is to manage and sort information about the objects in the scene relative to each other, minimizing the time needed to render the surface in the correct order: front-to-back or back-to-front.

Creating the Tree

To create the initial tree, obtain the maximum dimensions of the scene that is occupied by your surfaces, then adjust the dimensions to form a cube.

FIGURE 1

FIGURE 1. The volume of the root node.

 

This is the bounding cube for all the surfaces, and it is assigned to the root node of the octree. Figure 1 represents two spaceships in a volume of space. Note the use of shadow outlines against the background grids to make it easier to see the position of the ships. Figure 1 is the root node of the tree that holds the entire volume.

Next, select a subset of the surfaces based on an object hierarchy construction algorithm (OHC). This algorithm determines which surfaces are selected, in what order they are processed, and how many are allowed in each subset. You can choose from a number of different algorithms, depending on the needs of your game. In this example, I'll use a simple OHC that selects and groups surfaces based on the volume they occupy. The OHC randomly selects any surface from the scene, which I'll call the "seed surface," as it's the first surface from which a single branch of the Octree grows. The algorithm then finds the nearest surface to the seed surface. If both surfaces fit within a volume of space less than a predefined limit, then both surfaces belong to the same set. We call this predefined limit the "limit volume." In this example, we'll use a simple limit volume that is just a bounding box; more complex shapes can be used, depending on the characteristics of the game. The initial limit volume is usually large enough to contain the largest free-standing object in your scene.

You continue adding the nearest surfaces to the set until the total volume of the set reaches or exceeds the limit volume. All of these surfaces are assigned to a child node of the tree. This node also stores the coordinates of the volume occupied by these surfaces. Select another seed surface from the remaining surfaces in the scene and repeat this procedure until all surfaces in the scene belong to a set and are included in the tree. You have now completed the first level of the tree.

FIGURE 2

FIGURE 2. Limit volumes forming nodes on the tree.


Figure 2 shows the limit volumes around each of the ships. Note that the orientation of the left ship causes it to occupy a larger limit volume than the right ship. This difference is caused by our selection of a bounding-box OHC algorithm; other algorithms can provide tighter fits. Figure 2 is the tree with nodes for each of the ships.

Now we reduce the size of the limit volume, usually by splitting it in half, and recursively repeat the process. Each branch of the octree now points to a single set of surfaces. You repeat the seed-surface selection and subset creation for each of the branches of the octree, which adds a new level to the tree. Figure 3 shows the smaller limit volumes around components of the ships. For clarity, Figure 3 shows only two of the lowest level limit volumes for each ship.

Repeat this process recursively until the limit volume reaches the size of the smallest surface, or until every surface occupies its own branch of the tree. You may have to split some surfaces to accommodate the single surface per branch rule.

FIGURE 3

FIGURE 3. Further reduction of the limit volumes.


If you allow the algorithm to continue until the limit volume reaches the size of the smallest surface, your scene will display correctly, but it may take too long to create the octree. Using a limit volume that allows more than one surface into each branch improves performance, but sacrifices final quality. In this example, I used a bounding box limit volume, which improves performance of collision detection and object motion, but reduces that of ray tracing.

How you select the seed surfaces will determine the number of child nodes at each level of the tree. Ideally, you want a seed surface to be at the center of a cluster of surfaces in order to reduce the number of nodes in a level. Rubberbanding algorithms that find the center of a cluster are very useful in selecting an optimal seed surface. Seed surfaces that are too isolated from their neighbors generate too many nodes at certain levels, which in turn increases search times when doing collision-detection or ray-tracing calculations.

FIGURE 4

FIGURE 4. The camera's viewing frustrum.

 


Article Start Page 1 of 2 Next

Related Jobs

Disbelief
Disbelief — Chicago, Illinois, United States
[01.17.20]

Junior Programmer, Chicago
Disbelief
Disbelief — Cambridge, Massachusetts, United States
[01.17.20]

Senior Programmer, Cambridge, MA
Disbelief
Disbelief — Cambridge, Massachusetts, United States
[01.17.20]

Junior Programmer, Cambridge, MA
Wargaming.net
Wargaming.net — Bellevue , Washington, United States
[01.17.20]

UI Engineer





Loading Comments

loader image