“Speculative parallel asynchronous contact mechanics” by Ainsley, Vouga, Grinspun and Tamstorf
Conference:
Type(s):
Title:
- Speculative parallel asynchronous contact mechanics
Session/Category Title: Dynamics
Presenter(s)/Author(s):
Abstract:
We extend the Asynchronous Contact Mechanics algorithm [Harmon et al. 2009] and improve its performance by two orders of magnitude, using only optimizations that do not compromise ACM’s three guarantees of safety, progress, and correctness. The key to this speedup is replacing ACM’s timid, forward-looking mechanism for detecting collisions—locating and rescheduling separating plane kinetic data structures—with an optimistic speculative method inspired by Mirtich’s rigid body Time Warp algorithm [2000]. Time warp allows us to perform collision detection over a window of time containing many of ACM’s asynchronous trajectory changes; in this way we cull away large intervals as being collision free. Moreover, by replacing force processing intermingled with KDS rescheduling by windows of pure processing followed by collision detection, we transform an algorithm that is very difficult to parallelize into one that is embarrassingly parallel.
References:
1. Bender, J., and Bayer, D. 2008. Parallel simulation of inextensible cloth. In Proceedings of VRIPhys.
2. Borkar, S., and Chien, A. A. 2011. The future of microprocessors. Commun. ACM 54, 5 (May), 67–77.
3. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact, and friction for cloth animation. ACM Transactions on Graphics 21, 3, 594–603.
4. Bridson, R. 2003. Computational aspects of dynamic surfaces. PhD thesis, Stanford University.
5. Brochu, T., Edwards, E., and Bridson, R. 2012. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics (TOG) — Proceedings of the ACM SIGGRAPH 2012.
6. Cuthill, E., and McKee, J. 1969. Reducing the bandwidth of sparse symmetric matrices. In ACM ’69 Proceedings of the 1969 24th national conference, 157–172.
7. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. 2001. Dynamic real-time deformations using space and time adaptive sampling. In Proceedings of SIGGRAPH 01, 31–36.
8. Guibas, L. 1998. Kinetic data structures: a state of the art report. In Proceedings of the 3rd Workshop on Algorithmic Foundations of Robotics (WAFR), 191–209.
9. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Transactions on Graphics (TOG) — Proceedings of the ACM SIGGRAPH 2009.
10. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2011. Research highlights: Asynchronous contact mechanics. Communications of the ACM.
11. Harmon, D., Zhou, Q., and Zorin, D. 2011. Asynchronous integration with phantom meshes. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation.
12. Harmon, D. 2010. Robust, Efficient, and Accurate Contact Algorithms. PhD thesis, Columbia University.
13. Huang, J.-C., Jiao, X., Fujimoto, R. M., and Zha, H. 2007. DAG-guided parallel asynchronous variational integrators with super-elements. In Proceedings of the 2007 summer computer simulation conference, 691–697.
14. Jefferson, D. 1985. Virtual time. ACM Transactions on Programming Languages and Systems 7, 404–425.
15. Kale, K., and Lew, A. 2007. Parallel asynchronous variational integrators. International Journal for Numerical Methods in Engineering 70, 291–321.
16. Kim, D., Heo, J.-P., Huh, J., Kim, J., and Yoon, S.-E. 2009. HPCCD: Hybrid parallel continuous collision detection using cpus and gpus. Computer Graphics Forum (Pacific Graphics) 28, 7.
17. Konečný, P., and Zikan, K. 1997. Lower bound of distance in 3D. In Proceedings of WSCG 1997, vol. 3, 640–649.
18. Lew, A., Marsden, J. E., Ortiz, M., and West, M. 2003. Asynchronous variational integrators. Archive for Rational Mechanics and Analysis 167, 85–146.
19. Mirtich, B. 2000. Timewarp rigid body simulation. SIGGRAPH ’00 Proceedings of the 27th annual conference of computer graphics and interactive techniques, 193–200.
20. Pabst, S., Koch, A., and Straer, W. 2010. Fast and scalable cpu/gpu collision detection for rigid and deformable surfaces. Computer Graphics Forum 29, 5, 1605–1612.
21. Pingali, K., Nguyen, D., Kulkarni, M., Burtscher, M., Hassaan, M. A., Kaleem, R., Lee, T.-H., Lenharth, A., Manevich, R., Méndez-Lojo, M., Prountzos, D., and Sui, X. 2011. The tao of parallelism in algorithms. In Proceedings of the 32nd ACM SIGPLAN conference on programming language design and implementation, 12–25.
22. 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.
23. Stam, J. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In IEEE International Conference on Computer-Aided Design and Computer Graphics, 1–11.
24. Sutter, H., and Alexandrescu, A. 2004. C++ Coding Standards: 101 Rules, Guidelines, and Best Practices. Pearson Education, Inc.
25. Tang, M., Manocha, D., and Tong, R. 2010. Mccd: Multicore collision detection between deformable models using front-based decomposition. Graphical Models 72, 2, 7–23.
26. Tang, M., Manocha, D., Lin, J., and Tong, R. 2011. Collision-streams: Fast GPU-based collision detection for deformable models. In I3D ’11: Proceedings of the 2011 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games, 63–70.
27. Thomaszewski, B., and Blochinger, W. 2006. Parallel simulation of cloth on distributed memory architectures. Proc. Eurographics Symp. Parallel Graphics and Visualization.
28. Thomaszewski, B., Pabst, S., and Blochinger, W. 2008. Parallel techniques for physically-based simulation on multicore processor architectures. Computers and Graphics 31, 25–40.
29. Thomaszewski, B., Pabst, S., and Strasser, W. 2008. Asynchronous cloth simulation. Computer Graphics International.
30. Vouga, E., Harmon, D., Tamstorf, R., and Grinspun, E. 2011. Asynchronous variational contact mechanics. Computer Methods in Applied Mechanics and Engineering 200, 2181–2194.
31. Yoon, S.-E., Lindstrom, P., Pascucci, V., and Manocha, D. 2005. Cache-oblivious mesh layouts. ACM Trans. Graph. 24, 3 (July), 886–893.
32. Zheng, C., and James, D. L. 2011. Toward high-quality modal contact sound. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2011) 30, 4 (Aug.).
