Article

A framework for bounded-time collision detection in haptic interactions

Authors:

Maurizio de Pascale,

Domenico PrattichizzoAuthors Info & Claims

VRST '06: Proceedings of the ACM symposium on Virtual reality software and technology

Pages 305 - 311

https://doi.org/10.1145/1180495.1180556

Published: 01 November 2006 Publication History

Abstract

In this paper we present the V-GRAPH, a framework for bounded-time collision detection for point-like haptic interactions. This frame-work employs strategies similar to those used by the Lin-Canny and Dobkin-Kirkpatrick algorithms but, differently from these ones, it uses a partition of the space focused on vertices only, which al-lows both for an easier implementation and for usage with non-convex objects without the need for splitting the original mesh. In a preprocessing phase the mesh is analyzed to extract neighboring information based on Voronoi theory, then this data is used at run-time in a greedy visit exploiting motion coherence to achieve fast proximity queries. Finally standard segment-triangle intersection tests are eventually carried out to identify the exact point of collision. Moreover the framework can be easily extended to multiple levels of detail. Computational analysis and experimental results show that execution times are independent from mesh complexity, achieving same running times even on models composed by mil-lions of polygons. These features make it particularly suited for virtual museum and digital sculpting applications. Implementation is straightforward and freely available tools can be used for pre-processing.

References

[1]

J. Arvo and D. Kirk. A survey of ray tracing acceleration techniques. An introduction to ray tracing table of contents, pages 201--262, 1989.

Digital Library

[2]

F. Aurenhammer. Voronoi diagrams: a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR), 23(3):345--405, 1991.

Digital Library

[3]

D. Badouel. An efficient ray-polygon intersection. Graphics gems table of contents, pages 390--393, 1990.

Digital Library

[4]

D. Baraff. Curved surfaces and coherence for non-penetrating rigid body simulation. Proceedings of the 17th annual conference on Computer graphics and interactive techniques, pages 19--28, 1990.

Digital Library

[5]

G. Barequet, B. Chazelle, L. Guibas, J. Mitchell, and A. Tal. BOXTREE: A Hierarchical Representation for Surfaces in 3D. Computer Graphics Forum, 15(3):387--396, 1996.

[6]

N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. Proceedings of the 1990 ACM SIGMOD international conference on Management of data, pages 322--331, 1990.

Digital Library

[7]

D. Borro, A. Garcia-Alonso, and L. Matey. Approximation of Optimal Voxel Size for Collision Detection in Maintainability Simulations within Massive Virtual Environments. Computer Graphics Forum, 23(1):13--23, 2004.

[8]

S. Cameron. Approximation hierarchies and S-bounds. Proc. of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, pages 129--137, 1991.

Digital Library

[9]

S. Cameron. Enhancing GJK: computing minimum and penetration distances between convex polyhedra. Robotics and Automation, 1997. Proceedings., 1997 IEEE International Conference on, 4: 3112--3117, 1997.

[10]

J. Cohen, M. Lin, D. Manocha, and M. Ponamgi. I-COLLIDE: an interactive and exact collision detection system for large-scale environments. Proceedings of the 1995 symposium on Interactive 3D graphics, 1995.

Digital Library

[11]

M. De Pascale and D. Prattichizzo. The Haptik Library, a Component Architecture for Uniform Access to Haptic Devices. Robotics and Automation Magazine 2006. In Press.

[12]

S. Ehmann and M. Lin. Accelerated proximity queries between convex polyhedra bymulti-level Voronoi marching. Intelligent Robots and Systems, 2000.(IROS 2000). Proc. 2000 IEEE/RSJ International Conference on, 3, 2000.

[13]

Geometry Center. Qhull. www.qhull.org.

[14]

E. Gilbert, D. Johnson, and S. Keerthi. A fast procedure for computing the distance between complex objects in three-dimensional space. Robotics and Automation, IEEE Journal of {see also IEEE Transactions on Robotics and Automation}, 4(2): 193--203, 1988.

[15]

S. Gottschalk, M. Lin, and D. Manocha. OBBTree: a hierarchical structure for rapid interference detection. Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pages 171--180, 1996.

Digital Library

[16]

N. Govindaraju, M. Lin, and D. Manocha. Fast and reliable collision detection using graphics hardware. Proc. of ACM VRST, pages 2--9, 2004.

Digital Library

[17]

N. Govindaraju, S. Redon, M. Lin, and D. Manocha. CULLIDE: interactive collision detection between complex models in large environments using graphics hardware. Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, pages 25--32, 2003.

Digital Library

[18]

