demo範例
https://stackblitz.com/edit/vitejs-vite-xafdoe?file=src%2Futils%2Ftool%2FBufferGeometryTool.js
頂點擴散原理
本質是通過模型上的一個頂點，找到周圍相鄰的點；其他點又能找到周圍相鄰的點，就像水波一樣擴散出去。
通常會框定一個封閉邊界來找出邊界內所有點；或者只擴散一點點來加大選定的範圍。 許多3D的算法，如裁切、干涉深度偵測等都會用到。
實現網格擴散
建構頂點與鄰居點的資料
由於BufferGeometry無法直接獲得頂點周圍的點，所以需要先建構頂點與鄰居點的資料。
const floatView = new Float32Array(3);
const intView = new Uint32Array(floatView.buffer);
/**
* 為每個不同頂點，計算唯一的hash key
* 該函式尚有碰撞概率
*/
const hashPoint = (x, y, z) => {
let hash = 2166136261;
floatView[0] = x === 0 ? 0 : x;
floatView[1] = y === 0 ? 0 : y;
floatView[2] = z === 0 ? 0 : z;
hash = Math.imul(hash ^ intView[0], 16777619);
hash = Math.imul(hash ^ intView[1], 16777619);
hash = Math.imul(hash ^ intView[2], 16777619);
return hash >>> 0;
}
/**
* @typedef PointData
* @property {number[]} PointData.triIndices
* @property {number} PointData.firstPosIndex
* @property {Set<number>} [PointData.posIndices]
* @property {Set<number>} [PointData.neighborhashPos]
*
* @typedef {Map<number, PointData>} HashPointMap
*/
/**
* @param {BufferGeometry} geometry
* @param {Object} options
* @param {boolean} options.needPosIndices
* @param {boolean} options.needNeighborPosIndices
* @returns {HashPointMap}
*/
const buildHashPointMap = (geometry, options = {}) => {
const {
needPosIndices,
needNeighborPosIndices,
} = Object.assign({
needPosIndices: false,
needNeighborPosIndices: false,
}, options);
let index = geometry.getIndex();
if (!index) {
geometry.computeBoundsTree();
index = geometry.getIndex();
}
const indexArray = index.array;
const posArray = geometry.getAttribute('position').array;
const triHashPointArray = new Uint32Array(3);
/**兩個一組，分別代表3個索引的鄰居索引，0的鄰居是1和2，1的是0和2 */
const neighborOffset = [1, 2, 0, 2, 0, 1];
/**@type {HashPointMap} */
const pointMap = new Map();
const triCount = indexArray.length / 3;
for (let triIndex = 0; triIndex < triCount; triIndex++) {
const triFlatIndex = triIndex * 3;
const aPosFlatIndex = indexArray[triFlatIndex] * 3;
const bPosFlatIndex = indexArray[triFlatIndex + 1] * 3;
const cPosFlatIndex = indexArray[triFlatIndex + 2] * 3;
triHashPointArray[0] = hashPoint(posArray[aPosFlatIndex], posArray[aPosFlatIndex + 1], posArray[aPosFlatIndex + 2]);
triHashPointArray[1] = hashPoint(posArray[bPosFlatIndex], posArray[bPosFlatIndex + 1], posArray[bPosFlatIndex + 2]);
triHashPointArray[2] = hashPoint(posArray[cPosFlatIndex], posArray[cPosFlatIndex + 1], posArray[cPosFlatIndex + 2]);
for (let offset = 0; offset < 3; offset++) {
const posIndex = indexArray[triFlatIndex + offset];
const key = triHashPointArray[offset];
const flatOffset = offset * 2;
const pointData = pointMap.get(key);
if (!pointData) {
const pointData = {};
pointData.firstPosIndex = posIndex;
pointData.triIndices = [triIndex];
if (needPosIndices) pointData.posIndices = new Set().add(posIndex);
if (needNeighborPosIndices) {
const neighborhashPos = new Set(triHashPointArray);
neighborhashPos.add(triHashPointArray[neighborOffset[flatOffset]]);
neighborhashPos.add(triHashPointArray[neighborOffset[flatOffset + 1]]);
pointData.neighborhashPos = neighborhashPos
}
pointMap.set(key, pointData);
continue;
}
pointData.triIndices.push(triIndex);
if (needPosIndices) pointData.posIndices.add(posIndex);
if (needNeighborPosIndices) {
const flatOffset = offset * 2;
pointData.neighborhashPos.add(triHashPointArray[neighborOffset[flatOffset]]);
pointData.neighborhashPos.add(triHashPointArray[neighborOffset[flatOffset + 1]]);
}
}
}
return pointMap;
}
擴散指定層數的頂點
/**
* @param {HashPointMap} hashPointMap 拓撲資訊
* @param {Set<number>} hashPointKeySet 所有種子點
* @param {number} nRing 擴散次數
*/
const hashPosKey2Neihbors = (hashPointMap, hashPointKeySet, nRing) => {
/**發現的所有點 */
const checkedKeySet = new Set();
/**當前層的種子點 */
let currentLayer = new Set(hashPointKeySet);
/**下一層的邊緣點 */
let nextLayer = new Set();
for (let i = 0; i < nRing; i++) {
for (const pointKey of currentLayer) {
checkedKeySet.add(pointKey);
const pointData = hashPointMap.get(pointKey);
if (!pointData) continue;
const { neighborhashPos } = pointData;
for (const neighborKey of neighborhashPos) {
if (checkedKeySet.has(neighborKey)) continue;
nextLayer.add(neighborKey);
}
}
if (nextLayer.size === 0) break;
const temp = currentLayer;
currentLayer = nextLayer;
nextLayer = temp;
nextLayer.clear();
}
return checkedKeySet;
}
條件擴散頂點
/**
* @param {HashPointMap} hashPointMap
* @param {Set<string>} seedPointKeySet 所有種子點
* @param {(seedPointKey: number, neighborPointKey: number)=>{}} ifSpreadJudgeFunc 擴散判斷函式，為true則繼續擴散
* @return {Set<number>} 所有擴散到的點
*/
const hashPointSpread = (hashPointMap, seedPointKeySet, ifSpreadJudgeFunc = () => true) => {
const checkedKeySet = new Set();
const seedData = {
/**當前層的種子點 */
currentLayer: new Set(seedPointKeySet),
/**下一層的邊緣點 */
nextLayer: new Set(),
};
while (seedData.currentLayer.size > 0) {
seedData.nextLayer.clear();
for (const pointKey of seedData.currentLayer) {
checkedKeySet.add(pointKey);
const neighborKeySet = hashPointMap.get(pointKey).neighborhashPos;
for (const neighborKey of neighborKeySet) {
if (checkedKeySet.has(neighborKey)) continue;
if (!ifSpreadJudgeFunc(pointKey, neighborKey)) continue;
seedData.nextLayer.add(neighborKey);
}
}
const temp = seedData.currentLayer;
seedData.currentLayer = seedData.nextLayer;
seedData.nextLayer = temp;
}
return checkedKeySet;
}
參考資料
https://stackoverflow.com/questions/59561323/threejs-find-neighbor-faces-in-planebuffergeometry