Article

Minimal hierarchical collision detection

Author:

Gabriel ZachmannAuthors Info & Claims

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

Pages 121 - 128

https://doi.org/10.1145/585740.585761

Published: 11 November 2002 Publication History

Abstract

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 of axis-aligned bounding box trees. In addition to being very memory efficient, it can be constructed efficiently and very fast.We also propose a criterion to be used during the construction of the BV hierarchies is more formally established than previous heuristics. The idea of the argument is general and can be applied to other bounding volume hierarchies as well. Furthermore, we describe a general optimization technique that can be applied to most hierarchical collision detection algorithms.Finally, we describe several box overlap tests that exploit the special features of our new BV hierarchy. These are compared experimentally among each other and with the DOP tree using a benchmark suite of real-world CAD data.

References

[1]

P. K. Agarwal, J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang. Deformable free space tiling for kinetic collision detection. In Proc. 4th Workshop Algorithmic Found. Robot., 2000. To appear.]]

[2]

J. Avro and D. Kirk. A survey of ray tracing acceleration techniques. In A. Glassner, editor, An Introduction to Ray Tracing, pages 201--262. Academic Press, San Diego, CA, 1989.]]

Digital Library

[3]

G. Barequet, B. Chazelle, L. J. Guibas, J. S. B. Mitchell, and A. Tal. BOXTREE: A hierarchical representation for surfaces in 3D. Computer Graphics Forum, 15(3):C387--C396, C484, Sept. 1996.]]

[4]

N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The RΩ-tree: An efficient and robust access method for points and rectangles. In Proc. ACM SIGMOD Conf. on Management of Data, pages 322--331, 1990.]]

Digital Library

[5]

M. Dickerson, C. Duncan, and M. Goodrich. K-D trees are better when cut on the longest side. In LNCS 1879, ESA 2000, pages 179--190, 2000.]]

Digital Library

[6]

J. Eckstein and E. Schömer. Dynamic collision detection in virtual reality applications. In Proc. The 7-th International Conference in Central Europe on Computer Graphics, Visualization, and Interactive Digital Media '99 (WSCG'99), pages 71--78, Plzen, Czech Republic, Feb. 1999. University of West Bohemia.]]

[7]

S. A. Ehmann and M. C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition. In Computer Graphics Forum, volume 20, pages 500--510, 2001. ISSN 1067-7055.]]

[8]

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

[9]

B. Geiger. Real-time collision detection and response for complex environments. In Computer Graphics International, Geneva, Switzerland, June 19--23 2000.]]

Digital Library

[10]

J. Goldsmith and J. Salmon. Automatic creation of object hierarchies for ray tracing. IEEE Computer Graphics and Applications, 7(5):14--20, May 1987.]]

Digital Library

[11]

S. Gottschalk, M. Lin, and D. Manocha. OBB-Tree: A hierarchical structure for rapid interference detection. In H. Rushmeier, editor, SIGGRAPH 96 Conference Proceedings, Annual Conference Series, pages 171--180. ACM SIGGRAPH, Addison Wesley, Aug. 1996. held in New Orleans, Louisiana, 04--09 August 1996.]]

Digital Library

[12]

P. M. Hubbard. Real-time collision detection and time-critical computing. In SIVE 95, The First Worjshop on Simulation and Interaction in Virtual Environments, number 1, pages 92--96, Iowa City, Iowa, July 1995. University of Iowa, informal proceedings.]]

[13]

S. Huh, D. N. Metaxas, and N. I. Badler. Collision resolutions in cloth simulation. In IEEE Computer Animation Conf., Seoul, Korea, Nov.2001.]]

[14]

J. T. Klosowski, M. Held, J. S. 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, Jan. 1998.]]

Digital Library

[15]

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

[16]

W. A. McNeely, K. D. Puterbaugh, and J. J. Troy. Six degrees-of-freedom haptic rendering using voxel sampling. Proceedings of SIGGRAPH 99, pages 401--408, August 1999. ISBN 0-20148-560-5. Held in Los Angeles, California.]]

Digital Library

[17]

I. J. Palmer and R. L. Grimsdale. Collision detection for animation using sphere-trees. Computer Graphics Forum, 14(2):105--116, June 1995.]]

[18]

F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 3rd edition, Oct. 1990.]]

Digital Library

[19]

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

[20]

G. Zachmann. Real-time and exact collision detection for interactive virtual prototyping. In Proc. of the 1997 ASME Design Engineering Technical Conferences, Sacramento, California, Sept. 1997. Paper no. CIE-4306.]]

[21]

G. Zachmann. Rapid collision detection by dynamically aligned DOP-trees. In Proc. of IEEE Virtual Reality Annual International Symposium; VRAIS '98, pages 90--97, Atlanta, Georgia, Mar. 1998.]]

Digital Library

Cited By