A. Gregory, M. Lin, S. Gottschalk, and R. Taylor. A framework for fast and accurate collision detection for hapticinteraction. Virtual Reality, 1999. Proceedings., IEEE, pages 38--45, 1999.

Digital Library

[19]

L. Guibas, D. Hsu, and L. Zhang. H-Walk: hierarchical distance computation for moving convex bodies. Proceedings of the fifteenth annual symposium on Computational geometry, pp. 265--273, 1999.

Digital Library

[20]

B. Heidelberger, M. Teschner, and M. Gross. Real-time volumetric intersections of deforming objects. Proc. of Vision, Modeling, Visualization VMV03, pp. 461--468, 2003.

[21]

M. Held, J. Klosowski, and J. Mitchell. Evaluation of collision detection methods for virtual reality fly-throughs. Proc. 7th Canad. Conf. Comput. Geom, pp. 205--210, 1995.

[22]

P. Hubbard. Interactive collision detection. Virtual Reality, 1993. Proceedings., IEEE 1993 Symposium on Research Frontiers in, pages 24--31, 1993.

[23]

P. Jimenez, F. Thomas, and C. Torras. 3D collision detection: a survey. Computers and Graphics, 25(2):269--285, 2001.

[24]

Y. Kim, M. Otaduy, M. Lin, and D. Manocha. Fast penetration depth computation using rasterization hardware and hierarchical refinement. Proc. of Workshop on Algorithmic Foundations of Robotics, 3, 2002.

Digital Library

[25]

J. Klosowski, M. Held, J. Mitchell, H. Sowizral, and K. Zikan. Efficient collision detection using bounding volume hierarchies of k-DOPs. Visualization and Computer Graphics, IEEE Transactions on, 4(1):21--36, 1998.

Digital Library

[26]

D. Knott and D. Pai. Cinder: Collision and interference detection in real-time using graphics hardware. Proc. of Graphics Interface, pages 73--80, 2003.

[27]

H. Konig and T. Strothotte. Fast Collision Detection for Haptic Displays Using Polygonal Models. Proceedings of the Conference on Simulation and Visualization, 300, 2002.

[28]

S. Krishnan, A. Pattekar, M. Lin, and D. Manocha. Spherical shell: a higher order bounding volume for fast proximity queries. Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics: the algorithmic perspective: the algorithmic perspective table of contents, pages 177--190, 1998.

Digital Library

[29]

M. Lin and J. Canny. Efficient algorithms for incremental distance computation. IEEE Conference on Robotics and Automation, 10081014, 1991.

[30]

M. Lin and S. Gottschalk. Collision detection between geometric models: A survey. Proc. of IMA Conference on Mathematics of Surfaces, 1:602--608, 1998.

[31]

B. Mirtich. V-Clip: fast and robust polyhedral collision detection. ACM Transactions on Graphics (TOG), 17(3): 177--208, 1998.

Digital Library

[32]

T. Möller and B. Trumbore. Fast, minimum storage ray-triangle intersection. Journal of Graphics Tools, 2(1):21--28, 1997.

Digital Library

[33]

B. Naylor, J. Amanatides, and W. Thibault. Merging bsp trees yield polyhedral modeling results. Proc. of ACM Siggraph, pages 115--124, 1990.

Digital Library

[34]

M. Overmars. Point location in fat subdivisions. Information Processing Letters, 44(5):261--265, 1992.

Digital Library

[35]

S. Quinlan. Efficient distance computation between non-convex objects. Robotics and Automation, 1994. Proceedings., 1994 IEEE International Conference on, pages 3324--3329, 1994.

[36]

S. Redon, A. Kheddar, and S. Coquillart. Collision Detection and Augmented Reality: Fast Continuous Collision Detection between Rigid Bodies. Computer Graphics Forum, 21(3):279, 2002.

[37]

H. Samet and R. Webber. Hierarchical data structures and algorithms for computer graphics. I. Fundamentals. Computer Graphics and Applications, IEEE, 8(3):48--68, 1988.

Digital Library

[38]

Scuola Superiore Sant'Anna, Percro Lab. The museum of pure form. www.pureform.org.

[39]

G. van den Bergen. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools, 2(4):1--13, 1998.

Digital Library

Cited By

