做游戏资产的同学给我看过一个减面之后的角色模型。原本八万面,压到一万二千面,轮廓几乎没变,可一放进引擎就漏光:后脑勺和腋下破了几个洞,法线朝向反了,阴影上出现黑斑。减面算法把顶点数和面数都压下去了,也努力保住了形状,但它没有保证一件事:这个表面仍然是封闭的。

另一类现场在数据分析里。一批高维样本用降维方法压到二维,散点图上两个原来分得很开的簇粘成一片,评审问「这两个类是不是同一批用户」,谁也答不上来。降维优化的目标是让近的点仍然近,不负责让不连通的点保持不连通,也不负责保住数据里的环。环被压扁成一条线,图上看不出来。

这两个问题的共同点是:几何细节错了还能改,拓扑结构错了很难补。这里的拓扑指研究「连续变形下不变的性质」的数学分支:把橡皮泥捏成别的形状,只要不撕开、不粘合,有几个洞、是不是一整块都不变。图形学关心网格的连通性和洞的个数,数据分析关心点云在不同尺度下有多少块、有多少个环。这篇讲这两处怎么用拓扑,以及它什么时候会骗你。

图形学里的拓扑:网格先要问「是不是流形」

三维模型在文件里是一张多边形网格(mesh):顶点、边、面三张表,外加连接关系。拓扑决定了后面哪些操作能做。

第一个要查的性质是流形(manifold)。直观说法:网格表面上的每个点,放大看都像一张平面圆盘。落到可检查的规则上,就是每条边最多被两个面共用,每个顶点的邻域连成一片,不能两个锥尖对尖。满足这条才是二维流形网格。

流形检查用途:导出、物理碰撞、布尔运算、切片的前置条件。代价:要先建边到面的索引,遍历一次 O(F),扫描件的 T 形接头还得单独处理。
亏格 g用途:一句话概括模型有几个洞,配合欧拉公式 χ = V − E + F = 2 − 2g 可以快速核对。代价:公式只对封闭、可定向、流形的曲面成立,有边界或非流形时要另算。
布尔运算用途:并、交、差是最常见的组合手段。代价:它要算交线、切面、重建边界,共面和重合边会产生大量碎面。
UV 展开用途:把表面摊平到二维纹理空间才能贴图。代价:本质是找平面区域与曲面的一一对应(同胚参数化),摊不平的地方必须切开缝,拉伸免不了。
水密用途:3D 打印和体积计算要求内部与外部能明确分开。代价:每条边恰好两个面、法线一致、没有自交,缺一条切片就会多出空腔或薄壁。

两条容易混的。亏格(genus)就是洞的个数,甜甜圈是 1,两个环粘在一起是 2,球是 0。它是个拓扑量:把甜甜圈拉长、压扁,只要不撕开,亏格都不变。但「洞」在图形学里有两套含义,一个是穿透的隧道,一个是表面窟窿,减面破洞说的是后者。

UV 展开那句「同胚参数化」值得停一下。同胚(homeomorphism)指两个空间之间有一一对应,且对应和逆都连续,说白了就是不撕开、不粘连地互相变形。球面和平面不同胚,地图投影一定有失真;环面和平面也不同胚,甜甜圈状的模型展开必定要剪开。接缝和拉伸不是工具差,是拓扑不允许。

水密(watertight)是工业侧的硬门槛。一条边只挂一个面,它就是边界边,模型上就有一个窟窿。切片软件按内外关系判断填充,遇到窟窿会猜着补面,结果常是空腔、薄壁或整块丢失。排查顺序:找边界边、补洞、统一法线。

持续同调:给点云一个不断变大的阈值

数据这边没有网格,只有一堆点。要谈连通性,得先决定多近算连上。持续同调(persistent homology)的做法很朴素:设距离阈值 ε,把所有距离不超过 ε 的点对连起来,在这个结构上数块和洞;让 ε 从 0 慢慢变大,把过程记下来。

严格说:在点集上按阈值 ε 建一个单纯复形(simplicial complex),可以理解成由点、边、三角形、四面体拼起来的对象,它记录了哪些组合在 ε 尺度下足够近。ε 增大只会加入新块,不会删旧块,这一串嵌套结构叫过滤(filtration)。

