每年雙 11 大促前夕3D 互動前端團隊面臨最嚴苛的挑戰(zhàn)往往不是渲染管線的著色器復雜度而是海量商家自主上傳的 3D 商品模型資產。在中低端移動設備上一個由未經過專業(yè)三維建模拓撲優(yōu)化的工藝首飾或機械腕表模型面數動輒高達五萬至二十萬面。當十余個商品在同一個虛擬展廳貨架上協(xié)同加載時巨額的頂點屬性顯存開銷會瞬間擊穿移動端 iOS Safari 與低端 Android 瀏覽器的 WebGL 上下文內存上限直接誘發(fā) GPU 上下文丟失或嚴重掉幀。傳統(tǒng)的離線減面管線依賴模型上線前的云端烘焙但在大促秒殺和動態(tài)招商場景下大量商家臨時更換渲染貼圖與模型或者需要根據用戶當前的網絡帶寬和設備算力階梯式動態(tài)下發(fā)精細度不同的模型。我們需要一種能夠在前端運行時Runtime基于 Web Worker 多線程異步執(zhí)行的高性能動態(tài)幾何減面引擎。本文將深入剖析計算機圖形學中經典的二次誤差測度Quadric Error Metrics, QEM與邊折疊Edge Collapse算法并帶你手寫一套無阻塞主線程的運行時 3D 網格簡化器。幾何拓撲與二次誤差測度QEM核心數學模型網格簡化的本質是在盡可能保留原始三維模型外觀輪廓、法線曲率與紋理映射的前提下減少頂點Vertex與三角形三角面Triangle Face的數量。Garland 與 Heckbert 提出的 QEM 邊折疊算法是業(yè)界公認兼顧幾何保真度與計算效率的黃金標準。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}$$若上述系數矩陣可逆則直接通過高斯消元法求得空間最優(yōu)新頂點若矩陣奇異不可逆通常出現在共面退化區(qū)域我們退化為在 $v_i$、$v_j$ 以及邊中點 $(v_i v_j)/2$ 這三個離散候選點中選取使得誤差代價最小的點。最小堆與邊折疊拓撲管理網格減面的動態(tài)執(zhí)行流程是一個貪心算法遍歷網格所有三角面為每個頂點計算初始 $Q$ 矩陣遍歷所有邊計算每條邊折疊到最優(yōu)頂點的代價 $\Delta(\bar{v})$將所有邊按照折疊代價升序排列放入最小優(yōu)先隊列Min-Heap循環(huán)取出堆頂代價最小的邊執(zhí)行拓撲收縮操作更新受影響的鄰接頂點的 $Q$ 矩陣并重新計算關聯邊的代價動態(tài)更新最小堆持續(xù)迭代直到三角面數量或頂點數量縮減到目標閾值。核心實現基于 WebAssembly 思想的高效 JavaScript 減面引擎由于 3D 模型包含數萬個頂點和面高頻的對象創(chuàng)建和垃圾回收會導致嚴重的主線程卡頓。在下面的生產級實現中我們采用類型化數組TypedArray連續(xù)內存布局配合緊湊的半邊鄰接關系與斐波那契/二叉最小堆/** * 運行時 3D 網格 QEM 邊折疊動態(tài)簡化引擎 * 適用于 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}_$ : $_${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; } // 執(zhí)行折疊保留 v0更新其坐標為最優(yōu)收縮點標記 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 異步任務分發(fā)與顯存無縫熱替換在雙 11 3D 會場中我們絕對不能在主線程執(zhí)行長達 200ms 的網格拓撲計算。通過創(chuàng)建專職的 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] ); };主線程加載調度器則負責在用戶漫游靠近商品前利用設備空閑期啟動后臺簡化管線兼顧了即時展示的首幀速度與低端機極限抗壓穩(wěn)定性。