Robustness and efficiency of geometric programs: The Predicate Construction Kit (PCK). (March 2016)

• Record Type: Journal Article
• Authors: Lévy, Bruno
• Is Part Of: Computer aided design. Volume 72(2016)
• Page Start: 3
• Page End: 12
• Publication Date: 2016-03
• Subjects: Geometric predicates -- Arbitrary precision -- Symbolic perturbation -- Expansion arithmetics; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2015.10.004
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: In this article, I focus on the robustness of geometric programs (e.g., Delaunay 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 provably 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. Highlights: A system to automatically generate C++ code for robust predicates from their formulas. The predicates involved in the intersection between a Voronoi diagram and a tetrahedral solid. A companion open-source implementation (Predicate Construction Kit) in the GEOGRAM library. Experimental validation with several synthetic and real industrial datasets.