在这串结构里,某个拓扑特征会在某个 ε 上第一次出现,这个值叫出生尺度(birth);又在更大的 ε 上被合并或填实,这个值叫死亡尺度(death)。两者之差就是它的持久性(persistence)。按维度记:H0 是连通块,H1 是环形的洞,H2 是空腔。

为什么叫「持续」?因为只有活得久的特征才值得信。真实结构通常在很宽的尺度范围内都存在,噪声造出来的小块和小环往往刚出现就被下一个尺度抹平。比如四个点围成边长 1 的正方形,ε 刚过 1 时环出现,再大一点对角线连上、三角形填进来,环就死了,寿命不到 0.5。若点确实沿规则的圈分布,环可以活很久。寿命短的多是稀疏采样或噪声凑出来的,寿命长的才更可能是真结构。

所以持续同调的输出不是一个数,而是一堆区间。常见画法有两种:条形码(barcode,每个特征一条从出生到死亡的横线)和持续图(persistence diagram,每个特征一个点,横轴出生、纵轴死亡)。离对角线越远越可能是真结构。

手算一遍:6 个点上的 H0

先只看 H0,也就是连通块。这件事可以用并查集(union-find)手写:每个点一开始自成一个集合,遇到一条边就试着合并,合并成功说明两个块变成了一个,块数减一。

取六个一维点 0、0.5、1.2、3.0、3.4、5.0。相邻间隔是 0.5、0.7、1.8、0.4、1.6,其中 0.5 到 1.2 的间隔是 0.7,1.2 到 3.0 的间隔是 1.8。阈值从小到大扫,每次处理一条相邻点的边:

points = [0.0, 0.5, 1.2, 3.0, 3.4, 5.0]

parent = list(range(len(points)))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False
    parent[rb] = ra
    return True

gaps = sorted((points[i + 1] - points[i], i, i + 1) for i in range(len(points) - 1))
components = len(points)
print("start components =", components)
for d, i, j in gaps:
    merged = union(i, j)
    components -= int(merged)
    print(f"eps={d:.1f}  edge {points[i]:.1f}-{points[j]:.1f}  merged={merged}  components={components}")

本机 Python 3.15 的真实输出:

start components = 6
eps=0.4  edge 3.0-3.4  merged=True  components=5
eps=0.5  edge 0.0-0.5  merged=True  components=4
eps=0.7  edge 0.5-1.2  merged=True  components=3
eps=1.6  edge 3.4-5.0  merged=True  components=2
eps=1.8  edge 1.2-3.0  merged=True  components=1

六行输出就是 H0 的全部故事。每个 merged=True 都意味着一个连通块死掉了:ε = 0.4 时 3.0 和 3.4 合并;ε = 0.5 时 0 和 0.5 合并;ε = 0.7 时 {0, 0.5} 与 {1.2} 合并,块数从 4 掉到 3,死掉的那个 H0 特征出生 0、死亡 0.7,持久性 0.7。到 ε = 1.8 全部连通,H0 只剩一个。

为什么只处理相邻边?一维数轴上,不相邻两点的距离都大于中间的相邻间隔;等长边被处理时,短边早已把它们连成一块,它合并不了任何东西。这是 Kruskal 在一维上的直接结果:生成树就是那几个相邻间隔。通用代码仍要排所有点对,代价 O(n2 log n)。

同一条数轴,两个阈值下的连通分量
ε = 0.7 ε = 1.8 0 0.5 1.2 3.0 3.4 5.0

图里上排是 ε = 0.7 时的四个块:{0, 0.5, 1.2}、{3.0}、{3.4}、{5.0};下排是 ε = 1.8 时全部连通。同一条数轴,换一个阈值,块数就从 4 变成 1。TDA 记录的是这条随阈值变化的曲线,而不是某个阈值下的答案。

H1 的直觉:洞要由环撑起来

一维点集上没有 H1,这是能证明的:把阈值 ε 下的结构看成一张图,图上的环数(环秩)等于 E − V + C,E 是边数,V 是点数,C 是连通块数。在数轴上只有相邻边,E = V − C 恒成立,所以环秩恒为 0。没有环,就没有洞。

要出现洞,至少需要环状结构。四个点摆成边长 1 的正方形,对角线 √2 ≈ 1.4142。ε 小于 1 时只有孤立点;越过 1,四条边一起出现,V = 4、E = 4、C = 1,环秩 1,H1 出现。它什么时候死,取决于后面有没有东西填实。在常用的 Vietoris–Rips 复形里,ε 越过 1.4142,两条对角线出现,四个三角形同时加入,环被填成空心四面体表面,H1 归零,转而冒出 H2。

