Min Tang
Dinesh Manocha
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
Available for Download
zip
a186.zip (328.5 KB)
Supplemental material.
- 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. Google Scholar
Digital Library
- Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4 (June), 2472--2493. Google ScholarDigital Library
- Brochu, T., Edwards, E., and Bridson, R. 2012. Efficient geometrically exact continuous collision detection. ACM Trans. Graph. 31, 4 (July), 96:1--96:7. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Farin, G. 2002. Curves and surfaces for CAGD: a practical guide, 5th ed. Morgan Kaufmann Publishers Inc., San Francisco, USA. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. SIGGRAPH (ACM Transactions on Graphics) 27, 3, 1--4. Google ScholarDigital Library
- Hutter, M., and Fuhrmann, A. 2007. Optimized continuous collision detection for deformable triangle meshes. In Proc. WSCG '07, 25--32.Google Scholar
- 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. Google ScholarDigital Library
- LaValle, S. M. 2006. Planning Algorithms. Cambridge University Press. Google ScholarDigital Library
- Mezger, J., Kimmerle, S., and Etzmuß, O. 2003. Hierarchical techniques in cloth detection for cloth animation. Journal of WSCG 11, 1, 322--329.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Graphics Interface, 177--189.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Sederberg, T. W., and Nishita, T. 1990. Curve intersection using Bézier clipping. Comput. Aided Des. 22, 9, 538--549. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Stam, J. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In Proceedings of IEEE International Conference on CAD & CG, 1--11.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Tang, M., Kim, Y. J., and Manocha, D. 2010. CCQ: Efficient local planning using connection collision query. In WAFR, 229--247.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Wang, H. 2014. Defending continuous collision detection against errors. ACM Trans. Graph. 33, 4 (July), 122:1--122:10. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Zhao, J., Tang, M., and Tong, R. 2012. Connectivity-based segmentation for GPU-accelerated mesh decompression. J. Comput. Sci. Technol. 27, 6, 1110--1118.Google ScholarCross Ref
- 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. Google ScholarDigital Library
Recommendations
Efficient geometrically exact continuous collision detection
Continuous collision detection (CCD) between deforming triangle mesh elements in 3D is a critical tool for many applications. The standard method involving a cubic polynomial solver is vulnerable to rounding error, requiring the use of ad hoc tolerances,...
A Large-scale Benchmark and an Inclusion-based Algorithm for Continuous Collision Detection
We introduce a large-scale benchmark for continuous collision detection (CCD) algorithms, composed of queries manually constructed to highlight challenging degenerate cases and automatically generated using existing simulators to cover common cases. We ...
Incremental potential contact: intersection-and inversion-free, large-deformation dynamics
Contacts weave through every aspect of our physical world, from daily household chores to acts of nature. Modeling and predictive computation of these phenomena for solid mechanics is important to every discipline concerned with the motion of mechanical ...
Comments