Spatial queries on the GPU

Closest point, sphere and box tests, and your own shapecast over the scene in WGSL, plus the triangle helpers.

The trace module can also answer questions that aren't rays: which surface point is nearest, does a sphere or box touch anything, and a shapecast whose tests you write. They walk the same scene buffers as the rays (SceneTrees.traceBuffers or uploadTraceScene), in every node and triangle format, instanced or merged, and they are compiled in only when you ask for them, so a module without them is the ray walk alone.

Closest point in a batch

ClosestPointBatchKernel is TraceBatchKernel's counterpart: points in, the nearest point on any triangle of the scene out.

import { CLOSEST_POINT_RECORD_BYTES, ClosestPointBatchKernel, POINT_QUERY_BYTES } from '@pmndrs/bvh';

const kernel = await ClosestPointBatchKernel.create(device, {
    triangleLeaves: trees.triangleLeaves,
    positionLayout: trees.positionLayout,
    nodeFormat: trees.nodeFormat,
});
const count = points.length;
// One query per point: vec4f(point.xyz, maxDistance). Only triangles nearer than maxDistance count.
const data = new Float32Array(count * 4);
points.forEach((point, i) => data.set([...point, 1e30], i * 4));
const queries = device.createBuffer({ size: count * POINT_QUERY_BYTES, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST });
const results = device.createBuffer({ size: count * CLOSEST_POINT_RECORD_BYTES, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC });
device.queue.writeBuffer(queries, 0, data);

const encoder = device.createCommandEncoder();
kernel.encode(encoder, trees.traceBuffers, { queries, results, count, mask: 0xff });
device.queue.submit([encoder.finish()]);
// 48-byte records, words in CLOSEST_POINT_RECORD_WORD: distance (negative: nothing within maxDistance),
// instance, triangle, material, barycentrics, point (world) and normal (the triangle's authored front side).

Queries: 16 bytes each (POINT_QUERY_BYTES): the point in world space, then maxDistance. Larger distances (and infinity) are clamped to CLOSEST_POINT_MAX_DISTANCE (1e18).
Records: 48 bytes (CLOSEST_POINT_RECORD_BYTES), words in CLOSEST_POINT_RECORD_WORD: 0 distance, 1 instance, 2 triangle, 3 material, 4-5 barycentrics, 6-8 point, 9-11 normal. A miss has distance -1 and material NO_MATERIAL.
Masks: one instance mask per batch, as for rays; rayMasks: false compiles masks out.
The kernel refuses a scene whose formats differ from the ones it was made for, and a queries or results buffer too small for count. closestPointKernelWgsl(options) gives its WGSL, for a pipeline of your own.

In your own kernel

traceModuleWgsl({ queries: true }) adds the queries to the module:

    const code = /* wgsl */ `
${traceModuleWgsl({ queries: true })}
fn nearestSurface(p: vec3f) -> vec3f {
    let hit = bvhClosestPoint(p, 10.0);   // world space; hit.distance < 0: nothing within 10
    return select(p, hit.point, hit.distance >= 0.0);
}
fn overlaps(p: vec3f, axes: mat3x3f) -> bool {
    return bvhIntersectsSphere(p, 0.5)
        || bvhIntersectsBox(p - vec3f(1.0), p + vec3f(1.0))
        || bvhIntersectsOrientedBox(p, vec3f(2.0, 0.5, 0.5), axes);   // axes: orthonormal columns
}`;

struct BvhClosestHit { distance: f32, instance: u32, triangle: u32, material: u32,
                       barycentrics: vec2f, point: vec3f, normal: vec3f }

fn bvhClosestPoint(point: vec3f, maxDistance: f32) -> BvhClosestHit
fn bvhIntersectsSphere(center: vec3f, radius: f32) -> bool
fn bvhIntersectsBox(boxMin: vec3f, boxMax: vec3f) -> bool
fn bvhIntersectsOrientedBox(center: vec3f, halfSize: vec3f, rotation: mat3x3f) -> bool
// and bvhClosestPointMasked(point, maxDistance, mask), bvhIntersectsSphereMasked(..., mask), ... unless rayMasks: false

