The digital age has spurred the rise of entire industries aimed at simulating our world and the objects in it. Simulation is what helps movies have realistic effects, automakers test cars virtually, and scientists analyze geophysical data.
To simulate physical systems in 3D, researchers often program computers to divide objects into sets of smaller elements, a procedure known as “meshing.” Most meshing approaches tile 2D objects with patterns of triangles or quadrilaterals (quads), and tile 3D objects with patterns of triangular pyramids (tetrahedra) or bent cubes (hexahedra, or “hexes”).
While much progress has been made in the fields of computational geometry and geometry processing, scientists surprisingly still don’t fully understand the math of stacking together cubes when they are allowed to bend or stretch a bit. Many questions remain about the patterns that can be formed by gluing cube-shaped elements together, which relates to an area of math called topology.
New work out of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) aims to explore several of these questions. Researchers have published a series of papers that address shortcomings of existing meshing tools by seeking out mathematical structure in the problem. In collaboration with scientists at the University of Bern and the University of Texas at Austin, their work shows how areas of math like algebraic geometry, topology, and differential geometry could improve physical simulations used in computer-aided design (CAD), architecture, gaming, and other sectors.
“Simulation tools that are being deployed ‘in the wild’ don’t always fail gracefully,” says MIT Associate Professor Justin Solomon, senior author on the three new meshing-related papers. “If one thing is wrong with the mesh, the simulation might not agree with real-world physics, and you might have to throw the whole thing out.”
In one paper, a team led by MIT undergraduate Zoë Marschner developed an algorithm to repair issues that can often trip up existing approaches for hex meshing, specifically.
For example, some meshes contain elements that are partially inside-out or that self-intersect in ways that can’t be detected from their outer surfaces. The team’s algorithm works in iterations to repair those meshes in a way that untangles any such inversions while remaining faithful to the original shape.
“Thorny unsolved topology problems show up all over the hex-meshing universe,” says Marschner. “Until we figure them out, our algorithms will often fail in subtle ways.”
Marschner’s algorithm uses a technique called “sum-of-squares (SOS) relaxation” to pinpoint exactly where hex elements are inverted (which researchers describe as being “invalid”). It then moves the vertices of the hex element so that the hex is valid at the point where it was previously most invalid. The algorithm repeats this procedure to repair the hex.
In addition to being published at this week’s Symposium on Geometry Processing, Marschner’s work earned her MIT’s 2020 Anna Pogosyants UROP Award.
A second paper spearheaded by PhD student Paul Zhang improves meshing by incorporating curves, edges, and other features that provide important cues for the human visual system and pattern recognition algorithms.
It can be difficult for computers to find these features reliably, let alone incorporate them into meshes. By using an existing construction called an “octahedral frame field” that is traditionally used for meshing 3D volumes, Zhang and his team have been able to develop 2D surface meshes without depending on unreliable methods that try to trace out features ahead of time.
Zhang says that they’ve shown that these so-called “feature-aligned” constructions automatically create visually accurate quad meshes, which are widely used in computer graphics and virtual reality applications.
“As the goal of meshing is to simultaneously simplify the object and maintain accuracy to the original domain, this tool enables a new standard in feature-aligned quad meshing,” says Zhang.
A third paper led by PhD student David Palmer links Zhang and Marschner’s work, advancing the theory of octahedral fields and showing how better math provides serious practical improvement for hex meshing.
In physics and geometry, velocities and flows are represented as “vector fields,” which attach an arrow to every point in a region of space. In 3D, these fields can twist, knot around, and cross each other in remarkably complicated ways. Further complicating matters, Palmer’s research studies the structure of “frame fields,” in which more than one arrow appears at each point.
Palmer’s work gives new insight into the ways frames can be described and uses them to design methods for placing frames in 3D space. Building off of existing work, his methods produce smooth, stable fields that can guide the design of high-quality meshes.
Solomon says that his team aims to eventually characterize all the ways that octahedral frames twist and knot around each other to create structures in space.
“This is a cool area of computational geometry where theory has a real impact on the quality of simulation tools,” says Solomon.
Palmer cites organizations like Sandia National Labs that conduct complicated physical simulations involving phenomena like nonlinear elasticity and object deformation. He says that, even today, engineering teams often build or repair hex meshes almost completely by hand.
“Existing software for automatic meshing often fails to produce a complete mesh, even if the frame field guidance ensures that the mesh pieces that are there look good,” Palmer says. “Our approach helps complete the picture.”
Marschner’s paper was co-written by Solomon, Zhang, and Palmer. Zhang’s paper was co-written by Solomon, Josh Vekhter, and Etienne Vouga at the University of Texas at Austin, Professor David Bommes of the University of Bern in Germany, and CSAIL postdoc Edward Chien. Palmer’s paper was co-written by Solomon and Bommes. Zhang and Palmer’s papers will be presented at the SIGGRAPH computer graphics conference later this month.
The projects were supported, in part, by Adobe Systems, the U.S. Air Force Office of Scientific Research, the U.S. Army Research Office, the U.S. Department of Energy, the Fannie and John Hertz Foundation, MathWorks, the MIT-IBM Watson AI Laboratory, the National Science Foundation, the Skoltech-MIT Next Generation program, and the Toyota-CSAIL Joint Research Center.