VR/AR背后的弄潮儿（1）：微分几何之逼近理论

搜狐科技 • 8年前扫码分享

我是创始人李岩：很抱歉！给自己产品做个广告，点击进来看看。

　　顾险峰 (纽约州立大学石溪分校终身教授，清华大学丘成桐数学科学中心访问教授，计算共形几何创始人)

　　 2016年见证了虚拟现实/增强现实（VR/AR）技术发展的汹涌浪潮。诸多工业巨头和学术重镇纷纷投入巨大的人力物力促进这一场技术革命，例如阿里巴巴斥资8亿美元资助Magic Leap进行光场AR显示设备的研发，扎克伯格宣称VR将是FaceBook的未来发展方向。微软的HoloLens，谷歌的Cardboard在市场上迅猛普及，Oculus Rift 的开发硬件设备在Amazon上半天就被抢购一空。老顾的学生也开始创业，瞬间拿到数千万的风险投资。对于数学家而言， 这场VR/AR的狂潮实际上是微分几何理论对于现代科技推动作用的又一次范例。 一方面，微分几何为VR/AR技术的发展提供了指导作用，同时VR/AR的实际应用为微分几何提出了新的理论挑战。

　　VR/AR的大量应用涉及了很多几何领域，直接相关的包括逼近理论、几何数据压缩理论、映射和变形理论等等。老顾计划撰写一系列文章，简明扼要地剖析这些理论和相应的算法。

　　 历史轮回

　　目前，VR/AR的硬件支持依然差强人意，图像解析度，渲染复杂程度，刷新帧率都比较低。特别在手机上的VR/AR应用，几何形状和纹理贴图相对原始粗糙。如上图所示，在计算机中，光滑曲面都是用三角形多面体网格来近似逼近。由于硬件计算和存储能力有限，所用的三角网格尽量的简单，三角面片尽量的少。这样， 如何用简单的离散三角网格来逼近复杂的光滑曲面 成为VR/AR应用中的技术关键。更进一步，这个问题可以分解成两个子问题：如何在光滑曲面上 离散采样 和如何将采样点进行 三角剖分 。

　　其实，几何逼近问题具有相对“古老”的历史。二十年前，当GPU和三维扫描技术刚刚兴起的时候，几何逼近，重建理论成为工程领域中被关注的焦点。老顾向丘成桐先生请教过这个问题。当时丘先生说了一句意蕴深长的话，令老顾回味至今：“ 离散曲面不但位置上要逼近光滑曲面，法丛也要逼近 。”可惜那时候对这句话理解不够深刻，即使理解也没有功力为这一思想建立理论。那时，计算机科学领域对这个问题的理解相对肤浅，SIGGRAPH上的论文给出的方法只能证明离散曲面的拓扑与光滑曲面的拓扑彼此一致。十多年后，离散法丛的理论才被几何学家建立起来。时光流转，沧海桑田，瞬息万变的是工程技术，亘古不变的是几何理论。几十年后，GPU已经从一棵幼苗长成参天大树，生长点已从实时渲染转到了人工智能，对于这一问题的热情已是时过境迁；但是，VR/AR应用的兴起，重燃了公众对几何逼近理论的兴趣。技术发展的历史，几度轮回。

　　 经典曲率

　　微分几何的中心是空间弯曲，空间弯曲的精确表示是各种各样的曲率张量。曲率本身是抽象而费解的概念。直观而言， 几何中的曲率就是物理中的力 。比如，我们沿着一条空间曲线速度恒定地开车，我们所感受到的力就是曲线的曲率。

　　 图1 曲线的密切圆

　　假设我们沿着一条空间曲线驾车，，如果曲线是圆周，则我们受到的向心力为：

和半径成反比，因此圆周曲率为半径的倒数。一般空间曲线，我们固定一点，则存在唯一的圆和曲线在此点至少二阶相切，这个圆被称为是曲线在此点的密切圆。曲线在的曲率就是密切圆半径的倒数。

　　 图2 曲面的主曲率和主方向

