最优Voronoi剖分的理论和应用研究

本项目提出了最优Voronoi剖分（Optimal Voronoi Tessellation，简称OVT）的全新概念，并研究OVT的完整理论系统，在很大程度上推广了重心Voronoi剖分（CVT）方法，为图形学领域的多个应用问题提供功能强大的统一解决方案。首先从任意给定函数的任意阶分片多项式逼近角度定义OVT的目标函数，通过研究OVT函数的光滑性和梯度计算公式，给出OVT快速生成算法；结合高效的局部优化算法设计有效的全局优化算法，并研究OVT函数全局最优解对应的参数域剖分结构特点；系统比较OVT方法、CVT方法和最优Delaunay三角化（ODT）方法，揭示三种方法的内在关系和优缺点。最后基于统一的变分框架，将OVT方法应用于网格生成、重新网格化、函数/图像逼近、蓝噪声采样等问题。初步实验结果已经显示出OVT方法的有效性和优越性。

In this proposal, we define a new concept of optimal Voronoi tessellation (OVT for short), and conduct a systematic study of it. The method of OVT, which is considered as an extensive generalization of the centroidal Voronoi tessellation (CVT for short) method, provides a versatile variational framework for a variety of applications in computer graphics. We define the OVT objective function as the error between a given function and its piecewise polynomial approximation defined over Voronoi tessellation. Based on the study of the smoothness of the objective function and its gradient formula, we will give a fast computation method for the generation of OVT. An effective global optimization method is then proposed by combining the efficient local search method. The configurations of the Voronoi tessellations corresponding to the global minimizers of the OVT objective function are also worth examining. A systemic comparison between the OVT method, CVT method, and the optimal Delaunay triangulation (ODT for short) method will be conducted to show their interconnections and respective features. Based on the unified variational framework, the proposed OVT method will be applied to the applications in computer graphics, such as mesh generation, surface remeshing, function/image approximation, and blue noise sampling. Preliminary results have demonstrated the efficacy and superiority of the OVT method.