“Sensation preserving simplification for haptic rendering” by Otaduy and Lin

  • ©Miguel A. Otaduy and Ming C. Lin




    Sensation preserving simplification for haptic rendering



    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.


    1. BROOKS, JR., F. P., OUH-YOUNG, M., BATTER, J. J., AND KILPATRICK, P. J. 1990. Project GROPE—Haptic displays for scientific visualization. In Computer Graphics (SIGGRAPH ’90 Proceedings), F. Baskett, Ed., vol. 24, 177–185. Google Scholar
    2. CHAZELLE, B., DOBKIN, D., SHOURABOURA, N., AND TAL, A. 1997. Strategies for polyhedral surface decomposition: An experimental study. Computational Geometry: Theory and Applications 7, 327–342. Google ScholarDigital Library
    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.Google Scholar
    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.Google Scholar
    5. EL-SANA, J., AND VARSHNEY, A. 2000. Continuously-adaptive haptic rendering. Virtual Environments 2000, pp. 135–144. Google Scholar
    6. GARLAND, M., AND HECKBERT, P. S. 1997. Surface simplification using quadric error metrics. In Proc. of ACM SIGGRAPH, 209–216. Google Scholar
    7. GOTTSCHALK, S., LIN, M., AND MANOCHA, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. Proc. of ACM SIGGRAPH, pp. 171–180. Google Scholar
    8. GREGORY, A., MASCARENHAS, A., EHMANN, S., LIN, M. C., AND MANOCHA, D. 2000. 6-dof haptic display of polygonal models. Proc. of IEEE Visualization Conference. Google Scholar
    9. GUIBAS, L., HSU, D., AND ZHANG, L. 1999. H-Walk: Hierarchical distance computation for moving convex bodies. Proc. of ACM Symposium on Computational Geometry. Google Scholar
    10. GUSKOV, I., SWELDENS, W., AND SCHRODER, P. 1999. Multiresolution signal processing for meshes. Proc. of ACM SIGGRAPH, pp. 325–334. Google Scholar
    11. HOFF, K., ZAFERAKIS, A., LIN, M., AND MANOCHA, D. 2001. Fast and simple geometric proximity queries using graphics hardware. Proc. of ACM Symposium on Interactive 3D Graphics. Google Scholar
    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.Google Scholar
    13. HUBBARD, P. 1994. Collision Detection for Interactive Graphics Applications. PhD thesis, Brown University. Google Scholar
    14. KIM, Y., OTADUY, M., LIN, M., AND MANOCHA, D. 2002. 6-dof haptic display using localized contact computations. Proc. of Haptics Symposium. Google Scholar
    15. KLATZKY, R., AND LEDERMAN, S. 1995. Identifying objects from a haptic glance. Perception and Psychophysics 57, pp. 1111–1123.Google ScholarCross Ref
    16. KLOSOWSKI, J., HELD, M., MITCHELL, J., SOWIZRAL, H., AND ZIKAN, K. 1998. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Trans. on Visualization and Computer Graphics 4, 1, 21–37. Google ScholarDigital Library
    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.Google ScholarCross Ref
    18. LIN, M., AND GOTTSCHALK, S. 1998. Collision detection between geometric models: A survey. Proc. of IMA Conference on Mathematics of Surfaces.Google Scholar
    19. LOMBARDO, J. C., CANI, M.-P., AND NEYRET, F. 1999. Real-time collision detection for virtual surgery. Proc. of Computer Animation. Google Scholar
    20. LUEBKE, D., AND HALLEN, B. 2001. Perceptually driven simplification for interactive rendering. Rendering Techniques; Springer-Verlag. Google Scholar
    21. LUEBKE, D., REDDY, M., COHEN, J., VARSHNEY, A., WATSON, B., AND HUEBNER, R. 2002. Level of Detail for 3D Graphics. Morgan-Kaufmann. Google Scholar
    22. MARK, W., RANDOLPH, S., FINCH, M., VAN VERTH, J., AND TAYLOR II, R. M. 1996. Adding force feedback to graphics systems: Issues and solutions. Proc. of ACM SIGGRAPH, 447–452. Google Scholar
    23. MCNEELY, W., PUTERBAUGH, K., AND TROY, J. 1999. Six degree-of-freedom haptic rendering using voxel sampling. Proc. of ACM SIGGRAPH, 401–408. Google Scholar
    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.Google Scholar
    25. O’SULLIVAN, C., AND DINGLIANA, C. 2001. Collisions and perception. ACM Trans. on Graphics 20, 3, pp. 151–168. Google ScholarDigital Library
    26. OTADUY, M. A., AND LIN, M. C. 2003. CLODs: Dual hierarchies for multiresolution collision detection. UNC Technical Report TR03-013.Google Scholar
    27. PAI, D. K., AND REISSEL, L. M. 1997. Haptic interaction with multiresolution image curves. Computer and Graphics 21, 405–411.Google ScholarCross Ref
    28. REDON, S., KHEDDAR, A., AND COQUILLART, S. 2002. Fast continuous collision detection between rigid bodies. Proc. of Eurographics (Computer Graphics Forum).Google Scholar
    29. RUSPINI, D., KOLAROV, K., AND KHATIB, O. 1997. The haptic display of complex graphical environments. Proc. of ACM SIGGRAPH, 345–352. Google Scholar
    30. SALISBURY, J. K. 1999. Making graphics physically tangible. Communications of the ACM 42, 8. Google ScholarDigital Library
    31. TAUBIN, G. 1995. A signal processing approach to fair surface design. In Proc. of ACM SIGGRAPH, 351–358. Google Scholar

ACM Digital Library Publication: