Controlling the contact levels of details for fast and precise haptic collision detection

Abstract

For accurate and stable haptic rendering, collision detection for interactive haptic applications has to be done by filling in or covering target objects as tightly as possible with bounding volumes (spheres, axis-aligned bounding boxes, oriented bounding boxes, or polytopes). In this paper, we propose a method for creating bounding spheres with respect to the contact levels of details (CLOD), which can fit objects while maintaining the balance between high speed and precision of collision detection. Our method is composed mainly of two parts: bounding sphere formation and two-level collision detection. To specify further, bounding sphere formation can be divided into two steps: creating spheres and clustering spheres. Two-level collision detection has two stages as well: fast detection of spheres and precise detection in spheres. First, bounding spheres are created for initial fast probing to detect collisions of spheres. Once a collision is probed, a more precise detection is executed by examining the distance between a haptic pointer and each mesh inside the colliding boundaries. To achieve this refined level of detection, a special data structure of a bounding volume needs to be defined to include all mesh information in the sphere. After performing a number of experiments to examine the usefulness and performance of our method, we have concluded that our algorithm is fast and precise enough for haptic simulations. The high speed detection is achieved through the clustering of spheres, while detection precision is realized by voxel-based direct collision detection. Our method retains its originality through the CLOD by distance-based clustering.

Keywords

Collision detection / Haptic rendering / Bounding sphere / Clustering / Contact levels of details (CLOD)

References

[1] Aragón,A.M., Molinari, J.F., 2014. A hierarchical detection framework for computational contact mechanics. Comput. Meth. Appl. Mech. Eng., 268:574–588. https://doi.org/10.1016/j.cma.2013.10.001

[2] Barbič,J., James, D.L., 2008. Six-DoF haptic rendering of contact between geometrically complex reduced deformable models. IEEE Trans. Hapt., 1(1):39–52. https://doi.org/10.1109/TOH.2008.1

[3] Beckmann,N.,Kriegel, H.P., Schneider,R. , , 1990. The R*-tree: an efficient and robust access method for points and rectangles.Proc. ACM SIGMOD Int. Conf. on Management of Data, p.322–331. https://doi.org/10.1145/93597.98741

[4] Bentley,J.L., 1975. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509–517. https://doi.org/10.1145/361002.361007

[5] Blum,H.A., 1967. A transformation for extracting new descriptors of shape. In: Wathen-Dunn, W. (Ed.), Models for the Perception of Speech and Visual Form. MIT Press, Cambridge, p.362–380.

[6] Bradshaw,G., 2003. Sphere-tree Construction Toolkit. http://isg.cs.tcd.ie/spheretree

[7] Bradshaw,G., O’Sullivan, C., 2004. Adaptive medial axis approximation for sphere-tree construction. ACM Trans. Graph., 23(1):1–26. https://doi.org/10.1145/966131.966132

[8] Bridson,R., Fedkiw, R., Anderson,J. , 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph., 21(3):594–603. https://doi.org/10.1145/566570.566623

[9] Colgate,J.E., Brown,J.M., 1994. Factors affecting the Z-width of haptic display. Proc. IEEE Int. Conf. on Robotics and Automation, p.3205–3210. https://doi.org/10.1109/robot.1994.351077

[10] Dey,T.K., Zhao,W.L., 2004. Approximating the medial axis from the Voronoi diagram with a convergence guarantee.Algorithmica, 38(1):179–200. https://doi.org/10.1007/s00453-003-1049-y

[11] Garcia-Alonso,A., Serrano, N., Flaquer,J. , 1994. Solving the collision detection problem. IEEE Comput. Graph. Appl., 14(3):36–43. https://doi.org/10.1109/38.279041

[12] Goldsmith,J., Salmon, J., 1987. Automatic creation of object hierarchies for ray tracing. IEEE Comput. Graph. Appl., 7(5):14–20. https://doi.org/10.1109/MCG.1987.276983

[13] Gottschalk,S., Lin,M.C., Manocha,D., 1996. OBB-tree: a hierarchical structure for rapid interference detection. Proc. 23rd Annual Conf. on Computer Graphics and Interactive Techniques, p.171–180. https://doi.org/10.1145/237170.237244

[14] Gregory,A., Lin,M.C., Gottschalk,S. , , 2005. A framework for fast and accurate collision detection for haptic interaction. Proc. ACM SIGGRAPH 2005 Courses, Article 34. https://doi.org/10.1145/1198555.1198604

[15] Hubbard,P.M., 1995. Collision detection for interactive graphics applications. IEEE Trans. Visual. Comput. Graph., 1(3):218–230. https://doi.org/10.1109/2945.466717

