Separation-Sensitive Collision Detection for Convex Objects.pdf

a r X i v : c s / 9 8 0 9 0 3 5 v 2 [ c s .C G ] 2 4 O c t 1 9 9 8 Separation-Sensitive Collision Detection for Convex Objects Jeff Erickson? Leonidas J. Guibas? Jorge Stolfi? Li Zhang§ Abstract We develop a class of new kinetic data structures for colli- sion detection between moving convex polytopes; the per- formance of these structures is sensitive to the separation of the polytopes during their motion. For two convex poly- gons in the plane, let D be the maximum diameter of the polygons, and let s be the minimum distance between them during their motion. Our separation certificate changes O(log(D/s)) times when the relative motion of the two poly- gons is a translation along a straight line or convex curve, O( √ D/s) for translation along an algebraic trajectory, and O(D/s) for algebraic rigid motion (translation and rotation). Each certificate update is performed in O(log(D/s)) time. Variants of these data structures are also shown that exhibit hysteresis—after a separation certificate fails, the new cer- tificate cannot fail again until the objects have moved by some constant fraction of their current separation. We can then bound the number of events by the combinatorial size of a certain cover of the motion path by balls. 1 Introduction Collision detection is an algorithmic problem arising in all areas of computer science dealing with the simula- tion of physical objects in motion. Examples include motion planning in robotics, virtual reality animations, computer-aided design and manufacturing, and com- puter games. Often the problem is broken up into two parts, the so-called broad phase, in which we identify the pairs of objects we need to consider for possible collision, and the narrow phase in which we track the occurrence of collisions between a specific pair of objects [14]. (In ?Center for Geometric Computing, Department of Computer Science, Duke University, Durham, NC 27708-0129, and De- partment Computer Science, University of Illinois, Urba