Speculative Parallel Asynchronous Contact Mechanics

Samantha Ainsley

Columbia University

Etienne Vouga

Columbia University

Eitan Grinspun

Columbia University

Rasmus Tamstorf

Walt Disney Animation Studios


We extend the Asynchronous Contact Mechanics algorithm 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. Time warp allows us to perform collision detection over a window of time containingmany 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.


SIGGRAPH ASIA (ACM Transactions on Graphics) 2012

 author = {Ainsley, Samantha and Vouga, Etienne and Grinspun, Eitan and Tamstorf, Rasmus},
 title = {Speculative parallel asynchronous contact mechanics},
 journal = {ACM Trans. Graph.},
 issue_date = {November 2012},
 volume = {31},
 number = {6},
 month = nov,
 year = {2012},
 issn = {0730-0301},
 pages = {151:1--151:8},
 articleno = {151},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/2366145.2366170},
 doi = {10.1145/2366145.2366170},
 acmid = {2366170},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {collision, contact, parallelization, simulation},


[PDF] [Video]

To request the source code, please email sam AT media.mit.edu, with the exact subject title "SPACM Source Code" (without the quotes).