Reliable Collision Detection for Time-Dependent Parametric Surfaces

We improve on an algorithm by Von Herzen, Barr, and Zatz (HBZ) to detect geometric collisions between pairs of time-dependent parametric surfaces. The HBZ algorithm uses upper bounds on the parametric derivatives to guarantee detection of collisions and near misses, thus avoiding the defects of algorithms which sample the surfaces, possibly missing sharp spikes. Unfortunately, the user of the HBZ algorithm must supply not only routines computing the surface functions, but also routines bounding every component in the Jacobian of these surface functions over an arbitrary parametric range. Although they give helpful analyses for several types of surfaces, HBZ admit the need to provide Jacobian bounding routines as a disadvantage.We propose using interval arithmetic to bound functional values over a parametric input range, thus eliminating the need for the Jacobian entirely. Our interval version of the collision detection algorithm assumes neither bounded differentiability nor satisfaction of the Lipschitz criterion. Therefore, our code can detect geometric collisions for the much larger class of surface functions for which bounds on the function values can be computed using interval arithmetic. We contrast our code to that of HBZ and give timing comparisons.