3 Out-of-core Multiresolution Terrain Modeling
51
(a)
(b)
Fig. 3.2. (a) The bisection of a triangle; (b) An example of a triangle bintree
dependencies must be represented explicitly, thus resulting in a more verbose data
structure [18].
When extracting adaptive TINs from a triangle bintree, we need to guarantee that
whenever a triangle t is split, the triangle adjacent to t along its longest edge is also
split at the same time. In this way, the extracted mesh will be conforming that is,
it will not contain cracks. This can be achieved through the application of neighbor
finding techniques to the hierarchy. In [13], an algorithm for neighbor finding is proposed that works in worst-case constant time. An alternative approach consists of
using an error saturation technique, which through manipulation of the errors associated with the triangles in the hierarchy, allows for extracting conforming meshes (but
not with a minimal number of triangles) without the need for neighbor finding [34].
Other representations for multiresolution models generated through triangle bisection have been proposed that encode the model as a directed acyclic graph (DAG)
of atomic updates, each of which is called a “diamond,” formed by pairs of triangles
that need to be split at the same time [26, 35, 38].
The space requirements of a hierarchical representation can be reduced through
the use of pointerless tree representations, also known as “compressed representations.” There are a number of alternative compressed representations for a binary
tree, and, in general, for a tree with fanout equal to 2
d (i.e. a quadtree for d = 2 and
an octree for d = 3). One simple method, known as a “DF expression” [24], makes
use of a list consisting of the traversal of the tree’s constituent nodes, where a one
bit code is used to denote if the corresponding node is a non-leaf or a leaf node.
This method is very space-efficient but does not provide for random access to nodes
without traversing the list from the start for each query. Thus, most implementations
make use of structures that are based on finding a mapping from the cells of the
domain decomposition to a subset of the integers (i.e. to one dimension).
In the case of a triangle bintree or triangle quadtree, this mapping is constructed
by associating a location code with each node that corresponds to a triangle element
51
(a)
(b)
Fig. 3.2. (a) The bisection of a triangle; (b) An example of a triangle bintree
dependencies must be represented explicitly, thus resulting in a more verbose data
structure [18].
When extracting adaptive TINs from a triangle bintree, we need to guarantee that
whenever a triangle t is split, the triangle adjacent to t along its longest edge is also
split at the same time. In this way, the extracted mesh will be conforming that is,
it will not contain cracks. This can be achieved through the application of neighbor
finding techniques to the hierarchy. In [13], an algorithm for neighbor finding is proposed that works in worst-case constant time. An alternative approach consists of
using an error saturation technique, which through manipulation of the errors associated with the triangles in the hierarchy, allows for extracting conforming meshes (but
not with a minimal number of triangles) without the need for neighbor finding [34].
Other representations for multiresolution models generated through triangle bisection have been proposed that encode the model as a directed acyclic graph (DAG)
of atomic updates, each of which is called a “diamond,” formed by pairs of triangles
that need to be split at the same time [26, 35, 38].
The space requirements of a hierarchical representation can be reduced through
the use of pointerless tree representations, also known as “compressed representations.” There are a number of alternative compressed representations for a binary
tree, and, in general, for a tree with fanout equal to 2
d (i.e. a quadtree for d = 2 and
an octree for d = 3). One simple method, known as a “DF expression” [24], makes
use of a list consisting of the traversal of the tree’s constituent nodes, where a one
bit code is used to denote if the corresponding node is a non-leaf or a leaf node.
This method is very space-efficient but does not provide for random access to nodes
without traversing the list from the start for each query. Thus, most implementations
make use of structures that are based on finding a mapping from the cells of the
domain decomposition to a subset of the integers (i.e. to one dimension).
In the case of a triangle bintree or triangle quadtree, this mapping is constructed
by associating a location code with each node that corresponds to a triangle element