H-COLLIDE: A Framework for Fast and Accurate Collision Detection for Haptic Interaction

Motivation

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 6-DoF-in/3-DoF-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. In addition, the skin is sensitive to vibrations greater than 500 Hz, 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-DoF arms) and deformable surfaces.

System Overview

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.

Implementation and Performance

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 3-DoF 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 towards which the PHANToM probe should move. 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.

Method	Hash Grid	Hybrid	OBBTree	GHOST
Ave Col. Hit	0.0122	0.00883	0.0120	0.0917
Worst Col. Hit	0.157	0.171	0.0800	0.711
Ave Col. Miss	0.00964	0.00789	0.00856	0.0217
Worst Col. Miss	0.0753	0.0583	0.0683	0.663
Ave Int. Hit	0.0434	0.0467	0.0459	0.0668
Worst Int. Hit	0.108	0.102	0.0793	0.100
Ave Int. Miss	0.0330	0.0226	0.0261	0.0245
Worst Int. Miss	0.105	0.141	0.0890	0.364
Ave. Query	0.019	0.014	0.017	0.048

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

Method	Hash Grid	Hybrid	OBBTree	GHOST
Ave Col. Hit	0.0115	0.0185	0.0109	0.131
Worst Col. Hit	0.142	0.213	0.138	0.622
Ave Col. Miss	0.0104	0.00846	0.0101	0.0176
Worst Col. Miss	0.0800	0.0603	0.0813	0.396
Ave Int. Hit	0.0583	0.0568	0.0652	0.0653
Worst Int. Hit	0.278	0.200	0.125	0.233
Ave Int. Miss	0.0446	0.0237	0.0349	0.0322
Worst Int. Miss	0.152	0.173	0.111	0.287
Ave. Query	0.030	0.025	0.028	0.070

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

Method	Hash Grid	Hybrid	OBBTree	GHOST
Ave Col. Hit	0.0138	0.0101	0.0134	0.332
Worst Col. Hit	0.125	0.168	0.0663	0.724
Ave Col. Miss	0.00739	0.00508	0.00422	0.0109
Worst Col. Miss	0.0347	0.0377	0.0613	0.210
Ave Int. Hit	0.0428	0.0386	0.0447	0.0851
Worst Int. Hit	0.0877	0.102	0.0690	0.175
Ave Int. Miss	0.0268	0.0197	0.0213	0.0545
Worst Int. Miss	0.0757	0.0697	0.0587	0.284
Ave. Query	0.022	0.016	0.039	0.18

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

Method	Hash Grid	Hybrid	OBBTree	GHOST
Ave Col. Hit	0.0113	0.00995	0.0125	0.104
Worst Col. Hit	0.136	0.132	0.177	0.495
Ave Col. Miss	0.0133	0.00731	0.0189	0.0280
Worst Col. Miss	0.128	0.0730	0.137	0.641
Ave Int. Hit	0.0566	0.0374	0.609	0.0671
Worst Int. Hit	0.145	0.105	0.170	0.293
Ave Int. Miss	0.0523	0.0225	0.0452	0.0423
Worst Int. Miss	0.132	0.133	0.167	0.556
Ave. Query	0.027	0.014	0.028	0.048

Timings an 18K triangle model of a Ford Bronco.

Method	Hash Grid	Hybrid	OBBTree	GHOST
Ave Col. Hit	0.0232	0.0204	0.0163	1.33
Worst Col. Hit	0.545	0.198	0.100	5.37
Ave Col. Miss	0.00896	0.00405	0.00683	0.160
Worst Col. Miss	0.237	0.139	0.121	3.15
Ave Int. Hit	0.228	0.0659	0.0704	0.509
Worst Int. Hit	0.104	0.138	0.103	1.952
Ave Int. Miss	0.258	0.0279	0.0256	0.229
Worst Int. Miss	0.0544	0.131	0.0977	3.28
Ave. Query	0.030	0.016	0.016	0.32

Timings for a butterfly model with 79K triangles.

Publications

H-Collide: A Framework for Fast and Accurate Collision Detection for Haptic Interaction (8 pages: PDF, 209 KB)
Arthur D. Gregory, Ming C. Lin, Stefan Gottschalk, and Russell M. Taylor II.
Proceedings of IEEE Virtual Reality Conference 1999.
Fast and Accurate Collision Detection for Haptic Interaction Using a Three Degree-of-Freedom Force-Feedback Device (24 pages: PDF, 238 KB)
Arthur D. Gregory, Ming C. Lin, Stefan Gottschalk, and Russell M. Taylor II.
Computational Geometry: Theory and Applications.
Contact Determination for Real-time Haptic Interaction in 3D Modeling, Editing and Painting (4 pages: PDF, 18 KB)
Ming C. Lin, Arthur D. Gregory, Stephen A. Ehmann, Stefan Gottschalk, and Russell M. Taylor II.
Proceedings of the 1999 Workshop for PhanTom User Group.

Principle Investigator

Ming C. Lin

Other Faculty Members

Russell M. Taylor II

Past Project Members

Arthur D. Gregory
Stefan Gottschalk

Other Related Projects

For more information, contact geom@cs.unc.edu
Last content update: January 3, 2000
Last content review: January 3, 2000

Copyright 1998-2000. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.