A collision detection framework for deformable NURBS surfaces

偵測可變型的 NURBS 曲面踫撞的架構

Student thesis: Master's Thesis

View graph of relations


  • Kwok On CHAN

Related Research Unit(s)


Awarding Institution
Award date15 Feb 2006


Collision detection is an important process in almost all forms of computer animation and physical simulation. Interactive environments with dynamically deforming objects play an important role in surgery simulation and entertainment industry. However, deforming objects are computationally expensive to handle, but these applications require efficient rendering and interactive collision detection of deformable objects. Collision detection of rigid bodies has been well studied. However, collision detection of deformable objects introduces additional difficulties. There are two types of object collisions: inter-collision and self-collision. Intercollisions refer to the collisions that occur between two separate objects and selfcollisions refer to the collisions that occur within an object itself. Self-collisions only occur in deformable objects. In this thesis, we study existing work on collision detection of deformable objects and summarize the difficulties to do so. We then present a collision detection framework for deformation NURBS surfaces. The framework addresses difficulties involved in both inter-collision detection and self-collision detection. We first demonstrate how to improve the performance of inter-collision detection by introducing a new bounding volume intersection test, which is 25% faster than existing methods available in the literature. The intersection test makes use of the information from the overlay Gauss map of the two bounding volumes undergoing intersection test. This method successfully reduces the overhead introduced by a popular method discussed in the literature. We then present our self-collision detection method for deformable NURBS surfaces. We first classify all possible self-collision configurations into different types. We then employ Volino’s method [VM94, VM95] to determine the possibly self-colliding surfaces. We further improve the performance by introducing a constant time adjacency checking method. We demonstrate the performance of the inter-collision and the self-collision detection methods that we propose in this thesis with some popular methods.

    Research areas

  • Computer animation, Three-dimensional display systems