[16] Hubbard,P.M., 1996. Approximating polyhedra with spheres for time-critical collision detection. ACM Trans. Graph., 15(3):179–210. https://doi.org/10.1145/231731.231732

[17] James,D.L., Pai,D.K.,2004. BD-tree: output-sensitive collision detection for reduced deformable model. ACM Trans. Graph., 23(3):393–398. https://doi.org/10.1145/1015706.1015735

[18] Klosowski,J.T., Held,M., Mitchell,J.S.B. , , 1998. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Trans. Visual. Comput. Graph., 4(1):21–36. https://doi.org/10.1109/2945.675649

[19] Larsson,T., Akenine-Mölller, T., 2001. Collision detection for continuously deforming bodies. Proc. Eurographics, p.325–333. https://doi.org/10.2312/egs.20011005

[20] McNeely,W.A., Puterbaugh, K.D., Troy,J.J. , 1999. Six degree-of-freedom haptic rendering using voxel sampling. Proc. 26th Annual Conf. on Computer Graphics and Interactive Techniques, p.401–408. https://doi.org/10.1145/311535.311600

[21] Moore,M., Wilhelms, J., 1988. Collision detection and response for computer animation. Proc. 15th Annual Conf. on Computer Graphics and Interactive Techniques, p.289–298. https://doi.org/10.1145/378456.378528

[22] Otaduy,M.A., Lin,M.C., 2003. CLODs: dual hierarchies for multiresolution collision detection. Proc. Eurographics/ACM SIGGRAPH Symp. on Geometry Processing, p.94–101. https://doi.org/10.2312/SGP/SGP03/094-101

[23] Quinlan,S., 1994. Efficient distance computation between non-convex objects. Proc. IEEE Int. Conf. on Robotics and Automation, p.3324–3329. https://doi.org/10.1109/ROBOT.1994.351059

[24] Roussopoulos,N., Leifker, D., 1985. Direct spatial search on pictorial databases using packed R-trees. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.17–31. https://doi.org/10.1145/318898.318900

[25] Ruspini,D.C., Kolarov, K., Khatib,O. , 1997. The haptic display of complex graphical environments. Proc. 24th Annual Conf. on Computer Graphics and Interactive Techniques, p.345–352.https://doi.org/10.1145/258734.258878

[26] Salisbury,L., Conti,F., Barbagli,F. , 2004. Haptic rendering: introductory concepts. Comput. Graph. Appl., 24(2): 24–32. https://doi.org/10.1109/MCG.2004.1274058

[27] Samet,H., 1984. The quadtree and related hierarchical data structures. ACM Comput. Surv., 16(2):187–260. https://doi.org/10.1145/356924.356930

[28] Sibson,R., 1973. SLINK: an optimally efficient algorithm for the single-link cluster method. Comput. J., 16(1):30–34. https://doi.org/10.1093/comjnl/16.1.30

[29] Teschner,M., Kimmerle, S., Heidelberger,B. , , 2005. Collision detection for deformable objects. Comput. Graph. For., 24(1):61–81. https://doi.org/10.1111/j.1467-8659.2005.00829.x

[30] Thibalt,W.C., Naylor, B.F., 1987. Set operations on polyhedra using binary space partitioning trees. Proc. 14th Annual Conf. on Computer Graphics and Interactive Techniques, p.153–162. https://doi.org/10.1145/37401.37421

[31] van den Bergen,G., 1997. Efficient collision detection of complex deformable models using AABB trees. J. Graph. Tools, 2(4):1–13. https://doi.org/10.1080/10867651.1997.10487480

[32] Vlasov,R., Friese, K.I., Wolter,F.E. , 2013. Haptic rendering of volume data with collision detection guarantee using path finding. LNCS, 7848:212–231. https://doi.org/10.1007/978-3-642-38803-3_12

[33] Weller,R., 2013. New Geometric Data Structures for Collision Detection and Haptics. Springer International Publishing, Switzerland. https://doi.org/10.1007/978-3-319-01020-5

[34] Weller,R., Zachmann, G., 2009. A unified approach for physically-based simulations and haptic rendering. Proc. ACM SIGGRAPH Symp. on Video Games, p.151–159. https://doi.org/10.1145/1581073.1581097

[35] Zeng,D., Zheng,D.Y., 2012. Three-dimensional deformation in curl vector field. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 13(8):565–572. https://doi.org/10.1631/jzus.C1200004

RIGHTS & PERMISSIONS

2017 Zhejiang University and Springer-Verlag GmbH Germany