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