Sandia LabNews

Automating complex 3D modeling

Sandia-developed software could save hours of manual labor

Mohamed Ebeida looks at geometric models
NOVEL PROCESS — Sandia computer scientist Mohamed Ebeida worked with a team to develop VoroCrust, a software program that creates meshes using polyhedral cells rather than tetrahedral and hexahedral cells. (Photo by Randy Montoya)

A team of researchers led by Sandia has invented a first-of-its-kind software for scientists to create accurate digital representations of complex objects.

The new software, VoroCrust, offers a novel way to create digital representations, called meshes, used by scientists in many disciplines to create geometric models of all kinds of parts, from rotors to wheels to protective equipment.

Complex meshes often have curves, sharp edges or holes. Once created, they look like 3D images used in computer simulations that incorporate algorithms to determine when parts might fail in extreme conditions. This is a helpful — and often essential — aspect of design that precedes the creation of prototypes and parts for testing.

For example, a scientist in the aerospace industry might make a mesh of an airplane wing and run it through a computer simulation to learn more about what will happen to it in high wind and extreme temperatures. Some scientists also use meshes to model geology to anticipate underground changes, such as subsurface flows of liquids or contaminants.

VoroCrust incorporates a special type of 3D polyhedral cells, called Voronoi cells, to create the meshes, said Sandia computer scientist and project lead Mohamed Ebeida. Most other mesh-generation methods use 3D tetrahedral or hexahedral cells that can have low quality or are difficult to automate, he said.

Existing methods for Voronoi meshing don’t always conform to all corners and angles of complex objects. This can be fixed with manual labor, but it is a tedious process that can take a significant number of work hours, Mohamed said. VoroCrust is the first software to generate Voronoi-cell meshes that conform to complex models without needing to be fixed manually.

Mohamed has been working on the software for more than three years and said it could reduce many hours of manual labor that scientists currently spend on 3D modeling.

“Sandia identified meshing as the single biggest bottleneck in these analyses. Current practices require human intervention, and VoroCrust provides us with a path toward automating this process to relieve tech staff by reducing the time spent on fixing computer-generated errors in modeling,” he said.

A recent manuscript describing VoroCrust has been reviewed and accepted in Transaction on Graphics. It will be presented at SIGGRAPH 2020, a top computer graphics conference, Mohamed said, adding that “this is quite an honor.”

The software was developed in collaboration with the University of Maryland, College Park; the University of Texas, Austin; and the University of California, Davis.

How VoroCrust works

In 3D modeling, analysts create meshes that look like geometric shells around the objects they need to analyze. Ideally, the mesh will look exactly like the object and conform to all edges, but that’s not always easy using current meshing techniques.

Common meshing methods typically use the tetrahedral and hexahedral cells to fill the space of an object, moving from the object’s interior toward its outside boundaries. However, problems occur when the cells do not conform to the shape near the boundary. Manually fixing this problem is not always reliable and sometimes changes the mathematical properties of the final model, Mohamed said.

geometric models
SAVING TIME — These images show 3D models created using VoroCrust, the first software program to generate Voronoi-cell meshes that don’t need to be fixed manually. (Images courtesy of Sandia National Laboratories)

One way to imagine the meshing process is to think of filling a mattress. Tetrahedral “cushions” could fill the space easily, but they might be too firm. Hexahedral cushions could be more flexible but might not follow the edges along the top or corners, due to their fixed structure. Using flexible material like a polyhedron that can have an arbitrary number of sides could make it easier to fill all areas and corners of the mattress.

To fully automate the meshing process, Mohamed’s team not only used polyhedrons, they also reversed the standard approach and found a way to start at the boundary, rather than the middle, of a 3D model. The team carefully placed points, called seeds, around the boundaries of geometric objects, which then became footholds for Voronoi cells. Once the outside of the boundary is complete, the interior of the object can be filled in with additional Voronoi cells.

Ahmed Abdelkader, a doctoral student at the University of Maryland, worked on VoroCrust with Mohamed and described the advantages of using Voronoi cells.

“The facets are cleaner, like gemstones or diamonds,” he said. “They can perfectly and naturally fit together.”

Curves present challenges, Abdelkader said, using the examples of bowls and more complex objects like engines. He said it took a lot of work to pin down the necessary ingredient that would set the pieces together perfectly in a mathematical proof. Now, he said, the team is excited to build upon this deeper understanding to enhance the software with more features.

“The Voronoi magic will happen,” Mohamed said. “Once you decompose the object into these well-shaped pieces — these cells — you can mesh any model you want with confidence about the quality of the resulting mesh without any post-processing.”

Wide use for government, industry

When working on VoroCrust, the goal was to create a software robust enough that it could model any object needed for simulation, said Ahmed Mahmoud, a University of California doctoral student who worked on the software.

geometric model of geological layers
SUBSURFACE MODELS — This image shows a VoroCrust mesh for a geological model with seven layers. Scientists at Sandia and Los Alamos national laboratories have used the software to make geological models as part of their research related to the geological disposal of spent nuclear fuel and high-level nuclear waste. (Image courtesy of Sandia and Los Alamos national laboratories)

Sandia manager Emily Stein and research engineer Tara LaForce have used VoroCrust to make geological models for deep disposal of nuclear waste as part of DOE’s spent fuel and waste science and technology campaign, which Sandia leads. The VoroCrust project receives funding from the DOE campaign and from Sandia’s Laboratory Directed Research and Development program.

Two priorities of the campaign are to create design concepts and numerical modeling approaches for disposal systems. VoroCrust might create a mesh of an underground repository and the waste in it, or it could create a mesh of the underground geology. This mesh can then be used to solve the subsurface flow of liquid or gas in porous material or the transport of contaminants within flowing fluids.

Tara said VoroCrust offers promising capabilities for creating a mesh that can run in a reasonable timeframe. Emily added that other meshing methods sometimes distort the mesh, creating a simulation that is not as accurate as it could be.

“The idea is that we could take the geological model as it is and run it without additional manipulation,” Tara said.

Carl Gable, who leads the computational earth sciences group at Los Alamos National Laboratory, has also used VoroCrust to create geological models as part of the campaign.

“If you’re making an airplane, submarine or car, one of the first steps is building the computational framework you’re trying to represent,” Gable said. “In our case, it’s geology. We need to represent tunnels, canisters and waste packages, and we also need to represent the natural system — the geological system — and VoroCrust is a tool that is good at doing that.”

Achieving technical readiness

Mohamed said while the research problem of creating geometric meshes with Voronoi cells has been solved, the technical readiness of the software is not at a place where it could be used off-the-shelf.

Sandia manager Joe Bishop, who has been interested in VoroCrust for years, said modeling and simulation engineers on his team could benefit from the software for simulations if current software packages can leverage the polyhedral elements.

“We need to know if we can run our simulations on these objects and compare it to tetrahedral and hexahedral methods,” he said. “VoroCrust is a promising tool. It could provide the geometry, and we would do the physics.”

Research licenses

VoroCrust is currently being tested by a few other government agencies and universities. The software has been awarded one patent, and two additional patent applications have been filed. Research licenses are available through Sandia’s Intellectual Property office. Visit to learn more.