DDG课程笔记1-外代数与外微分

这个系列是对CMU离散微分几何课程(CMU CS 15-458/858: Discrete Differential Geometry)的总结和回顾。课程涉及了离散曲面、曲率、曲面参数化、测地线、向量场等一系列几何处理相关内容。和常见的几何处理课程不同,这门课基本是基于离散外微分的框架来介绍几何处理的理论。因此在正式进入几何处理相关内容前首先来补充一些外代数和外微分的基础知识。

Exterior Algebra

Wedge Product

首先从向量出发。我们知道向量可以表示空间中一个同时具有大小和方向的量,一般可以用一个箭头来表示。外代数(exterior algebra)可以看成是对向量的推广,它表示一个带方向的「体积」,我们把它称为一个k-vector。比如说一个2-vector表示2个向量张成的平行四边形:

向量张成的运算称为wedge product。接下来我们来看一下wedge product的一些性质。由于k-vector是带方向的,交换向量uv会得到相反的结果:

wedge product的运算结果与顺序无关,即需要满足结合律:

同时,k-vector需要满足向量的平行四边形运算法则:

总结下来,对任意向量u,v,wRn以及标量a,bR, wedge product满足以下性质:

  • 反对称性: uv=vu
  • 结合律: (uv)w=u(vw)
  • 对加法分配律: u(v+w)=uv+uw
  • 对数乘分配律: (au)(bv)=ab(uv)

Hodge Star

接下来我们介绍外代数的Hodge star运算()。对于一个2-vector(uv),我们定义w=(uv)为垂直于平行四边形且大小等于四边形面积的向量,即相当于正交补:

更加严格的定义如下:对于Rn中的k-vector α=e1e2ekα是一个(nk)-vector且满足:

det(α,α)=1

根据这个定义我们可以发现在R2平面上相当于把向量逆时针转90:

类似地,在R3中我们有:

1=e1e2e3 e1=e2e3,e2=e3e1,e3=e1e2 (e2e3)=e1,(e3e1)=e2,(e1e2)=e3 (e1e2e3)=1

Coordinate Representation

对于Rn中的一组基e1,e2,...,en,它们通过wedge product构成了k-vector的基:

通过k-vector的基就可以进行k-vector之间的运算。比如说我们有R2上的2个向量α=2e1+e2, β=e1+2e2:

αβ=(2e1+e2)(e1+2e2)=2e1e1+4e1e2e2e1+2e2e2=4e1e2e2e1=5e1e2

Differential Forms

Covector

有了k-vector的概念以后接下来的问题是如何去度量一个k-vector。要回答这个问题我们首先回到向量中,考虑如何去度量一个向量。在线性空间中我们可以使用另一个向量来度量我们已有的向量,比如说对于任意向量u可以通过一个单位向量α去度量,它们的内积对应了uα上的度量:

这样的向量α称为一个covector。下面给出covector更严格的定义:对于线性空间V,它的对偶空间 V 定义为满足加法和数乘的线性函数α:VR的集合。即α,βV,uV,cR,

(α+β)(u)=α(u)+β(u) (cα)(u)=cα(u)

对偶空间 V 中的元素称为dual vectorcovector

k-Form

接下来我们把covector的概念进行推广。正如covector是将向量映射到实数的线性映射,我们把将k-vector映射到实数的线性映射称为k-form。举个简单的例子,我们可以利用欧式空间下的内积来定义向量对应的1-form:

α(u)=iαiui

这和向量内积计算没有任何区别,唯一需要注意的是这里并不要求α的长度为1。

然后考虑更高维度的k-form。对于2-form,我们把(αβ)去度量(uv)的过程记为αβ(u,v),它表示将uv投影到αβ对应平行四边形的面积(图中阴影部分):

为了计算所需的面积我们首先将uv分别用αβ进行投影:

  • u(α(u),β(u))
  • v(α(v),β(v))

然后计算投影后向量张成的平行四边形面积,得到如下的计算公式:

αβ(u,v)=α(u)β(v)α(v)β(u)

不难发现交换uv或者αβ都会得到相反的结果:

αβ(v,u)=α(v)β(u)α(u)β(v)=αβ(u,v) βα(u,v)=β(u)α(v)β(v)α(u)=αβ(u,v)

因此k-form具有某种反对称性。实际上k-form可以定义为具有多重线性和完全反对称性的函数,它将一个k-vector映射成一个标量:

  • 多重线性:对任意维度保持线性,如
α(au+bv,w)=aα(u,w)+bα(v,w) α(u,av+bw)=aα(u,v)+bα(u,w)
  • 完全反对称性:交换输入维度相当于取反,如
α(u,v,w)=α(v,w,u)=α(w,u,v)=α(u,w,v)=α(w,v,u)=α(v,u,w)

k-form的通用计算公式如下:

(α1αk)(u1,,uk)=|α1(u1)α1(uk)αk(u1)αk(uk)|

Differential Form

有了k-form的概念就可以来定义differential form了。简单来说,一个differential k-form就是对空间中的每一点指定一个k-form。比如说differential 0-form为空间中每一点指定了一个0-form,也就是标量;而differential 1-form则是为每一点指定了一个1-form:

不难发现differential 0-form和标量场没有什么区别,但需要说明的是differential 1-form和向量场是有本质区别的:空间中每一点对应的并不是一个向量,而是一个把向量映射成标量的线性函数。同时,我们可以用differential 1-form来度量任意给定的向量场进而获得一个标量函数,这个标量函数每一点的值对应该点向量场在相应「方向」上的「强度」:

本节最后来讨论一下坐标系中的differential form。首先定义Rn上向量场的基为指向坐标轴正方向的单位向量构成的向量场,比如说R2上的基向量场分别为x1x2

