8.11. What Octrees are used for   

One use of octrees is in the speeding up of a raytracing algorithm. Instead of casting a ray through a pixel and intersecting it with each object in the scene, the ray is tested through an octree representation of the scene. A ray is initially tested for intersection with each child of the root node (a ray will always hit the root node). The ray will intersect with a node, and will then be tested against its child nodes. This process continues until the ray is intersected with a leaf node. This node will either contain an object (that the ray intersects with in the scene), or nothing (indicating that the ray hits nothing in the scene).

This process of intersection testing is much quicker than the classic raytracing technique, because only a fraction of the number of objects are tested for intersection. Naturally, if the scene contains few objects then there will be little, or no saving. Time savings are gained when the number of objects in a scene exceeds approximately four times the octree depth. This figure represents the maximum number of tests that might be made on an octree.

A second use of the octree is in colour quantisation. Colour quantisation is a method for determining a "near enough" value for a colour in an image. This normally occurs for a 24-bit (16 million colour) image being displayed on an 8-bit (256 colour) display.

"The first 256 different pixels form the leaf nodes of a tree. If the tree has 256 nodes, then a reduction is made before adding the next pixel. Two possible strategies can be used for reduction. Either the deepest nodes are reduced, or the nodes containing the fewest pixels. ... After a reduction, one or more further pixels can be added, either as leaf nodes or by inclusion in the average of a reduced node. In this way, the total number of leaf nodes and reduced nodes can be kept to 256, thereby reducing the memory requirement. Mapping of the image points to the lookup table entries is a simple search of the final octree."

           (Burger and Gillies 1989).