　　 欧拉的观点 曲面的情形比较复杂，欧拉认为曲面是由曲线编制而成，通过用曲线曲率，我们可以刻画曲面的几何。固定曲面上一点，任选一切方向，法向量和切向量张成一张平面，平面和曲面相交于一条平面曲线，曲线在p点的曲率被称为是曲面在p点沿着方向的法曲率，记为。当我们旋转切向量时，法曲率连续变化。有两个相互垂直的方向，对应的法曲率取得最大值和最小值。被称为主曲率，被称为主方向。曲面上处处和主曲率相切的曲线被称为是主曲率线。对于艺术家而言，曲面明暗色调的模式主要是由主曲率线来刻画。因此，出色的画家对于主曲率线都具有异常敏锐的直觉。主曲率的均值被称为平均曲率，主曲率之积被称为高斯曲率。

　　 图3 曲面上的主曲率线

　　 高斯的观点 假设是一光滑曲面，光滑嵌入在三维欧式空间中，这里是位置向量。任给一点，我们任取局部参数。曲面的法向量场记为，所谓高斯映射（Gauss Map）就是将位置向量映射到法向量：。直观上，高斯映射将曲面上邻域映到单位球面上区域，球面区域和曲面区域的面积比就是高斯曲率。曲面面元等于，球面面元是，因此高斯曲率为

。

　　高斯发展了更为深刻的见解，他认为曲面本身就是一个空间，高斯曲率是曲面空间的内蕴性质，和曲面在欧式空间中的嵌入无关。这里我们看到了一个显然的悖论：为了定义高斯曲率，我们假设曲面嵌入在欧式空间之中，然后用法向量来定义高斯映射，高斯映射的面元比定义成高斯曲率。随后，我们又宣称如此定义的曲率其实和嵌入（法向量）无关，这岂不自相矛盾？其实，高斯曲率可以由平行移动内蕴地定义如下。曲面上给定了黎曼度量，我们可以测量两点间的距离。如果两点相距不太远，则两点间的最短线就是所谓的测地线。给定曲面上的一个区域，我们用分段测地线包围。在边界曲线的起点处选择一个切向量，然后沿着测地线移动切向量，使得切向量和测地线的夹角不变，这就是平行移动。沿着边界平行移动一周之后，回到起点处，那么平移后的切向量和初始切向量一般不会重合，两者相差的角度就是区域内部的高斯总曲率。

　　 图4 平行移动

这种解释方式只用到了黎曼度量。由此可见，高斯曲率由曲面的黎曼度量所决定，和曲面在背景空间中的等距嵌入方式无关。

　　 图5 光滑曲面的离散逼近

　　 离散曲率

　　在计算机中，我们用离散曲面来逼近光滑曲面，如图5所示。米开朗基罗的大卫王的头像被三角网格逼近。每个三角面片定义了一张支撑平面，过每个顶点我们可以定义一族支撑平面。我们将网格上每个点映到过此点所有支撑平面的法向量的集合，由此得到了离散高斯映射。我们也可以考虑网格上的测地线和平行移动。

　　应用离散高斯映射，或者平行移动，我们可以将离散曲面上的高斯曲率定义为角欠。给定一个内顶点，考察和相邻的三角形内角之和，其高斯曲率是周角和内角和之差；对于边界顶点，其高斯曲率是平角和内角和之差。因此，离散高斯曲率的公式为

，

　　 图6 离散曲率

　　类似的，每条边相邻两个三角面片，两个面片之间具有二面角。这条边的离散平均曲率定义为边长和其上二面角之积：

。

　　 单位法丛

　　为几何逼近论建立的各种数学理论中，相对简洁并具有一般性的是离散法丛理论（Normal Cycle Theory）。给定一张光滑曲面，其单位法丛是一张光滑曲面，嵌入在中，

，

　　这里是在点的法向量。

　　 图7 光滑曲面和单位法丛

　　如图7所示，这里淡蓝色的曲面是浅绿色曲面的单位法丛，单位法丛嵌在了三维欧式空间中。一般情况下，曲面的单位法丛如果实现在三维欧式空间中会出现自相交。因此，我们把它嵌在了五维的空间中。

