54
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
available representation; a set of local updates U refining it; and a dependency relation among updates [38]. In general, an update u defines two sets of triangles u
−
and u
+ , representing the same portion of a surface at a lower and a higher LOD,
respectively. An update can be applied locally either to refine or to coarsen a mesh.
The direct dependency relation is defined as follows. An update u 2 depends on an
update u 1 if it removes some cells inserted by u 1 , that is, if the intersection u 2
−
∩ u 1
+
is not empty. The transitive closure of the dependency relation is a partial order, and
the direct dependency relation can be represented as a directed acyclic graph (DAG).
Any subset of updates, which is closed with respect to the partial order, that is, which
defines a cut of the DAG, can be applied to the base mesh in any total order extending
the partial one, and gives a mesh at an intermediate (uniform or variable) resolution.
In Fig. 3.4 we show a simple multiresolution model composed of a base mesh and
three updates, the gray line represents a cut of the DAG encoding the dependency
relation and the mesh on the right represents the extracted mesh, associated to the
depicted cut. In [8], we have shown that all the existing multiresolution models are
captured by this framework, which can be extended to higher dimensions and to cell
complexes.
In some cases, when a multiresolution model is built through some specific local
modification operators (such as vertex removal, edge collapse, or vertex-pair contraction), an implicit, procedural encoding of the updates can be used and the dependency relation can be encoded in a more compact form than a DAG, such as the
view-dependent tree proposed in [11].
Various techniques have recently been proposed in the literature for out-of-core
multiresolution modeling of large irregular datasets. The general strategy in the design of out-of-core data structure consists of organizing information in disk pages
in such a way that the number of page loads/swaps is minimized when traversing
the model. In this respect, the basic queries on a multiresolution model are instances
of selective refinement that consists of extracting adaptive meshes of minimal size
according to application-dependent requirements. The idea is to select and apply to
0
3
1
2
(a)
(b)
Fig. 3.4. (a) A simple multiresolution model composed of a base mesh and three updates, bold
gray line represents a cut; (b) the mesh corresponding to the front represented by the bold gray
line
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
available representation; a set of local updates U refining it; and a dependency relation among updates [38]. In general, an update u defines two sets of triangles u
−
and u
+ , representing the same portion of a surface at a lower and a higher LOD,
respectively. An update can be applied locally either to refine or to coarsen a mesh.
The direct dependency relation is defined as follows. An update u 2 depends on an
update u 1 if it removes some cells inserted by u 1 , that is, if the intersection u 2
−
∩ u 1
+
is not empty. The transitive closure of the dependency relation is a partial order, and
the direct dependency relation can be represented as a directed acyclic graph (DAG).
Any subset of updates, which is closed with respect to the partial order, that is, which
defines a cut of the DAG, can be applied to the base mesh in any total order extending
the partial one, and gives a mesh at an intermediate (uniform or variable) resolution.
In Fig. 3.4 we show a simple multiresolution model composed of a base mesh and
three updates, the gray line represents a cut of the DAG encoding the dependency
relation and the mesh on the right represents the extracted mesh, associated to the
depicted cut. In [8], we have shown that all the existing multiresolution models are
captured by this framework, which can be extended to higher dimensions and to cell
complexes.
In some cases, when a multiresolution model is built through some specific local
modification operators (such as vertex removal, edge collapse, or vertex-pair contraction), an implicit, procedural encoding of the updates can be used and the dependency relation can be encoded in a more compact form than a DAG, such as the
view-dependent tree proposed in [11].
Various techniques have recently been proposed in the literature for out-of-core
multiresolution modeling of large irregular datasets. The general strategy in the design of out-of-core data structure consists of organizing information in disk pages
in such a way that the number of page loads/swaps is minimized when traversing
the model. In this respect, the basic queries on a multiresolution model are instances
of selective refinement that consists of extracting adaptive meshes of minimal size
according to application-dependent requirements. The idea is to select and apply to
0
3
1
2
(a)
(b)
Fig. 3.4. (a) A simple multiresolution model composed of a base mesh and three updates, bold
gray line represents a cut; (b) the mesh corresponding to the front represented by the bold gray
line