Multi-resolution Modeling, Visualization
and Streaming of Volume Meshes

Keywords

Geometric modeling, visualization techniques, data compression.

Overview

Volume meshes are widely used in geometric modeling, object reconstruction, level set methods and accurate simulations of physical behaviors like deformable materials, objects under stress, fracture dynamics, optical effects and reproduction of smoke and fluid dynamics.

These techniques require bigger and bigger input meshes to obtain high quality results and for this reason the use of multi-resolution techniques is imperative in any interactive application managing non-trivial models.

This course covers the fundamental issues in multi-resolution modeling and visualization of volume meshes, including topics from mesh construction, visualization and compression. The presentation of each topic starts from the basics, to be understandable by a novice, and is conclude with a discussion of advanced research topics.

We present two classes of mesh generation techniques. Mesh decimation that reduces the size of high-resolution data within guaranteed quality error bounds, and subdivision methods that admit coarse models of a very general type and deal simply with adaptive refinement, sharp features as well as wavelet decompositions.

We discuss the foundations of multi-resolution data structures showing how to build a hierarchical model from a sequence of decimation operations. Efficient traversal strategies extract quickly adaptive approximations of the original data for rendering or further processing. As a special case, we present the detailed analysis of a very simple multi-resolution model that allows achieving realtime interaction (slicing and volume rendering) with a very large data set (rectilinear grid with eight billion nodes).

Interactive techniques for rendering large unstructured volume meshes are also covered in detail, with focus on direct volume rendering and extraction of level set surfaces. We conclude with efficient techniques for storing and transmitting volume meshes. This includes discussion of connectivity and geometry coding as well as different strategies for single resolution encoding versus progressive encoding. The most advanced topics will include compression of 4D meshes.

Simplification of Unstructured Tetrahedral Meshes (Paolo Cignoni)

In this section of the tutorial we will face two topics, first we will review the current solutions for the simplification of an unstructured volume dataset represented by a tetrahedral complex, shortly describing the existing algorithms and strategies. Then, we will give some hopefully useful hints to the efficient implementation of the skeleton of a simplification algorithm for tetrahedral meshes based on edge collapse.

Subdivision Methods for Volume Meshes (Valerio Pascucci)

The techniques for reducing the size of a volume dataset by preserving both the geometrical/topological shape and the information encoded in an attached scalar field are attracting growing interest. Given the framework of incremental 3Dmesh simplification based on edge collapse, the paper proposes an approach for the integrated evaluation of the error introduced by both the modification of the domain and the approximation of the field of the original volume dataset. We present and compare various techniques to evaluate the approximation error or to produce a sound prediction. A flexible simplification tool has been implemented, which provides different degree of accuracy and computational eficiency for the selection of the edge to be collapsed. Techniques for preventing a geometric or topological degeneration of the mesh are also presented.

Level-of-detail Data Structures for Tetrahedral Meshes (Leila De Floriani)

In this notes, we describe and evaluate data structures for representing LOD models based on regular and irregular tetrahedral meshes. We also discuss selective refinement queries relevant to volume data visualization as well as various approaches to selective refinement on an LOD data structure. Finally, we report some results and experimental comparisons.

Real-time Rendering in External Memory (Valerio Pascucci)

Increases in the number and size of volumetric meshes have popularized the use of hierarchical multi-resolution representations for visualization. A key component of these schemes has become the adaptive traversal of hierarchical data-structures to build, in real time, approximate representations of the input geometry for rendering. For very large datasets this process must be performed out-of-core. This part introduces a new cache oblivious data layout that accelerates adaptive traversal of geometric data represented with binary trees by improving the locality of hierarchical/ spatial data access. Such improvements play a critical role in the enabling of effective out-of-core processing. Three features make the scheme particularly attractive: (i) the data layout is independent of the external memory device blocking factor, (ii) the computation of the index for rectilinear grids is implemented with simple bit address manipulations and (iii) the data is not replicated, avoiding performance penalties for dynamically modified data. We reports performance statistics for the fundamental visualization technique of rendering arbitrary planar slices. Performance comparisons with alternative indexing approaches confirm the advantages predicted by the analysis of the scheme. Similar sdvantages are observed for volume rendering and isosurface computation.

Isosurface Computation Made Simple:
Hardware Acceleration, Adaptive Refinement and Tetrahedral Stripping (Valerio Pascucci)

This paper presents a simple approach for rendering isosurfaces of a scalar field. Using the vertex programming capability of commodity graphics cards, we transfer the cost of computing an isosurface from the Central Processing Unit (CPU), running the main application, to the Graphics Processing Unit (GPU), rendering the images. We consider a tetrahedral decomposition of the domain and draw one quadrangle (quad) primitive per tetrahedron. A vertex program transforms the quad into the piece of isosurface within the tetrahedron. In this way, the main application is only devoted to streaming the vertices of the tetrahedra from main memory to the graphics card. For adaptively refined rectilinear grids, the optimization of this streaming process leads to the definition of a new 3D space-filling curve, which generalizes the 2D Sierpinski curve used for efficient rendering of triangulated terrains. We maintain the simplicity of the scheme when constructing view-dependent adaptive refinements of the domain mesh. In particular, we guarantee the absence of T-junctions by satisfying local bounds in our nested error basis. The expensive stage of fixing cracks in the mesh is completely avoided. We discuss practical tradeoffs in the distribution of the workload between the application and the graphics hardware. With current GPU's it is convenient to perform certain computations on the main CPU. Beyond the performance considerations that will change with the new generations of GPU's this approach has the major advantage of avoiding completely the storage in memory of the isosurface vertices and triangles.

Volume Rendering (Claudio Silva)

Volume rendering is a powerful computer graphics technique for the visualization of large quantities of 3D data. It is specially well suited for three dimensional scalar and vector fields. Fundamentally, it works by mapping quantities in the dataset (such as color, transparency) to properties of a cloud-like material. Images are generated by modeling the interaction of light with the cloudy materials. Because of the type of data being rendered and the complexity of the lighting models, the accuracy of the volume representation and of the calculation of the volume rendering integrals are of major concern and have received considerable interest from researchers in the field.

Compressing Volumes and Animations (Jarek Rossignac)

This tutorial discusses compression techniques for reducing the storage requirements and transmission delays for triangle meshes, for their animations, for volumetric models representing a scalar field sampled at the vertices of a tetrahedral mesh, and finally for regularly sampled volumetric scalar fields that evolve with time.

Streaming Simplification and Compression of Unstructured Meshes (Peter Lindstrom)

This part of the tutorial describes representations of unstructured meshes as streams of triangles and methods for simplifying and compressing them. Windowed stream processing of geometric data is a new approach to performing out-of-core computations on large, even unbounded data sets using a fixed-size in-core buffer--a "sliding window"--through which an ordered sequential stream of mesh elements flows. While stream processing algorithms must respect the sequential order in which triangles arrive and process them in a single pass, full connectivity of the active submesh currently buffered is available, allowing random access to a coherent piece of the possibly much larger data set.