Collision Detection for Virtual Reality

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 whether 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.

Related publications:

M. Held, J.T. Klosowski, J.S.B. Mitchell (1995):
``Evaluation of Collision Detection Methods for Virtual Reality Fly-Throughs''.
Proc. 7th Canad. Conf. Computat. Geometry, C. Gold, J.-M. Robert (eds.), pp. 205-210; Québec City, Québec, Canada, Aug 10-13, 1995.

M. Held, J.T. Klosowski, J.S.B. Mitchell (1995):
``Real-Time Collision Detection for Motion Simulation within Complex Environments''.
SIGGRAPH'96 Visual Proc., p. 151; New Orleans, LA, USA, Aug 1996.

J.T. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, K. Zikan (1998):
``Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs''.
IEEE Trans. Visualizat. Comput. Graph. 4(1):21-36, Jan 1998.

The following images show some of the datasets on which we ran QuickCD. (Click on an image icon in order to see the full-size image. The full-size images have (more than) 1000x700 pixels.) Typically, the (static) environment is shown in yellow and the flying object is shown in either green or blue. When the flying object makes contact with the environmental obstacles, the contact region is highlighted in red.

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.

[Image of Torus Colliding with Stalagmites]

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.)

[Image of Hand Within Interior of Plane]

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.

[Image of 747 Flying Within Interior of Plane]

The 747 is flying within the same interior section.

file last modified: Thursday, 27-Feb-2020 07:29:07 CET