April 2010 Issue
cmt_v7n2_fe2_header-simple-terms.jpg
Issue Home | > In Simple Terms

In Simple Terms

By:

It's the first bone-chilling day of winter, and Adrien Treuille finds sanctuary from the cold in the steaming hot latte he sips at his office desk. Nearly imperceptible currents of vapor escape from the lid of his paper cup and quickly disappear. As the Carnegie Mellon professor settles in at his laptop, his well-worn T-shirt wrinkles against his skin. He runs his fingers through his close-clipped hair, which flattens slightly before bouncing back into position.

Outside, the arctic wind lashes against the tall grass covering the hill beneath Treuille's office window in the Gates Center for Computer Science. The blades bend back and forth, barely withstanding the force of each gust. Simultaneously, a tempest of snow churns in the air as the gale kicks up the dusting that veiled the Pittsburgh campus overnight. Evidently, the weather isn't harsh enough to deter throngs of students who hurry along the sidewalk to class, though most walk with their heads down to help ward off the wintry mix.

Steam evaporating. A shirt creasing. Hair mussed up. Wind blowing. Crowds moving. These are physical minutiae of the human experience that go largely unnoticed in our daily lives. Yet, what if you are trying to recreate those experiences on a computer so the virtual world you construct seems absolutely faithful to our perception of everyday reality? In that case, getting these small, deceivingly complex details right takes on huge importance.

There's a whole lot of math, physics, and computer theory inherent in that challenge. For Treuille, there's poetry, and maybe even some magic involved, too. "It's totally enchanting to look out your window and see all of these things happening—snow falling, plants bending in the wind—and to ask yourself not only how does it work, but how would I build these things?" says Treuille, who joined the faculty of the School of Computer Science at Carnegie Mellon one year ago as an assistant professor in the computer graphics group.

"It gets to a fundamental part of computer science," he adds, "where you have these building blocks, but unlike in other fields, there is a sense in which these building blocks actually live and breathe, and if you assemble them the right way, Pinocchio will come alive, so to speak."

Growing up as one of four children of two banking executives in Manhattan, Treuille (a French name pronounced "Troy" in English) never imagined himself on the frontiers of digital possibility, breathing virtual life into metaphorical wooden puppets. "In high school, I had a nerdy interest in computer games the way boys do," he recalls. "But I really hated science and math and thought they were really boring."

Fluent in French, thanks to his father, a French national who is a colonel and commander of the French Army Reserves in the United States, Treuille began college at the School of Foreign Service at Georgetown University. He quickly grew disenchanted with his studies in international relations and almost dropped out of school his sophomore year. That's when an economics professor told him, in the parlance of the field, that his intellectual resources were being "misallocated" and urged him to try classes in other disciplines. "Among other crazy things, I took a computer science and math class, and I thought they were totally sweet," recalls Treuille.

After graduating from Georgetown with a degree in computer science in 2002, Treuille enrolled in graduate school at the University of Washington. There, he discovered the field of computer graphics during a course on physics-based animation taught by his doctoral advisor, Zoran Popovi, who earned his PhD in computer science from Carnegie Mellon in 1999.

For many years, computer scientists have been applying the laws of physics—such as the set of equations that describe the behavior of fluids—to model physical phenomena like curling smoke and splashing water. However, the mathematical complexity of these simulations meant they required the power of supercomputers and a lot of time to conjure them realistically on the screen. For example, a full simulation of how a shirt might be folded would include extremely implausible, origami-like shapes described by complex algorithms requiring minutes or even hours for high-performance computers to process—a virtual eternity.

For his dissertation research, Treuille applied and developed a mathematical method called model reduction to make these kinds of simulations run at faster speeds on everyday personal computers and other commodity hardware devices. This breakthrough approach puts physics-based animation in the hands of ordinary people by boiling down the number of variables the computer must account for when representing physical systems, removing unlikely outcomes.

"The central principle is to realize that not everything is possible," Treuille explains. "It is not possible for your shirt to fold any which way. Typically, on a given day, it will simply fold in some ways that we can expect. If we restrict the space in which a physical simulation happens to those ways we expect, it turns out you can come up with very, very fast, compact algorithms."

These new algorithms create stunningly accurate displays of physical processes ranging from the flow of people in a crowd to the way air streams through a cityscape. And these simulations happen at real-time speeds—sometimes millions of times faster than previously possible.

"Adrien's techniques are mathematically elegant and achieve astounding performance and realism in simulations of highly complex physical systems," says Peter Lee, Carnegie Mellon computer science professor and office director at DARPA. "The potential for both scientific and artistic applications is tremendous."

For instance, Treuille's real-time simulations could help video game designers and moviemakers to create virtual worlds that are more true to life. Or allow engineers to interactively design the shape of cars or airplanes. Or empower students to play with wiggling proteins and explore spinning cosmos. Or create more realistic simulations for training firefighters, medical professionals, and soldiers.

"Adrien Treuille is really always thinking about how his work will not only move science forward, but also how it will impact the world outside of computer graphics," says longtime colleague Aaron Hertzmann, an associate professor in the Department of Computer Science at the University of Toronto.

