CAREER: Algebraic & Geometric Techniques for Interface Detection in Static and Dynamic Environments

Principal Investigator: Dinesh Manocha
Funding Agency: National Science Foundation
Agency Number: CCR-9625217

Abstract
The problems of interference detection are fundamental in computational geometry, solid modeling, robotics, manufacturing, computer graphics and computer-simulated environments. These include collision detection between geometric models undergoing motion, surface intersection between linear and curved surfaces, collision avoidance for robot motion planning, visibility computations, hidden surface removal and boundary computations. The proposed research takes a three-fold approach to these problems using algebraic, numeric and geometric techniques:

• Develop fast and robust algorithms for interference detection between geometric models in static and dynamic environments. The set of models include polyhedra, splines, algebraic surfaces and deformable objects.
• Specialize these algorithms to interactive collision detection, hidden surface removal, surface intersection and boundary computation with special emphasis onrobustness.
• Develop efficient software libraries for interference detection between moving polyhedral objects, solid models defined using algebraic surfaces and boundary evaluation. The resulting libraries will be distributed as public domain code and demonstrated on different applications.

The research efforts will be complemented with the following educational goals:

• Development of undergraduate and graduate courses on geometric, symbolic and scientific computing.
• Develop novel teaching methods and electronic course notes using the World-Wide Web (WWW) technology.
• Use of graphics, geometry and animation tools to develop an algorithm animation and programming laboratory for undergraduate courses.