‹header›
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
‹date/time›
‹footer›
‹#›
Haptic rendering or force display is often rendered through a force feedback device by delivering contact or restoring forces to prevent the haptic probe penetrating into a virtual object.  This is normally achieved by first detecting if a collision or penetration has occurred, determing the projected or surface contact points, and then computing the amount of penetration.  Based on the contact information, contact or restoring force is then calculated to resist further push from the user.  Sometimes, the separation distance is also computed to estimate the time of impact to reduce the frequency of collision checks.  These geometric computations -- distance computation, collision detection, contact manifold computation and penetration depth calculation -- are what I refer to as “proximity queries” to be addressed in the next few minutes.
These queries have been studied for decades in robotics, computational geometry, computer graphics and Virtual reality.  There is a large body of literature in these areas.  Some of the known techniques include hieararchies of bounding volumes, spatial partitioning, analytical solutions, and techniques that take advantages of motion coherence between successive frames.  However, most of the existing proximity query algorithms are not readily applicable to haptic rendering.  This is due to the fact that haptic rendering has stringent performance requirements.
For example, some of the commerical hardware, such as Phantom, requires force update at 1000 Hz.  This implies that all the force computation and thus proximity queries must be executed in much less than 1 ms.  In addition, the algorithm should scale well to complex, large models and be general enough to be applied to different environments – either static or dynamic. In addition, the design of any proximity query algorithm should also consider implementation issues, since it will be interfaced and tested with hardware devices.  For example, it should be robust enough to handle numerical errors and geometric degeneracies.  Will the data representation affect the design of the algorithm?  Is the algorithm general enough to deal
With challenging scenarios, such parallel close proximity, multiple contacts, etc.
Nearly all the existing work cannot address these issues simultaneously at KHz rates, especially when the environment is dynamic and there may be multiple contacts.  So, we need to reconsider the fundamental design of the algorithmic framework to meet the desired performance requirements for haptic rendering.
So, given the amount of time we have, I will present a survey of our recent work at UNC. I’ll first talk about some proximity queries for 3-DOF force display and then 6-DOF haptic rendering.  I’ll show some applications of our work on painting and modeling.  Then, I’ll quickly describe some approaches that we are currently investigating and some possible future research directions to conclude.
Next, I’ll present the design of our collision detection library for 3-DOF haptic rendering, H-Collide.
We made the following observations:
There is little movement in less than 1 millisecond.  This implies that there is a relatively high spatial and temporal coherence between successive time steps.  Information from previous computation can probably be used to initialize the current computation.
Also, since the motion between time steps is small,  potential contact region is localized to a small neighborhood.
Based on these observation, we use a hybrid approach that specializes several earlier algorithms to meet the stringent performance of haptic rendering.  Our framework utilizes many geometric concepts and data structures from computational geometry, including spatial partitioning, bounding volume hierarchy and frame-to-frame coherence.
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 locate the cell containing the path swept out by the probe.
For each cells consisting of a subset of polygons in a virtual model, we precompute an OBBTree, i.e. hierarchy of oriented bounding boxes.  At runtime, most of the computation time is spend in finding collisions btw  an OBBTree and the path swept out by the tip of the haptic probe between successive time steps.  To optimize this queries, we have developed a very specialized overlap test between a line segment and an OBB, that takes just a few operations (42-72, TXF included).
Typically there is little movement in the probe position between successive steps.  So, our algorithm take advantage of this motion coherence by caching the previous contact information to perform incremental computations.
Our most recent result in collision detection is a new algorithm that uses multi-resolution techniques, called SWIFT. 
Here are couple video clips of dynamic simulation of 3 tori of different sizes sliding down a spiral.  In both simulation scenarios, there are multiple contacts which are normally difficult to handle interactively.  Although this is a playback, the actually simulation is only slightly slower.
If you are interested, the details of the algorithm and system is available at
http://www.cs.unc.edu/~geom/SWIFT
Here are couple kinematic simulation of grinding teeth and opening jars.  The model of the teeth and jars are scanned in from a real patient and provided by a dentist, who is interested in using simulation technology to perform automatic crown fitting & adjustment.
(Joke:  The video clips were made during the Halloween.  The colors were chosen by the Ph.D. student, Stephen Ehmann, to show the Halloween spirit.  :-))
Left: We have a dynamic scene with objects moving under the influence of gravity. There are three dice in a box-like shaker. The user can grab the shaker and influence the motion of the dice. Gravity results in the user feeling continuous force and torque and the collisions between the shaker and the dice result in impulse force and torque which are felt as small “blips”.
Right: In this setup, there are four cubes, four spheres (320 faces each), four ellipsoids (320 faces each) and a stick like block. The user can grab any object and move about interacting with the other objects, using a 6-DOF haptic interface.  As the objects collide with the red stick held by the user, the user can feel the “bumps”, as collision occurs.
Very recently we developed a new approach for computing generalized proximity information of arbitrary 2D objects using graphics hardware to simulate interaction among multiple moving objects. Using multi-pass rendering techniques and accelerated distance computation we present a unified approach for performing a variety of proximity queries between objects. We use a hybrid geometry- and image-based apprach, that balances computation between CPU and graphics subsystems.
Our approach provides proximity information at interactive rates for a variety of simulation strategies including backtracking and penalty-based collision responses.  The main features of our approach are:  generality, simplicity, efficiency, no precomputation, robustness, bounded error approximation, and portability.
Here is a short video clip on bumper cars simulation.
Here is another short video clip on bumping letters & gears simulation.
This demonstration shows how some 3D scenes can be simplified to a 2D collision detection problem. Here we demonstrate various convex rigid body scenes moving and interacting realistically.
Here is a video clip showing 3D Deformable Body Dynamics using 2D queries.
This demonstration shows two deformable jellos colliding and responding based on their penetration. The models are deforming, showing how our method is dynamic and does not rely on any precomputation.