“Symmetric moving frames” by Corman and Crane

  • ©Étienne Corman and Keenan Crane




    Symmetric moving frames

Session/Category Title:   Transport: Parallel and Optimal



    A basic challenge in field-guided hexahedral meshing is to find a spatially-varying frame that is adapted to the domain geometry and is continuous up to symmetries of the cube. We introduce a fundamentally new representation of such 3D cross fields based on Cartan’s method of moving frames. Our key observation is that cross fields and ordinary frame fields are locally characterized by identical conditions on their Darboux derivative. Hence, by using derivatives as the principal representation (and only later recovering the field itself), one avoids the need to explicitly account for symmetry during optimization. At the discrete level, derivatives are encoded by skew-symmetric matrices associated with the edges of a tetrahedral mesh; these matrices encode arbitrarily large rotations along each edge, and can robustly capture singular behavior even on coarse meshes. We apply this representation to compute 3D cross fields that are as smooth as possible everywhere but on a prescribed network of singular curves—since these fields are adapted to curve tangents, they can be directly used as input for field-guided mesh generation algorithms. Optimization amounts to an easy nonlinear least squares problem that behaves like a convex program in the sense that it always appears to produce the same result, independent of initialization. We study the numerical behavior of this procedure, and perform some preliminary experiments with mesh generation.


    1. R. Abraham, J. E. Marsden, and R. Ratiu. 1988. Manifolds, Tensor Analysis, and Applications: 2nd Edition. Springer-Verlag, Berlin, Heidelberg. Google ScholarDigital Library
    2. C. Armstrong, H. Fogg, C. Tierney, and T. Robinson. 2015. Common Themes in Multiblock Structured Quad/Hex Mesh Generation. Proced. Eng. 124 (2015).Google Scholar
    3. D. Arnold, R. Falk, and R. Winther. 2006. Finite element exterior calculus, homological techniques, and applications. Acta Numer. 15 (2006), 1–155.Google ScholarCross Ref
    4. M. Bergou, M. Wardetzky, S. Robinson, B. Audoly, and E. Grinspun. 2008. Discrete Elastic Rods. ACM Trans. Graph. 27, 3 (Aug. 2008), 63:1–63:12. Google ScholarDigital Library
    5. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer Quadrangulation. ACM Trans. Graph. 28, 3, Article 77 (July 2009), 10 pages. Google ScholarDigital Library
    6. D. Bommes, H. Zimmer, and L. Kobbelt. 2012. Practical Mixed-Integer Optimization for Geometry Processing. In Curves and Surfaces. 193–206. Google ScholarDigital Library
    7. M. Brin, K. Johannson, and P. Scott. 1985. Totally peripheral 3-manifolds. Pacific J. Math. 118, 1 (1985), 37–51.Google ScholarCross Ref
    8. K. Crane, F. de Goes, M. Desbrun, and P. Schröder. 2013. Digital Geometry Processing with Discrete Exterior Calculus. In ACM SIGGRAPH 2013 courses (SIGGRAPH ’13). Google ScholarDigital Library
    9. K. Crane, M. Desbrun, and P. Schröder. 2010. Trivial Connections on Discrete Surfaces. Comp. Graph. Forum (SGP) 29, 5 (2010), 1525–1533.Google ScholarCross Ref
    10. F. de Goes, M. Desbrun, and Y. Tong. 2016. Vector Field Processing on Triangle Meshes. In ACM SIGGRAPH 2016 Courses (SIGGRAPH ’16). 27:1–27:49. Google ScholarDigital Library
    11. M. Desbrun, E. Kanso, and Y. Tong. 2006. Discrete Differential Forms for Computational Modeling. In ACM SIGGRAPH 2006 Courses (SIGGRAPH ’06). 16. Google ScholarDigital Library
    12. Z. DeVito, M. Mara, M. Zollöfer, G. Bernstein, C. Theobalt, P. Hanrahan, M. Fisher, and M. Nießner. 2017. Opt: A Domain Specific Language for Non-linear Least Squares Optimization in Graphics and Imaging. ACM Trans. Graph. (2017). Google ScholarDigital Library
    13. T. Dey, F. Fan, and Y. Wang. 2013. An Efficient Computation of Handle and Tunnel Loops via Reeb Graphs. ACM Trans. Graph. 32, 4 (2013). Google ScholarDigital Library
    14. O. Diamanti, A. Vaxman, D. Panozzo, and O. Sorkine. 2014. Designing N-PolyVector Fields with Complex Polynomials. Proc. Symp. Geom. Proc. 33, 5 (Aug. 2014). Google ScholarDigital Library
    15. M.P. do Carmo. 1994. Differential Forms and Applications. Springer-Verlag.Google Scholar
    16. J. Frauendiener. 2006. Discrete differential forms in general relativity. Classical and Quantum Gravity 23, 16 (2006).Google Scholar
    17. X. Gao, W. Jakob, M. Tarini, and D. Panozzo. 2017. Robust Hex-dominant Mesh Generation Using Polyhedral Agglomeration. ACM Trans. Graph. 36, 4 (2017). Google ScholarDigital Library
    18. A. Hertzmann and D. Zorin. 2000. Illustrating Smooth Surfaces. In Proc. SIGGRAPH. Google ScholarDigital Library
    19. A. Hirani. 2003. Discrete Exterior Calculus. Ph.D. Dissertation. Caltech. Google ScholarDigital Library
    20. J. Huang, Y. Tong, H. Wei, and H. Bao. 2011. Boundary Aligned Smooth 3D Cross-frame Field. ACM Trans. Graph. 30, 6, Article 143 (Dec. 2011). Google ScholarDigital Library
    21. T. Jiang, X. Fang, J. Huang, H. Bao, Y. Tong, and M. Desbrun. 2015. Frame Field Generation Through Metric Customization. ACM Trans. Graph. 34, 4 (July 2015). Google ScholarDigital Library
    22. Junho Kim, M. Jin, Q. Zhou, F. Luo, and X. Gu. 2008. Computing Fundamental Group of General 3-Manifold. In Advances in Visual Computing. Google ScholarDigital Library
    23. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally optimal direction fields. ACM Trans. Graph. 32, 4 (2013). Google ScholarDigital Library
    24. J. Lee. 2003. Introduction to Smooth Manifolds. Springer.Google Scholar
    25. Y. Li, Y. Liu, W. Xu, W. Wang, and B. Guo. 2012. All-hex Meshing Using Singularity-restricted Field. ACM Trans. Graph. 31, 6 (Nov. 2012), 177:1–177:11. Google ScholarDigital Library
    26. Y. Lipman, D. Cohen-Or, R. Gal, and D. Levin. 2007. Volume and Shape Preservation via Moving Frame Manipulation. ACM Trans. Graph. 26, 1 (Jan. 2007). Google ScholarDigital Library
    27. Y. Lipman, O. Sorkine, D. Levin, and D. Cohen-Or. 2005. Linear Rotation-invariant Coordinates for Meshes. ACM Trans. Graph. 24, 3 (July 2005). Google ScholarDigital Library
    28. H. Liu, P. Zhang, E. Chien, J. Solomon, and D. Bommes. 2018. Singularity-constrained Octahedral Fields for Hexahedral Meshing. ACM Trans. Graph. 37, 4 (2018). Google ScholarDigital Library
    29. M. Lyon, D. Bommes, and L. Kobbelt. 2016. HexEx: Robust Hexahedral Mesh Extraction. ACM Trans. Graph. 35, 4 (July 2016), 11. Google ScholarDigital Library
    30. E. Mansfield, G. Marí Beffa, and J.P. Wang. 2013. Discrete moving frames and discrete integrable systems. Found. Comput. Math. 13, 4 (2013). Google ScholarDigital Library
    31. J. Moré. 1978. The Levenberg-Marquardt Algorithm: Implementation and Theory. In Numerical Analysis, G.A. Watson (Ed.). Lecture Notes in Mathematics, Vol. 630.Google Scholar
    32. M. Nieser, U. Reitebuch, and K. Polthier. 2011. CubeCover: Parameterization of 3D Volumes. Computer Graphics Forum 30, 5 (2011).Google Scholar
    33. P. Olver. 2000. Moving Frames in Geometry, Algebra, Computer Vision, and Numerical Analysis. In Foundations of Computational Mathematics.Google Scholar
    34. J. Palacios, L. Roy, P. Kumar, C.Y. Hsu, W. Chen, C. Ma, L.Y. Wei, and E. Zhang. 2017. Tensor Field Design in Volumes. ACM Trans. Graph. 36, 6 (Nov. 2017). Google ScholarDigital Library
    35. J. Palacios and E. Zhang. 2007. Rotational Symmetry Field Design on Surfaces. ACM Trans. Graph. 26, 3 (July 2007). Google ScholarDigital Library
    36. H. Pan, Y. Liu, A. Sheffer, N. Vining, C.J. Li, and W. Wang. 2015. Flow Aligned Surfacing of Curve Networks. ACM Trans. Graph. 34, 4 (July 2015). Google ScholarDigital Library
    37. N. Ray, D. Sokolov, and B. Lévy. 2016. Practical 3D Frame Field Generation. ACM Trans. Graph. 35, 6 (Nov. 2016). Google ScholarDigital Library
    38. R.W. Sharpe. 2000. Differential Geometry: Cartan’s Generalization of Klein’s Erlangen Program. Springer New York.Google Scholar
    39. H. Si. 2015. TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator. ACM Trans. Math. Softw. 41, 2 (Feb. 2015). Google ScholarDigital Library
    40. Y. Soliman, D. Slepčev, and K. Crane. 2018. Optimal Cone Singularities for Conformal Flattening. ACM Trans. Graph. 37, 4 (2018). Google ScholarDigital Library
    41. J. Solomon, A. Vaxman, and D. Bommes. 2017. Boundary Element Octahedral Fields in Volumes. ACM Trans. Graph. 36, 4, Article 114b (May 2017). Google ScholarDigital Library
    42. Vaxman, Campen, Diamanti, Panozzo, Bommes, Hildebrandt, and Ben-Chen. 2016. Directional Field Synthesis, Design and Processing. Comp. Graph. Forum (2016).Google Scholar
    43. V. Vyas and K. Shimada. 2009. Tensor-Guided Hex-Dominant Mesh Generation with Targeted All-Hex Regions. In Proc. Int. Mesh. Roundtable, Brett W. Clark (Ed.).Google Scholar
    44. F.W. Warner. 2013. Foundations of Differentiable Manifolds and Lie Groups.Google Scholar
    45. W. Yu, K. Zhang, and X. Li. 2015. Recent algorithms on automatic hexahedral mesh generation. In Int. Conf. Comp. Sci. Ed. 697–702.Google Scholar

ACM Digital Library Publication:

Overview Page: