DDG Geodesics

原课件来自：https://brickisland.net/ddg-web/

测地线（Geodesics）

测地线（Geodesics）是微分几何中的核心概念，它将“直线”的概念推广到弯曲的空间中。我们将从历史背景出发，逐步介绍测地线的基本性质、在不同几何空间中的表现，以及在离散曲面上的推广。

Euclidean Geometry

欧几里得在《几何原本》中提出了五条基本公设，构建了整个平面几何的基础：

1. 两点之间可连一条直线段
2. 线段可无限延伸成直线
3. 可作圆
4. 所有直角都相等
5. 过直线外一点有且仅有一条平行线

这些公设成为几何学的基石，直到两千年后人们才发现，第五条公设并非必然成立。

Non-Euclidean Geometry

19世纪，罗巴切夫斯基、波约、高斯等人发现，平行公设无法由前四条公设推导得出，从而诞生了非欧几何：

• 椭圆几何：过直线外一点没有平行线，所有直线都会相交
• 双曲几何：过直线外一点有无数条平行线

这些几何空间中，“直线”即测地线，其行为与平面中截然不同。

带边界的区域上的测地线

在有边界的区域中，最短路径不一定是“直”的，它可能会沿着边界走。在内部区域中，测地线仍然是“最直”且“最短”的路径。

此时此刻，我正在听《悬日》，看到这张图，也会有一些莫名的失落。前阵子和高中同学闲聊，看到一个二中（我的高中）的学生拍的，其实一个镜头，在书桌上一张一张的整理试卷。面对时空，如果曾经熟悉的知识不再记得，还有必要再重学吗，就好像那些曾经解不出来的题，答案还重要吗。

等距不变性（Isometry Invariance）

等距变换是指保持内在几何不变的变形（如卷起地图）。测地线在等距变换下保持不变，即两点之间的最短路径不会因为曲面的等距变形而改变。

离散测地线（Discrete Geodesics）

在离散曲面（如三角网格）上，我们如何定义测地线？可以从以下几个角度出发：

• 最直（零曲率/加速度）
• 局部最短
• 无测地曲率
• 距离函数的梯度

然而，在离散情形下，“最直”和“最短”这两个性质并不总是一致的，这导致我们需要不同的数值算法来求解。

局部最短路径

在欧几里得空间中，一条线段可以被定义为两点之间的最短路径。但是，我们如何描述一整条直线呢？直线是没有端点的。

这里的答案在于 “局部” 的视角：

• 局部最短：对于路径上的任意两个“足够近”的点，你都无法找到一条连接它们且更短的路径。
  • “足够近”在这里有一个技术性的要求：即在这两点之间，最短路径是唯一的。
• 从局部到整体：这条性质为我们定义（光滑或弯曲空间中的）测地线提供了一种可能的方式：测地线是一条局部最短的曲线。

至关重要的区别：

• 局部最短并不等同于全局最短。
• 一条连接A和B的曲线，可能在其上的每一小段都是最短的，但整体来看，可能存在一条从A直接到B的、更短的完全不同的路径。

结论： 无论是全局最短还是局部最短的路径，在它们的局部范围内，都属于测地线。

狄利克雷能量与曲线长度

对于一条平面曲线 $\gamma: [0, 1] \rightarrow \mathbb{R}^2$，其狄利克雷能量定义为：

可以将任何曲线 $\gamma$ 表示为单位速度曲线的重新参数化：

寻找最平滑的曲线：

关键洞察：对于一条曲线，最小化狄利克雷能量等价于最小化其长度 \(\min E_D(\gamma) \iff \min \text{Length}(\gamma)\)

在弯曲流形 $(M, g)$ 上，狄利克雷能量为：

几何意义：测地线是狄利克雷能量的临界点（谐和曲线），但在弯曲空间中可能不再是全局最小点。

最短测地线 — 变分视角

平面情形

考虑曲线 $\gamma(t): [0,1] \rightarrow \mathbb{R}^2$，通过最小化狄利克雷能量来寻找固定端点 $\gamma(0)=p$，$\gamma(1)=q$ 的最短路径：

推导过程：

• 通过分部积分可得等价形式： \(\min_{\gamma} - \int_{0}^{1} \langle \gamma(t), \gamma''(t) \rangle dt\)
• 对 $\gamma$ 取梯度，得到一维泊松方程

