52
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
(i.e. noblock) in the tree. A location code for a node implicitly encodes the node as a
bit string consisting of the path from the root of the tree to that node, where the path
is really the binary (1 bit) or quaternary (2 bits) representation of the transitions that
have been made along the path. If the node is at level (i.e. depth) i in the tree, a string
of length d i binary digits is associated with the node, where each step in the descent
from the root is represented by d bits. In a triangle bintree, each step is encoded as
0(1) depending on whether the corresponding arc in the tree leads to the left (right)
child of its parent, while in a triangle quadtree a labeling scheme is applied that
extends the one used for region quadtrees. In particular, in a region quadtree where
the blocks are square, the 2-bit string patterns 00, 01, 10, and 11 are associated with
the NW, NE, SW, and SE transitions, respectively. In the case of a triangle quadtree,
the same 2-bit string patterns are used with the difference that they correspond to
different triangles in the hierarchy depending on the triangle orientation (i.e. whether
it is tip-up as in Fig. 3.1 (a) or tip-down as in Fig. 3.1 (b)).
Note that the location codes in a square quadtree are equivalent to the Z order
(or Morton order) (e.g. see [41]), which is an ordering of the underlying space in
which the result is a mapping from the coordinate values of the upper-left corner u
of each square quadtree block to the integers. The Morton order mapping consists of
concatenating the result of interleaving the binary representations of the coordinate
values of the upper-left corner (e.g. (a, b) in two dimensions) and i of each block
of size 2
i so that i is at the right. In the case of a triangle quadtree, the analog of a
Z or Morton order can still be constructed but there is no interpretation in terms of
bit interleaving as can be seen by examining the three-level labeling of the triangle
quadtree in Fig. 3.3 that is three levels deep. If we record the depth of the tree at
which the node is found and append it to the right of the number corresponding to
the path from the root to the node thereby forming a more complex location code,
then the result of sorting the resulting location codes of all the nodes in increasing
order yields the equivalent of a depth-first traversal of the tree. If we vary the format
of the resulting location codes so that we record the depth of the tree at which the
node is found on the left (instead of on the right) and the number corresponding
to the path from the root to the node is on the right, then the result of sorting the
resulting location codes of all the nodes in increasing order yields the equivalent of a
breadth-first traversal of the tree access structure [2]. These depth-first and breadthfirst traversal characterizations are also applicable to triangle quadtrees.
Location codes are used for performing neighbor finding efficiently as well as to
retrieve the vertices of a triangle, the value of the field associated with a vertex, and
so on. An efficient implementation involving arithmetic manipulation and a few bit
operations allows performing such computations in constant time [13, 25].
Out-of-core representations of triangle quadtrees and bintrees are based on encoding the location codes of both internal and leaf nodes in an external memory index
such as a B-tree, as done for encoding a quadtree or an octree in external memory.
In [18], Gerstner presents a compressed representation of a triangle bintree
that works in main memory, but it could be implemented to provide an effective
out-of-core representation. One of the most interesting features of this approach is
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
(i.e. noblock) in the tree. A location code for a node implicitly encodes the node as a
bit string consisting of the path from the root of the tree to that node, where the path
is really the binary (1 bit) or quaternary (2 bits) representation of the transitions that
have been made along the path. If the node is at level (i.e. depth) i in the tree, a string
of length d i binary digits is associated with the node, where each step in the descent
from the root is represented by d bits. In a triangle bintree, each step is encoded as
0(1) depending on whether the corresponding arc in the tree leads to the left (right)
child of its parent, while in a triangle quadtree a labeling scheme is applied that
extends the one used for region quadtrees. In particular, in a region quadtree where
the blocks are square, the 2-bit string patterns 00, 01, 10, and 11 are associated with
the NW, NE, SW, and SE transitions, respectively. In the case of a triangle quadtree,
the same 2-bit string patterns are used with the difference that they correspond to
different triangles in the hierarchy depending on the triangle orientation (i.e. whether
it is tip-up as in Fig. 3.1 (a) or tip-down as in Fig. 3.1 (b)).
Note that the location codes in a square quadtree are equivalent to the Z order
(or Morton order) (e.g. see [41]), which is an ordering of the underlying space in
which the result is a mapping from the coordinate values of the upper-left corner u
of each square quadtree block to the integers. The Morton order mapping consists of
concatenating the result of interleaving the binary representations of the coordinate
values of the upper-left corner (e.g. (a, b) in two dimensions) and i of each block
of size 2
i so that i is at the right. In the case of a triangle quadtree, the analog of a
Z or Morton order can still be constructed but there is no interpretation in terms of
bit interleaving as can be seen by examining the three-level labeling of the triangle
quadtree in Fig. 3.3 that is three levels deep. If we record the depth of the tree at
which the node is found and append it to the right of the number corresponding to
the path from the root to the node thereby forming a more complex location code,
then the result of sorting the resulting location codes of all the nodes in increasing
order yields the equivalent of a depth-first traversal of the tree. If we vary the format
of the resulting location codes so that we record the depth of the tree at which the
node is found on the left (instead of on the right) and the number corresponding
to the path from the root to the node is on the right, then the result of sorting the
resulting location codes of all the nodes in increasing order yields the equivalent of a
breadth-first traversal of the tree access structure [2]. These depth-first and breadthfirst traversal characterizations are also applicable to triangle quadtrees.
Location codes are used for performing neighbor finding efficiently as well as to
retrieve the vertices of a triangle, the value of the field associated with a vertex, and
so on. An efficient implementation involving arithmetic manipulation and a few bit
operations allows performing such computations in constant time [13, 25].
Out-of-core representations of triangle quadtrees and bintrees are based on encoding the location codes of both internal and leaf nodes in an external memory index
such as a B-tree, as done for encoding a quadtree or an octree in external memory.
In [18], Gerstner presents a compressed representation of a triangle bintree
that works in main memory, but it could be implemented to provide an effective
out-of-core representation. One of the most interesting features of this approach is