## 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).