Monte Carlo method dispenses with troublesome meshes
Researchers at Carnegie Mellon University have developed an efficient new way to quickly analyze complex geometric models by borrowing a computational approach that has made photorealistic animated films possible.
Carnegie Mellon University researchers have shown complex shapes need not be divided into intricate meshes, left, to perform geometric analysis. Instead of spending 14 hours creating a mesh, they use Monte Carlo methods to get initial results in less than a minute of the amount of heat radiated from an ant's body, center. Additional computation further refines the results, right.
Credit: Carnegie Mellon University
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.
Byron Spice | EurekAlert!
New method for simulating yarn-cloth patterns to be unveiled at ACM SIGGRAPH
09.07.2020 | Association for Computing Machinery
Virtual Reality Environments for the Home Office
09.07.2020 | Universität Stuttgart
New insight into the spin behavior in an exotic state of matter puts us closer to next-generation spintronic devices
Aside from the deep understanding of the natural world that quantum physics theory offers, scientists worldwide are working tirelessly to bring forth a...
Kiel physics team observed extremely fast electronic changes in real time in a special material class
In physics, they are currently the subject of intensive research; in electronics, they could enable completely new functions. So-called topological materials...
Solar cells based on perovskite compounds could soon make electricity generation from sunlight even more efficient and cheaper. The laboratory efficiency of these perovskite solar cells already exceeds that of the well-known silicon solar cells. An international team led by Stefan Weber from the Max Planck Institute for Polymer Research (MPI-P) in Mainz has found microscopic structures in perovskite crystals that can guide the charge transport in the solar cell. Clever alignment of these "electron highways" could make perovskite solar cells even more powerful.
Solar cells convert sunlight into electricity. During this process, the electrons of the material inside the cell absorb the energy of the light....
Empa researchers have succeeded in applying aerogels to microelectronics: Aerogels based on cellulose nanofibers can effectively shield electromagnetic radiation over a wide frequency range – and they are unrivalled in terms of weight.
Electric motors and electronic devices generate electromagnetic fields that sometimes have to be shielded in order not to affect neighboring electronic...
A promising operating mode for the plasma of a future power plant has been developed at the ASDEX Upgrade fusion device at Max Planck Institute for Plasma...
07.07.2020 | Event News
02.07.2020 | Event News
19.05.2020 | Event News
10.07.2020 | Life Sciences
10.07.2020 | Materials Sciences
10.07.2020 | Life Sciences