Reliable collision detection for time-dependent parametric surfaces (Q1276125)

In order to detect collisions and near misses of parametrically defined objects that move and change shape over time, B. von Herzen, A. H. Barr and H. R. Zatz proposed an algorithm that is based on bisection and on the construction of a box \[ (x(u_c, v_c, t_c), y(u_c, v_c, t_c), z(u_c, v_c, t_c))^T+ [- 1,1](dx, dy, dz)^T \] which encloses an object. This object is given by \[ (x(u, v,t), y(u,v,t), z(u,v,t))^T, \] where the real parameters \(u\), \(v\) and the time \(t\) vary over some box \((u_c, v_c, t_c)^T+ [-1,1](du, dv,dt)^T\). In order to simplify the process of constructing the bounding box, the authors use an interval arithmetic approach which requires less work for the programmer and which may lead to a tighter box. Moreover, it appears to be considerably faster. They present the routines which the user must supply to the von Herzen-Barr-Zatz-algorithm and they demonstrate the efficiency of their interval algorithm by an example.