/**
 * Compute shader for BIM ↔ scan deviation.
 *
 * For each scan point, walk a per-triangle BVH and compute the signed
 * distance to the nearest mesh surface. Sign is positive on the side
 * the triangle's outward normal points to.
 *
 * Bind group layout:
 *   @binding(0) bvhNodes: array<vec4<f32>, 2>   — 32-byte nodes (read)
 *                                                 packed: [aabbMin, leafOrLeft]
 *                                                         [aabbMax, leafOrRight]
 *   @binding(1) triangles: array<f32>           — 12 floats per triangle
 *   @binding(2) positions: array<f32>           — 6 floats per point
 *                                                 (matches POINT_VERTEX_BYTES
 *                                                  layout: vec3 + colorPacked)
 *   @binding(3) deviations: array<f32>          — output, one float per point
 *   @binding(4) params: DeviationParams
 *
 * Workgroup size 64 (one wavefront / warp on most desktop GPUs).
 * Each invocation processes one point.
 */
export declare const deviationShaderSource = "\nstruct BvhNode {\n  aabbMinX: f32, aabbMinY: f32, aabbMinZ: f32,\n  // High bit: leaf flag. Low 31 bits: leaf=triStart, internal=leftChildIdx.\n  leafOrLeft: u32,\n  aabbMaxX: f32, aabbMaxY: f32, aabbMaxZ: f32,\n  // Leaf=triCount, internal=rightChildIdx.\n  countOrRight: u32,\n}\n\nstruct DeviationParams {\n  pointCount: u32,\n  pointStrideF32: u32,    // floats between successive points in positions buffer\n  positionOffsetF32: u32, // float offset of vec3 position within a point\n  // Optional clip range \u2014 when nonzero, signs above + below are kept\n  // but values past \u00B1maxRange are clamped (saves shader work for\n  // points far outside the model).\n  maxRange: f32,\n  // Reserved padding to keep the struct 16-byte aligned for std140.\n  _pad0: u32, _pad1: u32, _pad2: u32, _pad3: u32,\n}\n\n@group(0) @binding(0) var<storage, read> bvhNodes: array<BvhNode>;\n@group(0) @binding(1) var<storage, read> triangles: array<f32>;\n@group(0) @binding(2) var<storage, read> positions: array<f32>;\n@group(0) @binding(3) var<storage, read_write> deviations: array<f32>;\n@group(0) @binding(4) var<uniform> params: DeviationParams;\n\nconst LEAF_FLAG: u32 = 0x80000000u;\nconst STACK_SIZE: u32 = 64u;\n\n// Squared distance from point p to AABB [aabbMin, aabbMax].\n// Returns 0 if p is inside the box.\nfn distSqPointAabb(\n  px: f32, py: f32, pz: f32,\n  ax: f32, ay: f32, az: f32,\n  bx: f32, by: f32, bz: f32,\n) -> f32 {\n  let dx = max(max(ax - px, 0.0), px - bx);\n  let dy = max(max(ay - py, 0.0), py - by);\n  let dz = max(max(az - pz, 0.0), pz - bz);\n  return dx * dx + dy * dy + dz * dz;\n}\n\nstruct ClosestResult {\n  point: vec3<f32>,\n  distSq: f32,\n}\n\n// Ericson, Real-Time Collision Detection \u00A75.1.5: closest point on\n// a triangle to an arbitrary point in space. Branches over the\n// Voronoi regions of the triangle (3 verts, 3 edges, interior).\nfn closestPointOnTriangle(p: vec3<f32>, a: vec3<f32>, b: vec3<f32>, c: vec3<f32>) -> ClosestResult {\n  let ab = b - a;\n  let ac = c - a;\n  let ap = p - a;\n  let d1 = dot(ab, ap);\n  let d2 = dot(ac, ap);\n  if (d1 <= 0.0 && d2 <= 0.0) {\n    let diff = p - a;\n    return ClosestResult(a, dot(diff, diff));\n  }\n  let bp = p - b;\n  let d3 = dot(ab, bp);\n  let d4 = dot(ac, bp);\n  if (d3 >= 0.0 && d4 <= d3) {\n    let diff = p - b;\n    return ClosestResult(b, dot(diff, diff));\n  }\n  let vc = d1 * d4 - d3 * d2;\n  if (vc <= 0.0 && d1 >= 0.0 && d3 <= 0.0) {\n    let v = d1 / (d1 - d3);\n    let q = a + v * ab;\n    let diff = p - q;\n    return ClosestResult(q, dot(diff, diff));\n  }\n  let cp = p - c;\n  let d5 = dot(ab, cp);\n  let d6 = dot(ac, cp);\n  if (d6 >= 0.0 && d5 <= d6) {\n    let diff = p - c;\n    return ClosestResult(c, dot(diff, diff));\n  }\n  let vb = d5 * d2 - d1 * d6;\n  if (vb <= 0.0 && d2 >= 0.0 && d6 <= 0.0) {\n    let w = d2 / (d2 - d6);\n    let q = a + w * ac;\n    let diff = p - q;\n    return ClosestResult(q, dot(diff, diff));\n  }\n  let va = d3 * d6 - d5 * d4;\n  if (va <= 0.0 && (d4 - d3) >= 0.0 && (d5 - d6) >= 0.0) {\n    let w = (d4 - d3) / ((d4 - d3) + (d5 - d6));\n    let q = b + w * (c - b);\n    let diff = p - q;\n    return ClosestResult(q, dot(diff, diff));\n  }\n  // Inside the face: barycentric (v, w).\n  let denom = 1.0 / (va + vb + vc);\n  let v = vb * denom;\n  let w = vc * denom;\n  let q = a + ab * v + ac * w;\n  let diff = p - q;\n  return ClosestResult(q, dot(diff, diff));\n}\n\n@compute @workgroup_size(64)\nfn cs_main(@builtin(global_invocation_id) gid: vec3<u32>) {\n  let pi = gid.x;\n  if (pi >= params.pointCount) {\n    return;\n  }\n  let posOff = pi * params.pointStrideF32 + params.positionOffsetF32;\n  let p = vec3<f32>(positions[posOff], positions[posOff + 1u], positions[posOff + 2u]);\n\n  // Best squared distance across all triangles. Stored squared so\n  // we can prune AABBs without taking sqrt every step.\n  var bestDistSq: f32 = 1.0e30;\n  var bestPoint: vec3<f32> = vec3<f32>(0.0);\n  var bestNormal: vec3<f32> = vec3<f32>(0.0, 1.0, 0.0);\n\n  // Stack-based BVH descent. Workgroup-uniform stack would let\n  // siblings cooperate; for v1 a per-thread stack in private memory\n  // is simpler and fast enough.\n  var stack: array<u32, STACK_SIZE>;\n  var sp: u32 = 0u;\n  stack[sp] = 0u;\n  sp = sp + 1u;\n\n  loop {\n    if (sp == 0u) { break; }\n    sp = sp - 1u;\n    let nodeIdx = stack[sp];\n    let node = bvhNodes[nodeIdx];\n\n    let aabbDistSq = distSqPointAabb(\n      p.x, p.y, p.z,\n      node.aabbMinX, node.aabbMinY, node.aabbMinZ,\n      node.aabbMaxX, node.aabbMaxY, node.aabbMaxZ,\n    );\n    if (aabbDistSq >= bestDistSq) {\n      continue;\n    }\n\n    let leafFlag = node.leafOrLeft & LEAF_FLAG;\n    if (leafFlag != 0u) {\n      let triStart = node.leafOrLeft & (~LEAF_FLAG);\n      let triCount = node.countOrRight;\n      var i: u32 = 0u;\n      loop {\n        if (i >= triCount) { break; }\n        let triOff = (triStart + i) * 12u;\n        let v0 = vec3<f32>(triangles[triOff],      triangles[triOff + 1u],  triangles[triOff + 2u]);\n        let v1 = vec3<f32>(triangles[triOff + 3u], triangles[triOff + 4u],  triangles[triOff + 5u]);\n        let v2 = vec3<f32>(triangles[triOff + 6u], triangles[triOff + 7u],  triangles[triOff + 8u]);\n        let n  = vec3<f32>(triangles[triOff + 9u], triangles[triOff + 10u], triangles[triOff + 11u]);\n        let res = closestPointOnTriangle(p, v0, v1, v2);\n        if (res.distSq < bestDistSq) {\n          bestDistSq = res.distSq;\n          bestPoint = res.point;\n          bestNormal = n;\n        }\n        i = i + 1u;\n      }\n    } else {\n      // Internal node: push both children. Sibling that's closer to\n      // p first (top of stack) so we hit the tighter bound earlier.\n      let leftIdx = node.leafOrLeft;\n      let rightIdx = node.countOrRight;\n      let lNode = bvhNodes[leftIdx];\n      let rNode = bvhNodes[rightIdx];\n      let lDist = distSqPointAabb(\n        p.x, p.y, p.z,\n        lNode.aabbMinX, lNode.aabbMinY, lNode.aabbMinZ,\n        lNode.aabbMaxX, lNode.aabbMaxY, lNode.aabbMaxZ,\n      );\n      let rDist = distSqPointAabb(\n        p.x, p.y, p.z,\n        rNode.aabbMinX, rNode.aabbMinY, rNode.aabbMinZ,\n        rNode.aabbMaxX, rNode.aabbMaxY, rNode.aabbMaxZ,\n      );\n      // Push the farther child first \u2192 closer popped first.\n      if (sp + 2u <= STACK_SIZE) {\n        if (lDist < rDist) {\n          stack[sp] = rightIdx; sp = sp + 1u;\n          stack[sp] = leftIdx;  sp = sp + 1u;\n        } else {\n          stack[sp] = leftIdx;  sp = sp + 1u;\n          stack[sp] = rightIdx; sp = sp + 1u;\n        }\n      }\n    }\n  }\n\n  // Signed distance: project (p - closestPoint) onto the closest\n  // triangle's normal. Positive means p is on the outward side.\n  //\n  // sign() returns 0 when (p - closestPoint) is perpendicular to the\n  // normal -- i.e. the point is COPLANAR with the triangle but its closest\n  // feature is an edge/vertex (a point beside a wall, an open door swung\n  // into a wall's plane, a floor point laterally past the nearest floor\n  // tri). That multiplied a genuinely large dist by 0 and painted far\n  // points at the ramp centre (white). Treat the in-plane case as the\n  // outward side so the magnitude still flags them.\n  let toPoint = p - bestPoint;\n  let dist = sqrt(bestDistSq);\n  let nd = dot(toPoint, bestNormal);\n  let s = select(-1.0, 1.0, nd >= 0.0);\n  var signed: f32 = s * dist;\n\n  // Optional clip: keeps the histogram + ramp focused on near-surface\n  // points. Past \u00B1maxRange the value pegs at the edge.\n  if (params.maxRange > 0.0) {\n    let mr = params.maxRange;\n    if (signed > mr) { signed = mr; }\n    if (signed < -mr) { signed = -mr; }\n  }\n\n  deviations[pi] = signed;\n}\n";
//# sourceMappingURL=deviation-shader.wgsl.d.ts.map