Ongoing Research Seminar
Friday September 29, 1995

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

Department of Applied Mathematics and Statistics
State University of New York, Stony Brook, NY 11794-3600

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. (Dimitris Margaritis, Thu Sep 21 13:13:55 EDT 1995)