Research drive could ‘untangle’ vexing problem in computer-simulation technology

LAWRENCE — The computer simulations used to design, optimize, test or control a vast range of objects and products in our daily lives are underpinned by finite element methods.

Finite element simulations use a mesh of geometric shapes — triangles, tetrahedra, quadrilaterals or hexahedra, for instance. These shapes can be combined to form a mesh that approximates the geometry of a model. For example, meshes can be used to model the human knee in biomechanics simulations, create computer-animated movies or help developers bring products, like airplanes and cars, from concept to production more quickly via better prototypes, testing and development.

“When you were a kid you played with LEGOs and thought about building different projects — like a house,” said Suzanne Shontz, associate professor of electrical engineering & computer science at the University of Kansas. “You were basically stacking blocks and building an object. Meshes are a lot like that — but they’re more flexible than cubes. We’re building with things like tetrahedra and hexahedra that you can combine to make different kinds of larger shapes. If you’re doing an airplane simulation, you’ll know the geometry of the airplane, and that determines with which shapes to build it.”

But a problem arises with finite element meshes, especially when they’re put into motion during a simulation: The shapes can tangle and overlap.

“The most common context for tangled meshes is a simulation involving motion,” Shontz said. “Suppose you have a two-dimensional mesh made of triangles. Now focus on one triangle and its three vertices. If one vertex is moved too far to the left with respect to the vertex to its left, this causes the orientation of the triangle to be flipped and triangles to overlap. A tangled mesh is one that contains elements with a mixture of orientations.”

The KU researcher said the use of a tangled mesh in a finite element simulation can lead to inaccurate results — with potentially disastrous consequences in biomechanical design, product development or large-deformation analysis.

“If you try to run such a simulation, you’ll get a physically invalid solution,” Shontz said. “That will cause a host of problems. Engineers need accurate solutions in making design decisions. With an airplane, the pilot will make decisions about how to fly the plane in turbulent weather; it’s crucial that these decisions are based on correct simulation results regarding the weather and the plane’s response. When making important medical decisions, a doctor needs to be able to trust that the simulation results for the disease progression or treatment are correct.”

For years, researchers have pursued a solution to the tangled mesh problem, proposing solutions like re-meshing, meshfree methods and the finite cell method. But no definitive answer has yet been developed.

With a new $250,000 award from the National Science Foundation, Shontz and her KU colleagues are working with a team at the University of Wisconsin-Madison headed by Krishnan Suresh, a professor of mechanical engineering, to explore new methods for addressing the tangled mesh problem. Suresh’s team received a similar $250,000 award from the National Science Foundation for their research. 

Shontz already has developed several promising untangling algorithms, but she said it has proven difficult to “completely” untangle a mesh. Working with Suresh, she said she hopes the collaboration might yield a breakthrough.

Under the new grant, Shontz’s group will create new constrained optimization methods for mesh untangling to convert “severely tangled meshes into mildly tangled meshes.” In the meantime, Suresh’s group will hone the finite-cell method to ensure accurate finite-element solutions over these mildly tangled meshes. 

“Our part at KU is to develop a method to untangle meshes so they can be used with standard finite element methods,” Shontz said. “At the University of Wisconsin-Madison, they’re coming up with a finite-element solver that can work on tangled meshes. We’re also looking at a hybrid solution that uses some of their research and some of ours.”

Among many biomechanics applications, the researchers hope their work could lead to improved untangling of finite element meshes used to model the brains of patients with hydrocephalus. In these patients, large ventricular displacements of the brain can be modeled with finite-element simulations — but the models often result in tangled meshes.

“With hydrocephalus, the brain has excess fluid buildup from cerebrospinal fluid,” Shontz said. “The brain changes shape due to the excess pressure that usually results within the skull. The idea is to be able to run simulations which will help doctors predict which surgery to perform. However, due to the nonlinear deformations of the brain ventricles, the meshes will often become tangled.”

As part of the work under the award, the investigators at KU and UW-Madison will exchange teaching modules in the form of prerecorded lectures to be used in graduate-level classes. Shontz will deliver lectures on mesh generation, smoothing, tangling and untangling to students at UW-Madison, while Suresh will provide lectures to KU students on geometric modeling and computational mechanics.

The researchers will also develop a Design, Analyze and Print Workshop to be offered to middle and high school students on the campuses of the two universities.

Graduate students also will receive support and training via the NSF grant.

“There’s funding for graduate-student salaries, faculty summer salary support, and conference travel,” Shontz said. “We’ll also do student exchanges. I’ll send a KU graduate student to Wisconsin for a few weeks, and they’ll send a student here, too. They’ll get exposed to new ideas, so it’s a great opportunity for students at both institutions.”

Top right images (bird and wheel): Untangling quadrilateral meshes using locally injective mappings. Images courtesy of Krishnan Suresh. Bottom right images: A close-up view of a tangled mesh and a close-up view of the mesh after untangling. Images courtesy of John Wiley & Sons Ltd.