需求

要在一個模型上畫出更多細節，就需要細分現有的網格。

直接細分模型所有網格並不實際，代價是三角形數量爆炸，記憶體爆炸還有畫面卡頓。所以需要的是局部網格細分：只在使用者選中的區域增加三角形，其他地方維持原樣。

前情提要

網格細分算法主要參考開源專案Sculptgl 專案鏈接、算法位置

Sculptgl不是用THREEjs實現，THREEjs處理拓撲（hashPoint、hashEdge、建立鄰居關係）的部分，可參考我之前分享的文章 THREEjs BufferGeometry網格擴散。

說明原理

整個流程可以拆成四個步驟：找出選中三角形、標記需要分割的三角形、沿最長邊中點分割、修補T-junction裂縫。

1. 找出使用者選中區域的三角形

根據使用者畫刷的位置和大小，用BVH找出被包含的三角形，作為這次要處理的集合。可參考我之前分享的文章Three-mesh-bvh shapecast函式

2. 標記需要分割的三角形

對於每個使用者選中的三角形，量測它三條邊的長度，若最長邊大於細分精度（edgeMax2），則標記為需要分割，並記錄下是哪一條邊。

這裡所有長度都用平方距離（distanceToSquared）來比較，避免開根號的開銷。回傳值 1 / 2 / 3 代表最長邊是哪一條，0 代表不需要分割。

findSplit = (triangleIndex, checkInsideSphere) => {
    const { v1, v2, v3 } = this.findSplitTempData;
    const { bigIndexAttr, bigPosAttr } = this;

    const index = triangleIndex * 3;
    const a = bigIndexAttr.array[index];
    const b = bigIndexAttr.array[index + 1];
    const c = bigIndexAttr.array[index + 2];
    v1.fromBufferAttribute(bigPosAttr, a);
    v2.fromBufferAttribute(bigPosAttr, b);
    v3.fromBufferAttribute(bigPosAttr, c);

    // 只處理真的落在筆刷球體內的三角形
    if (checkInsideSphere) {
        let triangleInsideSphereArray = false;
        for (const center of this.centerArray) {
            if (triangleInsideSphere(center, this.radius2, v1, v2, v3)) {
                triangleInsideSphereArray = true;
                break;
            }
        }
        if (!triangleInsideSphereArray) return 0;
    }

    // 找出最長邊，若超過細分精度才標記
    const length1 = v1.distanceToSquared(v2);
    const length2 = v2.distanceToSquared(v3);
    const length3 = v1.distanceToSquared(v3);
    if (length1 > length2 && length1 > length3) return length1 > this.edgeMax2 ? 1 : 0;
    else if (length2 > length3) return length2 > this.edgeMax2 ? 2 : 0;
    else return length3 > this.edgeMax2 ? 3 : 0;
}

3. 沿最長邊的中點分割

對於每個被標記的三角形，沿著最長邊的中點分割成兩個三角形，並把這條被分割的邊記錄起來（存進 verticesMap），key 是邊的 hash，value 是新插入的中點索引。

記錄的用意是：相鄰的三角形共用這條邊，後面修補 T-junction 時就能查到「這條邊已經有中點了」，直接重用同一個頂點，而不會在同一條邊上產生兩個不同的點。

中點位置除了取兩端點的平均，還會依兩端法線的夾角往外推一點（curvatureStrength），讓細分後的表面更圓滑而不是維持平面。

