Discrete Geometry Processing with Topological Guarantees

Tuesday, May 29, 2007 - 10:40am - 11:30am
EE/CS 3-180
Dinesh Manocha (University of North Carolina, Chapel Hill)
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
hand, current approximate techniques may not provide any
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,
surface polygonization and Minkowski sum evaluation.
We compute an approximate boundary of the final solid defined
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
applications: Boolean operations on complex polyhedral models
low degree algebraic primitives, model simplification and
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 present an
algorithm for complete motion planning, i.e., find a path if
exists and report a failure otherwise. Our algorithm performs
deterministic sampling to compute a roadmap that captures the
connectivity of the free space and combines with randomized
sampling and cell decomposition to further improve the performance. We
demonstrate the performance of our algorithm on a number of
challenging environments with narrow passages and no collision-free paths.