Shape Analysis课程笔记04-Discrete Curves

这个系列是MIT 6.838: Shape Analysis的同步课程笔记。本课程会介绍几何方法在图形学、机器学习、计算机视觉、医疗图像以及建筑设计等相关领域的原理和应用。本节主要介绍离散曲线的相关内容。

Discrete Curves

在上一节中我们介绍了曲线的Frenet标架以及winding number等内容，这些概念说明曲线的很多性质可以不依赖于外界坐标而是从曲线自身来推导出来。尽管这些性质都十分优雅，我们还需要关注如何在计算机中来表示曲线的问题。

Old-School Approach

Bezier曲线(Bezier curve)是工程中常用的一种曲线形式，我们可以通过一系列控制点来生成一条光滑的曲线。

但Bezier曲线本身也存在一些问题，比如说它的弧长是没有闭式解的。这导致我们很难更深入地研究Bezier曲线的各种几何性质。

实际上不仅是Bezier曲线，大多数常用曲线的弧长都没有闭式解，即使存在也往往具有非常复杂的形式。

另一方面，Bezier曲线只能表达有限的一部分曲线形式。很多曲线只能使用Bezier曲线来进行近似，而无法直接利用它进行表达。

因此在这门课中我们选择使用折线(polyline)来表达各种类型的曲线。直观来看折线是对光滑曲线的一种近似，通过以直代曲来离散地表达整条曲线。

使用折线来近似光滑曲线自然会引入一些问题，比如说原本有良好定义的一些几何量会出现未定义的情况。因此我们需要将原本光滑曲线的各种概念推广到离散的折线上。

Finite Difference Approach

对于离散的几何对象，一种直观的处理方法是使用有限差分(finite difference)来近似微分。实际上很多微分性质就是通过对差分取极限的方式来进行推导的。

但遗憾的是这种离散差分的形式有时也是不可行的。对于离散表示的函数差异\(h\)是严格大于0的，因此我们没有办法直接去通过极限来计算微分。

Two Key Considerations

在设计离散几何的相关概念时主要有两点考虑：首先我们希望离散的理论可以收敛到连续几何对象相应的理论上，同时我们还要求离散的理论可以保持对离散几何对象的相应特点。

同时还需要注意的是在连续几何对象上成立的概念可能会在离散情况下有着不同的表现形式。这些不同形式都是针对同一概念在离散情况下的近似，但通常情况下它们在离散几何对象的表达形式是不相同的。

Signed Curvature on Plane Curves

以二维平面曲线为例，利用Gauss映射可以把曲线映射到单位圆上。

而turning number则给出了封闭曲线的拓扑性质，即逆时针绕原点的旋转数。

在中学阶段我们都接触过外角定理，它指出多边形的外角和等于\(2\pi\)乘以转圈的次数。不难发现外角定理和turning number之间仿佛存在着某种联系。

Discrete Gauss Map

对于离散曲线我们可以把Gauss映射的概念进行推广。此时在线段上的法向与连续情况相同，而在顶点上的法向则对应相邻两段法向的夹角。这样离散Gauss映射(discrete Gauss map)就把折线的线段部分映射为单位圆上的点，而把折线的顶点映射为圆弧。

Integrated Curvature

实际上折线在顶点处的转角等于曲率在dual cell上面的积分。

另一个有趣的发现是即使两条折线有着不同的曲率，只要转角一致积分后的曲率就是相等的。而实际上曲率积分的这一性质对于连续曲线同样是成立的。

这个例子表明在处理离散几何对象中我们往往不会直接计算几何量，而是通过在dual cell上进行积分来进行处理。

从这样的角度来看外角定理就是turning angle theorem在离散曲线下的形式，因此它也称为discrete turning angle theorem。

First Variation Formula

回忆在上一节中我们介绍过将连续曲线上每一点沿\(\kappa \mathbf{N}\)方向移动是缩短曲线长度最快的方式。

而对于离散曲线则可以类似地证明将顶点沿法向移动\(2 \sin\frac{\theta}{2}\)是改变曲线长度最快的方式，从这个角度来看离散曲率的表达式为\(\kappa = 2 \sin\frac{\theta}{2}\)。注意到这里离散曲率的表达式不同于前面推导出的结果，这再次说明离散的几何概念是不能保证对于所有的情况都严格成立的。不过当\(\theta\)比较小时这两种曲率的定义是非常接近的。

Convergence

对于离散曲率还有一个问题是它是否能够收敛到连续情况的定义上。这个问题的答案是肯定的，当折线的端点足够多时我们定义的离散曲率会收敛到连续曲线的曲率上。

Discrete Differential Geometry

在平面离散曲线的基础上我们就可以正式介绍离散微分几何的知识了。在离散微分几何中，我们希望构造出的几何概念能够保持离散对象的行为，同时还可以收敛到连续情况的相关概念上。

Curves in 3D

考虑三维空间中的曲线。连续曲线需要满足Frenet方程：

基于Frenet方程可以对空间曲线进行离散：

除此之外也可以基于transfer matrix的概念进行离散：

Frenet Frame Issue

使用Frenet方程进行推导的一个问题在于当曲率为0时我们就无法区分主法向\(\mathbf{N}\)和副法向\(\mathbf{B}\)了，此时垂直于切向平面上任意相互垂直的两个方向都可以作为两个法向。

Adapted Framed Curve

同时在某些情况下仅仅使用折线也不能表达曲线的形状，显然折线不能表示绕切向进行旋转的曲线。

为了处理这种问题可以引入一个额外的material frame来描述曲线垂直于切向的两个正交方向\(\mathbf{m}_1\)和\(\mathbf{m}_2\)。利用这两个方向就可以描述曲线自身的扭转。

更进一步我们还可以利用material frame在曲线上定义弯曲能量(bending)和扭转能量(twisting energy)。通过优化这两个能量就可以实现弹性曲线(如橡皮筋等)的物理仿真。

Bishop Frame

实际使用material frame时还需要考虑如何表示两个正交方向\(\mathbf{m}_1\)和\(\mathbf{m}_2\)的问题。这里我们引入Bishop frame的概念，它指出除了Frenet标架外我们还可以使用自定义的标架来表达曲线。具体地，我们可以在曲线上选择任意点及其切向来定义一个标架\((\mathbf{T}, \mathbf{u}, \mathbf{v})\)，而曲线其它位置上的标架则可以认为是从起点出发通过尽可能小的弯曲和扭转进行移动来获得的标架，这样的移动方式也称为平行运输(parallel transport)。进一步可以证明这样定义的标架可以通过一个向量\(\Omega=\kappa \mathbf{B}\)以及微分方程来导出，这个向量\(\Omega\)也称为Darboux vector。