基于Voronoi最优平分图的网格生成方法研究

本项目研究一种新型多边形/多面体网格的变分生成方法，旨在快速获得与给定张量场自适应的最优网格。首先，基于Voronoi剖分提出一种改进的区域划分结构，称为最优平分图（optimally bisected tessellation，简称OBT），为种子点之间的平分线/面引入带约束的旋转，来弥补Voronoi图表达各向异性能力不足的问题。其次，给出OBT在平面区域的存在性和凸性证明，并逐步推广到三维空间。通过转化为对Voronoi网格顶点进行带约束的平移优化，提出OBT的快速计算方法。最后，以该结构划分求解域，并基于分片逼近方法建立网格生成的目标函数，给出其关于种子点和网格顶点的显式梯度计算公式。交替地优化OBT网格顶点和种子点，并结合多种组合优化手段，以快速获得最优的网格结果。初步实验结果表明，我们的结果比现有方法具有更好的网格质量，且各向异性与输入更加吻合。

This project studies a new variational method for polygonal/polyhedral mesh generation, aiming to quickly obtain the optimal mesh adaptive to a given tensor field. Firstly, based on the Voronoi diagram, we propose an improved geometric structure for region partitioning, named optimally bisected tessellation (OBT), and a constrained rotation is added to each bisector of seed points to make up for the insufficient ability of the Voronoi diagram to capture anisotropy. Secondly, the existence and convexity of OBT in the 2D space are proved, and will be gradually extended to 3D space. An efficient algorithm is then developed to compute OBT through constrained translating optimization of the Voronoi mesh vertices. At last, an objective function of mesh generation is established based on piecewise approximation over the OBT dividing the given domain, and the explicit gradient formulas of the seed points and mesh vertices are given, respectively. We alternately optimize mesh vertices and seed points of the OBT, and multiple optimization techniques are combined with to find the optimal meshes quickly. Preliminary experimental results show that our results have better mesh quality and more consistent anisotropy to the input than existing methods.