“Boundary Element Octahedral Fields in Volumes”

  • ©Justin Solomon, Amir Vaxman, and David Bommes




    Boundary Element Octahedral Fields in Volumes


Session Title: Meshing



    The computation of smooth fields of orthogonal directions within a volume is a critical step in hexahedral mesh generation, used to guide placement of edges and singularities. While this problem shares high-level structure with surface-based frame field problems, critical aspects are lost when extending to volumes, while new structure from the flat Euclidean metric emerges. Taking these considerations into account, this article presents an algorithm for computing such “octahedral” fields. Unlike existing approaches, our formulation achieves infinite resolution in the interior of the volume via the boundary element method (BEM), continuously assigning frames to points in the interior from only a triangle mesh discretization of the boundary. The end result is an orthogonal direction field that can be sampled anywhere inside the mesh, with smooth variation and singular structure in the interior, even with a coarse boundary. We illustrate our computed frames on a number of challenging test geometries. Since the octahedral frame field problem is relatively new, we also contribute a thorough discussion of theoretical and practical challenges unique to this problem.


    1. Mirela Ben-Chen, Adrian Butscher, Justin Solomon, and Leonidas Guibas. 2010. On discrete Killing vector fields and patterns on surfaces. In CGF, Vol. 29. 1701–1711. Google ScholarCross Ref
    2. Mirela Ben-Chen, Ofir Weber, and Craig Gotsman. 2009. Variational harmonic maps for space deformation. TOG 28, 3 (July 2009), 34:1–34:11.Google ScholarDigital Library
    3. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013a. Integer-grid maps for reliable quad meshing. TOG 32, 4 (July 2013), 98:1–98:12.Google ScholarDigital Library
    4. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-mesh generation and processing: A survey. CGF 32, 6 (2013), 51–76.Google ScholarDigital Library
    5. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77:1–77:10.Google ScholarDigital Library
    6. T. Bröcker and T. Dieck. 2003. Representations of Compact Lie Groups.Google Scholar
    7. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Designing N-polyvector fields with complex polynomials. Proc. SGP 33, 5 (2014), 1–11.Google Scholar
    8. Charles Dunkl. 1984. Orthogonal polynomials on the sphere with octahedral symmetry. Trans. AMS 282, 2 (1984), 555–575. Google ScholarCross Ref
    9. L. C. Evans. 2010. Partial Differential Equations. AMS. Google ScholarCross Ref
    10. G. H. Golub and C. F. Van Loan. 2012. Matrix Computations. Johns Hopkins University Press.Google Scholar
    11. R. D. Graglia. 1993. On the numerical integration of the linear shape functions times the 3-D green’s function or its gradient on a plane triangle. Trans. Antennas and Propagation 41, 10 (Oct. 1993), 1448–1455. Google ScholarCross Ref
    12. David Hahn and Chris Wojtan. 2015. High-resolution brittle fracture simulation with boundary elements. TOG 34, 4 (2015), 151:1–151:12.Google Scholar
    13. W. Hamilton. 1866. Elements of Quaternions. Longmans, Green, 8 Co.Google Scholar
    14. Jin Huang, Yiying Tong, Hongyu Wei, and Hujun Bao. 2011. Boundary aligned smooth 3D cross-frame field. TOG 30, 6 (Dec. 2011), 143:1–143:8.Google ScholarDigital Library
    15. Tengfei Jiang, Jin Huang, Yuanzhen Wang, Yiying Tong, and Hujun Bao. 2014. Frame field singularity correction for automatic hexahedralization. TVCG 20, 8 (2014), 1189–1199.Google ScholarDigital Library
    16. R. A. Kennedy and P. Sadeghi. 2013. Hilbert Space Methods in Signal Processing. Cambridge University Press. Google ScholarCross Ref
    17. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally optimal direction fields. TOG 32, 4 (July 2013), 59:1–59:10.Google ScholarDigital Library
    18. N. Kowalski, F. Ledoux, and P. Frey. 2014. Block-structured hexahedral meshes for CAD models using 3D frame fields. Procedia Eng. 82 (2014), 59–71. Google ScholarCross Ref
    19. Jeremy Lehner, Joscha Nehrkorn, Matthew Krzyaniak, Andrew Ho, and Stefan Stoll. 2015. EasySpin 5.0.15. Retrieved from http://easyspin.org/.Google Scholar
    20. Wan Chiu Li, Bruno Vallet, Nicolas Ray, and Bruno Lévy. 2006. Representing higher-order singularities in vector fields on piecewise linear surfaces. IEEE Transactions on Visualization and Computer Graphics 12, 5 (2006), 1315–1322. Google ScholarDigital Library
    21. Yufei Li, Yang Liu, Weiwei Xu, Wenping Wang, and Baining Guo. 2012. All-hex meshing using singularity-restricted field. TOG 31, 6 (Nov. 2012), 177:1–177:11.Google ScholarDigital Library
    22. Yaron Lipman, David Levin, and Daniel Cohen-Or. 2008. Green coordinates. TOG 27, 3 (Aug. 2008), 78:1–78:10.Google ScholarDigital Library
    23. Y. Liu. 2009. Fast Multipole Boundary Element Method: Theory and Applications in Engineering. Cambridge University Press. Google ScholarCross Ref
    24. Max Lyon, David Bommes, and Leif Kobbelt. 2016. HexEx: Robust hexahedral mesh extraction. ACM Trans. Graph. 35, 4, Article 123 (July 2016), 11 pages. DOI:http://dx.doi.org/10.1145/2897824.2925976 Google ScholarDigital Library
    25. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral conformal parameterization. In Proc. SGP. 1487–1494. Google ScholarCross Ref
    26. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. CubeCover: Parameterization of 3D volumes. In CGF, Vol. 30. 1397–1406.Google ScholarCross Ref
    27. C. Pozrikidis. 2002. A Practical Guide to Boundary Element Methods with the Software Library BEMLIB. CRC. Google ScholarCross Ref
    28. W. H. Press, Saul Teukolsky, William Vetterling, and Brian Flannery. 2007. Numerical Recipes: The Art of Scientific Computing. Cambridge University Press.Google ScholarDigital Library
    29. Nicolas Ray and Dmitry Sokolov. 2015. On smooth 3D frame field design. CoRR abs/1507.03351 (2015).Google Scholar
    30. Nicolas Ray, Bruno Vallet, Laurent Alonso, and Bruno Lévy. 2009. Geometry-aware direction field processing. TOG 29, 1 (2009). Google ScholarDigital Library
    31. Nicolas Ray, Bruno Vallet, Wan Chiu Li, and Bruno Lévy. 2008. N-symmetry direction field design. TOG 27, 2 (2008). Google ScholarDigital Library
    32. Vladimir Rokhlin. 1985. Rapid solution of integral equations of classical potential theory. J. Comput. Phys. 60, 2 (1985), 187–207. Google ScholarCross Ref
    33. Leonardo Sacht, Etienne Vouga, and Alec Jacobson. 2015. Nested cages. TOG 34, 6 (Oct. 2015), 170:1–170:14.Google ScholarDigital Library
    34. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional field synthesis, design, and processing. Computer Graphics Forum 35, 2 (2016), 545–572. Google ScholarDigital Library
    35. He Wang, Kirill A. Sidorov, Peter Sandilands, and Taku Komura. 2013. Harmonic parameterization by electrostatics. TOG 32, 5 (2013), 155:1–155:12.Google Scholar
    36. Ofir Weber, Roi Poranne, and Craig Gotsman. 2012. Biharmonic coordinates. CGF 31, 8 (Dec. 2012), 2409–2422. Google ScholarDigital Library

ACM Digital Library Publication: