research-article

Fast continuous collision detection using deforming non-penetration filters

Authors:

Dinesh Manocha,

Ruofeng TongAuthors Info & Claims

I3D '10: Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games

Pages 7 - 13

https://doi.org/10.1145/1730804.1730806

Published: 19 February 2010 Publication History

Abstract

We present a novel culling algorithm that uses deforming non-penetration filters to improve the performance of continuous collision detection (CCD) algorithms. The underlying idea is to use a simple and effective filter that reduces both the number of false positives and the elementary tests between the primitives. This filter is derived from the coplanarity condition and can be easily combined with other methods used to accelerate CCD. We have implemented the algorithm and tested its performance on many non-rigid simulations. In practice, we can reduce the number of false positives significantly and improve the overall performance of CCD algorithms by 1.5--8.2x.

References

[1]

Bradshaw, G., and O'Sullivan, C. 2004. Adaptive medial-axis approximation for sphere-tree construction. ACM Trans. on Graphics 23, 1, 1--26.

Digital Library

[2]

Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treament for collisions, contact and friction for cloth animation. Proc. of ACM SIGGRAPH, 594--603.

Digital Library

[3]

Brochu, T., and Bridson, R. 2009. Numerically robust continuous collision detection fro dynamic explict surfaces. Tech. rep., TR-2009-03, University of British Columbia, Vancouver.

[4]

Curtis, S., Tamstorf, R., and Manocha, D. 2008. Fast collision detection for deformable models using representative-triangles. In SI3D '08: Proceedings of the 2008 Symposium on Interactive 3D graphics and games, 61--69.

Digital Library

[5]

Gottschalk, S., Lin, M. C., and Manocha, D. 1996. Obb-tree: a hierarchical structure for rapid interference detection. In SIGGRAPH '96: Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 171--180.

Digital Library

[6]

Govindaraju, N., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. ACM Trans. on Graphics (Proc. of ACM SIGGRAPH) 24, 3, 991--999.

Digital Library

[7]

Hubbard, P. M. 1993. Interactive collision detection. In Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality.

[8]

Hutter, M., and Fuhrmann, A. 2007. Optimized continuous collision detection for deformable triangle meshes. In Proc. WSCG '07, 25--32.

[9]

Kim, B., and Rossignac, J. 2003. Collision prediction for polyhedra under screw motions. In ACM Symposium in Solid Modeling and Applications, ACM Press, 4--10.

Digital Library

[10]

Klosowski, J., Held, M., Mitchell, J., Sowizral, H., and Zikan, K. 1998. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Trans. on Visualization and Computer Graphics 4, 1, 21--37.

Digital Library

[11]

Manocha, D., and Demmel, J. 1995. Algorithms for intersecting parametric and algebraic curves ii: multiple intersections. Graph. Models Image Process. 57, 2, 81--100.

Digital Library

[12]

Mezger, J., Kimmerle, S., and Etzmuß, O. 2003. Hierarchical techniques in cloth detection for cloth animation. Journal of WSCG 11, 1, 322--329.

[13]

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

[14]

Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177--189.

[15]

Redon, S., Kheddar, A., and Coquillart, S. 2002. Fast continuous collision detection between rigid bodies. Proc. of Eurographics (Computer Graphics Forum) 21, 3, 279--288.

[16]

Redon, S., Kim, Y. J., Lin, M. C., and Manocha, D. June, 2004. Fast continuous collision detection for articulated models. In SM '04: Proceedings of the ninth ACM symposium on Solid modeling and applications, 145--156.

Digital Library

[17]

Sanna, A., and Milani, M. 2004. CDFast: an algorithm combining different bounding volume strategies for real time collision detection. SCI Proceedings 2, 144--149.

[18]

Sederberg, T. W., and Nishita, T. 1990. Curve intersection using bézier clipping. Comput. Aided Des. 22, 9, 538--549.

Digital Library

[19]

Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast proximity computation among deformable models using discrete voronoi diagrams. Proc. of ACM SIGGRAPH, 1144--1153.

[20]

Tang, M., Curtis, S., Yoon, S.-E., and Manocha, D. 2009. ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling. IEEE Transactions on Visualization and Computer Graphics 15, 4, 544--557.

Digital Library

[21]

Tang, M., Kim, Y. J., and Manocha, D. 2009. C2a: Controlled conservative advancement for continuous collision detection of polygonal models. Proceedings of International Conference on Robotics and Automation, 849--854.

Digital Library

[22]

Taubin, G. 1994. Rasterizing algebraic curves and surfaces. IEEE Comput. Graph. Appl. 14, 2, 14--23.

Digital Library

[23]

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

[24]

Volino, P., and Thalmann, N. M. 1994. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Computer Graphics Forum (EuroGraphics Proc.) 13, 3, 155--166.

[25]

Wong, W. S.-K., and Baciu, G. 2006. A randomized marking scheme for continuous collision detection in simulation of deformable surfaces. Proc. of ACM VRCIA, 181--188.

Digital Library

[26]

Zhang, X., Redon, S., Lee, M., and Kim, Y. J. 2007. Continuous collision detection for articulated models using taylor models and temporal culling. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007) 26, 3, 15.

