Full Text:   <1730>

Summary:  <1408>

CLC number: TP391

On-line Access: 2017-09-08

Received: 2015-12-31

Revision Accepted: 2016-05-30

Crosschecked: 2017-07-06

Cited: 0

Clicked: 5855

Citations:  Bibtex RefMan EndNote GB/T7714


Mee Young Sung


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2017 Vol.18 No.8 P.1117-1130


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

Author(s):  A Ram Choi, Sung Min Kim, Mee Young Sung

Affiliation(s):  Department of Computer Science and Engineering, Incheon National University, Incheon, Korea

Corresponding email(s):   choiaram11@inu.ac.kr, ksm3656@gmail.com, mysung@inu.ac.kr

Key Words:  Collision detection, Haptic rendering, Bounding sphere, Clustering, Contact levels of details (CLOD)

A Ram Choi, Sung Min Kim, Mee Young Sung. Controlling the contact levels of details for fast and precise haptic collision detection[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(8): 1117-1130.

@article{title="Controlling the contact levels of details for fast and precise haptic collision detection",
author="A Ram Choi, Sung Min Kim, Mee Young Sung",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Controlling the contact levels of details for fast and precise haptic collision detection
%A A Ram Choi
%A Sung Min Kim
%A Mee Young Sung
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 8
%P 1117-1130
%@ 2095-9184
%D 2017
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1500498

T1 - Controlling the contact levels of details for fast and precise haptic collision detection
A1 - A Ram Choi
A1 - Sung Min Kim
A1 - Mee Young Sung
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 8
SP - 1117
EP - 1130
%@ 2095-9184
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1500498

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.


概要:为实现精确稳定的触觉再现,包围体积(球体、轴对称包围盒、定向包围盒或多面体)必须尽可能紧密地填充或覆盖目标对象,来完成交互式触觉应用中的碰撞检测。本文提供了一种方法,用于创建与接触细节层次(contact levels of details, CLOD)相关的包围球体。该球体与目标对象相配合的同时,还能平衡碰撞检测的速度与精确性。所提出的方法主要包括包围球体成形以及两级碰撞检测两部分。进一步说,包围球体成形可分为2步:创建球体和聚类球体;两级碰撞检测也包括2个阶段:球体的快速检测以及精确检测。首先,通过包围球体的创建实现球体碰撞检测中的初始快速探测。一旦探测到碰撞,可通过检查碰撞边界内网格与触觉点的间距来实现更精确的检测效果。为实现这种精细层级的检测,需要定义一种特殊的包围体积数据结构来囊括球体内的全部网格信息。我们通过一系列实现检验了所提出方法的有效性和性能表现,结果表明所提出算法的速度和精确度可以满足触觉仿真的需要。通过球体聚类来保证检测速度,通过基于体素的直接碰撞检测来保证检测精确度。通过基于距离的聚类,所提出的方法在CLOD方面仍保持了其独创性。


Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[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.

[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.

[3]Beckmann, N., Kriegel, H.P., Schneider, R., et al., 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.

[4]Bentley, J.L., 1975. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509-517.

[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.

[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.

[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.

[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.

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

[12]Goldsmith, J., Salmon, J., 1987. Automatic creation of object hierarchies for ray tracing. IEEE Comput. Graph. Appl., 7(5):14-20.

[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.

[14]Gregory, A., Lin, M.C., Gottschalk, S., et al., 2005. A framework for fast and accurate collision detection for haptic interaction. Proc. ACM SIGGRAPH 2005 Courses, Article 34.

[15]Hubbard, P.M., 1995. Collision detection for interactive graphics applications. IEEE Trans. Visual. Comput. Graph., 1(3):218-230.

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

[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.

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

[19]Larsson, T., Akenine-Möller, T., 2001. Collision detection for continuously deforming bodies. Proc. Eurographics, p.325-333.

[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.

[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.

[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.

[23]Quinlan, S., 1994. Efficient distance computation between non-convex objects. Proc. IEEE Int. Conf. on Robotics and Automation, p.3324-3329.

[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.

[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.

[26]Salisbury, L., Conti, F., Barbagli, F., 2004. Haptic rendering: introductory concepts. Comput. Graph. Appl., 24(2): 24-32.

[27]Samet, H., 1984. The quadtree and related hierarchical data structures. ACM Comput. Surv., 16(2):187-260.

[28]Sibson, R., 1973. SLINK: an optimally efficient algorithm for the single-link cluster method. Comput. J., 16(1):30-34.

[29]Teschner, M., Kimmerle, S., Heidelberger, B., et al., 2005. Collision detection for deformable objects. Comput. Graph. For., 24(1):61-81.

[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.

[31]van den Bergen, G., 1997. Efficient collision detection of complex deformable models using AABB trees. J. Graph. Tools, 2(4):1-13.

[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.

[33]Weller, R., 2013. New Geometric Data Structures for Collision Detection and Haptics. Springer International Publishing, Switzerland.

[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.

[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.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE