A Shrink Wrapping Approach to Remeshing Polygonal Surfaces

Leif Kobbelt, Jens Vorsatz, Ulf Labsik, Hans-Peter SeidelComputer Graphics Forum 1999 · DOI

TL;DR

This paper introduces a novel "shrink wrapping" algorithm to convert arbitrary polygonal meshes into a specific "subdivision connectivity" format. This conversion is crucial for efficient multiresolution modeling and graphics applications, enabling smoother level-of-detail transitions and better data compression for transmission.

What Problem Does This Paper Address?

Computer graphics applications often deal with complex 3D models represented as polygonal meshes. While flexible, these meshes can have irregular structures that hinder efficient processing, especially for multiresolution representations. Many advanced algorithms, like those for progressive transmission or adaptive modeling, perform best when meshes have a uniform, predictable structure known as "subdivision connectivity." This structure arises from repeatedly applying a uniform subdivision rule to a simple "base mesh." The challenge is to convert a given, potentially complex and irregular, polygonal mesh into this structured subdivision connectivity format without losing geometric accuracy or introducing excessive distortion.

Methods

The core of the paper is a "shrink wrapping" approach inspired by how a plastic membrane conforms to an object. The algorithm simulates this by:

  • Deformable Surface Analogy: Treating the target subdivision mesh as a deformable membrane.
  • Attracting Force (Projection Operator P): Vertices of the shrinking mesh are projected onto the closest point on the original input mesh (M). This ensures the mesh stays "stuck" to the target geometry.
  • Relaxing Force (Umbrella Operator U): An internal force is applied to vertices to minimize mesh distortion and encourage even vertex distribution. This prevents the mesh from collapsing or self-intersecting.
  • Multi-Level Approach: To accelerate convergence and improve robustness, the process is applied iteratively across multiple levels of mesh refinement. A coarse mesh is first fitted, then refined, and the fitting process continues on the finer mesh.
  • Sphere Parameterization: A key innovation is parameterizing the input mesh onto a bounding sphere. This allows for a more stable and efficient relaxation process in the parameter domain, especially for complex or concave shapes, before projecting back to the 3D surface.
  • Base Mesh Construction: A method is presented to create a minimal, well-shaped base mesh (S0) that partitions the input surface into roughly equal area patches, crucial for uniform subdivision and reduced distortion.

Datasets

The paper evaluates its algorithm on several standard 3D models:

  • Stanford Bunny: A common benchmark for geometric processing.
  • Bust Model: A human bust model.
  • Brain Data: A brain model extracted from CT volume data.

No new benchmarks are introduced; the focus is on demonstrating the algorithm's effectiveness on existing, complex datasets.

Key Insights and Ideas

  • Shrink Wrapping as a Metaphor: The intuitive analogy of shrink wrapping effectively captures the algorithm's goal: conforming a structured mesh to arbitrary geometry.
  • Sphere Parameterization for Robustness: Mapping the problem to a sphere significantly improves the stability and efficiency of the fitting process, especially for challenging geometries like concave regions. This is a clever way to sidestep issues with complex surface metrics.
  • Base Mesh Importance: The quality and structure of the initial base mesh (S0) are critical. Creating a base mesh with roughly equal area triangles is essential for achieving uniform subdivision and minimizing distortion across all refinement levels.
  • Multi-Level Iteration: Applying the shrink-wrapping process iteratively across multiple refinement levels is key to achieving both speed and accuracy, by providing good starting points for subsequent stages.
  • Progressive Transmission Benefits: The resulting subdivision connectivity meshes are ideal for progressive transmission, allowing for efficient streaming of 3D models with smooth level-of-detail transitions.

Key Results

The paper demonstrates successful remeshing of complex models into subdivision connectivity meshes with:

  • Extremely Small Base Meshes: For example, the Stanford bunny (70K triangles) is remeshed with a base mesh of only 38 triangles.
  • High Geometric Fidelity: The resulting subdivision surfaces closely approximate the original geometry.
  • Effective Progressive Transmission: Figures show that even with a very small percentage (1-10%) of detail coefficients, visually convincing approximations of the original models can be reconstructed.

Limitations and Future Work

  • Genus-Zero Surfaces: The current approach is primarily designed for genus-zero surfaces (topologically equivalent to a sphere). Extending it to handle meshes with holes or handles (higher genus) is a potential area for future work.
  • Parameter Domain Metric Differences: While the sphere parameterization helps, the metric of the original surface and its projection onto the sphere are not identical. The paper mentions this difference and suggests modifications to the relaxation rule to better account for it, implying that perfect metric preservation is still a challenge.
  • Switching Criteria: Deciding when to switch from relaxing in the parameter domain to relaxing directly on the 3D surface is noted as being difficult and model-dependent. Further research could refine these criteria for more automated and robust switching.

Summary updated

BibTeX
@article{kobbelt1999shrink,
  author = {Leif Kobbelt and Jens Vorsatz and Ulf Labsik and Hans-Peter Seidel},
  title = {{A Shrink Wrapping Approach to Remeshing Polygonal Surfaces}},
  journal = {Computer Graphics Forum},
  year = {1999},
  doi = {10.1111/1467-8659.00333},
}
Figure