Good Random Multi-Triangulation of Surfaces.

Area of Science:

• Computer Graphics
• Computational Geometry
• Surface Reconstruction

Background:

• Multi-triangulation (MT) offers variable resolution surface representation.
• Hierarchical Poisson Disk Sampling (HPDS) provides well-spaced point distributions with blue noise characteristics.
• Existing methods often lack guarantees on mesh shape quality and adaptive resolution.

Purpose of the Study:

• Introduce the Hierarchical Poisson Disk Sampling Multi-Triangulation (HPDS-MT) for surface representation.
• Develop a method for extracting adaptive triangle meshes with guaranteed good shape quality.
• Analyze the theoretical properties and practical performance of the HPDS-MT.

Main Methods:

• Construct HPDS-MT using a preprocessed hierarchy of points.
• Employ incremental simplification for Multi-Triangulation (MT) construction.
• Implement and validate the HPDS-MT computation for accuracy and performance.

Main Results:

• HPDS-MT successfully extracts adaptive meshes with guaranteed triangle shape quality.
• Theoretical properties of shape quality are proven.
• The Hausdorff distance between the original surface and extracted meshes is bounded by the HPDS radii distribution.

Conclusions:

• HPDS-MT provides a robust framework for adaptive surface meshing with superior shape quality.
• The method demonstrates high accuracy and outperforms existing techniques in geometry processing.
• HPDS-MT offers significant advantages for various geometry processing tasks.