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.

14.0 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * The claim: a bake can be read through what this produces.
 *
 * That is one property and not a resemblance — NO TWO SURFACES SHARE A TEXEL —
 * so it is checked the way a bake would use it: rasterise every triangle into a
 * grid of lumels and look for one covered twice.
 */
import { describe, it, expect } from 'vitest';
import { readFileSync } from 'node:fs';
import path from 'node:path';
import { unwrapLightmapUV } from '../src/lightmap';
import { packOutlines, type ChartOutline } from '../src/lightmap/pack';
import { decodeMesh, MeshChannel, MeshChannelType, type MeshData, type MeshChannelDesc } from '../src/asset/meshFormat';

const chan = (m: MeshData, s: number): MeshChannelDesc =>
    m.channels.find((c) => c.semantic === s) as MeshChannelDesc;

function readVec(m: MeshData, semantic: number, v: number, n: number): number[] {
    const c = chan(m, semantic);
    const view = new DataView(m.vertices.buffer, m.vertices.byteOffset, m.vertices.byteLength);
    const at = v * m.vertexStride + c.offset;
    return Array.from({ length: n }, (_, i) => view.getFloat32(at + i * 4, true));
}

/** A unit cube: six faces at right angles, so a 60-degree chart angle must cut it
 *  into six pieces and split all eight of its corners three ways. */
function cube(): MeshData {
    const corners = [
        [-1, -1, -1], [1, -1, -1], [1, 1, -1], [-1, 1, -1],
        [-1, -1, 1], [1, -1, 1], [1, 1, 1], [-1, 1, 1],
    ];
    const faces = [
        [0, 1, 2, 3], [5, 4, 7, 6], [4, 0, 3, 7],
        [1, 5, 6, 2], [4, 5, 1, 0], [3, 2, 6, 7],
    ];
    const stride = 12;
    const vertices = new Uint8Array(corners.length * stride);
    const view = new DataView(vertices.buffer);
    corners.forEach((p, i) => {
        for (let k = 0; k < 3; k++) view.setFloat32(i * stride + k * 4, p[k], true);
    });
    const indices: number[] = [];
    for (const [a, b, c, d] of faces) indices.push(a, b, c, a, c, d);
    return {
        channels: [{ semantic: MeshChannel.Position, components: 3, type: MeshChannelType.Float32, offset: 0 }],
        vertexStride: stride,
        vertexCount: corners.length,
        vertices,
        indices: Uint32Array.from(indices),
        aabbMin: [-1, -1, -1],
        aabbMax: [1, 1, 1],
    };
}

/**
 * How many times each lumel of an `n`-by-`n` atlas is covered.
 *
 * A texel centre inside two triangles is the failure a lightmap cannot survive:
 * one surface's light is written over the other's, and which one wins depends on
 * the order the bake visits them in. A centre exactly on a shared edge is one point of one surface, and not that.
 */
function coverage(mesh: MeshData, n: number): { max: number; touched: number } {
    const count = new Uint16Array(n * n);
    const uvOf = (v: number): [number, number] => readVec(mesh, MeshChannel.TexCoord1, v, 2) as [number, number];
    for (let i = 0; i + 2 < mesh.indices.length; i += 3) {
        const p = [uvOf(mesh.indices[i]), uvOf(mesh.indices[i + 1]), uvOf(mesh.indices[i + 2])];
        const minX = Math.max(0, Math.floor(Math.min(...p.map((q) => q[0])) * n));
        const maxX = Math.min(n - 1, Math.ceil(Math.max(...p.map((q) => q[0])) * n));
        const minY = Math.max(0, Math.floor(Math.min(...p.map((q) => q[1])) * n));
        const maxY = Math.min(n - 1, Math.ceil(Math.max(...p.map((q) => q[1])) * n));
        const area = (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) - (p[2][0] - p[0][0]) * (p[1][1] - p[0][1]);
        if (Math.abs(area) < 1e-12) continue;
        for (let y = minY; y <= maxY; y++) {
            for (let x = minX; x <= maxX; x++) {
                const cx = (x + 0.5) / n, cy = (y + 0.5) / n;
                const w0 = ((p[1][0] - cx) * (p[2][1] - cy) - (p[2][0] - cx) * (p[1][1] - cy)) / area;
                const w1 = ((p[2][0] - cx) * (p[0][1] - cy) - (p[0][0] - cx) * (p[2][1] - cy)) / area;
                const w2 = 1 - w0 - w1;
                if (w0 > 1e-9 && w1 > 1e-9 && w2 > 1e-9) count[y * n + x]++;
            }
        }
    }
    let max = 0, touched = 0;
    for (const c of count) { if (c > max) max = c; if (c > 0) touched++; }
    return { max, touched };
}

