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

A Ram CHOI; Sung Min KIM; Mee Young SUNG

doi:10.1631/FITEE.1500498

Your Location：

Home >

Browse articles >

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

Regular Papers | Updated：2022-05-19

- Controlling the contact levels of details for fast and precise haptic collision detection
- 一种快速精确触觉碰撞检测中接触细节层次控制方法
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 8, Pages: 1117-1130(2017)
- Affiliations：
  
  Department of Computer Science and Engineering, Incheon National University, Incheon, Korea
- Author bio：
  
  [ "A Ram CHOI, choiaram11@inu.ac.kr" ]
  [ "Sung Min KIM, ksm3656@gmail.com" ]
  Mee Young SUNG, E-mail:mysung@inu.ac.kr
- Funds：
- DOI：10.1631/FITEE.1500498
  CLC： TP391
- Received：31 December 2015，
  
  Revised：2017-;7-;6，
  
  Published：2017-08
- Accepted：
Scan QR Code
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.
DOI：

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. DOI： 10.1631/FITEE.1500498.

摘要

为实现精确稳定的触觉再现，包围体积（球体、轴对称包围盒、定向包围盒或多面体）必须尽可能紧密地填充或覆盖目标对象，来完成交互式触觉应用中的碰撞检测。本文提供了一种方法，用于创建与接触细节层次（contact levels of details

CLOD）相关的包围球体。该球体与目标对象相配合的同时，还能平衡碰撞检测的速度与精确性。所提出的方法主要包括包围球体成形以及两级碰撞检测两部分。进一步说，包围球体成形可分为2步：创建球体和聚类球体；两级碰撞检测也包括2个阶段：球体的快速检测以及精确检测。首先，通过包围球体的创建实现球体碰撞检测中的初始快速探测。一旦探测到碰撞，可通过检查碰撞边界内网格与触觉点的间距来实现更精确的检测效果。为实现这种精细层级的检测，需要定义一种特殊的包围体积数据结构来囊括球体内的全部网格信息。我们通过一系列实现检验了所提出方法的有效性和性能表现，结果表明所提出算法的速度和精确度可以满足触觉仿真的需要。通过球体聚类来保证检测速度，通过基于体素的直接碰撞检测来保证检测精确度。通过基于距离的聚类，所提出的方法在CLOD方面仍保持了其独创性。

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

references

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

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

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

J.L. Bentley . . Multidimensional binary search trees used for associative searching . . Commun. ACM , , 1975 . . 18 ( ( 9 ): ): 509 - - 517 . . DOI: 10.1145/361002.361007 http://doi.org/10.1145/361002.361007 . .

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

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

G. Bradshaw , , , C. O'Sullivan . . Adaptive medial axis approximation for sphere-tree construction . . ACM Trans. Graph. , , 2004 . . 23 ( ( 1 ): ): 1 - - 26 . . DOI: 10.1145/966131.966132 http://doi.org/10.1145/966131.966132 . .

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

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

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

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

J. Goldsmith , , , J. Salmon . . Automatic creation of object hierarchies for ray tracing . . IEEE Comput. Graph. Appl. , , 1987 . . 7 ( ( 5 ): ): 14 - - 20 . . DOI: 10.1109/MCG.1987.276983 http://doi.org/10.1109/MCG.1987.276983 . .

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

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

P.M. Hubbard . . Collision detection for interactive graphics applications . . IEEE Trans. Visual. Comput. Graph. , , 1995 . . 1 ( ( 3 ): ): 218 - - 230 . . DOI: 10.1109/2945.466717 http://doi.org/10.1109/2945.466717 . .

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

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

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

T. Larsson , , , T. Akenine-Mller . . Collision detection for continuously deforming bodies . . Proc. Eurographics , , 2001 . . p.325 - - 333 . . DOI: 10.2312/egs.20011005 http://doi.org/10.2312/egs.20011005 . .

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

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

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

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

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

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

L. Salisbury , , , F. Conti , , , F. Barbagli . . Haptic rendering: introductory concepts . . Comput. Graph. Appl. , , 2004 . . 24 ( ( 2 ): ): 24 - - 32 . . DOI: 10.1109/MCG.2004.1274058 http://doi.org/10.1109/MCG.2004.1274058 . .

H. Samet . . The quadtree and related hierarchical data structures . . ACM Comput. Surv. , , 1984 . . 16 ( ( 2 ): ): 187 - - 260 . . DOI: 10.1145/356924.356930 http://doi.org/10.1145/356924.356930 . .

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

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

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

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

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

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

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

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

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

An anchor-based spectral clustering method

Related Author

Qin ZHANG

Guo-qiang ZHONG

Jun-yu DONG

Related Institution

Department of Computer Science and Technology, Ocean University of China

Science and Information College, Qingdao Agricultural University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