“Differentiable surface triangulation” by Rakotosaona, Aigerman, Mitra, Ovsjanikov and Guerrero
Conference:
Type(s):
Title:
- Differentiable surface triangulation
Session/Category Title: Curves and Surfaces
Presenter(s)/Author(s):
Abstract:
Triangle meshes remain the most popular data representation for surface geometry. This ubiquitous representation is essentially a hybrid one that decouples continuous vertex locations from the discrete topological triangulation. Unfortunately, the combinatorial nature of the triangulation prevents taking derivatives over the space of possible meshings of any given surface. As a result, to date, mesh processing and optimization techniques have been unable to truly take advantage of modular gradient descent components of modern optimization frameworks. In this work, we present a differentiable surface triangulation that enables optimization for any per-vertex or per-face differentiable objective function over the space of underlying surface triangulations. Our method builds on the result that any 2D triangulation can be achieved by a suitably perturbed weighted Delaunay triangulation. We translate this result into a computational algorithm by proposing a soft relaxation of the classical weighted Delaunay triangulation and optimizing over vertex weights and vertex locations. We extend the algorithm to 3D by decomposing shapes into developable sets and differentiably meshing each set with suitable boundary constraints. We demonstrate the efficacy of our method on various planar and surface meshes on a range of difficult-to-optimize objective functions. Our code can be found online: https://github.com/mrakotosaon/diff-surface-triangulation.
References:
1. Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016. Tensorflow: A system for large-scale machine learning. In 12th {USENIX} symposium on operating systems design and implementation ({OSDI} 16). 265–283.
2. Pierre Alliez, Giuliana Ucelli, Craig Gotsman, and Marco Attene. 2008. Recent advances in remeshing of surfaces. Shape analysis and structuring (2008), 53–82.
3. Franz Aurenhammer. 1987. Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16, 1 (1987), 78–96.
4. Matthew Berger, Andrea Tagliasacchi, Lee M Seversky, Pierre Alliez, Gael Guennebaud, Joshua A Levine, Andrei Sharf, and Claudio T Silva. 2017. A survey of surface reconstruction from point clouds. In Computer Graphics Forum, Vol. 36. 301–329.
5. Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud, and Mariette Yvinec. 2000. Triangulations in CGAL. In Proc. SoCG. 11–18.
6. Eric Brachmann, Alexander Krull, Sebastian Nowozin, Jamie Shotton, Frank Michel, Stefan Gumhold, and Carsten Rother. 2017. Dsac-differentiable ransac for camera localization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 6684–6692.
7. Frédéric Cazals and Joachim Giesen. 2004. Delaunay triangulation based surface reconstruction: ideas and algorithms. Ph.D. Dissertation. INRIA.
8. Long Chen and Michael Holst. 2011. Efficient mesh optimization schemes based on optimal Delaunay triangulations. Computer Methods in Applied Mechanics and Engineering 200, 9-12 (2011), 967–984.
9. S.-W Cheng, Tamal Dey, and J.R. Shewchuk. 2016. Delaunay mesh generation. 1–386 pages.
10. Xiao-Xiang Cheng, Xiao-Ming Fu, Chi Zhang, and Shuangming Chai. 2019. Practical error-bounded remeshing by adaptive refinement. Computers & Graphics 82 (2019), 163–173.
11. Paolo Cignoni, Marco Callieri, Massimiliano Corsini, Matteo Dellepiane, Fabio Ganovelli, and Guido Ranzuglia. 2008. Meshlab: an open-source mesh processing tool.. In Eurographics Italian chapter conference, Vol. 2008. Salerno, Italy, 129–136.
12. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. 2000. Computational Geometry: Algorithms and Applications. Springer-Verlag. 367 pages.
13. Fernando De Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue noise through optimal transport. ACM Transactions on Graphics (TOG) 31, 6 (2012), 1–11.
14. Fernando De Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power particles: an incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4 (2015), 50–1.
15. Boris Delaunay et al. 1934. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7, 793-800 (1934), 1–2.
16. 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. 317–324.
17. Olivier Devillers. 2002. The delaunay hierarchy. International Journal of Foundations of Computer Science 13, 02 (2002), 163–180.
18. Olivier Devillers, Sylvain Pion, and Monique Teillaud. 2001. Walking in a triangulation. In Proc. SoCG. 106–114.
19. Ulrich Dierkes, Stefan Hildebrandt, and Friedrich Sauvigny. 2010. Minimal surfaces. In Minimal Surfaces. Springer, 53–90.
20. Qiang Du, Max D Gunzburger, and Lili Ju. 2003. Constrained centroidal Voronoi tessellations for surfaces. SIAM Journal on Scientific Computing 24, 5 (2003), 1488–1506.
21. Marion Dunyach, David Vanderhaeghe, Loïc Barthe, and Mario Botsch. 2013. Adaptive remeshing for real-time mesh deformation. In Eurographics 2013. The Eurographics Association.
22. Ramsay Dyer, Hao Zhang, and Torsten Möller. 2007. Delaunay mesh construction. In Proceedings of the fifth Eurographics symposium on Geometry processing. 273–282.
23. Matthew Fisher, Boris Springborn, Peter Schröder, and Alexander I Bobenko. 2007. An algorithm for the construction of intrinsic Delaunay triangulations with applications to digital geometry processing. Computing 81, 2-3 (2007), 199–213.
24. Xiao-Ming Fu, Yang Liu, John Snyder, and Baining Guo. 2014. Anisotropic Simplicial Meshing Using Local Convex Functions. ACM Trans. Graph. 33, 6, Article 182 (Nov. 2014), 11 pages.
25. Yan Fu and Bingfeng Zhou. 2009. Direct sampling on surfaces for high quality remeshing. Computer Aided Geometric Design 26, 6 (2009), 711 — 723. Solid and Physical Modeling 2008.
26. Michael Garland and Paul S Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques. 209–216.
27. David Glickenstein. 2005. Geometric triangulations and discrete Laplacians on manifolds. arXiv preprint math/0508188 (2005).
28. Fernando de Goes, Pooran Memari, Patrick Mullen, and Mathieu Desbrun. 2014. Weighted triangulations for geometry processing. ACM Transactions on Graphics (TOG) 33, 3 (2014), 1–13.
29. Thibault Groueix, Matthew Fisher, Vladimir G Kim, Bryan C Russell, and Mathieu Aubry. 2018. A papier-mâché approach to learning 3d surface generation. In Proceedings of the IEEE conference on computer vision and pattern recognition. 216–224.
30. Rana Hanocka, Amir Hertz, Noa Fish, Raja Giryes, Shachar Fleishman, and Daniel Cohen-Or. 2019. Meshcnn: a network with an edge. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–12.
31. 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.
32. Kaimo Hu, Dong-Ming Yan, David Bommes, Pierre Alliez, and Bedrich Benes. 2016. Error-bounded and feature preserving surface remeshing with minimal angle improvement. IEEE transactions on visualization and computer graphics 23, 12 (2016), 2560–2573.
33. Muhammad Hussain. 2009. Efficient simplification methods for generating high quality LODs of 3D meshes. Journal of Computer Science and Technology 24, 3 (2009), 604–604.
34. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant Field-Aligned Meshes. ACM Transactions on Graphics 34, 6 (2015), 189.
35. Dawar Khan, Alexander Plopski, Yuichiro Fujimoto, Masayuki Kanbara, Gul Jabeen, Yongjie Zhang, Xiaopeng Zhang, and Hirokazu Kato. 2020. Surface remeshing: A systematic literature review of methods and research directions. IEEE Transactions on Visualization and Computer Graphics (2020).
36. A. Khatamian and Hamid Arabnia. 2016. Survey on 3D Surface Reconstruction. Journal of Information Processing Systems 12 (01 2016), 338–357.
37. Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). http://arxiv.org/abs/1412.6980
38. Thibault Lescoat, Hsueh-Ti Derek Liu, Jean-Marc Thiery, Alec Jacobson, Tamy Boubekeur, and Maks Ovsjanikov. 2020. Spectral Mesh Simplification. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 315–324.
39. Bruno Lévy and Nicolas Bonneel. 2013. Variational anisotropic surface meshing with Voronoi parallel linear enumeration. In Proceedings of the 21st international meshing roundtable. Springer, 349–366.
40. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. ACM Trans. Graph. 21, 3 (July 2002), 362–371.
41. Yiyi Liao, Simon Donne, and Andreas Geiger. 2018. Deep marching cubes: Learning explicit surface representations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2916–2925.
42. Minghua Liu, Xiaoshuai Zhang, and Hao Su. 2020. Meshing Point Clouds with Predicted Intrinsic-Extrinsic Ratio Guidance. In European Conference on Computer Vision. Springer, 68–84.
43. Shichen Liu, Tianye Li, Weikai Chen, and Hao Li. 2019. Soft rasterizer: A differentiable renderer for image-based 3d reasoning. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 7708–7717.
44. Adrien Loseille. 2017. Unstructured mesh generation and adaptation. In Handbook of Numerical Analysis. Vol. 18. Elsevier, 263–302.
45. Shitong Luo and Wei Hu. 2021. Diffusion probabilistic models for 3d point cloud generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2837–2845.
46. Emilie Marchandise, Jean-François Remacle, and Christophe Geuzaine. 2014. Optimal parametrizations for surface remeshing. Engineering with Computers 30, 3 (2014), 383–402.
47. Riccardo Marin, Marie-Julie Rakotosaona, Simone Melzi, and Maks Ovsjanikov. 2020. Correspondence learning via linearly-invariant embedding. Advances in Neural Information Processing Systems 33 (2020).
48. Pooran Memari, Patrick Mullen, and Mathieu Desbrun. 2011. Parametrization of generalized primal-dual triangulations. In Proceedings of the 20th International Meshing Roundtable. Springer, 237–253.
49. Luca Morreale, Noam Aigerman, Vladimir Kim, and Niloy J. Mitra. 2021. Neural Surface Maps. arXiv:2103.16942 [cs.CV]
50. Patrick Mullen, Pooran Memari, Fernando de Goes, and Mathieu Desbrun. 2011. HOT: Hodge-optimized triangulations. In ACM SIGGRAPH 2011 papers. 1–12.
51. Andrew Nealen, Takeo Igarashi, Olga Sorkine, and Marc Alexa. 2006. Laplacian mesh optimization. In Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia. 381–389.
52. Andrew Y Ng, Michael I Jordan, Yair Weiss, et al. 2002. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems 2 (2002), 849–856.
53. Kok-Why Ng and Zhi-Wen Low. 2014. Simplification of 3d triangular mesh for level of detail computation. In 2014 11th International Conference on Computer Graphics, Imaging and Visualization. IEEE, 11–16.
54. Hiromu Ozaki, Fumihito Kyota, and Takashi Kanai. 2015. Out-of-core framework for QEM-based mesh simplification. In Proceedings of the 15th Eurographics Symposium on Parallel Graphics and Visualization. 87–96.
55. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint arXiv:1912.01703 (2019).
56. Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. 2017. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition. 652–660.
57. Marie-Julie Rakotosaona, Paul Guerrero, Noam Aigerman, Niloy J Mitra, and Maks Ovsjanikov. 2021. Learning Delaunay Surface Elements for Mesh Reconstruction. CVPR (2021).
58. Nicholas Sharp and Keenan Crane. 2020. You can find geodesic paths in triangle meshes by just flipping edges. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–15.
59. Nicholas Sharp and Maks Ovsjanikov. 2020. Pointtrinet: Learned triangulation of 3d point sets. In European Conference on Computer Vision. Springer, 762–778.
60. Vitaly Surazhsky and Craig Gotsman. 2003. Explicit surface remeshing. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing. 20–30.
61. Gabriel Taubin. 1995. A signal processing approach to fair surface design. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. 351–358.
62. Csaba D Toth, Joseph O’Rourke, and Jacob E Goodman. 2017. Handbook of discrete and computational geometry. CRC press.
63. Jane Tournois, Pierre Alliez, and Olivier Devillers. 2008. Interleaving Delaunay refinement and optimization for 2D triangle mesh generation. In Proceedings of the 16th international meshing roundtable. Springer, 83–101.
64. Sébastien Valette, Jean Marc Chassery, and Rémy Prost. 2008. Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams. IEEE Transactions on Visualization and Computer Graphics 14, 2 (2008), 369–381.
65. Xiaoning Wang, Xiang Ying, Yong-Jin Liu, Shi-Qing Xin, Wenping Wang, Xianfeng Gu, Wolfgang Mueller-Wittig, and Ying He. 2015. Intrinsic computation of centroidal Voronoi tessellation (CVT) on meshes. Computer-Aided Design 58 (2015), 51–61.
66. Jin Wei and Yu Lou. 2010. Feature preserving mesh simplification using feature sensitive metric. Journal of Computer Science and Technology 25, 3 (2010), 595–605.
67. Dong-Ming Yan, Guanbo Bao, Xiaopeng Zhang, and Peter Wonka. 2014. Low-resolution remeshing using the localized restricted Voronoi diagram. IEEE transactions on visualization and computer graphics 20, 10 (2014), 1418–1427.
68. Dong-Ming Yan, Bruno Lévy, Yang Liu, Feng Sun, and Wenping Wang. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. In Computer graphics forum, Vol. 28. Wiley Online Library, 1445–1454.
69. Dong-Ming Yan and Peter Wonka. 2015. Non-obtuse remeshing with centroidal Voronoi tessellation. IEEE transactions on visualization and computer graphics 22, 9 (2015), 2136–2144.
70. Weining Yue, Qingwei Guo, Jie Zhang, and Guoping Wang. 2007. 3D triangular mesh optimization in geometry processing for CAD. In Proceedings of the 2007 ACM symposium on Solid and physical modeling. 23–33.
71. Qingnan Zhou and Alec Jacobson. 2016. Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:1605.04797 (2016).
