On mesh intersection robustness and efficiency

@inproceedings{levy_mesh_RM2023,
 abstract = {In this article, we discuss on mesh intersection, a problem that seems trivial at first sight, but that requires special care in practice, because of numerical precision issues. We present an algorithm that takes an arbitrary soup of triangles and that computes the exact co-refinement, that is, a set of non-intersecting vertices, edges and triangular facets that represent the intersection. The algorithm starts by determining the candidate facet intersection pairs using an axis-aligned bounding-boxes hierarchy. Then, for each pair of triangle, it determines the intersection (that can be a point, a segment, or a polygon in some degenerate cases). Finally, each triangle that contains some intersections is remeshed, using a 2D constrained Delaunay triangulation. To exactly represent the coordinates of the intersections, we use expansions, that are also used in Shewchuk’s predicates. The difference here is that expansions are used to store the coordinates of generated points. Several programming techniques make it possible to use 3D points and vectors with arbitrary-precision coordinates at a reasonable speed. Our constrained Delaunay triangulation uses predicates based on the exact coordinates of the generated points, and symbolic perturbation to ensure the uniqueness of the triangulation.},
 author = {Levy, Bruno and Li, Wan-Chiu and Borgese, Cedric},
 booktitle = {2023 {RING} meeting},
 language = {en},
 pages = {22},
 publisher = {ASGA},
 title = {On mesh intersection robustness and efficiency},
 year = {2023}
}