“Defending continuous collision detection against errors” by Wang
Conference:
Type(s):
Title:
- Defending continuous collision detection against errors
Session/Category Title: Hair & Collisions
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Numerical errors and rounding errors in continuous collision detection (CCD) can easily cause collision detection failures if they are not handled properly. A simple and effective approach is to use error tolerances, as shown in many existing CCD systems. Unfortunately, finding the optimal tolerance values is a difficult problem for users. Larger tolerance values will introduce false positive artifacts, while smaller tolerance values may cause collisions to be undetected. The biggest issue here is that we do not know whether or when CCD will fail, even though failures are extremely rare. In this paper, we demonstrate a set of simple modifications to make a basic CCD implementation failure-proof. Using error analysis, we prove the safety of this method and we formulate suggested tolerance values to reduce false positives. The resulting algorithms are safe, automatic, efficient, and easy to implement.
References:
1. Ainsley, S., Vouga, E., Grinspun, E., and Tamstorf, R. 2012. Speculative parallel asynchronous contact mechanics. ACM Transactions on Graphics (SIGGRAPH Asia 2012) 31, 6 (Nov.), 151:1. Google ScholarDigital Library
2. Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. ACM Transactions on Graphics (SIGGRAPH) 22 (July), 862–870. Google ScholarDigital Library
3. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. In Proc. of ACM SIGGRAPH 2002, E. Fiume, Ed., vol. 21 of Computer Graphics Proceedings, Annual Conference Series, 594–603. Google ScholarDigital Library
4. Brochu, T., Edwards, E., and Bridson, R. 2012. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics (SIGGRAPH 2012) 31, 4 (July), 96:1–96:7. Google ScholarDigital Library
5. Gilbert, E. G., Johnson, D. W., and Keerthi, S. S. 1988. A fast procedure for computing the distance between complex objects in three-dimensional space. Robotics and Automation 4, 2, 193–.Google ScholarCross Ref
6. Goldberg, D. 1991. What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys 23, 1. Google ScholarDigital Library
7. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. ACM Transactions on Graphics (SIGGRAPH) 27, 3 (August), 23:1–23:4. Google ScholarDigital Library
8. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Transactions on Graphics (SIGGRAPH) 28, 3 (July), 87:1–87:12. Google ScholarDigital Library
9. Harmon, D., Zhou, Q., and Zorin, D. 2011. Asynchronous integration with phantom meshes. In Proc. of SCA, 247–256. Google ScholarDigital Library
10. Huh, S., Metaxas, D. N., and Badler, N. I. 2001. Collision resolutions in cloth simulation. In Proc. of Computer Animation, IEEE, 122–127.Google Scholar
11. Larsen, E., Gottschalk, S., Lin, M. C., and Manocha, D. 2000. Fast distance queries with rectangular swept sphere volumes. In Proc. of Robotics and Automation, 3719–3726.Google Scholar
12. Lauterbach, C., Mo, Q., and Manocha, D. 2010. gProximity: Hierarchical GPU-based operations for collision and distance queries. In Proc. of Eurographics, vol. 29, 419–428.Google ScholarCross Ref
13. Pabst, S., Koch, A., and Straßer, W. 2010. Fast and scalable CPU/GPU collision detection for rigid and deformable surfaces. Computer Graphics Forum 29, 5, 1605–1612.Google ScholarCross Ref
14. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation, 177–189.Google Scholar
15. Schvartzman, S. C., Pérez, A. G., and Otaduy, M. A. 2010. Star-contours for efficient hierarchical self-collision detection. ACM Transactions on Graphics (SIGGRAPH 2010) 29 (July), 80:1. Google ScholarDigital Library
16. Selle, A., Su, J., Irving, G., and Fedkiw, R. 2009. Robust high-resolution cloth using parallelism, history-based collisions, and accurate friction. IEEE Transactions on Visualization and Computer Graphics 15 (March), 339–350. Google ScholarDigital Library
17. Shewchuk, J. R. 1996. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 305–363.Google ScholarCross Ref
18. Stam, J. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In 11th IEEE International Conference on Computer-Aided Design and Computer Graphics.Google ScholarCross Ref
19. Tang, M., Kim, Y. J., and Manocha, D. 2010. Continuous collision detection for non-rigid contact computations using local advancement. In ICRA, 4016–4021.Google Scholar
20. Tang, M., Manocha, D., Yoon, S.-E., Du, P., Heo, J.-P., and Tong, R.-F. 2011. VolCCD: Fast continuous collision culling between deforming volume meshes. ACM Transactions on Graphics 30, 5 (Oct.), 111:1–111:15. Google ScholarDigital Library
21. Thomaszewski, B., Pabst, S., and Straßer, W. 2008. Asynchronous cloth simulation. In Proc. of Computer Graphics International.Google Scholar
22. Volino, P., and Magnenat-Thalmann, N. 2006. Resolving surface collisions through intersection contour minimization. ACM Transactions on Graphics (SIGGRAPH) 25 (July), 1154–1159. Google ScholarDigital Library
23. Wilkinson, J. H. 1994. Rounding Errors in Algebraic Processes. Dover Publications, Incorporated. Google ScholarDigital Library
24. Zheng, C., and James, D. L. 2012. Energy-based self-collision culling for arbitrary mesh deformations. ACM Transactions on Graphics (SIGGRAPH 2012) 31, 4 (July), 98:1–98:12. Google ScholarDigital Library