import math
pts = [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)]
pairs = [(i, j, math.dist(pts[i], pts[j])) for i in range(4) for j in range(i + 1, 4)]
for i, j, d in sorted(pairs, key=lambda t: t[2]):
    print(f"  {i}-{j}  {d:.4f}")
print("cycle rank at eps=1.0:", 4 - 4 + 1)
print("triangles appear at eps = sqrt(2) =", round(math.sqrt(2), 4))
  0-1  1.0000
  0-3  1.0000
  1-2  1.0000
  2-3  1.0000
  0-2  1.4142
  1-3  1.4142
cycle rank at eps=1.0: 1
triangles appear at eps = sqrt(2) = 1.4142

这里 H1 出生 1、死亡 1.4142,持久性只有 0.4142。点更密地沿圆排布时,环能活到很大的 ε,持久性接近直径,这才是可信的洞。

工程实现不会枚举所有子集,而是先把点云建成单纯复形,常用 Vietoris–Rips、Alpha、Witness 几种构造,区别在于哪些三角形有资格加入,再用矩阵约简一类算法批量算出出生死亡对。输入是点、距离矩阵、最大维度;输出是每个维度的一串区间,外加 Betti 曲线、持续图。这篇不展开约简细节,只需知道:它算的是各尺度下有几个连通块、几个洞,不是洞长什么样。

TDA 能拿来做什么,又在哪儿会失灵

持续同调这一支通常叫拓扑数据分析(TDA)。它不替代统计,只是补一个统计看不到的角度:统计看分布,拓扑看形状。

特征提取

把持续图压成定长向量,比如像素化、持续性景观或 Betti 曲线,再喂给分类器。判断:适合形状本身即类别信号的问题,如材料微观结构,不适合当万金油特征。

噪声敏感

噪声会在低持久性区间堆满短条。判断:看持续图有没有明显的空隙,以上当结构,以下当噪声,别指望算法替你划线。

计算成本

复形规模随点数和维度迅速膨胀,几千个点算 H2 就可能卡住。判断:先降采样、限制维度,或用 Witness 这类稀疏构造,别拿全量数据硬上。

距离度量

换个度量,结论就换一套。判断:度量要和业务含义一致,图像用像素欧氏距离、轨迹用测地距离、文本用余弦距离,混用会让洞变成度量的产物。

四条合起来是一句话:TDA 给出的是一族尺度上的结构描述,不是一个能直接写进 if 判断的结论。它的价值是暴露形状变了但统计没变的情况,代价是你得自己定义远近。

同样的思路在别处:连通、环和割点

拓扑的语言在工程里到处都能对上号,只是平时不这么叫。

传感器网络。一堆节点随机撒在区域里,通信半径固定,问覆盖够不够、网络通不通。前者是覆盖区域有没有洞,二维上是 H1;后者是通信图的连通分量数。这正是拓扑的两类不变量。

机器人路径规划。机器人的构型空间(configuration space)里,障碍物是挖掉的部分。两点之间有没有路,问的是是否同一连通分量;要绕过一个障碍,问的是障碍是不是洞。高自由度机械臂规划难,难在维数高,连通性不能靠画图判断。

数据库一致性。把外键、触发器、事务依赖画成约束图,环不代表一定出错,但环上约束互相牵制,是排查循环依赖和死锁的第一现场。检测就是图上的环检测:深度优先搜索遇到回边,或拓扑排序排不完。

网络鲁棒性。割点(cut vertex)是删掉后连通分量数增加的点,割边同理。它们就是单点故障位置,和「有几个连通块」是同一套语言;再问至少删几个点才能断开,那是顶点连通度,Menger 定理把它和不相交路径条数绑在一起。

四条的共同结构是:把问题化成图或复形,只问连通块数、环数、割点。它们在连续变形下不变,对具体长什么样不敏感;这既是好用的原因,也是不够用的原因。

一张现象对照表

这些现象在建模和数据分析里都出现过,原因大多是拓扑前提没满足。

