“Boundary First Flattening” by Sawhney and Crane

  • ©Rohan Sawhney and Keenan Crane

Conference:


Type(s):


Title:

    Boundary First Flattening

Session/Category Title:   Flattening, Unflattening and Sampling

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    A conformal flattening maps a curved surface to the plane without distorting angles—such maps have become a fundamental building block for problems in geometry processing, numerical simulation, and computational design. Yet existing methods provide little direct control over the shape of the flattened domain, or else demand expensive nonlinear optimization. Boundary first flattening (BFF) is a linear method for conformal parameterization that is faster than traditional linear methods, yet provides control and quality comparable to sophisticated nonlinear schemes. The key insight is that the boundary data for many conformal mapping problems can be efficiently constructed via the Cherrier formula together with a pair of Poincaré-Steklov operators; once the boundary is known, the map can be easily extended over the rest of the domain. Since computation demands only a single factorization of the real Laplace matrix, the amortized cost is about 50× less than any previously published technique for boundary-controlled conformal flattening. As a result, BFF opens the door to real-time editing or fast optimization of high-resolution maps, with direct control over boundary length or angle. We show how this method can be used to construct maps with sharp corners, cone singularities, minimal area distortion, and uniformization over the unit disk; we also demonstrate for the first time how a surface can be conformally flattened directly onto any given target shape.

