In the realm of computer graphics and computer-aided design (CAD), 3D objects are typically represented by their outer surface contours. These objects are stored as “thin shells” in computer systems, capturing the shape of an animated character’s skin but not the underlying flesh, such as bones, tendons, and muscles.
While this modeling approach allows for efficient storage and manipulation of 3D shapes, it can lead to unexpected anomalies. For example, when a character’s fingers bend, their hand might crumple in a manner reminiscent of an empty rubber glove, rather than realistically mimicking the motion of a hand with internal structures. These disparities pose challenges when developing mapping algorithms that establish connections between different shapes.
To address these limitations, researchers at MIT have devised a novel technique that aligns 3D shapes by mapping volumes to volumes, instead of surfaces to surfaces. Their approach involves representing shapes as tetrahedral meshes, which account for the internal mass within a 3D object. By manipulating the corners of tetrahedra in a source shape, their algorithm determines how to stretch and move them to achieve alignment with a target shape.
The incorporation of volumetric information in this technique enables more accurate modeling of fine details in an object, circumventing the twisting and inversion issues prevalent in surface-based mapping. By switching from surfaces to volumes, the “rubber glove” analogy can be extended to envelop the entire hand, resulting in geometric mapping that closely approximates physical reality.
Lead author Mazdak Abulnaga, an electrical engineering and computer science (EECS) graduate student, explains, “Switching from surfaces to volumes stretches the rubber glove over the whole hand. Our method brings geometric mapping closer to physical reality.”
The technique developed by Abulnaga and his collaborators outperforms baseline methods in aligning shapes, yielding high-quality shape maps with reduced distortion compared to existing alternatives. The algorithm is particularly effective for challenging mapping scenarios involving geometrically distinct input shapes, such as mapping a smooth rabbit to a LEGO-style rabbit composed of cubes.
The applications of this technique span various graphics domains. For instance, it can be employed to transfer the motions of a previously animated 3D character to a new 3D model or scan. Additionally, the same algorithm can transfer textures, annotations, and physical properties between different 3D shapes. These applications extend beyond visual computing and have implications for computational manufacturing and engineering.
The paper documenting this research, authored by Mazdak Abulnaga, Oded Stein (formerly of MIT and now at the University of Southern California), Polina Golland, and Justin Solomon, will be presented at the ACM SIGGRAPH conference in August. The findings are also available in the ACM Transactions on Graphics journal.
Shaping an algorithm
When Abulnaga initiated the project, his goal was to expand surface-based algorithms to enable volumetric shape mapping. However, their initial attempts proved unsuccessful or yielded implausible maps. Recognizing the need for new mathematics and algorithms, the team realized the challenges involved in volume mapping.
Conventional mapping algorithms typically operate by minimizing an “energy” that quantifies the deformation of a shape when transformed, stretched, compressed, or sheared into another shape. These energy functions often draw inspiration from physics, which employs similar equations to model the behavior of elastic materials like gelatin.
Despite improving the energy in Abulnaga’s mapping algorithm to better capture volume physics, the method did not produce viable mappings. The team identified a key reason for this failure: many physical energies, as well as most mapping algorithms, lack symmetry.
In the new research, the team focused on developing a symmetric approach where the order of input shapes does not affect the results. There is no distinction between a “source” and a “target” when creating the map. For instance, mapping a horse onto a giraffe should yield the same results as mapping a giraffe onto a horse. However, many mapping algorithms yield inferior outcomes when the wrong shape is designated as the source or target, and this disparity is more pronounced in volumetric mapping.
Abulnaga emphasized that most mapping algorithms do not employ symmetric energies. He explained, “Choosing the right energy for your algorithm can produce more realistic maps.”
Typical energy functions used in shape alignment are designed to map in a single direction. When researchers attempt to apply them bidirectionally to create a symmetric map, these energies no longer behave as expected. Furthermore, the behavior of these energies differs when applied to surfaces versus volumes.
Based on their discoveries, Abulnaga and his collaborators established a mathematical framework that enables researchers to evaluate the behavior of different energies and determine which ones to select for creating a symmetric map between two objects. Leveraging this framework, they developed a mapping algorithm that combines energy functions for two objects in a manner that guarantees symmetry throughout the process.
In this algorithm, users input two shapes represented as tetrahedral meshes, and the algorithm computes bidirectional maps that define how each corner of each tetrahedron should move to achieve shape alignment.
Abulnaga emphasized the significance of energy in the mapping process, stating, “The energy is the cornerstone of this mapping process. The model aims to align the two shapes, and the energies prevent unexpected alignments from occurring.”
Achieving accurate alignments
During testing, the researchers observed that their approach generated superior maps compared to other volume-based methods. The resulting maps exhibited better alignment, higher quality, and reduced distortion, even when focusing solely on the outer surface.
However, the researchers also identified certain scenarios where their method encountered difficulties. For instance, the algorithm struggled when aligning shapes that required significant changes in volume, such as mapping a shape with a filled interior to one with a cavity.
In addition to addressing this limitation, the researchers aim to optimize the algorithm to enhance its computational efficiency. They are also working on extending the method to medical applications by incorporating MRI signals alongside shape data. This integration can facilitate the convergence of mapping techniques used in medical computer vision and computer graphics.
Joel Haas, a distinguished professor in the Department of Mathematics at the University of California, Davis, who was not involved in this research, commented on the significance of the algorithm’s theoretical underpinnings: “A theoretical analysis of symmetry drives the development of this algorithm and shows that symmetric shape comparison methods tend to have better performance in comparing and aligning objects. Alignments based exclusively on surface data can lead to collapsed volumes, as occasionally happened to Wile E. Coyote in the ‘Road Runner’ cartoons. A range of experiments shows that the new algorithm has remarkable success in maintaining interior consistency while aligning a pair of 3D objects. It gives a good correspondence throughout the interior as well as on the boundary.”