Premium
QuickTrace: a fast algorithm to detect contact
Author(s) -
Bruneel Herman C. J.,
De Rycke Igor
Publication year - 2002
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.428
Subject(s) - node (physics) , facet (psychology) , contact area , algorithm , surface (topology) , computer science , geometry , mathematics , materials science , engineering , structural engineering , composite material , psychology , social psychology , personality , big five personality traits
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 definition 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 log 4 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 log 4 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. Copyright © 2002 John Wiley & Sons, Ltd.