Guaranteed collision detection with toleranced motions. (English) Zbl 1364.70011

Schröcker, Hans-Peter; Weber, Matthias J.

Comput. Aided Geom. Des. 31, No. 7-8, 602-612 (2014).

Summary: We present a method for guaranteed collision detection with toleranced motions. The basic idea is to consider the motion as a curve in the 12-dimensional space of affine displacements, endowed with an object-oriented Euclidean metric, and cover it with balls. The associated orbits of points, lines, planes and polygons have particularly simple shapes that lend themselves well to exact and fast collision queries. We present formulas for elementary collision tests with these orbit shapes and we suggest an algorithm, based on motion subdivision and computation of bounding balls, that can give a no-collision guarantee. It allows a robust and efficient implementation and parallelization. At hand of several examples we explore the asymptotic behavior of the algorithm and compare different implementation strategies.

MSC:

70B15	Kinematics of mechanisms and robots
65D18	Numerical aspects of computer graphics, image analysis, and computational geometry

Keywords:

toleranced motion; collision detection; bounding ball; bounding volume

Software:

ISOLATE

References:

[1]	Belta, C.; Kumar, V., An SVD-based projection method for interpolation on SE(3), IEEE Trans. Robot. Autom., 18, 3, 334-345, (2002)
[2]	Bernabeu, E. J.; Tornero, J.; Tomizuka, M., Collision prediction and avoidance amidst moving objects for trajectory planning applications, (Proceedings of IEEE Conference on Robotics and Automation, Seoul, Korea, (2001)), 3801-3806
[3]	Chirikjian, G. S.; Zhou, S., Metrics on motion and deformation of solid models, ASME J. Mech. Des., 120, 2, 252-261, (1998)
[4]	Dingliana, J.; O’Sullivan, C., Graceful degradation of collision handling in physically based animation, Eurographics, 19, 3, 239-248, (2000)
[5]	Donev, A.; Torquato, S.; Stillinger, F. H., Neighbor List collision-driven molecular dynamics for nonspherical hard particles: I. algorithmic details, J. Comput. Phys., 202, 737-764, (2005) · Zbl 1067.82061
[6]	Donev, A.; Torquato, S.; Stillinger, F. H., Neighbor List collision-driven molecular dynamics for nonspherical hard particles: II. applications to ellipses and ellipsoids, J. Comput. Phys., 202, 765-793, (2005) · Zbl 1067.82062
[7]	Ericson, C., Real-time collision detection, (2005), Morgan Kaufman
[8]	Greenspan, M.; Burtnyk, K., Obstacle count independent real-time collision avoidance, (Proceedings of IEEE International Conference on Robotics and Automation, Minneapolis, Minnesota, USA, (1996)), 1073-1080
[9]	Hofer, M.; Pottmann, H.; Ravani, B., From curve design algorithms to the design of rigid body motions, Vis. Comput., 20, 5, 279-297, (2004)
[10]	Hubbard, P. M., Collision detection for interactive graphics applications, IEEE Trans. Vis. Comput. Graph., 1, 3, 218-230, (1995)
[11]	Hwang, S.-G., Cauchy’s interlace theorem for eigenvalues of Hermitian matrices, Am. Math. Mon., 111, 2, 157-159, (2004) · Zbl 1050.15008
[12]	Martínez-Salvador, B.; del Pobil, A. P.; Pérez-Francisco, M., Very fast collision detection for practical motion planning. part I: the spatial representation, (Proceedings of IEEE Conference on Robotics and Automation, Leuven, Belgium, (1998)), 624-629
[13]	Moore, M.; Wilhelms, J., Collision detection and response for computer animation, Comput. Graph., 22, 4, 289-298, (1988)
[14]	Nawratil, G., New performance indices for 6R robots, Mech. Mach. Theory, 42, 11, 1499-1511, (2007) · Zbl 1126.70304
[15]	Quinlan, S., Efficient distance computation between non-convex objects, (Proceedings of IEEE Conference on Robotics and Automation, San Diego, United States, vol. 4, (1994)), 3324-3329
[16]	Rouillier, F.; Zimmerman, P., Efficient isolation of Polynomial’s real roots, J. Comput. Appl. Math., 162, 33-50, (2004) · Zbl 1040.65041
[17]	Schröcker, H.-P.; Wallner, J., Curvatures and tolerances in the Euclidean motion group, Results Math., 47, 132-146, (2005) · Zbl 1075.53007
[18]	Schröcker, H.-P.; Jüttler, B.; Aigner, M., Evolving four-bars for optimal synthesis, (Ceccarelli, M., Proceedings of EUCOMES 08, (2009), Springer), 109-116 · Zbl 1330.70043
[19]	Weller, R.; Zachmann, G., A unified approach for physically-based simulations and haptic rendering, (Proceedings of the 2009 ACM SIGGRAPH Symposium on Video Games, Sandbox ’09, (2009), ACM New York, NY, USA), 151-159
[20]	Weller, R.; Zachmann, G., Inner sphere trees for proximity and penetration queries, (2009 Robotics: Science and Systems Conference (RSS), Seattle, WA, USA, (2009))
[21]	Welzl, E., Smallest enclosing disks (balls and ellipsoids), (New Results and New Trends in Computer Science, Lecture Notes in Computer Science, vol. 555, (1991), Springer), 359-370