“The shape space of discrete orthogonal geodesic nets”
Conference:
Type(s):
Title:
- The shape space of discrete orthogonal geodesic nets
Session/Category Title: Nets, cages and meshes
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Discrete orthogonal geodesic nets (DOGs) are a quad mesh analogue of developable surfaces. In this work we study continuous deformations on these discrete objects. Our main theoretical contribution is the characterization of the shape space of DOGs for a given net connectivity. We show that generally, this space is locally a manifold of a fixed dimension, apart from a set of singularities, implying that DOGs are continuously deformable. Smooth flows can be constructed by a smooth choice of vectors on the manifold’s tangent spaces, selected to minimize a desired objective function under a given metric. We show how to compute such vectors by solving a linear system, and we use our findings to devise a geometrically meaningful way to handle singular points. We base our shape space metric on a novel DOG Laplacian operator, which is proved to converge under sampling of an analytical orthogonal geodesic net. We further show how to extend the shape space of DOGs by supporting creases and curved folds and apply the developed tools in an editing system for developable surfaces that supports arbitrary bending, stretching, cutting, (curved) folds, as well as smoothing and subdivision operations.
References:
1. M. Alexa and M. Wardetzky. 2011. Discrete Laplacians on general polygonal meshes. ACM Trans. Graph. 30, 4 (2011). Google ScholarDigital Library
2. A. I. Bobenko and P. Schröder. 2005. Discrete Willmore Flow. In Proc. Symposium on Geometry Processing. http://dl.acm.org/citation.cfm?id=1281920.1281937 Google ScholarDigital Library
3. A. I. Bobenko and Y. B. Suris. 2008. Discrete differential geometry: integrable structure. Graduate studies in mathematics, Vol. 98. American Mathematical Society, Providence (R.I.).Google Scholar
4. S. Bouaziz, M. Deuss, Y. Schwartzburg, T. Weise, and M. Pauly. 2012. Shape-up: Shaping discrete geometry with projections. Comput. Graph. Forum 31, 5 (2012), 1657–1667. Google ScholarDigital Library
5. S. Bouaziz, S. Martin, T. Liu, L. Kavan, and M. Pauly. 2014. Projective dynamics: fusing constraint projections for fast simulation. ACM Trans. Graph. 33, 4 (2014). Google ScholarDigital Library
6. R. Burgoon, Z. J. Wood, and E. Grinspun. 2006. Discrete Shells Origami. In Computers and Their Applications.Google Scholar
7. K. Crane, U. Pinkall, and P. Schröder. 2013. Robust fairing via conformal curvature flow. ACM Trans. Graph. 32, 4 (2013). Google ScholarDigital Library
8. T. A. Davis. 2011. Algorithm 915, SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization. ACM Transactions on Mathematical Software (TOMS) 38, 1 (2011), 8. Google ScholarDigital Library
9. A. De Coninck, B. De Baets, D. Kourounis, F. Verbosio, O. Schenk, S. Maenhout, and J. Fostier. 2016. Needles: Toward Large-Scale Genomic Prediction with Marker-by-Environment Interaction. Genetics 203, 1 (2016), 543–555. arXiv:http://www.genetics.org/content/203/1/543.full.pdfGoogle Scholar
10. E. D. Demaine, M. L. Demaine, V. Hart, G. N. Price, and T. Tachi. 2011a. (Non) existence of pleated folds: how paper folds between creases. Graphs and Combinatorics 27, 3 (2011), 377–397. Google ScholarDigital Library
11. E. D. Demaine, M. L. Demaine, D. Koschitz, and T. Tachi. 2011b. Curved crease folding: a review on art, design and mathematics. In Proceedings of the IABSE-IASS Symposium: Taller, Longer, Lighter. 20–23.Google Scholar
12. E. D. Demaine and J. O’Rourke. 2007. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press. Google ScholarDigital Library
13. M. Desbrun, M. Meyer, P. Schröder, and A. H. Barr. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In Proc. ACM SIGGRAPH. 317–324. Google ScholarDigital Library
14. M. P. do Carmo. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall.Google Scholar
15. I. Eckstein, J.-P. Pons, Y. Tong, C.-C. Kuo, and M. Desbrun. 2007. Generalized surface flows for mesh processing. In Proc. Symposium on Geometry Processing. 183–192. Google ScholarDigital Library
16. S. Fröhlich and M. Botsch. 2011. Example-Driven Deformations Based on Discrete Shells. Comput. Graph. Forum 30, 8 (2011), 2246–2257.Google ScholarCross Ref
17. D. Fuchs and S. Tabachnikov. 1999. More on paperfolding. The American Mathematical Monthly 106, 1 (1999), 27–35.Google ScholarCross Ref
18. W. C. Graustein. 1917. On the geodesics and geodesic circles on a developable surface. Annals of Mathematics 18, 3 (1917), 132–138.Google ScholarCross Ref
19. R. F. Harik, H. Gong, and A. Bernard. 2013. 5-axis flank milling: A state-of-the-art review. Computer-Aided Design 45, 3 (2013), 796–808. Google ScholarDigital Library
20. B. Heeren, M. Rumpf, P. Schröder, M. Wardetzky, and B. Wirth. 2014. Exploring the geometry of the space of shells. Comput. Graph. Forum 33, 5 (2014), 247–256.Google ScholarDigital Library
21. B. Heeren, M. Rumpf, P. Schröder, M. Wardetzky, and B. Wirth. 2016. Splines in the space of shells. Comput. Graph. Forum 35, 5 (2016), 111–120.Google ScholarCross Ref
22. T. Hoffmann. 2009. Discrete differential geometry of curves and surfaces. COE Lecture Notes 18 (2009).Google Scholar
23. D. A. Huffman. 1976. Curvature and creases: a primer on paper. IEEE Trans. Computers 25, 10 (1976), 1010–1019. Google ScholarDigital Library
24. M. Kazhdan, J. Solomon, and M. Ben-Chen. 2012. Can mean-curvature flow be modified to be non-singular? Comput. Graph. Forum 31, 5 (2012), 1745–1754. Google ScholarDigital Library
25. M. Kilian, S. Flöry, Z. Chen, N. J. Mitra, A. Sheffer, and H. Pottmann. 2008. Curved folding. ACM Trans. Graph. 27, 3 (2008), 75:1–75:9. Google ScholarDigital Library
26. M. Kilian, N. J. Mitra, and H. Pottmann. 2007. Geometric modeling in shape space. ACM Trans. Graph. 26, 3 (2007). Google ScholarDigital Library
27. M. Kilian, A. Monszpart, and N. J. Mitra. 2017. String actuated curved folded surfaces. ACM Trans. Graph. 36, 3 (2017), 25:1–25:13. Google ScholarDigital Library
28. D. Kourounis, A. Fuchs, and O. Schenk. 2018. Towards the Next Generation of Multiperiod Optimal Power Flow Solvers. IEEE Transactions on Power Systems PP, 99 (2018), 1–10.Google Scholar
29. Y. Liu, H. Pottmann, J. Wallner, Y.-L. Yang, and W. Wang. 2006. Geometric modeling with conical meshes and developable surfaces. ACM Trans. Graph. 25, 3 (2006). Google ScholarDigital Library
30. J. Mitani and T. Igarashi. 2011. Interactive design of planar curved folding by reflection. In Proc. Pacific Graphics, Short Papers.Google Scholar
31. MOSEK ApS. 2017. The MOSEK optimization toolbox for MATLAB manual. Version 8.1. http://docs.mosek.com/8.1/toolbox/index.htmlGoogle Scholar
32. R. Narain, T. Pfaff, and J. F. O’Brien. 2013. Folding and Crumpling Adaptive Sheets. ACM Trans. Graph. 32, 4 (2013). Google ScholarDigital Library
33. J. Nocedal. 1980. Updating quasi-Newton matrices with limited storage. Math. Comp. 35, 151 (1980), 773–782.Google ScholarCross Ref
34. J. Nocedal and S. J. Wright. 2006. Sequential quadratic programming. Springer.Google Scholar
35. Y. Peng, B. Deng, J. Zhang, F. Geng, W. Qin, and L. Liu. 2018. Anderson Acceleration for Geometry Optimization and Physics Simulation. ACM Trans. Graph. 37, 4, Article 42 (July 2018), 14 pages. Google ScholarDigital Library
36. U. Pinkall and K. Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1 (1993), 15–36.Google ScholarCross Ref
37. H. Pottmann and J. Wallner. 2001. Computational line geometry. Springer, Berlin, Heidelberg, New York. Google ScholarDigital Library
38. M. Rabinovich, T. Hoffmann, and O. Sorkine-Hornung. 2018. Discrete Geodesic Nets for Modeling Developable Surfaces. ACM Trans. Graph. 37, 2 (2018), 16. Google ScholarDigital Library
39. T. W. Sederberg, P. Gao, G. Wang, and H. Mu. 1993. 2-D shape blending: an intrinsic solution to the vertex path problem. In Proc. ACM SIGGRAPH. 15–18. Google ScholarDigital Library
40. J. Solomon, E. Vouga, M. Wardetzky, and E. Grinspun. 2012. Flexible developable surfaces. Comput. Graph. Forum 31, 5 (2012), 1567–1576. Google ScholarDigital Library
41. O. Sorkine and M. Alexa. 2007. As-rigid-as-possible surface modeling. In Proc. Symposium on Geometry Processing. 109–116. Google ScholarDigital Library
42. O. Stein, E. Grinspun, and K. Crane. 2018. Developability of triangle meshes. ACM Trans. Graph. 37, 4 (2018). Google ScholarDigital Library
43. G. Sundaramoorthi, A. Yezzi, and A. C. Mennucci. 2007. Sobolev active contours. International Journal of Computer Vision 73, 3 (2007), 345–366. Google ScholarDigital Library
44. T. Tachi. 2009. Simulation of rigid origami. Origami 4 (2009), 175–187.Google ScholarCross Ref
45. C. Tang, P. Bo, J. Wallner, and H. Pottmann. 2016. Interactive design of developable surfaces. ACM Trans. Graph. 35, 2, Article 12 (2016), 12 pages. Google ScholarDigital Library
46. F. Verbosio, A. D. Coninck, D. Kourounis, and O. Schenk. 2017. Enhancing the scalability of selected inversion factorization algorithms in genomic prediction. Journal of Computational Science 22, Supplement C (2017), 99 — 108.Google Scholar
47. M. Wardetzky. 2007. Discrete differential operators on polyhedral surfaces – convergence and approximation. Ph.D. Dissertation. Freie Universität Berlin.Google Scholar
48. M. Wardetzky, S. Mathur, F. Kälberer, and E. Grinspun. 2007. Discrete Laplace operators: no free lunch. In Proc. Symposium on Geometry Processing. 33–37. Google ScholarDigital Library
49. Y.-L. Yang, Y.-J. Yang, H. Pottmann, and N. J. Mitra. 2011. Shape space exploration of constrained meshes. ACM Trans. Graph. 30, 6 (2011). Google ScholarDigital Library
