Fast and accurate collision detection for haptic interaction using a three degree-of-freedom force-feedback device

We present a fast and accurate collision detection algorithm for haptic interaction with polygonal models. Given a model, we precompute a hybrid hierarchical representation, consisting of uniform grids (represented using a hash table) and trees of tight-fitting oriented bounding box trees (OBBTrees). At run time, we use hybrid hierarchical representations and exploit frame-to-frame coherence for fast proximity queries. We describe a new overlap test, which is specialized for intersection of a Line segment with an oriented bounding box for haptic simulation and takes 42-72 operations including transformation costs. The algorithms have been implemented as part of H-COLLIDE and interfaced with a PHANToM arm and its haptic toolkit, GHOST, and applied to a number of models. As compared to the commercial implementation, we are able to achieve up to 20 times speedup in our experiments and sustain update rates over 1000 Hz on a 400 MHz Pentium II. In practice, our prototype implementation can accurately and efficiently detect contacts between a virtual probe guided by a force-feedback arm and large complex geometries composed of tens of thousands of polygons, with substained KHz rates, (C) 2000 Elsevier Science B.V. All rights reserved.