New research helps simulate reality

Treuille and his group have simulated a number of phenomena, including protein folding in real time. Above is a screen shot of FoldIt, a protein-folding program.   (credit: Courtesy of Edmund Huber) Treuille and his group have simulated a number of phenomena, including protein folding in real time. Above is a screen shot of FoldIt, a protein-folding program. (credit: Courtesy of Edmund Huber)

Simulating the physical world as we understand it, accurately, is the key to everything from games and movies to experiments.

“If you look at a Pixar movie, you’ll see that all the characters have simulated clothes and flowing hair,” said Adrien Treuille, asssistant professor in the computer science department, “but video games are totally different and have a much simpler world.”

The complexity of the physical simulations needed to make convincing hair, fur, and liquids require large “farms” of specialized computers and large amounts of time to render. Treuille’s research focus has been in making convincing physical simulations possible, in real time, on laptops and other commodity devices.

For example, the traditional approach to cloth simulation views the cloth as a number of particles connected by springs. Physically accurate simulation with this method, however, requires seconds or minutes to calculate per frame.

“Basically, even with very fast algorithms, it’s hard to update a large number of variables in real time. We need ways to represent physical systems using far fewer variables,” Treuille said.

The work in physical simulation by Treuille and his students attempts to boil down the problem to a smaller, more manageable number of variables that describe the essence of the phenomenon.

“Using huge numbers of variables to simulate physical systems is a little naive, because this enables an enormous number of configurations that we’ll never see that don’t actually happen in a typical day,” Treuille said.
In the case of cloth simulation, “a few number of variables, each of which is a representation of the global state, could represent the folds that you would typically expect to see,” Treuille explained. Treuille’s research group has applied this so-called “reduced basis” method to the problem of simulating fluid flow.

“In computer graphics, fluid is a relatively new field in the scheme of things,” said Matthew Stanton, a Ph.D. student under Treuille. “The problem is that the techniques are slow — even in a relatively small three-dimensional domain, it takes minutes per frame to simulate,” Stanton said.

The goal is to make fluid flow simulation responsive in real time so that it can be used in interactive contexts, such as games. In a paper published in SIGGRAPH 2009, a high-profile conference for computer graphics research, the group presented a method for linking several reduced basis simulations spatially. This allowed the group, for example, to simulate airflow through a cityscape in real time. The airflow around individual buildings was characterized independently, and the resulting piecewise simulations were stitched together on a city grid.

Treuille’s interest in simulating physical phenomena has also helped spark the FoldIt ( project, a game and competitive community for the problem of protein structure prediction.

As a protein is being created in a cell, it begins as a long string of building blocks called amino acids — the sequence of amino acids of a protein is called its primary structure. In this state, the protein is not useful, and so it either folds on itself naturally or is folded by another protein into its functional configuration. The problem of protein structure prediction is deciding how a protein will fold, knowing only its primary structure.

Computer algorithms for deciding protein folding are a hot topic in computational biology, because understanding how proteins fold can help to understand how to design proteins for specific problems.

In the FoldIt game, the player is given a protein in a partially unfolded state. The goal is then to get higher scores by folding the protein into a more and more stable state. “These are experiments to see how well human intuition helps players to find new shapes where computers fail,” Treuille said. Treuille hinted that they have had positive results in comparing human-folded proteins to computer-folded proteins, which will be revealed in an upcoming Nature article.
With the successes of FoldIt in hand, Treuille’s group has been designing and implementing a game called EvolveIt. In this game, the player designs an organism from the same building blocks used by RNA molecules. “RNA is believed to be the first, and simplest, form of life,” Treuille said. In an initial study, the players will be tasked with creating stable RNA molecules of various shapes. “We are trying to find the possible range of shapes for RNA structures,” said Jeehyung Lee, a student in Treuille’s group who is spearheading the project. Lee explained the kinds of RNA structures they want to make, saying, “Can this RNA be folded into a knot? And does it hold its shape when we shake it?” The best creatures, or RNA molecules, will be synthesized by the group’s partner lab.

In a further phase, the game will be expanded by allowing players to complete with one another. By designing and dueling their creatures, players will participate in a form of evolution, where the strongest creatures thrive and the weakest creatures are not reproduced. “Hopefully we can bring to life ancient pathways,” Treuille said.