Quad Mesh Generation via Field-Aligned Centroidal Voronoi Tessellation

Xingyi Du, Dong-Ming Yan, Juntao Ye, Hui Zhang

Journal of Computer-Aided Design & Computer Graphics, 2018, Vol.30, No.5

PDF

overview of algorithm — Figure 1. Given an orthogonal directional field (left) and a triangular mesh (middle left), our method repositions mesh vertices to align with the field direction (middle right). Finally, triangles are paired to obtain a quad-dominant mesh(right).

Abstract

In order to generate high quality quad mesh, a novel method based on field-aligned centroidal Voronoi tessellation (CVT) is proposed. Target mesh vertices are first uniformly distributed on input mesh surface via CVT optimization. Then, field-aligned CVT is applied to align mesh edges to the underlying direction field. Next, an initial quad mesh is extracted by matching mesh edges and field directions. Meanwhile, singular vertices are detected and eliminated based on topology optimization. Finally, the output quad-dominant mesh is generated by merging adjacent triangle pairs. Experiments show that our method has the ability to generate field-aligned high quality quad-dominant mesh.