Interval Methods for Multi-Point Collisions between Time-Dependent Curved Surfaces

John M. Snyder, Adam R. Woodbury, Kurt Fleischer, Bena Currin, Alan H. Barr
California Institute of Technology

From Proceedings of SIGGRAPH 1993, Computer Graphics Proceedings, Annual Conference Series, Association for Computing Machinery Special Interest Group on Computer Graphics (ACM SIGGRAPH), 1993, p. 321-334.


We present an efficient and robust algorithm for finding points of collision between time-dependent parametric and implicit surfaces. The algorithm detects simultaneous collisions at multiple points of contact. When the regions of contact form curves or surfaces, it returns a finite set of points uniformly distributed over each contact region.

Collisions can be computed for a very general class of surfaces: those for which inclusion functions can be constructed. Included in this set are the familiar kinds of surfaces and time behaviors encountered in computer graphics.

We use a new interval approach for constrained minimization to detect collisions, and a tangency condition to reduce the dimensionality of the search space. These approaches make interval methods practical for multi-point collisions between complex surfaces. An interval Newton method based on the solution of the interval linear equation is used to speed convergence to the collision time and location. This method is more efficient than the Krawczyk--Moore iteration used previously in computer graphics.

CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling; G.4 [Mathematical Software]: Reliability and Robustness

General Terms: collision detection, parametric surface, constrained minimization, interval analysis

Additional Key Words: inclusion function, interval Newton method, interval linear equation