3D scanners such as LiDAR are increasingly being used to capture 3D surfaces for both individual objects, like the Digital Michelangelo Project, and larger scenes—as in Resonai’s building and cityscape reconstructions for enhanced AR experiences, or even the surface of Mars via NASA’s Explore with Perseverance platform. The scanners used in these applications output a series of 3D points in space called a “point cloud,” which is then reconstructed into solid surfaces by computer algorithms. But as point cloud datasets grow larger and larger, current computing capabilities are limiting these algorithms’ abilities to reconstruct watertight surfaces, or surfaces without gaps and inconsistencies.
In collaboration with retired industry partner Hugues Hoppe, Misha Kazhdan, a professor of computer science, proposes a solution in a new paper appearing in Computer Graphics Forum, the official journal of Eurographics, the European Association for Computer Graphics. They present an efficient version of a commonly used surface reconstruction algorithm that is able to be distributed across a cluster of PCs, making it possible to reconstruct incredibly large surfaces in a fraction of the time.
Screened Poisson surface reconstruction is an algorithm that efficiently creates meshes from oriented point sets with resilience against noise and missing data. But for large datasets, the technique requires hours of computation and significant memory usage—and the larger these datasets grow, the more the algorithm begins to lag in its ability to generate large surfaces at scale.
To address this problem, Kazhdan and Hoppe propose a way to distribute the reconstruction algorithm’s computations across several PCs in a way that still produces a global solution. This reduces individual computational load without sacrificing the end result’s watertightness and resiliency against sampling noise.
Their method, called “Distributed Poisson Surface Reconstruction,” involves separating a desired surface reconstruction into low- and high-resolution components. The low-resolution reconstruction is completed by a single PC, whereas the high-resolution rendering is split into portions and distributed across a cluster of machines. Each individual computer refines its assigned section of the point cloud, called a “slab,” which overlaps slightly with the slabs on either side of it to “pad” the section and allow for seamless integration back into the full reconstruction.
In simpler terms, one computer estimates a low-resolution reconstruction, while the other computers are responsible for refining that estimation within their assigned slabs, the researchers explain.
The overlap between slabs gives each individual computer a “sense of what its neighbors are trying to do,” Kazhdan explains. “Combined, these two components ensure that when fusing the individually refined geometries, there is next to no work that needs to be done to ensure that they come together seamlessly, creating a single watertight surface.”
Because it distributes computation and minimizes inter-computer communication, Distributed Poisson Surface Reconstruction scales almost linearly with the number of computers it’s run on, according to the team. As an example, the reconstruction of Michelangelo’s “David” statue from a dataset made up of approximately one billion points used to take about a day to complete on a single PC—but takes only 20 minutes via their new reconstruction method when distributed across a cluster of 65 machines.
The team’s next steps involve exploring nested distributed solvers to further reduce memory utilization.
“We believe that the ability to localize computation is an essential step in opening the door to real-time, high-quality surface reconstruction,” Kazhdan says. “Because it would allow for interactive user guidance in terms of scan configuration, this would be a game-changer for 3D surface scanning and reconstruction.”