每年雙 11 大促前夕3D 互動(dòng)前端團(tuán)隊(duì)面臨最嚴(yán)苛的挑戰(zhàn)往往不是渲染管線的著色器復(fù)雜度而是海量商家自主上傳的 3D 商品模型資產(chǎn)。在中低端移動(dòng)設(shè)備上一個(gè)由未經(jīng)過專業(yè)三維建模拓?fù)鋬?yōu)化的工藝首飾或機(jī)械腕表模型面數(shù)動(dòng)輒高達(dá)五萬至二十萬面。當(dāng)十余個(gè)商品在同一個(gè)虛擬展廳貨架上協(xié)同加載時(shí)巨額的頂點(diǎn)屬性顯存開銷會(huì)瞬間擊穿移動(dòng)端 iOS Safari 與低端 Android 瀏覽器的 WebGL 上下文內(nèi)存上限直接誘發(fā) GPU 上下文丟失或嚴(yán)重掉幀。傳統(tǒng)的離線減面管線依賴模型上線前的云端烘焙但在大促秒殺和動(dòng)態(tài)招商場(chǎng)景下大量商家臨時(shí)更換渲染貼圖與模型或者需要根據(jù)用戶當(dāng)前的網(wǎng)絡(luò)帶寬和設(shè)備算力階梯式動(dòng)態(tài)下發(fā)精細(xì)度不同的模型。我們需要一種能夠在前端運(yùn)行時(shí)Runtime基于 Web Worker 多線程異步執(zhí)行的高性能動(dòng)態(tài)幾何減面引擎。本文將深入剖析計(jì)算機(jī)圖形學(xué)中經(jīng)典的二次誤差測(cè)度Quadric Error Metrics, QEM與邊折疊Edge Collapse算法并帶你手寫一套無阻塞主線程的運(yùn)行時(shí) 3D 網(wǎng)格簡(jiǎn)化器。幾何拓?fù)渑c二次誤差測(cè)度QEM核心數(shù)學(xué)模型網(wǎng)格簡(jiǎn)化的本質(zhì)是在盡可能保留原始三維模型外觀輪廓、法線曲率與紋理映射的前提下減少頂點(diǎn)Vertex與三角形三角面Triangle Face的數(shù)量。Garland 與 Heckbert 提出的 QEM 邊折疊算法是業(yè)界公認(rèn)兼顧幾何保真度與計(jì)算效率的黃金標(biāo)準(zhǔn)。1. 平面距離與二次誤差矩陣三維空間中任意一個(gè)平面方程可以表示為$$p \cdot v d 0 \quad \text{其中 } p [a, b, c]^T, \quad a^2 b^2 c^2 1$$任意空間頂點(diǎn) $v [x, y, z, 1]^T$ 到該平面的有符號(hào)正交距離平方為$$D^2(v) (p^T v)^2 v^T (p p^T) v v^T K_p v$$其中 $K_p p p^T$ 是一個(gè) $4 \times 4$ 的對(duì)稱矩陣被稱為平面的基礎(chǔ)誤差四元矩陣。對(duì)于網(wǎng)格中的任意頂點(diǎn) $v$其與相鄰的所有三角面構(gòu)成了該頂點(diǎn)的面鄰域。我們將這些相鄰平面集合記為 $Planes(v)$。該頂點(diǎn)在該空間位置上的初始幾何累積誤差矩陣 $Q$ 即為所有相鄰平面基礎(chǔ)矩陣的加權(quán)和$$Q(v) \sum_{p \in Planes(v)} K_p$$2. 邊折疊與收縮代價(jià)評(píng)估邊折疊操作將網(wǎng)格中連接頂點(diǎn) $v_i$ 與 $v_j$ 的邊 $e (v_i, v_j)$ 收縮合并為一個(gè)全新的單一頂點(diǎn) $\bar{v}$。原本以 $v_i$ 或 $v_j$ 為端點(diǎn)的所有三角形面其中退化為兩點(diǎn)重合的三角形將被剔除其余三角形則重新連接到新頂點(diǎn) $\bar{v}$。新頂點(diǎn) $\bar{v}$ 繼承的累積誤差矩陣定義為兩端點(diǎn)誤差矩陣的直接代數(shù)相加$$\bar{Q} Q(v_i) Q(v_j)$$將新頂點(diǎn)放置在三維空間中位置 $\bar{v}$ 時(shí)其產(chǎn)生的幾何誤差代價(jià)Error Cost表示為二次型$$\Delta(\bar{v}) \bar{v}^T \bar{Q} \bar{v}$$為了使局部幾何失真最小我們需要求解使得 $\Delta(\bar{v})$ 取極小值的新頂點(diǎn)坐標(biāo) $\bar{v}^* [\bar{x}, \bar{y}, \bar{z}, 1]^T$。通過對(duì)二次函數(shù)求一階偏導(dǎo)數(shù)并令其為零可以轉(zhuǎn)化為求解線性方程組$$\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}$$若上述系數(shù)矩陣可逆則直接通過高斯消元法求得空間最優(yōu)新頂點(diǎn)若矩陣奇異不可逆通常出現(xiàn)在共面退化區(qū)域我們退化為在 $v_i$、$v_j$ 以及邊中點(diǎn) $(v_i v_j)/2$ 這三個(gè)離散候選點(diǎn)中選取使得誤差代價(jià)最小的點(diǎn)。最小堆與邊折疊拓?fù)涔芾砭W(wǎng)格減面的動(dòng)態(tài)執(zhí)行流程是一個(gè)貪心算法遍歷網(wǎng)格所有三角面為每個(gè)頂點(diǎn)計(jì)算初始 $Q$ 矩陣遍歷所有邊計(jì)算每條邊折疊到最優(yōu)頂點(diǎn)的代價(jià) $\Delta(\bar{v})$將所有邊按照折疊代價(jià)升序排列放入最小優(yōu)先隊(duì)列Min-Heap循環(huán)取出堆頂代價(jià)最小的邊執(zhí)行拓?fù)涫湛s操作更新受影響的鄰接頂點(diǎn)的 $Q$ 矩陣并重新計(jì)算關(guān)聯(lián)邊的代價(jià)動(dòng)態(tài)更新最小堆持續(xù)迭代直到三角面數(shù)量或頂點(diǎn)數(shù)量縮減到目標(biāo)閾值。核心實(shí)現(xiàn)基于 WebAssembly 思想的高效 JavaScript 減面引擎由于 3D 模型包含數(shù)萬個(gè)頂點(diǎn)和面高頻的對(duì)象創(chuàng)建和垃圾回收會(huì)導(dǎo)致嚴(yán)重的主線程卡頓。在下面的生產(chǎn)級(jí)實(shí)現(xiàn)中我們采用類型化數(shù)組TypedArray連續(xù)內(nèi)存布局配合緊湊的半邊鄰接關(guān)系與斐波那契/二叉最小堆/** * 運(yùn)行時(shí) 3D 網(wǎng)格 QEM 邊折疊動(dòng)態(tài)簡(jiǎn)化引擎 * 適用于 WebGL / WebGPU BufferGeometry 運(yùn)行時(shí)拓?fù)渲貥?gòu) */ class SymmetricMatrix4 { constructor() { // 存儲(chǔ) 4x4 對(duì)稱矩陣的 10 個(gè)獨(dú)立分量 // 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 頂點(diǎn)位置一維數(shù)組 [x, y, z, x, y, z...] * param {Uint32Array} indices 索引數(shù)組 [i0, i1, i2, ...] */ constructor(positions, indices) { this.positions positions; this.indices indices; this.vertexCount positions.length / 3; this.triangleCount indices.length / 3; // 拓?fù)浯鎯?chǔ) 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() { // 實(shí)例化結(jié)構(gòu)化頂點(diǎn) 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 }); } // 實(shí)例化三角形并建立關(guān)聯(lián) 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() { // 計(jì)算每個(gè)三角面的法向量與空間平面方程累加到對(duì)應(yīng)頂點(diǎn) 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); // 候選點(diǎn)v0、v1 以及中心點(diǎn)選擇代價(jià)最小者 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); } } // 拓?fù)浔Ｗo(hù)防止法線翻轉(zhuǎn)導(dǎo)致視覺黑斑 if (this._willFlipNormal(v0, v1, edge.targetX, edge.targetY, edge.targetZ)) { return false; } // 執(zhí)行折疊保留 v0更新其坐標(biāo)為最優(yōu)收縮點(diǎn)標(biāo)記 v1 廢棄 v0.x edge.targetX; v0.y edge.targetY; v0.z edge.targetZ; v0.matrix.add(v1.matrix); v1.deleted true; // 標(biāo)記共享面刪除 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) { // 遍歷折疊影響的所有相鄰三角形校驗(yàn)新法線與原法線點(diǎn)積是否大于 0 for (const fId of v0.faces) { const tri this.triangles[fId]; if (tri.deleted) continue; if (v1.faces.has(fId)) continue; // 共享面會(huì)被直接刪除無需校驗(yàn) 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; // 產(chǎn)生退化三角形予以拒絕 } } 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 異步任務(wù)分發(fā)與顯存無縫熱替換在雙 11 3D 會(huì)場(chǎng)中我們絕對(duì)不能在主線程執(zhí)行長(zhǎng)達(dá) 200ms 的網(wǎng)格拓?fù)溆?jì)算。通過創(chuàng)建專職的 Web Worker利用零拷貝Transferable Objects傳遞ArrayBuffer計(jì)算完成后直接調(diào)用 Three.js 的BufferAttribute.copyArray并標(biāo)記needsUpdate true即可實(shí)現(xiàn)視覺上毫無頓挫的 3D 網(wǎng)格無縫熱替換// 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); // 零拷貝回傳精簡(jiǎn)后的幾何頂點(diǎn)數(shù)據(jù) self.postMessage( { taskId: taskId, positionsBuffer: result.positions.buffer, indicesBuffer: result.indices.buffer, faceCount: result.reducedTriangles }, [result.positions.buffer, result.indices.buffer] ); };主線程加載調(diào)度器則負(fù)責(zé)在用戶漫游靠近商品前利用設(shè)備空閑期啟動(dòng)后臺(tái)簡(jiǎn)化管線兼顧了即時(shí)展示的首幀速度與低端機(jī)極限抗壓穩(wěn)定性。