Virtual environments require natural interaction between interactive computer systems and users. Compared to the presentation of visual and auditory information, methods for haptic display have not been sufficiently developed. Haptic rendering as an augmentation to visual display can improve perception and understanding both of force fields and of world models populated in the synthetic environments. It allows users to reach into virtual worlds with their hands, so they can touch, feel, grasp, and manipulate simulated objects.

Haptic display is often rendered through what is essentially a small robot arm, used in reverse. Such devices are now commercially available for a variety of configurations (2D, 3D, 6D, specialized for laparoscopy or general-purpose). The system used in this work was a 6DOF-in/3DOF-out SensAble Technologies PHANToM arm.

"Real-time" graphics applications have display update requirements somewhere between 20 and 30 frames/second. In contrast, the update rate of haptic simulations must be as high as 1000 updates/second in order to maintain a stable system. This rate varies with the spatial frequency and stiffness of displayed forces, and with the speed of motion of the user. Also, the skin is sensitive to vibrations greater than 500Hz, so changes in force at even relatively high frequencies are detectable.

In order to create a sense of touch between the user's hand and a virtual object, contact or restoring forces are generated to prevent penetration into this virtual model. This is computed by first detecting if a collision or penetration has occurred, then determining the (projected) contact point on the model surface. Most of the existing algorithms are only sufficient to address the collision detection and contact determination problems for relatively small models consisting of merely a few thousand polygons or a few surfaces. Our ultimate goal is to be able to achieve smooth, realistic haptic interaction with CAD models of high complexity (normally consisting of tens of thousands of primitives) for virtual prototyping applications. In addition, we are aiming at designing algorithms that are easily extensible to support a wide range of force-feedback devices (including 6 degree-of-freedom arms) and deformable surfaces.

H-Collide is a framework for fast and accurate collision detection for haptic interaction. It consists of a number of algorithms and a system specialized for computing contact(s) between the probe of the force-feedback device and objects in the virtual environment. To meet the stringent performance requirements for haptic interaction, we use an approach that specializes many earlier algorithms for this application. Our framework utilizes:

• Spatial Decomposition: It decomposes the workspace into uniform grids or cells, implemented as a hash table to efficiently deal with large storage requirements. At runtime, the algorithm can quickly find the cell containing the path swept out by the probe.
• Bounding Volume Hierarchy based on OBBTrees: An OBBTree is a bounding volume hierarchy and each node of the hierarchy corresponds to a tight-fitting oriented bounding box (OBB). For each cell consisting of a subset of polygons of the virtual model, we pre-compute an OBBTree. At run-time, most of the computation time is spent in finding collisions between an OBBTree and the path swept out by the tip of the probe between two successive time steps. To optimize this query, we have developed a very fast specialized overlap test between a line segment and an OBB, that takes as few as 6 operations and only 36 arithmetic operations in the worst case, not including the cost of transformation.
• Frame-to-Frame Coherence: Typically, there is little movement in the probe position between successive steps. The algorithm utilizes this coherence by caching the contact information from the previous step to perform incremental computations.

We have successfully implemented all the algorithms described above, interfaced them with GHOST (a commercial haptic library) and used them to find collisions between the probe of a 3DOF PHANToM arm and large geometric models (composed of tens of thousands of polygons). Their performance varies based on the geometric model, the configuration of the probe relative to the model, machine configuration (e.g. cache and memory size) and the combination of techniques used by our system. Our approach results in a factor of 3-20 speed improvement as compared to earlier algorithms and commercial implementations. For comparison, we have implemented adaptive grids, our hybrid approach, and an algorithm using only OBBTrees and the specialized overlap test. The test set for each of these models contains 30,000 readings. The distinction between a collision and an intersection shown in the tables is particular to GHOST's haptic rendering recipe. Each haptic update cycle contains a "collision" test to see if the line segment from the last position of the PHANToM probe to its current position has intersected any of the geometry in the haptic scene. If there has been a collision, then the intersected primitive suggests a surface contact point for the PHANToM probe to move towards. In this case it is now necessary to perform an "intersection" test to determine if the line segment from the last position of the PHANToM probe to the suggested surface contact point intersects any of the geometry in the scene (including the primitive with which there was a collision). The timings (in milliseconds), shown in the tables below, were obtained by replaying the test data set on a 400 MHz PC.

Timings for a model of a man symbol with 5K triangles

Timings for a 7K triangle model of a man with a hat

Timings for a 12K triangle model of a surface observed from the nanoManipulator Workbench

Timings an 18K triangle model of a ford bronco

Timings for a butterfly model with 79K triangles