4. 边坍缩算法实战：半边数据结构、坍缩代价计算、实现一个简单的边坍缩简化器

好，我们终于到了动手环节。前面几章讲了理论、讲了度量，这一章咱们直接撸代码——实现一个能跑的边坍缩简化器。

说实话，我第一次实现边坍缩的时候，踩了不少坑。最头疼的不是算法本身，而是数据结构。你想想看，每次坍缩一条边，要删两个面、改一堆顶点的连接关系，如果数据结构选得不好，代码写起来简直是一场灾难。

4.1 为什么选半边数据结构？

网格简化里，最常见的三种数据结构是：

我个人习惯用半边数据结构。为什么？因为边坍缩本质上就是「把一条边变成顶点，同时更新周围所有半边的关系」。半边结构把每条边拆成两个方向相反的半边，每个半边知道自己属于哪个面、下一条半边是谁、对面的半边是谁——这些信息在坍缩时太有用了。

4.2 半边数据结构的核心定义

先看代码。我习惯用 C++ 来写，但思路可以移植到任何语言。

// 顶点
struct Vertex {
    Vec3 position;      // 位置
    int id;             // 顶点索引
    HalfEdge* outgoing; // 从该顶点出发的任意一条半边
};

// 半边
struct HalfEdge {
    Vertex* start;      // 起点
    HalfEdge* twin;     // 对边（方向相反的那条半边）
    HalfEdge* next;     // 当前面上的下一条半边
    Face* face;         // 所属的面
};

// 面
struct Face {
    HalfEdge* edge;     // 面上任意一条半边
    int id;             // 面索引
};

// 边（为了方便，我们额外存一条边结构）
struct Edge {
    HalfEdge* half;     // 任选一条半边
    float collapseCost; // 坍缩代价
};

嗯，这里要注意：半边结构里没有显式的「边」结构。一条边由一对 twin 半边隐式表示。但为了方便排序，我们会额外创建一个 Edge 结构来存代价。

4.3 坍缩代价计算

代价计算是边坍缩的灵魂。我们之前讲过 QEM（二次误差度量），这里就用它。

每条边 (v1, v2) 坍缩到新顶点 v' 的代价是：

cost(v1, v2) = v'^T * (Q1 + Q2) * v'

其中 Q1 和 Q2 分别是 v1 和 v2 的二次误差矩阵。v' 的位置我们取使得代价最小的点——也就是解一个线性方程组。

代码实现大致是这样：

float computeCollapseCost(Edge* e) {
    Vertex* v1 = e->half->start;
    Vertex* v2 = e->half->twin->start;

    // 合并两个顶点的 Q 矩阵
    Mat4 Q = v1->Q + v2->Q;

    // 求解最优坍缩位置
    Vec3 bestPos;
    float cost;

    // 尝试解线性方程组 [Qxx Qxy Qxz Qxw; ...]
    // 如果矩阵可逆，取最优位置
    // 如果不可逆，取中点或端点中代价较小的
    if (solveOptimalPosition(Q, bestPos)) {
        cost = evaluateQuadric(Q, bestPos);
    } else {
        // 退化为中点或端点
        Vec3 mid = (v1->pos + v2->pos) * 0.5f;
        cost = min(evaluateQuadric(Q, v1->pos),
                   min(evaluateQuadric(Q, v2->pos),
                       evaluateQuadric(Q, mid)));
        bestPos = (cost == evaluateQuadric(Q, v1->pos)) ? v1->pos :
                  (cost == evaluateQuadric(Q, v2->pos)) ? v2->pos : mid;
    }

    e->collapseCost = cost;
    e->optimalPos = bestPos;
    return cost;
}

4.4 边坍缩的核心流程

有了数据结构和代价计算，整个简化器的主循环其实很清晰：

1. 初始化：为每个顶点计算初始 Q 矩阵（基于邻接面的平面方程）
2. 计算所有边的代价：遍历所有边，调用 computeCollapseCost
3. 建最小堆：按代价从小到大排序所有边
4. 循环坍缩：每次从堆顶取代价最小的边，执行坍缩操作，然后更新受影响的其他边的代价
5. 终止条件：达到目标面数，或堆顶代价超过阈值

这里最关键的步骤是第 4 步里的「更新受影响的其他边的代价」。坍缩一条边后，周围顶点的 Q 矩阵变了，邻接边的代价也要重新算。但你不能全量重算——那样复杂度是 O(n²)。

我用的策略是：只重算坍缩顶点周围 1-ring 邻域内的边。具体来说：

• 坍缩后，新顶点 v' 替代了原来的 v1 和 v2
• 所有以 v1 或 v2 为端点的边，都要重新计算代价
• 这些边最多也就几十条，跟网格规模无关

4.5 坍缩操作：半边结构的真正威力

终于到了最刺激的部分——实际执行坍缩。这一步如果数据结构没选好，代码会写得想哭。但用半边结构，其实就几个指针操作。

坍缩边 (v1, v2) 到 v' 的步骤：

1. 把 v1 和 v2 的所有邻接半边重新指向 v'
2. 删除两个邻接面（如果存在）
3. 更新 v' 的位置为最优位置
4. 重新计算 v' 的 Q 矩阵
5. 标记 v1 和 v2 为已删除

伪代码：

void collapseEdge(Edge* e) {
    HalfEdge* h = e->half;
    Vertex* v1 = h->start;
    Vertex* v2 = h->twin->start;
    Vec3 newPos = e->optimalPos;

    // 1. 把 v1 和 v2 的所有半边指向新顶点
    for (HalfEdge* he : getOutgoingEdges(v1)) {
        he->start = v2;  // 重用 v2 作为新顶点
    }
    // 注意：这里要小心处理 v1 和 v2 之间的半边

    // 2. 删除两个邻接面
    deleteFace(h->face);
    deleteFace(h->twin->face);

    // 3. 更新位置和 Q 矩阵
    v2->pos = newPos;
    v2->Q = v1->Q + v2->Q;

    // 4. 标记 v1 为已删除
    v1->deleted = true;

    // 5. 重新计算 v2 邻域内所有边的代价
    for (Edge* adj : getAdjacentEdges(v2)) {
        computeCollapseCost(adj);
        updateHeap(adj);
    }
}

4.6 完整简化器的结构图

下面这张图展示了简化器的整体架构和数据流：

4.7 实现中的几个关键细节

写到这里，我觉得有必要再强调几个容易出问题的地方：

• 堆中边的有效性：坍缩后，堆里可能还残留着已经失效的边。每次从堆顶取边时，要检查该边是否仍然有效（两个顶点都没被删除）。
• 边界处理：网格边界上的边，坍缩时要特别小心。我一般会禁止坍缩边界边，或者给边界边加一个很大的惩罚系数（比如乘以 1000）。
• 面翻转检测：坍缩后，新顶点位置可能导致周围面法线翻转。我习惯在坍缩前先做一次法线检查，如果翻转了就跳过这条边。

4.8 性能数据参考

最后给一组我实测的性能数据，方便你评估自己的实现：

可以看到，半边构建只占总时间的 3% 左右，大头全在坍缩循环里。而坍缩循环里最耗时的又是「更新邻域代价」这一步——因为每次都要重新解线性方程组。

如果你追求极致性能，可以考虑用增量更新的技巧：坍缩后不重新计算所有邻域边的代价，而是只更新那些变化较大的边。不过这个优化实现起来比较复杂，初学者可以先跳过。