56
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
B
A
A
B
C
C
D
E
D
E
Fig. 3.6. Clustering of a binary vertex forest in subtrees of height 2
replacing the subtree formed by vertices v 1 , v 2 , and by their parent, which will be
again v 1 for a half-edge collapse with a pointer to the corresponding half-edge e in the
data structure describing the currently extracted mesh. In [7], DeCoro and Pajarola
propose an out-of-core representation of the same model to support view-dependent
rendering of large 3D meshes. The proposed technique starts from the binary forest
and computes almost balanced subtrees that can fit in a disk page. Pointers to empty
children are removed, thus reducing the storage cost by 25%. This, together with a
compact encoding of the information associated with the nodes of the binary forest
of edges, results in a compact data structure that requires less disk accesses. On the
other hand, computation of the disk blocks requires two depth-first traversals of the
binary forest. The objective is to perform selective refinement out-of-core efficiently,
while both the simplification step and the construction of the multiresolution model
are assumed to be performed in-core.
The strategies described above apply only to models based on edge collapse in
which the dependency relation is represented as a binary forest. In [6] we propose
and analyze clustering techniques that work on the full DAG of dependency relations. Such techniques are general and can be applied to any multiresolution model,
regardless of the way it is generated. An important assumption is that the updates in
the multiresolution model are atomic, that is, each update involves a relatively small
number of triangles. Conversely, the DAG may have a very large number of nodes.
On the basis of an analysis of selective refinement queries and of the shape of the
DAG describing the MT, we have defined and implemented the following techniques
for grouping the updates in an MT according to sorting criteria:
• Approximation error (Err)
• Layer: shortest path from the root (Lyr)
• Level: longest path from the root (Lev)
• Distance: average path length from the root (Ly2)
• Depth-first (DFS) and breadth-first (BFS) DAG traversal
• Multiresolution depth-first traversal (GrD) and multiresolution breadth-first
traversal (GrB): similar to depth-first or breadth-first DAG traversal, respectively, but before performing an update u on the currently extracted mesh, all
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
B
A
A
B
C
C
D
E
D
E
Fig. 3.6. Clustering of a binary vertex forest in subtrees of height 2
replacing the subtree formed by vertices v 1 , v 2 , and by their parent, which will be
again v 1 for a half-edge collapse with a pointer to the corresponding half-edge e in the
data structure describing the currently extracted mesh. In [7], DeCoro and Pajarola
propose an out-of-core representation of the same model to support view-dependent
rendering of large 3D meshes. The proposed technique starts from the binary forest
and computes almost balanced subtrees that can fit in a disk page. Pointers to empty
children are removed, thus reducing the storage cost by 25%. This, together with a
compact encoding of the information associated with the nodes of the binary forest
of edges, results in a compact data structure that requires less disk accesses. On the
other hand, computation of the disk blocks requires two depth-first traversals of the
binary forest. The objective is to perform selective refinement out-of-core efficiently,
while both the simplification step and the construction of the multiresolution model
are assumed to be performed in-core.
The strategies described above apply only to models based on edge collapse in
which the dependency relation is represented as a binary forest. In [6] we propose
and analyze clustering techniques that work on the full DAG of dependency relations. Such techniques are general and can be applied to any multiresolution model,
regardless of the way it is generated. An important assumption is that the updates in
the multiresolution model are atomic, that is, each update involves a relatively small
number of triangles. Conversely, the DAG may have a very large number of nodes.
On the basis of an analysis of selective refinement queries and of the shape of the
DAG describing the MT, we have defined and implemented the following techniques
for grouping the updates in an MT according to sorting criteria:
• Approximation error (Err)
• Layer: shortest path from the root (Lyr)
• Level: longest path from the root (Lev)
• Distance: average path length from the root (Ly2)
• Depth-first (DFS) and breadth-first (BFS) DAG traversal
• Multiresolution depth-first traversal (GrD) and multiresolution breadth-first
traversal (GrB): similar to depth-first or breadth-first DAG traversal, respectively, but before performing an update u on the currently extracted mesh, all