Multiresolution Volume Simplification and Polygonization

Nan Zhang, Arie E. KaufmanVG 2003 · DOI

TL;DR

This paper introduces a novel algorithm for simplifying and polygonizing 3D volumetric data, creating adaptive multiresolution representations. By combining hierarchical cell merging with quadric error metrics and an enhanced surfacenets algorithm, it effectively preserves sharp features and improves mesh quality while allowing for user-defined error tolerances.

What Problem Does This Paper Address?

Visualizing large 3D volumetric datasets interactively is a significant challenge due to increasing data sizes. Traditional methods like uniform downsampling often lead to a loss of sharp features and geometric fidelity. While adaptive techniques exist, they can struggle with generating well-formed polygons or maintaining topological consistency. This paper aims to bridge this gap by providing an adaptive multiresolution volume simplification and polygonization method that balances geometric accuracy, mesh quality, and computational efficiency.

Methods

The proposed approach is a two-step process:

  1. Bottom-up Hierarchical Cell Merging:
    • The algorithm starts with leaf cells of a volume octree. Each "gray" cell (representing a boundary) is assigned a representative vertex and an associated geometric error, quantified by quadric error metrics.
  2. Cells are merged hierarchically. To prevent topological issues during merging, "erroneous" cells (those that would lead to invalid polygonization) are disabled, and cells with disconnected surface components are penalized with additional costs.
  3. A novel aspect is the use of weighted quadric error metrics, where weights are based on triangle areas, and the incorporation of a "disconnected components" flag to penalize merges that could alter topology.
  4. Top-down Adaptive Polygonization:
    • After building the error hierarchy, a top-down traversal collects cells within a user-specified error threshold.
  5. The surfacenets algorithm is used for polygonization, enhanced with:
  6. Online Triangle Shape Optimization: Local edge swapping is employed to improve triangle quality, especially for sliver triangles that can arise from large error thresholds.
  7. Triangle-Budget Polygonization: This allows users to specify a maximum number of triangles, prioritizing simplification based on error and triangle count.
  8. A novel octree implementation is discussed, which simplifies neighborhood searches and polygonization operations.

Datasets

The paper evaluates its method on several datasets:

  • A voxelized sphere and sphereflake.
  • A voxelized cube.
  • An engine dataset converted from a CT volume.

These datasets are used to demonstrate the algorithm's effectiveness in preserving features and generating simplified meshes under various error thresholds.

Key Insights and Ideas

  • Adaptive Resolution is Crucial: Uniform downsampling is insufficient for preserving detail in volumetric data; adaptive methods are necessary.
  • Quadric Error Metrics for Volumes: Extending quadric error metrics, commonly used for surface simplification, to volumetric data is effective for geometric error estimation.
  • Handling Topology: Explicitly disabling erroneous cells and penalizing disconnected components during hierarchical merging is key to robust simplification and preventing topological errors in the output mesh.
  • Mesh Quality Matters: Simple polygonization can lead to poor triangle shapes. Online optimization techniques like edge swapping significantly improve visual quality without substantial computational overhead.
  • Triangle Budgeting for Control: Allowing users to specify a triangle budget provides practical control for real-time applications where rendering performance is critical.

Key Results

  • The algorithm successfully generates simplified volumes that preserve sharp features even at large error thresholds (e.g., Figure 9d shows a cube simplified to 12 triangles with a significant error tolerance).
  • The triangle shape optimization improves visual quality, offering a pleasing effect with Gouraud shading, and adds less than 10% overhead to the polygonization stage.
  • The adaptive simplification algorithm produces more robust results compared to uniform downsampling methods (Figure 7).
  • The preprocessing and polygonization are efficient, as shown in Table 1, with preprocessing times for a 512³ sphereflake at 19.6 seconds and polygonization times for various error thresholds being very low (e.g., 0.03 seconds for δ² = 10⁻²).

Limitations and Future Work

  • Limitations: The paper acknowledges that while it penalizes disconnected components, it doesn't strictly enforce manifoldness for all outputs, which might be a requirement for some applications. The current implementation uses at most two levels of recursion for detecting disconnected components for efficiency.
  • Future Work:
    • View-Dependent Rendering: Integrating viewing parameters into the error thresholding for more efficient view-dependent level-of-detail rendering.
  • Hierarchical Visibility Culling: Combining visibility culling with the simplification algorithm to further improve performance.
  • Multiple Representative Vertices: Investigating the use of multiple representative vertices per cell to achieve more drastic simplifications with less distortion.

Summary updated

BibTeX
@inproceedings{zhang2003multiresolution,
  author = {Nan Zhang and Arie E. Kaufman},
  title = {{Multiresolution Volume Simplification and Polygonization}},
  booktitle = {VG},
  year = {2003},
  doi = {10.2312/vg/vg03/087-094},
}
Figure