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

Valentin Z. NIGOLIAN (valentin.nigolian@gmail.com), Marcel CAMPEN, David BOMMES ACM Transaction on Graphics (Proceedings of SIGGRAPH Asia 2024)

Given a ball-topology tetrahedral mesh (left) and star-shaped boundary constraints, we generate a bijective piecewise linear map for the interior (right). We improve the recent Shrink-and-Expand approach [Nigolian et al. 2023], which relies on a two-step process. During the first \textit{shrinkage} step, all interior vertices are clustered to a single focal point, degenerating most tetrahedral elements. In the second \textit{expansion} step, interior vertices (blue) are successively detached from the cluster while ensuring that tetrahedra formed by expanded vertices are strictly positively oriented(orange). We introduce the concept of the cluster mesh (red), motivated by the observation that its topology provides all information necessary to efficiently determine a viable expansion sequence.

Project Page Dataset

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.

Building

This code assumes that CGAL is installed on your system.

It also depends on Eigen, OpenVolumeMesh, Google's or-tools and N. Lohmann's JSON parser, but those are downloaded as part of the (CMake) build process.

Alternatively, you can run either of the binaries in the corresponding folder.

##Usage The method can be run using ClusterMesh_SAE [input_mesh.ovm] [boundary_conditions.txt] [output_mesh.ovm]

The boundary conditions should contain a list of [index pos_x pos_y pos_z] entries for each boundary vertex and its prescribed boundary position (see the examples folder).