A Progressive Embedding Approach to Bijective Tetrahedral Maps driven by Cluster Mesh Topology

ACM Transactions on Graphics (SIGGRAPH ASIA 2024)
Valentin Z. Nigolian, Marcel Campen, David Bommes

Materials

Abstract

We present a novel algorithm to map ball-topology tetrahedral meshes onto star-shaped domains with guarantees regarding bijectivity. Our algorithm is based on the recently introduced idea of Shrink-and-Expand, where images of interior vertices are initially clustered at one point (Shrink-), before being sequentially moved to non-degenerate positions yielding a bijective map (-and-Expand). In this context, we introduce the concept of the cluster mesh, i.e. the unexpanded interior mesh consisting of geometrically degenerate simplices. Using local, per-vertex connectivity information solely from the cluster mesh, we show that a viable expansion sequence guaranteed to produce a bijective map can always be found as long as the mesh is shellable. In addition to robustness guarantees for this ubiquitous class of inputs, other practically relevant benefits include improved parsimony and reduced algorithmic complexity. While inheriting some of the worst-case high run time requirements of the state of the art, significant acceleration for the average case is experimentally demonstrated.

Selected figures

An example of a ``NO-BoUndary, Embeddable, Non-manifOld, Simply-connected Surface'' (NOBUENOSS) and how it can be constructed. The boundary edges (blue) are turned into non-manifold edges (red) by glueing them to another part of the mesh. In the resulting mesh, none of the vertices are on the boundary of a k-manifold. The resulting surface is 3D-embeddable and simply connected but does not separate space. A mesh with a NOBUENOSS interior cannot be handled by our method. However, we show in our paper that such configurations can be avoided for any "shellable" mesh. The right-most mesh is available for download in the list above.

BibTeX

@article{Nigolian:2024:cluster_mesh_SAE,
  author = {Nigolian, Valentin Z. and Campen, Marcel and Bommes, David},
  title = {A Progressive Embedding Approach to Bijective Tetrahedral Maps driven by Cluster Mesh Topology},
  journal = {ACM Transactions on Graphics},
  volume = {43},
  number = {6},
  year = {2024},
  publisher = {ACM},
  address = {New York, NY, USA},
  doi = {10.1145/3687992}
}