朱宇峰博士:计算机图形学映射最优化算法

朱宇峰博士:计算机图形学映射最优化算法

在我们读书期间,数学课上一定都学到过集合与映射。简单而言,集合就是将一类特定的事物(元素)归为一个抽象的类别。比如一群人当中将男性归入一个集合,将女性归入另外一个集合,而映射则是一种描述集合与集合的元素之间关系的一种方式。比如在刚才的那个例子中,可以将男性和女性是否为夫妻关系定义为两个集合之间的一种映射。这种看似抽象无聊的数学概念在生活中还可以找到许许多多的例子,而且他在工业生产以及科学研究上也有着极为广泛的应用。就读于英属哥伦比亚大学(University of British Columbia)的朱宇峰(Yufeng Zhu)博士在过去的5年来一直致力于有关保持结构映射(Structure Preserving Map)的研究并将其应用于计算机图形学(Computer Graphics)领域。计算机图形学是上个世纪八十年代兴起的学科,着重于利用计算机进行图形合成与计算的研究,在工业领域尤其是电影特效以及游戏制作方面都有着极为重要的价值与意义。而在图形学领域,映射问题也关联到许多研究方向,比如几何建模(Geometry Modeling),物理模拟(Physical Simulation),纹理贴图(Texture Mapping)等等。

在今年夏天即将于温哥华市加拿大广场旁的会议中心(Canada Convention Center)举办的图形学顶级会议SIGGRAPH 2018上,朱博士将会发表他最新的研究成果:一种当今世界上寻找最优映射最快速的优化算法。比如将图一左这个三维立体女孩雕像的轮廓曲面平铺到二维的平面上如图一右那样,或者将地球映射到二维平面上以便制作地图等等。这两个例子都是在寻找从三维到二维的映射关系,而由于是将曲面压成平面,所以扭曲形变在所难免,而如何将扭曲和形变的程度降到最低就形成了一个优化问题。

图一

image001

 

多年来,图形学研究领域已经将这个问题通过各种方式描述成为了数学问题,并且提出了多种优化算法试图能够高效地解决他,然后尽管在中等规模的问题上已经有了不错的解决方案,但当问题规模变得更大的时候,现有的方法还是无法胜任。朱博士所提出的BCQN算法是第一个可以被应用于大规模映射优化问题的方法,并且这种算法十分简单易行,不仅仅可以应用于图一所示的问题,还可以被应用于几何变形问题以及物理模拟问题,如图二所示。

图二

image003

此外,在去年于亚洲泰国曼谷召开的SIGGRAPH ASIA会议上,朱博士还展示了他的另一项关于形状插值的研究成果,不同于以往的方法,该算法第一次实现了拓扑不同(Inhomeomorphic)的形状之间的插值。如图三所示,球和椭球有着相同的拓扑,但球和甜甜圈的拓扑就不同了,因为甜甜圈有“洞”而球没有。为了实现这种插值技术,朱博士先是通过在拓扑不同的形状之间建立映射关系,由于这种映射关系数学上原本就是存在歧义的,所以需要通过新的方式来定义。为此,朱博士引入了剪切(Cut)和打开(Open)两种拓扑操作与粘性边集(Cohesive Edge Set)的概念来消除拓扑歧义。同时他结合形变最优与网格最优的两个概念,通过同时求解这两个最优目标来找到拓扑不同的形状间的最优映射。通过大量的实验证明,这样所找到的映射所构造的形状插值是与目前同类方法相比中最稳定的。找到了形状之间的映射,下一步就可以插值了,但是传统方法局限于拓扑相同的形状并且也只能进行静态插值。

图三:

image005

为了进一步拓展插值的能力,朱博士又提出了边势能(Boundary Potential)和动能插值(Kinetic Interpolation)两个概念,这样就可以将拓扑变化(Topology Change)以及惯性动能(Inertia Effect)的效果加入到插值的结果中。如图四所示,当给定三个细胞分裂的状态,该算法可以将中间细胞的分裂过程完整的插值还原出来。这种算法的出现有着极为广泛的影响和应用,比如在电影动画中,他可以被用来生成关键帧和关键帧之间的动画,目前该项技术已经被Adobe公司获取并有望在今后的产品中发布。这些成果都已经刊登在图形学的顶级期刊Transactions on Graphics上,并已经或即将在世界图形学的顶级会议上发表。

图四:

image007

此外,朱博士在2015年时也曾在该顶级会议上发表过两片有关映射的文章,分别是首次介绍如何只通过边界计算得到拓扑变换的映射以及如何自定义映射的最优函数,这有别于传统的方法,因为传统的方法只能通过体积算得到映射,并且也无法任意的定义映射的最优函数。有此可见,映射这个课题还有这许多影响深远的问题值得研究,朱宇峰博士以及像他一样的科研人员也将继续在这条道路上探索前进。