Collision Detection for Objects Modelled by CSG

Physically based computer animation has to deal with the problem of detecting collisions of moving objects and preventing solid objects from interpenetration. In this project a method for detecting collisions among complex objects modelled with the constructive solid geometry paradigm has been developed.

The detection of collisions between two CSG objects is decomposed into three stages. Since the collision detection method for CSG objects works on two objects all possible combinations of two objects in the animation environment have to be created in a preprocessing step.

In the first stage bounding volumes in each node of the CSG tree are used to determine as soon as possible whether a collision is likely to occur. S-bounds with bounding spheres and axis-aligned bounding boxes have proven to be well suited for this problem. If the bounding volumes of the entire objects do not interfere, the objects which are enclosed by these volumes obviously do not collide. Otherwise the collision region is located by applying the S-bounds technique to the combined bounding volumes of the two objects. If the collision region is empty we can stop collision detection for these objects. Otherwise we have to test those primitives in the collision region whether they collide.

We can exactly detect collisions only among two primitives. Therefore we decompose the two CSG objects into pairs of primitive shapes Ð one of each object. Since CSG objects may have complex shape due to the recursive application of union, intersection and difference operations, we split this problem into smaller subproblems. Both CSG objects are spatially subdivided to create an octree-like data structure for the CSG tree. This extended CSG octree is made up of five types of leaf nodes: full (completely embodies in the object), empty (not contained in the object), p-surface (contains positive part of the surface of one primitive), n-surface (contains negative part of the surface of one primitive), and mixed (lowest level of resolution). These extended CSG octrees are intersected to detect those cells that are covered by primitives in both objects. If no such cells can be found, collision detection for the two objects stops. Otherwise those pairs of primitives that may collide are determined.

In the third stage we have to detect collisions among all such pairs of primitive shapes. If they collide, we calculate the collision point as well as the time and type of contact which are necessary for a following collision response step. The primitive shapes which have been used in this project are natural quadrics and Platonic solids, i.e. regular convex polyhedra.

Therefore we have to distinguish between three types of intersections: polyhedron-polyhedron, quadric-quadric, and quadric-polyhedron. Polyhedron-polyhedron as well as quadric-polyhedron intersections are detected using a 3D analogy to Cyrus-Beck Clipping. Quadric-quadric intersections are performed with geometric reasoning based on the shape of the natural quadrics in 3D space, which is determined by their geometric representation, and for some pairs by an algebraic intersection using the algebraic representations of quadrics.

Here are some example images of an animation rendered with ray-tracing.