Lan LLu ZLong JYuan CLi XHe XWang HJiang CYang Y(2024)Efficient GPU Cloth Simulation with Non-distance Barriers and Subspace ReuseACM Transactions on Graphics10.1145/368776043:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687760
Gargano Ivon Ellenrieder KVivolo M(2024)A Survey of Trajectory Planning Algorithms for Off-Road Uncrewed Ground VehiclesModelling and Simulation for Autonomous Systems10.1007/978-3-031-71397-2_8(120-148)Online publication date: 25-Oct-2024
https://doi.org/10.1007/978-3-031-71397-2_8
Li JZhou XGu LZhang YDu JLin CWang YLin HWang T(2023)The cutting path planning of main components in China initiative accelerator driven subcritical system based on the quantum evolutionary algorithmNuclear Engineering and Design10.1016/j.nucengdes.2023.112332408(112332)Online publication date: Jul-2023
https://doi.org/10.1016/j.nucengdes.2023.112332
Show More Cited By

Index Terms

Minimal hierarchical collision detection
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

OBBTree: a hierarchical structure for rapid interference detection
SIGGRAPH '96: Proceedings of the 23rd annual conference on Computer graphics and interactive techniques

We present a data structure and an algorithm for efficient and exact interference detection amongst complex models undergoing rigid motion. The algorithm is applicable to all general polygonal models. It pre-computes a hierarchical representation of ...
Time-critical collision detection using an average-case approach
VRST '03: Proceedings of the ACM symposium on Virtual reality software and technology

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2002

232 pages

ISBN:1581135300

DOI:10.1145/585740

Conference Chairs:
Jiaoying Shi
Zhejiang University, China
,
Larry Hodges
Georgia Institute of Technology, USA
,
Program Chairs:
Hanqiu Sun
The Chinese University of Hong Kong, HK
,
Qunsheng Peng
Zhejiang University, China

Copyright © 2002 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: 11 November 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

VRST02

Sponsor:

VRST02: The ACM Symposium on Virtual Reality Software and Technology 2002

November 11 - 13, 2002

Hong Kong, China

Acceptance Rates

VRST '02 Paper Acceptance Rate 26 of 105 submissions, 25%;

Overall Acceptance Rate 66 of 254 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
1,348
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lan LLu ZLong JYuan CLi XHe XWang HJiang CYang Y(2024)Efficient GPU Cloth Simulation with Non-distance Barriers and Subspace ReuseACM Transactions on Graphics10.1145/368776043:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687760
Gargano Ivon Ellenrieder KVivolo M(2024)A Survey of Trajectory Planning Algorithms for Off-Road Uncrewed Ground VehiclesModelling and Simulation for Autonomous Systems10.1007/978-3-031-71397-2_8(120-148)Online publication date: 25-Oct-2024
https://doi.org/10.1007/978-3-031-71397-2_8
Li JZhou XGu LZhang YDu JLin CWang YLin HWang T(2023)The cutting path planning of main components in China initiative accelerator driven subcritical system based on the quantum evolutionary algorithmNuclear Engineering and Design10.1016/j.nucengdes.2023.112332408(112332)Online publication date: Jul-2023
https://doi.org/10.1016/j.nucengdes.2023.112332
Lan LKaufman DLi MJiang CYang Y(2022)Affine body dynamicsACM Transactions on Graphics10.1145/3528223.353006441:4(1-14)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530064
Chiroiu VMunteanu LRugină CNedelcu N(2021)Modeling of the Flexible Needle Insertion into the Human LiverBiomedical Signal and Image Processing10.5772/intechopen.96012Online publication date: 14-Apr-2021
https://doi.org/10.5772/intechopen.96012
Rosskamp JMeißenhelter HWeller RRüdel MGanser JZachmann G(2021)UnrealHaptics: Plugins for Advanced VR Interactions in Modern Game EnginesFrontiers in Virtual Reality10.3389/frvir.2021.6404702Online publication date: 16-Apr-2021
https://doi.org/10.3389/frvir.2021.640470
Lan LYang YKaufman DYao JLi MJiang C(2021)Medial IPCACM Transactions on Graphics10.1145/3450626.345975340:4(1-16)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459753
Meister DOgaki SBenthin CDoyle MGuthe MBittner J(2021)A Survey on Bounding Volume Hierarchies for Ray TracingComputer Graphics Forum10.1111/cgf.14266240:2(683-712)Online publication date: 4-Jun-2021
https://doi.org/10.1111/cgf.142662
Chiroiu VNedelcu NPisla DMunteanu LRugină C(2021)On the flexible needle insertion into the human liverScientific Reports10.1038/s41598-021-89479-811:1Online publication date: 13-May-2021
https://doi.org/10.1038/s41598-021-89479-8
Golitsyn DKorzun ARyabkov O(2021)CUDA Implementation of an Algorithm for Batch Mode Detection of CollisionsParallel Computational Technologies10.1007/978-3-030-81691-9_9(118-133)Online publication date: 9-Jul-2021
https://doi.org/10.1007/978-3-030-81691-9_9
Show More Cited By

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.

Media

Figures

Other

Tables

View Table of Contents