PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Tetrahedral Meshing in the Wild

Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, Daniele Panozzo

arXiv:1908.03581v2cs.GR

TL;DR

Imperfect triangle soups violate the assumptions of traditional tetrahedral meshing, while TetWild remains costly and does not guarantee a valid floating-point output. fTetWild incrementally inserts triangles into and optimizes a floating-point mesh, producing robust, high-quality tetrahedral meshes with faster execution. It is also useful for mesh repair and approximate Boolean or arrangement operations, though some input triangles can theoretically remain uninserted and floating-point energy evaluation can become unstable for large energies.

  • Problem

    Traditional meshing assumes clean manifold inputs, while TetWild’s rational arithmetic is slow and its output is not guaranteed to remain valid after floating-point conversion.

  • Method

    fTetWild incrementally inserts input triangles into a floating-point tetrahedral mesh, locally re-tetrahedralizes, rejects invalid operations, and interleaves mesh optimization.

  • Results

    18.5s average runtime on 4540 shared Thingi10k models, compared with 22s for TetGen, 95s for CGAL, and 107s for TetWild.

  • Takeaways & Limitations

    fTetWild combines TetWild-like robustness with Delaunay-comparable speed and supports volumetric meshing, mesh repair, and approximate Boolean operations.

  • Takeaways & Limitations

    Some input triangles may remain uninserted, and floating-point energy evaluation can become unstable when triangle energy is on the order of 10^8.

Abstract

from arXiv · show

We propose a new tetrahedral meshing method, fTetWild, to convert triangle soups into high-quality tetrahedral meshes. Our method builds on the TetWild algorithm, replacing the rational triangle insertion with a new incremental approach to construct and optimize the output mesh, interleaving triangle insertion and mesh optimization. Our approach makes it possible to maintain a valid floating-point tetrahedral mesh at all algorithmic stages, eliminating the need for costly constructions with rational numbers used by TetWild, while maintaining full robustness and similar output quality. This allows us to improve on TetWild in two ways. First, our algorithm is significantly faster, with running time comparable to less robust Delaunay-based tetrahedralization algorithms. Second, our algorithm is guaranteed to produce a valid tetrahedral mesh with floating-point vertex coordinates, while TetWild produces a valid mesh with rational coordinates which is not guaranteed to be valid after floating-point conversion. As a trade-off, our algorithm no longer guarantees that all input triangles are present in the output mesh, but in practice, as confirmed by our tests on the Thingi10k dataset, the algorithm always succeeds in inserting all input triangles.

1 INTRODUCTION

fTetWild addresses the assumptions and computational costs of tetrahedralizing imperfect triangle soups by combining robust processing with floating-point construction and optimization. It improves on TetWild with faster execution, valid floating-point outputs, and practical utility across meshing and geometry-processing applications.

  • Motivation: Traditional tetrahedral meshing assumes closed, manifold, non-self-intersecting inputs, but imperfect real-world geometric data often violates these conditions.Such data can contain self-intersections, gaps, and elements that are numerically unstable or too close together.
  • Motivation: TetWild robustly tetrahedralizes triangle soups using exact rational computations and geometric tolerance, but its rational-to-floating-point conversion can fail and its runtime is long.These are respectively TetWild’s theoretical and practical downsides relative to the desired output and performance.
  • fTetWild: fTetWild incrementally inserts one input triangle at a time into a floating-point tetrahedral mesh, locally re-tetrahedralizing and interleaving mesh optimization.Rejected triangles are retried after quality improvement, when insertion is less likely to fail.
  • fTetWild: fTetWild guarantees a valid tetrahedral mesh with floating-point vertex positions and avoids rational-number overhead, while remaining robust and supporting batch processing without parameter tuning.Floating-point arithmetic also simplifies parallelization during mesh optimization.
  • Applications: The method extends beyond volumetric meshing to mesh repair and approximate mesh arrangements, where it provides valid floating-point outputs under broader input conditions.The paper demonstrates tetrahedralization on 10,000 Thingi10k models, approximate Booleans, and simulations of elasticity, fluid flow, and heat diffusion.

