“Symmetric moving frames” by Corman and Crane
Conference:
Type:
Title:
- Symmetric moving frames
Session/Category Title: Transport: Parallel and Optimal
Presenter(s)/Author(s):
Abstract:
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.
References:
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
