【优博微展2017】许春旭：二维流形网格上的 测地Voronoi图研究

许春旭：2017年清华大学优秀博士学位论文二等奖获得者

二维流形网格上的 测地Voronoi图研究

作    者：许春旭

指导教师：刘永进

培养院系：计算机科学与技术系           

学    科：计算机科学与技术

读博感言：砥砺前行，方能柳暗花明。

研究背景/选题意义/研究价值

随着三维扫描和重建等技术的快速发展，已成为常见的数据表现形式，如何高效精确地分析和处理三维模型成为计算机图形学中的重要问题。本文围绕二维流形网格模型上的测地Voronoi图及其对偶结构，针对与之相关的一系列计算、构造和应用问题展开了研究。

主要研究内容

1.研究并提出了计算三角网格模型上离散测地线的快速波前传播算法；

2.研究了三角网格模型上的测地Voronoi图结构并提出了高效精确的构造算法；

3.提出了一类特殊的测地Voronoi图对偶——Delaunay网格的构造和简化算法；

4.提出了一类特殊的测地Voronoi图——质心Voronoi图的全局最优构造算法

快速波前传播算法在获得相同精度的结果时速度为已有算法的3~10倍。

Delaunay网格在诸如离散测地线计算、离散调和映射的计算等数字几何处理中有广泛应用。

主要创新点

1.提出的快速波前传播算法较已有高效同类型算法相比具有相同的理论渐近复杂度，且实际运行速度大大提高；

2.提出的测地Voronoi图构造算法较已有算法速度更快，且可以处理生成源为线段的情形；

3.提出的Delaunay网格构造和简化算法较已有算法速度更快；给出了Delaunay网格在数字几何处理中的应用场景；

4.提出的质心Voronoi图构造算法，所得质心Voronoi图较已有方法更优。

代表性学术发表

1.ChunxuXu,TuanfengY. Wang, Yong-Jin Liu,LigangLiu, Ying He. Fast wavefrontpropagation (FWP) for computing exact geodesic distances on meshes. IEEE transactions on Visualization and Computer Graphics.

2.ChunxuXu,Yong-JinLiu, Qian Sun, Jinyan Li, Ying He. Polyline‐sourced Geodesic VoronoiDiagrams on Triangle Meshes. Computer Graphics Forum.

3.Yong-JinLiu, Chun-Xu Xu, Dian Fan, Ying He. Efficient construction and simplification of delaunaymeshes. ACM Transactions on Graphics.

作者：许春旭

供图：许春旭

编辑：清华大学研究生院  周明坤  严颖巧