QuickTrace: a fast algorithm to detect contact

QuickTrace is a new, fast contact detection algorithm. It searches for contact typically between a tool, modelled by some kind of geometrical surface facets, and deforming material. Contact is searched for at material surface points called contact nodes. A contact node is in contact with a facet when the contact node is inside of the tool and the negative outer normal on the material surface at the contact node ‘leaves’ the tool surface through that facet. When multiple facets are intersected, only the closest facet to the contact node should be considered. From this de nition of contact, the penetration depth results automatically as a by-product. In QuickTrace, the m facets of the tool are packaged in boxes that are hierarchically ordered in a search tree with an average depth of log4 m. The computational complexity for one contact search is proportional to this average depth. So, for n contact nodes the computational complexity is O(n log4 m). This places QuickTrace amongst the best performing contact detection algorithms. At the same time there are no approximations or tricks involved and the contact detection is absolutely correct. The algorithm can easily be extended to material–material or tool–tool contact