“Variational surface cutting” by Sharp and Crane
Conference:
Type(s):
Entry Number: 156
Title:
- Variational surface cutting
Session/Category Title: An Atlas for the World and Other Surfaces
Presenter(s)/Author(s):
Moderator(s):
Abstract:
This paper develops a global variational approach to cutting curved surfaces so that they can be flattened into the plane with low metric distortion. Such cuts are a critical component in a variety of algorithms that seek to parameterize surfaces over flat domains, or fabricate structures from flat materials. Rather than evaluate the quality of a cut solely based on properties of the curve itself (e.g., its length or curvature), we formulate a flow that directly optimizes the distortion induced by cutting and flattening. Notably, we do not have to explicitly parameterize the surface in order to evaluate the cost of a cut, but can instead integrate a simple evolution equation defined on the cut curve itself. We arrive at this flow via a novel application of shape derivatives to the Yamabe equation from conformal geometry. We then develop an Eulerian numerical integrator on triangulated surfaces, which does not restrict cuts to mesh edges and can incorporate user-defined data such as importance or occlusion. The resulting cut curves can be used to drive distortion to arbitrarily low levels, and have a very different character from cuts obtained via purely discrete formulations. We briefly explore potential applications to computational design, as well as connections to space filling curves and the problem of uniform heat distribution.
References:
1. Giovanni Alberti, Rustum Choksi, and Felix Otto. 2009. Uniform energy distribution for an isoperimetric problem with long-range interactions. Journal of the American Mathematical Society (2009).Google Scholar
2. Marc Alexa and Jan Eric Kyprianidis. 2015. Error diffusion on meshes. Computers & Graphics (2015). Google ScholarDigital Library
3. Grégoire Allaire, François Jouve, and Anca-Maria Toader. 2004. Structural optimization using sensitivity analysis and a level-set method. Journal of computational physics (2004). Google ScholarDigital Library
4. Thierry Aubin. 2013. Some nonlinear problems in Riemannian geometry. Springer Science & Business Media.Google Scholar
5. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal Flattening by Curvature Prescription and Metric Scaling. Comput. Graph. Forum (2008).Google Scholar
6. Jean Céa. 1986. Conception optimale ou identification de formes, calcul rapide de la dérivée directionnelle de la fonction coût. RAIRO-Modélisation mathématique et analyse numérique (1986).Google Scholar
7. Yanqing Chen, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. (2008).Google Scholar
8. Keenan Crane, Fernando de Goes, Mathieu Desbrun, and Peter Schröder. 2013. Digital Geometry Processing with Discrete Exterior Calculus. In ACM SIGGRAPH 2013 courses. Google ScholarDigital Library
9. Philippe Decaudin, Dan Julius, Jamie Wither, Laurence Boissieux, Alla Sheffer, and Marie-Paule Cani. 2006. Virtual garments: A fully geometric approach for clothing design. In Computer Graphics Forum.Google Scholar
10. Kelly Delp and Bill Thurston. 2011. Playing with Surfaces: Spheres, Monkey Pants, and Zippergons. In Proceedings of the 14th Annual Bridges Conference.Google Scholar
11. Marion Dunyach, David Vanderhaeghe, Loïc Barthe, and Mario Botsch. 2013. Adaptive Remeshing for Real-Time Mesh Deformation. In Eurographics 2013 – Short Papers.Google Scholar
12. Jeff Erickson and Sariel Har-Peled. 2004. Optimally cutting a surface into a disk. Discrete & Computational Geometry (2004). Google ScholarDigital Library
13. Jeff Erickson and Kim Whittlesey. 2005. Greedy optimal homotopy and homology generators. In Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms. Google ScholarDigital Library
14. Jacqui Fletcher. 2005. Dressings: cutting and application guide. World Wide Wounds. (2005).Google Scholar
15. Michael Gage and Richard S Hamilton. 1986. The heat equation shrinking convex plane curves. Journal of Differential Geometry (1986).Google Scholar
16. Henryk Gerlach and Heiko von der Mosel. 2011. On sphere-filling ropes. Amer. Math. Monthly (2011).Google Scholar
17. Craig Gotsman. 2003. On graph partitioning, spectral analysis, and digital mesh processing. In Shape Modeling International, 2003. Google ScholarDigital Library
18. Matthew A Grayson. 1987. The heat equation shrinks embedded plane curves to round points. Journal of Differential geometry (1987).Google Scholar
19. Lin He, Chiu-Yen Kao, and Stanley Osher. 2007. Incorporating topological derivatives into shape derivatives based level set methods. J. Comput. Phys. (2007). Google ScholarDigital Library
20. Heinrich Hencky. 1928. Über die Form des Elastizitätsgesetzes bei ideal elastischen Stoffen. Zeitschrift für technische Physik (1928).Google Scholar
21. Sungchan Hong and Takeshi Asai. 2014. Effect of panel shape of soccer ball on its flight characteristics. Scientific reports (2014).Google Scholar
22. Martin Isenburg and Peter Lindstrom. 2005. Streaming meshes. In Visualization, 2005. VIS 05. IEEE.Google Scholar
23. Dan Julius, Vladislav Kraevoy, and Alla Sheffer. 2005. D-Charts: Quasi-Developable Mesh Segmentation. Comput. Graph. Forum (2005).Google Scholar
24. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Transactions on Graphics (TOG) (2006). Google ScholarDigital Library
25. Martin Kilian, Simon Flöry, Zhonggui Chen, Niloy J Mitra, Alla Sheffer, and Helmut Pottmann. 2008. Curved folding. In ACM Transactions on Graphics (TOG). ACM. Google ScholarDigital Library
26. R Kimmel and J A Sethian. 1998. Computing geodesic paths on manifolds. Proc. Natl. Acad. Sci. U. S. A. (1998).Google ScholarCross Ref
27. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally optimal direction fields. ACM Trans. Graph. (2013). Google ScholarDigital Library
28. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. In ACM transactions on graphics (TOG). Google ScholarDigital Library
29. Frank Losasso, Tamar Shinar, Andrew Selle, and Ronald Fedkiw. 2006. Multiple interacting liquids. In ACM SIGGRAPH 2006 Papers. Google ScholarDigital Library
30. Yu F Maydanik. 2005. Loop heat pipes. Applied Thermal Engineering (2005).Google Scholar
31. Jun Mitani and Hiromasa Suzuki. 2004. Making Papercraft Toys from Meshes Using Strip-based Approximate Unfolding. ACM Trans. Graph. (2004). Google ScholarDigital Library
32. Maks Ovsjanikov, Quentin Mérigot, Viorica Patraucean, and Leonidas Guibas. 2013. Shape matching via quotient spaces. In Computer Graphics Forum. Google ScholarDigital Library
33. Hans Pedersen and Karan Singh. 2006. Organic labyrinths and mazes. In Proceedings of the 4th international symposium on Non-photorealistic animation and rendering. Google ScholarDigital Library
34. Roi Poranne, Marco Tarini, Sandro Huber, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Autocuts: Simultaneous Distortion and Cut Optimization for UV Mapping. ACM Transactions on Graphics (2017). Google ScholarDigital Library
35. Michael Rabinovich, Tim Hoffmann, and Olga Sorkine-Hornung. 2018. Discrete Geodesic Nets for Modeling Developable Surfaces. ACM Trans. Graph. (2018). Google ScholarDigital Library
36. Pedro V. Sander, John Snyder, Steven J Gortler, and Hugues Hoppe. 2001. Texture mapping progressive meshes. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques. Google ScholarDigital Library
37. Rohan Sawhney and Keenan Crane. 2017. Boundary First Flattening. ACM Trans. Graph. (2017). Google ScholarDigital Library
38. C. Schüller, R. Poranne, and O. Sorkine-Hornung. 2017. Shape Representation by Zippable Ribbons. ArXiv e-prints (2017).Google Scholar
39. Alla Sheffer and John C Hart. 2002. Seamster: inconspicuous low-distortion texture seam layout. In Proceedings of the conference on visualization ’02. Google ScholarDigital Library
40. Jan Sokolowski and Antoni Zochowski. 1999. On the topological derivative in shape optimization. SIAM journal on control and optimization (1999). Google ScholarDigital Library
41. Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal Cone Singularities for Conformal Flattening. ACM Trans. Graph. (2018). Google ScholarDigital Library
42. Olga Sorkine, Daniel Cohen-Or, Rony Goldenthal, and Dani Lischinski. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of the conference on Visualization’02. Google ScholarDigital Library
43. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. In ACM SIGGRAPH 2008 Papers. Google ScholarDigital Library
44. Natarajan Sukumar, David L Chopp, Nicolas Moës, and Ted Belytschko. 2001. Modeling holes and inclusions by level sets in the extended finite-element method. Computer methods in applied mechanics and engineering (2001).Google Scholar
45. Chengcheng Tang, Pengbo Bo, Johannes Wallner, and Helmut Pottmann. 2016. Interactive design of developable surfaces. ACM Transactions on Graphics (TOG) (2016). Google ScholarDigital Library
46. Huy T Vo, Claudio T Silva, Luiz F Scheidegger, and Valerio Pascucci. 2012. Simple and efficient mesh layout with space-filling curves. Journal of Graphics Tools (2012).Google Scholar
47. Charlie CL Wang and Kai Tang. 2004. Achieving developability of a polygonal surface by minimum deformation: a study of global and local optimization approaches. The Visual Computer (2004).Google Scholar
48. Chunlin Wu and Xuecheng Tai. 2010. A level set formulation of geodesic curvature flow on simplicial surfaces. IEEE Trans. Vis. Comput. Graph. (2010). Google ScholarDigital Library
49. Hitoshi Yamauchi, Stefan Gumhold, Rhaleb Zayer, and Hans-Peter Seidel. 2005. Mesh segmentation driven by Gaussian curvature. The Visual Computer (2005).Google Scholar
50. Kun Zhou, John Synder, Baining Guo, and Heung-Yeung Shum. 2004. Iso-charts: stretch-driven mesh parameterization using spectral analysis. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing. Google ScholarDigital Library
