基于精确测地线度量的三角网格模型上Voronoi图的研究

三维数字几何是近年来新兴的重要数字媒体。本项目申请中将应用数学和理论计算机科学中广泛使用的Voronoi图引入到二维流形网格表面上，提出研究数字几何媒体计算中的一种基本工具，即在二维流形三角网格上基于精确测地线度量的Voronoi图表示及构建方法。研究内容包括二维流形网格上Voronoi图的完备拓扑和几何性质；Voronoi图增量构建算法的复杂度分析；Voronoi图构建算法中对各种几何退化情况的分析和处理；以及在数字几何媒体中的重要应用。这些应用包括三维网格模型的重剖分和分割；海量媒体数据分析中的维数约减；以及三维模型的检索与匹配。申请研究的内容密切结合当前数字媒体技术的发展趋势，提出研究的内容在国内外没有看到类似的工作。同时拟研究的内容在数字媒体技术中具有较大的应用前景。

本项目按照任务书要求研究三角网格模型上基于精确测地线度量的Voronoi 图及其应用。在国际上首次提出二维流形三角网格曲面上基于精确测地线度量的Voronoi图构建方法，并分析给出了测地线度量下二维曲面上Voronoi图的特殊拓扑性质，理论研究工作发表在IEEE Transactions on Pattern Analysis and Machine Intelligence和Theoretical Computer Science国际著名期刊上。在应用上，基于计算几何算法，将草图界面技术引入到数字媒体的处理过程中，提出了基于手绘草图的视频创作和三维几何建模技术，为表达连续性的设计概念和创新思维提供了新的工具。一系列应用研究工作发表在IEEE Transactions on Multimedia、IEEE Transactions on Automation Science and Engineering、IEEE Computer Graphics and Applications、Eurographics 2011、Computer in Industry、Computer-Aided Design、Computer Aided Geometric Design等国际著名期刊上。在此基础上，搭建了二维流形网格曲面上构建Voronoi图的演示平台，连同精确测地线的源代码一起发布在互联网上，已经被美国、新加坡和香港等地的学者在ACM SIGRAPH、IEEE Transactions on Multimedia、IEEE Journal of Selected Topics in Signal Processing、Computer Graphics Forum、Computer-Aided Design、Computer Aided Geometric Design、Journal of Computational and Applied Mathematics、Graphical Models等国际著名期刊论文中所关注。研究成果发表论文17篇，其中SCI期刊论文13篇，SCI影响因子总和19.68，平均单篇SCI影响因子1.514，其中项目负责人作为第一作者8篇、第二作者5篇；申请中国发明专利10项，已授权5项，获2011年国家技术发明奖二等奖一项（排名第三）。