skip to main content
10.1145/1180495.1180556acmconferencesArticle/Chapter ViewAbstractPublication PagesvrstConference Proceedingsconference-collections
Article

A framework for bounded-time collision detection in haptic interactions

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.
[2]
F. Aurenhammer. Voronoi diagrams: a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR), 23(3):345--405, 1991.
[3]
D. Badouel. An efficient ray-polygon intersection. Graphics gems table of contents, pages 390--393, 1990.
[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.
[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.
[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.
[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.
[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.
[16]
N. Govindaraju, M. Lin, and D. Manocha. Fast and reliable collision detection using graphics hardware. Proc. of ACM VRST, pages 2--9, 2004.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[32]
T. Möller and B. Trumbore. Fast, minimum storage ray-triangle intersection. Journal of Graphics Tools, 2(1):21--28, 1997.
[33]
B. Naylor, J. Amanatides, and W. Thibault. Merging bsp trees yield polyhedral modeling results. Proc. of ACM Siggraph, pages 115--124, 1990.
[34]
M. Overmars. Point location in fat subdivisions. Information Processing Letters, 44(5):261--265, 1992.
[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.
[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.

Cited By

View all
  • (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
  • (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
  • (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
  • Show More Cited By

Index Terms

  1. A framework for bounded-time collision detection in haptic interactions

    Recommendations

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

    Check for updates

    Author Tags

    1. V-GRAPH
    2. Voronoi
    3. bounded time
    4. collision detection
    5. haptic

    Qualifiers

    • Article

    Conference

    VRST06

    Acceptance Rates

    Overall Acceptance Rate 66 of 254 submissions, 26%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)4
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 18 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (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
    • (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
    • (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
    • (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
    • (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
    • (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

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media