It would be hard to imagine a world more removed from academic computer science than NASCAR racing. But after Treuille presented his findings on real-time simulation at the SIGGRAPH computer graphics conference in 2006, he and Popovi were approached by Sportvision Inc. about licensing the technology to create a new effect for racing coverage. Millions of NASCAR fans watching ESPN have now seen the Emmy-nominated Draft Track special effect, which allows TV audiences to view the never-before-seen air flow around cars traveling at speeds upward of 200 miles per hour. NASCAR drivers use a technique called drafting, which involves aligning their cars to take advantage of this air flow—represented live in Draft Track by different colors—as a way to gain faster speeds and better fuel efficiency.

Several of Treuille's other simulations also have attracted commercial interest. For instance, his crowd simulation techniques were licensed by video game maker Electronic Arts Inc. and Microsoft to replace more processing-intensive artificial intelligence methods. Graphics chip maker AMD also used these methods in developing an advanced test game called "Froblins."

Beyond entertainment, what's most gratifying to Treuille is the potential for real-time simulation to open up otherwise-hidden natural worlds and, in the process, change the way scientific progress is made and perhaps even save lives. During his final year of graduate school, he was invited to a meeting with David Baker, a biochemistry professor at the University of Washington interested in creating a computer game to help tackle the biggest challenge in computational biology: protein folding.

Proteins are the workhorses of the human body, responsible for everything from building muscles to producing mothers' milk. The key to figuring out what a protein does is cracking its three-dimensional shape, determined by all the ways its tens of thousands of atoms interact. Knowing how proteins naturally fold could help scientists develop new cancer drugs, HIV vaccines, or biofuels. However, all the computers in the world working together would take centuries to do the trillions of calculations required to solve this puzzle. Baker believed that people, using their intuitive spatial reasoning and 3D problem-solving skills, might find answers more quickly.

Treuille spent a year as a postdoctoral fellow at the University of Washington helping to develop Foldit, a free, multiplayer online game that transforms protein folding into a competitive sport. Players are presented with a simulated image of a protein—a multicolored, geometric knot of amino acids—and then use the cursor to grab, bend, pull, and wiggle that tangle into an optimally folded molecule. The more energetically stable the protein shape, the higher the score. More than 50,000 people worldwide—among them grandmothers, teenagers, historians, and farmers—play Foldit regularly, scientific skills not required. It's a Web 2.0 approach to science, and a new version of the popular game harnesses the brainpower of users to design completely novel proteins that Treuille says could one day lead to a Nobel Prize–winning discovery.

"We are basically asking the public to help us do advanced biomedical research by playing a video game," he says. "It's absolutely opening up the frontiers of science directly to the world of amateurs. And there's totally the possibility that some Kasparov will start beating every puzzle and make it possible for us to find new, medically useful ways to fold proteins. The potential energy of the Foldit project is huge—like way high into the stratosphere."

According to Baker, Treuille's long-term vision and creative energy helped transform the dream of Foldit into a reality. "Adrien is always thinking beyond the next turn in the road," says Baker, who is writing a paper with Treuille for the prestigious scientific journal Nature comparing human-folded proteins to their computer-folded counterparts.

Treuille's pioneering work has earned him recognition from the editors of Technology Review magazine and a panel of expert judges, who named the 30-year-old to its annual list of the world's top 35 innovators younger than age 35. He was selected from a pool of more than 300 nominees. "The TR35 honors young innovators who are poised to have a dramatic impact on the world as we know it," says Jason Pontin, editor-in-chief and publisher.

That impact has already become apparent since Treuille joined the computer science faculty at Carnegie Mellon in 2008, where he is inspired by his colleagues and students to keep breaking new ground in computer graphics. "It's just this amazing thing to be able to work with these colleagues who all have a computer science 'superpower' and to want to have a 'superpower' too, and to join forces with them and 'fight evil,' scientifically," he says.

At Carnegie Mellon, Treuille is continuing his work on Foldit and is now collaborating with researchers at Stanford University to expand into new realms of biology. They are working on a game that would invite online players to simulate the evolution of ribonucleic acid (RNA) and explore the beginnings of life.

In addition, Treuille recently was awarded a five-year, $549,000 Faculty Early Career Development (CAREER) Award from the National Science Foundation to make the tool of model reduction more powerful and flexible. Right now, even small changes to simulation parameters require scientists to rerun all calculations, making it impossible to create rich physical models on the fly. He also hopes to apply model reduction to a broader range of physics-based phenomena such as deformable objects under fluids—think of a flag flapping in the wind—and even molecular dynamics and cosmology.

"Ultimately, there's the potential to take all parts of the world and come up with efficient techniques to simulate them," Treuille says. "And what's most amazing about physical simulation is that it allows us to see the world anew and understand how it works, to realize how far we've come and how far we still have to go."

These are big ideas with big implications. But their beauty remains rooted in the small details. Air flowing around a speeding car. Proteins folding in the body. People crossing a street. A hot cup of coffee. A wrinkled shirt.

Jennifer Bails is an award-winning former newspaper reporter. She is a regular contributor to this magazine.

Back to Top ^

TalkBack

Leave a comment about the story

Comments are moderated and will be published at the moderator's discretion.

Thank you for your comment it has been submited for review.