“RXMesh: a GPU mesh data structure” by Mahmoud, Porumbescu and Owens

We propose a new static high-performance mesh data structure for triangle surface meshes on the GPU. Our data structure is carefully designed for parallel execution while capturing mesh locality and confining data access, as much as possible, within the GPU’s fast “shared memory.” We achieve this by subdividing the mesh into patches and representing these patches compactly using a matrix-based representation. Our patching technique is decorated with ribbons, thin mesh strips around patches that eliminate the need to communicate between different computation thread blocks, resulting in consistent high throughput. We call our data structure RXMesh: Ribbon-matriX Mesh. We hide the complexity of our data structure behind a flexible but powerful programming model that helps deliver high performance by inducing load balance even in highly irregular input meshes. We show the efficacy of our programming model on common geometry processing applications—mesh smoothing and filtering, geodesic distance, and vertex normal computation. For evaluation, we benchmark our data structure against well-optimized GPU and (single and multi-core) CPU data structures and show significant speedups.

1. Saman Ashkiani. 2017. Parallel Algorithms and Dynamic Data Structures on the Graphics Processing Unit: a warp-centric approach. Ph.D. Dissertation. University of California, Davis. https://escholarship.org/uc/item/5qd0r4wsGoogle Scholar
2. Saman Ashkiani, Andrew A. Davidson, Ulrich Meyer, and John D. Owens. 2017. GPU Multisplit: an extended study of a parallel algorithm. ACM Transactions on Parallel Computing 4, 1 (Aug. 2017), 2:1–2:44. Google ScholarDigital Library
3. Saman Ashkiani, Martin Farach-Colton, and John D. Owens. 2018. A Dynamic Hash Table for the GPU. In Proceedings of the 32nd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2018). 419–429. Google ScholarCross Ref
4. Muhammad A. Awad, Saman Ashkiani, Serban D. Porumbescu, and John D. Owens. 2020. Dynamic Graphs on the GPU. In Proceedings of the 34th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2020). 739–748. Google ScholarCross Ref
5. Bruce G. Baumgart. 1972. Winged Edge Polyhedron Representation. Technical Report STAN-CS-72-320. Stanford University Computer Science Department, Stanford, CA, USA. https://apps.dtic.mil/dtic/tr/fulltext/u2/755141.pdfGoogle Scholar
6. Gilbert Louis Bernstein, Chinmayee Shah, Crystal Lemire, Zachary Devito, Matthew Fisher, Philip Levis, and Pat Hanrahan. 2016. Ebb: A DSL for Physical Simulation on CPUs and GPUs. ACM Trans. Graph. 35, 2, Article 21 (May 2016), 12 pages. Google ScholarDigital Library
7. M. Botsch, S. Steinberg, S. Bischoff, and L. Kobbelt. 2002. OpenMesh – a generic and efficient polygon mesh data structure. In 1st OpenSG Symposium. https://www.graphics.rwth-aachen.de/media/papers/openmesh1.pdfGoogle Scholar
8. Aydın Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. 2016. Recent Advances in Graph Partitioning. Springer International Publishing, 117–158. Google ScholarCross Ref
9. Swen Campagna, Leif Kobbelt, and Hans-Peter Seidel. 1998. Directed Edges—A Scalable Representation for Triangle Meshes. Journal of Graphics Tools 3, 4 (Dec. 1998), 1–11. Google ScholarDigital Library
10. Nathan A. Carr, Jared Hoberock, Keenan Crane, and John C. Hart. 2006. Rectangular Multi-Chart Geometry Images. In Symposium on Geometry Processing (SGP06). 181–190. Google ScholarCross Ref
11. David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2004. Variational Shape Approximation. ACM Transactions on Graphics 23, 3 (Aug. 2004), 905–914. Google ScholarDigital Library
12. Narcís Coll and Marité Guerrieri. 2017. Parallel Constrained Delaunay Triangulation on the GPU. International Journal of Geographical Information Science 31, 7 (July 2017), 1467–1484. Google ScholarDigital Library
13. Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H. Barr. 1999. Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’99). ACM Press/Addison-Wesley Publishing Co., USA, 317–324. Google ScholarDigital Library
14. Antonio DiCarlo, Alberto Paoluzzi, and Vadim Shapiro. 2014. Linear algebraic representation for topological structures. Computer-Aided Design 46 (2014), 269–274. 2013 SIAM Conference on Geometric and Physical Modeling. Google ScholarDigital Library
15. Vladimir Dyedov, Navamita Ray, Daniel Einstein, Xiangmin Jiao, and Timothy J. Tautges. 2015. AHF: array-based half-facet data structure for mixed-dimensional and non-manifold meshes. Engineering with Computers 31, 3 (July 2015), 389–404. Google ScholarDigital Library
16. Shachar Fleishman, Iddo Drori, and Daniel Cohen-Or. 2003. Bilateral Mesh Denoising. ACM Transactions on Graphics 22, 3 (July 2003), 950–953. Google ScholarDigital Library
17. Leonidas Guibas and Jorge Stolfi. 1985. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi. ACM Transactions on Graphics 4, 2 (April 1985), 74–123. Google ScholarDigital Library
18. Yuanming Hu, Tzu-Mao Li, Luke Anderson, Jonathan Ragan-Kelley, and Frédo Durand. 2019. Taichi: A Language for High-Performance Computation on Spatially Sparse Data Structures. ACM Transactions on Graphics 38, 6 (Nov. 2019), 201:1–201:16. Google ScholarDigital Library
19. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.Google Scholar
20. Alan D. Kalvin and Russell H. Taylor. 1996. Superfaces: Polygonal Mesh Simplification with Bounded Error. IEEE Computer Graphics and Applications 16, 3 (May 1996), 64–77. Google ScholarDigital Library
21. Bernhard Kerbl, Michael Kenzel, Elena Ivanchenko, Dieter Schmalstieg, and Markus Steinberger. 2018. Revisiting The Vertex Cache: Understanding and Optimizing Vertex Processing on the Modern GPU. Proceedings of the ACM on Computer Graphics and Interactive Techniques 1, 2, Article 29 (Aug. 2018), 16 pages. Google ScholarDigital Library
22. Lutz Kettner. 2019. Halfedge Data Structures. In CGAL User and Reference Manual (4.14 ed.). CGAL Editorial Board. https://doc.cgal.org/4.14/Manual/packages.html#PkgHalfedgeDSGoogle Scholar
23. Stuart P. Lloyd. 1982. Least Squares Quantization in PCM. IEEE Transactions on Information Theory 28, 2 (March 1982), 129–137. Google ScholarDigital Library
24. Yu Lu and Harrison H. Zhou. 2016. Statistical and Computational Guarantees of Lloyd’s Algorithm and its Variants. arXiv:1612.02099v1 [math.ST]Google Scholar
25. M. Mäntylä. 1988. Introduction to Solid Modeling. W. H. Freeman & Co., New York, NY, USA.Google Scholar
26. Nelson Max. 1999. Weights for Computing Vertex Normals from Facet Normals. Journal of Graphics Tools 4, 2 (March 1999), 1–6. Google ScholarDigital Library
27. Robert Ryan McCune, Tim Weninger, and Greg Madey. 2015. Thinking Like a Vertex: A Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing. Comput. Surveys 48, 2, Article 25 (Oct. 2015), 39 pages. Google ScholarDigital Library
28. D. Mlakar, M. Winter, P. Stadlbauer, H.-P. Seidel, M. Steinberger, and R. Zayer. 2020. Subdivision-Specialized Linear Algebra Kernels for Static and Dynamic Mesh Connectivity on the GPU. Computer Graphics Forum 39, 2 (2020), 335–349. Google ScholarCross Ref
29. J. S. Mueller-Roemer, C. Altenhofen, and A. Stork. 2017. Ternary Sparse Matrix Representation for Volumetric Mesh Subdivision and Processing on GPUs. Computer Graphics Forum 36, 5 (2017), 59–69. Google ScholarDigital Library
30. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral Conformal Parameterization, In Proceedings of the Symposium on Geometry Processing. Computer Graphics Forum, 1487–1494. Google ScholarDigital Library
31. Rahul Narain, Armin Samii, and James F. O’Brien. 2012. Adaptive Anisotropic Remeshing for Cloth Simulation. ACM Transactions on Graphics 31, 6 (Nov. 2012), 152:1–152:10. Google ScholarDigital Library
32. Maxim Naumov and Timothy Moon. 2016. Parallel Spectral Graph Partitioning. Technical Report NVR-2016-001. NVIDIA Research. https://research.nvidia.com/publication/parallel-spectral-graph-partitioning.Google Scholar
33. Luciano A. Romero Calla, Lizeth J. Fuentes Perez, and Anselmo A. Montenegro. 2019. A minimalistic approach for fast computation of geodesic distances on triangular meshes. Computers & Graphics 84 (2019), 77–92. Google ScholarDigital Library
34. J. Rossignac. 2001. 3D compression made simple: Edgebreaker with Zip&Wrap on a Corner-Table. In Proceedings of the International Conference on Shape Modeling and Applications. 278–283. Google ScholarCross Ref
35. H. Schäfer, B. Keinert, M. Nießner, and M. Stamminger. 2014. Local Painting and Deformation of Meshes on the GPU. Computer Graphics Forum 34, 1 (Aug. 2014), 26–35. Google ScholarDigital Library
36. Kirk Schloegel, George Karypis, and Vipin Kumar. 1997. Parallel Multilevel Diffusion Algorithms for Repartitioning of Adaptive Meshes. Technical Report 97-014. University of Minnesota, Department of Computer Science. http://glaros.dtc.umn.edu/gkhome/node/87.Google Scholar
37. Jonathan Richard Shewchuk. 1994. An introduction to the conjugate gradient method without the agonizing pain. https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdfGoogle Scholar
38. Smithsonian Institution Digitization Program Office. 2020. Smithsonian 3D Digitization. https://3d.si.edu/.Google Scholar
39. Robert F. Tobler and Stefan Maierhofer. 2006. A Mesh Data Structure for Rendering and Subdivision. In Proceedings of WSCG (International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision). 157–162. http://www.vrvis.at/publications/PB-VRVis-2006-007Google Scholar
40. Yangzihao Wang, Yuechao Pan, Andrew Davidson, Yuduo Wu, Carl Yang, Leyuan Wang, Muhammad Osama, Chenshan Yuan, Weitang Liu, Andy T. Riffel, and John D. Owens. 2017. Gunrock: GPU Graph Analytics. ACM Transactions on Parallel Computing 4, 1 (Aug. 2017), 3:1–3:49. Google ScholarDigital Library
41. Martin Winter, Daniel Mlakar, Rhaleb Zayer, Hans-Peter Seidel, and Markus Steinberger. 2018. faimGraph: High Performance Management of Fully-Dynamic Graphs Under Tight Memory Constraints on the GPU. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC ’18). Article 60, 13 pages. Google ScholarDigital Library
42. Yizhou Yu, Kun Zhou, Dong Xu, Xiaohan Shi, Hujun Bao, Baining Guo, and Heung-Yeung Shum. 2004. Mesh Editing with Poisson-Based Gradient Field Manipulation. ACM Transactions on Graphics 23, 3 (Aug. 2004), 644–651. Google ScholarDigital Library
43. Rhaleb Zayer, Markus Steinberger, and Hans-Peter Seidel. 2017. A GPU-adapted Structure for Unstructured Grids. In Computer Graphics Forum (Proceedings of Eurographics 2017), Vol. 36. 495–507. Issue 2. Google ScholarDigital Library
44. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. CoRR (May 2016). arXiv:cs.GR/1605.04797Google Scholar