Rigid Body Simulation
(CSE 557 Final Project)

Jia-chi Wu

Video

Introduction

Our goal is to build a real-time rigid body simulation with multiple moving objects and visually (and perhaps physically) accurate collision detection and response.

We use the V-Clip algorithm [7] as the low-level collision detection algorithm. We planned to use (but did not implement) Baraff's algorithm [2] to compute contact forces with friction in order to remove the vibration of static objects. Microcollisions applied to objects at rest in order to keep them from penetrating the surface below them cause the vibration.

Collision detection between moving objects can take up to O(n2) time. We use the one-dimensional sweep and prune algorithm with three lists, one for each dimension, as described in [4], to reduce the time complexity.

We also try to accelerate the collision detection between moving objects and a large set of static objects by automatically creating object hierarchies of the static objects using Goldsmith and Salmon's algorithm [5] which is primary for use of ray tracing.

Finally, we added the visually pleasant hardware-accelerated real-time shadow [3, 9].

Implementation

The V-Clip module is a conversion from the set of C functions in my GLRally project. Collision detection is much more complex than the two object case in GLRally, since we have to compute the transformation for all the objects after each collision. Another complexity comes from the fact that the nearest two objects at a certain time are not necessarily the two that collide with each other at the next time step.

The V-Clip algorithm only handles convex polygonal objects. We describe concave objects with multiple polyhedra so that we can still use the V-Clip algorithm for collision detection. Polyhedra and the object geometry for rendering are separate so objects can have much more complex structure while the polyhedra are kept simple to improve collision detection efficiency.

We soon found that the raw output from the V-Clip algorithm is not suitable for computing contact forces using Baraff's algorithm (or perhaps the other way around), since only one set of nearest points between two objects is reported by the V-Clip algorithm, but we need several sets of contacting points in order to solve the contacting forces between them. Extension to the V-Clip algorithm (not implemented in this project) is required to find all the contacting points. One method is to keep track of the pairs of nearest points between each iteration (each call to the V-Clip module), as described in [8].

For efficiency and simplicity, integration of the relative velocity and impulse is done in only one step. This sometimes generates noticeable inaccurate friction between colliding objects.

The benefits of using Goldsmith and Salmon's algorithm are not obvious for the number of static objects we tried. More exhausted tests and measurements with larger set of static objects are required.

The real-time shadow was pretty straightforward to implement. The only drawback for this stenciled shadow rendering method is that the viewer must be outside of the shadow in order to see the correct results. Please note that some 3D graphics cards do not support OpenGL hardware stencil buffers, and the simulation will run much slower on those machines.

Issues

Since the polyhedra have to be convex and our V-Clip module only handles triangles, we have to distort some of our objects to get perfect convex polyhedra. For example, a cube (two triangles on each face) will cause problems in the V-Clip module. In addition, there is no automatic convexity checking to make sure that the input polyhedra are legal.

The simplified impulse integrator produces incorrect impulse under some circumstances and causes objects to move in unpredictable ways.

No collision heap is implemented. The search for time of impact is expensive since all objects are involved.

Screenshots


References

  1. D. Baraff. Coping with Friction for Non-penetrating Rigid Body Simulation. In Computer Graphics (Proc. SIGGRAPH), volume 25, pages 31-40. ACM, July 1991.
  2. D. Baraff. Fast Contact Force Computation for Nonpenetrating Rigid Bodies. In Computer Graphics (Proc. SIGGRAPH), Annual Conference Series, pages 23-34. ACM, July 1994.
  3. J. Bestimt and B. Freitag. Real-Time Shadow Casting Using Shadow Volumes. Gamasutra.
  4. J. Cohen, M. Lin, D. Manocha, and M. Ponamgi. I-COLLIDE: An Interactive and Exact Collision Detection System for Large-scale Environments. 1995 Symposium on Interactive 3D Graphics, pages 189-196, April 1995.
  5. J. Goldsmith and J. Salmon. Automatic Creation of Object Hierarchies for Ray Tracing. IEEE CG&A, volume 7, no. 5, pages 14-20. IEEE, May 1987.
  6. D. Greenwood. Principles of Dynamics Second Edition. Prentice Hall, 1988.
  7. B. Mirtich. V-Clip Collision Detection Library. MERL.
  8. B. Mirtich. Rigid Body Contact: Collision Detection to Force Computation. MERL Technical Report 98-01, Proc. of Workshop on Contact Analysis and Simulation. IEEE International Conference on Robotics and Automation, May 1998.
  9. NVIDIA OpenGL-based stenciled shadow example.