Deformable Free-Space Tilings for Kinetic Collision Detection†

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(n ⁷ ^/ ³ ) 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

collision detection kinetic data structure pseudo triangulation

Get full access to this article

View all access options for this article.

References

Agarwal, P.K. , Eppstein, D. , Guibas , and Henzinger, M.H. 1998. Parametric and kinetic minimum spanning trees. In Proc. 39th Annual IEEE Symposium Found. Computer Science, pp. 596-605.

Agarwal, P.K. , Erickson, J. , and Guibas, L.J. 1998. Kinetic BSPs for intersecting segments and disjoint triangles . In Proc. 9th ACM-SIAM Symposium Discrete Algorithms , pp. 107-116.

Agarwal, P.K. , Guibas, L.J. , Hershberger, J. , and Veach, E. 2001 Maintaining the extent of a moving point set. Discrete and Comput. Geom. 26:353-374.

Agarwal, P.K. , Guibas, L.J. , Murali, T.M. , and Vitter, J.S. 2000. Cylindrical static and kinetic binary space partitions . Comput. Geom.: Theory Appls., pp. 103-127.

Basch, J. 1999. Kinetic data structures. Ph.D. thesis, Dept. Computer Science, Stanford University.

Basch, J. , Erickson, J. , Guibas, L.J. , Hershberger, J. , and Zhang, L. 1999. Kinetic collision detection for two simple polygons. In Proc. 9th ACM-SIAM Symposium Discrete Algorithms, pp. 102-111.

Basch, J. , Guibas, L.J. , and Hershberger, J. 1999. Data structures for mobile data. J. Algorithms 31:1-28.

Basch, J. , Guibas, L.J. , and Zhang, L. 1997. Proximity problems on moving points. In Proc. 13th Annual ACM Symposium Computer Geom, pp. 344-351.

Cameron, S. 1990. Collision detection by four-dimensional intersection testing . In Proc. IEEE International Conf. Robot. Autom., pp. 291-302.

10.

Eppstein, D. , and Erickson, J. 1999. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. Discrete and Computer Geom. 22:569-592.

11.

Erickson, J. , Guibas, L.J. , Stolfi, J. , and Zhang, L. 1999. Separation-sensitive kinetic collision detection for convex objects. In Proc. 9th ACM-SIAM Symposium Discrete Algorithms.

12.

Guibas, L. , Xie, F. , and Zhang, L. 2001. Kinetic collision detection: Algorithms and experiments . In Proc. International Conference on Robotics and Automation.

13.

Guibas, L.J. 1998. Kinetic data structures: A state of the art report. In Proc. 3rd Workshop on Algorithmic Foundations of Robotics , eds. P. K. Agarwal, L. E. Kavraki, and M. Mason, 191-209. Wellesley, MA: A. K. Peters.

14.

Guibas, L.J. , and Hershberger, J. 1989. Optimal shortest path queries in a simple polygon. J. Computer Syst. Sci. 39(2):126-152.

15.

Guibas, L.J. , and Karavelas, M. 1999. Interval methods for kinetic simulations. In Proc. 5th ACM Symposium on Computational Geometry, pp. 255-264.

16.

Gupta, P. , Janardan, R. , and Smid, M. 1996. Fast algorithms for collision and proximity problems involving moving geometric objects. Computer Geom. Theory Appl. 6:371- 391.

17.

Halperin, D. , and Sharir, M. 1991. On disjoint concave chains in arrangements of (pseudo) lines. Inform. Process. Lett. 40:189-192.

18.

Halperin, D. , and Sharir, M. 1994. Corrigendum: On disjoint concave chains in arrangements of (pseudo) lines. Inform. Process. Lett. 51:53-56.

19.

Hubbard, P.M. 1995. Collision detection for interactive graphics applications . IEEE Trans. Visualization and Computer Graphics 1:218-230.

20.

Kettner, L. , Mantler, A. , Snoeyink, J. , Speckmann, B. , and Takeuchi, F. 2001. Bounded-degree pseudotriangulations of points. In Proc. 17th European Workshop on Computational Geometry .

21.

Kirkpatrick, D. , Snoeyink, J. , and Speckmann, B. 2000. Kinetic collision detection for simple polygons. In Proc. 6th ACM Symposium on Computational Geometry, pp. 322- 330.

22.

Kirkpatrick, D. , and Speckmann, B. 2000. Separation sensitive kinetic collision detection for simple polygons. In Proc. Japan Conference on Discrete and Computational Geometry.

23.

Kirkpatrick, D. , and Speckmann, B. 2002. Kinetic maintenance of context-sensitive hierarchical representations of disjoint simple polygon. In Proc. 13th Annual ACM Symposium Comput. Geom

24.

Pocchiola, M. , and Vegter, G. 1996. Topologically sweeping visibility complexes via pseudo-triangulations . Discrete Comput. Geom. 16:419-453.

25.

Ponamgi, M.K. , Manocha, D. , and Lin, M.C. 1995. Incremental algorithms for collision detection between general solid models. In Proc. ACM Siggraph Symposium Solid Modeling, pp. 293-304.

26.

Preparata, F.P. , and Shamos, M.I. 1990. Computational Geometry: An Introduction. Springer-Verlag, 3rd edition.

27.

Schömer, E. , and Thiel, C. 1995. Efficient collision detection for moving polyhedra. In Proc. 11th Annual ACM Symposium Comput. Geom, pp. 51-60.

28.

Sharir, M. , and Agarwal, P.K. 1995. Davenport-Schinzel Sequences and Their Geometric Applications . New York: Cambridge University Press.

29.

Streinu, I. 2000. A combinatorial approach to planar non-colliding robot arm motion planning. In Proc. 41st ACM Annual Symposium on Foundations of Computer Science, pp. 443-453.

30.

Suri, S. 1987. Minimum link paths in polygons and related problems. Ph.D. thesis, Dept. Computer Science, Johns Hopkins University , Baltimore, MD.