Robust Geometry Processing

When dealing with geometric models, turning a theoretical algorithm into a reliable computer program might become a tricky and sometimes frustrating task. Even when an algorithm is provably correct, its actual implementation might still fail because it approximates real numbers with finite floating point representations. Exact geometric predicates and adaptive precision may help, but the cost in terms of performance loss can be relevant.

This talk analyses and discusses how recent results have tackled this fundamental problem. Starting from Shewchuk's seminal work and CGAL approach to robustness, I will show how geometric algorithms can be made robust with virtually no performance penalty. We will see how the concept of "indirect geometric predicate" has enabled the development of a whole new family of modern algorithms that resolve long lasting problems within the geometry processing community, including 3D arrangements, boolean operations, cascaded editing, volume meshing and collision detection.