Collision detection has been a fundamental problem in computer animation, physically-based modeling, geometric modeling, and robotics. In these applications, interactions between moving objects are modeled by dynamic constraints and contact analysis. The motions of the objects are constrained by various interactions, including collisions.
A virtual environment, like a walkthrough, creates a computer-generated world, filled with virtual objects. Such an environment should give the user a feeling of presence, which includes making the images of both the user and the surrounding objects feel solid. For example, the objects should not pass through each other, and things should move as expected when pushed, pulled or grasped. Such actions require accurate collision detection, if they are to achieve any degree of realism. However, there may be hundreds, even thousands of objects in the virtual world, so a naive algorithm could take a long time just to check for possible collisions as the user moves. This is not acceptable for virtual environments, where the issues of interactivity impose fundamental constraints on the system. A fast and interactive collision detection algorithm is a fundamental component of a complex virtual environment.
Physically-based modeling simulations depend highly on the physical interaction between objects in a scene. Complex physics engines require fast, accurate, and robust proximity queries to maintain a realistic simulation at interactive rates. We couple our proximity query research with physically-based modeling to ensure that our packages provide the capabilities of today’s physics engines.