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.

8.3 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file    surface.ts
 * @brief   The ground as one set of triangles: what is drawn near the eye, what is collided with and what a query answers.
 *
 * @details The ground is the lattice of `cellSize` cells in the terrain's space (a node at every multiple of the cell), each node as
 *          high as the source says there (an area's nodes past its edge take the edge's height), and each cell cut in two along the
 *          diagonal from its (1, 0) corner to its (0, 1) corner. That is the finest level the quadtree draws (a patch's vertices fall
 *          on the lattice and are cut the same way), the triangles collision is built from, and what `heightAt` and `normalAt` read, so
 *          all three agree to the GPU's 16-bit height encoding. Coarser levels farther from the eye are drawn coarser; nothing collides
 *          with them. The rule does not change with the camera, the order tiles are made in, or a reload.
 */
import type { TerrainSource } from './source';

/** Cells along a collision tile's side. */
export const TILE_CELLS = 32;

/** A tile's triangles: positions relative to its corner (x0, 0, z0) in the terrain's space, wound counter-clockwise from above. */
export interface SurfaceTile { x0: number; z0: number; positions: Float32Array; indices: Uint32Array }

export class TerrainSurface {
    constructor(readonly source: TerrainSource, readonly cell: number) {}

    /** The height of lattice node (i, k), or null where the source has not answered. Off an area it is its nearest edge's, as the pages have it. */
    node(i: number, k: number): number | null {
        let x = i * this.cell, z = k * this.cell;
        const b = this.source.bounds;
        if (b) {
            x = Math.min(Math.max(x, b[0]), b[2]);
            z = Math.min(Math.max(z, b[1]), b[3]);
        }
        return this.source.height(x, z);
    }

    /** Whether (x, z) is on the ground: inside an area, anywhere for ground without end. */
    covers(x: number, z: number): boolean {
        const b = this.source.bounds;
        return !b || (x >= b[0] && x <= b[2] && z >= b[1] && z <= b[3]);
    }

    /** The height at (x, z) on its cell's triangle, or null off the ground or where a corner is not known yet. */
    height(x: number, z: number): number | null {
        const c = this.corners(x, z);
        if (!c) return null;
        const [a, b, cc, d, fx, fz] = c;
        return fx + fz <= 1 ? a + (b - a) * fx + (cc - a) * fz : d + (cc - d) * (1 - fx) + (b - d) * (1 - fz);
    }

    /** The normal of the triangle under (x, z), or null where its height is not known. */
    normal(x: number, z: number): [number, number, number] | null {
        const c = this.corners(x, z);
        if (!c) return null;
        const [a, b, cc, d, fx, fz] = c;
        const sx = (fx + fz <= 1 ? b - a : d - cc) / this.cell, sz = (fx + fz <= 1 ? cc - a : d - b) / this.cell;
        const len = Math.hypot(sx, 1, sz);
        return [-sx / len, 1 / len, -sz / len];
    }

    /** Tile (tx, tz)'s triangles, or null while a node of it is not known yet. */
    tile(tx: number, tz: number): SurfaceTile | null {
        const n = TILE_CELLS, side = n + 1;
        const positions = new Float32Array(side * side * 3);
        for (let k = 0; k <= n; k++) for (let i = 0; i <= n; i++) {
            const h = this.node(tx * n + i, tz * n + k);
            if (h === null) return null;
            const at = (k * side + i) * 3;
            positions[at] = i * this.cell;
            positions[at + 1] = h;
            positions[at + 2] = k * this.cell;
        }
        const indices = new Uint32Array(n * n * 6);
        let at = 0;
        for (let k = 0; k < n; k++) for (let i = 0; i < n; i++) {
            const a = k * side + i, b = a + 1, c = a + side, d = c + 1;
            // The patch's cut and winding (patch.ts): a, the next row, the next column; then the other half.
            indices.set([a, c, b, b, c, d], at);
            at += 6;
        }
        return { x0: tx * n * this.cell, z0: tz * n * this.cell, positions, indices };
    }