图8 离散凸曲面和单位法丛

　　类似的，我们需要定义离散曲面的离散法丛。构造方法也是非常直观。假设是一个四面体，其上任意一点，过p的平面被称为支撑平面，如果整个四面体在的一侧。点p处所有支撑平面的法向量集合被称为点的法锥，记为

，

那么，四面体的离散法丛定义为

。

　　我们可以将四面体替换为中任意的凸集合，例如三角形，线段，甚至离散点。图8显示了一个离散凸曲面的单位法丛，它等于凸曲面所包围的凸体和单位球体的闵科夫斯基和（Minkowski Sum）。

图9 离散曲面的内部三角剖分

　　对于一般非凸的离散曲面，离散法丛可以递归定义如下。给定一个封闭离散曲面（多面体），如图9所示，我们将的内部三角剖分，得到四面体网格，其四面体集合记为。

图10 包含-去除公式

　　我们利用如下的包含-去除法则来定义离散曲面的离散法丛：

，

图10是包含-去除公式的示意图。离散曲面只是连续曲面，本身并不光滑。离散曲面的离散法丛却是一张光滑曲面，更精确的，是一张光滑曲面。

　　 内蕴曲率的外化

　　利用法丛理论，我们可以将内蕴的高斯曲率外蕴化。在背景空间中，有三个全局定义的2阶微分形式，我们称之为曲率微分形式，它们在理论中起到举足轻重的作用。假设背景空间的坐标是，则面积（曲率）微分式：

，

高斯曲率微分式：

，

平均曲率微分式：

　　 光滑情形 令是光滑曲面上的波莱尔集合，我们用来表示法丛在上的限制。奇妙的是， 曲率微分在法丛上的积分等于曲率测度 ，

，

。

　　我们知道 高斯曲率是内蕴的，通过法丛和曲率微分形式，我们将其转换为外蕴 。

　　 离散情形 我们令为离散曲面上的任意波莱尔集合，和光滑情况相似，则曲率微分形式在离散法丛上的积分等于离散曲率测度，

，

。

　　如果我们能够用离散法丛来逼近光滑法丛，则离散曲率测度必然收敛到光滑曲率测度。由此我们看到， 法丛理论统一了离散和光滑曲率理论 。

　　 法丛逼近

　　历史上，有一种错误的观点。人们曾经天真地认为，只要采样密度足够高，三角面片足够小，那么离散曲面自然会逼近光滑曲面。早在1880年，数学家 Hermann Schwartz 构造了一个著名的反例，后来被世人称为许瓦茨的灯笼，如下图所示。

图11 许瓦茨的灯笼

　　对于离散曲面上的任意一点，我们可以找到光滑曲面上的最近点，这样，我们得到所谓 最近点映射 ，记为，

　　这里是空间中的欧式距离。所谓的豪斯道夫距离（Hausdorff Distance ）定义如下:

。

　　许瓦茨的灯笼是对光滑圆柱面的离散逼近。假如我们在光滑柱面上采样，假设在个等高线上采样，每个等高线上采个采样点，然后如图中所示建立三角剖分。依随k趋向无穷，我们得到一系列离散曲面。我们可以证明，离散曲面到光滑曲面的豪斯道夫距离趋于零，但是离散曲面的面积并不趋于光滑曲面的面积，离散高斯曲率测度并不收敛于光滑高斯曲率测度，离散平均曲率测度并不收敛于光滑平均曲率测度。本质上，这是 因为离散法丛并没有收敛到光滑法丛 。

通过利用曲面局部微分几何的细致分析，如果我们在光滑曲面上采样，然后在欧式空间中建立三角剖分，我们可以得到一系列离散曲面，离散法丛收敛的充分条件如下：

所有三角形的边长为，，趋于零，

所有三角形的最小角大于一个正的下界。

这两条可以保证离散法丛曲面和光滑法丛曲面的豪斯道夫距离为，从而保证面积收敛，曲率收敛。进一步，我们可以证明离散黎曼度量收敛到光滑黎曼度量，离散拉普拉斯算子收敛到光滑拉普拉斯算子。