Digital Library

Cited By

Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687988
Yu BCordier FSeo H(2024)Inverse Garment and Pattern Modeling with a Differentiable SimulatorComputer Graphics Forum10.1111/cgf.1524943:7Online publication date: 7-Nov-2024
https://doi.org/10.1111/cgf.15249
Zhang DLiang CGao XWu KPan Z(2024)Provably Feasible Semi-Infinite Program Under Collision Constraints via SubdivisionIEEE Transactions on Robotics10.1109/TRO.2024.339164940(2602-2619)Online publication date: 2024
https://doi.org/10.1109/TRO.2024.3391649
Show More Cited By

Recommendations

Fast continuous collision culling with deforming noncollinear filters

We present a novel culling algorithm that uses deforming noncollinear filters to improve the performance of continuous collision detection (CCD) algorithms. The underlying idea is to use simple and effective filters, deforming noncollinear filters (NCFs)...
Reduced deforming filter culling for fast continuous collision detection
VRST '10: Proceedings of the 17th ACM Symposium on Virtual Reality Software and Technology

We propose a novel efficient deforming filter culling method for continuous collision detection (CCD) problem performed by dimension reduction in subspace. We present a fast linear filter (1D reduced filter) considering relative motion between ...
A fast algebraic non-penetration filter for continuous collision detection

We present a low-cost filtering algorithm using algebraic analysis techniques.Our algorithm can significantly reduce the number of elementary collision tests that occur in the narrow stage of continuous collision detection.We demonstrated that cubic-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

I3D '10: Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games

February 2010

201 pages

ISBN:9781605589398

DOI:10.1145/1730804

Conference Chairs:
Daniel Aliaga
Purdue University
,
Manuel M. Oliveira
Universidade Federal do Rio Grande do Sul - UFRGS
,
General Chairs:
Amitabh Varshney
University of Maryland
,
Chris Wyman
University of Iowa

Copyright © 2010 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

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 February 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

MOE-Intel special research fund on information technology
National Key Technology R&D Program, China
National Natural Science Foundation of China
Natural Science Foundation of Zhejiang Province
Army Research Office
Ministry of Education of the People's Republic of China
National Science Foundation
Defense Advanced Research Projects Agency
Ministry of Science and Technology of the People's Republic of China

Conference

I3D '10

Sponsor:

SIGGRAPH

I3D '10: Symposium on Interactive 3D Graphics and Games

February 19 - 21, 2010

D.C., Washington

Acceptance Rates

Overall Acceptance Rate 148 of 485 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
Total Citations
View Citations
692
Total Downloads

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

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687988
Yu BCordier FSeo H(2024)Inverse Garment and Pattern Modeling with a Differentiable SimulatorComputer Graphics Forum10.1111/cgf.1524943:7Online publication date: 7-Nov-2024
https://doi.org/10.1111/cgf.15249
Zhang DLiang CGao XWu KPan Z(2024)Provably Feasible Semi-Infinite Program Under Collision Constraints via SubdivisionIEEE Transactions on Robotics10.1109/TRO.2024.339164940(2602-2619)Online publication date: 2024
https://doi.org/10.1109/TRO.2024.3391649
Dinas S(2024)Collision DetectionEncyclopedia of Computer Graphics and Games10.1007/978-3-031-23161-2_291(356-358)Online publication date: 5-Jan-2024
https://doi.org/10.1007/978-3-031-23161-2_291
Shi JLiu Z(2022)Track Pairs Collision Detection with Applications to Ship Collision Risk AssessmentJournal of Marine Science and Engineering10.3390/jmse1002021610:2(216)Online publication date: 6-Feb-2022
https://doi.org/10.3390/jmse10020216
Zhu XQian YWang QFeng ZHeng P(2022)Collision-aware interactive simulation using graph neural networksVisual Computing for Industry, Biomedicine, and Art10.1186/s42492-022-00113-45:1Online publication date: 7-Jun-2022
https://doi.org/10.1186/s42492-022-00113-4
Mandal AChaudhuri PChaudhuri S(2022)Interactive Physics-Based Virtual Sculpting with Haptic FeedbackProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/35226115:1(1-20)Online publication date: 4-May-2022
https://dl.acm.org/doi/10.1145/3522611
Mandal AChaudhuri PChaudhuri S(2022)Remeshing‐free Graph‐based Finite Element Method for Fracture SimulationComputer Graphics Forum10.1111/cgf.1472542:1(117-134)Online publication date: 21-Dec-2022
https://doi.org/10.1111/cgf.14725
Wang BFerguson ZJiang XAttene MPanozzo DSchneider T(2022)Fast and Exact Root Parity for Continuous Collision DetectionComputer Graphics Forum10.1111/cgf.1447941:2(355-363)Online publication date: 24-May-2022
https://doi.org/10.1111/cgf.14479
Cha IKo H(2022)Tanglement Resolution in Clothing Simulation With Explicit ConvergenceIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2020.303956628:7(2764-2775)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TVCG.2020.3039566
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.

Figures

Tables

Media

View Table of Conten