Broad-phase collision detection using semi-adjusting BSP-trees

ABSTRACT

The broad-phase step of collision detection in scenes composed of n moving objects is a challenging problem because enumerating collision pairs has an inherent O(n²) complexity. Spatial data structures are designed to accelerate this process, but often their static nature makes it difficult to handle dynamic scenes. In this work we propose a new structure called Semi-Adjusting BSP-tree for representing scenes composed of thousands of moving objects. An scheduling algorithm evaluates locations where the BSP-tree becomes unbalanced, uses several strategies to alter cutting planes, and defer updates based on their re-structuring cost. We show that the tree does not require a complete re-structuring even in highly dynamic scenes, but adjusts itself while maintaining desirable balancing and height properties.

REFERENCES

• 1: Pankaj K. Agarwal , Jeff Erickson , Leonidas J. Guibas, Kinetic binary space partitions for intersecting segments and disjoint triangles, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.107-116, January 25-27, 1998, San Francisco, California, United States
• 2: Sigal Ar , Bernard Chazelle , Ayellet Tal, Self-customized BSP trees for collision detection, Computational Geometry: Theory and Applications, v.15 n.1-3, p.91-102, Feb.1.2000 [doi>10.1016/S0925-7721(99)00049-8]
• 3: Ar, S., Montag, G., and Tal, A. 2002. Deferred, self-organizing bsp trees. Computer Graphics Forum 21, 3.
• 4: Gino Van Den Bergen , Gino Johannes Bergen, Collision Detection, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 5: Cassen, T., Subramanian, K., and Michalewicz, Z. 1995. Near-optimal construction of partitioning trees by evolutionary techniques. In Proceedings of Graphics Interface '95, 263--270.
• 6: Chrysanthou, Y., and Slater, M. 1992. Computing dynamic changes to BSP trees. Computer Graphics Forum 11, 3 (September), C321--C332.
• 7: Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
• 8: Joao Luiz Dihl Comba , Leonidas J. Guibas, Kinetic vertical decomposition trees, 1999
• 9: Dave Eberle, S. H., 2004. Siggraph 2004 course 14 -- collision detection for deformable objects.
• 10: Eberly, D. 2001. 3D Game Engine Design. Morgan Kauffman.
• 11: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 12: Naga K. Govindaraju , Stephane Redon , Ming C. Lin , Dinesh Manocha, CULLIDE: interactive collision detection between complex models in large environments using graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 13: Hasan, K. M., Parker, D. L., and Alexander, A. L. 2001. Comparison of gradient encoding schemes for diffusion tensor imaging. Journal Of Magnetic Ressonance and Imaging 13, 5, 769--780.
• 14: Heidelberger, T. K., 2004. Eurographics 2004 star -- state of the art report collision detection for deformable objects.
• 15: Philip M. Hubbard, Collision Detection for Interactive Graphics Applications, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.218-230, September 1995 [doi>10.1109/2945.466717]
• 16: Thomas C. Hudson , Ming C. Lin , Jonathan Cohen , Stefan Gottschalk , Dinesh Manocha, V-COLLIDE: accelerated collision detection for VRML, Proceedings of the second symposium on Virtual reality modeling language, p.117-ff., February 24-26, 1997, Monterey, California, United States [doi>10.1145/253437.253472]
• 17: Doug L. James , Dinesh K. Pai, BD-tree: output-sensitive collision detection for reduced deformable models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 18: Mirtich, B., 1997. Efficient algorithms for two-phase collision detection.
• 19: Bruce F. Naylor, Interactive solid geometry via partitioning trees, Proceedings of the conference on Graphics interface '92, p.11-18, September 1992, Vancouver, British Columbia, Canada
• 20: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 21: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 22: Daniel Dominic Sleator , Robert Endre Tarjan, Self adjusting heaps, SIAM Journal on Computing, v.15 n.1, p.52-69, Feb. 1986 [doi>10.1137/0215004]
• 23: Smith, R. 2004. Open dynamics engine v 0.5 user guide. http://ode.org/ode-latest-userguide.pdf.
• 24: John Snyder , Jed Lengyel, Visibility sorting and compositing without splitting for image layer decompositions, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.219-230, July 1998 [doi>10.1145/280814.280878]
• 25: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 26: Teschner, M., Heidelberger, B., Mueller, M., Pomeranets, D., and Gross, M., 2003. Optimized spatial hashing for collision detection of deformable objects.
• 27: Thatcher, U. 2000. Loose octrees. In Game Programming Gems, Charles River Media, 444--453.
• 28: Torres, E. 1990. Optimization of the binary space partition algorithm (BSP) for the visualization of dynamic scenes. In Eurographics '90, North-Holland, C. E. Vandoni and D. A. Duce, Eds., 507--518.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Keywords:
BSP-trees, collision detection, dynamic scenes