Deformable Free-Space Tilings for Kinetic Collision Detection†
Authors:
- 1 March 2002
- journal article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 21 (3) , 179-197
Abstract
We present kinetic data structures for detecting collisions between a set of polygons that are moving continuously. Unlike classical collision detection methods that rely on bounding volume hierarchies, our method is based on deformable tilings of the free space surrounding the polygons. The basic shape of our tiles is that of a pseudo-triangle , a shape sufficiently flexible to allow extensive deformation, yet structured enough to make detection of self-collisions easy. We show different schemes for maintaining pseudo-triangulations as a kinetic data structure, and we analyze their performance. Specifically, we first describe an algorithm for maintaining a pseudo-triangulation of a point set, and show that the pseudo-triangulation changes only quadratically many times if points move along algebraic arcs of constant degree. In addition, by refining the pseudo-triangulation, we show triangulations of points that only change about O(n7 /3 ) times for linear motion. We then describe an algorithm for maintaining a pseudo-triangulation of a set of convex polygons. Finally, we extend our algorithm to the general case of maintaining a pseudo-triangulation of a set of moving or deforming simple polygons.Keywords
This publication has 12 references indexed in Scilit:
- Maintaining the Extent of a Moving Point SetDiscrete & Computational Geometry, 2001
- Cylindrical static and kinetic binary space partitionsComputational Geometry, 2000
- Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise InteractionsDiscrete & Computational Geometry, 1999
- Data Structures for Mobile DataJournal of Algorithms, 1999
- Fast algorithms for collision and proximity problems involving moving geometric objectsComputational Geometry, 1996
- Topologically sweeping visibility complexes via pseudotriangulationsDiscrete & Computational Geometry, 1996
- Collision detection for interactive graphics applicationsIEEE Transactions on Visualization and Computer Graphics, 1995
- On disjoint concave chains in arrangements of (pseudo) linesInformation Processing Letters, 1994
- On disjoint concave chains in arrangements of (pseudo) linesInformation Processing Letters, 1991
- Optimal shortest path queries in a simple polygonJournal of Computer and System Sciences, 1989