15418 Final Project

Parallelizing LiquidFun

Project Proposal PDF

Project Checkpoint PDF

Project Summary

We are going to parallelize a 2D physics engine for games, specifically the LiquidFun extension to Box2D by Google. As LiquidFun/Box2D is a large library, we will be specifically tackling the problem of particle dynamics within the library. We will be implementing basic parallelism by using Intel's Threading Building Blocks and/or openMP.


LiquidFun is a 2D physics engine for game based upon Box2D that includes particle­based fluid simulation. It is an open source written in platform independent C++ by Google, and it has an additional functionality that adds a particle based fluid and soft body simulation to the rigid body functionality in Box2D. As Box2D is a complete 2D physics engine, it has many different functionalities. We chose to focus on the portion of the code that deals with particle dynamics, including velocity, collision, adhesion/cohesion, and other attributes.

Completed Work

We profiled liquidfun’s particle collision library, and measured the time complexity and the usage of functions in the program. Since, our choice of architecture is a multi-core Intel processor, we decided to use Intel’s Threading Building Blocks (Intel TBB). TBB is a C++ template library that take advantage of multi-core processors. We first idenfitied a single for-loop that is safe to process each element concurrently, and replaced it with the template function tbb: :parallel_for to break a iteration space into chunks and runs each chunk on a separate thread.


Duration Bryan's Tasks Ji Hye's Tasks
April 17th (Thur) + 3 days (April 19th, Sat) Write more tests that test particle detection functionality and profile it Parallelize for loops and check performance improvement
April 20th (Sun) + 3 days (April 22nd, Tues) Based on profiling result, find areas where it can be parallelized using pthreads Create pthreads level parallelism and look for improvements based on SIMD
April 23rd (Wed) + 4 days (April 25th, Sat) Based on profiling result, vectorize using SIMD intrinsic Vectorize using SIMD
April 26th (Sun) + 4 days (April 29th, Tues) Analyze the performance improvement, and look for algorithmic improvmene that utilizes parallelism. Implement an algorithm that efficiently parallelize the program
April 30th (Wed) + 4 days (May 3rd, Sat) Write a test case that shows an improvement of performance. Analyze why the performance of physical simulator was greatly improved by certain parallell implementation
May 4th (Sun) + 4 days (May 7th, Wed) Last minute analysis and programming / check with course staffs Last minute analysis and programming / check with course staffs
May 8th (Thur) + 2 days (May 9th, Fri) Webpage / post Prepare for presentation