References:


    1. Marc Alexa and Max Wardetzky. 2011. Discrete laplacians on general polygonal meshes. ACM Trans. Graph. 30, 4 (2011). 
    2. Pierre Alliez, Éric Colin de Verdière, Olivier Devillers, and Martin Isenburg. 2003. Iso tropic surface remeshing. In Proceedings of Shape Modeling International.
    3. Mosek ApS. 2010. The MOSEK optimization software. Retrieved from http://www.mosek.com.
    4. T. Aubin. 1998. Some Nonlinear Problems in Riemannian Geometry. Springer, Berlin. 
    5. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. CG Forum (2008).
    6. A. Bobenko, U. Pinkall, and B. Springborn. 2010. Discrete conformal maps and ideal hyperbolic polyhedra. ArXiv e-prints (2010).
    7. A. I. Bobenko and F. Günther. 2015. Discrete complex analysis on planar quad-graphs. ArXiv e-prints (2015).
    8. Mario Botsch, David Bommes, and Leif Kobbelt. 2005. Efficient linear system solvers for mesh processing. In Proceedings of IMA International Conference on Mathematics of Surfaces. 62–83. 
    9. Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press. 
    10. Guy Bunin. 2008. A continuum theory for unstructured mesh generation in two dimensions. In Proceedings of the Conference on Computer Aided Geometric Design (CAGD’08), Vol. 25. 14–40. 
    11. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 4 (2010).
    12. Renjie Chen, Ofir Weber, Daniel Keren, and Mirela Ben-Chen. 2013. Planar shape interpolation with bounded distortion. ACM Trans. Graph. 32, 4 (2013). 
    13. Yanqing Chen, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, supernodal sparse cholesky factorization and update/downdate. ACM Trans. Math. Softw. 35, 3 (2008). 
    14. Pascal Cherrier. 1984. Problèms de Neumann non linéaires sur les variétés riemanniennes. J. Funct. Anal. 57 (1984), 154–206. 
    15. Keenan Crane. 2013. Conformal Geometry Processing. Ph.D. Dissertation. Caltech.
    16. Keenan Crane, Fernando de Goes, Mathieu Desbrun, and Peter Schröder. 2013. Digital geometry processing with discrete exterior calculus. In Proceedings of the Special Interest Group on Computer Graphics Courses (SIGGRAPH’13).
    17. Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic parameterizations of surface meshes. CG Forum (2002).
    18. T. A. Driscoll and L. N. Trefethen. 2002. Schwarz-Christoffel Mapping. Cambridge University Press. 
    19. Monty Essid and Justin Solomon. 2017. Quadratically regularized optimal transport on graphs (in submission) (2017).
    20. Michael S. Floater. 2003. One-to-one piecewise linear mappings over triangulations. Math. Comp. 72 (2003), 685–696. 
    21. X. D. Gu and S. T. Yau. 2008. Computational Conformal Geometry. International Press.
    22. Monica K. Hurdal and Ken Stephenson. 2009. Discrete conformal methods for cortical brain flattening. NeuroImage 45, 1 (2009), 86–98. 
    23. John E. Hutchinson. 1991. Computing conformal maps and minimal surfaces. In Theoretical and Numerical Aspects of Geometric Variational Problems. 140–161.
    24. Miao Jin, Xianfeng Gu, Feng Luo, and Junho Kim. 2008. Discrete surface ricci flow. IEEE Trans. Vis. Comp. Graph. 14 (2008), 1030–1043. 
    25. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2 (2006), 412–438.
    26. Jungwook Kim, James A. Hanna, Myunghwan Byun, Christian D. Santangelo, and Ryan C. Hayward. 2012. Designing responsive buckled surfaces by halftone gel lithography. Science 335, 6073 (2012), 1201–1205. 
    27. Patrice Koehl and Joel Hass. 2015. Landmark-free geometric methods in biological shape analysis. J. Roy. Soc. Interface 12, 113 (2015). 
    28. Mina Konakovic, Keenan Crane, Bailin Deng, Sofien Bouaziz, Daniel Piker, and Mark Pauly. 2016. Beyond Developable: Computational design and fabrication with auxetic materials. ACM Trans. Graph. 35, 4 (2016). 
    29. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps. ACM Trans. Graph. 21, 3 (2002).
    30. Y. Lipman and I. Daubechies. 2011. Conformal Wasserstein distances: Comparing surfaces in polynomial time. ArXiv e-prints (2011).
    31. Yaron Lipman, Vladimir G. Kim, and Thomas A. Funkhouser. 2012. Simple formulas for quasiconformal plane deformations. ACM Trans. Graph. 31, 5 (2012). 
    32. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven Gortler. 2008. A local/global approach to mesh parameterization. In Proceedings of the Symposium on Geometry Processing. 1495–1504. 
    33. Feng Luo. 2004. Combinatorial yamabe flow on surfaces. Commun. Contemp. Math. 6, 5 (2004), 765–780. 
    34. Richard MacNeal. 1949. The Solution of Partial Differential Equations by means of Electrical Networks. Ph.D. Dissertation. Caltech.
    35. Christian Mercat. 2001. Discrete riemann surfaces and the ising model. Comm. Math. Phys. 218, 1 (2001), 177–216. 
    36. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral conformal parameterization. In Proceedings of the Symposium on Geometry Processing. 1487–1494. 
    37. Ashish Myles and Denis Zorin. 2013. Controlled-distortion constrained global parametrization. ACM Trans. Graph. 32, 4 (July 2013). 
    38. Konrad Polthier. 2000. Conjugate harmonic maps and minimal surfaces. Preprint No. 446, TU-Berlin, SFB 288 (2000).
    39. Pedro V. Sander, John Snyder, Steven J. Gortler, and Hugues Hoppe. 2001. Texture mapping progressive meshes. In Proceedings of the ACM Special Interest Group on Computer Graphics (SIGGRAPH’01). 409–416. 
    40. Rik Sarkar, Xiaotian Yin, Jie Gao, Feng Luo, and Xianfeng David Gu. 2009. Greedy routing with guaranteed delivery using Ricci flows. In Proceedings of the Conference on Information Processing in Sensor Networks (IPSN’09). 121–132.
    41. Aviv Segall and Mirela Ben-Chen. 2016. Iterative closest conformal maps between planar domains. CG Forum (2016).
    42. Aviv Segall, Orestis Vantzos, and Mirela Ben-Chen. 2016. Hele-shaw flow simulation with interactive control. In Proceedings of the Symposium on Computer Animation. 85–95.
    43. A. Sheffer and E. de Sturler. 2001. Parameterization of faceted surfaces for meshing using angle-based flattening. Engineer. Comput. 17, 3 (2001), 326–337. 
    44. Alla Sheffer, Bruno Lévy, Maxim Mogilnitsky, and Alexander Bogomyakov. 2005. ABF++ : Fast and robust angle based flattening. ACM Trans. Graph. 24, 2 (2005).
    45. Alla Sheffer, Emil Praun, and Kenneth Rose. 2006. Mesh parameterization methods and their applications. Found. Trends. Comput. Graph. Vis. 2, 2 (2006), 105–171. 
    46. Jason Smith and Scott Schaefer. 2015. Bijective parameterization with free boundaries. ACM Trans. Graph. 34, 4 (July 2015). 
    47. Boris Springborn. 2005. A unique representation of polyhedral types. centering via Möbius transformations. Math. Z. 249 (2005), 513–517. 
    48. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27, 3 (2008).
    49. Ofir Weber and Craig Gotsman. 2010. Controll able conformal maps for shape deformation and interpolation. ACM Trans. Graph. 29, 4 (2010). 
    50. Ofir Weber and Denis Zorin. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Trans. Comp. Sys. 33, 4 (2014). 
    51. Rhaleb Zayer, Bruno Lévy, and Hans-Peter Seidel. 2007. Linear angle based parameterization. In Proceedings of Symposium on Geometry Processing. 135–141.
    52. Wei Zeng, Lok Ming Lui, Xianfeng Gu, and Shing-Tung Yau. 2008. Shape analysis by conformal modules. Meth. Appl. Anal. 15, 4 (2008), 539–556.
    53. Zichun Zhong, Liang Shuai, Miao Jin, and Xiaohu Guo. 2014. Anisotropic surface meshing with conformal embedding. Graph. Models 76, 5 (2014), 468–483. 

ACM Digital Library Publication:


Overview Page: