“Interval methods for multi-point collisions between time-dependent curved surfaces” by Snyder, Woodbury, Fleischer, Currin and Barr

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.

1. Alefeld, G., and J. Herzberger, Introduction to Interval Computations, Academic Press, New York, 1983.
2. Baraff, David, “Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies,” Computer Graphics, 23(3), pp. 223-232, July 1989.
3. Baraff, David, “Curved Surfaces and Coherence for Nonpenetrating Rigid Body Simulation,” Computer Graphics, 24(4), pp. 19-28, August 1990.
4. Baraff, David, “Coping with Friction for Non-penetrating Rigid Body Simulation,” Computer Graphics, 25(4), pp. 31-39, July 1991.
5. Baraff, David, and A. Witkin, “Dynamic Simulation of Non-penetrating Flexible Bodies,” Computer Graphics, 26(2), pp. 303-308, July 1992.
6. Duff, Tom, “Interval Arithmetic and Recursive Subdivision for Implicit Functions and Constructive Solid Geometry,” Computer Graphics, 26(2), July 1992, pp. 131-138.
7. Metaxas, Dimitri, and D. Terzopoulos, “Dynamic Deformation of Solid Primitives with Constraints,” Computer Graphics, 26(2), pp. 309-312, July 1992.
8. Mitchell, Don, and E Hanrahan, “Illumination from Curved Reflectors,” Computer Graphics, 26(2), July 1992, pp. 283- 291.
9. Moore, R.E., Interval Analysis, Prentice Hall, Englewood Cliffs, New Jersey, 1966.
10. Moore, R.E., Methods and Applications of Interval Analysis, SIAM, Philadelphia.
11. Moore, R.E., “New Results on Nonlinear Systems,” in Interval Mathematics 1980, Karl Nickel, ed., Academic Press, New York, 1980, pp. 165-180.
12. Moore, M. and Wilhelms, J., “Collision Detection and Response for Computer Animation,” Computer Graphics, 22(4), pp. 289-298, August 1988.
13. Press, W. H., B. E Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes, Cambridge University Press, Cambridge, England, 1986.
14. Ratschek, H. and J. Rokne, New Computer Methods for Global Optimization, Ellis Horwood Limited, Chichester, England, 1988.
15. Sclaroff, Stan, and A. Pentland, “Generalized Implicit Functions for Computer Graphics,” Computer Graphics, 25(4), pp. 247-250, July 1991.
16. Six, H.W., and D. Wood, “Counting and Reporting Intersections of d-Ranges,” IEEE Transactions on Computers, C-31 (3), March 1982, pp. 181-187.
17. Snyder, John, and J. Kajiya, “Generative Modeling: A Symbolic System for Geometric Modeling,” Computer Graphics, 26(2), pp. 369-378, July 1992.
18. Snyder, John, Generative Modeling for Computer Graphics and CAD: Symbolic Shape Design Using Interval Analysis, Academic Press, Cambridge, MA, July 1992.
19. Snyder, John, “Interval Analysis for Computer Graphics,” Computer Graphics, 26(2), pp. 121-130,July 1992.
20. Toth, Daniel L., “On Ray Tracing Parametric Surfaces,” Computer Graphics, 19(3), July 1985, pp. 171-179.
21. Von Herzen, B., A.H. Barr, and H.R. Zatz, “Geometric Collisions for Time-Dependent Parametric Surfaces,” Computer Graphics, 24(4), August 1990, pp. 39-48.