Collision detection is a fundamental process in virtual reality, objects interactions in physical simulation and constructive solid geometry (CSG). As these interactions require realistic and accurate interference test, the collision detection process should be efficient, robust and able to accommodate a large number of objects. Moreover, the capability of finding the points of collision or the contact regions is important for computing the response between interactive objects. Most of the collision detection algorithms are based on geometrical properties of the objects to perform interference tests. Some algorithms adopt an image-space approach to tackle the problem. In this thesis, we present a collision detection process which exploits both the geometrical property and the image prop...[ Read more ]

Collision detection is a fundamental process in virtual reality, objects interactions in physical simulation and constructive solid geometry (CSG). As these interactions require realistic and accurate interference test, the collision detection process should be efficient, robust and able to accommodate a large number of objects. Moreover, the capability of finding the points of collision or the contact regions is important for computing the response between interactive objects. Most of the collision detection algorithms are based on geometrical properties of the objects to perform interference tests. Some algorithms adopt an image-space approach to tackle the problem. In this thesis, we present a collision detection process which exploits both the geometrical property and the image property of the objects. Most of the non-colliding pairs can be quickly eliminated in the object space. The interference determination and computation of the colliding regions are done in the image space. In both levels, some optimization schemes are employed.

This algorithm efficiently balances the work load between the main CPU and the hardware rendering pipeline. It achieves real time performance for interactions of some complex objects. The colliding regions can be computed easily by using the contents stored in the depth buffer and the stencil buffer provided in a conventional graphics hardware. The overhead of computing contact regions is relatively small.

The algorithm is implemented in a package called RECODE, REndered COllision DEtection. We have performed some experiments to evaluate the performance of RECODE in the context of the fastest algorithms, currently available. The empirical results show that our algorithm performance is satisfactory.

Some variants of the approach are also discussed.