Contact Determination for Real-time Haptic Interaction in 3D Modeling, Editing and Painting
Author(s): Ming C. Lin, Arthur Gregory, Stephen Ehmann, Stephan Gottschalk, Russ Taylor.
Proceedings: Proceedings of 1999 Workshop for PhanTom User Group,
1999.
[BibTeX] 
Abstract:
Collision detection and distance computation are important for a number of engineering applications including dynamic
simulation, tolerance verification, object manipulation, motion planning and control. Numerous algorithms and
techniques have been proposed. (See a recent survey [LG98].) In order to meet the stringent requirement of haptic
rendering, new algorithms and specialized system implementation need to be developed to substain KHz haptic update
rates on complex models. This requires improving the state of the art in contact determination by at least an order of
magnitude.
In this paper, we present a general and extensible algorithmic framework for fast and accurate contact determination
for haptic display of complex geometric models. Our ultimate goal is to support a wide range of force feedback
devices. Given a model, we pre-compute a hybrid hierarchical representation, utilizing both spatial partitioning and
bounding volume hierarchy. At run time, we use hybrid hierarchical representations and exploit frame-to-frame coherence
for fast proximity queries. We further discuss technical issues involved and propose approaches to improve the
overall system performance. An initial prototype system has been implemented and interfaced with a 3-dof 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 1000Hz on a
400MHz Pentium II.
Based on our prototype implementation “H-Collide”, we develop an intuitive 3D interface for interactively editing
and painting a 3D polygonal mesh using a 3-dof PHANToM. An artist or a designer can use this system to create
a multi-resolution polygonal mesh, further refine it by multi-resolution modeling techniques or enhance its look by
painting colors and textures on it. The system allows the user to naturally create complex forms by a sense of touch
and to freely interact with the design space without specification of rigorous mathematics.