Zonotopes as bounding volumes

ABSTRACT

Zonotopes are centrally symmetric polytopes with a very special structure: they are Minkowski sums of line segments. In this paper we propose to use zonotopes as bounding volumes for geometry in collision detection and other applications where the spatial relationship between two pieces of geometry is important. We show how to construct optimal, or approximately optimal zonotopes enclosing given set of points or other geometry. We also show how zonotopes can be used for efficient collision testing, based on their representation via their defining line segments --- without ever building their explicit description as polytopes. This implicit representation adds flexibility, power, and economy to the use of zonotopes as bounding volumes.

REFERENCES

• 1: U. Betke and P. McMullen. Estimating the sizes of convex bodies from projections. Journal of London Mathematics Society, 27:525--538, 1983.
• 2: J. Bourgain, J. Lindenstrauss, and V. Milman. Approximation of zonoids by zonotopes. Acta Mathematics, 162:73--141, 1989.
• 3: S. Cameron. Collision detection by four-dimensional intersection testing. In Proc. IEEE Internat. Conf. Robot. Autom., pages 291--302, 1990.
• 4: 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]
• 5: Richard Cole , Jeffrey S. Salowe , W. L. Steiger , Endre Szemerédi, An optimal-time algorithm for slope selection, SIAM Journal on Computing, v.18 n.4, p.792-810, Aug. 1989 [doi>10.1137/0218055]
• 6: D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection. Theoret. Comput. Sci., 27(3):241--253, December 1983.
• 7: R. M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory, 10:227--236, 1974.
• 8: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 9: Jeff Erickson , Leonidas J. Guibas , Jorge Stolfi , Li Zhang, Separation-sensitive collision detection for convex objects, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.327-336, January 17-19, 1999, Baltimore, Maryland, United States
• 10: 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]
• 11: Philip M. Hubbard, Space-Time Bounds for Collision Detection, Brown University, Providence, RI, 1993
• 12: 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]
• 13: Birkett Huber , Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Mathematics of Computation, v.64 n.212, p.1541-1555, Oct. 1995 [doi>10.2307/2153370]
• 14: 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]
• 15: M. C. Lin and J. F. Canny. Efficient algorithms for incremental distance computation. In Proc. IEEE Internat. Conf. Robot. Autom., volume 2, pages 1008--1014, 1991.
• 16: B. Mirtich. V-Clip: Fast and robust polyhedral collision detection. Technical Report TR97--05, MERL, 201 Broadway, Cambridge, MA 02139, USA, July 1997.
• 17: Mark H. Overmars , Jan van Leeuwen, Dynamically maintaining configurations in the plane (Detailed Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.135-145, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804661]
• 18: I. J. Palmer and R. L. Grimsdale. Collision detection for animation using sphere-trees. Comput. Graph. Forum, 14(2):105--116, June 1995.
• 19: M. H. Wright. Interior methods for constrained optimization. In A. Iserles, editor, Acta Numerica 1992, pages 341--407. Cambridge University Press, New York, USA, 1992.
• 20: G. M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, Heidelberg, 1994.

INDEX TERMS

Primary 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

Additional Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Algorithms, Theory