Good Random Multi-Triangulation of Surfaces

We introduce the Hierarchical Poisson Disk Sampling Multi-Triangulation (HPDS-MT) of surfaces, a novel structure that combines the power of multi-triangulation (MT) with the benefits of Hierarchical Poisson Disk Sampling (HPDS). MT is a general framework for representing surfaces through variable resolution triangle meshes, while HPDS is a well-spaced random distribution with blue noise characteristics. The distinguishing feature of the HPDS-MT is its ability to extract adaptive meshes whose triangles are guaranteed to have good shape quality. The key idea behind the HPDS-MT is a preprocessed hierarchy of points, which is used in the construction of a MT via incremental simplification. In addition to proving theoretical properties on the shape quality of the triangle meshes extracted by the HPDS-MT, we provide an implementation that computes the HPDS-MT with high accuracy. Our results confirm the theoretical guarantees and outperform similar methods. We also prove that the Hausdorff distance between the original surface and any (extracted) adaptive mesh is bounded by the sampling distribution of the radii of Poisson-disks over the surface. Finally, we illustrate the advantages of the HPDS-MT in some typical problems of geometry processing.