Regular/Structural Mesh Generation using Polycube Parameterization

click to see HR video

Overview

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

Papers: [1] [2] [3] [7]

(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.

Optimizing Polycube Domain Construction

Papers: [9] [10]

Polycube Domain Shape Refinement

Papers: [6]

Optimizing polycube domain shape (c,f) (top vs bottom) using mapping distortion. The meshing quality improve: from (a,d) to (b,e).

Biharmonic Polycube Mapping with Fixed Boundary Condition

Papers: [8]

(Left) Harmonic Maps; (Right) Biharmonic Maps.

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

BZ06

** Geometric Deviation = Hausdorff Distance / Bounding box diagonal

Publications

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. .