| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
SQ-Map: Efficient Layered Collision Detection and Haptic Rendering
January/February 2007 (vol. 13 no. 1)
pp. 80-93
Abstract—This paper presents a novel layered and fast framework for real-time collision detection and haptic interaction in virtual environments based on superquadric virtual object modeling. An efficient algorithm is initially proposed for decomposing the complex objects into subobjects suitable for superquadric modeling, based on visual salience and curvature constraints. The distance between the superquadrics and the mesh is then projected onto the superquadric surface, thus generating a distance map (SQ-Map). Approximate collision detection is then performed by computing the analytical equations and distance maps instead of triangle per triangle intersection tests. Collision response is then calculated directly from the superquadric models and realistic smooth force feedback is obtained using analytical formulae and local smoothing on the distance map. Experimental evaluation demonstrates that SQ-Map reduces significantly the computational cost when compared to accurate collision detection methods and does not require the huge amounts of memory demanded by distance field-based methods. Finally, force feedback is calculated directly from the distance map and the superquadric formulae.
[1] 80 G.C. Burdea and P. Coiffet, Virtual Reality Technology, second ed. Wiley-IEEE Press, 2003.[2] P.M. Hubbard, “Approximating Polyhedra with Spheres for Time-Critical Collision Detection,” ACM Trans. Graphics, vol. 15, no. 3, pp. 179-210, July 1996.[3] S. Gottschalk, M.C. Lin, and D. Manocha, “OBBTree: A Hierarchical Structure for Rapid Interference Detection,” Computer Graphics, Proc. ACM SIGGRAPH, pp. 171-180, 1996.[4] J.T. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, and K. Zikan, “Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs,” IEEE Trans. Visualization and Computer Graphics, vol. 4, no. 1, pp. 21-36, Jan.-Mar. 1998.[5] M.C. Lin and J.F. Canny, “A Fast Algorithm for Incremental Distance Calculation,” Proc. IEEE Int'l Conf. Robotics and Automation, vol. 2, pp. 1008-1014, 1991.[6] G. van den Bergen, “Efficient Collision Detection of Complex Deformable Models Using AABB Trees,” J. Graphics Tools, vol. 2, no. 4, pp. 1-13, Apr. 1997.[7] S.J. Osher and R.P. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag, 2002.[8] A. Fuhrmann, G. Sobottka, and C. Gross, “Distance Fields for Rapid Collision Detection in Physically Based Modeling,” Proc. GraphiCon '03, pp. 58-65, Sept. 2003.[9] M. Teschner, S. Kimmerle, B. Heidelberger, G. Zachmann, L. Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N. Magnenat-Thalmann, W. Strasser, and P. Volino, “Collision Detection for Deformable Objects,” Proc. Eurographics, 2004.[10] S. Osher and J. A. Sethian, “Fronts Propagating with Curvature-Dependent Speed: Algorithms Based on Hamilton-Jacobi Formulations,” J. Computational Physics, vol. 79, no. 1, pp. 12-49, 1988.[11] J.A. Sethian, P.G. Ciarlet, A. Iserles, R.V. Kohn, and M.H. Wright, Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge Univ. Press, 1999.[12] S.F. Frisken, R.N. Perry, A.P. Rockwood, and T.R. Jones, “Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics,” Computer Graphics and Interactive Techniques, pp. 249-254, 2000.[13] W.A. McNeely, K.D. Puterbaugh, and J.J. Troy, “Six Degree-of-Freedom Haptic Rendering Using Voxel Sampling,” Computer Graphics and Interactive Techniques,” pp. 401-408, 1999.[14] F. Solina and R. Bajcsy, “Recovery of Parametric Models from Range Images: The Case for Superquadrics with Global Deformations,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 2, pp. 131-147, Feb. 1990.[15] D.D. Hoffman and M. Singh, “Salience of Visual Parts,” Cognition, vol. 63, pp. 29-78, 1997.[16] H.S. Lin, H.M. Liao, and J. Lin, “Visual Salience-Guided Mesh Decomposition,” Proc. IEEE Int'l Workshop Multimedia Signal Processing (MMSP), 2004.[17] G. Taubin, “Estimating the Tensor of Curvature of a Surface from a Polyhedral Approximation,” Proc. Int'l Conf. Computer Vision, pp. 902-907, 1995.[18] J. Peng, Q. Li, C.C Jay Kuo, and M. Zhou, “Estimating Gaussian Curvatures from 3D Meshes,” Human Vision and Electronic Imaging, Proc. SPIE, pp. 270-280, 2003.[19] M. Do Carmo, Differential Geometry of Curves and Surfaces. Prentice Hall, 1976.[20] D. DeCarlo and D. Metaxas, “Blended Deformable Models,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 4, pp.443-448, Apr. 1996.[21] G.C. Burdea, Force and Touch Feedback for Virtual Reality. Wiley-Interscience Publication, 1996.[22] L. Kim, A. Kyrikou, G. Sukhatme, and M. Desbrun, “An Implicit-Based Haptic Rendering Technique,” Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS '02), 2002.[23] D. Tzovaras, G. Nikolakis, G. Fergadis, S. Malasiotis, and M. Stavrakis, “Design and Implementation of Haptic Virtual Environments for the Training of Visually Impaired,” IEEE Trans. Neural Systems and Rehabilitation Eng., vol. 12, no. 2, pp. 266-278, June 2004.[24] K. Moustakas, D. Tzovaras, and M.G. Strintzis, “Fast Hierarchical Simulation of Cloth and Deformable Objects Using an Optimal Pyramidal Representation,” Proc. Computer Animation and Social Agents Conf. (CASA '04), pp. 163-170, July 2004.[25] M.A. Otaduy, N. Jain, A. Sud, and M.C. Lin, “Haptic Display of Interaction between Textured Models,” Proc. Conf. Visualization (VIS '04), pp. 297-304, 2004.[26] D.C. Ruspini, K. Kolarov, and O. Khatib, “The Haptic Display of Complex Graphical Environments,” Computer Graphics (SIGGRAPH '97 Conf. Proc.), pp. 345-352, 1997.
Index Terms:
Collision detection, haptic rendering, force feedback, collision response, superquadrics.
Citation:
Konstantinos Moustakas, Dimitrios Tzovaras, Michael Gerassimos Strintzis, "SQ-Map: Efficient Layered Collision Detection and Haptic Rendering," IEEE Transactions on Visualization and Computer Graphics, vol. 13, no. 1, pp. 80-93, Jan./Feb. 2007, doi:10.1109/TVCG.2007.20
