Automating complex 3-D modeling could save hours of manual labor

A team of researchers led by Sandia National Laboratories have 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, which are used by scientists in many disciplines that work with 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 3-D images that can be 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 prior to creating prototypes and parts for real tests.

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 special types of 3-D polyhedral cells called Voronoi cells to create the meshes, said Sandia computer scientist and project lead Mohamed Ebeida. Most other mesh-generation methods use 3-D 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, Ebeida said.

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

VoroCrust is the first software to generate Voronoi-cell meshes that conform to complex models without needing to be fixed manually, said Ebeida. He's been working on the software for more than three years and said the software could reduce many hours of manual labor that scientists spend on 3-D modeling.

"Sandia identified meshing as the single biggest bottleneck in these analyses," Ebeida said. "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."

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

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

How VoroCrust works

In 3-D 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, starting 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, Ebeida said.

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 arbitrary number of sides could make it easier to fill all areas and corners of the mattress.

Ebeida said to fully automate the meshing process, his 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 3-D model. The team carefully placed points, called seeds, around the boundaries of geometrical 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 Ebeida 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," Ebeida 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."

Software could have 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.

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 the Department of Energy's Spent Fuel and Waste Science and Technology Campaign that Sandia leads. In addition to the Laboratory Directed Research and Development program, the campaign contributes funding for VoroCrust development.

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 be then used to solve the subsurface flow of liquid or gas in porous material or the transport of contaminants within flowing fluids.

LaForce said VoroCrust offers promising capabilities for creating a mesh that can run in a reasonable timeframe. Stein 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," LaForce said.

Carl Gable, the leader of 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 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 represent the natural system, the geological system, and VoroCrust is a tool that is good at doing that."

Researchers working on technical readiness

Ebeida 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's 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."