Graphics Reference
In-Depth Information
The analogous structure to the octree in two dimensions is known as a
quadtree
.
The world is now enclosed in an axis-aligned bounding square, and is subdivided
into four smaller squares at each recursive step.
Just as binary trees can be represented in a flat array without using pointers,
so can both quadtrees and octrees. If the tree nodes are stored in the zero-based
array
node[N]
, then being at some parent node
node[i]
, the children would for
a quadtree be
node[4*i+1]
through
node[4*i+4]
and for an octree
node[8*i+1]
through
node[8*i+8]
. This representation requires the tree being stored as a
complete tree.
Where a complete binary tree of
n
levels has 2
n
−
1 nodes, a complete
d
-ary tree
d
n
of
n
levels has
nodes. Using this type of representation, a complete
seven-level octree would require just short of 300,000 nodes, limiting most trees to
five or possibly six levels in practice.
As the tree must be preallocated to a specific depth and cannot easily grow further,
the array representation is more suitable for static scenes and static octrees. The
pointer-based representation is more useful for dynamic scenes in which the octree
is constantly updated.
(
−
1
)
/
(
d
−
1
)
7.3.2
Octree Object Assignment
Octrees may be built to contain either static or dynamic data. In the former case, the
data may be the primitives forming the world environment. In the latter case, the
data is the moving entities in the world.
In the static scenario, it is straightforward to form the octree using top-down con-
struction. Initially, all primitives in the world are associated with the root volume. As
the root volume is split, the set of primitives is reassigned to the child cells it overlaps,
duplicating the primitives when they overlap more than one cell. The procedure is
repeated recursively, with the stopping criteria of not subdividing cells containing
fewer than some fixed number of primitives or when primitives are assigned to all of
the children (obviating further subdivision).
Determining to which child volumes to assign a primitive can be done by first
dividing the primitives by the octree
x
-axis partitioning plane, splitting any straddling
primitives into two parts, one for each side. Both sets are then similarly split for the
y
-axis partitioning plane, and the resulting four sets are split once more by the
z
-axis
plane. The eight final sets are then assigned to the corresponding child node. Whether
a primitive must be split by a given partitioning plane is determined by testing to see
if it has vertices on both sides of the plane. Splitting of polygon primitives is discussed
in detail in Section 8.3.4.
An alternative assignment approach is not to split the primitives. Instead, for each
child volume and each primitive a full AABB-primitive overlap test is performed to see
if the primitive should be assigned to that volume. Although perhaps a conceptually
simpler method, this test is more expensive.
