Virtual Reality (VR) refers to the use of computers to simulate a physical environment in such a way that humans can readily visualize, explore, and interact with the ``objects'' in the environment. Since physical environments are inherently geometric, many of the computational problems involved in designing and building a VR system are geometric in nature. One particularly important problem that must be addressed in order to make VR a reality is the problem of real-time interactive collision detection (CD): Determine if two virtual objects intersect each other.
Over the last few years, I have been working on efficient algorithms for collision detection. This has been a multi man-year effort, and is joint work with Jim Klosowski and Joe Mitchell, and has been carried out in cooperation with Boeing.
One of our CD algorithms builds a tetrahedral mesh of free space, and then tracks the motion of the moving object within this tetrahedral mesh. The motivation for using a tetrahedral mesh is that one can anticipate to reduce the number of pairwise intersection checks drastically by exploiting the information encoded in the mesh.
In other, more recent approaches we make use of discrete-orientation polytopes (k-dops) and of bounding-volume trees (BV-trees), and of similar hierarchical data structures. Both k-dops and BV-trees have been cast into efficient code and are now part of our collision detection software QuickCD. Financial support for this project was provided by Boeing.
You may also want to see our related work on NC verification.
|This environment consists of 25,000 tetrahedra (100,000 triangles) randomly placed within the scene. The flying object is a 747, which consists of nearly 15,000 triangles.|
|This environment of stalagmites consists of nearly 100,000 triangles. The torus consists of 20,000 triangles. (These datasets were graciously provided to us by the University of North Carolina at Chapel Hill.)|
|Each copy of the system of pipes contains over 140,000 triangles. (This dataset was graciously provided to us by the University of North Carolina at Chapel Hill.)|
|A virtual hand is moved within the interior section of another plane. The environment (which depicts some of the internal structure and hydraulic pipes in the plane) contains roughly 170,000 triangles.|
|A close-up of the virtual hand within the same interior section.|
|The 747 is flying within the same interior section.|
file last modified: Tuesday, 06-Aug-2013 11:58:50 CEST
Copyright © 2015 Martin Held. All rights reserved.