export declare const HULL_WGSL = "\nconst MAX_CLIP = 64u;\nconst NO_HULL = 0xffffffffu;\n\n/** A convex shape as the hull code sees it: a box (hull = NO_HULL, extents h) or a hull. */\nstruct Poly {\n  c: vec3f,\n  q: vec4f,\n  h: vec3f,\n  hull: u32,\n  vs: u32, nv: u32, fs: u32, nf: u32, es: u32, ne: u32, is: u32,\n}\n\n// Box topology: vertex v has signs (bit 0: x, 1: y, 2: z); faces +x -x +y -y +z -z as vertex\n// loops; edges as vertex a, vertex b, the two faces they separate.\nvar<private> BOX_FACE_VERTS: array<u32, 24> = array<u32, 24>(1u, 3u, 7u, 5u, 0u, 2u, 6u, 4u, 2u, 3u, 7u, 6u, 0u, 1u, 5u, 4u, 4u, 5u, 7u, 6u, 0u, 1u, 3u, 2u);\nvar<private> BOX_EDGES: array<vec4u, 12> = array<vec4u, 12>(\n  vec4u(0u, 1u, 3u, 5u), vec4u(2u, 3u, 2u, 5u), vec4u(4u, 5u, 3u, 4u), vec4u(6u, 7u, 2u, 4u),\n  vec4u(0u, 2u, 1u, 5u), vec4u(1u, 3u, 0u, 5u), vec4u(4u, 6u, 1u, 4u), vec4u(5u, 7u, 0u, 4u),\n  vec4u(0u, 4u, 1u, 3u), vec4u(1u, 5u, 0u, 3u), vec4u(2u, 6u, 1u, 2u), vec4u(3u, 7u, 0u, 2u));\n\nfn isHull(i: u32) -> bool {\n  return bodies[i].angVel.w >= SHAPE_HULL;\n}\n\nfn polyOf(i: u32) -> Poly {\n  var P: Poly;\n  P.c = bodies[i].pos.xyz;\n  P.q = bodies[i].rot;\n  P.h = bodies[i].size.xyz * 0.5;\n  P.hull = NO_HULL;\n  P.nv = 8u; P.nf = 6u; P.ne = 12u;\n  if (isHull(i)) {\n    let h = u32(bodies[i].angVel.w - SHAPE_HULL + 0.5);\n    let h0 = hulls[h];\n    let h1 = hulls[h + 1u];\n    P.hull = h;\n    P.vs = h0.x; P.nv = h0.y; P.fs = h0.z; P.nf = h0.w;\n    P.es = h1.x; P.ne = h1.y; P.is = h1.z;\n  }\n  return P;\n}\n\nfn vertLocal(P: Poly, v: u32) -> vec3f {\n  if (P.hull == NO_HULL) {\n    return vec3f(select(-P.h.x, P.h.x, (v & 1u) != 0u), select(-P.h.y, P.h.y, (v & 2u) != 0u), select(-P.h.z, P.h.z, (v & 4u) != 0u));\n  }\n  return bitcast<vec4f>(hulls[P.vs + v]).xyz;\n}\n\nfn vert(P: Poly, v: u32) -> vec3f {\n  return P.c + qrotate(P.q, vertLocal(P, v));\n}\n\n/** Face f's world plane: outward normal (xyz) and offset (w). */\nfn facePlane(P: Poly, f: u32) -> vec4f {\n  var nl: vec3f;\n  var d: f32;\n  if (P.hull == NO_HULL) {\n    let k = f / 2u;\n    let s = select(1.0, -1.0, (f & 1u) != 0u);\n    nl = vec3f(0.0);\n    nl[k] = s;\n    d = P.h[k];\n  } else {\n    let p = bitcast<vec4f>(hulls[P.fs + 2u * f]);\n    nl = p.xyz;\n    d = p.w;\n  }\n  let n = qrotate(P.q, nl);\n  return vec4f(n, d + dot(n, P.c));\n}\n\nfn faceVertCount(P: Poly, f: u32) -> u32 {\n  if (P.hull == NO_HULL) { return 4u; }\n  return hulls[P.fs + 2u * f + 1u].y;\n}\n\nfn faceVert(P: Poly, f: u32, j: u32) -> u32 {\n  if (P.hull == NO_HULL) { return BOX_FACE_VERTS[f * 4u + j]; }\n  let k = hulls[P.fs + 2u * f + 1u].x + j;\n  return hulls[P.is + k / 4u][k % 4u];\n}\n\nfn edgeOf(P: Poly, e: u32) -> vec4u {\n  if (P.hull == NO_HULL) { return BOX_EDGES[e]; }\n  return hulls[P.es + e];\n}\n\nfn polySupport(P: Poly, dir: vec3f) -> vec3f {\n  let l = qrotate(qconj(P.q), dir);\n  if (P.hull == NO_HULL) { return P.c + qrotate(P.q, select(-P.h, P.h, l >= vec3f(0.0))); }\n  var best = -3.4e38;\n  var at = vec3f(0.0);\n  for (var v = 0u; v < P.nv; v++) {\n    let p = bitcast<vec4f>(hulls[P.vs + v]).xyz;\n    let s = dot(p, l);\n    if (s > best) { best = s; at = p; }\n  }\n  return P.c + qrotate(P.q, at);\n}\n\nstruct FaceQuery { sep: f32, face: u32 }\n\n/** The face of A whose plane B sticks out of least (largest separation). */\nfn queryFaces(A: Poly, B: Poly) -> FaceQuery {\n  var out = FaceQuery(-3.4e38, 0u);\n  for (var f = 0u; f < A.nf; f++) {\n    let p = facePlane(A, f);\n    let s = dot(p.xyz, polySupport(B, -p.xyz)) - p.w;\n    if (s > out.sep) { out = FaceQuery(s, f); }\n  }\n  return out;\n}\n\n/** The edges' Gauss-map arcs (a-b on A's, c-d on B's negated) cross: their cross product is a candidate axis. */\nfn minkowskiFace(a: vec3f, b: vec3f, c: vec3f, d: vec3f) -> bool {\n  let bxa = cross(b, a);\n  let dxc = cross(d, c);\n  let cba = dot(c, bxa);\n  let dba = dot(d, bxa);\n  let adc = dot(a, dxc);\n  let bdc = dot(b, dxc);\n  return cba * dba < 0.0 && adc * bdc < 0.0 && cba * bdc > 0.0;\n}\n\nstruct EdgeQuery { sep: f32, ea: u32, eb: u32, n: vec3f, valid: bool }\n\n/** Face f's outward normal in the shape's own frame. */\nfn faceNormalLocal(P: Poly, f: u32) -> vec3f {\n  if (P.hull == NO_HULL) {\n    var n = vec3f(0.0);\n    n[f / 2u] = select(1.0, -1.0, (f & 1u) != 0u);\n    return n;\n  }\n  return bitcast<vec4f>(hulls[P.fs + 2u * f]).xyz;\n}\n\nfn queryEdges(A: Poly, B: Poly) -> EdgeQuery {\n  var out: EdgeQuery;\n  out.sep = -3.4e38;\n  // The Gauss-map test in B's frame: A's normals turned once per A edge, B's read as stored\n  let toB = qmul(qconj(B.q), A.q);\n  for (var i = 0u; i < A.ne; i++) {\n    let ea = edgeOf(A, i);\n    let a = qrotate(toB, faceNormalLocal(A, ea.z));\n    let b = qrotate(toB, faceNormalLocal(A, ea.w));\n    for (var j = 0u; j < B.ne; j++) {\n      let eb = edgeOf(B, j);\n      if (!minkowskiFace(a, b, -faceNormalLocal(B, eb.z), -faceNormalLocal(B, eb.w))) { continue; }\n      let pa = vert(A, ea.x);\n      let qa = vert(A, ea.y);\n      let pb = vert(B, eb.x);\n      let qb = vert(B, eb.y);\n      var n = cross(qa - pa, qb - pb);\n      let l = length(n);\n      // Parallel edges: their faces' normals already cover the axis\n      if (l < 1e-5 * length(qa - pa) * length(qb - pb)) { continue; }\n      n /= l;\n      if (dot(n, pa - A.c) < 0.0) { n = -n; }\n      let s = dot(n, pb - pa);\n      if (s > out.sep) { out = EdgeQuery(s, i, j, n, true); }\n    }\n  }\n  return out;\n}\n\n/** Clip poly (n points) to dot(pn, x) <= offset. */\nfn clipHull(src: ptr<function, array<vec3f, 64>>, n: u32, dst: ptr<function, array<vec3f, 64>>, pn: vec3f, offset: f32) -> u32 {\n  if (n == 0u) { return 0u; }\n  var count = 0u;\n  var a = (*src)[n - 1u];\n  var da = dot(pn, a) - offset;\n  for (var i = 0u; i < n; i++) {\n    let b = (*src)[i];\n    let db = dot(pn, b) - offset;\n    if ((da <= PLANE_EPSILON) != (db <= PLANE_EPSILON)) {\n      var t = 0.0;\n      if (abs(da - db) > SAT_AXIS_EPSILON) { t = clamp(da / (da - db), 0.0, 1.0); }\n      if (count < MAX_CLIP) { (*dst)[count] = a + (b - a) * t; count++; }\n    }\n    if (db <= PLANE_EPSILON && count < MAX_CLIP) { (*dst)[count] = b; count++; }\n    a = b;\n    da = db;\n  }\n  return count;\n}\n\n/** Face contact: A's (refIsA) or B's face refFace is the reference face; the other shape's is clipped to it. */\nfn hullFaceContact(A: Poly, B: Poly, refIsA: bool, refFace: u32) -> Found {\n  var found: Found;\n  var R = B;\n  var I = A;\n  if (refIsA) { R = A; I = B; }\n  let plane = facePlane(R, refFace);\n  let rn = plane.xyz;\n  // Incident face: the other shape's most anti-parallel among those with its deepest vertex. The\n  // most anti-parallel of all may not touch that vertex on an irregular hull (it does on a box), and\n  // clipping it would then leave the deepest corner without a contact.\n  var deepest = 0u;\n  var low = 3.4e38;\n  for (var v = 0u; v < I.nv; v++) {\n    let d = dot(vert(I, v), rn);\n    if (d < low) { low = d; deepest = v; }\n  }\n  var inc = 0u;\n  var least = 3.4e38;\n  for (var f = 0u; f < I.nf; f++) {\n    var touches = false;\n    for (var j = 0u; j < faceVertCount(I, f); j++) { if (faceVert(I, f, j) == deepest) { touches = true; break; } }\n    if (!touches) { continue; }\n    let d = dot(facePlane(I, f).xyz, rn);\n    if (d < least) { least = d; inc = f; }\n  }\n  var poly: array<vec3f, 64>;\n  var tmp: array<vec3f, 64>;\n  var n = min(faceVertCount(I, inc), MAX_CLIP);\n  for (var j = 0u; j < n; j++) { poly[j] = vert(I, faceVert(I, inc, j)); }\n  // Side planes of the reference face, outward from its centre\n  let k = faceVertCount(R, refFace);\n  var centre = vec3f(0.0);\n  for (var j = 0u; j < k; j++) { centre += vert(R, faceVert(R, refFace, j)); }\n  centre /= f32(k);\n  for (var j = 0u; j < k && n > 0u; j++) {\n    let v0 = vert(R, faceVert(R, refFace, j));\n    let v1 = vert(R, faceVert(R, refFace, (j + 1u) % k));\n    var s = cross(v1 - v0, rn);\n    let l = length(s);\n    if (l < SAT_AXIS_EPSILON) { continue; }\n    s /= l;\n    if (dot(s, centre - v0) > 0.0) { s = -s; }\n    n = clipHull(&poly, n, &tmp, s, dot(s, v0));\n    for (var m = 0u; m < n; m++) { poly[m] = tmp[m]; }\n  }\n  // Points on or below the reference plane; at most MAX_CONTACTS, the deepest first then the\n  // farthest from those chosen (the patch's extent is what keeps a resting shape upright)\n  // (feature keys use the point's index in the clipped polygon, as faceManifold does: stable from\n  // step to step, so warm starts and static-friction anchors stay with their point)\n  var depth: array<f32, 64>;\n  var index: array<u32, 64>;\n  var keep = 0u;\n  for (var m = 0u; m < n; m++) {\n    let dist = dot(rn, poly[m]) - plane.w;\n    if (dist <= PLANE_EPSILON) { tmp[keep] = poly[m]; depth[keep] = dist; index[keep] = m; keep++; }\n  }\n  let prefix = (select(AXIS_FACE_B, AXIS_FACE_A, refIsA) << 24u) | (min(refFace, 255u) << 16u) | (min(inc, 255u) << 8u);\n  var chosen: array<bool, 64>;\n  for (var c = 0u; c < min(keep, MAX_CONTACTS); c++) {\n    var pick = 0u;\n    var bestScore = -3.4e38;\n    for (var m = 0u; m < keep; m++) {\n      if (chosen[m]) { continue; }\n      var score = -depth[m];\n      if (c > 0u) {\n        score = 3.4e38;\n        for (var o = 0u; o < keep; o++) { if (chosen[o]) { score = min(score, dot(tmp[m] - tmp[o], tmp[m] - tmp[o])); } }\n      }\n      if (score > bestScore) { bestScore = score; pick = m; }\n    }\n    chosen[pick] = true;\n    let p = tmp[pick];\n    let onRef = p - rn * depth[pick];\n    addFound(&found, select(p, onRef, refIsA), select(onRef, p, refIsA), prefix | min(index[pick], 255u));\n  }\n  if (found.count == 0u) {\n    let nAB = select(-rn, rn, refIsA);\n    addFound(&found, polySupport(A, nAB), polySupport(B, -nAB), prefix);\n  }\n  return found;\n}\n\nfn hullEdgeContact(A: Poly, B: Poly, q: EdgeQuery) -> Found {\n  var found: Found;\n  let ea = edgeOf(A, q.ea);\n  let eb = edgeOf(B, q.eb);\n  let p0 = vert(A, ea.x);\n  let q0 = vert(B, eb.x);\n  let d1 = vert(A, ea.y) - p0;\n  let d2 = vert(B, eb.y) - q0;\n  let r = p0 - q0;\n  let a = dot(d1, d1);\n  let e = dot(d2, d2);\n  let f = dot(d2, r);\n  let c = dot(d1, r);\n  let b = dot(d1, d2);\n  let denom = a * e - b * b;\n  var s = 0.0;\n  if (abs(denom) > SAT_AXIS_EPSILON * a * e) { s = clamp((b * f - c * e) / denom, 0.0, 1.0); }\n  var t = (b * s + f) / max(e, SAT_AXIS_EPSILON);\n  if (t < 0.0) { t = 0.0; s = clamp(-c / max(a, SAT_AXIS_EPSILON), 0.0, 1.0); }\n  else if (t > 1.0) { t = 1.0; s = clamp((b - c) / max(a, SAT_AXIS_EPSILON), 0.0, 1.0); }\n  addFound(&found, p0 + d1 * s, q0 + d2 * t, (AXIS_EDGE << 24u) | (min(q.ea, 255u) << 8u) | min(q.eb, 255u));\n  return found;\n}\n\n/** Collide two convex shapes (at least one a hull); sat.n from A towards B. */\nfn collidePoly(A: Poly, B: Poly, sat: ptr<function, Sat>) -> Found {\n  var none: Found;\n  let fa = queryFaces(A, B);\n  if (fa.sep > 0.0) { return none; }\n  let fb = queryFaces(B, A);\n  if (fb.sep > 0.0) { return none; }\n  let eq = queryEdges(A, B);\n  if (eq.valid && eq.sep > 0.0) { return none; }\n  // Faces are preferred (stabler manifolds) unless an edge axis is clearly better, as in collide\n  let faceSep = max(fa.sep, fb.sep);\n  var edgeWins = eq.valid && eq.sep > 0.95 * faceSep + 0.01;\n  if ((params.flags & FLAG_FACE_BIAS) == 0u) { edgeWins = eq.valid && 0.95 * eq.sep > faceSep + 0.01; }\n  if (edgeWins) {\n    *sat = Sat(AXIS_EDGE, eq.ea, eq.eb, eq.sep, eq.n, true);\n    return hullEdgeContact(A, B, eq);\n  }\n  // A's face unless B's separates more, as collide does\n  if (fb.sep > fa.sep) {\n    *sat = Sat(AXIS_FACE_B, 0u, fb.face, fb.sep, -facePlane(B, fb.face).xyz, true);\n    return hullFaceContact(A, B, false, fb.face);\n  }\n  *sat = Sat(AXIS_FACE_A, fa.face, 0u, fa.sep, facePlane(A, fa.face).xyz, true);\n  return hullFaceContact(A, B, true, fa.face);\n}\n\n/** Closest point of segment ab to p. */\nfn segmentPoint(a: vec3f, b: vec3f, p: vec3f) -> vec3f {\n  let d = b - a;\n  return a + d * clamp(dot(p - a, d) / max(dot(d, d), 1e-20), 0.0, 1.0);\n}\n\n/** Sphere S (centre c, radius r) against hull X: as sphereBox (n from the sphere towards X). */\nfn sphereHull(c: vec3f, r: f32, X: Poly) -> SphereBoxHit {\n  var out: SphereBoxHit;\n  var deepest = -3.4e38;\n  var deepFace = 0u;\n  for (var f = 0u; f < X.nf; f++) {\n    let s = dot(facePlane(X, f).xyz, c) - facePlane(X, f).w;\n    if (s > deepest) { deepest = s; deepFace = f; }\n  }\n  if (deepest > r) { return out; }\n  if (deepest <= 0.0) {\n    // Centre inside: out through the face it is least deep behind\n    let n = facePlane(X, deepFace).xyz;\n    out.hit = true;\n    out.n = -n;\n    out.onBox = c - n * deepest;\n    out.onSphere = c - n * r;\n    return out;\n  }\n  // Outside: the closest point is on a face the centre is in front of\n  var best = vec3f(0.0);\n  var bestDist = 3.4e38;\n  for (var f = 0u; f < X.nf; f++) {\n    let plane = facePlane(X, f);\n    let s = dot(plane.xyz, c) - plane.w;\n    if (s <= 0.0) { continue; }\n    var p = c - plane.xyz * s;\n    let k = faceVertCount(X, f);\n    var centre = vec3f(0.0);\n    for (var j = 0u; j < k; j++) { centre += vert(X, faceVert(X, f, j)); }\n    centre /= f32(k);\n    var inside = true;\n    var edgeBest = vec3f(0.0);\n    var edgeDist = 3.4e38;\n    for (var j = 0u; j < k; j++) {\n      let v0 = vert(X, faceVert(X, f, j));\n      let v1 = vert(X, faceVert(X, f, (j + 1u) % k));\n      var side = cross(v1 - v0, plane.xyz);\n      if (dot(side, centre - v0) > 0.0) { side = -side; }\n      if (dot(side, p - v0) > 0.0) { inside = false; }\n      let q = segmentPoint(v0, v1, c);\n      let dq = dot(q - c, q - c);\n      if (dq < edgeDist) { edgeDist = dq; edgeBest = q; }\n    }\n    if (!inside) { p = edgeBest; }\n    let dist = length(p - c);\n    if (dist < bestDist) { bestDist = dist; best = p; }\n  }\n  if (bestDist > r) { return out; }\n  var n = vec3f(0.0, 0.0, 1.0);\n  if (bestDist > 0.0) { n = (c - best) / bestDist; }  // from the hull towards the sphere\n  out.hit = true;\n  out.n = -n;\n  out.onBox = best;\n  out.onSphere = c - n * r;\n  return out;\n}\n";
//# sourceMappingURL=wgsl-hull.d.ts.map