有了基向量场以后就可以对任意向量场进行分解,得到基的线性组合:

类似地,我们可以用坐标的函数来定义differential form的基dx1dx2:

接着,我们规定xdx满足kronecker delta性质:

dxi(xj)=δji={0,i=j1,otherwise

需要说明的是这里只是借用了偏导数()和微分(d)的记号,实际上并没有任何的求导运算,这里只需要把它们当成是基向量就好。有了这些基础就可以对向量场进行计算,比如说对于R2上的向量场X=(1x)x+(1y)y和differen 1-form α=xdx,把α作用到X上可以得到标量函数α(X)

α(X)=(xdx)((1x)x+(1y)y)=(xdx)((1x)x)+(xdx)((1y)y)=x(1x)

需要说明的是在各种参考资料中会把(几乎)所有的differen k-form简写成k-form,尽管有时会引起歧义但我们仍然沿用这种记法。

Exterior Derivative

Properties of Exterior Derivative

下面介绍本课程最重要的概念之一外微分(exterior derivative),这里直接给出外微分的定义:设Ωk是differential k-form构成的空间,外微分算子d:ΩkΩk+1是一个线性映射,且满足如下性质:

  • differential: 对于0-form,有dϕ(X)=DXϕ
  • product rule: 对于k-form αd(αβ)=dαβ+(1)kαdβ
  • exactness: dd=0

Differential

对于任意的0-form ϕ,它的(外)微分为:

dϕ=ϕx1dx1++ϕxndxn

回忆欧式坐标中梯度的定义:

ϕ=ϕx1x1++ϕxnxn

可以发现求外微分类似于求梯度。但是外微分和梯度是不完全一致的:梯度依赖于内积的定义,而外微分与内积无关。换句话说,梯度需要通过内积来转换成外微分:

dϕ()=ϕ,

在欧式空间下二者不会有什么区别,但在其他的空间中则会导致一些差异。

Product Rule

product rule是外微分的运算法则,举个简单例子:设α(x,y)=xdx+ydy,对α进行微分有

dα=dxdx+xd(dx)+dydy+yd(dy)=dxdx+dydy=0+0=0

Exactness

exactness则表明了外微分与求导的一个重要区别:我们总是可以对函数进行多次的求导,但对任意的k-form求两次微分即为0。

Stokes’ Theorem

接下来介绍本课程最重要的定理Stokes定理

Ωdα=Ωα

Stokes定理说明对于任意的k-form α,它在边界Ω上的积分等于它的微分dα在积分域Ω的积分。

Stokes定理定理是非常强大的工具,我们可以通过它来规避掉大量的全局积分运算而只需要考虑边界。同时,微积分中的很多公式也可以看做是Stokes定理的特例:

  • 高斯散度定理:ΩXdA=ΩnXdlΩdα=Ωα
  • 格林定理:Ω×XdA=ΩtXdlΩdα=Ωα
  • 微积分基本定理:abϕxdx=ϕ(b)ϕ(a)[a,b]dϕ=[a,b]ϕ

Discrete Exterior Derivative

Discretization

到这里我们已经有了足够的基础知识来学习几何处理了,但在那之前我们还需要考虑离散化(Discretization)的问题。我们知道计算机不能表示连续的对象,而且在几何处理中我们大部分时间都会去研究如何分析处理三角网格,因此我们需要把前面学习到的外代数和外微分的内容在网格上进行离散化。当然,经过离散化我们会不可避免地丢失掉一部分信息,不过剩下的信息也足够我们去解决很多问题了。

对于Rn上的k-form ω,我们定义对应的离散形式为ω在k维单纯复形σ积分,即

ω^σ=σω

这样的从连续到离散的映射称为discretization map或de Rham map。简单来说,离散化就是对网格的顶点、边和面元赋予相应的值:

  • 对于顶点取0-form在该点处的值:pϕ=ϕ(p)
  • 对于边取1-form在边上的积分:α^e=eα=0Lα(T)ds
  • 对于面取2-form在面元上的积分:tω=tω(T1,T2)dA

Discrete Exterior Derivative

不难发现想要精确地计算离散微分形式是非常困难的,不过幸运的是在实际应用中我们几乎不会显式地计算任何高阶的微分形式,相反我们会使用离散微分算子(Discrete Exterior Derivative)来帮助我们获得高阶的微分形式。

通过Stokes定理我们可以把k-form的积分转换为(k-1)-form的积分,因此对于1-form我们有:

(dϕ^)e=edϕ=eϕ=ϕ^2ϕ^1

也就是说,有向边e上1-form的积分等于顶点函数值的差。类似地,有向面上2-form的积分等于有向边积分的和:

(dα^)σ=σdα=σα=i=13α^i

因此我们可以得到针对0-form和1-form的离散微分算子d0d1

  • d0是一个|E|×|V|的矩阵,将0-form转换成1-form;
  • d1是一个|F|×|E|的矩阵,将1-form转换成2-form;

Discrete Hodge Star

最后我们来介绍一下Hodge star()的离散形式。定义离散Hodge star为(n-k)-form α在dual cell上面的积分:

α^=σα

其中σ表示σ对应的dual cell。当α比较光滑或者网格比较小的时候,α^α^只相差一个缩放:

α^(σ)=|σ||σ|α^(σ)

也就是说Hodge star仅仅是对k-form进行了一定的缩放,因此其矩阵形式为一对角矩阵:

在几何处理中常用的Hodge star算子如下:

  • 0
  • 1
  • 2

最后,离散微分形式和相应的微分算子转换关系如下:

Reference