Analyzing bounding boxes for object intersection

ABSTRACT

Heuristics that exploit bouning boxes are common in algorithms for rendering, modeling, and animation. While experience has shown that bounding boxes improve the performance of these algorithms in practice, the previous theoretical analysis has concluded that bounding boxes perform poorly in the worst case. This paper reconciles this discrepancy by analyzing intersections among n geometric objects in terms of two parameters: &agr; an upper bound on the aspect ratio or elongatedness of each object; and &sgr; an upper bound on the scale factor or size disparity between the largest and smallest objects. Letting Ko and Kb be the number of intersecting object pairs and bounding box pairs, respectively, we analyze a ratio measure of the bounding boxes' efficiency, r=Kb/n+Ko . The analysis proves that r=Oas log

2

s and r=Was . One important consequence is that if &agr; and &sgr; are small constants (as is often the case in practice), then Kb= O(Ko)+ O(n, so an algorithm that uses bounding boxes has time complexity proportional to the number of actual object intersections. This theoretical result validates the efficiency that bounding boxes have demonstrated in practice. Another consequence of our analysis is a proof of the output-sensitivity of an algorithm for reporting all intersecting pairs in a set of n convex polyhedra with constant &agr; and &sgr;. The algorithm takes time O(nlogd−1n+ Kolog d−1n) for dimension d = 2, 3. This running time improves on the performance of previous algorithms, which make no assumptions about &agr; and &sgr;.

REFERENCES

• 1: Bernard Chazelle, An optimal algorithm for intersecting three-dimensional convex polyhedra, SIAM Journal on Computing, v.21 n.4, p.671-696, Aug. 1992 [doi>10.1137/0221041]
• 2: 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]
• 3: Mark de Berg, Linear Size Binary Space Partitions for Fat Objects, Proceedings of the Third Annual European Symposium on Algorithms, p.252-263, September 25-27, 1995
• 4: Mark de Berg , Matthew Katz , A. Frank van der Stappen , Jules Vleugels, Realistic input models for geometric algorithms, Proceedings of the thirteenth annual symposium on Computational geometry, p.294-303, June 04-06, 1997, Nice, France [doi>10.1145/262839.262986]
• 5: DOBKIN, D., HERSHBERGER, g., KIRKPATRICK, D., AND SURI, S. 1993. Computing the intersection-depth of polyhedra. Algorithmica 9, 518-533.
• 6: David P. Dobkin , David G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.400-413, July 1990, Warwick University, England
• 7: EDELSBRUNNER, H. 1983. A new approach to rectangle intersections, Parts I&II. Int. J. Comput. Math. 13, 209-229.
• 8: Alon Efrat , Micha Sharir, On the complexity of the union of fat objects in the plane, Proceedings of the thirteenth annual symposium on Computational geometry, p.104-112, June 04-06, 1997, Nice, France [doi>10.1145/262839.262911]
• 9: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics (2nd ed. in C): principles and practice, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 10: Alejandro Garcia-Alonso , Nicolás Serrano , Juan Flaquer, Solving the Collision Detection Problem, IEEE Computer Graphics and Applications, v.14 n.3, p.36-43, May 1994 [doi>10.1109/38.279041]
• 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: Ned Greene, Detecting intersection of a rectangular solid and a convex polyhedron, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 13: GUPTA, P., JANARDAN, R., AND SMID, M. 1996. Efficient algorithms for counting and reporting pairwise intersection between convex polygons. Tech. Rep. Computer Science, King's College, UK.
• 14: Dan Halperin , Mark H. Overmars, Spheres, molecules, and hidden surface removal, Proceedings of the tenth annual symposium on Computational geometry, p.113-122, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177574]
• 15: HARDY, H., LITTLEWOOD, g. E., AND P LYA, G. 1988. Inequalities. Cambridge University Press, New York, NY.
• 16: Martin Held , James T. Klosowski , Joseph S. B. Mitchell, Collision detection for fly-throughs in virtual environments, Proceedings of the twelfth annual symposium on Computational geometry, p.513-514, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237428]
• 17: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 18: 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]
• 19: James T. Klosowski , Martin Held , Joseph S. B. Mitchell , Henry Sowizral , Karel Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, v.4 n.1, p.21-36, January 1998 [doi>10.1109/2945.675649]
• 20: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 21: Jiri Matousek , Janos Pach , Micha Sharir , Shmuel Sifrony , Emo Welzl, Fat Triangles Determine Linearly Many Holes, SIAM Journal on Computing, v.23 n.1, p.154-169, Feb. 1994 [doi>10.1137/S009753979018330X]
• 22: Leonard McMillan, Jr., An image-based approach to three-dimensional computer graphics, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1997
• 23: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 24: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.289-298, June 1988
• 25: Elmar Schömer , Christian Thiel, Efficient collision detection for moving polyhedra, Proceedings of the eleventh annual symposium on Computational geometry, p.51-60, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220285]
• 26: VAN DER STAPPEN, A. F., HALPERIN, D., AND OVERMARS, M. H. 1993. Efficient algorithms for exact motion planning amidst fat obstacles. In Proceedings of the IEEE International Conference on Robotics and Automation, IEEE Computer Society, New York, NY, 297-304.
• 27: Yunhong Zhou , Subhash Suri, Analysis of a bounding box heuristic for object intersection, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.830-839, January 17-19, 1999, Baltimore, Maryland, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Performance, Theory

Keywords:
aspect ratio, bounding boxes, collison detection