Guaranteed collision detection with toleranced motions |
| |
Affiliation: | 1. Department of Mathematics, University of Oslo, PO Box 1053, Blindern, 0316 Oslo, Norway;2. SINTEF ICT, PO Box 124, Blindern, 0314 Oslo, Norway;1. Dept. of Mathematics, Darmstadt University of Technology, Germany;2. University of Passau, Innstrasse 43, 94032 Passau, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Toleranced motion Collision detection Bounding ball Bounding volume |
本文献已被 ScienceDirect 等数据库收录! |
|