Analysis of complex geometric models made simple

Rapid improvements in sensor technology have generated vast amounts of new geometric information, from scans of ancient architectural sites to the internal organs of humans. But analyzing that mountain of data, whether it's determining if a building is structurally sound or how oxygen flows through the lungs, has become a computational chokepoint.

"The data has become a monster," said Keenan Crane, assistant professor of computer science and robotics. "Suddenly, you have more data than you can possibly analyze -- or even care about."

Crane and Rohan Sawhney, a Ph.D. student in the Computer Science Department, are taming the monster by using so-called Monte Carlo methods to simulate how particles, heat and other things move through or within a complex shape. The process eliminates the need to painstakingly divide shapes into meshes -- collections of small geometric elements that can be computationally analyzed. The researchers will present their method at the SIGGRAPH 2020 Conference on Computer Graphics and Interactive Techniques, which will be held virtually in July.

"Building meshes is a minefield of possible errors," said Sawhney, the lead author. "If just one element is distorted, it can throw off the entire computation. Eliminating the need for meshes is pretty huge for a lot of industries."

Meshing was also a tough problem for filmmakers trying to create photorealistic animations in the 1990s. Not only was meshing laborious and slow, but the results didn't look natural. Their solution was to add randomness to the process by simulating light rays that could bounce around a scene. The result was beautifully realistic lighting, rather than flat-looking surfaces and blocky shadows.

Likewise, Crane and Sawhney have embraced randomness in geometric analysis. They aren't bouncing light rays through structures, but they are using Monte Carlo methods to imagine how particles, fluids or heat randomly interact and move through space. First developed in the 1940s and 1950s for the U.S. nuclear weapons program, Monte Carlo methods are a class of algorithms that use randomness in an ordered way to produce numerical results.

Crane and Sawhney's work revives a little-used "walk on spheres" algorithm that makes it possible to simulate a particle's long, random walk through a space without determining each twist and turn. Instead, they calculate the size of the largest empty space around the particle -- in the lung, for instance, that would be the width of a bronchial tube -- and make that the diameter of each sphere. The program can then just jump from one random point on each sphere to the next to simulate the random walk.

While it might take a day just to build a mesh of a geometric space, the CMU approach allows users to get a rough preview of the solution in just a few seconds. This preview can then be refined by taking more and more random walks.

"That means one doesn't have to sit around, waiting for the analysis to be completed to get the final answer," Sawhney said. "Instead, the analysis is incremental, providing engineers with immediate feedback. This translates into more time doing and less time banging one's head against the wall trying to understand why the analysis isn't working."

Sawhney and Crane are working with industry partners to expand the kinds of problems that can be solved with their methods. The National Science Foundation, Packard Fellowship, Sloan Foundation, Autodesk, Adobe, Disney and Facebook provided support for this work.