IJAT Vol.9 No.6 pp. 756-764
doi: 10.20965/ijat.2015.p0756


Edge-Based Quadrilateral Mesh Fitting Using Normal Vector Diffusion

Yusuke Imai*, Seungki Kim**, Hiroyuki Hiraoka*, and Hiroshi Kawaharada***

*Department of Precision Mechanics, Chuo University
1-13-27 Kasuga, Bunkyo-ku, Tokyo 112-8551, Japan

**Department of Precision Engineering, The University of Tokyo
4-6-1 Komaba, Meguro, Tokyo 153-8904, Japan

***Division of System Research, Faculty of Engineering, Yokohama National University
79-5 Tokiwadai, Hodogaya-ku, Yokohama, Kanagawa 240-8501, Japan

January 15, 2015
August 6, 2015
November 5, 2015
CAD model, hexahedral mesh, sharp feature, fitting, multi-normal vectors
Nowadays, many manufacturers use computer-aided design (CAD) for processes such as computer numerical control (CNC) machining, simulations, and press working. They use CAD models for their simulations because the cost of performance simulations is lower than that of actual product testing. In this paper, we consider hexahedral meshes for finite element analysis because simulations using such meshes are more accurate than those using tetrahedral meshes. Our aim is to automatically generate hexahedral meshes with sharp features that precisely represent the corresponding features of the target shape. Our hexahedral mesh generation algorithm is voxel-based, and thus in our previous studies, we fitted the surface of voxels to the target surface using Laplacian energy minimization. We used normal vectors during the fitting to preserve any existing sharp features. Each face of the boundary surface of a hexahedral mesh is a quadrilateral face, which we consider to consist of four triangles. Herein, we assume that an edge of a quadrilateral surface has four normal vectors of four connected triangles. Here, we diffuse normal vectors of the target shape after extracting them to accurately preserve the shape features. Moreover, for the Laplacian energy, we add a term that matches the normal vector of the target shape with the four normal vectors of a boundary edge. Finally, we present some experimental results using our method.
Cite this article as:
Y. Imai, S. Kim, H. Hiraoka, and H. Kawaharada, “Edge-Based Quadrilateral Mesh Fitting Using Normal Vector Diffusion,” Int. J. Automation Technol., Vol.9 No.6, pp. 756-764, 2015.
Data files:
  1. [1] H. Kawaharada and H. Hiraoka, “Boundary Stencils of Volume Subdivision for Simulations,” Proc. of the ACDDE2011, 3-8.
  2. [2] H. Kawaharada and K. Sugihara, “Hexahedral Mesh Generation Using Subdivision,” Computational Engineering, Vol.16, No.2, pp. 12-15, 2011.
  3. [3] T. J. Tautges, “The generation of Hexahedral Meshes for Assembly Geometry: Survey and Progress,” International Journal for Numerical Methods in Engineering, Vol.50, pp. 2617-2642, 2001.
  4. [4] R. Schneiders, R. Schindler, and F. Weiler, “Octree-based Generation of Hexahedral Element Meshes,” Proc. of the 5th International Meshing Roundtable, pp. 205-215, 1996.
  5. [5] Marechal Loic, “A New Approach to Octree-based Hexahedral Meshing,” Proc. of the 10th International Meshing Roundtable, pp. 209-221, 2001.
  6. [6] M. L. Saten, S. J. Owen, and T. D. Blacker, “Unconstrained Paving and Plastering: A New Idea for All Hexahedral Mesh Generation,” Proc. of the 14th International Meshing Roundtable, pp. 399-416, 2005.
  7. [7] Y. Wada, S. Yoshimura, and G. Yagawa, “Intelligent Local Approach for Automatic Hexahedral Mesh Generation,” The 2nd Symposium on Trends in Unstructured Mesh Generation, 1999.
  8. [8] T. D. Blacker and R. J. Meyers, “Seams and Wedges in Plastering: A 3D Hexahedral Mesh Generation Algorithm,” Engineering with Computers, Vol.2, No.9, pp. 83-93, 1993.
  9. [9] T. J. Tautges, T. Blacker, and S. A. Mitchell, “The Whisker Weaving Algorithm: A Connectivity-based Method for Constructing All-hexahedral Finite Element Meshes,” International Journal for Numerical Methods in Engineering, Vol.39, pp. 3327-3349, 1996.
  10. [10] M. Muller-Hannemann, “Hexahedral Mesh Generation by Successive Dual Cycle Elimination,” Proc. of the 7th International Meshing Roundtable, pp. 365-378, 1998.
  11. [11] A. Sheffer, M. Etzion, A. Rappoport, and M. Bercovier, “Hexahedral Mesh Generation Using The Embedded Voronoi Graph,” Proc. of the 7th International Meshing Roundtable, pp. 347-364, 1998.
  12. [12] P. K. J. Shepherd, S. A. Mitchell, and D. White, “Methods for Multisweep Automation,” Proceedings of the 9th International Meshing Roundtable, pp. 77-87, 2000.
  13. [13] X. R. Eloi Ruiz-Gironées and J. Sarrate, “A New Procedure to Compute Imprints in Multi-Sweeping Algorithms,” Proc. of the 18th International Meshing Roundtable, Springer, pp. 281-299, 2009.
  14. [14] T. D. Blacker and M. B. Stephenson, “Paving: A New Approach to Automated Quadrilateral Mesh Generation,” International Journal for Numerical Methods in Engineering, Vol.32, pp. 811-847, 1991.
  15. [15] D. R. White and P. Kinney, “Redesign of the Paving Algorithm: Robustness Enhancements through Element by Element Meshing,” Proc. of the 6th International Meshing Roundtable, pp. 323-335, 1997.
  16. [16] R. J. Cass, S. E. Benzley, R. J. Meyers, and T. D. Blacker, “Generalized 3-D Paving: An Automated Quadrilateral Surface Mesh Generation Algorithm,” International Journal for Numerical Methods in Engineering, Vol.39, pp. 1475-1489, 1996.
  17. [17] C. Park, J.-S. Noh, I.-S. Jang, and J. M. Kang, “A New Automated Scheme of Quadrilateral Mesh Generation for Randomly Distributed Line Constraints,” Computer-Aided Design, Vol.39, pp. 258-267, 2007.
  18. [18] F. Labelle and J. R. Shewchuk, “Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles,” ACM Trans. on Graphics, Vol.26, No.3:57, pp. 1-10, 2007.
  19. [19] L. Marechal, “Advances in Octree-Based All Hexahedral Mesh Generation: Handling Sharp Features,” Proc. of the 18th Meshing Roundtable, pp. 65-84, 2009.
  20. [20] J. H.-C. Lu and I. Song, William Roshan Quadros, K. Shimada, “Volumetric Decomposition via Medial Object and Pen-based User Interface for Hexahedral Mesh Generation,” Proc. of the 20th International Meshing Roundtable, pp. 179-196, 2011.
  21. [21] H. Kawaharada, Y. Imai, and H. Hiraoka, “Quadrilateral Meshing for Hexahedral Mesh Generation Based on Facet Normal Matching,” Int. J. of Automation Technology, Vol.8, No.3, 2014.
  22. [22] Aim@Shape Project, available from: [cited Jul. 11, 2012]
  23. [23] Polymender, available from: taoju/code/ polymender.htm [cited Jul. 11, 2012] (T. Ju, “Robust Repair of Polygonal Models,” ACM Transactions on Graphics, Vol.23, No.3, pp. 888-895, 2004.)
  24. [24] R. Mehra, Q. Zhou, J. Long, A. Sheffer, A. Gooch, and N. J. Mitra, “Abstraction of Man-Made Shapes,” ACM Trans. on Graphics, Vol.28, No.5, pp. 1-10, 2009.
  25. [25] S. Moriya, H. Hiraoka, and H. Kawaharada, “Replication of Sharp Features Hexahedral Meshes Using Modified Laplacian Energy Minimization,” Proc. of ACDDE2012.
  26. [26] Y. Imai, S. Moriya, H. Hiraoka, and H. Kawaharada, “Quadrilateral Mesh Fitting that Preserves Sharp Features Based on Multi-Normals for Laplacian Energy,” Proc. of ACDDE2013.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Oct. 02, 2023