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

摘要

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.