Function findIntersectingTriangles

js/meshValidation.js:71–192

* Find pairs of intersecting triangles using spatial hashing for the broad * phase and the Separating Axis Theorem for the narrow phase. * Skips triangle pairs that share any vertex (topological neighbors). * * @param {THREE.BufferGeometry} geometry * @param {{ get:() => number }} token - abor

(geometry, token)

 * phase and the Separating Axis Theorem for the narrow phase.
 * Skips triangle pairs that share any vertex (topological neighbors).
 *
 * @param {THREE.BufferGeometry} geometry
 * @param {{ get:() => number }} token  - abort when token.get() !== startValue
 * @returns {Promise<number>} count of intersecting triangle pairs
 */
async function findIntersectingTriangles(geometry, token) {
  const startToken = token.get();
  const pos = geometry.attributes.position.array;
  const triCount = pos.length / 9;

  // Assign a numeric ID to each unique vertex position (quantized).
  // Two triangles that share any vertex are topological neighbors and must be
  // skipped — they touch at that vertex and SAT would flag them otherwise.
  const QUANT = 1e4;
  const posToId = new QuantizedPointMap(QUANT, Math.min(triCount * 3, 1 << 22));
  let nextVId = 0;
  const triVerts = new Uint32Array(triCount * 3);
  for (let t = 0; t < triCount; t++) {
    const b = t * 9;
    for (let v = 0; v < 3; v++) {
      const off = b + v * 3;
      const id = posToId.getOrSet(pos[off], pos[off+1], pos[off+2], nextVId);
      if (posToId.inserted) nextVId++;
      triVerts[t * 3 + v] = id;
    }
  }

  function sharesVertex(a, b) {
    const aBase = a * 3, bBase = b * 3;
    for (let i = 0; i < 3; i++) {
      const vid = triVerts[aBase + i];
      if (vid === triVerts[bBase] || vid === triVerts[bBase + 1] || vid === triVerts[bBase + 2]) return true;
    }
    return false;
  }

  // Build per-triangle AABB
  const minX = new Float32Array(triCount);
  const minY = new Float32Array(triCount);
  const minZ = new Float32Array(triCount);
  const maxX = new Float32Array(triCount);
  const maxY = new Float32Array(triCount);
  const maxZ = new Float32Array(triCount);

  for (let t = 0; t < triCount; t++) {
    const b = t * 9;
    const ax = pos[b], ay = pos[b+1], az = pos[b+2];
    const bx = pos[b+3], by = pos[b+4], bz = pos[b+5];
    const cx = pos[b+6], cy = pos[b+7], cz = pos[b+8];
    minX[t] = Math.min(ax, bx, cx); maxX[t] = Math.max(ax, bx, cx);
    minY[t] = Math.min(ay, by, cy); maxY[t] = Math.max(ay, by, cy);
    minZ[t] = Math.min(az, bz, cz); maxZ[t] = Math.max(az, bz, cz);
  }

  // Determine grid cell size from median AABB extent
  const extents = new Float32Array(triCount);
  for (let t = 0; t < triCount; t++) {
    extents[t] = Math.max(maxX[t] - minX[t], maxY[t] - minY[t], maxZ[t] - minZ[t]);