Skip to content

A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.

9.1 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file    bvh.ts
 * @brief   What a ray hits, and how far away — the question a bake asks millions
 *          of times and nothing else here answers.
 *
 * Flat typed arrays throughout, and a traversal that allocates nothing: a bake
 * of one room is tens of millions of these, and an object per ray is the whole
 * cost of the pass.
 */

/** Triangles as `9 * count` floats: three world-space corners each. */
export interface TriangleSoup {
    positions: Float32Array;
    count: number;
}

const LEAF_TRIS = 4;
/** The count an inner node carries: a leaf's is never negative, an empty one included. */
const INNER = -1;

export class Bvh {
    /** Six floats per node: min xyz, max xyz. */
    private readonly bounds: Float32Array;
    /** Two ints per node: a leaf's first triangle or an inner node's LEFT child
     *  (the right is the one after it), then the triangle count — {@link INNER}
     *  for an inner node. */
    private readonly node: Int32Array;
    /** Triangle indices, reordered so a leaf's are contiguous. */
    private readonly order: Int32Array;
    private readonly tris: TriangleSoup;
    private used = 0;
    private depth = 0;
    /** Sized to the tree: a walk leaves one waiting sibling per level, and a
     *  fixed stack drops the deepest ones without a word. */
    private readonly stack: Int32Array;

    constructor(tris: TriangleSoup) {
        this.tris = tris;
        this.order = new Int32Array(tris.count);
        for (let i = 0; i < tris.count; i++) this.order[i] = i;
        const maxNodes = Math.max(1, tris.count * 2);
        this.bounds = new Float32Array(maxNodes * 6);
        this.node = new Int32Array(maxNodes * 2);
        this.used = 1;
        this.build(0, 0, tris.count, 0);
        this.stack = new Int32Array(this.depth + 2);
    }

    private centroid(tri: number, axis: number): number {
        const at = this.order[tri] * 9;
        return (this.tris.positions[at + axis] + this.tris.positions[at + 3 + axis]
              + this.tris.positions[at + 6 + axis]) / 3;
    }

    private bound(node: number, from: number, to: number): void {
        const b = node * 6;
        for (let k = 0; k < 3; k++) { this.bounds[b + k] = Infinity; this.bounds[b + 3 + k] = -Infinity; }
        for (let t = from; t < to; t++) {
            const at = this.order[t] * 9;
            for (let c = 0; c < 3; c++) {
                for (let k = 0; k < 3; k++) {
                    const v = this.tris.positions[at + c * 3 + k];
                    if (v < this.bounds[b + k]) this.bounds[b + k] = v;
                    if (v > this.bounds[b + 3 + k]) this.bounds[b + 3 + k] = v;
                }
            }
        }
    }

    /** Split on the widest axis at the centroid midpoint — cheap, and a bake
     *  builds this once per scene while it traverses it for hours. */
    private build(node: number, from: number, to: number, depth: number): void {
        if (depth > this.depth) this.depth = depth;
        this.bound(node, from, to);
        const n = to - from;
        if (n <= LEAF_TRIS) {
            this.node[node * 2] = from;
            this.node[node * 2 + 1] = n;
            return;
        }
        const b = node * 6;
        let axis = 0;
        let widest = -1;
        for (let k = 0; k < 3; k++) {
            const w = this.bounds[b + 3 + k] - this.bounds[b + k];
            if (w > widest) { widest = w; axis = k; }
        }
        const mid = (this.bounds[b + axis] + this.bounds[b + 3 + axis]) / 2;
        let i = from, j = to - 1;
        while (i <= j) {
            if (this.centroid(i, axis) < mid) i++;
            else { const tmp = this.order[i]; this.order[i] = this.order[j]; this.order[j] = tmp; j--; }
        }
        // Every centroid on one side of the midpoint: split down the middle
        // instead, or the recursion never shrinks.
        let split = i;
        if (split === from || split === to) split = (from + to) >> 1;

        // The two children are allocated together, so ONE index names both: the
        // left, and the right beside it. `node + 1` is the left only for the root —
        // building a left subtree allocates everything under it first.
        const left = this.used++;
        const right = this.used++;
        this.node[node * 2] = left;
        this.node[node * 2 + 1] = INNER;
        this.build(left, from, split, depth + 1);
        this.build(right, split, to, depth + 1);
    }

    /**
     * Whether anything blocks the segment from `origin` to `origin + dir * far`.
     *
     * A shadow ray wants the first blocker, not the nearest one, so this stops at
     * the first hit — which is most of what a bake asks and the cheapest to answer.
     */
    occluded(ox: number, oy: number, oz: number,
             dx: number, dy: number, dz: number, far: number, epsilon: number): boolean {
        return this.trace(ox, oy, oz, dx, dy, dz, far, epsilon, true) >= 0;
    }