Everything is in world space, through scaled, rotated and mirrored instances: distances are world distances, and a sphere stays a sphere. (A ray can be moved into an instance's space because t survives any affine map; a distance doesn't, so queries move the scene to the query instead.)
bvhClosestPoint counts only triangles strictly nearer than maxDistance. Of triangles at the same distance it returns one; which one is not specified. instance, triangle, material and barycentrics mean what they mean in BvhHit, merged scenes included; normal is the triangle's authored front side in world space.
Touching counts as intersecting in the sphere and box tests. bvhIntersectsOrientedBox takes the box's axes as the columns of rotation; fold a scale into halfSize.
The triangle filter is not asked: every triangle counts. Instances with mask 0 are left out, as for rays; with rayMasks: false masks are compiled out and every instance counts, mask 0 included.
maxDistance of 0 or less finds nothing; infinity is clamped to 1e18 and finds the nearest point.
Degenerate triangles (segments, points) and slivers thinner than about 1:3000 are measured to their three edges: three's region arithmetic cancels in f32 there. A sliver's answer is off by at most its own height.
They are CpuMeshBvh's closestPointToPoint, intersectsSphere and intersectsBox on the GPU, and the query-oracle GPU page checks them against those (below).

Your own shapecast

traceModuleWgsl({ shapecast }) compiles the same walk around three functions you write, and adds bvhShapecast() (bvhShapecastMasked(mask) with ray masks), which returns true when your triangle test stopped it:

    // Count the triangles within a radius of a point: the caller's three hooks, compiled into the walk.
    const shapecast = /* wgsl */ `
var<private> queryCenter: vec3f;
var<private> queryRadiusSq: f32;
var<private> touched: u32;

fn bvhShapecastBounds(bounds: BvhShapecastBounds) -> f32 {
    let distanceSq = bvhPointBoxDistanceSq(queryCenter, bounds.min, bounds.max);
    return select(-1.0, distanceSq, distanceSq <= queryRadiusSq);   // < 0 skips the box; else the lower goes first
}

fn bvhShapecastKeep(score: f32) -> bool {
    return true;   // asked when a pushed box is popped, with its score: false skips it
}

fn bvhShapecastTriangle(triangle: BvhShapecastTriangle) -> bool {
    let offset = bvhClosestPointToTriangle(queryCenter, triangle.a, triangle.b, triangle.c).point - queryCenter;
    if (dot(offset, offset) <= queryRadiusSq) {
        touched += 1u;   // triangle.instance and triangle.triangle name it; its corners are in world space
    }
    return false;   // true stops the cast
}`;
    const code = /* wgsl */ `
${traceModuleWgsl({ shapecast })}
fn countNear(p: vec3f, radius: f32) -> u32 {
    queryCenter = p;
    queryRadiusSq = radius * radius;
    touched = 0u;
    _ = bvhShapecast();
    return touched;
}`;

bvhShapecastBounds(bounds) scores a box (world space): negative skips it; of two children the lower score is entered first and the other pushed with its score. three-mesh-bvh's intersectsBounds and boundsTraverseOrder in one.
bvhShapecastKeep(score) is asked when a pushed box comes off the stack. Return score < best to cull by a distance that has shrunk since the box was pushed, as bvhClosestPoint does; return true otherwise.
bvhShapecastTriangle(triangle) gets each triangle of an entered leaf: corners a, b, c in world space, instance and triangle as in BvhHit, mirrored (the world winding is the reverse of the authored one), and record and slot for bvhShapecastMaterial(triangle) and bvhShapecastNormal(triangle).
Mesh boxes reach your hook as the world box around the instance's moved box, grown by QUERY_BOX_PADDING (1e-6) of the sizes of the terms the f32 transform adds (the moved centre's terms, the translation and the half size), so the corners the walk hands to your triangle hook lie inside, also for an instance far from the origin whose geometry is offset back near it. They are a little larger than the exact world boxes.
WGSL has no closures, so hooks keep their state in var<private> variables. Pass shapecast: '' to declare the hooks in your kernel instead.
bvhShapecastTriangle may call the module's other walks (bvhTraceAny, bvhClosestPoint, bvhIntersects*): the shapecast re-reads its instance's quantized node frame after each leaf, which a nested walk overwrites. bvhShapecastBounds and bvhShapecastKeep must not call a walk (a node is decoded right after them), and neither may the ray walk's triangle filter, bvhTrianglePasses.
The library's queries are shapecasts of their own, so queries and shapecast can be used together.

Triangle helpers

The walk's watertight ray-triangle test and a closest point on one triangle are in every trace module, and alone, with no bindings, in triangleGeometryWgsl():

import { triangleGeometryWgsl } from '@pmndrs/bvh';

    // The walk's watertight test and the closest point on one triangle, with no scene and no bindings.
    const code = /* wgsl */ `
${triangleGeometryWgsl()}
fn pick(ray: BvhRay, a: vec3f, b: vec3f, c: vec3f) -> f32 {
    let hit = bvhIntersectRayTriangle(ray, a, b, c);   // hit.hit, hit.t, hit.barycentrics, hit.frontFacing
    return select(-1.0, hit.t, hit.hit);
}
fn snap(p: vec3f, a: vec3f, b: vec3f, c: vec3f) -> vec3f {
    return bvhClosestPointToTriangle(p, a, b, c).point;   // .barycentrics: the weights of b and c
}`;

bvhIntersectRayTriangle is the walk's own test (bvhMakeRaySetup and bvhIntersectWatertight), not a copy: a ray through an edge two triangles share hits one of them. bvhClosestPointToTriangle is three's Triangle.closestPointToPoint, except that segments, points and slivers are measured to their edges. Use one or the other text in a kernel, never both: the trace module already contains it.

/three

new BvhTraceNodes(renderer, trees, { queries: true }) puts the queries in bvh.module (call them by name from a wgslFn), and bvh.closestPoint(point, maxDistance) returns a BvhClosestPointHit struct node (.get('distance'), 'instance', 'triangle', 'material', 'barycentrics', 'point', 'normal'); closestPointMasked takes a mask. bvh.getShapecastFn({ shape, intersectsBounds, intersectsTriangle, keep }) compiles a shapecast whose hooks are TSL Fns or wgslFns, three-mesh-bvh's getShapecastFn (Shapecasts with TSL hooks).

How they are checked

The query-oracle GPU page runs the queries on the oracle's scenes (thin walls, instancing, mirrored and non-uniformly scaled boxes, random soups under random rotations, scales and mirrors, 200 instances, a 30,000-triangle mesh), plus instances 1000-1500 from the origin with their geometry offset back near it, degenerate triangles, and a mask-0 instance, in f32 and quantized nodes, records and indexed leaves, instanced and merged, with masks on and off and per-triangle materials, and compares with CpuMeshBvh built over each instance in world space. A tie (another triangle at the same distance, within the tolerance) agrees; a shape within the tolerance of touching is not counted. It also checks nesting (a shapecast hook tracing bvhTraceAny per triangle, against the CPU walk) and the box padding (every corner as the walk moves it, queried at radius 0, must be found with culling as without). On the Apple M5 every query agrees. The three-trace page checks that closestPoint gives exactly the batch kernel's records.

Not here

Signed distance fields and the inside test (bvhRayCrossings, bvhInsideVotes, bvhIsInside, also in this module): see Signed distance fields.
Closest point between two meshes (closestPointToGeometry) and bvhcast exist on the CPU only.