那么如何从算法角度实现如上的两条，从而保证曲率收敛？主要的方法来自经典的计算几何和共形几何。

　　 Delaunay三角剖分

计算几何领域的传统问题是计算Delaunay三角剖分。如图12所示，给定平面离散点集，一般情况下，存在唯一的三角剖分，使得每个三角形的外接圆不包括第四个点。Delaunay三角剖分的计算也有很多种，比较常见的是Edge Swap和凸包方法。

图12 Delaunay三角剖分

在网格生成领域（Mesh Generation），Delaunay Refinement是最为有效而常用的算法。其基本思想如图13所示，给定平面点集，我们计算Delaunay三角剖分。然后寻找外接圆半径过大的三角形，将其外接圆心加入到点集中，然后重新计算Delaunay三角剖分。重复这一步骤，直到所有的三角形外接圆半径都小于给定阈值。在适当条件下，这种方法可以保证上面提出的两条：三角形边长足够小，和最小角有正的下界。这种方法有数目繁多的变种，但是万变不离其宗。那么如何将欧式空间中的Delaunay Refinement算法推广到曲面范畴？这必须借助于共形几何。

　　 图13 Delaunay refinement算法

　　 单值化定理

　　 Delaunay三角剖分的一个本质特性是： 最大化最小角 。我们知道，共形变换保持角度不变，因此，从某种意义来说， 共形变换保持Delaunay三角剖分 。共形几何中的单值化定理是说：大千世界，各种曲面千变万化，不可穷尽；但是在共形变换下，都归结为三种标准曲面中的一种：球面，欧式平面，双曲圆盘。丘先生曾经说过：单值化定理是曲面微分几何最为深刻，最为基础的根本定理。几乎所有曲面微分几何的大定理的证明，都无法绕过单值化定理。

图14 共形几何中的单值化定理

图14显示了曲面单值化定理。给定一个封闭曲面，嵌入在三维欧式空间之中，因而具有欧式度量诱导的黎曼度量记为。曲面上任意一个函数都定义了一个新的度量，和初始度量共形等价。单值化定理断言，存在一个函数，使得诱导常值高斯曲率。如果曲面的亏格为零，如左列所示，那么常值为+1，曲面共形映射到单位球面上；如果曲面的亏格为1，如中列所示，那么常值为0，曲面周期性的共形映射到欧式平面上；如果曲面的亏格大于1，如右列所示，那么常值为-1，曲面周期性地共形映射到双曲圆盘上。

Delaunay Refinement算法可以直接从欧式平面推广到球面和双曲圆盘上面。如果我们用球极投影将球面投射到平面上，或者用Poincare模型来表示双曲圆盘，那么欧式平面上的Delaunay三角剖分等价于球面上和双曲圆盘上的Delaunay三角剖分。因此，对于任意光滑曲面，我们用单值化定理，可以构造一系列离散曲面来逼近光滑曲面，使得曲率测度收敛。

　　总结

　　至此，在理论和算法层面，我们给出了几何逼近论相对完备的答案。回顾历史，我们可以看到几何逼近理论的发展是被GPU技术、三维扫描技术，以及VR/AR技术的发展所推动。工业界和学术界无数工程师为此付出了辛勤的汗水，建立了正确的直觉，研发了实用的软件工具。但是，真正的理论根基还是由数学家所奠定，其中涉及的理论工具，例如法丛、曲率微分形式和共形单值化，实际上已经触及到曲面微分几何最深层次的理论，并且历经数十年。这显示了从工程直觉提炼出基础理论的艰辛。就目前发展水平而言，理论的发展又超前于工业界的发展，尤其是复杂曲面的离散逼近软件工具依然缺乏。我们相信，工业界和学术界的紧密合作，必将会再度推进这一领域的进一步发展。

在下一篇文章中，我们力图分析如下的问题：一个几何曲面所包含的所有信息如何理解和表示？信息熵的概念如何推广到曲面上面？几何压缩的微分几何理论基础如何？

本文被转载1次

首发媒体

| 转发媒体