Octrees

Foreword

Removing an invisible geometry of the scene is one of the most important problems to be solved in the process of creating three-dimensional graphics display subsystem. Such treatment allows you to draw only that part of the scene that is currently visible (located in the cone of camera's view). There are many data structures and algorithms that allow to solve the above problem to a greater or lesser extent.

Why Are Such Treatments Necessary?

The answer is obvious: efficiency. Although modern graphics processors are able to process millions of polygons per second, the actual performance per frame is much worse. The scene, of course, must consist of a large number of polygons to look strikingly. If we had to ignore the problem and process all the triangles within each frame of the animation, eventually the number of frames per second would fall drastically, since it would be handled a lot of unnecessary polygons that do not appear on the screen. Adding to this, the problem with the overhead of geometry data transfer over the bus (if for some reason these data cannot be allocated in server-side memory) and the GPU power needed for rasterization (including fillrate) and various graphics effects (eg. bump mapping, lighting, shading, etc.). To solve this problem, different algorithms of scene partitioning are applied where polygons are divided into smaller sets which are capable of being processed by the card with an acceptable speed. So far, BSP was the most widely used algorithm in the games (BSP tree could be seen as a some sort of painter's algorithm modification). It divides the scene into sectors, and sorts collections of polygons in the forward-backward relationship. With this sorting, it was possible to render with turned off depth buffer, but this was not the best idea since received better performance after the enable depth buffer and drawing polygons in order from those in the front of those at the very rear. However, BSP trees, during a scene partitioning, could divide a scene polygon which leads to the creation of new geometry data (more triangles to be processed). They also introduce restrictions on the geometry and prevent any modification of the level (it would require rebuilding the tree). BSP trees yet fulfilled its role well in games where the locations consisted of a small number of triangles. BSP (or its modifications) has been used in such hits as all of Quake, Unreal, Unreal Tournament. In his own engine, the author applied the alternative method of hidden surface removal, namely octree.

Octree

Octree encloses the whole geometry of the scene (the world in which the player is) within the cube. The cube (called the parent or the root node) can then be divided into eight smaller (hereinafter referred to as descendants, sub-nodes or octans) as shown in the illustration (Fig. 1). In turn, each of the descendants can be divided into eight consecutive and so continue recursively until it reaches a certain threshold (which is most often the quantity of the minimum number of polygons the cube can contain, or the maximum level of dividing the stage, or the minimum length of the edges of the cube). Each descendant has assigned a list of triangles, which in itself contains. The root contains all the polygons of the world. Each parent contains the polygons, which are later assigned to the concrete descendants.

Rendering

Drawing the scene relies on checking whether a cube surrounding the root is in the area of view. If it is not, then any polygon of the scene is not drawn. If it is visible as a whole, then all polygons of the scene are drawn, thus the whole world. If the root is visible only partially, we begin to traverse the tree. We check the descendants as we did it with the root. If we encounter a fully visible cube, we render geometry contained within it. If the cube is visible partially only and do not have descendants (sub-nodes), we draw polygons assigned to it (the case where the player is smaller than the smallest octan). As can be seen using this algorithm, we draw only what is currently seen by the player.

Creating a Tree

At the outset, you must create a cube that surrounds the root of the whole scene. To accomplish this, we are looking for the largest absolute value (lets call it V) for the coordinates x, y, z of each node from the list of scene geometry. This value will serve to generate a cube (opposite vertices are [V, V, V] and [-V,-V,-V]). We attach the list of all polygons of the scene we are about to divide to the structure describing the root. Then the cube is divided into eight sections along the main axis, and check which polygons are in different octans (sub-nodes). So proceed recursively until it reaches a certain threshold which we set ourselves the condition of the completion of the tree and about which I referred above. Since a polygon can be contained in a few nodes (through a few cubes), it is exceedingly indicated it would not store a copy in a few leaves. In some cases, this will force the card to several times the processing of the same polygon, and thus decrease productivity. Splitting a polygon along the edge of a cube is a solution of somehow, which unfortunately we are not interested because it leads to the emergence of new data about the geometry and thus eliminates a degree of abstraction in the implementation (when the data of the level was kept separately, and data on tree separately). Frame counter in every polygon will be the solution. Rendering subsystem will check the value of the counter and prevented a further drawing of the triangle already rendered on the screen (in the current frame).

What About Dynamic Objects?

To allow the correct rendering of dynamic objects in the tree, each node should contain a list of dynamic objects, and each such object should contain a list of nodes to which it is attached. When an object changes position, detach it from the current node and the joining of new ones. In the course of drawing the scene using only the visible nodes and objects connected to it, do not forget about the possibility of re-drawing of the object and also use the frame counter.

Conclusion

As you can see, octree structure is a very effective way to record and visualize the scene (including, of course, the main purpose of its use - rejection the invisible geometry from the process of rendering). It can process the scene of any size and does not put any restrictions on the geometry, as was the case with the binary space partitioning (BSP trees). Presented here are methods that describe specific implementation used by the author in his own engine. It is clear that some aspects of the implementation can be resolved otherwise.

History

• 10^th September, 2010: Initial post