Octree

From DmWiki

This article is a stub. You can help improve the article by expanding it.

An octree is a tree structure and belongs to the group of spatial subdivision algorithms. It is most commonly used to speed up the rendering of scenes by culling parts of the world not seen by the viewing frustum. Because of its structure it is also often used for collision detection as it enables an application to quickly find the set of triangles nearest to the player. Therefor the expensive collision detection must be applied only to a far smaller set of geometry.

Every octree node has 8 children or none (if it is a leaf of the tree). Each of the 8 children is a part of the node and taken all children together occupy the same space as the node itself. The advantage of the octree is now, that a test against a box can tell whether the entire contents (including all the children the node might have) are visible or not - so this greatly speeds up the rendering process by ignoring not-seen geometry.

Octrees are axis-aligned (see AABB) to speed up the triangle-in-box test. The root octree node covers the map completely.

When creating an octree each triangle in the world has to be assigned to the smallest octree box possible - so you end up with n octree nodes and their parent-child relationship. Every node carries a list of triangles it contains. The recursion process of creating smaller octree nodes is usually stopped at a certain depth or a minimum number of elements in a node.

When rendering, you start at the root node and recurse deeper into the tree if you can neither say a node is completely visible nor it is completely invisible.