58
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
The out-of-core organization in this case is very simple, thanks to the approach that
acts on the different levels of granularity of nodes in the hierarchy. The triangle bintree is relatively small, even for huge models, and can easily be kept in main memory.
The mesh associated with a macrotriangle is stored in a disk page through a compact
data structure.
In [5], the same approach is extended to work on multitessellations, that is, the
general model, in which the hierarchy is represented by a DAG. Also in this case,
every node of the DAG contains a patch of a few thousands of triangles and is stored
in secondary memory, while the DAG describing the dependency relation among
updates is small enough to be kept in core. As for the standard multitessellation, this
model can be used for both terrains and 3D shapes.
The model is constructed by computing a partition of the input mesh into patches
of almost equal size. Such patches are computed by uniformly distributing on the
mesh a set of seed points. The number of such points must be proportional to the
mesh size. Then, an approximated Voronoi diagram of the seed points is computed,
so that the Voronoi cells define the patches of the subdivision. Each patch is then
independently simplified, without modifying its boundary. Simplification of a patch
usually reduces the number of triangles by a factor of 2. The same process described
above is applied again to the simplified mesh by starting with a new, smaller set
of seed points. The process is repeated until the resulting mesh satisfies some size
constraint. It has been shown that the number of steps is usually logarithmic in the
size of the mesh. The DAG describing the dependency relation is built during this
process.
During selective refinement, the DAG is traversed, and only those patches that
are needed to achieve the resolution required by the user are loaded into the memory. Each patch is stored as a compressed triangle strip to improve rendering
performances.
Lindstrom [30] and Shaffer and Garland [43] have proposed two similar outof-core multiresolution models for massive triangle meshes describing 3D scenes
generated through vertex clustering. The purpose is in both cases view-dependent
rendering of very large 3D meshes. The multiresolution model is an octree in which
the leaves store the vertices of the mesh at full resolution, or of an already simplified
mesh (in the case of Lindstrom’s approach), while the internal octree cells represent
vertices obtained as a result of the vertex clustering process and the triangles are
associated with cells containing their vertices.
Lindstrom’s approach is based on the out-of-core simplification technique reported in Sect. 3.3. The construction of the multiresolution model is performed in
two steps. During the first step, the mesh is regularly sampled. Each side of the sampling grid is composed by 2
n cells, where n is a user-defined quantity. After that, the
vertices are sorted in external memory according to their position in the grid. This
guarantees local access during the construction of the hierarchy. The second step
considers the simplified mesh, composed of the list of vertices, error information,
and the list of triangles, and produces an octree having the simplified mesh stored in
its leaves. Starting from a group of sibling vertices, position, normal, and error of the
parent are computed. Note that a leaf cell stores just the vertex and its normal, while
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
The out-of-core organization in this case is very simple, thanks to the approach that
acts on the different levels of granularity of nodes in the hierarchy. The triangle bintree is relatively small, even for huge models, and can easily be kept in main memory.
The mesh associated with a macrotriangle is stored in a disk page through a compact
data structure.
In [5], the same approach is extended to work on multitessellations, that is, the
general model, in which the hierarchy is represented by a DAG. Also in this case,
every node of the DAG contains a patch of a few thousands of triangles and is stored
in secondary memory, while the DAG describing the dependency relation among
updates is small enough to be kept in core. As for the standard multitessellation, this
model can be used for both terrains and 3D shapes.
The model is constructed by computing a partition of the input mesh into patches
of almost equal size. Such patches are computed by uniformly distributing on the
mesh a set of seed points. The number of such points must be proportional to the
mesh size. Then, an approximated Voronoi diagram of the seed points is computed,
so that the Voronoi cells define the patches of the subdivision. Each patch is then
independently simplified, without modifying its boundary. Simplification of a patch
usually reduces the number of triangles by a factor of 2. The same process described
above is applied again to the simplified mesh by starting with a new, smaller set
of seed points. The process is repeated until the resulting mesh satisfies some size
constraint. It has been shown that the number of steps is usually logarithmic in the
size of the mesh. The DAG describing the dependency relation is built during this
process.
During selective refinement, the DAG is traversed, and only those patches that
are needed to achieve the resolution required by the user are loaded into the memory. Each patch is stored as a compressed triangle strip to improve rendering
performances.
Lindstrom [30] and Shaffer and Garland [43] have proposed two similar outof-core multiresolution models for massive triangle meshes describing 3D scenes
generated through vertex clustering. The purpose is in both cases view-dependent
rendering of very large 3D meshes. The multiresolution model is an octree in which
the leaves store the vertices of the mesh at full resolution, or of an already simplified
mesh (in the case of Lindstrom’s approach), while the internal octree cells represent
vertices obtained as a result of the vertex clustering process and the triangles are
associated with cells containing their vertices.
Lindstrom’s approach is based on the out-of-core simplification technique reported in Sect. 3.3. The construction of the multiresolution model is performed in
two steps. During the first step, the mesh is regularly sampled. Each side of the sampling grid is composed by 2
n cells, where n is a user-defined quantity. After that, the
vertices are sorted in external memory according to their position in the grid. This
guarantees local access during the construction of the hierarchy. The second step
considers the simplified mesh, composed of the list of vertices, error information,
and the list of triangles, and produces an octree having the simplified mesh stored in
its leaves. Starting from a group of sibling vertices, position, normal, and error of the
parent are computed. Note that a leaf cell stores just the vertex and its normal, while