Collider Generator

ColliderGen is a small .NET tool and library that builds a convex-hull collider from a sprite. It reads the alpha channel, wraps the solid pixels in a convex polygon, and simplifies the polygon to at most 16 vertices. I wrote it for my 2D shmup , which only had circle and AABB colliders before.

The devlog post Collisions, Part Trois covers the collision tests that use the hulls.

How It Works

Every frame goes through four steps. A still sprite is one frame. An animation strip is several frames, and each frame is processed on its own. Each step is a small class in the library and is tested on its own.

1. Slice and Mask

A horizontal animation strip is first cut into frames of equal width (see Frames and Origin ). For each frame, the tool reads only the alpha value of every pixel. A pixel is solid if its alpha is at or above the threshold (default 128), otherwise it is empty. The result is a grid of true/false values.

The threshold decides what happens to soft edges. Anti-aliased borders, glows and drop shadows are partly transparent, and a hitbox usually shouldn’t include them. With the default threshold, a pixel that is more than half transparent doesn’t count.

2. Find Each Row’s Outer Pixels

A convex hull only depends on the outermost points, so the tool ignores the inside of the sprite. In each row, it finds the first solid pixel from the left and the last solid pixel from the right.

It keeps the outer corners of those two pixels: the left pixel’s two left corners, (x, y) and (x, y + 1), and the right pixel’s two right corners, (x + 1, y) and (x + 1, y + 1). A row’s top corners lie on the same line as the bottom corners of the row above. When two points on the same side share a y, only the outer one is kept. So each side has at most one point per horizontal pixel edge.

That’s all the hull needs. Every other corner in a row lies between that row’s outermost left and right corners. A convex hull contains the straight line between any two of its points, so leaving those corners out doesn’t change the hull. For a frame that is h pixels tall, the next step gets at most h + 1 points per side instead of four corners per solid pixel. The points are already sorted from top to bottom, because the rows were read in that order.

Every row with a solid pixel counts, even if the pixels aren’t connected. A detached part of a sprite, like a booster floating next to a ship, ends up inside the same hull. So does a stray pixel of noise, which can make the hull much bigger. If that happens, raise the alpha threshold or clean up the sprite.

3. Wrap It in a Convex Hull

The hull is built with a variant of Andrew’s monotone chain algorithm . Using pixel corners instead of pixel coordinates matters: a hull through pixel coordinates would stop one pixel short of the sprite’s right and bottom edges. A hull through the corners reaches the sprite’s real outer edges.

The standard algorithm sorts the points along one axis (usually x) and builds the hull as two chains, one per side. Here the row scan already delivers the points sorted by y, in a left list and a right list. So there is no sort, and the two chains are the left and right sides of the hull.

The tool goes through each list once and keeps the chain on a stack. If a new point makes the chain turn inward, or go straight on, the last point is removed. This repeats until the chain turns outward, then the new point is added. That also removes points in the middle of straight edges, so only real corners remain. The right chain and the reversed left chain are then joined into one ring that starts at the leftmost, topmost vertex. Each point is added and removed at most once, so the time is linear in the frame’s height. A rectangular sprite gets four vertices.

4. Simplify

Simplification removes vertices one at a time, cheapest first. As long as the cheapest removal costs no more than epsilon, it is removed. This cleans up almost-straight stretches. After that, vertices are only removed while there are more than the maximum (default 16). A hull never gets fewer than three vertices. With the default epsilon of 0, only the maximum applies, and a hull that already fits stays exactly as built in step 3. There are two ways to remove a vertex.

Inner Fit (Default)

Inner fit is Visvalingam-Whyatt simplification . The cost of a vertex is the area of the triangle it forms with its two neighbors. A vertex with a tiny triangle sits on an almost straight stretch and adds little to the shape. The vertex with the smallest triangle is removed, its two neighbors get new costs, and this repeats.

Because the hull is convex, removing a vertex always cuts a corner off. The collider can end up slightly smaller than the sprite, never bigger. That suits hitboxes: a bullet that only grazes an outer pixel may miss.

Outer Fit

Outer fit works the other way round: it removes edges instead of vertices. For each edge, it extends the two neighboring sides until they meet. Replacing the edge’s two endpoints with that intersection removes one vertex and adds a small triangle outside the hull. The triangle’s area is the cost. The cheapest edge is collapsed, its neighbors get new costs, and this repeats.

Each step only adds area, so the result always contains every solid pixel. That suits walls and other solid objects. New vertices can end up outside the frame: in the diagram, the third collapse puts one at y = -1. Two parallel sides never meet, so the edge between them can’t be collapsed. That is why a rectangle keeps four vertices. The tool always picks the cheapest edge next, which doesn’t guarantee the smallest enclosing polygon, so a round sprite can come out a bit uneven with a low maximum.

The limit of 16 vertices applies to both fits. It lets a game keep a hull in a fixed-size buffer.

Frames and Origin

A still sprite is one frame and gets one hull. An animation strip is cut into frames of equal width before the steps above, and each frame gets its own hull. Without a frame width, an image that is wider than it is tall, and whose width is an exact multiple of its height, is read as a strip of square frames. Anything else is a single frame. Set a frame width for other layouts. This also means a single 64×32 sprite is read as two 32×32 frames, so set the frame width to 64 for it. The frame width must divide the image width exactly, otherwise the tool stops with an error.

Hull vertices are relative to the frame’s origin: its center by default, or its top-left corner. Every frame uses its own coordinates, so the third frame of a strip uses the same coordinate system as the first. A game can switch between hulls without computing an offset. A frame without solid pixels gets a hull with no vertices.

Command Line

collidergen <sprite.png> [options]
collidergen --all <directory> [options]

Output

One entry per frame, each a list of vertices in frame coordinates, in order:

{
  "Frames": [
    { "Vertices": [ { "X": -18, "Y": -18 }, { "X": 17, "Y": -18 }, { "X": 0, "Y": 17 } ] }
  ]
}

Library

The library takes raw RGBA bytes and doesn’t decode images, so it doesn’t depend on any engine or image package. This example decodes the image with StbImageSharp :

using System.Numerics;
using ColliderGen;
using StbImageSharp;

using var stream = File.OpenRead("sprites/ship.png");
ImageResult image = ImageResult.FromStream(stream, ColorComponents.RedGreenBlueAlpha);

SpriteCollider collider = SpriteColliderGenerator.Generate(
    new SpriteImage(image.Data, image.Width, image.Height),
    new ColliderOptions {
        AlphaThreshold = 128, Epsilon = 0f, MaxVertices = 16, Origin = ColliderOrigin.Center, Fit = ColliderFit.Inner
    });

IReadOnlyList<Vector2> firstFrame = collider.Frames[0];

Tech Stack

• Language: C# 14
• Framework: .NET 10
• Libraries: StbImageSharp, StbImageWriteSharp (CLI only, the core library has no dependencies)
• Build Tool: .NET SDK (dotnet CLI), packaged as a .NET tool
• Testing: NUnit 5, Moq, coverlet
• Other Tools / Services: GitHub Actions, Dependabot

Links

• Source: GitHub
• Devlog: Collisions, Part Trois

Resources

• https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
• https://en.wikipedia.org/wiki/Visvalingam%E2%80%93Whyatt_algorithm
• https://github.com/StbSharp/StbImageSharp
• https://github.com/shendriks/collidergen