    /** The nearest triangle along the ray, or -1. `hitDistance` holds how far. */
    hit(ox: number, oy: number, oz: number,
        dx: number, dy: number, dz: number, far: number, epsilon: number): number {
        return this.trace(ox, oy, oz, dx, dy, dz, far, epsilon, false);
    }

    /** Distance to the last {@link hit}; meaningless before one. */
    hitDistance = 0;
    /** Barycentric coordinates of the last {@link hit}, as `u` and `v` on corners
     *  two and three — corner one takes `1 - u - v`. */
    hitU = 0;
    hitV = 0;

    private trace(ox: number, oy: number, oz: number, dx: number, dy: number, dz: number,
                  far: number, epsilon: number, anyHit: boolean): number {
        const invX = 1 / dx, invY = 1 / dy, invZ = 1 / dz;
        let best = -1;
        let bestT = far;
        let sp = 0;
        this.stack[sp++] = 0;
        // A tree is walked once per node at most; past that the walk is going in
        // circles, and a bake that hangs says less than one that throws.
        let visits = 0;
        while (sp > 0) {
            if (++visits > this.used) throw new Error('Bvh: the walk revisited a node — the tree is malformed');
            const node = this.stack[--sp];
            const b = node * 6;
            const tx1 = (this.bounds[b] - ox) * invX, tx2 = (this.bounds[b + 3] - ox) * invX;
            let tmin = Math.min(tx1, tx2), tmax = Math.max(tx1, tx2);
            const ty1 = (this.bounds[b + 1] - oy) * invY, ty2 = (this.bounds[b + 4] - oy) * invY;
            tmin = Math.max(tmin, Math.min(ty1, ty2)); tmax = Math.min(tmax, Math.max(ty1, ty2));
            const tz1 = (this.bounds[b + 2] - oz) * invZ, tz2 = (this.bounds[b + 5] - oz) * invZ;
            tmin = Math.max(tmin, Math.min(tz1, tz2)); tmax = Math.min(tmax, Math.max(tz1, tz2));
            if (tmax < Math.max(tmin, epsilon) || tmin > bestT) continue;

            const count = this.node[node * 2 + 1];
            if (count === INNER) {
                const left = this.node[node * 2];
                this.stack[sp++] = left;
                this.stack[sp++] = left + 1;
                continue;
            }
            const first = this.node[node * 2];
            for (let k = 0; k < count; k++) {
                const tri = this.order[first + k];
                const t = this.intersect(tri, ox, oy, oz, dx, dy, dz, epsilon, bestT);
                if (t < 0) continue;
                if (anyHit) { this.hitDistance = t; return tri; }
                // A tie goes to the lower index, so the answer is the geometry's and
                // not the order a tree happens to visit coincident triangles in.
                if (t === bestT && (best < 0 || tri > best)) continue;
                bestT = t; best = tri;
                this.hitU = this.lastU; this.hitV = this.lastV;
            }
        }
        this.hitDistance = bestT;
        return best;
    }

    private lastU = 0;
    private lastV = 0;

    /** Möller-Trumbore, both faces: a bake lights what is there, and a wall
     *  modelled inside out still occludes the room. */
    private intersect(tri: number, ox: number, oy: number, oz: number,
                      dx: number, dy: number, dz: number, epsilon: number, far: number): number {
        const p = this.tris.positions;
        const at = tri * 9;
        const e1x = p[at + 3] - p[at], e1y = p[at + 4] - p[at + 1], e1z = p[at + 5] - p[at + 2];
        const e2x = p[at + 6] - p[at], e2y = p[at + 7] - p[at + 1], e2z = p[at + 8] - p[at + 2];
        const hx = dy * e2z - dz * e2y, hy = dz * e2x - dx * e2z, hz = dx * e2y - dy * e2x;
        const a = e1x * hx + e1y * hy + e1z * hz;
        if (a > -1e-12 && a < 1e-12) return -1;
        const f = 1 / a;
        const sx = ox - p[at], sy = oy - p[at + 1], sz = oz - p[at + 2];
        const u = f * (sx * hx + sy * hy + sz * hz);
        if (u < 0 || u > 1) return -1;
        const qx = sy * e1z - sz * e1y, qy = sz * e1x - sx * e1z, qz = sx * e1y - sy * e1x;
        const v = f * (dx * qx + dy * qy + dz * qz);
        if (v < 0 || u + v > 1) return -1;
        const t = f * (e2x * qx + e2y * qy + e2z * qz);
        if (t <= epsilon || t > far) return -1;
        this.lastU = u; this.lastV = v;
        return t;
    }
}