Nav: Home

Analysis of complex geometric models made simple

June 29, 2020

PITTSBURGH--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.

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.

Carnegie Mellon University

Related Data Articles:

Data centers use less energy than you think
Using the most detailed model to date of global data center energy use, researchers found that massive efficiency gains by data centers have kept energy use roughly flat over the past decade.
Storing data in music
Researchers at ETH Zurich have developed a technique for embedding data in music and transmitting it to a smartphone.
Life data economics: calling for new models to assess the value of human data
After the collapse of the blockchain bubble a number of research organisations are developing platforms to enable individual ownership of life data and establish the data valuation and pricing models.
Geoscience data group urges all scientific disciplines to make data open and accessible
Institutions, science funders, data repositories, publishers, researchers and scientific societies from all scientific disciplines must work together to ensure all scientific data are easy to find, access and use, according to a new commentary in Nature by members of the Enabling FAIR Data Steering Committee.
Democratizing data science
MIT researchers are hoping to advance the democratization of data science with a new tool for nonstatisticians that automatically generates models for analyzing raw data.
Getting the most out of atmospheric data analysis
An international team including researchers from Kanazawa University used a new approach to analyze an atmospheric data set spanning 18 years for the investigation of new-particle formation.
Ecologists ask: Should we be more transparent with data?
In a new Ecological Applications article, authors Stephen M. Powers and Stephanie E.
Should you share data of threatened species?
Scientists and conservationists have continually called for location data to be turned off in wildlife photos and publications to help preserve species but new research suggests there could be more to be gained by sharing a rare find, rather than obscuring it, in certain circumstances.
Futuristic data storage
The development of high-density data storage devices requires the highest possible density of elements in an array made up of individual nanomagnets.
Making data matter
The advent of 3-D printing has made it possible to take imaging data and print it into physical representations, but the process of doing so has been prohibitively time-intensive and costly.
More Data News and Data Current Events

Trending Science News

Current Coronavirus (COVID-19) News

Top Science Podcasts

We have hand picked the top science podcasts of 2020.
Now Playing: TED Radio Hour

Listen Again: Meditations on Loneliness
Original broadcast date: April 24, 2020. We're a social species now living in isolation. But loneliness was a problem well before this era of social distancing. This hour, TED speakers explore how we can live and make peace with loneliness. Guests on the show include author and illustrator Jonny Sun, psychologist Susan Pinker, architect Grace Kim, and writer Suleika Jaouad.
Now Playing: Science for the People

#565 The Great Wide Indoors
We're all spending a bit more time indoors this summer than we probably figured. But did you ever stop to think about why the places we live and work as designed the way they are? And how they could be designed better? We're talking with Emily Anthes about her new book "The Great Indoors: The Surprising Science of how Buildings Shape our Behavior, Health and Happiness".
Now Playing: Radiolab

The Third. A TED Talk.
Jad gives a TED talk about his life as a journalist and how Radiolab has evolved over the years. Here's how TED described it:How do you end a story? Host of Radiolab Jad Abumrad tells how his search for an answer led him home to the mountains of Tennessee, where he met an unexpected teacher: Dolly Parton.Jad Nicholas Abumrad is a Lebanese-American radio host, composer and producer. He is the founder of the syndicated public radio program Radiolab, which is broadcast on over 600 radio stations nationwide and is downloaded more than 120 million times a year as a podcast. He also created More Perfect, a podcast that tells the stories behind the Supreme Court's most famous decisions. And most recently, Dolly Parton's America, a nine-episode podcast exploring the life and times of the iconic country music star. Abumrad has received three Peabody Awards and was named a MacArthur Fellow in 2011.