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.8 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file polygon-decompose.test.ts — a concave ring as the shapes it collides as.
 *
 * The properties matter more than the piece count: any partition is correct if
 * every piece is convex, within the solver's cap, and the pieces together cover
 * the ring and nothing outside it. Asserting a count would pin the algorithm
 * rather than the contract, so only the cases with one obvious answer do.
 *
 * Coverage is checked by sampling: points known to be inside the ring must land
 * in some piece, and points in a notch must land in none. That is the property a
 * player actually feels — whether they can walk into the dent.
 */
import { describe, it, expect } from 'vitest';
import { decomposePolygon2D } from '../src/physics/polygonDecompose2D';
import { MAX_POLYGON_VERTICES, MIN_POLYGON_VERTICES } from '../src/physics/polygonHull2D';
import { collider2DOutline, type Collider2DShape } from '../src/physics/ColliderShape2D';

type P = { x: number; y: number };
const p = (x: number, y: number): P => ({ x, y });

const cross = (ax: number, ay: number, bx: number, by: number) => ax * by - ay * bx;

/** Inside or on the boundary of a convex CCW ring. */
function inPiece(q: P, ring: readonly P[]): boolean {
    for (let i = 0; i < ring.length; i++) {
        const a = ring[i];
        const b = ring[(i + 1) % ring.length];
        if (cross(b.x - a.x, b.y - a.y, q.x - a.x, q.y - a.y) < -1e-9) return false;
    }
    return true;
}

const covered = (q: P, pieces: readonly P[][]) => pieces.some((piece) => inPiece(q, piece));

/** Every piece a shape Box2D will take: convex, wound CCW, within the cap. */
function expectWellFormed(pieces: readonly P[][]) {
    expect(pieces.length).toBeGreaterThan(0);
    for (const ring of pieces) {
        expect(ring.length).toBeGreaterThanOrEqual(MIN_POLYGON_VERTICES);
        expect(ring.length).toBeLessThanOrEqual(MAX_POLYGON_VERTICES);
        let area2 = 0;
        for (let i = 0; i < ring.length; i++) {
            const a = ring[i];
            const b = ring[(i + 1) % ring.length];
            area2 += cross(a.x, a.y, b.x, b.y);
            const c = ring[(i + 2) % ring.length];
            expect(cross(b.x - a.x, b.y - a.y, c.x - b.x, c.y - b.y)).toBeGreaterThanOrEqual(-1e-9);
        }
        expect(area2).toBeGreaterThan(0); // counter-clockwise, with real area
    }
}

// A dart: three corners with the bottom edge pushed up into the middle.
const DART = [p(-1, -1), p(0, 0), p(1, -1), p(0, 1)];
// An L, the textbook concave case: one inner corner.
const L = [p(0, 0), p(2, 0), p(2, 1), p(1, 1), p(1, 2), p(0, 2)];
// A C, which no single split can solve — the mouth is deep.
const C = [
    p(0, 0), p(3, 0), p(3, 1), p(1, 1), p(1, 2), p(3, 2), p(3, 3), p(0, 3),
];

describe('decomposePolygon2D', () => {
    it('leaves a convex ring alone — one piece, the points as drawn', () => {
        const square = [p(-1, -1), p(1, -1), p(1, 1), p(-1, 1)];
        const d = decomposePolygon2D(square);
        expect(d.degenerate).toBe(false);
        expect(d.pieces).toHaveLength(1);
        expect(d.pieces[0]).toEqual(square);
    });

    it('rewinds a clockwise ring rather than refusing it', () => {
        const cw = [p(-1, -1), p(-1, 1), p(1, 1), p(1, -1)];
        const d = decomposePolygon2D(cw);
        expect(d.pieces).toHaveLength(1);
        expectWellFormed(d.pieces);
    });

    it('splits a dart, and the notch is no longer solid', () => {
        const d = decomposePolygon2D(DART);
        expect(d.degenerate).toBe(false);
        expectWellFormed(d.pieces);
        expect(d.pieces.length).toBeGreaterThan(1);
        // Just below the notch vertex is outside the ring: the hull would cover it.
        expect(covered(p(0, -0.5), d.pieces)).toBe(false);
        // ...while the two lobes beside it are still solid.
        expect(covered(p(-0.5, -0.3), d.pieces)).toBe(true);
        expect(covered(p(0.5, -0.3), d.pieces)).toBe(true);
        expect(covered(p(0, 0.5), d.pieces)).toBe(true);
    });

    it('splits an L and leaves the missing quadrant empty', () => {
        const d = decomposePolygon2D(L);
        expectWellFormed(d.pieces);
        expect(covered(p(0.5, 0.5), d.pieces)).toBe(true);
        expect(covered(p(1.5, 0.5), d.pieces)).toBe(true);
        expect(covered(p(0.5, 1.5), d.pieces)).toBe(true);
        expect(covered(p(1.5, 1.5), d.pieces)).toBe(false); // the quadrant the L omits
    });

    it('keeps the mouth of a C open', () => {
        const d = decomposePolygon2D(C);
        expectWellFormed(d.pieces);
        expect(covered(p(2, 1.5), d.pieces)).toBe(false); // inside the mouth
        expect(covered(p(0.5, 1.5), d.pieces)).toBe(true); // the spine behind it
        expect(covered(p(2, 0.5), d.pieces)).toBe(true);   // the lower arm
        expect(covered(p(2, 2.5), d.pieces)).toBe(true);   // the upper arm
    });

    it('takes a ring far past the solver cap, in pieces that each obey it', () => {
        // A 24-point star: twelve reflex vertices, nothing a single polygon can hold.
        const star: P[] = [];
        for (let i = 0; i < 24; i++) {
            const a = (i * 2 * Math.PI) / 24;
            const r = i % 2 === 0 ? 2 : 1;
            star.push(p(r * Math.cos(a), r * Math.sin(a)));
        }
        const d = decomposePolygon2D(star);
        expect(d.degenerate).toBe(false);
        expectWellFormed(d.pieces);
        expect(covered(p(0, 0), d.pieces)).toBe(true);       // the body
        expect(covered(p(1.9, 0), d.pieces)).toBe(true);      // out along a spike
        expect(covered(p(1.35, 1.35), d.pieces)).toBe(false); // the gap between two
    });

    it('partitions a comb — several teeth, several slots, one ring', () => {
        const comb = [
            p(-3, -1), p(3, -1), p(3, 0), p(2, 0), p(2, 2), p(1, 2),
            p(1, 0), p(0, 0), p(0, 2), p(-1, 2), p(-1, 0), p(-3, 0),
        ];
        const d = decomposePolygon2D(comb);
        expect(d.degenerate).toBe(false);
        expectWellFormed(d.pieces);
        expect(covered(p(0.5, 1), d.pieces)).toBe(false); // the slot between the teeth
        expect(covered(p(1.5, 1), d.pieces)).toBe(true);  // a tooth
        expect(covered(p(-0.5, 1), d.pieces)).toBe(true); // the other tooth
        expect(covered(p(0.5, -0.5), d.pieces)).toBe(true); // the base under the slot
    });

    it('survives a ring whose first eight points are collinear', () => {
        // What the editor's insert makes of one edge subdivided over and over. The
        // hull only ever looks at eight points, so using it to ask "is this a shape"
        // answered no here, and the collider vanished.
        let ring = [p(-1, -1), p(1, -1), p(1, 1), p(-1, 1)];
        for (let k = 0; k < 8; k++) {
            const a = ring[0];
            const b = ring[1];
            ring = [a, p((a.x + b.x) / 2, (a.y + b.y) / 2), ...ring.slice(1)];
        }
        expect(ring.length).toBeGreaterThan(MAX_POLYGON_VERTICES);
        const d = decomposePolygon2D(ring);
        expect(d.degenerate).toBe(false);
        expectWellFormed(d.pieces);
        expect(covered(p(0, 0), d.pieces)).toBe(true);     // still a solid square
        expect(covered(p(0, 2), d.pieces)).toBe(false);
    });

    it('is deterministic — the same ring gives the same pieces every time', () => {
        expect(decomposePolygon2D(C).pieces).toEqual(decomposePolygon2D(C).pieces);
    });

    it('falls back to the hull for a ring that crosses itself, and says so', () => {
        const bowtie = [p(-1, -1), p(1, 1), p(1, -1), p(-1, 1)];
        const d = decomposePolygon2D(bowtie);
        expect(d.degenerate).toBe(true);
        expectWellFormed(d.pieces);
        expect(d.pieces).toHaveLength(1);
    });

    it('builds nothing from a ring with no shape in it', () => {
        expect(decomposePolygon2D([p(0, 0), p(1, 0)]).pieces).toEqual([]);
        expect(decomposePolygon2D([]).pieces).toEqual([]);
        // Three points on a line: welded and collinear, so the solver builds none.
        expect(decomposePolygon2D([p(0, 0), p(1, 0), p(2, 0)]).pieces).toEqual([]);
    });

    it('welds a duplicated point rather than tripping over the zero-length edge', () => {
        const d = decomposePolygon2D([p(0, 0), p(0.001, 0), p(2, 0), p(2, 1), p(1, 1), p(1, 2), p(0, 2)]);
        expect(d.degenerate).toBe(false);
        expectWellFormed(d.pieces);
        expect(covered(p(1.5, 1.5), d.pieces)).toBe(false);
    });
});

describe('collider2DOutline draws what collides', () => {
    const outlineOf = (vertices: P[]) =>
        collider2DOutline({ kind: 'polygon', vertices } as Collider2DShape, p(0, 0), 0, 100);

    it('a convex polygon draws once, as authored', () => {
        const o = outlineOf([p(-0.5, -0.5), p(0.5, -0.5), p(0.5, 0.5), p(-0.5, 0.5)]);
        expect(o.declined).toBeUndefined();
        expect(o.polylines[0]).toHaveLength(5); // 4 corners + the closing point
    });

    it('a concave polygon ALSO draws once — the ring is what it collides as', () => {
        const o = outlineOf(DART);
        expect(o.declined).toBeUndefined();
        expect(o.polylines).toHaveLength(1);
        expect(o.polylines[0]).toHaveLength(5); // the authored 4, closed
    });

    it('a ring past the vertex cap draws whole, because it is built whole', () => {
        const o = outlineOf(C);
        expect(o.declined).toBeUndefined();
        expect(o.polylines[0]).toHaveLength(C.length + 1);
    });

    it('a self-crossing ring draws its hull solid and the ring apart', () => {
        const o = outlineOf([p(-1, -1), p(1, 1), p(1, -1), p(-1, 1)]);
        expect(o.declined?.[0]).toHaveLength(5);
        expect(o.polylines.length).toBeGreaterThan(0);
    });

    it('a ring with no area draws no solid outline at all', () => {
        const o = outlineOf([p(0, 0), p(1, 0), p(2, 0)]);
        expect(o.polylines).toEqual([]);
        expect(o.declined?.[0]).toHaveLength(4);
    });
});