“Sum-of-squares geometry processing” by Marschner, Zhang, Palmer and Solomon
Conference:
Type(s):
Title:
- Sum-of-squares geometry processing
Session/Category Title: Geometry Processing and Simulation
Presenter(s)/Author(s):
Abstract:
Geometry processing presents a variety of difficult numerical problems, each seeming to require its own tailored solution. This breadth is largely due to the expansive list of geometric primitives, e.g., splines, triangles, and hexahedra, joined with an ever-expanding variety of objectives one might want to achieve with them. With the recent increase in attention toward higher-order surfaces, we can expect a variety of challenges porting existing solutions that work on triangle meshes to work on these more complex geometry types. In this paper, we present a framework for solving many core geometry processing problems on higher-order surfaces. We achieve this goal through sum-of-squares optimization, which transforms nonlinear polynomial optimization problems into sequences of convex problems whose complexity is captured by a single degree parameter. This allows us to solve a suite of problems on higher-order surfaces, such as continuous collision detection and closest point queries on curved patches, with only minor changes between formulations and geometries.
References:
1. Amir Ahmadi, Georgina Hall, Ameesh Makadia, and Vikas Sindhwani. 2017. Geometry of 3D Environments and Sum of Squares Polynomials.
2. Farid Alizadeh. 1995. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization 5, 1 (1995), 13–51.
3. Robert E. Barnhill, Gerald Farin, M. Jordan, and Bruce R. Piper. 1987. Surface/surface intersection. Computer Aided Geometric Design 4, 1-2 (1987), 3–16.
4. Grigoriy Blekherman, Pablo A. Parrilo, and Rekha R. Thomas. 2012. Semidefinite Optimization and Convex Algebraic Geometry. SIAM.
5. Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.
6. David Cardoze, Alexandre Cunha, Gary L. Miller, Todd Phillips, and Noel Walkington. 2004. A bezier-based approach to unstructured moving meshes. In Proceedings of the twentieth annual symposium on Computational geometry. 310–319.
7. Edwin Catmull and James Clark. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-aided design 10, 6 (1978), 350–355.
8. Zhongshi Jiang, Ziyi Zhang, Yixin Hu, Teseo Schneider, Denis Zorin, and Daniele Panozzo. 2021. Bijective and Coarse High-Order Tetrahedral Meshes. ACM Transactions on Graphics (2021).
9. Kęstutis Karčiauskas and Jörg Peters. 2020. Low degree splines for locally quad-dominant meshes. Computer Aided Geometric Design 83 (2020), 101934.
10. Sebastian Koch, Albert Matveev, Zhongshi Jiang, Francis Williams, Alexey Artemov, Evgeny Burnaev, Marc Alexa, Denis Zorin, and Daniele Panozzo. 2019. ABC: A big cad model dataset for geometric deep learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 9601–9611.
11. Jean B. Lasserre. 2001. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization 11, 3 (2001), 796–817.
12. Johan Löfberg. 2004. YALMIP: A Toolbox for Modeling and Optimization in MATLAB. In In Proceedings of the CACSD Conference. Taipei, Taiwan.
13. Charles Loop. 1987. Smooth subdivision surfaces based on triangles. Master’s thesis, University of Utah, Department of Mathematics (1987).
14. Manish Mandad and Marcel Campen. 2020. Bézier guarding: precise higher-order meshing of curved 2D domains. ACM Transactions on Graphics (TOG) 39, 4 (2020), 103–1.
15. Zoë Marschner, David Palmer, Paul Zhang, and Justin Solomon. 2020. Hexahedral Mesh Repair via Sum-of-Squares Relaxation. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 133–147.
16. MOSEK ApS. 2017. The MOSEK optimization toolbox for MATLAB manual. Version 8.1. http://docs.mosek.com/8.1/toolbox/index.html
17. Yurii Nesterov and Arkadii Nemirovskii. 1994. Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics.
18. Young-Taek Oh, Yong-Joon Kim, Jieun Lee, Myung-Soo Kim, and Gershon Elber. 2012. Efficient point-projection to freeform curves and surfaces. Computer Aided Geometric Design 29, 5 (2012), 242–254.
19. Pablo A. Parillo. 2019. Algebraic Techniques and Semidefinite Optimization. https://learning-modules.mit.edu/materials/index.html?uuid=/course/6/sp19/6.256#materials.
20. Diana Pekerman, Gershon Elber, and Myung-Soo Kim. 2008. Self-intersection detection and elimination in freeform curves and surfaces. Computer-Aided Design 40, 2 (2008), 150–159.
21. Stephen Prajna, Antonis Papachristodoulou, and Pablo A. Parrilo. 2002. Introducing SOSTOOLS: A general purpose sum of squares programming solver. In Proceedings of the 41st IEEE Conference on Decision and Control, 2002., Vol. 1. IEEE, 741–746.
22. Mihai Putinar. 1993. Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal 42, 3 (1993), 969–984.
23. Rohan Sawhney and Keenan Crane. 2020. Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-Based Methods on Volumetric Domains. ACM Trans. Graph. 39, 4 (2020).
24. Teseo Schneider, Jérémie Dumas, Xifeng Gao, Mario Botsch, Daniele Panozzo, and Denis Zorin. 2019. Poly-Spline Finite-Element Method. ACM Trans. Graph. 38, 3, Article 19 (March 2019), 16 pages.
25. Teseo Schneider, Yixin Hu, Jérémie Dumas, Xifeng Gao, Daniele Panozzo, and Denis Zorin. 2018. Decoupling Simulation Accuracy from Mesh Quality. ACM Transactions on Graphics 37, 6 (10 2018).
26. Dmitriy Smirnov, Mikhail Bessmeltsev, and Justin Solomon. 2020a. Learning Manifold Patch-Based Representations of Man-Made Shapes, In International Conference on Learning Representations. arXiv preprint arXiv:1906.12337.
27. Dmitriy Smirnov, Matthew Fisher, Vladimir G. Kim, Richard Zhang, and Justin Solomon. 2020b. Deep parametric shape predictions using distance fields. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 561–570.
28. Michael J Todd. 2016. Minimum-volume ellipsoids: Theory and algorithms. SIAM.
29. Kim-Chuan Toh, Michael J. Todd, and Reha H. Tütüncü. 2001. SDPT3—a Matlab software package for semidefinite-quadratic-linear programming, version 3.0. Web page http://www.math.nus.edu.sg/mattohkc/sdpt3.html (2001).
30. Ty Trusty, Honglin Chen, and David I.W. Levin. 2021. The Shape Matching Element Method: Direct Animation of Curved Surface Models. ACM Transactions on Graphics (2021).
31. Anna Wawrzinek, Klaus Hildebrandt, and Konrad Polthier. 2011. Koiter’s Thin Shells on Catmull-Clark Limit Surfaces. In Vision, Modeling, and Visualization (2011), Peter Eisert, Joachim Hornegger, and Konrad Polthier (Eds.). The Eurographics Association.
