Visual Computing

University of Konstanz
Computer Aided Geometric Design

Tetrahedral Meshing via Maximal Poisson-disk Sampling

J. Guo, D. Yan, L. Chen, X. Zhang, O. Deussen, P. Wonka


In this paper, we propose a simple yet effective method to generate 3D-conforming tetrahedral meshes from closed 2-manifold surfaces. Our approach is inspired by recent work on maximal Poisson-disk sampling (MPS), which can generate well-distributed point sets in arbitrary domains. We first perform MPS on the boundary of the input domain, we then sample the interior of the domain, and we finally extract the tetrahedral mesh from the samples by using 3D Delaunay or regular triangulation for uniform or adaptive sampling, respectively. We also propose an efficient optimization strategy to protect the domain boundaries and to remove slivers to improve the meshing quality. We present various experimental results to illustrate the efficiency and the robustness of our proposed approach. We demonstrate that the performance and quality (e.g., minimal dihedral angle) of our approach are superior to current state-of-the-art optimization-based approaches.


  acmid      = {2912369},
  address    = {Amsterdam, The Netherlands, The Netherlands},
  author     = {J. Guo and D. Yan and L. Chen and X. Zhang and O. Deussen and P. Wonka},
  doi        = {10.1016/j.cagd.2016.02.004},
  issn       = {0167-8396},
  issue_date = {March 2016},
  journal    = {Computer Aided Geometric Design},
  keywords   = {Maximal Poisson-disk sampling, Mesh optimization, Sliver removal, Tetrahedral mesh generation},
  month      = {mar},
  number     = {C},
  numpages   = {14},
  pages      = {186--199},
  publisher  = {Elsevier Science Publishers B. V.},
  title      = {Tetrahedral Meshing via Maximal Poisson-disk Sampling},
  volume     = {43},
  year       = {2016},

Supplemental Material

Paper (.pdf, 5.1 MB)