Dinesh Manocha, University of North Carolina at Chapel Hill

Dinesh Manocha is currently a Phi Delta Theta/Mason Distinguished Professor of Computer Science at the University of North Caro lina at Chapel Hill. He received his Ph.D. in Computer Science at the University of California at Berkeley 1992. He received Junior Faculty Award in 1992, Alfred P. Sloan Fellowship and NSF Career Award in 1995, Office of Naval Research Young Investigator Award in 1996, Honda Research Initiation Award in 1997, and Hettleman Prize for Scholarly Achievements at UNC Chapel Hill in 1998. He has also received ten best paper & panel awards at top conferences in graphics, modeling, simulation and visualization. Many of the technologies developed by his group on collison detection, GPU-based algorithms and large model rendering have been widely used. He has published more than 250 papers in leading conferences and journals on computer graphics, geometric modeling, robotics, virtual environments and computational geometry. He has also served as a program committee member for more than 50 leading conferences in these areas and also served in the editorial board of many journals.

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.