基于精确测地线度量的三角网格模型上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年国家技术发明奖二等奖一项（排名第三）。

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

随着三维图形媒体的高速发展，超大三维模型的分析和计算已经成为主流。精确的离散测地线算法需要非常高昂的计算成本。CPU处理能力的瓶颈限制了现有串行算法在超大模型上的计算速度，而并行测地线算法的缺失限制了现代并行处理器在测地线计算中的发挥。本项目从测地线的精确算法和近似算法两方面着手， 构建适用于超大三维模型的快速离散测地线算法：（1）设计只依赖于局部信息的完全并行的测地线算法，使之能充分利用现代GPU的并行计算性能，从而使测地线计算不受硬件发展的制约。并行的测地线算法可以随着并行处理器日益增长的计算能力而处理更加巨大的三维模型。（2）针对超大三维模型设计快速近似测地线算法，以适用于对精度不敏感但对时间敏感的测地线应用。

本项目针对现代计算几何中离散测地线算法这一经典难题，现有的测地线算法占用内存大、耗时慢、难以并行，对于千万级三角面片的超大三维模型，计算成本高昂或者几乎无法计算。 本项目的主要内容为离散测地线算法的并行算法，采用了基于离散微分几何的办法，提出测地线计算中的全新数据结构，设计了高度并行化的计算过程，并应用于高度复杂曲面表面的测地距离。 本项目提出了目前计算速度最快、也是唯一一个可以完全并行化的精确测地线算法。在先进的消费级显卡上，我们的计算速度是此前最快算法的2-5倍。更关键的是，现代GPU的处理性能正在快速增长，而单核CPU处理能力的提升则面临物理瓶颈。此前的精确测地线算法为串行或不能完全并行，在可预见的未来，本项目提出的完全并行算法将具有更明显的效率优势。 2100433B