Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We introduce a novel "sensation preserving" simplification algorithm for faster collision queries between two polyhedral objects in haptic rendering. Given a polyhedral model, we construct a multiresolution hierarchy using " filtered edge collapse", subject to constraints imposed by collision detection. The resulting hierarchy is then used to compute fast contact response for haptic display. The computation model is inspired by human tactual perception of contact information. We have successfully applied and demonstrated the algorithm on a time-critical collision query framework for haptically displaying complex object-object interaction. Compared to existing exact contact query algorithms, we observe noticeable performance improvement in update rates with little degradation in the haptic perception of contacts.

REFERENCES

• 1: Frederick P. Brooks, Jr. , Ming Ouh-Young , James J. Batter , P. Jerome Kilpatrick, Project GROPEHaptic displays for scientific visualization, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.177-185, September 1990, Dallas, TX, USA
• 2: Bernard Chazelle , David P. Dobkin , Nadia Shouraboura , Ayellet Tal, Strategies for polyhedral surface decomposition: an experimental study, Computational Geometry: Theory and Applications, v.7 n.5-6, p.327-342, April 1997 [doi>10.1016/S0925-7721(96)00024-7]
• 3: EHMANN, S., AND LIN, M. C. 2000. Accelerated proximity queries between convex polyhedra using multi-level voronoi marching. Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems.
• 4: EHMANN, S., AND LIN, M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Computer Graphics Forum (Proc. of Eurographics'2001) 20, 3.
• 5: EL-SANA, J., AND VARSHNEY, A. 2000. Continuously-adaptive haptic rendering. Virtual Environments 2000, pp. 135--144.
• 6: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 7: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 8: Arthur Gregory , Ajith Mascarenhas , Stephen Ehmann , Ming Lin , Dinesh Manocha, Six degree-of-freedom haptic display of polygonal models, Proceedings of the conference on Visualization '00, p.139-146, October 2000, Salt Lake City, Utah, United States
• 9: Leonidas J. Guibas , David Hsu , Li Zhang, H-Walk: hierarchical distance computation for moving convex bodies, Proceedings of the fifteenth annual symposium on Computational geometry, p.265-273, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304979]
• 10: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 11: Kenneth E. Hoff, III , Andrew Zaferakis , Ming Lin , Dinesh Manocha, Fast and simple 2D geometric proximity queries using graphics hardware, Proceedings of the 2001 symposium on Interactive 3D graphics, p.145-148, March 2001 [doi>10.1145/364338.364383]
• 12: HOLLERBACH, J., COHEN, E., THOMPSON, W., FREIER, R., JOHNSON, D., NAHVI, A., NELSON, D., AND II, T. T. 1997. Haptic interfacing for virtual prototyping of mechanical CAD designs. CDROM Proc. of ASME Design for Manufacturing Symposium.
• 13: Philip Martyn Hubbard, Collision detection for interactive graphics applications, Brown University, Providence, RI, 1996
• 14: Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Six-Degree-of-Freedom Haptic Display Using Localized Contact Computations, Proceedings of the 10th Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems, p.209, March 24-25, 2002
• 15: KLATZKY, R., AND LEDERMAN, S. 1995. Identifying objects from a haptic glance. Perception and Psychophysics 57, pp. 1111--1123.
• 16: James T. Klosowski , Martin Held , Joseph S. B. Mitchell , Henry Sowizral , Karel Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, v.4 n.1, p.21-36, January 1998 [doi>10.1109/2945.675649]
• 17: LARSEN, E., GOTTSCHALK, S., LIN, M., AND MANOCHA, D. 2000. Distance queries with rectangular swept sphere volumes. Proc. of IEEE Int. Conference on Robotics and Automation.
• 18: LIN, M., AND GOTTSCHALK, S. 1998. Collision detection between geometric models: A survey. Proc. of IMA Conference on Mathematics of Surfaces.
• 19: Jean-Christophe Lombardo , Marie-Paule Cani , Fabrice Neyret, Real-time Collision Detection for Virtual Surgery, Proceedings of the Computer Animation, p.82, May 26-28, 1999
• 20: David P. Luebke , Benjamin Hallen, Perceptually-Driven Simplification for Interactive Rendering, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, p.223-234, June 25-27, 2001
• 21: David Luebke , Benjamin Watson , Jonathan D. Cohen , Martin Reddy , Amitabh Varshney, Level of Detail for 3D Graphics, Elsevier Science Inc., New York, NY, 2002
• 22: William R. Mark , Scott C. Randolph , Mark Finch , James M. Van Verth , Russell M. Taylor, II, Adding force feedback to graphics systems: issues and solutions, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.447-452, August 1996 [doi>10.1145/237170.237284]
• 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: OKAMURA, A., AND CUTKOSKY, M. 1999. Haptic exploration of fine surface features. Proc. of IEEE Int. Conf. on Robotics and Automation, pp. 2930--2936.
• 25: Carol O'Sullivan , John Dingliana, Collisions and perception, ACM Transactions on Graphics (TOG), v.20 n.3, p.151-168, July 2001 [doi>10.1145/501786.501788]
• 26: OTADUY, M. A., AND LIN, M. C. 2003. CLODs: Dual hierarchies for multiresolution collision detection. UNC Technical Report TR03-013.
• 27: PAI, D. K., AND REISSEL, L. M. 1997. Haptic interaction with multiresolution image curves. Computer and Graphics 21, 405--411.
• 28: REDON, S., KHEDDAR, A., AND COQUILLART, S. 2002. Fast continuous collision detection between rigid bodies. Proc. of Eurographics (Computer Graphics Forum).
• 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: J. Kenneth Salisbury, Jr., Making graphics physically tangible, Communications of the ACM, v.42 n.8, p.74-81, Aug. 1999 [doi>10.1145/310930.310976]
• 31: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Virtual reality

Keywords:
collision detection, haptics, level-of-detail algorithms