Graphics Reference
In-Depth Information
Figure 7.12 The cells of a 4 × 4 grid given in Morton order.
comparisons with the coordinates of the octree nodes. Let the point's coordinates be
given as three floats x , y , and z . Remap each of these into binary fractions over the range
[
]
[
]
0 ... 1
. For instance, if the octree's x range spans
10 ... 50
, then an x coordinate of
25 would map into the fraction (25
0. 01100000. Note
that this does not require either all dimensions to be the same or that they be powers
of 2. By virtue of construction, it should be clear that the most significant bit of the
binary fraction for the x coordinate specifies whether the point lies to the left of the
octree yz plane through the octree center point (when the bit is 0) or to the right of
it (when the bit is 1). Taking the three most significant bits of the binary fractions for
x , y , and z together as a unit, they form the index number (0-7) of the root's child
node, in which the point lies. Similarly, the three next-most significant bits specify
the subnode within that node in which the point lies, and so on until a leaf node has
been reached.
The resulting binary string of interleaved bits of the three binary fractions can be
seen as a key, a locational code , directly describing a node position within the tree.
Nodes output in sorted order based on this locational code are said to be in Morton
order (Figure 7.12).
Given the locational code for the parent node, a new locational code for one of
its child nodes is easily constructed by left-shifting the parent key by 3 and adding
(or ORing) in the parent's child index number (0-7) for the child node childKey =
(parentKey << 3) + childIndex . Locational codes can be used in a very memory-
efficient octree representation, explored next.
10)/(50
10)
=
0. 375
=
7.3.4 Linear Octrees (Hash-based)
Although the pointer-based representation is likely to save memory over the flat
array-based representation for average trees, the former still requires up to eight
child pointers to be stored in the octree nodes. These likely constitute a major part of
the memory required to hold the tree.
A clever nonpointer-based representation alternative is the linear octree . A linear
octree consists of just the octree nodes containing data, in which each node has
Search WWH ::




Custom Search