“Lock-free Vertex Clustering for Multicore Mesh Reduction” by Fathollahi and Chester
Conference:
Type(s):
Title:
- Lock-free Vertex Clustering for Multicore Mesh Reduction
Session/Category Title: Embed to a Different Space
Presenter(s)/Author(s):
Abstract:
Modern 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.
References:
[1]
Jose Luis Blanco and Pranjal Kumar Rai. 2014. nanoflann: a C++ header-only fork of FLANN, a library for Nearest Neighbor (NN) with KD-trees. https://github.com/jlblancoc/nanoflann.
[2]
Guy E. Blelloch. 1990. Prefix Sums and Their Applications. Technical Report CMU-CS-90-190. School of Computer Science, Carnegie Mellon University.
[3]
Blender. 2023. Blender Software. https://github.com/blender.
[4]
City of Vancouver. 2019. LiDAR 2018. https://opendata.vancouver.ca/explore/dataset/lidar-2018/information/.
[5]
Christopher Decoro and Natalya Tatarchuk. 2007. Real-time mesh simplification using the GPU. 161–166. https://doi.org/10.1145/1230100.1230128
[6]
Maurice Herlihy and Jeannette M. Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst. 12, 3 (1990), 463–492. https://doi.org/10.1145/78969.78972
[7]
Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1993. Mesh optimization. In Proceedings of the 20th annual conference on Computer graphics and interactive techniques. 19–26.
[8]
Peter Lindstrom. 2000. Out-of-Core Simplification of Large Polygonal Models. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques(SIGGRAPH ’00). ACM Press/Addison-Wesley Publishing Co., USA, 259–262. https://doi.org/10.1145/344779.344912
[9]
Kok-Lim Low and Tiow-Seng Tan. 1997. Model Simplification Using Vertex-Clustering. In Proceedings of the 1997 Symposium on Interactive 3D Graphics (Providence, Rhode Island, USA) (I3D ’97). Association for Computing Machinery, New York, NY, USA, 75–ff.https://doi.org/10.1145/253284.253310
[10]
Mohamed Mousa and Mohamed Hussein. 2021. High-performance simplification of triangular surfaces using a GPU. PLOS ONE 16 (08 2021), e0255832. https://doi.org/10.1371/journal.pone.0255832
[11]
Marius Muja and David Lowe. 2009. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration.VISAPP 2009 – Proceedings of the 4th International Conference on Computer Vision Theory and Applications 1, 331–340.
[12]
Jarek Rossignac and Paul Borrel. 1993. Multi-resolution 3D approximation for rendering complex scenes. (01 1993), 455–465. https://doi.org/10.1007/978-3-642-78114-8_29
[13]
William Schroeder, Jonathan Zarge, and William Lorensen. 1997. Decimation of triangle meshes. SIGGRAPH Comput. Graph. 26 (06 1997), 65–70. https://doi.org/10.1145/133994.134010
[14]
Jerry O. Talton. 2004. A Short Survey of Mesh Simplification Algorithms.
[15]
The Foundry. 2023. Modo Software. https://www.foundry.com/products/modo.
[16]
Unity Technologies. 2023. Unity Software. https://github.com/Unity-Technologies.
[17]
Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).
[18]
Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun. 2018. Open3D: A Modern Library for 3D Data Processing. arXiv:1801.09847 (2018).
