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

项目名称： 最优Voronoi剖分的理论和应用研究

项目编号： No.61472332

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 计算机科学学科

项目作者： 陈中贵

作者单位： 厦门大学

项目金额： 84万元

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

中文关键词： 最优Voronoi图；重心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.

英文关键词： Optimal Voronoi Tessellation;Centroidal Voronoi Tessellation;Mesh Generation;Surface Approximation;Optimization