Lock-free Vertex Clustering for Multicore Mesh Reduction
DescriptionModern data collection methods can capture representations of 3D objects at resolutions much greater than they can be discretely rendered as an image. To improve the efficiency of storage, transmission, rendering, and editing of 3D models constructed from such data, it is beneficial to first employ a mesh reduction technique to reduce the size of a mesh. Vertex clustering, a technique that merges close vertices together, has particularly wide applicability, because it operates only on vertices and their spatial proximity. However, it is also very difficult to accelerate with parallelisation in a deterministic manner because it contains extensive algorithmic dependencies.
Prior work treats the non-trivial clustering step of this process serially to preserve vertex priorities, which fundamentally limits to mid-single digits the acceleration rates that are possible for the process overall. This paper introduces a novel lock-free parallel algorithm, P-Weld, that exposes parallelism with a graph-theoretic lens that iteratively peels away layers of a mesh that have no remaining dependencies. Concurrent updates to shared data are managed with a linearisable sequence of atomic instructions that exactly reproduces the serial clustering. The resulting parallelism and improved spatial locality yield a 3.86× speed-up on a standard 14-million vertex mesh and a 2.93× speed-up on a 400-million vertex LiDaR point cloud covering the city of Vancouver, Canada, relative to a popular open source library.
Prior work treats the non-trivial clustering step of this process serially to preserve vertex priorities, which fundamentally limits to mid-single digits the acceleration rates that are possible for the process overall. This paper introduces a novel lock-free parallel algorithm, P-Weld, that exposes parallelism with a graph-theoretic lens that iteratively peels away layers of a mesh that have no remaining dependencies. Concurrent updates to shared data are managed with a linearisable sequence of atomic instructions that exactly reproduces the serial clustering. The resulting parallelism and improved spatial locality yield a 3.86× speed-up on a standard 14-million vertex mesh and a 2.93× speed-up on a 400-million vertex LiDaR point cloud covering the city of Vancouver, Canada, relative to a popular open source library.
Event Type
Technical Papers
TimeTuesday, 12 December 20239:30am - 12:45pm
LocationDarling Harbour Theatre, Level 2 (Convention Centre)
