This is a small post about the algorithm I wrote for the recent pixel font tool to establish paths of shapes and holes on the image.
The task
The input is a grid of booleans representing state (filled / not filled) of each pixel in source image.
The output is an array of contours describing the shapes on the image. Each contour has an array of points, and array of holes in it, each of which also has an array of points describing it.
The output then can be fed to a polygon triangulation algorithm to generate geometry, or just written as-is in case of TTF format.
Also we very specifically do NOT want this:
because that counts as a self-intersecting path and can be very cursed.
Implementation
It goes like this:
1. Populate a temporary numeric grid with two special values representing whether a grid cell is empty or filled.
For my purposes I found use of min/max values for grid's value types to be good enough.
2. Establish the "outer" space by walking along the grid edges and running 8-directional flood fill starting from cells that hold the special "empty" value:
Here I used index 0 for outer space for convenience.
Given this sample, flood fill would run exactly once
(as no areas are isolated by filled cells touching the grid edges)
3. Figure out unique "islands" of connected pixels by walking over the grid and doing a 4-directional flood fill with an incremental index starting from any cell that holds the special "filled" value:
As you can see, the I/O/B/8 main shapes get indexes 1, 2, 3, and 4, and the two detached grid cells on B's right edge get indexes 5 and 6 as we iterate over them afterwards. Storing the coordinates of each shape's first encountered (top-left) cell here will also prove handy later.
4. Do the same thing for holes inside the shapes, which by now are the only cells to still hold the special "empty" value:
So O's hole gets index -1 while 8's holes get indexes -2 and -3.
Similarly, storing coordinates of each hole's top-left cell will be useful soon;
If you need to associate holes with their surrounding shapes, this is where you do that
- since a hole is by definition in the middle of the shape, a cell to the left or top
of a hole's top-left corner is warranted to be a shape cell.
5. Finally, with every shape and hole established, we can go over them to actually produce an outline, starting with (previously recorded) top-left corner and moving down (CCW):
The logic for this part is dead simple - so simple that it can be put into a small image:
That is:
- If there's a wall ahead on the left and no wall blocking the path, move forward one cell (1).
- If there's a wall ahead on the left and a wall blocking the path, add a point and turn right (2).
- Otherwise add a point and turn left (3).
This also covers the corner-touching case (4).
For holes, we simply invert the rule for what counts as wall.
And that's it!
The code
If you came here hoping to peek at a reference implementation, there's that too (in Haxe):
import haxe.ds.Vector;
class Contour {
public var col:Int;
public var row:Int;
public var shape:Polygon = new Polygon();
public var holes:Array<Polygon> = [];
public function new() { }
private static var grid:Vector<Vector<Int>>;
private static var width:Int;
private static var height:Int;
private static var result:Array<Contour>;
static function buildPoly(poly:Polygon, colStart:Int, rowStart:Int, z:Bool) {
var points = poly.points;
var dir = 3; // ENWS
var col = colStart, row = rowStart, dirStart = dir;
inline function add(x:Int, y:Int):Void {
points.push(new Point(x, y));
}
var w = width, h = height, grid = Contour.grid;
add(col, row);
var steps = 0;
while (steps == 0 || (col != colStart || row != rowStart || dir != dirStart)) {
switch (dir) {
case 0: { // right (BR corner)
if ((col + 1 < w && grid[row][col + 1] > 0) == z) {
if ((row + 1 < h && grid[row + 1][col + 1] > 0) == z) {
add(col + 1, row + 1);
dir = 3;
}
col += 1;
} else {
add(col + 1, row + 1);
dir = 1;
}
};
case 1: { // up (TR corner)
if ((row > 0 && grid[row - 1][col] > 0) == z) {
if ((col + 1 < w && grid[row - 1][col + 1] > 0) == z) {
add(col + 1, row);
dir = 0;
}
row -= 1;
} else {
add(col + 1, row);
dir = 2;
}
};
case 2: { // left (TL corner)
if ((col > 0 && grid[row][col - 1] > 0) == z) {
if ((row > 0 && grid[row - 1][col - 1] > 0) == z) {
add(col, row);
dir = 1;
}
col -= 1;
} else {
add(col, row);
dir = 3;
}
};
case 3: { // down (BL corner)
if ((row + 1 < h && grid[row + 1][col] > 0) == z) {
if ((col > 0 && grid[row + 1][col - 1] > 0) == z) {
add(col, row + 1);
dir = 2;
}
row += 1;
} else {
add(col, row + 1);
dir = 0;
}
};
default: break;
}
steps += 1;
}
}
public static inline var defaultEmpty = -0x7FffFFff;
public static inline var defaultSolid = 0x7FffFFff;
static function floodFill(col:Int, row:Int, val:Int, is8dir:Bool = false) {
var grid = Contour.grid;
var w = Contour.width;
var h = Contour.height;
var ref = grid[row][col];
//
grid[row][col] = val;
var queue = [];
inline function add(_col:Int, _row:Int):Void {
queue.push(_row);
queue.push(_col);
}
add(col, row);
while (queue.length > 0) {
row = queue.shift();
col = queue.shift();
if (col > 0) {
if (grid[row][col - 1] == ref) {
grid[row][col - 1] = val;
add(col - 1, row);
}
}
if (col + 1 < w) {
if (grid[row][col + 1] == ref) {
grid[row][col + 1] = val;
add(col + 1, row);
}
}
if (row > 0) {
if (grid[row - 1][col] == ref) {
grid[row - 1][col] = val;
add(col, row - 1);
}
}
if (row + 1 < h) {
if (grid[row + 1][col] == ref) {
grid[row + 1][col] = val;
add(col, row + 1);
}
}
if (!is8dir) continue;
if (col > 0 && row > 0) {
if (grid[row - 1][col - 1] == ref) {
grid[row - 1][col - 1] = val;
add(col - 1, row - 1);
}
}
if (col + 1 < w && row > 0) {
if (grid[row - 1][col + 1] == ref) {
grid[row - 1][col + 1] = val;
add(col + 1, row - 1);
}
}
if (col > 0 && row + 1 < h) {
if (grid[row + 1][col - 1] == ref) {
grid[row + 1][col - 1] = val;
add(col - 1, row + 1);
}
}
if (col + 1 < w && row + 1 < h) {
if (grid[row + 1][col + 1] == ref) {
grid[row + 1][col + 1] = val;
add(col + 1, row + 1);
}
}
}
}
public static function build(input:Vector<Vector<Bool>>):Array<Contour> {
var h = input.length;
if (h == 0) return [];
var w = input[0].length;
if (w == 0) return [];
height = h;
width = w;
// create an temp grid:
var grid = new Vector(h);
for (row in 0 ... h) {
var inRow = input[row];
var outRow = new Vector(w);
for (col in 0 ... w) outRow[col] = inRow[col] ? defaultSolid : defaultEmpty;
grid[row] = outRow;
}
Contour.grid = grid;
// fill boundaries:
for (row in 0 ... h) {
if (grid[row][0] == defaultEmpty) floodFill(0, row, 0, true);
if (grid[row][w - 1] == defaultEmpty) floodFill(w - 1, row, 0, true);
}
for (col in 0 ... w) {
if (grid[0][col] == defaultEmpty) floodFill(col, 0, 0, true);
if (grid[h - 1][col] == defaultEmpty) floodFill(col, h - 1, 0, true);
}
// mark shapes:
var ctrs = [];
Contour.result = ctrs;
var solidID = 0;
for (row in 0 ... height) {
for (col in 0 ... width) {
var val = grid[row][col];
if (val == defaultSolid) {
floodFill(col, row, ++solidID);
var ctr = new Contour();
ctr.col = col;
ctr.row = row;
ctrs.push(ctr);
}
}
}
// mark holes:
var emptyID = 0;
for (row in 0 ... height) {
for (col in 0 ... width) {
var val = grid[row][col];
if (val == defaultEmpty) {
floodFill(col, row, --emptyID);
var adj = grid[row - 1][col];
var poly = new Polygon();
buildPoly(poly, col, row, false);
result[adj - 1].holes.push(poly);
}
}
}
// build contours:
for (ctr in ctrs) {
buildPoly(ctr.shape, ctr.col, ctr.row, true);
}
//
Contour.result = null;
return ctrs;
}
}
class Polygon {
public var points:Array<Point> = [];
public function new() { }
}
class Point {
public var x:Int;
public var y:Int;
public function new(x:Int, y:Int) {
this.x = x;
this.y = y;
}
public function toString() {
return '($x, $y)';
}
}
Closing notes
- If the cells are warranted to not touch grid borders, you can skip the along-the-grid-border loop in step 2.
- If the grid is warranted to only contain a single shape without holes, you could skip straight to step 5 by looping from top-left until you find the first pixel of the shape and then starting traversal.
- For use cases where performance is important or garbage collection is expensive, resizing the same grid (to be large enough to fit new data) can be better than creating a new one.
Have fun!