halfEdgeSplit = (triIdx, iv1, iv2, iv3) => {
    const { /* temp vectors... */ } = this.halfEdgeSplitTempData;
    const { bigIndexAttr, bigPosAttr, bigNorAttr, bigColAttr, verticesMap, localPointMap } = this;

    v1.fromBufferAttribute(bigPosAttr, iv1);
    v2.fromBufferAttribute(bigPosAttr, iv2);
    v3.fromBufferAttribute(bigPosAttr, iv3);

    const key1 = hashPoint(v1.x, v1.y, v1.z);
    const key2 = hashPoint(v2.x, v2.y, v2.z);
    const key = hashEdge(key1, key2);

    // 同一條邊只建立一次中點，相鄰三角形共用
    let midIndex = verticesMap.get(key);
    if (midIndex === undefined) {
        midIndex = bigPosAttr.usedCount;
        verticesMap.set(key, midIndex);

        // 中點法線、顏色取兩端平均
        n1.fromBufferAttribute(bigNorAttr, iv1);
        n2.fromBufferAttribute(bigNorAttr, iv2);
        nMid.addVectors(n1, n2).normalize();
        bigNorAttr.setXYZ(midIndex, nMid.x, nMid.y, nMid.z);
        bigNorAttr.usedCount++;

        c1.fromBufferAttribute(bigColAttr, iv1);
        c2.fromBufferAttribute(bigColAttr, iv2);
        cMid.addVectors(c1, c2).multiplyScalar(0.5);
        bigColAttr.setXYZ(midIndex, cMid.x, cMid.y, cMid.z);
        bigColAttr.usedCount++;

        // 依兩端法線夾角，把中點往外推一點讓表面更圓滑
        const dot = THREE.MathUtils.clamp(n1.dot(n2), -1, 1);
        const angle = Math.acos(dot);
        vEdge.subVectors(v1, v2);
        let offset = angle * this.curvatureStrength * vEdge.length();
        norPlus.addVectors(n1, n2);
        if (norPlus.length() > 0) offset /= norPlus.length();
        norDiff.subVectors(n1, n2);
        if (vEdge.dot(norDiff) < 0) offset = -offset;

        vMid.addVectors(v1, v2).multiplyScalar(0.5);
        vMid.add(norPlus.multiplyScalar(offset));
        bigPosAttr.setXYZ(midIndex, vMid.x, vMid.y, vMid.z);
        bigPosAttr.usedCount++;
    }

    // 原三角形改成 (iv1, mid, iv3)，再新增一個 (mid, iv2, iv3)
    const triPosIdx = triIdx * 3;
    bigIndexAttr.array[triPosIdx] = iv1;
    bigIndexAttr.array[triPosIdx + 1] = midIndex;
    bigIndexAttr.array[triPosIdx + 2] = iv3;

    const newTriPosIdx = bigIndexAttr.usedCount;
    bigIndexAttr.array[newTriPosIdx] = midIndex;
    bigIndexAttr.array[newTriPosIdx + 1] = iv2;
    bigIndexAttr.array[newTriPosIdx + 2] = iv3;
    bigIndexAttr.usedCount += 3;

    // ... 同步更新 localPointMap / divideMap
}

4. 修補 T-junction

只分割選中的三角形會留下問題：被分割的邊上多了一個中點，但邊另一側的鄰居三角形沒有跟著分割，於是這個中點懸在邊上，形成 T-junction，渲染時會出現裂縫。

修補方式是：擴張到選中三角形外圍的鄰居，對於每個三角形，只要它的某條邊在 verticesMap 裡已經有中點，就沿那個既有中點補上一刀，讓中點被兩側的三角形共用，裂縫就消除了。

一個三角形可能有不止一條邊被標記，所以這裡會反覆處理直到沒有新的待分割三角形為止；當多條邊都被標記時，會優先選擇連接點數較少的邊分割，避免局部過度密集。

fillTriangles = (triArray) => {
    const { bigIndexAttr, bigPosAttr, verticesMap, localPointMap } = this;
    const indexArray = bigIndexAttr.array;

    const newTriArray = [];
    for (let i = 0; i < triArray.length; i++) {
        const triIndex = triArray[i];
        const index = triIndex * 3;
        const iv1 = indexArray[index];
        const iv2 = indexArray[index + 1];
        const iv3 = indexArray[index + 2];

        const key1 = pointIndex2pointHash(bigPosAttr, iv1);
        const key2 = pointIndex2pointHash(bigPosAttr, iv2);
        const key3 = pointIndex2pointHash(bigPosAttr, iv3);

        // 查三條邊有沒有已存在的中點
        const val1 = verticesMap.get(hashEdge(key1, key2));
        const val2 = verticesMap.get(hashEdge(key2, key3));
        const val3 = verticesMap.get(hashEdge(key1, key3));

        // 多條邊被標記時，挑連接三角形較少的邊優先分割
        const num1 = localPointMap.get(key1).length;
        const num2 = localPointMap.get(key2).length;
        const num3 = localPointMap.get(key3).length;

        let split = 0;
        if (val1) {
            if (val2) {
                if (val3) {
                    if (num1 < num2 && num1 < num3) split = 2;
                    else if (num2 < num3) split = 3;
                    else split = 1;
                } else if (num1 < num3) split = 2;
                else split = 1;
            } else if (val3 && num2 < num3) split = 3;
            else split = 1;
        } else if (val2) {
            if (val3 && num2 < num1) split = 3;
            else split = 2;
        } else if (val3) split = 3;

        // 沿著「已存在的中點」補一刀，不再建立新點
        if (split === 1) this.fillTriangle(triIndex, iv1, iv2, iv3, val1);
        else if (split === 2) this.fillTriangle(triIndex, iv2, iv3, iv1, val2);
        else if (split === 3) this.fillTriangle(triIndex, iv3, iv1, iv2, val3);
        else continue;

        newTriArray.push(triIndex, bigIndexAttr.usedCount / 3 - 1);
    }

    return newTriArray;
}

THREEjs 實現上的細節

處理拓撲

BufferGeometry 本身查不到「一個頂點周圍有哪些三角形、一條邊被哪兩個三角形共用」這類拓撲關係，必須自己建立。

作法是用 hashPoint 為每個頂點座標算出唯一 hash，用 hashEdge 為一條邊（兩個頂點 hash）算出唯一 hash，再建一個 Map 記錄每個點連到哪些三角形（buildLocalPointMap）。這部分的觀念和 THREEjs BufferGeometry網格擴散 一樣，差別只在這裡只對局部範圍建表，省時省記憶體。

const buildLocalPointMap = (geometry, triIndexSet) => {
    const indexArray = geometry.index.array;
    const posArray = geometry.getAttribute('position').array;

    const pointMap = new Map();
    for (const triIndex of triIndexSet) {
        const triPointIndex = triIndex * 3;
        for (let offset = 0; offset < 3; offset++) {
            const vecIndex = indexArray[triPointIndex + offset] * 3;
            const key = hashPoint(posArray[vecIndex], posArray[vecIndex + 1], posArray[vecIndex + 2]);

            const pointData = pointMap.get(key);
            if (pointData === undefined) pointMap.set(key, [triIndex]);
            else pointData.push(triIndex);
        }
    }

    return pointMap;
}

動態記憶體

細分過程中會不斷新增三角形與頂點，如果每加一個就重新配置一次 BufferAttribute，搬移成本會非常高。

作法是預先配置一塊比目前需求大上一倍的緩衝區（bigIndexAttr、bigPosAttr 等），並用一個 usedCount 標記目前實際用到哪裡。新增資料時只往後寫並遞增 usedCount；只有當緩衝區不夠、或閒置太多時才重新配置。最後再依 usedCount 把實際用到的部分切出來組成新的 geometry。

reAllocate = (length) => {
    // ...取得原始 index / position / normal / color attribute

    const indexAttr = this.bigIndexAttr ? this.bigIndexAttr : oriIndexAttr;
    const triLen = indexAttr.usedCount + length;
    // 不夠用，或配置過大（超過需求 4 倍）時才重新配置成 2 倍緩衝
    if (!this.bigIndexAttr || this.bigIndexAttr.count < triLen || this.bigIndexAttr.count > triLen * 4) {
        const bigIndexAttr = new THREE.Uint32BufferAttribute(triLen * 2, 1, indexAttr.normalized);
        bigIndexAttr.set(indexAttr.array);
        bigIndexAttr.usedCount = indexAttr.usedCount;
        this.bigIndexAttr = bigIndexAttr;
    }

    // position / normal / color 同樣的方式預配置 2 倍
    // ...
}

快速更新 BVH

筆刷需要連續地刷，每刷一次三角形數量都在變，若每次都重建一棵 BVH 會嚴重拖慢互動。比較好的作法是局部地更新既有的 boundsTree，這部分牽涉的細節較多，會另外寫一篇專門分享。