“Fast and exact continuous collision detection with Bernstein sign classification” by Tang, Tong, Wang and Manocha
Conference:
Type(s):
Title:
- Fast and exact continuous collision detection with Bernstein sign classification
Session/Category Title: Smash and Stretch
Presenter(s)/Author(s):
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.
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.Cross Ref
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.Cross Ref
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.Cross Ref
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.Cross Ref
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.Cross Ref
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.Cross Ref
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.Cross Ref
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.
