Regular/Structural Mesh Generation using Polycube Parameterization



  • We study polycube surface and volumetric parametrization, which is a key-enabling technology in geometric modeling and computer graphics. One important application is high quality regular mesh generation.
  • Regular meshes, such as quadrilateral mesh (for surface data) and hexahedral mesh (for volumetric data), are favored by many scientific applications. The regular mesh structure can significantly reduce the computational cost in finite element analysis and computation. However, automatic generation of high quality hexahedral meshes remains challenging.
  • Our basic idea is to general regular meshes through polycube parameterizations .
  • Several difficult problems in this pipeline include: (1) automatic polycube construction; (2) lowly distorted mapping computation; (3) effective feature sampling and alignment. We study efficient algorithms to tackle these problems.

  • Developed Polycube Parameterization Algorithms

    Harmonic Polycube Mapping with Fixed Boundary Condition
    Biharmonic Polycube Mapping with Fixed Boundary Condition
      Papers: [1] [2] [3] [7]
      Papers: [8]
    (a) illustrates a hex-remeshed solid two-torus. (b) is the polycube constructed for a kitten. (c-d) are the generated hexahedral mesh for a kitten. (e) is the polycube constructed for a horse. (f-h) show the generated hexahedral mesh for a horse.
    (Left) Harmonic Maps; (Right) Biharmonic Maps.
    Polycube Domain Shape Refinement
    Optimizing Polycube Domain Construction
      Papers: [6]
      Papers: [9] [10]
    Optimizing polycube domain shape (c,f) (top vs bottom) using mapping distortion. The meshing quality improve: from (a,d) to (b,e).
    Generalized Polycube (GPC) Mapping
      Papers: [4] [5]
    A GPC and spline construction pipeline. (a) The input genus-3 model is first decomposed into some "T-shape" patches. (b) Each "T-shape" is further decomposed into 4 cuboids.
    (c-d) Overlay all cuboid edges onto the model to visualize the global structure. (e) All cuboids comprise a topological GPC. (f-g) Construct the parametric mapping between the input model and its GPC. (h) Transform the model into a volumetric spline representation.

    Hexahedral Meshing Results (Data and Statistics)

    A set of all-hex meshes results and their statistics are given below. The input triangle meshes are in .obj format. The polycubes hex meshes and the hex remeshing results are in .vtk format.
    Papers Input Surface Surface/Volume Polycube Hex Re-Meshing Avg. Scaled Jacobian * Geometric Deviation **
    ([3]+[7]) Horse.obj horse_pc.obj horse.vtk 0.867 2.40e-7
    ([3]+[7]) David_Head.obj david_pc.obj david.vtk 0.886 2.52e-7
    ([3]+[7]) Kitten.obj kitten_pc.obj kitten.vtk 0.861 3.62e-7
    ([3]+[7]) 2-Torus.obj 2-torus_pc.obj 2-torus.vtk 0.856 5.78e-7
    ([6]) Beethoven.obj Beethoven_pc.obj Beethoven.vtk 0.851 2.16e-7
    ([6]) Cow.obj cow_pc.obj cow.vtk 0.857 4.32e-7
    ([6]) Horse.obj horse_pc.obj horse.vtk 0.864 2.87e-7
    ([6]) Isis.obj isis_pc.obj isis.vtk 0.889 5.32e-7
    ([6]) Max_Planck.obj maxplanck_pc.obj maxplanck.vtk 0.901 3.18e-7
    ([9]) Bunny.obj bunny_pc.obj / bunny_pc.vtk bunny.vtk 0.935 0.04e-7
    ([9]) Rockerarm.obj rockerarm_pc.obj / rockerarm_pc.vtk rockerarm.vtk 0.931 0.01e-7
    ([9]) Kitten.obj kitten_pc.obj / kitten_pc.vtk Kitten.vtk 0.918 0.017e-7
    ([9]) Fertility.obj fertility_pc.obj / fertility_pc.vtk Fertility.vtk 0.914 2.23e-7
    ([9]) Hand.obj hand_pc.obj / hand_pc.vtk Hand.vtk 0.936 2.12e-7
    ([9]) 3-Torus.obj 3-torus_pc.obj / 3-torus_pc.vtk 3-Torus.vtk 0.927 2.36e-7
    ([10]) bunny.obj bunny_pc.obj / bunny_pc_pc.vtk bunny.vtk 0.933 0.02e-7
    ([10]) rockerarm.obj ra_pc.obj / ra_pc.vtk ra.vtk 0.910 0.02e-7
    ([10]) fertility.obj fertility_pc.obj / fertility_pc.vtk fertility.vtk 0.911 3.23e-7
    ([10]) kitten.obj kitten_pc.obj / kitten_pc.vtk kitten.vtk 0.910 0.08e-7
      * The scaled Jacobian [BZ06] is adopted to evaluate the hexahedral meshing quality. The scaled Jacobian has a range of [-1,1], where 1 is optimal.
      ** Geometric Deviation = Hausdorff Distance / Bounding box diagonal


    1. Xin Li, Xiaohu Guo, Hongyu Wang, Ying He, Xianfeng Gu, and Hong Qin, " Harmonic Volumetric Mapping for Solid Modeling Applications ," Proc. of ACM Solid and Physical Modeling Symposium, pp. 109-120, 2007. [PDF] [Bibtex]

    2. Xin Li, Xiaohu Guo, Hongyu Wang, Ying He, Xianfeng Gu, and Hong Qin, " Meshless Harmonic Volumetric Mapping using Fundamental Solution Methods," IEEE Transactions on Automation Science and Engineering (TASE), Vol. 6, Issue 3, pp. 409 - 422, 2009. [PDF] [Video] [Bibtex]

    3. Xin Li, Huanhuan Xu, Shenghua Wan, Zhao Yin and Wuyi Yu, " Feature-aligned Harmonic Volumetric Mapping using MFS," Computers & Graphics (CAG), Volume 34, Issue 3, (Special Issue of Shape Modeling International (SMI) 2010), pp. 242-251, 2010. [PDF] [Video:Remeshing David Head] [Video:Remeshing Horse] [Videos: Volumetric Head and its Cube Parameterization] [Bibtex] [Data]
    4. Bo Li, Xin Li, Kexiang Wang, and Hong Qin, "Generalized Polycube Trivariate Splines," in Proc. IEEE International Conference of Shape Modeling and Applications, pp. 261-266, 2010. [PDF] [Bibtex]
    5. Bo Li, Xin Li, Kexiang Wang, Hong Qin, "Surface Mesh to Volumetric Spline Conversion with Generalized Poly-cubes," IEEE Transactions on Visualization and Computer Graphics (TVCG), in press, 2013 [Paper] [Bibtex]
    6. Shenghua Wan, Zhao Yin, Kang Zhang, Hongchao Zhang, Xin Li, "A Topology-Preserving Optimization Algorithm for Polycube Mapping," Computers & Graphics (CAG), Volume 35, Issue 3, Pages 639-649, 2011 [PDF] [Bibtex] [Data]
    7. Kexiang Wang, Xin Li, Bo Li, Huanhuan Xu, and Hong Qin, "Restricted Trivariate Polycube Splines for Volumetric Data Modeling," IEEE Transactions on Visualization and Computer Graphics (TVCG), Vol. 18, Issue 5, pp. 703-716, 2012 [Paper] [Bibtex]
    8. Huanhuan Xu, Wuyi Yu, Shiyuan Gu, Xin Li, "Biharmonic Volumetric Mapping using Fundamental Solutions," IEEE Transactions on Visualization and Computer Graphics (TVCG), vol. 19, issue 5, pp. 787-798, 2013. [Paper] [Bibtex]
    9. Xin Li, Wuyi Yu, Kang Zhang, Shenghua Wan, "Optimizing Polycube Domain Construction for Hexahedral Remeshing ," Computer-aided Design (SIAM/ACM Conference on Geometric & Physical Modeling GD/SPM2013), 46:58-68, 2013.. [Paper] [Video:Hex-Remeshing] [Data]
    10. Wuyi Yu, Xin Li, " A New Polycube Shape Optimization Algorithm for Hex Mesh Generation ," Structured Meshing Workshop: Theory, Applications, and Evaluation 2014. .


    Go back to my homepage