2 RELATED WORK

The related work spans tetrahedral meshing, mesh repair, and Boolean or arrangement operations, with existing methods often trading robustness, accuracy, quality, or computational cost. fTetWild combines incremental background-mesh insertion and optimization to handle imperfect inputs while maintaining uniformly high mesh quality.

  • 2.1 Tetrahedral Meshing: Delaunay methods are widely used for tetrahedral meshing, and the paper compares fTetWild directly with TetGen and CGAL.TetGen and CGAL are used as comparison systems in Section 4.
  • 2.1 Tetrahedral Meshing: Background-grid methods are simpler and more robust than Delaunay methods but struggle with imperfect geometry and may produce poor-quality boundary elements.fTetWild borrows the background-mesh idea while incrementally inserting elements and interleaving optimization stages.
  • 2.1 Tetrahedral Meshing: Front-advancing methods create high-quality elements near boundaries but encounter interior corner cases where fronts meet, lowering element quality.
  • 2.1 Tetrahedral Meshing: Envelope-based methods address imperfect inputs through tolerance-based approximations, including TetWild for volumetric meshing and TriWild for its two-dimensional counterpart.
  • 2.2 Applications: Existing mesh-repair approaches include local healing, tetrahedralization followed by boundary extraction, and methods that can be computationally expensive or delete substantial mesh regions.fTetWild is positioned as another tetrahedralization-based option for repair.
  • 2.2 Applications: Boolean and arrangement methods commonly assume closed, manifold, non-self-intersecting, or positively wound inputs, while other approaches trade accuracy or robustness for efficiency.fTetWild permits gaps, self-intersections, and degeneracies, and can eliminate near-degenerate or overly refined input triangles.
  • 2.2 Applications: fTetWild converts an imperfect surface mesh with self-intersections and poor base triangulation into a high-quality tetrahedral mesh.

3 METHOD

fTetWild tetrahedralizes imperfect triangle soups using floating-point coordinates throughout, combining envelope-based robustness with incremental face insertion and mesh improvement. It maintains validity during processing while accepting that some input faces may theoretically remain uninserted.

  • Input and robustness: fTetWild accepts arbitrarily connected, potentially intersecting triangle soups with duplicated vertices and uses target edge length ℓ and envelope size ϵ as user-defined parameters.The ϵ-envelope bounds the permitted deviation from the input surface.
  • Incremental construction: Unlike TetWild’s rational polyhedral construction, fTetWild inserts one input triangle at a time into a floating-point background tetrahedral mesh and re-tetrahedralizes locally.Operations producing inverted or degenerate elements are rejected.
  • Validity and efficiency: The method uses only floating-point vertex coordinates while maintaining a valid inversion-free tetrahedral mesh with exact predicates and table-based local subdivision.This reduces running time and memory consumption while preserving the mesh’s validity conditions.
  • Failure handling: Triangle insertion can fail because floating-point limitations create numerically zero-volume tetrahedra, after which the operation is rolled back and retried following mesh improvement.This is the only possible failure identified for fTetWild, although it never appeared in the reported experiments.
  • Pipeline: The four phases are input simplification, background-mesh generation with iterative triangle insertion, mesh improvement with reinsertion attempts, and optional removal of exterior elements.The overview summarizes the same sequence from simplification through filtering.

3.4 Incremental Triangle Insertion

Incremental triangle insertion identifies affected tetrahedra, constructs a tolerance-based covering near the triangle’s plane, and subdivides the affected region using fixed connectivity patterns. Snapping and exact predicates help preserve validity despite floating-point arithmetic.

  • Background mesh: A background Delaunay tetrahedralization is created from preprocessed vertices inside a box expanded by 2ϵ around the input bounding box.Additional points are inserted uniformly and at least ϵ away from input faces.
  • Finding cut tetrahedra: The affected set TI initially contains tetrahedra cut by the inserted triangle, where cutting requires interior-point intersection or complete containment.The set is iteratively expanded during snapping and intersection processing.
  • Robust predicates: Exact predicates test containment and triangle–triangle cuts, ensuring topological correctness despite floating-point coordinates.The predicates support robust decisions during affected-region construction.
  • Plane–tetrahedra intersection: The insertion constructs a cover whose faces stay within δ of every point of the triangle and whose projections onto the plane cover the triangle.Allowing the cover to deviate from the plane is crucial for robust floating-point insertion.
  • Tolerance choice: The first insertion pass uses δ = max(ϵzero, 10^-3ϵ), while later passes reduce the tolerance to δ = ϵzero.The larger initial tolerance reduces insertion failures and subsequent mesh-optimization iterations.
  • Snapping: If moving a near-plane vertex would invert an element, the algorithm instead deforms the cover by moving suitable interior cover vertices to that vertex.Boundary-vertex effects require extending TI, whereas interior-vertex changes preserve the cover boundary.
  • Snapping: Vertices within δ of the plane are collected, moved to their closest points when safe, and used to expand TI through intersecting adjacent tetrahedra.The process repeats until no additional tetrahedra are added.
  • Tetrahedron subdivision: All tetrahedra sharing cut edges in TI and neighboring affected tetrahedra are subdivided using a precomputed table that preserves valid mesh connectivity.The table covers 41 realizable edge-cut configurations grouped into seven symmetry classes.

3.5 Mesh Improvement

fTetWild improves tetrahedral mesh quality through floating-point AMIPS optimization interleaved with incremental face insertion. It parallelizes smoothing, stabilizes high-energy evaluations, and handles open boundaries by projecting tracked vertices back to the boundary.

  • Mesh Improvement: The method adapts TetWild’s conformal AMIPS 3D energy optimization while specializing the framework for floating-point computation.AMIPS is differentiable and scale-invariant, making it suitable for mesh-quality optimization.
  • Mesh Improvement: Input faces are retried every three mesh-improvement iterations until all faces are inserted or optimization terminates.This change accommodates the possibility that floating-point computations cannot immediately insert every face.
  • Mesh Improvement: Vertex smoothing is parallelized with a graph-coloring strategy to improve performance.
  • Mesh Improvement: For tetrahedra with energy larger than 10^8, the method evaluates the cubed energy with rational arithmetic before rounding and taking the cubic root.Floating-point evaluation can become unstable at high energy and misidentify the descent direction, causing over-refinement.
  • Mesh Improvement: Optimization stops at a user-specified quality target or iteration limit; experiments use max AMIPS energy below 10 or 80 iterations.The reported experiments also use envelope size ϵ = 10^-3d and target edge length ℓ = d/20.
  • Mesh Improvement: Open-boundary vertices are tracked and projected back during mesh improvement, preserving the boundary while allowing the open side to be closed.Users may optionally smooth the closed open region.

3.6 Filtering

After mesh improvement, fTetWild filters the volumetric mesh using winding numbers. This supports both extracting tetrahedra inside the input surface and evaluating Boolean operations on triangle soups.

  • Filtering: The output is a volumetric tetrahedral mesh of the expanded bounding box with the preprocessed input triangles inserted.
  • Filtering: Fast winding numbers can remove tetrahedra outside the preserved or tracked input surface.
  • Filtering: For Boolean operations, triangle provenance produces generalized winding numbers that determine which tetrahedra satisfy the requested operation.For an intersection, tetrahedra inside both input triangle soups are retained.
  • Filtering: Compared with the prior arrangement method, this approach handles non-PWN surfaces, outputs a tetrahedral mesh, and preserves high surface quality through remeshing within the ϵ envelope.

4 RESULTS

On the Thingi10k dataset, fTetWild robustly tetrahedralizes real-world inputs, runs substantially faster than TetWild, and produces mesh quality and density comparable to TetWild. Its runtime is also comparable to TetGen on a common-success subset.

  • 4.1 Success Rate: 100% of the 10 000 Thingi10k meshes are successfully tetrahedralized under the stated memory and time limits.Most models use less than 1GB of RAM, although very complex models can require around 17GB.
  • 4.1 Success Rate: Only fTetWild and TetWild achieve high success rates among the compared methods on the full Thingi10k dataset.
  • 4.2 Running Time: 49.8s average runtime with code optimizations is seven times faster than TetWild’s serial implementation.With portable optimizations disabled, fTetWild averages 80.4s versus TetWild’s 360s.
  • 4.2 Running Time: The method is up to 17 times faster than TetWild on a challenging example.
  • 4.2 Running Time: 18.5s average runtime on 4540 common-success models is comparable to TetGen’s 22s and faster than CGAL’s 95s and TetWild’s 107s.Within less than 2 minutes, fTetWild tetrahedralizes 98.7% of the inputs.
  • 4.3 Mesh Quality: fTetWild produces geometric quality similar to TetWild across five quality measures on the full Thingi10k output.The comparison includes worst and average element quality.
  • 4.4 Mesh Density: The two methods generate meshes of similar density while targeting as-coarse-as-possible meshes that preserve the input surface.A user-specified sizing field can increase density when desired.
  • Mesh Repair: MeshFix is fast but loses details during repair, whereas fTetWild preserves them in the illustrated invalid-mesh example.The intermediate tetrahedral mesh has maximum AMIPS energy 1975, below the stopping threshold of 2000.

5 APPLICATIONS

fTetWild supports mesh repair, Boolean operations, physical simulation, and challenging real-world geometries while maintaining valid tetrahedral meshes throughout optimization. Its applications exploit robustness to imperfect inputs and the ability to stop optimization early.

  • 5 APPLICATIONS: fTetWild repairs imperfect triangle meshes by extracting a high-quality manifold boundary within the prescribed distance from the input soup.Optimization can stop once all input faces are used because the mesh remains inversion-free and floating-point throughout.
  • 5 APPLICATIONS: For imperfect CAD surfaces, fTetWild computes approximate unions, differences, and intersections when Mesh Arrangements and CGAL cannot operate on non-PWN inputs.The output is a tetrahedral mesh with a high-quality triangular boundary, providing robust but slower Boolean operations.
  • 5 APPLICATIONS: fTetWild successfully tetrahedralizes models with severe self-intersections, degenerate triangles, and up to 93 million vertices.The architectural example contains 80 999 self-intersecting faces, while the 93-million-vertex example remains geometrically high quality under different envelope sizes.
  • 5 APPLICATIONS: The resulting high-quality tetrahedral meshes are suitable for downstream finite-element simulation and fluid-flow applications.Boolean difference is used to generate a background mesh for flow around an obstacle in a cylindrical tube.
  • 5 APPLICATIONS: Shared-memory parallelization benefits fTetWild, while distributed HPC parallelization and more advanced techniques remain future work.The authors also identify dynamic remeshing and extension to two-dimensional triangle meshing as future directions.

Q. Zhou and A. Jacobson. 2016. Thingi10K: A Dataset of 10, 000 3D-Printing Models.

The cited passage identifies the Thingi10K dataset as a collection of 10,000 3D-printing models published by Zhou and Jacobson in 2016.

  • Q. Zhou and A. Jacobson. 2016. Thingi10K: A Dataset of 10, 000 3D-Printing Models.: The cited work is authored by Q. Zhou and A. Jacobson and dated 2016.The passage identifies the authors and publication year.
  • Q. Zhou and A. Jacobson. 2016. Thingi10K: A Dataset of 10, 000 3D-Printing Models.: The cited record is available as CoRR abs/1605.04797 and arXiv:1605.04797.These identifiers specify the referenced preprint record.

A A BRIEF DESCRIPTION OF THE TETWILD ALGORITHM

