Weighted Squared Volume Minimization (WSVM) for Generating Uniform Tetrahedral Meshes

Kaixin Yu^*1,2
Yifu Wang^*1
Peng Song³
Xiangqiao Meng⁴
Ying He^2†
Jianjun Chen^1†

¹ School of Aeronautics and Astronautics, Zhejiang University, Hangzhou, China.
² College of Computing and Data Science, Nanyang Technological University, Singapore.
³ Pillar of Information Systems Technology and Design, Singapore University of Technology and Design, Singapore.
⁴ Department of Computing, The Hong Kong Polytechnic University, Hong Kong, China.

Paper (arXiv) Code: coming soon

Abstract

This paper presents a new algorithm, Weighted Squared Volume Minimization (WSVM), for generating high-quality tetrahedral meshes from closed triangle meshes. Drawing inspiration from the principle of minimal surfaces that minimize squared surface area, WSVM employs a new energy function integrating weighted squared volumes for tetrahedral elements. When minimized with constant weights, this energy promotes uniform volumes among the tetrahedra. Adjusting the weights to account for local geometry further achieves uniform dihedral angles within the mesh. The algorithm begins with an initial tetrahedral mesh generated via Delaunay tetrahedralization and proceeds by sequentially minimizing volume-oriented and then dihedral angle-oriented energies. At each stage, it alternates between optimizing vertex positions and refining mesh connectivity through the iterative process. The algorithm operates fully automatically and requires no parameter tuning. Evaluations on a variety of 3D models demonstrate that WSVM consistently produces tetrahedral meshes of higher quality, with fewer slivers and enhanced uniformity compared to existing methods.

Algorithmic pipeline. (a) Our method takes a set of watertight, high-quality manifold triangular meshes as the input boundaries. (b) The initial tetrahedral mesh, constructed via Delaunay tetrahedralization. Elements with dihedral angles less than \(30^\circ\) are rendered in red. Minimizing the volume-oriented energy improves the uniformity of the volume of tetrahedra. (c) Subsequently, minimizing the dihedral angle-oriented energy further reduces the number of bad elements. (d) The final high quality tetrahedral mesh. The red and blue histograms represent the volume distribution and dihedral angle distribution of tetrahedral elements, respectively. In each angle histogram, we indicate the range of dihedral angles \([\theta_{\min}, \theta_{\max}]\) via short solid lines and the average of the minimal and maximal angles \(\theta_{\min}^{\mathrm{avg}}\) and \(\theta_{\max}^{\mathrm{avg}}\) via long dashed lines.

The change of tetrahedra with minimum dihedral angles less than 30 degrees during optimization.

Quality comparison between the input model, the initial tetrahedral mesh, and the optimized results of WSVM (with quality values, where 0 is best)

Comparison

Comparison of WSVM with various methods, for the first two models, elements with dihedral angles less than 30 degrees are rendered in red. For the latter two models, we show the mesh visualization colored by equiangle skewness values, along with corresponding histograms indicating the distribution of skewness values. The histograms highlight the minimum, average, and maximum skewness values, represented by green bars on the plot.

More results

Visualization of selected results across the test models. For each model, we present: a slice view of Equiangle Skewness quality, a visualization highlighting tetrahedra with minimum dihedral angles less than 30 degrees, and histograms depicting the distribution of dihedral angles (blue) and tetrahedron volumes (red).

        
          @misc{yu2024wsvm,
            author={Kaixin Yu and Yifu Wang and Peng Song and Xiangqiao Meng and Ying He and Jianjun Chen},
            title={Weighted Squared Volume Minimization (WSVM) for Generating Uniform Tetrahedral Meshes},
            howpublished={arXiv:2409.05525 [cs.GR]},
            month={September},
            year={2024},
            doi={10.48550/arXiv.2409.05525},
            url={https://arxiv.org/abs/2409.05525v1}
          }