Collider Generator

ColliderGen is a small .NET tool and library that turns a sprite into a convex-hull collider. It reads the alpha channel, wraps the solid pixels in a convex polygon, and simplifies it to at most 16 vertices. It came about while I was working on my 2D shmup, which until then had only supported colliders based on circles and AABBs. I wanted more suitable colliders for more complex sprites.

How It Works

All sprites go through the same four steps. A still sprite is one frame, an animation strip is several, and each frame is processed on its own. Each step is a small class in the library, so each can be tested on its own.

1. Slice and Mask

The tool works on one frame at a time. A still sprite is just one frame. A horizontal animation strip is first cut into equal-width frames (see Frames and Origin), and each frame is processed separately. For each frame, the tool reads only the alpha byte of every pixel and keeps a boolean grid. A pixel is solid if its alpha is at or above the threshold (the default is 128). Otherwise, it is empty.

The threshold determines how soft edges are handled. Anti-aliased borders, glows, and drop shadows have partial alpha, and a hitbox usually should not include them. A pixel that is half-transparent doesn’t count.

2. Find Each Row’s Outer Pixels

A convex hull only cares about the outermost points, so the tool doesn’t look at the inside of the sprite at all. For each row of the alpha mask, it walks in from the left edge to the first solid pixel and in from the right edge to the last one. The area between the two pixels is ignored.

From each row, 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). The top corners of each row are lined up with the bottom corners of the row above. If two points share a y, only the outer one is kept. This means that each side ends up with at most one point for every pixel edge line.

That’s all the hull needs. Every other corner in a row is on the straight line between that row’s outermost left and right corners. A convex hull contains every straight line between two of its points. The corners can’t stick out, and you can’t change the hull by leaving them out. For a frame that is h pixels tall, the input to the next step goes from four corners per solid pixel to at most h + 1 points per side. The lists are also in order from top to bottom because the rows were read from top to bottom.

Each row with a solid pixel is included, even if they are not connected. A part of a sprite that is not attached to anything, like a booster that floats next to the ship, lands inside the same hull. Even a small bit of noise can make the hull bigger than it was planned. If that happens, either raise the alpha threshold or clean up the sprite.

3. Wrap It in a Convex Hull

The boundary points use a version of Andrew’s monotone-chain algorithm. Using pixel corners instead of pixel coordinates makes a difference: a hull through pixel coordinates would stop one pixel short of the sprite’s right and bottom edges, while a hull through the corners reaches the real outer edges of the sprite.

The standard monotone-chain algorithm sorts the points along one axis (usually x) and builds the hull as two chains, one on each side of the sweep. Any axis works. Here the row scan already yields points ordered by y, split into a left list and a right list, so the sort is skipped and the two chains are the left and right sides of the hull.

The tool makes one pass down each list, keeping a stack of chain points. Whenever a new point makes the chain turn inward (or not turn at all), the last point is popped. This repeats until the turn is outward. Then the new point is pushed. Points that are next to each other are removed in the same way. This leaves only the corners that are at the true corners. The right chain and the reversed left chain then connect into one ring, starting at the leftmost, topmost vertex. Each point is pushed and popped at most once, so the hull takes time linear in the frame’s height. A simple rectangle sprite has four vertices.

4. Simplify

Simplification removes vertices one at a time, cheapest first, in two phases. First, it removes them while the cost is at or below epsilon. This cleans up the near-collinear points. After that, removal continues only when the vertex count is above the maximum (default: 16). It never has fewer than three vertices. The default epsilon of 0 only affects the cap. If you set the cap to 0, the hull will be exactly as it was built in step 3. The two removal modes are different.

Inner Fit (Default)

Inner fit is Visvalingam-Whyatt simplification. It calculates a score for each vertex based on the area of the triangle it forms with its two neighbors. A vertex with a tiny triangle sits on a nearly straight stretch and doesn’t add much to the shape. The vertex with the smallest triangle is removed first. Then, the areas of its two neighbors are recomputed. This process is repeated.

The hull is convex, which means that when you drop a vertex, you always cut a corner off inward. The collider can be a little smaller than the sprite, but not bigger. That suits hitboxes: a bullet that only grazes an outer pixel can miss.

Outer Fit

The outer fit works in the opposite way. It removes the edges instead of the vertices. For every edge, it extends the two neighboring sides until they meet. If you replace the edge’s two endpoints with that intersection, you’ll remove one vertex and add a small triangle of area outside the hull. That area is the cost. The cheapest edge is collapsed first. Then, its neighbors are measured again, and the process is repeated.

Each step adds to the polygon, so the result always includes every solid pixel. This is great for walls and other solid objects. The corners of the frame can end up outside it. In the diagram, the third collapse puts the new vertex at y = -1. Two sides that are parallel will never meet, so their edge cannot be collapsed. The choice of edge is greedy rather than the smallest possible enclosing polygon, so a round sprite can come out somewhat uneven at low caps.

The 16-vertex limit applies to both fits. It exists so a consumer can keep a hull in a fixed-size buffer.

Frames and Origin

A still sprite is just one frame and gets one hull. An animation strip is divided into equal-width frames before any of the above processes are run. Each frame is given its own hull. If you don’t set a frame width, a sprite that is an exact multiple of its height (and larger than it) is read as a strip of square frames. Anything else is a single frame, and you can set a frame width to cover other layouts. If a sprite is a certain number of pixels wide and a certain number of pixels tall, like 64×32, it will be read as a strip. So, set the frame width to the sprite’s full width. The width must divide the image evenly; otherwise, the tool won’t guess.

Hull vertices are written relative to the frame’s origin. The origin is the center by default, or the top-left corner. Coordinates are specific to a frame. So, the third frame of a strip has the same coordinate system as the first frame. This means that an engine can swap hulls without any math to find the offset. If the frame doesn’t have any solid pixels, the hull won’t have any vertices.

Command Line

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

Output

One entry per frame, each an ordered list of frame-local pixel coordinates:

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

Library

The library takes raw RGBA bytes and does no image decoding, so it has no dependency on any engine or image package. This example decodes 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

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