skip to main content
research-article

Fast and exact continuous collision detection with Bernstein sign classification

Published: 19 November 2014 Publication History

Abstract

We present fast algorithms to perform accurate CCD queries between triangulated models. Our formulation uses properties of the Bernstein basis and Bézier curves and reduces the problem to evaluating signs of polynomials. We present a geometrically exact CCD algorithm based on the exact geometric computation paradigm to perform reliable Boolean collision queries. Our algorithm is more than an order of magnitude faster than prior exact algorithms. We evaluate its performance for cloth and FEM simulations on CPUs and GPUs, and highlight the benefits.

Supplementary Material

ZIP File (a186.zip)
Supplemental material.

References

[1]
Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3 (July), 594--603.
[2]
Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4 (June), 2472--2493.
[3]
Brochu, T., Edwards, E., and Bridson, R. 2012. Efficient geometrically exact continuous collision detection. ACM Trans. Graph. 31, 4 (July), 96:1--96:7.
[4]
Burnikel, C., Funke, S., and Seel, M. 2001. Exact geometric computation using cascading. International J. Comp. Geometry and Applications 11, 3, 245--266. Special Issue.
[5]
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.
[6]
Farin, G. 2002. Curves and surfaces for CAGD: a practical guide, 5th ed. Morgan Kaufmann Publishers Inc., San Francisco, USA.
[7]
Farouki, R. T., and Rajan, V. T. 1987. On the numerical condition of polynomials in berstein form. Comput. Aided Geom. Des. 4, 3 (Nov.), 191--216.
[8]
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.
[9]
Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. SIGGRAPH (ACM Transactions on Graphics) 27, 3, 1--4.
[10]
Hutter, M., and Fuhrmann, A. 2007. Optimized continuous collision detection for deformable triangle meshes. In Proc. WSCG '07, 25--32.
[11]
Kim, B., and Rossignac, J. 2003. Collision prediction for polyhedra under screw motions. In Proceedings of the eighth ACM symposium on Solid modeling and applications, SM '03, 4--10.
[12]
LaValle, S. M. 2006. Planning Algorithms. Cambridge University Press.
[13]
Mezger, J., Kimmerle, S., and Etzmuß, O. 2003. Hierarchical techniques in cloth detection for cloth animation. Journal of WSCG 11, 1, 322--329.
[14]
Mourrain, B., Rouillier, F., and Roy, M.-F. 2005. The Bernstein basis and real root isolation. In Combinatorial and Computational Geometry, MSRI Publications, 459--478.
[15]
Narain, R., Samii, A., and O'Brien, J. F. 2012. Adaptive anisotropic remeshing for cloth simulation. ACM Trans. Graph. 31, 6 (Nov.), 152:1--152:10.
[16]
Pabst, S., Koch, A., and Strasser, W. 2010. Fast and scalable CPU/GPU collision detection for rigid and deformable surfaces. Computer Graphics Forum 29, 5, 1605--1612.
[17]
Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Graphics Interface, 177--189.
[18]
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.
[19]
Schvartzman, S. C., Pérez, A. G., and Otaduy, M. A. 2010. Star-contours for efficient hierarchical self-collision detection. ACM Trans. Graph. 29, 4 (July), 80:1--80:8.
[20]
Sederberg, T. W., and Nishita, T. 1990. Curve intersection using Bézier clipping. Comput. Aided Des. 22, 9, 538--549.
[21]
Selle, A., Lentine, M., and Fedkiw, R. 2008. A mass spring model for hair simulation. ACM Trans. Graph. 27, 3 (Aug.), 64:1--64:11.
[22]
Stam, J. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In Proceedings of IEEE International Conference on CAD & CG, 1--11.
[23]
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, 544--557.
[24]
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, 356--361.
[25]
Tang, M., Kim, Y. J., and Manocha, D. 2010. CCQ: Efficient local planning using connection collision query. In WAFR, 229--247.
[26]
Tang, M., Manocha, D., and Tong, R. 2010. Fast continuous collision detection using deforming non-penetration filters. In Proceedings of ACM Symposium on Interactive 3D Graphics and Games, ACM, New York, NY, USA, 7--13.
[27]
Tang, M., Manocha, D., Yoon, S.-E., Du, P., Heo, J.-P., and Tong, R. 2011. VolCCD: Fast continuous collision culling between deforming volume meshes. ACM Trans. Graph. 30 (May), 111:1--111:15.
[28]
Tang, M., Tong, R., Narain, R., Meng, C., and Manocha, D. 2013. A GPU-based streaming algorithm for high-resolution cloth simulation. Computer Graphics Forum 32, 7, 21--30.
[29]
Volino, P., and Thalmann, N. M. 1994. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Computer Graphics Forum 13, 3, 155--166.
[30]
Wang, H. 2014. Defending continuous collision detection against errors. ACM Trans. Graph. 33, 4 (July), 122:1--122:10.
[31]
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.
[32]
Yap, C. 2004. Robust geometric computation. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, Eds., 2nd ed. Chapmen & Hall/CRC, Boca Raton, FL, ch. 41, 927--952.
[33]
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.
[34]
Zhao, J., Tang, M., and Tong, R. 2012. Connectivity-based segmentation for GPU-accelerated mesh decompression. J. Comput. Sci. Technol. 27, 6, 1110--1118.
[35]
Zheng, C., and James, D. L. 2012. Energy-based self-collision culling for arbitrary mesh deformations. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2012) 31, 4 (Aug.), 98:1--98:12.