核心思想：测地线是调和函数

弯曲曲面情形

在弯曲流形 $(M, g)$ 上，故事本质上相同：

• 考虑可微曲线 $\gamma: [0,1] \rightarrow M$
• 狄利克雷能量为： \(E_D(\gamma) = \int_0^1 |\gamma'(t)|^2 dt = \int_0^1 g\left( \gamma'(t), \gamma'(t) \right) dt\)

重要结论：

• 测地线仍然是临界点（调和的）
• 但可能不再是全局最小点

关键难点： 测地线不再通过求解简单的线性方程（拉普拉斯方程）得到，需要数值算法。

变分视角总结：

• 平面中：测地线 = 线性函数 = 狄利克雷能量的最小化子
• 弯曲曲面中：测地线 = 狄利克雷能量的临界点（调和曲线）
• 从线性到非线性：需要从解析解转向数值计算

离散最短路径—边值问题

• 局部最短路径： 可以通过迭代拉直Dijkstra路径直到无法进一步改进
• 全局最短路径： 需要更复杂的方法

离散最短路径—顶点处的行为

在顶点附近，即使是局部最短路径也需要特别注意—行为取决于角缺陷 $\Omega$：

平坦顶点 ($\Omega = 0$)

• 最短路径直接穿过顶点
• $\Omega_i = 2\pi - \sum_{ijk} \theta_i^{jk}$

锥形顶点 ($\Omega > 0$)

• 总是从一侧绕行更快
• 从不穿过顶点

鞍点顶点 ($\Omega < 0$)

• 总是有许多局部最短路径通过鞍点顶点

多面体最短测地线算法

将Dijkstra算法推广到包含穿过三角形的路径:

• MMP算法 (Mitchell, Mount, Papadimitriou, 1986)
• 复杂度：$O(n^2 \log n)$
• 核心思想： 跟踪公共测地线路径的区间或”窗口”

最短测地线—光滑vs离散对比

光滑情形

从源点 $p$ 到不同点 $p_1, p_2$ 的两条最小测地线 $\gamma_1, \gamma_2$：

• 仅当 $\gamma_1 \subseteq \gamma_2$ 或 $\gamma_2 \subseteq \gamma_1$ 时才会相交

离散情形

• 多条测地线可以在鞍点顶点处重合（”伪源点”）

重要提示： 多面体最短测地线可能无法忠实捕捉光滑测地线的行为

闭合测地线

光滑曲面理论

定理 (Birkhoff, 1917)

• 每个光滑凸曲面都包含一条简单闭合测地线
• 即：不自交的测地线环（”Birkhoff赤道”）

定理 (Lyusternik & Schnirelmann, 1929)

• 实际上，至少存在三条简单闭合测地线
• 这个结果是尖锐的：在某些光滑曲面上确实只有三条

离散情形的根本差异

定理 (Galperin, 2002)

• 大多数凸多面体没有简单闭合测地线
• （基于离散最短测地线的定义）

核心问题：离散测地线的”最短”特征再次无法捕捉光滑情形的性质

为什么离散情形不同？

约束1： 最短测地线不能穿过凸顶点

约束2： 根据高斯-博内定理：

对于闭合测地线：

• 必须将顶点划分为两个集合
• 每个集合的总角缺陷必须恰好等于 $2\pi$

结论： 光滑微分几何中的经典定理在离散设定中往往不再成立，这推动了离散微分几何发展自身特有的理论体系。

割迹与单射半径

割迹定义

• 对于光滑曲面 $M$ 上的源点 $p$，割迹是所有满足以下条件的点 $q$ 的集合：
  • 在 $p$ 和 $q$ 之间不存在唯一的（全局）最短测地线

单射半径定义

• 单射半径是到割迹上最近点的距离
• 衡量了从 $p$ 出发的测地线保持最短性的最大范围

经典例子：球面

• 球面上任意点 $+p$ 的割迹是对跖点 $-p$
• 单射半径覆盖整个半球面

离散割迹

关键观察

• 绕行锥形顶点（正曲率顶点，$\Omega_i > 0$）总是更短
• 因此，永远不要直接穿过锥形顶点

理论意义：割迹的研究揭示了离散度量几何与光滑微分几何之间的深刻差异，强调了在离散设定中重新审视经典概念的必要性。

中轴（Medial Axis）

定义

• 与割迹类似，区域（或曲面）的中轴是所有不具有唯一最近边界点的点 $p$ 的集合

中轴球

• 以中轴上点为球心
• 半径为到最近边界点的距离
• 是包含在区域内的最大内切球

结构特点

• 与割迹一样，结构可能非常复杂
• 通常具有三个分支

对偶表示 中轴提供了一种”对偶”的形状表示，可以从以下两者恢复原始形状：

• 中轴拓扑结构
• 半径函数

离散中轴

• 正方形：由对角线和中线组成的骨架
• 圆形：单一中心点
• 矩形：类似正方形但比例不同的骨架
• 椭圆：主要轴线

非凸多边形的惊喜

• 不再只是直线段！
• 出现抛物线弧等复杂曲线

三维中轴

维度无关性

• 定义适用于任意维度
• 提供形状的”骨架”概念

计算挑战

• 精确计算困难（涉及二次曲面片）
• 通常用单纯复形近似

中轴计算算法

Voronoi图方法

1. 在边界上采样点
2. 计算Voronoi图
3. 保留”高瘦”单元的”短”面片

收敛性

• 采样足够密时，可获得正确的拓扑结构

中轴与曲面重建

从点云重建曲面

• 连接沿”长边”相遇的”瘦长”单元中心
• 在三维中提供具有拓扑保证的曲面重建

理论保证

• 在足够多的采样点下，能够正确恢复原始曲面的拓扑

总结：中轴作为形状的内在骨架表示，在几何处理、形状分析和曲面重建中具有重要应用，但在离散设定中需要特殊的算法和理论来处理其与光滑情形的差异。

最直路径 (Straightest Paths)

在欧几里得空间中，直线可以被描述为”尽可能直”的曲线。如何将这一概念精确化并推广到流形中的曲线？

两种等价描述：

• 几何视角：无曲率
• 动力学视角：无加速度

流形中的推广：

• 几何视角：无测地曲率
• 动力学视角：协变导数为零

几何视角详解

考虑曲面上的曲线 $\gamma(s)$，其切向量为 $T$，曲面法向量为 $N$，定义 $B := T \times N$。

曲率分解： 可以将曲线的”弯曲”分解为两个分量：

几何解释：

• 法曲率：由曲面 $M$ 本身的曲率”强制”产生
• 测地曲率：超出这一最小弯曲量的任何额外弯曲

核心思想：测地线是满足 $k_g = 0$ 的曲线

可视化对比：

• 大法曲率 $k_n$，小测地曲率 $k_g$：曲线紧密贴合曲面弯曲
• 大测地曲率 $k_g$，小法曲率 $k_n$：曲线在曲面上额外弯曲

这一分解揭示了：

1. 内在vs外在：测地曲率衡量曲线在曲面上的”内在”弯曲，与曲面在空间中的嵌入方式无关
2. 最直性：测地线在曲面上尽可能直地行进，仅因曲面本身的弯曲而偏离”直线”路径
3. 局部特征：测地曲率为零提供了判断曲线是否”直”的局部准则

这一几何视角为在离散曲面上定义”最直”路径奠定了理论基础。

离散曲面上的离散曲线

• 在单纯曲面 $M$ 上，离散曲线是在每个单形内分段线性的连续曲线 $\gamma$

重要特性：

• 不必是边路径：可以穿过面片，在单个面片内有多个顶点等
• 灵活表示：能够处理不同维度的单形序列

编码方式： 使用单形序列和重心坐标表示：

单形类型 | 重心坐标
---------|-----------
三角形 ilj | (0.1, 0.7, 0.2)  
边 ij    | (0.45, 0.55)
三角形 ijk | (0.40, 0.15, 0.45)  
顶点 k   | (1.00)

离散测地曲率

平面曲线的离散曲率：

• 定义为转向角 $\kappa_i$

单纯曲面上的推广：

• 由于单纯曲面的大部分点内在地平坦，可以采用相同的定义
• 面片内：直接测量线段间夹角
• 边穿越：”展开”相邻面片并测量角度
• 顶点处：问题复杂，无法展开

从光滑到离散的转换

光滑情形的挑战：

• 光滑设定中：测地线 = 零测地曲率
• 离散设定中：在顶点处遇到困难（无法展开，某些顶点无最短路径）

替代特征： 光滑情形的另一种描述：曲线两侧具有相同角度

离散自然推广：

• 在曲线两侧具有相等的角度和
• 这提供了离散最直测地线的定义（Polthier & Schmies, 1998）

指数映射 (Exponential Map)

1. 基本定义

在光滑曲面 $ M $ 上的某一点 $ p $，其指数映射是一个函数：

直观理解：

• 输入：一个指明“方向和距离”的向量。
• 输出：在弯曲的曲面上，沿着“直线”（测地线）走完该向量所指定的路程后抵达的终点。

2. 几何图像：“包裹”切平面

可以将指数映射想象成一个将切平面 $ T_p M $ “包裹”或“卷曲”到曲面 $ M $ 本身上的过程。

• 切平面在 $ p $ 点与曲面相切，是一个平坦的参考空间。
• 指数映射将切平面上的直线射线 $ tX $ 精确地对应为曲面上的测地线 $ \exp_p(tX) $。

3. 核心思想：弯曲空间中的“平移”

这是指数映射最根本的价值所在。

• 在平坦的欧几里得空间中，平移非常简单：点 $ p $ 加上向量 $ v $ 就得到新点 $ p+v $。
• 在弯曲的流形上，没有全局的向量加法。指数映射 $ \exp_p(X) $ 替代了 $ p + X $ 的操作，提供了在弯曲背景下“从 $ p $ 点移动一个向量 $ X $”的自然且内蕴的定义。

指数映射 $ \exp_p $ 是连接局部平坦性（切空间）与全局弯曲性（流形本身）的桥梁。它通过测地线将切空间中的向量转换为流形上的点，从而在弯曲空间中实现了类似于“平移”的基本操作，是整个黎曼几何赖以建立的基石之一。

对数映射 (Logarithmic Map)

1. 什么是对数映射？

对数映射 $ \log_p $ 是指数映射 $ \exp_p $ 的逆映射。

• 指数映射：输入切向量 $ X $，输出流形上的点 $ q $。

  \[\exp_p(X) = q\]

• 对数映射：输入流形上的点 $ q $，输出切向量 $ X $。

  \[\log_p(q) = X\]

2. 存在性与唯一性

在局部是唯一的，在全局上不一定。

让我们分解来看：

存在性

• 答案：是的（对于完备的无边界流形）。
• 理论依据：Hopf-Rinow 定理。该定理保证，在完备的黎曼流形上，任意两点之间都存在一条最短测地线。
• 构造方法：
  1. 找到从 $ p $ 到 $ q $ 的最短测地线 $ \gamma $。
  2. 令 $ X $ 为在 $ p $ 点处与 $ \gamma $ 相切的向量，其长度等于 $ p $ 到 $ q $ 的测地距离。
  3. 那么根据指数映射的定义，有 $ \exp_p(X) = q $，因此 $ \log_p(q) = X $。

唯一性

• 答案：在局部是唯一的，在全局上不唯一。
• 局部唯一性：如果点 $ q $ 离 $ p $ 足够近（位于 $ p $ 的单射半径内），那么从 $ p $ 到 $ q $ 的最短测地线是唯一的。因此，$ \log_p(q) $ 也被唯一确定。

• 全局不唯一性：如果点 $ q $ 离 $ p $ 较远，可能存在多条不同的最短测地线连接 $ p $ 和 $ q $。每条测地线都对应一个不同的切向量 $ X $，它们都是 $ \log_p(q) $ 的有效值。

  经典例子：在地球（球面）上，从北极点 $ p $ 到南极点 $ q $ 有无数条最短测地线（任何经线）。每条经线都对应一个不同的初始方向（切向量 $ X $）。因此，$ \log_p(q) $ 有无数个可能的值。

核心洞察：对数映射的唯一性问题，直接反映了流形整体几何的复杂性。割迹 正是由那些使得 $ \log_p $ 不唯一的点 $ q $ 所构成的集合。指数/对数映射是弯曲空间的“翻译官”，能把曲面问题变成平面问题来计算，但要注意路径可能不唯一。

曲面上的平均值

弯曲空间如何求平均？

在平面上，计算平均值是直接的算术运算：

但在弯曲的曲面上，这个方法行不通，因为：

• 脱离曲面：坐标相加的结果可能不在曲面上。
• 非内在性：计算依赖于外部坐标，而我们可能只关心曲面自身的内在几何。

解决方案：Karcher 均值 将“平均值”定义为曲面上那个到所有给定点的测地距离平方和最小的点：

这个定义是内在的，并且在平面上与算术平均完全一致。

如何计算？利用指数/对数映射

计算Karcher均值的关键在于一个优雅的迭代算法，通过 log 和 exp，将复杂的“弯曲空间平均”问题，转化为一系列简单的“线性空间平均”步骤。

离散指数映射

基本思想与计算方式

在离散曲面（如三角网格）上，计算指数映射 $ \exp_p(u) $ 是一个直接的、一步一步的几何过程，类似于“光线追踪”。

算法步骤：

1. 定位起点：确定点 $ p $ 位于哪个三角形面片内。
2. 发射射线：从 $ p $ 出发，沿着给定的切向量 $ u $ 的方向，在当前三角形内画一条射线。
3. 穿越网格：
   • 如果射线击中一条边，则进入相邻的三角形。根据最直准则，入射角等于出射角，以此确定在新三角形中的前进方向。
   • 如果射线击中一个顶点，同样应用最直准则（即在该顶点处，路径两侧的角度和相等）来决定方向。在鞍点等复杂顶点处，这可能产生多个可能的方向。

4. 终止：当行走的总距离等于向量 $ u $ 的长度 $

   u

   $ 时，停止并返回当前位置 $ \exp_p(u) $。

与光滑情形的对比

测地线方程

协变导数 $ \nabla $ 提供了对测地线的另一种刻画，即测地线方程：

逐部分解读：

• $ \gamma $：曲面上的曲线。
• $ \dot{\gamma} $：曲线在某一时刻的速度向量（切向量）。
• $ \nabla $：协变导数（或联络）。
• $ \nabla_{\dot{\gamma}} $：沿着速度向量 $ \dot{\gamma} $ 的方向求协变导数。
• $ \nabla_{\dot{\gamma}} \dot{\gamma} $：速度向量 $ \dot{\gamma} $ 沿着它自身方向的协变导数。这正定义了前文所说的内在加速度。
• $ = 0 $：加速度为零。

几何直觉：没有“面内转弯”

方程 $ \nabla_{\dot{\gamma}} \dot{\gamma} = 0 $ 的直观几何含义是：当沿着曲线 $ \gamma $ 移动时，感觉不到任何在曲面内的转弯。

测地线方程 $ \nabla_{\dot{\gamma}} \dot{\gamma} = 0 $ 是微分几何中最核心的方程之一。

• 理论价值：它提供了一个完全内蕴的、与坐标选取无关的测地线定义。
• 实用价值：给定一个黎曼度量 $ g $，我们可以从中推导出 $ \nabla $ 的具体形式（通过克里斯托费尔符号），然后通过数值求解这个二阶微分方程，来计算光滑曲面上的测地线。

协变导数：外在视角**

目标与动机

我们想衡量一个向量场 $ Y $ 沿着另一个向量场 $ X $ 的方向变化得有多快。

计算步骤（基于曲面嵌入）

1. 找一条曲线：在点 $ p $ 附近，找到一条曲线 $ \gamma(t) $，使得其在 $ p $ 点的切向量就是 $ X(p) $。
2. 限制向量场：将向量场 $ Y $ 限制在这条曲线上，得到一个沿曲线的向量值函数 $ Y’(t) = Y(\gamma(t)) $。
3. 求普通导数：计算 $ Y’(t) $ 在 $ t=0 $ （即 $ p $ 点）的常规导数 $ \frac{dY’}{dt} $。这个导数向量存在于外围的欧几里得空间中。
4. 投影到切空间：将 $ \frac{dY’}{dt} $ 投影到曲面在 $ p $ 点的切平面 $ T_pM $ 上。这个投影操作就是“移除法向分量”。

最终结果：这个投影得到的切向量就是 $ Y $ 沿着 $ X $ 在 $ p $ 点的协变导数，记作 $ \nabla_X Y $。

与测地曲率的联系

这个过程听起来非常熟悉，因为它本质上就是计算测地曲率 $ k_g $ 时所做的：

• 当时，我们取曲线的切向量 $ T $，计算其普通导数 $ \frac{dT}{ds} $，然后将其投影到由 $ B = T \times N $ 张成的“切向方向”上，从而得到测地曲率。
• 因此，测地线方程 $ \nabla_{\dot{\gamma}} \dot{\gamma} = 0 $ 正是要求速度向量 $ \dot{\gamma} $ 沿着自身方向的协变导数（即其内在加速度）为零。

核心思想：协变导数衡量了一个向量场沿着另一个向量场方向的变化率（仅考虑曲面内的变化）。

协变导数：内在视角

动机

既然测地线是内蕴的（只依赖于曲面的第一基本形式，即度量 $ g $），那么定义它的工具（协变导数）也应该能够仅用度量 $ g $ 来定义，而不依赖于曲面在空间中的嵌入方式。

公理化定义

可以证明，协变导数 $ \nabla $ 是唯一满足以下一系列公理的算子：

线性性：

与函数的兼容性（莱布尼兹律）：

与度量的兼容性：

这个性质保证了协变导数在微分过程中不会“破坏”角度和长度的概念。

无挠性：

这里 $ [X, Y] $ 是向量场的李括号。无挠性意味着协变导数中不包含不必要的“扭曲”，协变导数的反对称部分由李括号这一纯代数对象完全决定。

方法一：ODE积分法（在参数域求解）

这种方法直接在光滑的参数化表面上工作。

1. 准备工作：
   • 给定参数化表面 $ f: U \subset \mathbb{R}^2 \rightarrow \mathbb{R}^3 $。
   • 计算其雅可比矩阵 $ J_f $。
   • 写出度量张量 $ g = J_f^T J_f $ 及其逆矩阵 $ g^{ij} $。
2. 计算克里斯托费尔符号：
   • 利用度量 $ g $ 及其导数，通过公式计算克里斯托费尔符号 $ \Gamma_{ij}^k $。
   • 公式：$ \Gamma_{ik}^p = \frac{1}{2} g^{pj} (g_{ij,k} + g_{jk,i} - g_{ki,j}) $
3. 写出测地线方程：

   • 在参数域 $ u(t) = (u^1(t), u^2(t)) $ 中，测地线方程是一个二阶ODE系统：

     \[\ddot{u}^k + \Gamma_{ij}^k \dot{u}^i \dot{u}^j = 0\]
     • 其中 $ \dot{u}^i $ 代表对时间 $ t $ 求导。
     • 这个方程来源于 $ \nabla_{\dot{\gamma}} \dot{\gamma} = 0 $。
4. 数值积分：
   • 使用标准的数值积分器（如龙格-库塔法）。
   • 输入：初始位置 $ u(0) $ 和初始速度 $ \dot{u}(0) $（对应于三维空间中的初始点和初始方向）。
   • 输出：参数域中的路径 $ u(t) $。
   • 映射：最后通过 $ f(u(t)) $ 得到三维空间中的测地线。

方法二：离散化法（在三角网格上追踪）

这种方法将光滑曲面离散化，然后在离散网格上操作。

1. 离散化：将光滑参数化表面 $ f $ 三角剖分，得到一个三角网格。
2. 射线追踪：
   • 在三角网格上，使用之前介绍的离散指数映射算法。
   • 从初始点 $ p $ 出发，沿初始方向发射一条“射线”。
   • 根据“最直”准则（在边和顶点处保持角度相等）穿越三角形。
   • 持续进行，直到达到所需的路径长度。

两种方法的优缺点比较

总结

在光滑曲面上：

• “最短”和“最直”是同一回事，都是测地线。

在离散曲面（如三角网格）上：

• “最短”和“最直”分家了，变成了两个不同的概念。
• 最短：适合解决“从A到B怎么走最短”（边值问题）。
• 最直：适合解决“朝这个方向一直走会去哪”（初值问题）。

重要结论：

1. 没有完美定义：两种离散定义都有缺陷，无法完全复制光滑测地线的所有性质。
2. 按需选用：在实践中，需要根据你的问题（求最短路径还是预测行进轨迹）来选择合适的工具。
3. 保持开放：鼓励寻找新的、更好的离散定义。