Article

Time-critical collision detection using an average-case approach

Authors:

Gabriel ZachmannAuthors Info & Claims

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

Pages 22 - 31

https://doi.org/10.1145/1008653.1008660

Published: 01 October 2003 Publication History

Abstract

We present a novel, generic framework and algorithm for hierarchical collision detection, which allows an application to balance speed and quality of the collision detection.We pursue an average-case approach that yields a numerical measure of the quality. This can either be specified by the simulation or interaction, or it can help to assess the result of the collision detection in a time-critical system.Conceptually, we consider sets of polygons during traversal and estimate probabilities that there is an intersection among these sets. This can be done efficiently by storing characteristics about the average distribution of the set of polygons with each node in a bounding volume hierarchy (BVH). Consequently, we neither need any polygon intersection tests nor access to any polygons during the collision detection process.Our approach can be applied to virtually any BVH. Therefore, we call a BVH that has been augmented in this way an average-distribution tree or ADB-tree.We have implemented our new approach with two basic BVHs and present performance measurements and comparisons with a very fast previous algorithm, namely the DOP-tree. The results show a speedup of about a factor 3 to 6 with only approximately 4% error.

References

[1]

P. K. Agarwal, J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang. Deformable free space tiling for kinetic collision detection. In Algorithmic and Computational Robotics: New Directions (Proc. 5th Workshop Algorithmic Found. Robotics), pages 83--96, 2001.

[2]

P. K. Agarwal, M. de Berg, J. Gudmundsson, M. Hammar, and H. J. Haverkort. Box-trees and R-trees with near-optimal query time. In Proc. Seventeenth Annual Symposium on Computational Geometry (SCG 2001), pages 124--133, 2001.

Digital Library

[3]

S. Ar, B. Chazelle, and A. Tal. Self-customized BSP trees for collision detection. Computational Geometry: Theory and Applications, 15(1--3):91--102, 2000.

Digital Library

[4]

S. Ar, G. Montag, and A. Tal. Deferred, self-organizing BSP trees. In Eurographics, pages 269--278, 2002.

[5]

G. Baciu and W. Sai-Keung Wong. Hardware-assisted self-collision for deformable surfaces. In Proc. VRST 2002, pages 129--136, Hong Kong, China, 2002.

Digital Library

[6]

G. Baciu and W. Sai-Keung Wong. Image-based techniques in a hybrid collision detector. IEEE Transactions on Visualization and Computer Graphics, 9(2):254--271, 2003.

Digital Library

[7]

W. Barth and E. Huber. Computations with tight bounding volumes for general parametric surfaces. In Proc. 15th European Workshop on Computational Geometry (CG 1999), pages 123--126, 1999.

[8]

R. Barzel, J. Hughes, and D. N. Wood. Plausible motion simulation for computer graphics animation. In Proc. Eurographics Workshop Computer Animation and Simulation, pages 183--197, 1996.

Digital Library

[9]

J. Dingliana and C. O'Sullivan. Graceful degradation of collision handling in physically based animation. Proc. Eurographics 2000, 19(3):239--247, 2000.

[10]

S. A. Ehmann and M. C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Proc. Eurographics 2001, 20(3):500--510, 2001.

[11]

S. Fisher and M. Lin. Fast penetration depth estimation for elastic bodies using deformed distance fields. In Proc. International Conf. on Intelligent Robots and Systems (IROS), 2001.

[12]

S. Gottschalk, M. Lin, and D. Manocha. OBB-Tree: A hierarchical structure for rapid interference detection. In SIGGRAPH 1996 Conference Proc., pages 171--180, 1996.

Digital Library

[13]

P. M. Hubbard. Approximating polyhedra with spheres for time-critical collision detection. ACM Transactions on Graphics, 15(3):179--210, 1996.

Digital Library

[14]

S. Huh, D. N. Metaxas, and N. I. Badler. Collision resolutions in cloth simulation. In IEEE Computer Animation Conf., pages 122--127, Seoul, Korea, 2001.

[15]

Y. Kitamura, A. Smith, H. Takemura, and F. Kishino. A real-time algorithm for accurate collision detection for deformable polyhedral objects. Presence, 7(1):36--52, 1998.

Digital Library

[16]

J. Klein, J. Krokowski, M. Fischer, M. Wand, R. Wanka, and F. Meyer auf der Heide. The randomized sample tree: A data structure for interactive walkthroughs in externally stored virtual environments. In Proc. VRST 2002, pages 137--146, Hong Kong, China, 2002.

Digital Library

[17]

J. Klein and G. Zachmann. Controlling the error of time-critical collision detection using ADB-trees. Tech. Rep. tr-ri-03-242, Institute of Computer Science, University of Paderborn, 2003. http://www.upb.de/cs/janklein.

[18]

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

Digital Library

[19]

T. Larsson and T. Akenine-Möller. Collision detection for continuously deforming bodies. In Eurographics, pages 325--333, 2001. short presentation.

[20]

R. W. H. Lau, O. Chan, M. Luk, and F. W. B. Li. A collision detection method for deformable objects. In Proc. VRST 2002, pages 113--120, 2002.

Digital Library

[21]

J.-C. Lombardo, M.-P. Cani, and F. Neyret. Real-time collision detection for virtual surgery. In Proc. of Computer Animation, pages 82--90, Geneva, Switzerland, 1999.

Digital Library

[22]

W. A. McNeely, K. D. Puterbaugh, and J. J. Troy. Six degrees-of-freedom haptic rendering using voxel sampling. In SIGGRAPH 1999 Conference Proc., pages 401--408, 1999.

Digital Library

[23]

K. Myszkowski, O. G. Okunev, and T. L. Kunii. Fast collision detection between complex solids using rasterizing graphics hardware. The Visual Computer, 11(9):497--512, 1995.

[24]

C. O'Sullivan, R. Radach, and S. Collins. A model of collision perception for real-time animation. In Proc. 1999 Conference on Computer Animation and Simulation - Eurographics Workshop (EGCAS 1999), pages 67--76, 1999.

[25]

I. J. Palmer and R. L. Grimsdale. Collision detection for animation using sphere-trees. Proc. Eurographics 1995, 14(2):105--116, 1995.

[26]

M. Shinya and M.-C. Forgue. Interference detection through rasterization. The Journal of Visualization and Computer Animation, 2(4):132--134, 1991.

[27]

S. Uno and M. Slater. The sensitivity of presence to collision response. In Proc. VRAIS, page 95, Albuquerque, New Mexico, 1997.

Digital Library

[28]

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

Digital Library

[29]

M. Wand, M. Fischer, I. Peter, F. Meyer auf der Heide, and W. Straßer. The randomized z-buffer algorithm: Interactive rendering of highly complex scenes. In SIGGRAPH 2001 Conference Proc., pages 361--370, 2001.

Digital Library

[30]

G. Zachmann. Rapid collision detection by dynamically aligned DOP-trees. In Proc. VRAIS 1998, pages 90--97, Atlanta, Georgia, 1998.

Digital Library

[31]

G. Zachmann. Minimal hierarchical collision detection. In Proc. VRST 2002, pages 121--128, Hong Kong, China, 2002.

Digital Library

Cited By

Weller RWeller R(2013)Evaluation and Analysis of Collision Detection AlgorithmsNew Geometric Data Structures for Collision Detection and Haptics10.1007/978-3-319-01020-5_6(147-192)Online publication date: 2013
https://doi.org/10.1007/978-3-319-01020-5_6
Zachmann G(2011)Collision DetectionVirtual Technologies for Business and Industrial Applications10.4018/978-1-61520-631-5.ch003(36-67)Online publication date: 2011
https://doi.org/10.4018/978-1-61520-631-5.ch003
Zhang TChen XZhang J(2011)Research on the key technology of virtual hysteroscopy laparoscopy surgery simulator system2011 International Conference on Computational Problem-Solving (ICCP)10.1109/ICCPS.2011.6092300(1-5)Online publication date: Oct-2011
https://doi.org/10.1109/ICCPS.2011.6092300
Show More Cited By

Index Terms

Time-critical collision detection using an average-case approach

Recommendations

Minimal hierarchical collision detection
VRST '02: Proceedings of the ACM symposium on Virtual reality software and technology

We present a novel bounding volume hierarchy that allows for extremely small data structure sizes while still performing collision detection as fast as other classical hierarchical algorithms in most cases. The hierarchical data structure is a variation ...
Hierarchical partitioning for field-programmable systems
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design

This paper presents a new recursive bipartitioning algorithm for a hierarchical field-programmable system. It draws new insights into relating the quality of the bipartitioning algorithm to circuit structures by the use of the partitioning tree (Hagen ...
Load-balancing spatially located computations using rectangular partitions

Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

October 2003

235 pages

ISBN:1581135696

DOI:10.1145/1008653

Copyright © 2003 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 October 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

VRST03

Sponsor:

VRST03: The ACM Symposium on Virtual Reality Software and Technology 2003

October 1 - 3, 2003

Osaka, Japan

Acceptance Rates

VRST '03 Paper Acceptance Rate 28 of 81 submissions, 35%;

Overall Acceptance Rate 66 of 254 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
647
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Weller RWeller R(2013)Evaluation and Analysis of Collision Detection AlgorithmsNew Geometric Data Structures for Collision Detection and Haptics10.1007/978-3-319-01020-5_6(147-192)Online publication date: 2013
Zachmann G(2011)Collision DetectionVirtual Technologies for Business and Industrial Applications10.4018/978-1-61520-631-5.ch003(36-67)Online publication date: 2011
Zhang TChen XZhang J(2011)Research on the key technology of virtual hysteroscopy laparoscopy surgery simulator system2011 International Conference on Computational Problem-Solving (ICCP)10.1109/ICCPS.2011.6092300(1-5)Online publication date: Oct-2011
Gissler MSchmedding RTeschner M(2009)Time‐critical collision handling for deformable modelingComputer Animation and Virtual Worlds10.1002/cav.29820:2-3(355-364)Online publication date: 5-May-2009
Zachmann G(2008)Collision Detection as a Fundamental Technology in VR Based Product EngineeringProduct Engineering10.1007/978-1-4020-8200-9_9(195-230)Online publication date: 2008
Preim BBartz D(2007)Visualization in MedicineundefinedOnline publication date: 21-Jun-2007
Weller RKlein JZachmann G(2006)A model for the expected running time of collision detection using AABBs treesProceedings of the 12th Eurographics conference on Virtual Environments10.5555/2386021.2386023(11-17)Online publication date: 8-May-2006
Dochev VVassilev TSpanlang BBoyanov K(2004)Image-space based collision detection in cloth simulation on walking humansProceedings of the 5th international conference on Computer systems and technologies10.1145/1050330.1050377(1-6)Online publication date: 17-Jun-2004
Klein JZachmann G(2004)Point Cloud Collision DetectionComputer Graphics Forum10.1111/j.1467-8659.2004.00788.x23:3(567-576)Online publication date: 27-Aug-2004

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