做游戏资产的同学给我看过一个减面之后的角色模型。原本八万面,压到一万二千面,轮廓几乎没变,可一放进引擎就漏光:后脑勺和腋下破了几个洞,法线朝向反了,阴影上出现黑斑。减面算法把顶点数和面数都压下去了,也努力保住了形状,但它没有保证一件事:这个表面仍然是封闭的。
另一类现场在数据分析里。一批高维样本用降维方法压到二维,散点图上两个原来分得很开的簇粘成一片,评审问「这两个类是不是同一批用户」,谁也答不上来。降维优化的目标是让近的点仍然近,不负责让不连通的点保持不连通,也不负责保住数据里的环。环被压扁成一条线,图上看不出来。
这两个问题的共同点是:几何细节错了还能改,拓扑结构错了很难补。这里的拓扑指研究「连续变形下不变的性质」的数学分支:把橡皮泥捏成别的形状,只要不撕开、不粘合,有几个洞、是不是一整块都不变。图形学关心网格的连通性和洞的个数,数据分析关心点云在不同尺度下有多少块、有多少个环。这篇讲这两处怎么用拓扑,以及它什么时候会骗你。
图形学里的拓扑:网格先要问「是不是流形」
三维模型在文件里是一张多边形网格(mesh):顶点、边、面三张表,外加连接关系。拓扑决定了后面哪些操作能做。
第一个要查的性质是流形(manifold)。直观说法:网格表面上的每个点,放大看都像一张平面圆盘。落到可检查的规则上,就是每条边最多被两个面共用,每个顶点的邻域连成一片,不能两个锥尖对尖。满足这条才是二维流形网格。
两条容易混的。亏格(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 时的四个块:{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 要和几何、统计一起用,不适合单独当判据。
当天能验证的五个练习
- 把这篇的并查集改成读入 20 个随机一维点,阈值从 0 扫到最大间隔,打印每次合并和块数;再验证块数等于「间隔大于阈值的相邻对数加一」。
- 拿一个封闭网格,数出 V、E、F,用 χ = V − E + F 算亏格 g = (2 − χ)/2;再故意删掉一个面,看公式还成不成立,解释为什么。
- 写一个函数遍历边表,统计每条边挂的面数;找出所有面数为 1 的边和大于 2 的边,各打印几条。
- 对一批二维点逐步加高斯噪声,固定阈值打印连通分量数;再固定噪声扫阈值,看两组数字是不是同一种敏感。
- 想一个保拓扑但不保形状的操作,比如把杯子把手弯成甜甜圈,或只做重网格化而不改亏格;说明它保住了哪个不变量、破坏了哪个几何量。
本组收尾:从连续到应用
这一组从「连续」的直觉开始。数轴上的连续,是说画曲线不用抬笔;推广到一般空间,就得把「靠近」说清楚,于是有了开集:集合里每个点都带一小圈邻居,圈可任意小,但必须整个落在集合里。
有了开集,连续映射的定义就能落地:目标空间里每个开集,原像也是开集。这句话等价于靠近的点映过去还靠近,也等价于 ε-δ 那一套。把双向连续的双射挑出来就是同胚;同胚之下的性质叫拓扑性质,洞的个数、连通块数、紧致性都在里面。再往后是紧致与连通,决定了极限能不能取、中间值能不能用;加上「局部看起来像 ℝn」就是流形。网格和点云采样处理的是流形的离散近似,这篇的应用就是在离散近似上算连通块数和洞数。
把线收回来:连续给出靠近,开集给出局部,连续映射保住靠近,同胚给出一样,紧致与连通给出整体性质,流形给出可以局部坐标化,应用则是在网格和点云上把这些量算出来。中间任何一环理解偏了,后面都会以很具体的方式出错。本组到此结束,下一组进入概率与统计,从随机性怎么描述讲起;那里的几乎必然和依分布收敛会反复用到这一组的极限与连续,只是讨论对象换成了随机的。