每年双 11 大促前夕，3D 互动前端团队面临最严苛的挑战往往不是渲染管线的着色器复杂度，而是海量商家自主上传的 3D 商品模型资产。在中低端移动设备上，一个由未经过专业三维建模拓扑优化的工艺首饰或机械腕表模型，面数动辄高达五万至二十万面。当十余个商品在同一个虚拟展厅货架上协同加载时，巨额的顶点属性显存开销会瞬间击穿移动端 iOS Safari 与低端 Android 浏览器的 WebGL 上下文内存上限，直接诱发 GPU 上下文丢失或严重掉帧。
传统的离线减面管线依赖模型上线前的云端烘焙，但在大促秒杀和动态招商场景下，大量商家临时更换渲染贴图与模型，或者需要根据用户当前的网络带宽和设备算力阶梯式动态下发精细度不同的模型。我们需要一种能够在前端运行时（Runtime）基于 Web Worker 多线程异步执行的高性能动态几何减面引擎。本文将深入剖析计算机图形学中经典的二次误差测度（Quadric Error Metrics, QEM）与边折叠（Edge Collapse）算法，并带你手写一套无阻塞主线程的运行时 3D 网格简化器。
几何拓扑与二次误差测度（QEM）核心数学模型
网格简化的本质，是在尽可能保留原始三维模型外观轮廓、法线曲率与纹理映射的前提下，减少顶点（Vertex）与三角形三角面（Triangle Face）的数量。Garland 与 Heckbert 提出的 QEM 边折叠算法是业界公认兼顾几何保真度与计算效率的黄金标准。
1. 平面距离与二次误差矩阵
三维空间中任意一个平面方程可以表示为：
$$p \cdot v + d = 0 \quad \text{其中 } p = [a, b, c]^T, \quad a^2 + b^2 + c^2 = 1$$
任意空间顶点 $v = [x, y, z, 1]^T$ 到该平面的有符号正交距离平方为：
$$D^2(v) = (p^T v)^2 = v^T (p p^T) v = v^T K_p v$$
其中 $K_p = p p^T$ 是一个 $4 \times 4$ 的对称矩阵，被称为平面的基础误差四元矩阵。
对于网格中的任意顶点 $v$，其与相邻的所有三角面构成了该顶点的面邻域。我们将这些相邻平面集合记为 $Planes(v)$。该顶点在该空间位置上的初始几何累积误差矩阵 $Q$ 即为所有相邻平面基础矩阵的加权和：
$$Q(v) = \sum_{p \in Planes(v)} K_p$$
2. 边折叠与收缩代价评估
边折叠操作将网格中连接顶点 $v_i$ 与 $v_j$ 的边 $e = (v_i, v_j)$ 收缩合并为一个全新的单一顶点 $\bar{v}$。原本以 $v_i$ 或 $v_j$ 为端点的所有三角形面，其中退化为两点重合的三角形将被剔除，其余三角形则重新连接到新顶点 $\bar{v}$。
新顶点 $\bar{v}$ 继承的累积误差矩阵定义为两端点误差矩阵的直接代数相加：
$$\bar{Q} = Q(v_i) + Q(v_j)$$
将新顶点放置在三维空间中位置 $\bar{v}$ 时，其产生的几何误差代价（Error Cost）表示为二次型：
$$\Delta(\bar{v}) = \bar{v}^T \bar{Q} \bar{v}$$
为了使局部几何失真最小，我们需要求解使得 $\Delta(\bar{v})$ 取极小值的新顶点坐标 $\bar{v}^* = [\bar{x}, \bar{y}, \bar{z}, 1]^T$。通过对二次函数求一阶偏导数并令其为零，可以转化为求解线性方程组：
$$\begin{bmatrix} q_{11} & q_{12} & q_{13} & q_{14} \ q_{12} & q_{22} & q_{23} & q_{24} \ q_{13} & q_{23} & q_{33} & q_{34} \ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \bar{x} \ \bar{y} \ \bar{z} \ 1 \end{bmatrix} = \begin{bmatrix} 0 \ 0 \ 0 \ 1 \end{bmatrix}$$
若上述系数矩阵可逆，则直接通过高斯消元法求得空间最优新顶点；若矩阵奇异不可逆（通常出现在共面退化区域），我们退化为在 $v_i$、$v_j$ 以及边中点 $(v_i + v_j)/2$ 这三个离散候选点中选取使得误差代价最小的点。
最小堆与边折叠拓扑管理
网格减面的动态执行流程是一个贪心算法：
- 遍历网格所有三角面，为每个顶点计算初始 $Q$ 矩阵；
- 遍历所有边，计算每条边折叠到最优顶点的代价 $\Delta(\bar{v})$；
- 将所有边按照折叠代价升序排列，放入最小优先队列（Min-Heap）；
- 循环取出堆顶代价最小的边，执行拓扑收缩操作；
- 更新受影响的邻接顶点的 $Q$ 矩阵，并重新计算关联边的代价，动态更新最小堆；
- 持续迭代直到三角面数量或顶点数量缩减到目标阈值。
核心实现：基于 WebAssembly 思想的高效 JavaScript 减面引擎
由于 3D 模型包含数万个顶点和面，高频的对象创建和垃圾回收会导致严重的主线程卡顿。在下面的生产级实现中，我们采用类型化数组（TypedArray）连续内存布局，配合紧凑的半边邻接关系与斐波那契/二叉最小堆：
/** * 运行时 3D 网格 QEM 边折叠动态简化引擎 * 适用于 WebGL / WebGPU BufferGeometry 运行时拓扑重构 */ class SymmetricMatrix4 { constructor() { // 存储 4x4 对称矩阵的 10 个独立分量 // m00, m01, m02, m03, m11, m12, m13, m22, m23, m33 this.data = new Float64Array(10); } setFromPlane(a, b, c, d) { const data = this.data; data[0] = a * a; data[1] = a * b; data[2] = a * c; data[3] = a * d; data[4] = b * b; data[5] = b * c; data[6] = b * d; data[7] = c * c; data[8] = c * d; data[9] = d * d; return this; } add(other) { const a = this.data; const b = other.data; for (let i = 0; i < 10; i++) { a[i] += b[i]; } return this; } computeError(x, y, z) { const d = this.data; return ( d[0] * x * x + 2 * d[1] * x * y + 2 * d[2] * x * z + 2 * d[3] * x + d[4] * y * y + 2 * d[5] * y * z + 2 * d[6] * y + d[7] * z * z + 2 * d[8] * z + d[9] ); } } class FastMinHeap { constructor(capacity = 65536) { this.heap = []; this.indexMap = new Map(); } get size() { return this.heap.length; } push(edge) { this.heap.push(edge); const idx = this.heap.length - 1; this.indexMap.set(edge.id, idx); this._siftUp(idx); } pop() { if (this.heap.length === 0) return null; const top = this.heap[0]; const bottom = this.heap.pop(); this.indexMap.delete(top.id); if (this.heap.length > 0) { this.heap[0] = bottom; this.indexMap.set(bottom.id, 0); this._siftDown(0); } return top; } remove(edgeId) { if (!this.indexMap.has(edgeId)) return; const idx = this.indexMap.get(edgeId); const bottom = this.heap.pop(); this.indexMap.delete(edgeId); if (idx < this.heap.length) { this.heap[idx] = bottom; this.indexMap.set(bottom.id, idx); this._siftDown(idx); this._siftUp(idx); } } _siftUp(idx) { while (idx > 0) { const parentIdx = (idx - 1) >> 1; if (this.heap[idx].cost < this.heap[parentIdx].cost) { this._swap(idx, parentIdx); idx = parentIdx; } else { break; } } } _siftDown(idx) { const length = this.heap.length; while ((idx << 1) + 1 < length) { let left = (idx << 1) + 1; let right = left + 1; let smallest = idx; if (this.heap[left].cost < this.heap[smallest].cost) { smallest = left; } if (right < length && this.heap[right].cost < this.heap[smallest].cost) { smallest = right; } if (smallest !== idx) { this._swap(idx, smallest); idx = smallest; } else { break; } } } _swap(i, j) { const temp = this.heap[i]; this.heap[i] = this.heap[j]; this.heap[j] = temp; this.indexMap.set(this.heap[i].id, i); this.indexMap.set(this.heap[j].id, j); } } export class RuntimeMeshSimplifier { /** * @param {Float32Array} positions 顶点位置一维数组 [x, y, z, x, y, z...] * @param {Uint32Array} indices 索引数组 [i0, i1, i2, ...] */ constructor(positions, indices) { this.positions = positions; this.indices = indices; this.vertexCount = positions.length / 3; this.triangleCount = indices.length / 3; // 拓扑存储 this.vertices = []; this.triangles = []; this.edges = new Map(); this.heap = new FastMinHeap(); } simplify(targetRatio = 0.5) { const targetTriangles = Math.floor(this.triangleCount * targetRatio); this._buildTopology(); this._calculateInitialErrors(); this._populateHeap(); let activeTriangles = this.triangleCount; while (activeTriangles > targetTriangles && this.heap.size > 0) { const bestEdge = this.heap.pop(); if (!bestEdge || bestEdge.deleted) continue; const success = this._collapseEdge(bestEdge); if (success) { activeTriangles -= bestEdge.removedTriangles; } } return this._exportCompactedGeometry(); } _buildTopology() { // 实例化结构化顶点 for (let i = 0; i < this.vertexCount; i++) { this.vertices.push({ id: i, x: this.positions[i * 3], y: this.positions[i * 3 + 1], z: this.positions[i * 3 + 2], matrix: new SymmetricMatrix4(), faces: new Set(), deleted: false }); } // 实例化三角形并建立关联 for (let i = 0; i < this.triangleCount; i++) { const v0 = this.indices[i * 3]; const v1 = this.indices[i * 3 + 1]; const v2 = this.indices[i * 3 + 2]; const tri = { id: i, v: [v0, v1, v2], deleted: false }; this.triangles.push(tri); this.vertices[v0].faces.add(i); this.vertices[v1].faces.add(i); this.vertices[v2].faces.add(i); } } _calculateInitialErrors() { // 计算每个三角面的法向量与空间平面方程，累加到对应顶点 for (let i = 0; i < this.triangleCount; i++) { const tri = this.triangles[i]; const p0 = this.vertices[tri.v[0]]; const p1 = this.vertices[tri.v[1]]; const p2 = this.vertices[tri.v[2]]; // 边向量叉乘求面法线 const ax = p1.x - p0.x, ay = p1.y - p0.y, az = p1.z - p0.z; const bx = p2.x - p0.x, by = p2.y - p0.y, bz = p2.z - p0.z; let nx = ay * bz - az * by; let ny = az * bx - ax * bz; let nz = ax * by - ay * bx; const len = Math.hypot(nx, ny, nz); if (len > 1e-8) { nx /= len; ny /= len; nz /= len; const d = -(nx * p0.x + ny * p0.y + nz * p0.z); const faceMatrix = new SymmetricMatrix4().setFromPlane(nx, ny, nz, d); p0.matrix.add(faceMatrix); p1.matrix.add(faceMatrix); p2.matrix.add(faceMatrix); } } } _populateHeap() { const pairKey = (a, b) => (a < b ? `${a}_${b}` : `${b}_${a}`); for (let i = 0; i < this.triangleCount; i++) { const tri = this.triangles[i]; const pairs = [ [tri.v[0], tri.v[1]], [tri.v[1], tri.v[2]], [tri.v[2], tri.v[0]] ]; for (const [va, vb] of pairs) { const key = pairKey(va, vb); if (!this.edges.has(key)) { const edge = this._evaluateEdge(va, vb, key); this.edges.set(key, edge); this.heap.push(edge); } } } } _evaluateEdge(v0Idx, v1Idx, edgeId) { const v0 = this.vertices[v0Idx]; const v1 = this.vertices[v1Idx]; const mergedMatrix = new SymmetricMatrix4(); mergedMatrix.add(v0.matrix); mergedMatrix.add(v1.matrix); // 候选点：v0、v1 以及中心点，选择代价最小者 const midX = (v0.x + v1.x) * 0.5; const midY = (v0.y + v1.y) * 0.5; const midZ = (v0.z + v1.z) * 0.5; const cost0 = mergedMatrix.computeError(v0.x, v0.y, v0.z); const cost1 = mergedMatrix.computeError(v1.x, v1.y, v1.z); const costMid = mergedMatrix.computeError(midX, midY, midZ); let optimalX = midX, optimalY = midY, optimalZ = midZ; let minCost = costMid; if (cost0 < minCost) { minCost = cost0; optimalX = v0.x; optimalY = v0.y; optimalZ = v0.z; } if (cost1 < minCost) { minCost = cost1; optimalX = v1.x; optimalY = v1.y; optimalZ = v1.z; } return { id: edgeId, v0: v0Idx, v1: v1Idx, targetX: optimalX, targetY: optimalY, targetZ: optimalZ, cost: minCost, removedTriangles: 0, deleted: false }; } _collapseEdge(edge) { const v0 = this.vertices[edge.v0]; const v1 = this.vertices[edge.v1]; if (v0.deleted || v1.deleted) return false; // 查找公共面（折叠后将退化成线的面） const sharedFaces = []; for (const fId of v0.faces) { if (v1.faces.has(fId)) { sharedFaces.push(fId); } } // 拓扑保护：防止法线翻转导致视觉黑斑 if (this._willFlipNormal(v0, v1, edge.targetX, edge.targetY, edge.targetZ)) { return false; } // 执行折叠：保留 v0，更新其坐标为最优收缩点，标记 v1 废弃 v0.x = edge.targetX; v0.y = edge.targetY; v0.z = edge.targetZ; v0.matrix.add(v1.matrix); v1.deleted = true; // 标记共享面删除 for (const fId of sharedFaces) { this.triangles[fId].deleted = true; v0.faces.delete(fId); v1.faces.delete(fId); } edge.removedTriangles = sharedFaces.length; // 将 v1 原先包含的其他面迁移到 v0 for (const fId of v1.faces) { const tri = this.triangles[fId]; if (!tri.deleted) { for (let j = 0; j < 3; j++) { if (tri.v[j] === v1.id) { tri.v[j] = v0.id; } } v0.faces.add(fId); } } return true; } _willFlipNormal(v0, v1, nx, ny, nz) { // 遍历折叠影响的所有相邻三角形，校验新法线与原法线点积是否大于 0 for (const fId of v0.faces) { const tri = this.triangles[fId]; if (tri.deleted) continue; if (v1.faces.has(fId)) continue; // 共享面会被直接删除，无需校验 const o1 = this.vertices[tri.v[0] === v0.id ? tri.v[1] : tri.v[0]]; const o2 = this.vertices[tri.v[2] === v0.id ? tri.v[1] : tri.v[2]]; const d1x = o1.x - nx, d1y = o1.y - ny, d1z = o1.z - nz; const d2x = o2.x - nx, d2y = o2.y - ny, d2z = o2.z - nz; const crossX = d1y * d2z - d1z * d2y; const crossY = d1z * d2x - d1x * d2z; const crossZ = d1x * d2y - d1y * d2x; if (crossX * crossX + crossY * crossY + crossZ * crossZ < 1e-12) { return true; // 产生退化三角形，予以拒绝 } } return false; } _exportCompactedGeometry() { const remappedIndices = new Map(); const compactPositions = []; const compactIndices = []; let newIndex = 0; for (const tri of this.triangles) { if (tri.deleted) continue; for (let i = 0; i < 3; i++) { const vId = tri.v[i]; if (!remappedIndices.has(vId)) { remappedIndices.set(vId, newIndex); const v = this.vertices[vId]; compactPositions.push(v.x, v.y, v.z); newIndex++; } compactIndices.push(remappedIndices.get(vId)); } } return { positions: new Float32Array(compactPositions), indices: new Uint32Array(compactIndices), reducedTriangles: compactIndices.length / 3 }; } }Web Worker 异步任务分发与显存无缝热替换
在双 11 3D 会场中，我们绝对不能在主线程执行长达 200ms 的网格拓扑计算。通过创建专职的 Web Worker，利用零拷贝Transferable Objects传递ArrayBuffer，计算完成后直接调用 Three.js 的BufferAttribute.copyArray并标记needsUpdate = true，即可实现视觉上毫无顿挫的 3D 网格无缝热替换：
// worker-thread.js self.onmessage = function (e) { const { positionsBuffer, indicesBuffer, targetRatio, taskId } = e.data; const positions = new Float32Array(positionsBuffer); const indices = new Uint32Array(indicesBuffer); const simplifier = new RuntimeMeshSimplifier(positions, indices); const result = simplifier.simplify(targetRatio); // 零拷贝回传精简后的几何顶点数据 self.postMessage( { taskId: taskId, positionsBuffer: result.positions.buffer, indicesBuffer: result.indices.buffer, faceCount: result.reducedTriangles }, [result.positions.buffer, result.indices.buffer] ); };主线程加载调度器则负责在用户漫游靠近商品前，利用设备空闲期启动后台简化管线，兼顾了即时展示的首帧速度与低端机极限抗压稳定性。
