Real-Time Soft Body Dynamics for Video Games | Two Minute Papers #103

Dear Fellow Scholars, this is Two Minute Papers with Károly Zsolnai-Fehér. We have had plenty of episodes about fluid simulations, so how about some tasty soft body dynamics for today? Soft body dynamics basically means computing what happens when we smash together different deformable objects. Examples include folding sheets, playing around with noodles, or torturing armadillos. I think this is a nice and representative showcase of the immense joys of computer graphics research! The key to real-time physically based simulations is parallelism. Parallelism means that we have many of the same units working together in harmony. Imagine if we had to assign 50 people to work together to make a coffee in the same kitchen. As you may imagine, they would trip over each other, and the result would be chaos, not productivity. Such a process would not scale favorably, because as we would add more people after around 3 or 4, the productivity would not increase, but drop significantly. You can often hear a similar example of 9 pregnant women not being able to give birth to a baby in one month. For better scaling, we have to subdivide a bigger task into small tasks in a way that these people can work independently. The more independently they can work, the better the productivity will scale as we add more people. In software engineering, these virtual people we like call threads, or compute units. As of 2016, mid-tier processors are equipped with 4-8 logical cores, and for a video card, we typically have compute units in the order of hundreds. So if we wish to develop efficient algorithms, we have to make sure that these big simulation tasks are subdivided in a way so that these threads are not tripping over each other. And the big contribution of this piece of work is a technique to distribute the computation tasks to these compute units in a way that they are working on independent chunks of the problem. This is achieved via using graph coloring, which is a technique typically used for designing seating plans, exam timetabling, solving sudoku puzzles and similar assignment tasks. It not only works in an absolutely spectacular manner, but graph theory is an immensely beautiful subfield of mathematics, so additional style points to the authors! The technique produces remarkably realistic animations and requires only 15 milliseconds per frame, which means that this technique can render over 60 frames per second comfortably. And the other most important factor is that this technique is also stable, meaning that it offers an appropriate solution, even when many other techniques fail to deliver. Thanks for watching, and for your generous support, and I'll see you next time!