    /**
     * Where the ray from (ox, oy, oz) along (dx, dy, dz) first meets the ground, within `maxDistance` (along the direction, normalised):
     * the distance, the point and the triangle's normal; null where it meets none (or crosses ground not known yet). Exact against the
     * triangles: it walks the lattice cell by cell under the ray and meets each cell's two.
     */
    raycast(ox: number, oy: number, oz: number, dx: number, dy: number, dz: number, maxDistance: number):
        { distance: number; point: [number, number, number]; normal: [number, number, number] } | null {
        const len = Math.hypot(dx, dy, dz);
        if (len <= 0) return null;
        dx /= len; dy /= len; dz /= len;
        const c = this.cell;
        // Over the cells the ray's shadow on the ground crosses, in order (Amanatides and Woo).
        let i = Math.floor(ox / c), k = Math.floor(oz / c);
        const si = dx > 0 ? 1 : -1, sk = dz > 0 ? 1 : -1;
        const tdi = dx !== 0 ? Math.abs(c / dx) : Infinity, tdk = dz !== 0 ? Math.abs(c / dz) : Infinity;
        let ti = dx !== 0 ? ((dx > 0 ? (i + 1) * c : i * c) - ox) / dx : Infinity;
        let tk = dz !== 0 ? ((dz > 0 ? (k + 1) * c : k * c) - oz) / dz : Infinity;
        let t = 0;
        for (let steps = 0; steps < 1_000_000 && t <= maxDistance; steps++) {
            const a = this.node(i, k), b = this.node(i + 1, k), cc = this.node(i, k + 1), d = this.node(i + 1, k + 1);
            if (a === null || b === null || cc === null || d === null) return null;
            const x0 = i * c, z0 = k * c;
            // The cell's two triangles, cut from its (1, 0) corner to its (0, 1) corner, as the patch is.
            for (const tri of [[[x0, a, z0], [x0, cc, z0 + c], [x0 + c, b, z0]], [[x0 + c, b, z0], [x0, cc, z0 + c], [x0 + c, d, z0 + c]]] as const) {
                const hit = rayTriangle(ox, oy, oz, dx, dy, dz, tri[0], tri[1], tri[2]);
                if (hit && hit.t <= maxDistance && this.covers(ox + dx * hit.t, oz + dz * hit.t)) {
                    return { distance: hit.t, point: [ox + dx * hit.t, oy + dy * hit.t, oz + dz * hit.t], normal: hit.n };
                }
            }
            if (ti < tk) { t = ti; ti += tdi; i += si; } else { t = tk; tk += tdk; k += sk; }
            if (dx === 0 && dz === 0) break;
        }
        return null;
    }

    /** The four corners of the cell under (x, z) and where in it the point is, or null. */
    private corners(x: number, z: number): [number, number, number, number, number, number] | null {
        if (!this.covers(x, z)) return null;
        const u = x / this.cell, v = z / this.cell;
        const i = Math.floor(u), k = Math.floor(v);
        const a = this.node(i, k), b = this.node(i + 1, k), c = this.node(i, k + 1), d = this.node(i + 1, k + 1);
        if (a === null || b === null || c === null || d === null) return null;
        return [a, b, c, d, u - i, v - k];
    }
}

/** Where a ray (unit direction) meets a triangle from either side, and the triangle's upward normal; null where it misses. */
function rayTriangle(ox: number, oy: number, oz: number, dx: number, dy: number, dz: number,
                     p0: readonly number[], p1: readonly number[], p2: readonly number[]): { t: number; n: [number, number, number] } | null {
    const e1x = p1[0]! - p0[0]!, e1y = p1[1]! - p0[1]!, e1z = p1[2]! - p0[2]!;
    const e2x = p2[0]! - p0[0]!, e2y = p2[1]! - p0[1]!, e2z = p2[2]! - p0[2]!;
    const px = dy * e2z - dz * e2y, py = dz * e2x - dx * e2z, pz = dx * e2y - dy * e2x;
    const det = e1x * px + e1y * py + e1z * pz;
    if (Math.abs(det) < 1e-12) return null;
    const inv = 1 / det;
    const sx = ox - p0[0]!, sy = oy - p0[1]!, sz = oz - p0[2]!;
    const u = (sx * px + sy * py + sz * pz) * inv;
    if (u < -1e-9 || u > 1 + 1e-9) return null;
    const qx = sy * e1z - sz * e1y, qy = sz * e1x - sx * e1z, qz = sx * e1y - sy * e1x;
    const v = (dx * qx + dy * qy + dz * qz) * inv;
    if (v < -1e-9 || u + v > 1 + 1e-9) return null;
    const t = (e2x * qx + e2y * qy + e2z * qz) * inv;
    if (t < 0) return null;
    let nx = e1y * e2z - e1z * e2y, ny = e1z * e2x - e1x * e2z, nz = e1x * e2y - e1y * e2x;
    if (ny < 0) { nx = -nx; ny = -ny; nz = -nz; }
    const l = Math.hypot(nx, ny, nz) || 1;
    return { t, n: [nx / l, ny / l, nz / l] };
}