TetWild starts from a Delaunay-based background mesh, uses BSP subdivision and rational arithmetic to preserve input triangles robustly, then improves and filters the tetrahedralization.

  • A BRIEF DESCRIPTION OF THE TETWILD ALGORITHM: TetWild generates an initial background tetrahedralization from input points plus regularly sampled grid points to improve element shapes.The background mesh is produced using unconstrained Delaunay tetrahedralization.
  • A BRIEF DESCRIPTION OF THE TETWILD ALGORITHM: BSP subdivision converts each input triangle into a plane that cuts background tetrahedra, producing a polyhedral mesh preserving the input faces.Convex polyhedra are then subdivided into tetrahedra.
  • A BRIEF DESCRIPTION OF THE TETWILD ALGORITHM: TetWild uses rational coordinates during subdivision and optimization to avoid numerical issues and maintain convex, non-inverted sub-elements.Rational coordinates complicate later floating-point rounding because poorly shaped tetrahedra may flip.
  • A BRIEF DESCRIPTION OF THE TETWILD ALGORITHM: Mesh improvement combines edge splitting, collapsing, swapping, and vertex smoothing while rolling back operations that invert tetrahedra or leave the epsilon envelope.The 3D conformal AMIPS energy measures tetrahedral quality.
  • A BRIEF DESCRIPTION OF THE TETWILD ALGORITHM: TetWild gradually rounds rational coordinates toward floating point during mesh improvement, although theoretically unroundable vertices can exist.Such vertices were not observed in tests on ten thousand models.
  • A BRIEF DESCRIPTION OF THE TETWILD ALGORITHM: TetWild removes exterior tetrahedra by filtering centroids according to their winding number relative to the tracked surface.Tetrahedra with centroid winding number larger than 0.5 are filtered out.

B EXAMPLE OF UNSTABLE AMIPS ENERGY

The example illustrates numerical instability in floating-point AMIPS evaluation for a tetrahedron, contrasted with a rationally computed reference value.

  • B EXAMPLE OF UNSTABLE AMIPS ENERGY: The passage introduces computation of the 3D AMIPS energy for a tetrahedron with four vertices.The example evaluates the energy using the tetrahedron's vertex data.
  • B EXAMPLE OF UNSTABLE AMIPS ENERGY: The AMIPS evaluation considers vertex permutations, with 24 total permutations and four shown as an example.The passage notes that the displayed subscript indicates vertex permutations.
  • B EXAMPLE OF UNSTABLE AMIPS ENERGY: The rational-number computation provides the correct AMIPS reference value for comparison with floating-point evaluations.The passage explicitly identifies the rational result as the correct value.

C UNUSED DECOMPOSITIONS OF A TETRAHEDRON

The authors identify two symmetry classes of tetrahedron-face triangulations whose decomposition would require an additional internal vertex. Their selection rule excludes both classes.

  • Two symmetry classes of face triangulations require an additional internal vertex.These are the two unused configurations shown in Figure 28.
  • Case 1 cannot be selected because the rule would imply the impossible cycle v3 > v2 > v1 > v3.
  • Case 2 is likewise excluded by the same type of contradiction.

D AN EXAMPLE FOR OPEN-BOUNDARY EDGE PRESERVATION

When an inserted triangle lies inside a tetrahedron, its open-boundary edges may not be preserved after the initial subdivision. The method performs an additional subdivision and computes projected intersections to restore those edges.

  • An interior inserted triangle can produce a larger plane–tetrahedron polygon, causing its open-boundary edges to be lost.
  • Figure 29 depicts the sequence from triangle insertion through sub-tetrahedron subdivision and edge-intersection recovery.
  • The tetrahedron is subdivided once more to preserve the triangle’s open-boundary edges.
  • The method projects the open-boundary edge and covering faces onto a best-fitting plane, computes 2D intersections, and lifts them back to 3D.The resulting intersection points define edges that are cut into two before neighboring tetrahedra are subdivided.

E CHANGES OF EDGE-CUT CONFIGURATION AFTER SNAPPING

After snapping, the method enumerates edge-cut configurations for cutting tetrahedra and restricts how many vertices can be snapped near the cutting plane.

  • Table 3 lists the possible edge-cut configurations before and after snapping for the four relevant symmetry classes.The remaining three classes are excluded because the tetrahedron is not cut or is affected only by neighboring tetrahedra.
  • A tetrahedron can have at most three vertices snapped to the cutting plane.
  • If all four vertices lie within δ of the plane, only the three closest vertices are snapped.
Loading 1908.03581v2…