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

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