Publication

An orientation-based pruning tool to speed up contact determination between translating polyhedral models

Journal Article (2001)

Journal

The International Journal of Robotics Research

Pages

466-483

Volume

20

Number

6

Doc link

http://dx.doi.org/10.1177/02783640122067499

File

Download the digital copy of the doc pdf document

Abstract

Contact determination in terms of edge-face intersection tests permits handling nonconvex polyhedra directly, without decomposing them into convex entities. This saves the decomposition time and avoids having to deal with fictitious features, but requires checking all possible pairings. However, by considering only translations and departing from a noninterfering situation, the number of pairings to be checked decreases drastically. The set of critical pairings can be determined efficiently by using the Spherical Face Orientation Graph (SFOG), a representation developed by the authors. An algorithm to exploit the SFOG in convex settings provides controlled evidence of the pruning potential of this approach: the number of critical pairings grows linearly with the complexity of the polyhedra, instead of quadratically as the total number of pairings does. Experiments with a similar algorithm on nonconvex settings confirm the expected potential of the approach: for workpieces with many concavities moving in close proximity, our contact determination procedure performs one order of magnitude faster than RAPID, at the expense of a much higher preprocessing time.

Categories

robots.

Author keywords

multiple contacts, interference checking, collision detection, nonconvex polyhedra, sphere of orientations

Scientific reference

P. Jiménez and C. Torras. An orientation-based pruning tool to speed up contact determination between translating polyhedral models. The International Journal of Robotics Research, 20(6): 466-483, 2001.