Articolo in rivista, 2020, ENG, 10.1145/3414685.3417818

Fast and robust mesh arrangements using floating-point arithmetic

G. Cherchi, M. Livesu, R. Scateni and M. Attene

University of Cagliari, Italy; IMATI - CNR, Italy

We introduce a novel algorithm to transform any generic set of triangles in 3D space into a well-formed simplicial complex. Intersecting elements in the input are correctly identified, subdivided, and connected to arrange a valid configuration, leading to a topologically sound partition of the space into piece-wise linear cells. Our approach does not require the exact coordinates of intersection points to calculate the resulting complex. We represent any intersection point as an unevaluated combination of input vertices. We then extend the recently introduced concept of indirect predicates [Attene 2020] to define all the necessary geometric tests that, by construction, are both exact and efficient since they fully exploit the floating-point hardware. This design makes our method robust and guaranteed correct, while being virtually as fast as non-robust floating-point based implementations. Compared with existing robust methods, our algorithm offers a number of advantages: it is much faster, has a better memory layout, scales well on extremely challenging models, and allows fully exploiting modern multi-core hardware with a parallel implementation. We thoroughly tested our method on thousands of meshes, concluding that it consistently outperforms prior art. We also demonstrate its usefulness in various applications, such as computing efficient mesh booleans, Minkowski sums, and volume meshes.

ACM transactions on graphics 39 (6), pp. 250:1–250:16

Keywords

Computing methodologies: Mesh geometry models, Mesh models; Intersections, geometric predicates, mesh booleans, constrained triangulation

CNR authors

Attene Marco, Livesu Marco

CNR institutes

IMATI – Istituto di matematica applicata e tecnologie informatiche "Enrico Magenes"