Interference detection between non-convex polyhedra revisited with a practical aim

Exact interference checking between two arbitrary polyhedra is known to have O(mn) complexity, where m and n are the number of edges in the two polyhedra. This is just a worst-case bound that still leaves plenty of room for algorithm improvement in practice. The algorithm presented herein has been developed so as to: 1. Minimize the number of operations that each pairing of edges entails. We prove that this factor is 4.5 for multiplications and 8.5 for additions. 2. Avoid the construction of auxiliary geometric entities. The standard approach is to decompose the nonconvex polyhedra (or their faces) into convex entities and then check for interference in this convex setting. This entails the construction of many fictitious edges and faces, which indirectly contribute to the growth of the complexity. 3. Permit the straightforward application of prunning strategies to most practical situations, so that the worst-case bound above is reached only when truly needed. 4 Allow the derivation of both directional and undirectional distance bounds between the polyhedra, which prove extremely useful for collision avoidance and local path planning. The simplicity and homogeneity of the algorithm has led to a quick implementation, which has been proven to be robust and fast. Some performance measurements are reported