We introduce a novel algorithm to transform any generic set of triangles in3D space into a well-formed simplicial complex. Intersecting elements in theinput are correctly identified, subdivided, and connected to arrange a validconfiguration, leading to a topologically sound partition of the space intopiece-wise linear cells. Our approach does not require the exact coordinatesof intersection points to calculate the resulting complex. We represent anyintersection point as an unevaluated combination of input vertices. We thenextend the recently introduced concept of indirect predicates [Attene 2020] todefine all the necessary geometric tests that, by construction, are both exactand efficient since they fully exploit the floating-point hardware. This designmakes our method robust and guaranteed correct, while being virtually asfast as non-robust floating-point based implementations. Compared withexisting robust methods, our algorithm offers a number of advantages: itis much faster, has a better memory layout, scales well on extremely challengingmodels, and allows fully exploiting modern multi-core hardware with a parallel implementation. We thoroughly tested our method on thousandsof meshes, concluding that it consistently outperforms prior art. Wealso demonstrate its usefulness in various applications, such as computingefficient mesh booleans, Minkowski sums, and volume meshes.
展开▼
