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

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.

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

几何区域的离散剖分生成是一个基础而重要的问题，在很多领域具有重要的应用。虽然各向同性网格剖分的生成问题已经得到较好的研究，但是将复杂几何区域转换成各向异性网格的研究相对落后。各向异性剖分在节约计算成本和提高数值解精度方面通常是有利的，而且图形学中的很多问题都可以归结为求解最优剖分的问题。为生成最优网格剖分，本项目提出了最优Voronoi剖分的概念，取得的主要理论和应用成果如下。.我们扩展了先前用于生成各向同性多边形/多面体剖分的重心Voronoi 剖分（CVT）能量函数。从函数逼近的角度来看，CVT能量函数描述了L1范数中凸函数与其下镶嵌多面体之间的误差。我们放宽了对CVT能量函数的近似和目标函数的约束。更确切地说，目标函数不一定是凸的，其通过在L2范数中的子区域上单独定义的多项式函数来近似。我们使用更一般的Power图来表示给定域的剖分，从而可以有效地解决能量最小化问题。Power图是一种广义的Voronoi剖分。最小化目标函数归结为找到区域的最佳广义Voronoi划分，为了有效地解决我们提出的目标函数的最小化问题，我们设计了一种混合优化算法。由于目标函数的非光滑性、高度非线性和非凸性，使最小化能量函数非常具有挑战性。我们的混合优化方法将局部搜索与全局优化技术相结合，可以降低陷入较差局部最小值的可能性，并快速收敛到足够深的局部最小值。此外，我们还提出了一种有效的初始化方法来极大地改善结果。我们将提出的优化框架应用于网格生成、函数/图像逼近、蓝噪声采样、点云重采样、超像素生成、拼贴画生成、马赛克图像生成、不规则物体排样等问题，取得了很好的实验效果，并且展现出在更多问题上的应用前景。.项目共发表学术论文21篇，其中中国计算机学会（简称CCF）推荐的A类期刊论文3篇，CCF推荐B类期刊论文8篇，CCF推荐C类期刊论文2篇，SCI检索论文14篇，EI检索论文20篇。申请发明专利5项，其中已授权发明专利3项。