Title: Discrete Geometry Processing with Topological Guarantees

Abstract:
Our goal is to compute reliable solutions for many non-linear geometric problems that arise in geometric modeling, computer graphics and robotics. Prior methods for solving these problems can be classified into exact and approximate approaches. The exact algorithms are able to guarantee correct output, but are usually difficult to implement reliably and efficiently. On the other hand, current approximate techniques may not provide any topological guarantees on the solution. We bridge the gap between these two approaches, by developing a unified sampling based approach to solve these problems with topological guarantees. Specifcally, we present results for surface extraction and motion planning problems. Surface extraction problems include Boolean operations, implicit surface polygonization, swept volume computation and Minkowski sum evaluation. We compute an approximate boundary of the final solid defined by these operations. Our algorithm computes an approximation that is guaranteed to be topologically equivalent to the exact surface and bounds the approximation error using two-sided Hausdorff error. We demonstrate the performance of our approach for the following applications: Boolean operations on complex polyhedral models and low degree algebraic primitives, model simplification and remeshing of polygonal models, and Minkowski sums and offsets of complex polyhedral models. The second class of problems is motion planning of rigid or articulated robots translating or rotating among stationary obstacles. We briefly describe how our sampling framework can be used for complete motion planning of low degree of freedom robots.