现象真实原因第一步查什么
减面后模型破洞减面只约束形状误差,没有约束边界,边界边被合并掉统计只挂一个面的边,顺着边界边找出破洞的环
降维后两个簇粘连降维保的是局部距离或邻域概率,不保连通性,也不保洞回到高维算连通分量,再和低维图上的分组对照
点云噪声把结构淹没短命特征被当成结构,阈值取在了噪声区间画持续图,看短条和对角线之间有没有空隙
网格非流形报错有边挂了三个以上面,或某个顶点的邻域分成几片建边到面的索引,逐条统计每条边挂几个面
布尔运算后出现多余边共面、重合边、退化三角形没有合并,切分产生了碎片检查容差设置,合并重合顶点,清理零面积面
连通分量数算错并查集只合并了部分边,或阈值比较用了浮点数打印每次合并的日志,核对阈值和边表是否完整
亏格算出负数或非整数欧拉公式用在了带边界或非流形的网格上,或有重复面先数边界边、重复面和孤立顶点,确认公式前提

边界与代价

第一,拓扑不变量不管几何。甜甜圈和带把手的杯子同胚,亏格都是 1,靠拓扑分不出哪个是杯子。所以拓扑特征只能当补充,替代不了形状、尺寸、材质。反过来,形状误差小不代表拓扑没变,开头的减面模型就是例子。

第二,持续同调对噪声和度量都敏感。同一批点在欧氏距离和余弦距离下可能得出完全不同的持续图;单位从毫米换成米,阈值全变,但持久性的相对大小不变。噪声更麻烦:它不会抹掉真特征,而是在对角线附近堆一片短条,你得自己划线。

第三,计算成本高。点数上去,Vietoris–Rips 复形里的单纯形按组合数增长,三维以上很快不可算。工程上的做法是降采样、限制维度、稀疏构造,或只算 H0 和 H1。这些不是免费午餐,降采样本身就可能把要找的洞采没。

第四,离散化会引入伪特征。有限采样让光滑的圆看起来像折线,采样越稀,伪环和伪块越多;阈值太大时整个点云填成一个团,洞全被抹平。持续同调能说清特征在哪个尺度存在,但说不清这个洞是不是本来就有。

第五,拓扑不变量分不出方向。两个环相扣和两个环并排,H1 都是 2,要分开得看更高阶结构或别的工具。所以 TDA 要和几何、统计一起用,不适合单独当判据。

当天能验证的五个练习

  1. 把这篇的并查集改成读入 20 个随机一维点,阈值从 0 扫到最大间隔,打印每次合并和块数;再验证块数等于「间隔大于阈值的相邻对数加一」。
  2. 拿一个封闭网格,数出 V、E、F,用 χ = V − E + F 算亏格 g = (2 − χ)/2;再故意删掉一个面,看公式还成不成立,解释为什么。
  3. 写一个函数遍历边表,统计每条边挂的面数;找出所有面数为 1 的边和大于 2 的边,各打印几条。
  4. 对一批二维点逐步加高斯噪声,固定阈值打印连通分量数;再固定噪声扫阈值,看两组数字是不是同一种敏感。
  5. 想一个保拓扑但不保形状的操作,比如把杯子把手弯成甜甜圈,或只做重网格化而不改亏格;说明它保住了哪个不变量、破坏了哪个几何量。

本组收尾:从连续到应用

这一组从「连续」的直觉开始。数轴上的连续,是说画曲线不用抬笔;推广到一般空间,就得把「靠近」说清楚,于是有了开集:集合里每个点都带一小圈邻居,圈可任意小,但必须整个落在集合里。

有了开集,连续映射的定义就能落地:目标空间里每个开集,原像也是开集。这句话等价于靠近的点映过去还靠近,也等价于 ε-δ 那一套。把双向连续的双射挑出来就是同胚;同胚之下的性质叫拓扑性质,洞的个数、连通块数、紧致性都在里面。再往后是紧致与连通,决定了极限能不能取、中间值能不能用;加上「局部看起来像 ℝn」就是流形。网格和点云采样处理的是流形的离散近似,这篇的应用就是在离散近似上算连通块数和洞数。

把线收回来:连续给出靠近,开集给出局部,连续映射保住靠近,同胚给出一样,紧致与连通给出整体性质,流形给出可以局部坐标化,应用则是在网格和点云上把这些量算出来。中间任何一环理解偏了,后面都会以很具体的方式出错。本组到此结束,下一组进入概率与统计,从随机性怎么描述讲起;那里的几乎必然和依分布收敛会反复用到这一组的极限与连续,只是讨论对象换成了随机的。