“The shape space of discrete orthogonal geodesic nets” by Rabinovich, Hoffman and Sorkine-Hornung

  • ©Michael Rabinovich, Tom Hoffman, and Olga Sorkine-Hornung

Conference:


Type:


Title:

    The shape space of discrete orthogonal geodesic nets

Session/Category Title: Cutting, Zipping and Folding Surfaces

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). 
    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 
    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.).
    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. 
    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). 
    6. R. Burgoon, Z. J. Wood, and E. Grinspun. 2006. Discrete Shells Origami. In Computers and Their Applications.
    7. K. Crane, U. Pinkall, and P. Schröder. 2013. Robust fairing via conformal curvature flow. ACM Trans. Graph. 32, 4 (2013). 
    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. 
    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.pdf
    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. 
    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.
    12. E. D. Demaine and J. O’Rourke. 2007. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press. 
    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. 
    14. M. P. do Carmo. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall.
    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. 
    16. S. Fröhlich and M. Botsch. 2011. Example-Driven Deformations Based on Discrete Shells. Comput. Graph. Forum 30, 8 (2011), 2246–2257.
    17. D. Fuchs and S. Tabachnikov. 1999. More on paperfolding. The American Mathematical Monthly 106, 1 (1999), 27–35.
    18. W. C. Graustein. 1917. On the geodesics and geodesic circles on a developable surface. Annals of Mathematics 18, 3 (1917), 132–138.
    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. 
    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.
    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.
    22. T. Hoffmann. 2009. Discrete differential geometry of curves and surfaces. COE Lecture Notes 18 (2009).
    23. D. A. Huffman. 1976. Curvature and creases: a primer on paper. IEEE Trans. Computers 25, 10 (1976), 1010–1019. 
    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. 
    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. 
    26. M. Kilian, N. J. Mitra, and H. Pottmann. 2007. Geometric modeling in shape space. ACM Trans. Graph. 26, 3 (2007). 
    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. 
    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.
    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). 
    30. J. Mitani and T. Igarashi. 2011. Interactive design of planar curved folding by reflection. In Proc. Pacific Graphics, Short Papers.
    31. MOSEK ApS. 2017. The MOSEK optimization toolbox for MATLAB manual. Version 8.1. http://docs.mosek.com/8.1/toolbox/index.html
    32. R. Narain, T. Pfaff, and J. F. O’Brien. 2013. Folding and Crumpling Adaptive Sheets. ACM Trans. Graph. 32, 4 (2013). 
    33. J. Nocedal. 1980. Updating quasi-Newton matrices with limited storage. Math. Comp. 35, 151 (1980), 773–782.
    34. J. Nocedal and S. J. Wright. 2006. Sequential quadratic programming. Springer.
    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. 
    36. U. Pinkall and K. Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1 (1993), 15–36.
    37. H. Pottmann and J. Wallner. 2001. Computational line geometry. Springer, Berlin, Heidelberg, New York. 
    38. M. Rabinovich, T. Hoffmann, and O. Sorkine-Hornung. 2018. Discrete Geodesic Nets for Modeling Developable Surfaces. ACM Trans. Graph. 37, 2 (2018), 16. 
    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. 
    40. J. Solomon, E. Vouga, M. Wardetzky, and E. Grinspun. 2012. Flexible developable surfaces. Comput. Graph. Forum 31, 5 (2012), 1567–1576. 
    41. O. Sorkine and M. Alexa. 2007. As-rigid-as-possible surface modeling. In Proc. Symposium on Geometry Processing. 109–116. 
    42. O. Stein, E. Grinspun, and K. Crane. 2018. Developability of triangle meshes. ACM Trans. Graph. 37, 4 (2018). 
    43. G. Sundaramoorthi, A. Yezzi, and A. C. Mennucci. 2007. Sobolev active contours. International Journal of Computer Vision 73, 3 (2007), 345–366. 
    44. T. Tachi. 2009. Simulation of rigid origami. Origami 4 (2009), 175–187.
    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. 
    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.
    47. M. Wardetzky. 2007. Discrete differential operators on polyhedral surfaces – convergence and approximation. Ph.D. Dissertation. Freie Universität Berlin.
    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. 
    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). 

ACM Digital Library Publication:


Overview Page: