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.
TypeScript 2d-game-engine3d3d-game-engineandroidcppecsgame-editorgame-enginegamedeviostypescriptwebassemblywebglwebgpuwechat-minigame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
* @file polygonDecompose2D.ts
* @brief The convex pieces a concave collider ring collides as.
*
* @details Box2D builds only convex polygons, and only eight vertices of one. A
* ring that is neither is not a shape it can take — but it IS a union of
* shapes it can take, so the limit belongs to a PIECE rather than to
* what an author may draw.
*
* Ear clipping to triangles, then merging neighbours back while the
* result stays convex and within the cap. The merge works on vertex
* INDICES, so two pieces share an edge exactly rather than within a
* tolerance: float comparison at a seam is how a partition develops
* gaps nothing can be pushed out of.
*
* Every piece is finally passed through {@link computePolygonHull},
* which is what Box2D will do to it. A sliver the solver would refuse
* is dropped here instead of silently becoming no shape at run time.
*/
import type { Vec2 } from '../types';
import { computePolygonHull, MAX_POLYGON_VERTICES, MIN_POLYGON_VERTICES } from './polygonHull2D';
/** Points nearer than this are one point, matching the hull's own welding. */
const WELD = 0.02;
/** Box2D's linear slop; {@link WELD} is the 4x radius its hull welds within. */
const SLOP = WELD / 4;
const cross = (ax: number, ay: number, bx: number, by: number): number => ax * by - ay * bx;
/** The turn at `b` walking a → b → c. Positive is a left turn, so convex in CCW. */
function turn(a: Vec2, b: Vec2, c: Vec2): number {
return cross(b.x - a.x, b.y - a.y, c.x - b.x, c.y - b.y);
}
/**
* Whether the ring encloses more than slop. Area against PERIMETER, because area
* alone has no scale to be small against: a long thin sliver and a small honest
* triangle measure alike, and only one of them is a shape Box2D builds.
*/
function hasArea(ring: readonly Vec2[]): boolean {
let perimeter = 0;
for (let i = 0; i < ring.length; i++) {
const a = ring[i];
const b = ring[(i + 1) % ring.length];
perimeter += Math.hypot(b.x - a.x, b.y - a.y);
}
return Math.abs(signedArea2(ring)) > 2 * SLOP * perimeter;
}
/** Twice the signed area of a ring: positive counter-clockwise. */
function signedArea2(ring: readonly Vec2[]): number {
let sum = 0;
for (let i = 0; i < ring.length; i++) {
const a = ring[i];
const b = ring[(i + 1) % ring.length];
sum += cross(a.x, a.y, b.x, b.y);
}
return sum;
}
/** No right turn anywhere. Collinear joints pass: Box2D merges those away itself. */
function isConvex(ring: readonly Vec2[]): boolean {
for (let i = 0; i < ring.length; i++) {
const a = ring[(i + ring.length - 1) % ring.length];
const b = ring[i];
const c = ring[(i + 1) % ring.length];
if (turn(a, b, c) < 0) return false;
}
return true;
}
/**
* Whether two segments cross at a point interior to BOTH. Touching — an endpoint
* on a segment, two collinear runs — is not a crossing: a ring may legitimately
* fold back onto its own corner, and only a real crossing has no partition.
*/
function segmentsCross(a: Vec2, b: Vec2, c: Vec2, d: Vec2): boolean {
const d1 = cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
const d2 = cross(b.x - a.x, b.y - a.y, d.x - a.x, d.y - a.y);
const d3 = cross(d.x - c.x, d.y - c.y, a.x - c.x, a.y - c.y);
const d4 = cross(d.x - c.x, d.y - c.y, b.x - c.x, b.y - c.y);
return d1 !== 0 && d2 !== 0 && d3 !== 0 && d4 !== 0
&& (d1 > 0) !== (d2 > 0) && (d3 > 0) !== (d4 > 0);
}
/**
* Whether any two non-adjacent edges cross. Asked outright rather than inferred
* from ear clipping running out of ears: a self-crossing ring often still yields
* ears, and the triangulation it yields covers the wrong area in silence.
*/
function selfIntersects(ring: readonly Vec2[]): boolean {
const n = ring.length;
for (let i = 0; i < n; i++) {
for (let j = i + 2; j < n; j++) {
if (i === 0 && j === n - 1) continue; // adjacent around the wrap
if (segmentsCross(ring[i], ring[(i + 1) % n], ring[j], ring[(j + 1) % n])) return true;
}
}
return false;
}
/** Inside or ON the boundary of a counter-clockwise triangle. */
function inTriangle(p: Vec2, a: Vec2, b: Vec2, c: Vec2): boolean {
return cross(b.x - a.x, b.y - a.y, p.x - a.x, p.y - a.y) >= 0
&& cross(c.x - b.x, c.y - b.y, p.x - b.x, p.y - b.y) >= 0
&& cross(a.x - c.x, a.y - c.y, p.x - c.x, p.y - c.y) >= 0;
}
/** The ring with consecutive duplicates removed, wound counter-clockwise. */
function normalize(vertices: readonly Vec2[]): Vec2[] {
const out: Vec2[] = [];
for (const v of vertices) {
const last = out[out.length - 1];
if (last && Math.hypot(v.x - last.x, v.y - last.y) < WELD) continue;
out.push({ x: v.x, y: v.y });
}
const first = out[0];
const last = out[out.length - 1];
if (out.length > 1 && first && last && Math.hypot(first.x - last.x, first.y - last.y) < WELD) out.pop();
if (out.length >= MIN_POLYGON_VERTICES && signedArea2(out) < 0) out.reverse();
return out;
}
/**
* Triangles as index triples, or null when no ear can be found — which a simple
* ring always has, so failing means this one is not simple: it crosses itself,
* and no partition of it exists to compute.
*/
function earClip(pts: readonly Vec2[]): number[][] | null {
const live = pts.map((_, i) => i);
const out: number[][] = [];
const turnAt = (i: number): number => turn(
pts[live[(i + live.length - 1) % live.length]], pts[live[i]], pts[live[(i + 1) % live.length]]);
while (live.length > 3) {
let clipped = -1;
for (let i = 0; i < live.length; i++) {
const a = live[(i + live.length - 1) % live.length];
const b = live[i];
const c = live[(i + 1) % live.length];
if (turn(pts[a], pts[b], pts[c]) <= 0) continue;
let blocked = false;
for (let j = 0; j < live.length && !blocked; j++) {
const k = live[j];
if (k === a || k === b || k === c) continue;
// Only a REFLEX vertex can invalidate an ear, and touching the
// triangle invalidates it as surely as sitting inside: a cut that
// grazes the boundary leaves a remainder with no ear at all.
if (turnAt(j) > 0) continue;
if (inTriangle(pts[k], pts[a], pts[b], pts[c])) blocked = true;
}
if (blocked) continue;
out.push([a, b, c]);
clipped = i;
break;
}
if (clipped < 0) return null;
live.splice(clipped, 1);
}
out.push([live[0], live[1], live[2]]);
return out;
}
/** Two pieces joined along the edge they share, with that edge's own endpoints. */
interface Join {
ring: number[];
u: number;
v: number;
}
/** The two pieces joined along the edge they share, or null when they share none. */
function joined(a: readonly number[], b: readonly number[]): Join | null {
for (let i = 0; i < a.length; i++) {
const u = a[i];
const v = a[(i + 1) % a.length];
for (let j = 0; j < b.length; j++) {
// A consistently wound partition traverses a shared edge in opposite
// directions, which is what makes the walk below close.
if (b[j] !== v || b[(j + 1) % b.length] !== u) continue;
const ring: number[] = [];
for (let k = 0; k < a.length - 1; k++) ring.push(a[(i + 1 + k) % a.length]);
for (let k = 0; k < b.length - 1; k++) ring.push(b[(j + 1 + k) % b.length]);
return { ring, u, v };
}
}
return null;
}
/**
* Merge neighbours back while each result stays convex and within the cap,
* longest shared edge first. The candidate is tested for convexity outright
* rather than at the two joints the merge creates: on a polygon capped at eight
* vertices that walk is cheaper than being clever, and cannot mistake a winding.
*/
function mergePieces(pts: readonly Vec2[], pieces: number[][]): number[][] {
const key = (u: number, v: number): number => u * pts.length + v;
for (;;) {
// Who owns each directed edge, so candidates come from adjacency rather
// than from every pair: a hundred-point ring starts as ninety-eight
// triangles, and all-pairs-every-round costs milliseconds.
const owner = new Map<number, number>();
for (let i = 0; i < pieces.length; i++) {
const ring = pieces[i];
for (let k = 0; k < ring.length; k++) owner.set(key(ring[k], ring[(k + 1) % ring.length]), i);
}
let best = -1;
let bestA = -1;
let bestB = -1;
let bestRing: number[] | null = null;
for (let i = 0; i < pieces.length; i++) {
const ring = pieces[i];
for (let k = 0; k < ring.length; k++) {
const j = owner.get(key(ring[(k + 1) % ring.length], ring[k]));
// `j > i` takes each neighbouring pair once: the shared edge is
// reachable from both of its sides.
if (j === undefined || j <= i) continue;
if (ring.length + pieces[j].length - 2 > MAX_POLYGON_VERTICES) continue;
const join = joined(ring, pieces[j]);
if (!join || !isConvex(join.ring.map((n) => pts[n]))) continue;
// What the merge buys: the shared edge stops being a wall between
// two shapes. The longest one is the most wall removed.
const u = pts[join.u];
const v = pts[join.v];
const value = (u.x - v.x) ** 2 + (u.y - v.y) ** 2;
if (value <= best) continue;
best = value;
bestA = i;
bestB = j;
bestRing = join.ring;
}
}
if (!bestRing) return pieces;
pieces.splice(bestB, 1);
pieces[bestA] = bestRing;
}
}
/** What a collider ring collides as, once Box2D's two constraints are applied.
* Shared with every caller that asks about the same ring, so treat it as frozen. */
export interface PolygonDecomposition {
/** Convex pieces, each counter-clockwise and within the solver's vertex cap. */
readonly pieces: readonly Vec2[][];
/** The ring crosses itself, so no partition of it exists: `pieces` is the
* convex hull, which is what the solver falls back to. */
degenerate: boolean;
}
/**
* One answer per vertex array: the gizmo asks about the same ring every frame,
* and a hundred-vertex one measures milliseconds to partition. The key is the
* ARRAY, so an edit writes a new one and misses — while a mutation in place hits
* a stale entry, as does the solver, whose shapes that same flag rebuilds.
*/
const memo = new WeakMap<object, PolygonDecomposition>();
/**
* The convex pieces `vertices` collides as. A ring already convex and within the
* cap is ONE piece and the same points, so the common shape costs nothing and
* keeps the identity an author drew.
*/
export function decomposePolygon2D(vertices: readonly Vec2[]): PolygonDecomposition {
const hit = memo.get(vertices);
if (hit) return hit;
const out = partition(vertices);
memo.set(vertices, out);
return out;
}
function partition(vertices: readonly Vec2[]): PolygonDecomposition {
const ring = normalize(vertices);
if (ring.length < MIN_POLYGON_VERTICES) return { pieces: [], degenerate: false };
// Crossing is asked FIRST. A symmetric bow tie encloses zero net area, so the
// area gate below would call it nothing at all — and "you crossed your own
// outline" is both the truer answer and the one an author can act on.
if (selfIntersects(ring)) return { pieces: [computePolygonHull(ring)], degenerate: true };
// Asked of the WHOLE ring. The hull models what b2ComputeHull does to an array,
// and that keeps only the first eight points — so as a shape gate it judges a
// long ring by eight of them, and loses the collider when those are collinear.
if (!hasArea(ring)) return { pieces: [], degenerate: false };
// Only now: a star traced as one stroke has no right turn either, so this test
// is a claim about convexity only once crossing has been ruled out. Normalizing
// already welded to Box2D's radius, so the points stay the ones an author placed.
if (ring.length <= MAX_POLYGON_VERTICES && isConvex(ring)) {
return { pieces: [ring], degenerate: false };
}
const triangles = earClip(ring);
if (!triangles) return { pieces: [computePolygonHull(ring)], degenerate: true };
// Each piece is finally what Box2D would make of it, so a sliver the solver
// refuses is dropped where it can be seen rather than at shape creation.
const pieces = mergePieces(ring, triangles)
.map((indices) => computePolygonHull(indices.map((k) => ring[k])))
.filter((piece) => piece.length >= MIN_POLYGON_VERTICES);
return { pieces, degenerate: false };
}