Revisiting Fundamental Equations in Computer Graphics

The use of computer graphics has expanded beyond making realistic movie and video game effects to fields like architecture and robotics. As the field evolves, researchers continue to reformulate the basic components powering computer graphics in hopes of creating versions that are more efficient, expressive and in tune with the broader needs of science and engineering.

"Fundamental representations continue to be really important. How do you describe things to a computer? What's its model of the universe?" said Keenan Crane(opens in new window), a professor of computer science at Carnegie Mellon University’s School of Computer Science(opens in new window). "That's a question we've been asking for years and yet there's still so much to be explored."

"At its core, computer graphics is about coming up with representations of the world — and algorithms to go along with them — that enable accurate and efficient simulations of complex physical phenomena," said Ioannis Gkioulekas(opens in new window), a robotics professor at SCS. "This combination of accuracy and efficiency has allowed computer graphics in recent years to make inroads into scientific and engineering areas well beyond its traditional applications.”

SCS researchers recently demonstrated their boundary-pushing computer graphics work in Denver at the Association for Computing Machinery's Special Interest Group on Computer Graphics and Interactive Techniques(opens in new window) (SIGGRAPH) conference, the premier conference on computer graphics and interactive techniques.

Two projects from Crane, Gkioulekas and their collaborators received best paper award honors at the conference. The work sheds new light on a series of classic computer graphics problems, including reworking algorithms used to simulate physics on extremely detailed 3D models(opens in new window) and inventing new descriptions of solid objects(opens in new window) that provide better predictions about physical items and biology.

Using ideas from Hollywood to design robots on Mars

The paper "Walkin' Robin: Walk on Stars With Robin Boundary Conditions(opens in new window)," describes a method that can predict the temperature in a large building or on a complex piece of electronics by borrowing computer graphics principles used by Hollywood to light objects. The research team included Crane and Gkioulekas; Bailey Miller, a Ph.D. student in computer science; and Rohan Sawhney, who earned his Ph.D. in computer science at CMU and is now a senior research scientist at NVIDIA.

Hollywood uses lighting techniques like ray tracing and Monte Carlo rendering to create photorealistic images complete with shadows and highlights. These methods trace the path of light from its source as it interacts with objects.

"The entertainment industry has developed incredibly efficient and robust rendering algorithms for simulating the visual appearance of complex and realistic 3D models," Miller said. "Often, the 3D models used in film are so detailed and realistic that we cannot distinguish them from reality."

"What many people don't realize is that the equations used for movies are perfectly physically accurate. In fact, people use the same technology for lighting design in architecture," Crane said. "The algorithms that come from computer graphics are so good, you can know exactly how things will look before the building is actually built. Imagine if you could do the same thing for heating and air conditioning."

When it comes to designing a microchip or a rocket engine, the tools engineers use to understand a system's heating and cooling are much more limited. Current methods for simulating physics — like finite element analysis — require objects to be diced into millions of tiny triangles or pyramids that the computer can easily analyze. Engineers in turn invest a huge amount of time in meticulously "meshing," or generating a grid over every shape they want to use. But even with such an investment of time and resources, these meshed models often omit important details.

As a result, the status quo is to simplify models before simulation. But these simplifications can betray the reality of the situation. For instance, a tree in an urban planning model might be replaced with a simple sphere or a cube, even though its particular shape and size have a big effect on street temperature.

Miller and his co-authors want to change that.

"Our goal has been to enable the same kind of simulation technology found in the movies for physical effects beyond lighting. For example, to allow engineers and scientists to design systems where geometry can influence everything from temperature distribution to air flow," Miller said.

For example: Imagine sitting in an air-conditioned room with the hot sun hitting a window. How can the temperature at the room’s chair be predicted? Instead of light rays, "Walkin' Robin" uses many random "drunkard's walks" radiating from the chair to survey the temperature at different points of the room. The program can then immediately jump to a random point on a sphere. Miller and his co-authors observed that by replacing the sphere with other shapes, like a star, the basic algorithm can be applied to a much broader range of physical simulation problems with a complexity level much closer to reality.

"We no longer need to dice up the world into tiny pieces. We don't have to solve the meshing problem," Crane said. "As a result, you're freer to express the shape or the environment the way you want to and at an incredible level of detail."

As a test problem, the team looked at how different components on NASA's Mars rover might heat up while sitting under the Martian sun.

"In a tiny fraction of a second, you can get some feedback on how hot things could become. It's noisy and it's got some errors. But the longer you sit there, the better the answer becomes. And the simulation just works, no matter how bad the input model is," Gkioulekas said. "These are nice properties to have if you're trying to explore different designs and possibilities, compared to having to wait hours for an answer from the meshing process."

The shape of things to come

Drop a basketball on the ground and it bounces back, but computer models don't always get that right. Depending on how the computer encodes shape, the ball might merge with the floor like a water droplet hitting a pond or pass through the floor altogether.

In their paper, "Repulsive Shells(opens in new window)," Crane and researchers from Chemnitz University of Technology, the University of Bonn and École Normale Supérieure Paris-Saclay developed a new digital representation that makes it impossible for shapes to pass through themselves. For instance, if an animated character has their hands behind their back and needs to move into a fighting stance with fists raised, current algorithms might produce a bizarre solution where the hands pass straight through the abdomen. The team's new method provides a more natural solution, where the arms swing around the character's hips.

"Our goal is not only to stop collisions but also to get the computer to make more realistic predictions about how objects move around in the world," Crane said.

The algorithm is based on the physical law of electrostatic repulsion, which is the tiny force that pushes electrons away from each other so they don't collide. This force increases as objects approach each other. Crane and his team decided to stretch out space in regions where the forces are large, so it takes an infinite amount of time to reach a self-intersecting state.

"This is a lot like what happens if you watch a spaceship flying toward a black hole. It will get closer and closer, but can never quite get there," Crane said.

This otherworldly idea can be used to solve some down-to-earth problems, like animating the process of turning socks and pants right side out while folding laundry. Crane has also started collaborating with biologists to see if this kind of model can be used to make sense of the wide variety of shapes seen in biological cells. It might also help model how red blood cells pass through capillaries and what happens when biomembranes change shape due to sickle cell anemia. Repulsive shells could also be used to predict how shapes might change well into the future, like the evolution of an animal's body part over millions of years.

To get the answer right, Crane said, requires moving beyond the status quo.

"Real shapes don't pass through themselves," he said. "Beyond computer graphics, if you want to understand things happening in the physical or biological world, you need computational models that forbid intersections.