Zou SXiao HWan HZhou XNakajima MWu EMiyata KThalmann DHuang Z(2009)Vision-based hand interaction and its application in pervasive gamesProceedings of the 8th International Conference on Virtual Reality Continuum and its Applications in Industry10.1145/1670252.1670286(157-162)Online publication date: 14-Dec-2009
https://dl.acm.org/doi/10.1145/1670252.1670286
Wan HHan XZhou ZRahardja SWu EThalmann DHuang Z(2008)Haptic rendering of complex objects via directional samplingProceedings of The 7th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and Its Applications in Industry10.1145/1477862.1477889(1-7)Online publication date: 8-Dec-2008
https://dl.acm.org/doi/10.1145/1477862.1477889
El-Far NGeorganas NEl Saddik A(2008)An algorithm for haptically rendering objects described by point clouds2008 Canadian Conference on Electrical and Computer Engineering10.1109/CCECE.2008.4564780(001443-001448)Online publication date: May-2008
https://doi.org/10.1109/CCECE.2008.4564780
Show More Cited By

Index Terms

A framework for bounded-time collision detection in haptic interactions
1. Computing methodologies
  1. Computer graphics
    1. Graphics systems and interfaces
      1. Graphics file formats

Recommendations

Localized delaunay refinement for piecewise-smooth complexes
SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometry

Delaunay refinement, a versatile method of mesh generation, is plagued by memory thrashing when required to generate large output meshes. To address this space issue, a localized version of Delaunay refinement was proposed for generating meshes for ...
Quality Triangulations with Locally Optimal Steiner Points

We propose two novel ideas to improve the performance of Delaunay refinement algorithms which are used for computing quality triangulations. The first idea is an effective use of the Voronoi diagram and unifies previously suggested Steiner point ...
VoroCrust: Voronoi Meshing Without Clipping

Polyhedral meshes are increasingly becoming an attractive option with particular advantages over traditional meshes for certain applications.

What has been missing is a robust polyhedral meshing algorithm that can handle broad classes of domains ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

VRST '06: Proceedings of the ACM symposium on Virtual reality software and technology

November 2006

400 pages

ISBN:1595933212

DOI:10.1145/1180495

General Chairs:
Mel Slater
ICREA & UCL, UK
,
Yoshifumi Kitamura
Osaka University, Japan
,
Program Chairs:
Ayellet Tal
Technion, Israel
,
Angelos Amditis
ICCS-NTUA, Greece
,
Yiorgos Chrysanthou
University of Cyprus, Cyprus

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

VRST06

Sponsor:

VRST06: The ACM Symposium on Virtual Reality Software and Technology 2006

November 1 - 3, 2006

Limassol, Cyprus

Acceptance Rates

Overall Acceptance Rate 66 of 254 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
393
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zou SXiao HWan HZhou XNakajima MWu EMiyata KThalmann DHuang Z(2009)Vision-based hand interaction and its application in pervasive gamesProceedings of the 8th International Conference on Virtual Reality Continuum and its Applications in Industry10.1145/1670252.1670286(157-162)Online publication date: 14-Dec-2009
https://dl.acm.org/doi/10.1145/1670252.1670286
Wan HHan XZhou ZRahardja SWu EThalmann DHuang Z(2008)Haptic rendering of complex objects via directional samplingProceedings of The 7th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and Its Applications in Industry10.1145/1477862.1477889(1-7)Online publication date: 8-Dec-2008
https://dl.acm.org/doi/10.1145/1477862.1477889
El-Far NGeorganas NEl Saddik A(2008)An algorithm for haptically rendering objects described by point clouds2008 Canadian Conference on Electrical and Computer Engineering10.1109/CCECE.2008.4564780(001443-001448)Online publication date: May-2008
https://doi.org/10.1109/CCECE.2008.4564780
El-Far NGeorganas NEl-Saddik A(2007)A Collision Detection Algorithm for Point-Like Haptic Interactions in Highly Detailed Virtual Environments2007 IEEE Symposium on Virtual Environments, Human-Computer Interfaces and Measurement Systems10.1109/VECIMS.2007.4373922(25-30)Online publication date: Jun-2007
https://doi.org/10.1109/VECIMS.2007.4373922
Casalicchio EGalli ETucci S(2007)Federated Agent-based Modeling and Simulation Approach to Study Interdependencies in IT Critical InfrastructuresProceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications10.1109/DS-RT.2007.29(182-189)Online publication date: 22-Oct-2007
https://dl.acm.org/doi/10.1109/DS-RT.2007.29
El-Far NGeorganas NSaddik A(2007)Collision Detection and Force Response in Highly-Detailed Point-Based Hapto-Visual Virtual EnvironmentsProceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications10.1109/DS-RT.2007.17(15-22)Online publication date: 22-Oct-2007
https://dl.acm.org/doi/10.1109/DS-RT.2007.17

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten