article

BD-tree: output-sensitive collision detection for reduced deformable models

Authors:

Dinesh K. PaiAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 23, Issue 3

Pages 393 - 398

https://doi.org/10.1145/1015706.1015735

Published: 01 August 2004 Publication History

Abstract

We introduce the Bounded Deformation Tree, or BD-Tree, which can perform collision detection with reduced deformable models at costs comparable to collision detection with rigid objects. Reduced deformable models represent complex deformations as linear superpositions of arbitrary displacement fields, and are used in a variety of applications of interactive computer graphics. The BD-Tree is a bounding sphere hierarchy for output-sensitive collision detection with such models. Its bounding spheres can be updated after deformation in any order, and at a cost independent of the geometric complexity of the model; in fact the cost can be as low as one multiplication and addition per tested sphere, and at most linear in the number of reduced deformation coordinates. We show that the BD-Tree is also extremely simple to implement, and performs well in practice for a variety of real-time and complex off-line deformable simulation examples.

Supplementary Material

MOV File (pps023.mov)

Download
12.29 KB

References

[1]

ALEXA, M., AND MÜLLER, W. 2000. Representing Animations by Principal Components. Computer Graphics Forum 19, 3 (Aug.), 411--418.

[2]

BRADSHAW, G., AND O'SULLIVAN, C. 2004. Adaptive Medial-Axis Approximation for Sphere-Tree Construction. ACM Transactions on Graphics 23, 1, 1--26.

Digital Library

[3]

BRIDSON, R., FEDKIW, R. P., AND ANDERSON, J. 2002. Robust Treatment of Collisions, Contact, and Friction for Cloth Animation. ACM Transactions on Graphics 21, 3 (July), 594--603.

Digital Library

[4]

BROWN, J., SORKIN, S., BRUYNS, C., LATOMBE, J., MONTGOMERY, K., AND STEPHANIDES, M. 2001. Real-Time Simulation of Deformable Objects: Tools and Application. In Proceedings of Computer Animation 2001.

[5]

DEBUNNE, G., DESBRUN, M., CANI, M.-P., AND BARR, A. H. 2001. Dynamic Real-Time Deformations Using Space & Time Adaptive Sampling. In Proc. of ACM SIGGRAPH 2001, 31--36.

Digital Library

[6]

DINGLIANA, J., AND O'SULLIVAN, C. 2000. Graceful Degradation of Collision Handling in Physically Based Animation. Computer Graphics Forum 19, 3 (Aug.), 239--248.

[7]

FALOUTSOS, P., VANDE PANNE, M., AND TERZOPOULOS, D. 1997. Dynamic Free-Form Deformations for Animation Synthesis. IEEE Trans. on Vis. and Comp. Graph. 3, 3, 201--214.

Digital Library

[8]

GANOVELLI, F., DINGLIANA, J., AND O'SULLIVAN, C. 2000. BucketTree: Improving collision detection between deformable objects. In Spring Conference in Computer Graphics (SCCG2000), 156--163.

[9]

GOTTSCHALK, S., LIN, M. C., AND MANOCHA, D. 1996. OBB-Tree: A Hierarchical Structure for Rapid Interference Detection. In Proceedings of ACM SIGGRAPH 96, 171--180.

Digital Library

[10]

GUIBAS, L., NGUYEN, A., RUSSEL, D., AND ZHANG, L. 2002. Collision Detection for Deforming Necklaces. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry, ACM Press, 33--42.

Digital Library

[11]

HUBBARD, P. M. 1995. Collision Detection for Interactive Graphics Applications. IEEE Transactions on Visualization and Computer Graphics 1, 3, 218--230.

Digital Library

[12]

JAMES, D. L., AND PAI, D. K. 1999. ARTDEFO: Accurate Real Time Deformable Objects. In Proceedings of ACM SIGGRAPH 99, Computer Graphics Proceedings, 65--72.

Digital Library

[13]

JAMES, D. L., AND PAI, D. K. 2002. DyRT: Dynamic Response Textures for Real Time Deformation Simulation With Graphics Hardware. ACM Transactions on Graphics 21, 3, 582--585.

Digital Library

[14]

JIMENEZ, P., THOMAS, F., AND TORRAS, C. 2001. 3D Collision Detection: A Survey. Computers and Graphics 25, 2 (Apr.), 269--285.

[15]

LARSSON, T., AND AKENINE-MÖLLER, T. 2001. Collision Detection for Continuously Deforming Bodies. In Eurographics 2001, A. Chalmers and T.-M. Rhyne, Eds., Eurographics, 325--333.

[16]

LARSSON, T., AND AKENINE-MÖLLER, T. 2003. Efficient collision detection for models deformed by morphing. The Visual Computer 19, 2, 164--174.

[17]

LEWIS, J. P., CORDNER, M., AND FONG, N. 2000. Pose Space Deformations: A Unified Approach to Shape Interpolation and Skeleton-Driven Deformation. In Proceedings of ACM SIGGRAPH 2000, 165--172.

Digital Library

[18]

LIN, M. C., AND GOTTSCHALK, S. 1998. Collision detection between geometric models: A survey. In Proc. of IMA Conference on Mathematics of Surfaces, 37--56.

[19]

MANOCHA, D., LIN, M. C., DOGGETT, M., GREENE, N., HOFF, K., KILGARD, M., AND KRISHNAN, S. 2002. Interactive Geometric Computations Using Graphics Hardware. In SIGGRAPH 2002 Course Notes, ACM SIGGRAPH.

[20]

QUINLAN, S. 1994. Efficient Distance Computation between Non-Convex Objects. In IEEE Intern. Conf. on Robotics and Automation, IEEE, 3324--3329.

[21]

VAN DEN BERGEN, G. 1997. Efficient Collision Detection of Complex Deformable Models using AABB Trees. Journal of Graphics Tools 2, 4, 1--14.

Digital Library

[22]

WARREN, J., AND WEIMER, H. 2001. Subdivision Methods for Geometric Design: A Constructive Approach, first ed. Morgan Kaufmann Publishers, October.

Digital Library

[23]

WELZL, E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Comp. Sci., H. Maurer, Ed., vol. 555 of Lecture Notes Comp. Sci. Springer-Verlag, 359--370.

Cited By

Zesch RWitemeyer BXiong ZLevin DSueda S(2024)NBD-Tree: Neural Bounded Deformation Tree for Collision Culling of Deformable ObjectsNext Generation Data Science10.1007/978-3-031-61816-1_6(73-87)Online publication date: 27-Jun-2024
https://doi.org/10.1007/978-3-031-61816-1_6
Dinas SMartínez H(2024)Spheres, AABB, and OOBB as Bounding Volume HierarchiesEncyclopedia of Computer Graphics and Games10.1007/978-3-031-23161-2_392(1736-1740)Online publication date: 5-Jan-2024
https://doi.org/10.1007/978-3-031-23161-2_392
Li XSong SYao JZhang HZhou RHong Q(2023)Efficient collision detection using hybrid medial axis transform and BVH for rigid body simulationGraphical Models10.1016/j.gmod.2023.101180128:COnline publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.gmod.2023.101180
Show More Cited By

Index Terms

BD-tree: output-sensitive collision detection for reduced deformable models
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

BD-tree: output-sensitive collision detection for reduced deformable models
SIGGRAPH '04: ACM SIGGRAPH 2004 Papers

We introduce the Bounded Deformation Tree, or BD-Tree, which can perform collision detection with reduced deformable models at costs comparable to collision detection with rigid objects. Reduced deformable models represent complex deformations as linear ...
Real-Time Resolution of Self-Intersection in Dynamic Cylindrical Free-Form Deformation

This paper presents a method of self-intersection detection and resolution for dynamic cylindrical-lattice-based free-form deformation (FFD). The lattice-based approach allows efficient computation of deformation of complex geometries. But excessive ...
Monocular Template-based Reconstruction of Inextensible Surfaces

We present a monocular 3D reconstruction algorithm for inextensible deformable surfaces. It uses point correspondences between a single image of the deformed surface taken by a camera with known intrinsic parameters and a template. The main assumption ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 23, Issue 3

August 2004

684 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1015706

Editor:
John C. Hart

Issue’s Table of Contents

Copyright © 2004 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2004

Published in TOG Volume 23, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

140
Total Citations
View Citations
1,770
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zesch RWitemeyer BXiong ZLevin DSueda S(2024)NBD-Tree: Neural Bounded Deformation Tree for Collision Culling of Deformable ObjectsNext Generation Data Science10.1007/978-3-031-61816-1_6(73-87)Online publication date: 27-Jun-2024
https://doi.org/10.1007/978-3-031-61816-1_6
Dinas SMartínez H(2024)Spheres, AABB, and OOBB as Bounding Volume HierarchiesEncyclopedia of Computer Graphics and Games10.1007/978-3-031-23161-2_392(1736-1740)Online publication date: 5-Jan-2024
https://doi.org/10.1007/978-3-031-23161-2_392
Li XSong SYao JZhang HZhou RHong Q(2023)Efficient collision detection using hybrid medial axis transform and BVH for rigid body simulationGraphical Models10.1016/j.gmod.2023.101180128:COnline publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.gmod.2023.101180
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
Cho IHuo YYoon S(2021)Weakly-supervised contrastive learning in path manifold for Monte Carlo image reconstructionACM Transactions on Graphics10.1145/3450626.345987640:4(1-14)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459876
Chen JKala VMarquez-Razon AGueidon EHyde DTeran J(2021)A momentum-conserving implicit material point method for surface tension with contact angles and spatial gradientsACM Transactions on Graphics10.1145/3450626.345987440:4(1-16)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459874
Yang KChen X(2021)Unsupervised learning for cuboid shape abstraction via joint segmentation from point cloudsACM Transactions on Graphics10.1145/3450626.345987340:4(1-11)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459873
Jia K(2021)SANMACM Transactions on Graphics10.1145/3450626.345975540:4(1-16)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459755
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
Kaspar AWu KLuo YMakatura LMatusik W(2021)Knit sketchingACM Transactions on Graphics10.1145/3450626.345975240:4(1-15)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459752
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents