Time-critical distributed contact for 6-DoF haptic rendering of adaptively sampled reduced deformable models

ABSTRACT

Real-time evaluation of distributed contact forces for rigid or deformable 3D objects is important for providing multi-sensory feedback in emerging real-time applications, such as 6-DoF haptic force-feedback rendering. Unfortunately, at very high temporal rates (1 kHz for haptics), there is often insufficient time to resolve distributed contact between geometrically complex objects.

In this paper, we present a spatially and temporally adaptive sample-based approach to approximate contact forces under hard real-time constraints. The approach is CPU based, and supports contact between a rigid and a reduced deformable model with complex geometry. Penalty-based contact forces are efficiently resolved using a multi-resolution point-based representation for one object, and a signed-distance field for the other. Hard realtime approximation of distributed contact forces uses multi-level progressive point-contact sampling, and exploits temporal coherence, graceful degradation and other optimizations. We present several examples of 6-DoF haptic rendering of geometrically complex rigid and deformable objects in distributed contact at real-time kilohertz rates.

REFERENCES

• 1: {AH98} Astley O., Hayward V.: Multirate Haptic Simulation Achieved by Coupling Finite Element Meshes Through Norton Equivalents. In Proc. of the IEEE Int. Conf. on Robotics and Automation (1998).
• 2: J. Andreas Baerentzen , Henrik Aanaes, Signed Distance Computation Using the Angle Weighted Pseudonormal, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.243-253, May 2005 [doi>10.1109/TVCG.2005.49]
• 3: {Bar07} Barbič J.: Real-time Reduced Nonlinear Deformable Objects for Computer Graphics and Haptics. PhD thesis, Computer Science Department, Carnegie Mellon University, 2007.
• 4: Jernej Barbič , Doug L. James, Real-Time subspace integration for St. Venant-Kirchhoff deformable models, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 5: {BNC96} Bro-Nielsen M., Cotin S.: Real-time Volumetric Deformable Models for Surgery Simulation using Finite Elements and Condensation. Comp. Graphics Forum 15, 3 (1996), 57--66.
• 6: Stéphane Cotin , Hervé Delingette , Nicholas Ayache, Real-Time Elastic Deformations of Soft Tissues for Surgery Simulation, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.62-73, January 1999 [doi>10.1109/2945.764872]
• 7: {CGSS93} Colgate J., Grafing P., Stanley M., Schenkel G.: Implementation of Stiff Virtual Walls in Force-Reflecting Interfaces. In Proc. of IEEE Virtual Reality Annual Int. Symp. (1993), IEEE, pp. 202--208.
• 8: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 9: Christian Duriez , Frederic Dubois , Abderrahmane Kheddar , Claude Andriot, Realistic Haptic Rendering of Interacting Deformable Objects in Virtual Environments, IEEE Transactions on Visualization and Computer Graphics, v.12 n.1, p.36-47, January 2006 [doi>10.1109/TVCG.2006.13]
• 10: Naga K. Govindaraju , David Knott , Nitin Jain , Ilknur Kabul , Rasmus Tamstorf , Russell Gayle , Ming C. Lin , Dinesh Manocha, Interactive collision detection between deformable models using chromatic decomposition, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 11: Philip Martyn Hubbard, Collision detection for interactive graphics applications, Brown University, Providence, RI, 1996
• 12: Seongki Jun , Jinbok Choi , Maenghyo Cho, Physics-based s-Adaptive Haptic Simulation for Deformable Object, Proceedings of the Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems, p.72, March 25-29, 2006
• 13: {JP01} James D. L., Pai D. K.: A Unified Treatment of Elastostatic Contact Simulation for Real Time Haptics. Haptics-e, The Electronic J. of Haptics Research (www.haptics-e.org) 2, 1 (September 2001).
• 14: Doug L. James , Dinesh K. Pai, DyRT: dynamic response textures for real time deformation simulation with graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 15: Doug L. James , Dinesh K. Pai, Multiresolution green's function methods for interactive simulation of large-scale elastostatic objects, ACM Transactions on Graphics (TOG), v.22 n.1, p.47-82, January 2003 [doi>10.1145/588272.588278]
• 16: Doug L. James , Dinesh K. Pai, BD-tree: output-sensitive collision detection for reduced deformable models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 17: {KcM00} Kühnapfel U., Çakmak H., MaassH.: Endoscopic surgery training using virtual reality and deformable tissue simulation. Computers & Graphics 24 (2000), 671--682.
• 18: {KMH*04} Keiser R., Müller M., Heidelberger B., Teschner M., Gross M.: Contact Handling for Deformable Point-Based Objects. In Proc. of Vision, Modeling, Visualization 2004 (2004), pp. 339--346.
• 19: Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Six-degree-of-freedom haptic rendering using incremental and localized computations, Presence: Teleoperators and Virtual Environments, v.12 n.3, p.277-295, 1 June 2003 [doi>10.1162/105474603765879530]
• 20: {LD07} Laycock S., Day A.: A Survey of Haptic Rendering Techniques. Computer Graphics Forum 26 (2007), 50--65.
• 21: {LLVT03} Lewiner T., Lopes H., Vieira A. W., Tavares G.: Efficient implementation of Marching Cubes' cases with topological guarantees. Journal of Graphics Tools 8, 2 (2003), 1--15.
• 22: {MO06} Mendoza C., O'Sullivan C.: Interruptible collision detection for deformable objects. Computer & Graphics 30, 2 (2006).
• 23: William A. McNeely , Kevin D. Puterbaugh , James J. Troy, Six degree-of-freedom haptic rendering using voxel sampling, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.401-408, July 1999 [doi>10.1145/311535.311600]
• 24: {MPT06} McNeely W., Puterbaugh K., Troy J.: Voxel-Based 6-DOF Haptic Rendering Improvements. Haptics-e 3, 7 (2006).
• 25: Miguel A. Otaduy , Markus Gross, Transparent Rendering of Tool Contact with Compliant Environments, Proceedings of the Second Joint EuroHaptics Conference and Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems, p.225-230, March 22-24, 2007 [doi>10.1109/WHC.2007.120]
• 26: Miguel A. Otaduy , Ming C. Lin, Sensation preserving simplification for haptic rendering, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 27: {OL06} Otaduy M. A., Lin M. C.: A Modular Haptic Rendering Algorithm for Stable and Transparent 6-DoF Manipulation. IEEE Trans. on Robotics 22, 4 (2006), 751--762.
• 28: Mark Pauly , Dinesh K. Pai , Leonidas J. Guibas, Quasi-rigid objects in contact, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028539]
• 29: Diego C. Ruspini , Krasimir Kolarov , Oussama Khatib, The haptic display of complex graphical environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.345-352, August 1997 [doi>10.1145/258734.258878]
• 30: Szymon Rusinkiewicz , Marc Levoy, QSplat: a multiresolution point rendering system for large meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.343-352, July 2000 [doi>10.1145/344779.344940]
• 31: {RPP*01} Renz M., Preusche C., Pötke M., Kriegel H.-P., Hirzinger G.: Stable haptic interaction with virtual environments using an adapted voxmap-pointshell algorithm. In Proc. of Eurohaptics (2001), pp. 149--154.
• 32: Chen Shen , James F. O'Brien , Jonathan R. Shewchuk, Interpolating and approximating implicit surfaces from polygon soup, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 33: Greg Turk, Re-tiling polygonal surfaces, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.55-64, July 1992
• 34: Greg Turk, Texture synthesis on surfaces, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.347-354, August 2001 [doi>10.1145/383259.383297]
• 35: Andrew P. Witkin , Paul S. Heckbert, Using particles to sample and control implicit surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.269-277, July 1994 [doi>10.1145/192161.192227]
• 36: Ming Wan , William A. McNeely, Quasi-Static Approximation for 6 Degrees-of-Freedom Haptic Rendering, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.34, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250380]
• 37: C. B. Zilles , J. K. Salisbury, A constraint-based god-object method for haptic display, Proceedings of the International Conference on Intelligent Robots and Systems-Volume 3, p.3146, August 05-09, 1995

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
      I.3.7 Three-Dimensional Graphics and Realism