Graphical display of deformable objects has been extensively studied in computer graphics. With the addition of haptic feedback, deformable objects gain a new characteristic. Now, our models should not only estimate the direction and the amount of deformation of each node but also the magnitude and direction of interaction forces that will be reflected to the user via a haptic device. This tutorial note discusses the modeling and programming principles of force-reflecting deformable objects. 

Surgical simulators are currently being developed at many research centers and companies to train doctors and residents with new surgical devices and techniques. Conveying to the surgeon the touch and force sensations with the use of haptic interfaces is an important component of a simulator. Force-reflecting deformable models in various fidelities need to be developed to simulate the behavior of soft tissues when they are manipulated with surgical instruments. The developed algorithms should deal directly with geometry of anatomical organs, surface and compliance characteristics of tissues, and the estimation of appropriate reaction forces to convey to the user a feeling of touch and force sensations.

3D modeling of deformable objects using NURBS or FFD are well known concepts in CAD. With the addition of force feedback, the interactions will be more intuitive and physically based. For example, various constraints can be implemented naturally using force feedback.

An animator can intuitively deform the body parts of a 3D character using a haptic device. For example, an animator can use force cues to decide on how much the knee of a 3D character should be flexed at each time frame to make its locomotion more realistic.

Mechanistic interactions between the melted materials and the manufacturing tools can be studied in virtual environments. For example, an extrusion process can be simulated to better understand the behavior of materials under certain external loads.

• reflect stable forces
• display smooth deformations
• handle various boundary conditions and constraints
• display "physically-based" behavior in real-time

One way to categorize the deformation techniques is according to the approach followed by the researchers to deform the surfaces: geometric or physically-based deformations. In geometric deformations, the object or the surrounding space is deformed based purely on geometric manipulations. In general, the user manipulates vertices or control points that surround the 3D object to modify the shape of the object. On the other hand, physically-based deformation techniques aim to model the physics involved in the motion and dynamics of interactions. Models simulate physical behavior of objects under the affect of external and internal forces. Geometric-based deformation techniques are faster, and are relatively easier to implement. But they do not simulate the underlying mechanics of deformations. Hence, the emphasis is on visual display and the goal is to make deformations appear smoother to the end-user. Sophisticated physically based models, although necessary for simulating the dynamics of realistic interactions, are not suitable for fully interactive, real-time simulation of multiple objects in virtual environments due to the current limitations in computational power. 

• a sample subroutine for particle-based deformations
• a sample matlab file for modal analysis

• A damping term needs to be considered to bring the system into a global equilibrium. Increasing damping makes the system stiffer. This is going to force us to take shorter time steps to achieve stability. 
• Adding multiple constraints leads to a stiffer system. We may need to reduce the “elasticity” of the system to control the deformations. This is, again, going to force us to take shorter time steps to achieve stability. 
• Uneven distribution of vertices (nodes) of the 3D model may easily generate unstable interaction forces and non-smooth graphical deformations.
• Note that explicit integration schemes are conditionally stable (see the work done by Barraf and Witkin on implicit techniques, “Large steps in Cloth animation”, SIGGRAPH’98)

 
The following solutions has been  proposed for these problems:
 
• Taking variable time step to improve the stability
• Considering local deformations to reduce the stability problems
• Remeshing or automatic refinement to reduce the stability problems and to make the deformations appear smoother
• Controlling deformation and/or force update rate

In general, finite element models are comphrensive and well suited for accurate computation of deformations. However, it is difficult achive a real-time performance using FEM. Moreover, the addition of haptic feedback increases the complexity of the problem. To achive real-time rendering rates,   Inv(K) can be pre-computed and static condensation (i.e. eliminating unwanted degrees of freedom) technique can be implemented. However, the precomputation of  is a problem if the topology of object permenantly changes during the interaction. For example, if an object is sliced or cut, it has to be remeshed and the stiffness matrix has to be updated. Moreover, taking the inverse of the K matrix is not trouble free and singularities may occur. Finally, the entries of the matrices need to be allocated wisely to save from the memory. 

