| Contact determination in terms
of edge-face intersection tests permits handling nonconvex polyhedra directly,
without decomposing them into convex entities, which 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
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,
the contact determination procedure presented in this paper performs one
order of magnitude faster than RAPID, at the expense of a much higher preprocessing
time. |
