Benefits of applicability constraints in decomposition-free interference detection between nonconvex polyhedral models

Abstract

Non-convex polyhedral models of workpieces or robot parts can be directly tested for interference, without resorting to a previous decomposition into convex entities. Here we show that this interference detection, based on the elemental edge - face intersection test, can be performed efficiently: a computational effort reducing strategy based on applicability constraints reduces drastically the set of edge - face pairings that have to be considered for intersection. This is accomplished by using an appropriate representation, the Spherical Face Orientation Graph, developed by the authors, as well as feature pairing algorithms, based on the line sweep paradigm, that have been adapted to work on that representation. Furthermore, the benefits of such a strategy extend to the computation of a lower distance bound between the polyhedra, particularly on the quality of this lower bound. Experimental results confirm the expected advantages of this strategy.