Ongoing Research Seminar
Friday September 29, 1995

---

Joseph S.B. Mitchell
Applications of Computational Geometry:
Virtual Reality, 3D Graphics, and Route Planning

We describe ongoing work in applied computational geometry in three problem domains:

1. Virtual Reality --- Motivated by this need to do collision detection in virtual reality, we address the following problem: Given a description of a geometric environment, E, in three dimensions, preprocess it into a data structure of small size so that queries of the form, ``Does object A intersect any of the obstacles in E?'' can be answered very rapidly. Further, we study the problem of tracking the motion of A within E, in order to detect dynamically, in real time, when A collides with an obstacle. The environment E is given to us as a boundary representation of a set of polyhedral obstacles, each of which is a component part that has been designed and modeled within a CAD system.
2. 3D Graphics --- We have been studying theoretical and practical aspects of the model simplification/approximation problem for some time. We will briefly discuss some current approaches.
3. Route Planning --- Motivated by applications in geographic information systems, we have studied route planning problems for travel through varied terrain and on surfaces. Objectives include minimum-time paths, search/explore routes, concealment, etc.

Most of the above work is joint with students. Throughout the talk, we will identify open problem domains of possible interest for future research.