Robustness and Efficiency of Geometric Programs The Predicate Construction Kit (PCK)

Bruno Lévy 1
1 ALICE - Geometry and Lighting
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : In this article, I focus on the robustness of geometric programs (e.g., De-launay triangulation, intersection between surfacic or volumetric meshes, Voronoi-based meshing. . .) w.r.t. numerical degeneracies. Some of these geometric programs require " exotic " predicates, not available in standard libraries (e.g., J.-R. Shewchuk's implementation and CGAL). I propose a complete methodology and a sample Open Source implementation of a toolset (PCK: Predicate Construction Kit) that makes it reasonably easy to design geometric programs free of numerical errors. The C++ code of the predicates is automatically generated from its formula, written in a simple specification language. Robustness is obtained through a combination of arithmetic filters, expansion arithmetics and symbolic perturbation. As an example of my approach, I give the formulas and PCK source-code for the 4 predicates used to compute the intersection between a 3d Voronoi diagram and a tetrahedral mesh, as well as symbolic perturbations that provalby escapes the corner cases. This allows to robustly compute the intersection between a Voronoi diagram and a triangle mesh, or the intersection between a Voronoi diagram and a tetrahedral mesh. Such an algorithm may have several applications, including surface and volume meshing based on Lloyd relaxation.
Document type :
Journal articles
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01225202
Contributor : Bruno Levy <>
Submitted on : Thursday, November 5, 2015 - 4:50:02 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:25 PM
Long-term archiving on : Saturday, February 6, 2016 - 11:28:01 AM

File

CAD_PCK.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01225202, version 1

Collections

Citation

Bruno Lévy. Robustness and Efficiency of Geometric Programs The Predicate Construction Kit (PCK). Computer-Aided Design, Elsevier, 2015. ⟨hal-01225202⟩

Share

Metrics

Record views

936

Files downloads

549