/** World area of every triangle, by index, from the positions. */
function worldAreas(mesh: MeshData): number[] {
    const out: number[] = [];
    for (let i = 0; i + 2 < mesh.indices.length; i += 3) {
        const [a, b, c] = [0, 1, 2].map((k) => readVec(mesh, MeshChannel.Position, mesh.indices[i + k], 3));
        const u = [b[0] - a[0], b[1] - a[1], b[2] - a[2]];
        const v = [c[0] - a[0], c[1] - a[1], c[2] - a[2]];
        out.push(Math.hypot(u[1] * v[2] - u[2] * v[1], u[2] * v[0] - u[0] * v[2], u[0] * v[1] - u[1] * v[0]) / 2);
    }
    return out;
}

function uvAreas(mesh: MeshData): number[] {
    const out: number[] = [];
    for (let i = 0; i + 2 < mesh.indices.length; i += 3) {
        const [a, b, c] = [0, 1, 2].map((k) => readVec(mesh, MeshChannel.TexCoord1, mesh.indices[i + k], 2));
        out.push(Math.abs((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) / 2);
    }
    return out;
}

describe('a lightmap UV set', () => {
    it('gives a cube six charts and splits every corner three ways', () => {
        const { mesh, charts } = unwrapLightmapUV(cube());
        expect(charts).toBe(6);
        // Eight corners, each used by three faces that are three charts.
        expect(mesh.vertexCount).toBe(24);
        expect(mesh.indices.length).toBe(36);
    });

    it('never covers one lumel twice', () => {
        const { mesh } = unwrapLightmapUV(cube());
        const { max, touched } = coverage(mesh, 128);
        expect(touched).toBeGreaterThan(0);
        expect(max).toBe(1);
    });

    it('keeps coincident layers separate across welded non-manifold edges', () => {
        const source = cube();
        source.indices = Uint32Array.from([...source.indices, ...source.indices]);
        const { mesh } = unwrapLightmapUV(source);
        expect(mesh.indices.length).toBe(source.indices.length);
        expect(coverage(mesh, 128).max).toBe(1);
    });

    it('keeps duplicate triangles separate when their shared edges have the same winding', () => {
        const source = cube();
        source.indices = Uint32Array.from([0, 1, 2, 0, 1, 2]);
        const { mesh } = unwrapLightmapUV(source);
        expect(mesh.indices.length).toBe(6);
        expect(coverage(mesh, 128).max).toBe(1);
    });

    it('stays inside the unit square', () => {
        const { mesh } = unwrapLightmapUV(cube());
        for (let v = 0; v < mesh.vertexCount; v++) {
            const [u, w] = readVec(mesh, MeshChannel.TexCoord1, v, 2);
            expect(u).toBeGreaterThanOrEqual(0);
            expect(w).toBeGreaterThanOrEqual(0);
            expect(u).toBeLessThanOrEqual(1);
            expect(w).toBeLessThanOrEqual(1);
        }
    });

    it('lights every face at the same resolution', () => {
        // ONE world-to-texel ratio, which is what stops a wall being sharper than
        // the floor it meets. Per triangle the ratio is uv area over world area.
        const { mesh } = unwrapLightmapUV(cube());
        const ratios = uvAreas(mesh).map((uv, i) => uv / worldAreas(mesh)[i]);
        const lo = Math.min(...ratios), hi = Math.max(...ratios);
        expect(hi / lo).toBeLessThan(1.0001);
    });

    it('does not move a single vertex', () => {
        const before = cube();
        const { mesh } = unwrapLightmapUV(before);
        const tri = (m: MeshData, i: number): string =>
            [0, 1, 2].map((k) => readVec(m, MeshChannel.Position, m.indices[i + k], 3).join(',')).join('|');
        const was = new Set<string>();
        for (let i = 0; i + 2 < before.indices.length; i += 3) was.add(tri(before, i));
        for (let i = 0; i + 2 < mesh.indices.length; i += 3) expect(was.has(tri(mesh, i))).toBe(true);
        expect(mesh.indices.length).toBe(before.indices.length);
    });

    it('takes every shape the mesh can be blended into with it', () => {
        // A split vertex is the SAME vertex twice, so whatever moves the original
        // has to move both. Nothing else here reads the deltas, and a remap that
        // indexed the new table by its own position passed every other case.
        const base = cube();
        const per = 3;
        const deltas = new Float32Array(base.vertexCount * per);
        for (let v = 0; v < base.vertexCount; v++) deltas[v * per] = v + 1;
        const { mesh } = unwrapLightmapUV({
            ...base,
            morph: { names: ['Push'], hasNormals: false, deltas },
        });
        const moved = mesh.morph as NonNullable<MeshData['morph']>;
        expect(moved.deltas.length).toBe(mesh.vertexCount * per);
        // Looked up rather than derived: the corners are in winding order, and a
        // bit-pattern guess at their indices is a bug in this case, not the unwrap.
        const corners = new Map<string, number>();
        for (let v = 0; v < base.vertexCount; v++) {
            corners.set(readVec(base, MeshChannel.Position, v, 3).join(','), v);
        }
        for (let v = 0; v < mesh.vertexCount; v++) {
            const from = corners.get(readVec(mesh, MeshChannel.Position, v, 3).join(','));
            expect(from).toBeDefined();
            expect(moved.deltas[v * per]).toBe((from as number) + 1);
        }
    });

    it('carries a real model, not only a cube', () => {
        // A cube's charts are six flat quads; a model's are neither, and the packer
        // meets shapes a synthetic case never produces. Resolved from THIS file: a
        // relative path made the case skip itself in silence and pass for it.
        const file = path.resolve(__dirname,
            '../../examples/character-rig/assets/models/knight_4_0.esmesh');
        const source = decodeMesh(new Uint8Array(readFileSync(file)));
        expect(source.vertexCount).toBeGreaterThan(100);
        const { mesh, charts, coverage: filled } = unwrapLightmapUV(source);
        expect(charts).toBeGreaterThan(1);
        expect(mesh.vertexCount).toBeGreaterThanOrEqual(source.vertexCount);
        expect(filled).toBeGreaterThan(0.05);
        expect(coverage(mesh, 256).max).toBe(1);
    });

    it('uses the room there is: a cube fills all it can, not a fixed half of its square', () => {
        const { coverage: filled } = unwrapLightmapUV(cube());
        // Six squares at one size in a square: two rows of three is 2/3 of it, less the padding.
        expect(filled).toBeGreaterThan(0.6);
        expect(filled).toBeLessThanOrEqual(2 / 3);
    });

    it('keeps its padding between charts', () => {
        const atlasSize = 256, paddingTexels = 4;
        const { mesh } = unwrapLightmapUV(cube(), { atlasSize, paddingTexels });
        const boxes: number[][] = [];
        for (let i = 0; i < mesh.indices.length; i += 6) {
            const uv = [0, 1, 2, 5].map((k) => readVec(mesh, MeshChannel.TexCoord1, mesh.indices[i + k], 2));
            boxes.push([Math.min(...uv.map((p) => p[0])), Math.min(...uv.map((p) => p[1])), Math.max(...uv.map((p) => p[0])), Math.max(...uv.map((p) => p[1]))]);
        }
        expect(boxes.length).toBe(6);
        for (let a = 0; a < 6; a++) {
            for (let b = a + 1; b < 6; b++) {
                const apart = Math.max(boxes[b][0] - boxes[a][2], boxes[a][0] - boxes[b][2], boxes[b][1] - boxes[a][3], boxes[a][1] - boxes[b][3]);
                expect(apart * atlasSize).toBeGreaterThanOrEqual(paddingTexels - 0.01);
            }
        }
    });

    it('still holds with more charts than it lays out by outline', () => {
        // Scattered triangles facing every way: each its own chart, past where rasterising them all is worth it.
        const count = 2000;
        const vertices = new Uint8Array(count * 3 * 12);
        const view = new DataView(vertices.buffer);
        const indices: number[] = [];
        for (let t = 0; t < count; t++) {
            const [x, y, z] = [t % 13, (t * 7) % 17, (t * 3) % 19];
            const tri = [[x, y, z], [x + 0.4, y, z], [x, y + 0.4, z]];
            tri.forEach((p, k) => p.forEach((c, n) => view.setFloat32((t * 3 + k) * 12 + n * 4, c + (n === 2 ? t * 40 : 0), true)));
            indices.push(t * 3, t * 3 + 1, t * 3 + 2);
        }
        const { mesh, charts } = unwrapLightmapUV({
            channels: [{ semantic: MeshChannel.Position, components: 3, type: MeshChannelType.Float32, offset: 0 }],
            vertexStride: 12, vertexCount: count * 3, vertices, indices: Uint32Array.from(indices),
            aabbMin: [0, 0, 0], aabbMax: [13, 17, count * 40],
        });
        expect(charts).toBe(count);
        expect(coverage(mesh, 2048).max).toBe(1);
        for (let v = 0; v < mesh.vertexCount; v++) {
            for (const c of readVec(mesh, MeshChannel.TexCoord1, v, 2)) { expect(c).toBeGreaterThanOrEqual(0); expect(c).toBeLessThanOrEqual(1); }
        }
    });
});

describe('packing by outline', () => {
    /** An L: most of its bounding box is the bite out of its corner. */
    const ell: ChartOutline = {
        width: 1, height: 1,
        triangles: [0, 0, 1, 0, 1, 0.2, 0, 0, 1, 0.2, 0, 0.2, 0, 0.2, 0.2, 0.2, 0.2, 1, 0, 0.2, 0.2, 1, 0, 1],
    };
    const square = (side: number): ChartOutline => ({ width: side, height: side, triangles: [0, 0, side, 0, side, side, 0, 0, side, side, 0, side] });

    it('sets a small chart in the bite of a large one, where their rectangles would need twice the room', () => {
        const placed = packOutlines([ell, square(0.5)], 0.95, 128, 1)!;
        expect(placed).not.toBeNull();
        const [a, b] = placed;
        expect(Math.max(b!.x - a!.x, b!.y - a!.y)).toBeGreaterThan(0);
        // The square is inside the L's rectangle: it did not need room of its own.
        expect(b!.x + 0.5 * 0.95).toBeLessThanOrEqual(a!.x + 0.95 + 1e-6);
        expect(b!.y + 0.5 * 0.95).toBeLessThanOrEqual(a!.y + 0.95 + 1e-6);
    });

    it('says when they do not fit', () => {
        expect(packOutlines([square(1), square(1)], 0.9, 64, 1)).toBeNull();
    });

    it('reads the same every time', () => {
        const charts = [ell, square(0.3), square(0.2), square(0.1)];
        expect(packOutlines(charts, 0.7, 128, 1)).toEqual(packOutlines(charts, 0.7, 128, 1));
    });
});