research-article

Speculative parallel asynchronous contact mechanics

Authors:

Samantha Ainsley,

Eitan Grinspun,

Rasmus TamstorfAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 31, Issue 6

Article No.: 151, Pages 1 - 8

https://doi.org/10.1145/2366145.2366170

Published: 01 November 2012 Publication History

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.

Supplementary Material

ZIP File (151-146-0166.zip)

Supplemental Materials for Speculative parallel asynchronous contact mechanics

Download
15.10 MB

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.

Digital Library

[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.

Digital Library

[4]

Bridson, R. 2003. Computational aspects of dynamic surfaces. PhD thesis, Stanford University.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[10]

Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2011. Research highlights: Asynchronous contact mechanics. Communications of the ACM.

Digital Library

[11]

Harmon, D., Zhou, Q., and Zorin, D. 2011. Asynchronous integration with phantom meshes. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation.

Digital Library

[12]

Harmon, D. 2010. Robust, Efficient, and Accurate Contact Algorithms. PhD thesis, Columbia University.

Digital Library

[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.

Digital Library

[14]

Jefferson, D. 1985. Virtual time. ACM Transactions on Programming Languages and Systems 7, 404--425.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[27]

Thomaszewski, B., and Blochinger, W. 2006. Parallel simulation of cloth on distributed memory architectures. Proc. Eurographics Symp. Parallel Graphics and Visualization.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.).

Digital Library

Cited By

Morales NJones RLifflander JPébaÿ PMcGovern SSkrzyński CSchilly C(2024)Distributed Asynchronous Contact Mechanics with DARMA/vtAsynchronous Many-Task Systems and Applications10.1007/978-3-031-61763-8_4(34-45)Online publication date: 14-Feb-2024
https://dl.acm.org/doi/10.1007/978-3-031-61763-8_4
Wang TChen JLi DLiu XWang HZhou K(2023)Fast GPU-based Two-way Continuous Collision HandlingACM Transactions on Graphics10.1145/360455142:5(1-15)Online publication date: 28-Jul-2023
https://dl.acm.org/doi/10.1145/3604551
Gay Neto A(2023)Framework for automatic contact detection in a multibody systemComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2022.115703403(115703)Online publication date: Jan-2023
https://doi.org/10.1016/j.cma.2022.115703
Show More Cited By

Index Terms

Speculative parallel asynchronous contact mechanics
1. Computing methodologies
  1. Computer graphics
    1. Animation

Recommendations

Asynchronous contact mechanics

We develop a method for reliable simulation of elastica in complex contact scenarios. Our focus is on firmly establishing three parameter-independent guarantees: that simulations of well-posed problems (a) have no interpenetrations, (b) obey causality, ...
Asynchronous contact mechanics
SIGGRAPH '09: ACM SIGGRAPH 2009 papers

We develop a method for reliable simulation of elastica in complex contact scenarios. Our focus is on firmly establishing three parameter-independent guarantees: that simulations of well-posed problems (a) have no interpenetrations, (b) obey causality, ...
Investigation of joint clearance effects on the dynamic performance of a planar 2-DOF pick-and-place parallel manipulator

In this study, the effects of joint clearance on the dynamic performance of a planar 2-DOF pick-and-place parallel manipulator are investigated. The parallel manipulator is modeled by multi-body system dynamics. The contact effect in revolute joints ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 31, Issue 6

November 2012

794 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2366145

Issue’s Table of Contents

Copyright © 2012 ACM.

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: 01 November 2012

Published in TOG Volume 31, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
567
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Morales NJones RLifflander JPébaÿ PMcGovern SSkrzyński CSchilly C(2024)Distributed Asynchronous Contact Mechanics with DARMA/vtAsynchronous Many-Task Systems and Applications10.1007/978-3-031-61763-8_4(34-45)Online publication date: 14-Feb-2024
https://dl.acm.org/doi/10.1007/978-3-031-61763-8_4
Wang TChen JLi DLiu XWang HZhou K(2023)Fast GPU-based Two-way Continuous Collision HandlingACM Transactions on Graphics10.1145/360455142:5(1-15)Online publication date: 28-Jul-2023
https://dl.acm.org/doi/10.1145/3604551
Gay Neto A(2023)Framework for automatic contact detection in a multibody systemComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2022.115703403(115703)Online publication date: Jan-2023
https://doi.org/10.1016/j.cma.2022.115703
Wang QZhang WCheng YLiu LFu X(2023)Practical construction of globally injective parameterizations with positional constraintsComputational Visual Media10.1007/s41095-022-0269-59:2(265-277)Online publication date: 3-Jan-2023
https://doi.org/10.1007/s41095-022-0269-5
Andrews SErleben KFerguson ZNandigjav MShinar T(2022)Contact and friction simulation for computer graphicsACM SIGGRAPH 2022 Courses10.1145/3532720.3535640(1-172)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3532720.3535640
Lee SLee KKo H(2022)Regularly striped preconditioner for implicit clothing simulationThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-021-02158-738:8(2827-2838)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s00371-021-02158-7
Lan LYang YKaufman DYao JLi MJiang C(2021)Medial IPCACM Transactions on Graphics10.1145/3450626.345975340:4(1-16)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459753
Gay Neto AHudobivnik BMoherdaui TWriggers P(2021)Flexible polyhedra modeled by the virtual element method in a discrete element contextComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2021.114163387(114163)Online publication date: Dec-2021
https://doi.org/10.1016/j.cma.2021.114163
Neto AWriggers P(2021)Discrete element model for general polyhedraComputational Particle Mechanics10.1007/s40571-021-00415-z9:2(353-380)Online publication date: 1-Jun-2021
https://doi.org/10.1007/s40571-021-00415-z
Lifflander JMiller PSlattengren NMorales NStickney PPebay P(2020)Design and Implementation Techniques for an MPI-Oriented AMT Runtime2020 Workshop on Exascale MPI (ExaMPI)10.1109/ExaMPI52011.2020.00009(31-40)Online publication date: Nov-2020
https://doi.org/10.1109/ExaMPI52011.2020.00009
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents