Abstract
The directional contact range of two convex polyhedra is the range of positions that one of the polyhedron may locate along a given straight line so that the two polyhedra are in collision. Using the contact range, one can quickly classify the positions along a line for a polyhedron as “safe” for free of collision with another polyhedron, or “unsafe” for the otherwise. This kind of contact detection between two objects is important in CAD, computer graphics and robotics applications. In this paper we propose a robust and efficient computation scheme to determine the directional contact range of two polyhedra. We consider the problem in its dual equivalence by studying the Minkowski difference of the two polyhedra under a duality transformation. The algorithm requires the construction of only a subset of the faces of the Minkowski difference, and resolves the directional range efficiently. It also computes the contact configurations when the boundaries of the polyhedra are in contact.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Jiménez, P., Thomas, F., Torras, C.: 3D collision detection: a survey. Computers & Graphics 25(2), 269–285 (2001)
Lin, M.C., Manocha, D.: Collision and proximity queries. In: Handbook. of Discrete and Computational Geometry (2003)
Cameron, S., Culley, R.: Determining the minimum translational distance between two convex polyhedra. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 591–596 (1986)
Gilbert, E.G., Johnson, D.W., Keerthi, S.S.: A fast procedure for computing the distance between objects in three-dimensional space. IEEE J. Robot. Automat. (4), 193–203 (1988)
Lin, M.C., Canny, J.: A fast algorithm for incremental distance calculation. In: Proc. IEEE Int. Conf. on Robotics and Automation, Sacremento, pp. 1008–1014 (April 1991)
Mirtich, B.: V-Clip: Fast and robust polyhedral collision detection. ACM Trans. Graph. 17(3), 177–208 (1998)
Kim, Y.J., Lin, M.C., Manocha, D.: Incremental penetration depth estimation between convex polytopes using dual-space expansion. IEEE Trans. Visual. Comput. Graphics 10(2), 152–163 (2004)
Dobkin, D.P., Hershberger, J., Kirkpatrick, D.G., Suri, S.: Computing the intersection-depth of polyhedra. Algorithmica 9(6), 518–533 (1993)
Günther, O.: Efficient structures for geometric data management. Springer, New York (1988)
Kolingerová, I.: Convex polyhedron-line intersection detection using dual representation. The Visual Computer 13(1), 42–49 (1997)
Grünbaum, B.: Convex Polytopes. Wiley, Chichester (1967)
Dobkin, D.P., Kirkpatrick, D.G.: A linear algorithm for determining the separation of convex polyhedra. J. Algorithms 6(3), 381–392 (1985)
Levy, H.: Projective and Related Geometry. Macmillan, Basingstoke (1964)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Choi, YK., Li, X., Rong, F., Wang, W., Cameron, S. (2008). Determining Directional Contact Range of Two Convex Polyhedra. In: Chen, F., Jüttler, B. (eds) Advances in Geometric Modeling and Processing. GMP 2008. Lecture Notes in Computer Science, vol 4975. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79246-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-79246-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79245-1
Online ISBN: 978-3-540-79246-8
eBook Packages: Computer ScienceComputer Science (R0)