#
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.

## Abstract

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