Cited By

View all
  • (2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
  • (2024)A Time-Dependent Inclusion-Based Method for Continuous Collision Detection between Parametric SurfacesACM Transactions on Graphics10.1145/368796043:6(1-11)Online publication date: 19-Dec-2024
  • (2024)Enhancing a Bellow-Structure Soft Actuator Simulations via a Novel Continuous Collision Detection Algorithm2024 30th International Conference on Mechatronics and Machine Vision in Practice (M2VIP)10.1109/M2VIP62491.2024.10746100(1-4)Online publication date: 3-Oct-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 33, Issue 6
November 2014
704 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/2661229
Issue’s Table of Contents
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: 19 November 2014
Published in TOG Volume 33, Issue 6

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Bernstein sign classification
  2. continuous collision detection
  3. exact geometric computation
  4. physically based simulation

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)29
  • Downloads (Last 6 weeks)6
Reflects downloads up to 17 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
  • (2024)A Time-Dependent Inclusion-Based Method for Continuous Collision Detection between Parametric SurfacesACM Transactions on Graphics10.1145/368796043:6(1-11)Online publication date: 19-Dec-2024
  • (2024)Enhancing a Bellow-Structure Soft Actuator Simulations via a Novel Continuous Collision Detection Algorithm2024 30th International Conference on Mechatronics and Machine Vision in Practice (M2VIP)10.1109/M2VIP62491.2024.10746100(1-4)Online publication date: 3-Oct-2024
  • (2024)IIPC: Intra-Inter Patch Correlations for Garment Collision Handling2024 IEEE International Conference on Multimedia and Expo (ICME)10.1109/ICME57554.2024.10687452(1-6)Online publication date: 15-Jul-2024
  • (2024)A Collision Detection Algorithm Based on Sphere and EBB Mixed Hierarchical Bounding BoxesIEEE Access10.1109/ACCESS.2024.339292012(62719-62729)Online publication date: 2024
  • (2024)CTSN: Predicting cloth deformation for skeleton-based characters with a two-stream skinning networkComputational Visual Media10.1007/s41095-023-0344-610:3(471-485)Online publication date: 19-Apr-2024
  • (2024)High-fidelity surgical simulator for the performance of craniofacial osteotomiesInternational Journal of Computer Assisted Radiology and Surgery10.1007/s11548-024-03297-7Online publication date: 11-Dec-2024
  • (2023)Recent Trends in High Speed ComputingTechnological Tools for Innovative Teaching10.4018/979-8-3693-3132-3.ch019(369-379)Online publication date: 29-Dec-2023
  • (2023)Fast GPU-based Two-way Continuous Collision HandlingACM Transactions on Graphics10.1145/360455142:5(1-15)Online publication date: 28-Jul-2023
  • (2023)Research on algorithms of physics-based cloth simulationFourth International Conference on Signal Processing and Computer Science (SPCS 2023)10.1117/12.3012301(124)Online publication date: 21-Dec-2023
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media