• Synchronize your haptic and graphic loops: Software integration of visual and haptic modalities was achieved in an efficient manner by creating a hierarchical database for geometrical properties of objects and by programming with multi-threading techniques. In our simulations, visual and haptic servo loops were separated to achieve faster rendering rates. When displaying visual images, it is known that the update rate should be around 30 Hz to appear continuous. On the other hand, to create a satisfying haptic display, the update rates for sending the force commands to the haptic interface needs to be about 1000 Hz. In order to create a VE that satisfies both requirements and optimally use the CPU power of a computer, the visual and the haptic servo loops need to be separated. That is, we run two loops at the same time, with the graphic loop updated at 30 Hz and the haptic loop updated at 1000 Hz. Since there are two loops running at the same time, there is always a chance a conflict occurs in accessing the shared memory. For example, in the case of simulating deformable objects, changes in geometry require frequent updates of visual and haptic databases in real-time. This will cause a problem if one loop is writing data to the memory and the other loop is reading from there. In order to avoid this situation, we need to synchronize the two loops. The easiest way to synchronize two loops is to create a Boolean flag. When one loop wants to access the shared data, it should check the flag first to see if the data is being accessed by the other loop. If the flag indicates that the shared memory is not being used, the loop can access the data and the flag is set to indicate that the shared memory is currently being used. If the flag indicates that the data is being used by the other loop, the loop waits until the other loop is done. When one loop finishes its operations with the shared memory, it sets the flag back to normal to let other loop access the data. 
• Construct a multi-layered computational architecture: Although separating haptic and graphic loops, using a client-server model as described in the previous paragraph, is helpful in improving update rates, it may not be sufficient in certain situations. In a typical client-server model for haptic rendering of 3D objects, haptic thread is usually designated as the client and the model computations are performed in this thread. However, physically-based modeling techniques for displaying forces and deformations are computationally expensive and the haptic update rate may drop below the requirement. For example, a real-time dynamic analysis of force-reflecting deformable objects using finite-element techniques is quite difficult with the available computational power. To overcome this difficulty, we suggest a layer between the “computation” and the “display” modules. In this layer, forces can be extrapolated based on the previous force values and their rate of change. Based on this approach, forces can be computed at 200 Hz using a finite element technique, extrapolated in between the computation cycles, and displayed to the user at 1 kHz.
• Construct a data structure for primitive hierarchy: We use polygonal models in our simulations. We separate each polyhedron into three types of primitives: vertices, lines (i.e. edges), and polygons. In our database, each primitive has a pointer to its neighboring primitives. The primitive hierarchy helps us to quickly access the neighbors of the primitive when it is necessary. For example, when a simulated tool contacts a primitive of an object in the current loop to modify its coordinates, we know that, in the next loop, the model can only affect the primitives that are in the close neighborhood of the contacted primitive. Neighborhood hirerchy is helpful in simulating force-reflecting deformable objects. For example, forces due to inertial effects can be transferred to all nodes by propagating radially through the neighboring primitives from the contact point.

• consider deforming your object locally
• take advantage of single point interactions
• condense your matrices by eliminating unwanted degrees of freedom
• pre-compute as much as you can
• solve your system for unit displacements/forces and then superimpose solutions
• transform your coordinates to modal coordinates to perform dynamic analysis
• try decoupling your force and visual deformation models

1. Ackerman, M. J., 1994, "The Visible Human Project.", Medicine Meets Virtual Reality II: Interactive Technology and Healthcare, 5-7. 

2. Basdogan C., Ho, C., Srinivasan, M.A., 1999, "Simulation of Tissue Cutting and Bleeding for Laparoscopic Surgery Using Auixilary Surfaces" To appear in the proceedings of the Medicine Meets Virtual Reality VII Conference, San Francisco, CA. 

3. Basdogan C., Ho, C., Srinivasan, M.A., Small, S., Dawson, S., 1998, "Force interactions in laparoscopic simulations: haptic rendering of soft tissues" Medicine Meets Virtual Reality VI, pp. 385-391, San Diego, CA, January 19-22. 

4. Basdogan C., Loan J.P., Rosen J.M., Delp S.L., 1996, "An interactive model of the human lower limb for simulation of surgical procedures in virtual environments", the Winter Annual Meeting of ASME'96, BED-Vol. 33, pp. 439-440, Nov. 17-22, Atlanta (see http://touchlab.mit.edu/people/publications.html)

5. Bier, E.A., Sloan K.R., 1986, "Two-Part Texture Mapping", IEEE Computer Graphics and Applications, September, pp. 40-53. 

6. Bro-Nielson, M., 1997, "Fast Finite Elements for Surgery Simulation" Medicine Meets Virtual Reality V, pp. 395-400.

7. Canny, J., 1986, "A computational approach to edge detection.", IEEE Trans Pat An Mach Int., 8, 679-698. 

8. Carter, F. J., 1998, "Biomechanical Testing of Intra-Abdominal Soft Tissue", Tutorial Notes, Int. Workshop on Tissue Deformation and Palpation, Oct. 10, 1998, Cambridge, MICCAI'98. 

9. Chen, E., Markus, B., 1998, "Force Feedback for Surgical Simulation", Proceedings of the IEEE, Vol. 86, No. 3, pp. 524-530. 

10. Cohen, L.D., Cohen, I., 1993 "Finite Element Methods for Active Contour Models and Balloons for 2D and 3D images", IEEE Trans. On Pattern Analysis and Machine Intelligence, Vol. 15, No. 11, pp. 1131-1147. 

11. Cover, S.A., Ezquerra N.F., O'Brien J. F., Rowe R., Gadacz T., Palm E., 1993, "Interactively Deformable Models for Surgery Simulation.", IEEE Computer Graphics and Applications, pg. 68-75.

12. Delingette, H., 1998, "Toward Realistic Soft-Tissue Modeling in Medical Simulation", Proceedings of the IEEE, Vol. 86, No. 3, pp. 512-523. 

13. Gibson, S., Mirtch, B., 1997, "A Survey of Deformable Modeling in Computer Graphics", Technical Report No: TR97-19, MERL, http://www.merl.com/reports/index.html. 

14. Gupta, V., Reddy N., Batur, P., 1997, "Forces in Laparoscopic Surgical Tools", Presence: Teleoperators and Virtual Environments, Vol. 6, No. 2, pp. 218-228. 

15. Ho, C., Basdogan, C., Srinivasan, M.A., 1998, "An Efficient Haptic Rendering Technique for Displaying Polygonal Objects with Surface Details in Virtual Environments" submitted to Presence: Teleoperators and Virtual Environments. 

16. Hubbard, P., 1995, "Collision Detection for Interactive Graphics Applications", IEEE Transactions on Visualization and Computer Graphics, 1(3), Sept., pp. 219-230. 

17. Johnston, R. et al., 1996, " Assessing a Virtual Reality Surgical Skills Simulator", Medicine Meets Virtual Reality IV, pp. 608-617. 

18. Kass, M., Witkin, A., Terzopoulos, D., 1987, "Snakes: Active contour models", Int. J. of Computer Vision, 1 (4). 

19. Lee, Y., Terzopoulos, D., Waters, K., 1995, "Realistic Modeling for Facial Animation", Proceedings of SIGGRAPH'95, ACM, pp. 55-62. 

20. Lin, M., 1993, "Efficient Collision Detection for Animation and Robotics,'' Ph.D. thesis, University of California, Berkeley.

21. McInerney T., Terzopoulos, D., 1995, "A Dynamic Finite Element Surface Model for Segmentation and Tracking in Multidimensional Medical Images with Applications to Cardiac 4D Image Analysis", Comp. Medical Imaging and Graphics, Vol. 19, No. 1, pp. 69-83. 

22. Mirtch, B., 1997, "Efficient Algorithms for Two-Phase Collision Detection", Technical Report No: TR97-23, MERL, http://www.merl.com/reports/index.html.

23. O'Toole, R., et al., 1997, "A Novel Virtual Reality Surgical Trainer with Force Feedback: Surgeon vs. Medical Student Performance", Proceedings of the Second Phantom User's Group Workshop, Published as MIT Artificial Intelligence Lab Technical Report No. 1617, and RLE Technical Report No. 618. 

24. Schroeder, W., Martin, K., Lorensen, B., 1996, "The Visualization Toolkit: An Object-Oriented Approach to 3D Graphics", Prentice Hall, Inc., New Jersey. 

25. Weghorst, S., Airola, C., Oppenheimer, P., 1998, "Validation of the Madigan ESS Simulator", Medicine Meets Virtual Reality VI, pp. 399-405, San Diego, CA, January 19-22. 

26. Witkin A., Barraff D., Kass M., 1997, "An Introduction to Physically-Based Modeling", SIGGRAPH'97 Course Notes, http://www.cs.cmu.edu/afs/cs.cmu.edu/user/aw/www/awhome.html