How TurboWarp's Box2D polygon mode traces a costume

A walkthrough of the five-stage pipeline that turns a sprite's opaque region into a small set of convex Box2D fixtures, as implemented in TurboWarp/extensions PR #2490.

The pipeline runs once per sprite when physics is enabled — not per frame — and reconstructs collision geometry purely from the skin's "is this pixel opaque?" predicate, with no dependency on SVG path data. That makes it work for both vector and bitmap costumes.

The pipeline at a glance

1. Sample the silhouette into a binary grid

The PR uses isTouchingLinear — the same 2×2 anti-aliased opacity test that scratch-render uses for its own convex hull _getConvexHullPointsForDrawable — so the traced silhouette lines up exactly with what "this costume" mode would produce as its convex-hull boundary.

The grid resolution scales with costume size: roughly costume_size / 4 per axis, clamped to [16, 96]. For this cat (size ≈ 95×100) the formula gives 24×25 interior cells, plus a 1-cell transparent padding border on every side — that's the dashed outer ring below. The padding guarantees every contour is a closed loop strictly inside the grid, so marching squares needs no boundary special-casing. The result: 286 opaque cells out of 600 sampled.

Notice the lone amber cell upper-right of the head — that's a single sample-pixel speckle (probably a whisker tip). Marching squares dutifully traces it as a 4-vertex loop with signed area 0.5 cells², but it's below the _POLY_MIN_AREA = 2.0 threshold so _polyGroupContours drops it as noise.

2. Marching squares + 3. RDP simplification

Marching squares walks every 2×2 block of grid cells, indexes a 16-entry case table (with the saddle cases 5 and 10 emitting two segments each), and chains segments end-to-end into closed loops via a doubled-half-integer lookup map. That gives one big 150-vertex outer contour (the light purple outline below).

The Ramer-Douglas-Peucker simplification then collapses any vertex within _POLY_RDP_EPSILON = 0.75 cells of a kept edge. Because RDP wants an open polyline, the closed ring is split at two well-separated anchor points (the vertex farthest from loop[0], then the vertex farthest from *that*) before recursing on each half. The result: 33 corners (dark purple, with vertex markers).

4. Earcut + 5. Hertel-Mehlhorn convex merge

The outline now has 33 corners — enough to capture the ears, leg notches, and tail point without staircase noise. Earcut triangulates the simple polygon (no holes here, since the cat's body is fully opaque) into 31 triangles.

Then Hertel-Mehlhorn sweeps through triangle pairs that share an edge, greedily merging any union that stays convex and within the 8-vertex cap (_POLY_MAX_VERTS = 8, which matches Box2D's b2PolygonShape limit), until nothing more can be merged. The 31 triangles collapse to 15 convex pieces — each becomes one b2PolygonShape fixture attached to the sprite's body.

The big teal piece on the right covers most of the body — it absorbed eight earcut triangles into one fat 8-vertex polygon (exactly the _POLY_MAX_VERTS limit, so the merge stopped there). Smaller pieces fill the limbs, ears, and tail tip where reflex corners stop further merging. All 15 pieces land below the _POLY_MAX_FIXTURES = 32 cap, so polygon mode is accepted; otherwise the algorithm would fall back to the existing convex hull.

What this means in practice

Every concave notch the costume has — the gap between the ears, the V between the legs, the curve under the chin — is now real physics geometry. Drop two cats on top of each other in polygon mode and an ear can rest in the notch between the other cat's ears. In "this costume" mode (convex hull), that whole concave region was filled in and they'd just bounce off each other's bounding outlines.

Constants reference