Tracing images to create Box2D objects - part 1
Today I was looking at the forums and I noticed that there was a level creator for Box2D which had a feature which allowed image files to be converted onto Box2D objects. This program traced around the edge of the image and then output a series of points which could be used to create the Box2D shape. I've written a series of tutorials on how to create Box2D objects using Inkscape SVG images but when you have a sprite and just want to convert it straight to Box2D this technique looks easier. I decided to see if I could write my own script to do this.
My first thought was that it made sense to use the image's alpha channel to determine the outline. Then it was necessary to scan the pixels in the image and determine which ones constituted the outer edge. Finally it was necessary to reduce the number of edge points (for even a fairly small image there could be over 1000 points) whilst not losing the characteristic of the shape.
Finding a boundary point
Finding which points are on the outline of the shape is fairly easy. Any boundary point will have an alpha value greater than zero and at least one neighbor with an alpha value of zero. Here's my "find boundary point" function:
/* * Helper function to determine the alpha value of a pixel on the image where the variable img is a BufferedImage */ public boolean hasAlpha (int x, int y) { if((img.getRGB(x, y) >>> 24)>0) return true; return false; } /* * Test a point to see if the alpha is greater than 0. If the point falls outside the image return false for no alpha. */ public boolean pointHasAlpha (int x, int y) { if(x<0||x>(img.getWidth()-1)||y<0||y>(img.getHeight()-1)) { return false; } else { if(hasAlpha(x,y)) return true; else return false; } } /* * Test to see if a pixel on the image is a boundary pixel. */ public boolean isBoundary (int x, int y) { // If this point doesn't have alpha we're not interested if(!pointHasAlpha(x,y)) return false; // Look at the 8 adjoining points, if at least one has alpha then // it's a boundary for(int i=-1; i<2; i++) { for(int j=-1; j<2; j++) { if(!pointHasAlpha(x+i, y+j)) return true; } } // If this point has alpha and all of the adjoining points // have alpha then it's not a boundary return false; }
My first attempt algorithm just scanned the whole image and identified all the boundary points. There were several problems with this approach. The first being that it's horribly inefficient. The time taken would grow linearly with the canvas area regardless of how much space the actual image took up. The second problem is that the points zigzag as the program traces vertical lines across the image. After some thought I found that it's actually quite difficult to get the points in the correct order.
My second attempt turned out to be much more successful. This algorithm used the first algorithm to identify the first point on the shapes outline. After that a different algorithm kicked in. It follows that any point on the shape's outline will have a neighbor which also sits on the shape's outline. This algorithm looked at the adjoining points of the pixel in turn to find out which of them was another boundary pixel. When it found one the process was repeated on the new pixel. This meant that the algorithm could zip directly around the shape and collect all the boundary pixel in the correct order. The advantage of this is that the length of time it takes is only dependent on the size of the shape.
// function which loops over the image file until it identifies the first boundary pixel public int loopOverImage () { if(img!=null) { // Loop until we find a boundary pixel for (int cx=0;cx<img.getWidth();cx++) { for (int cy=0;cy<img.getHeight();cy++) { if(isBoundary(cx, cy)) { traverseBoundary(cx, cy); return 0; } } } } else { LogMessage.log(TAG, "loopOverImage", "image null"); } return 0; } public void traverseBoundary (int x, int y) { Pixel start = new Pixel(x,y,Pixel.WEST,Pixel.CENTRE); Pixel next = start; Pixel old = new Pixel(-1,-1); points.add(start.toVertex()); // Set arbitary limit to length of circumference for(int i=0; i<10000000; i++) { // Save off the last position old = next; // Find the next clockwise boundary pixel next = findNextBounearyPoint(next); // Set the search start point as the previous pixel // to avoid loops and continue traversing the shape // in the same direction i.e. // edge: x first point second point 34x // x 23x 2x // x 1x 1 // In this diagram the numbers represent the order // in which the neighboring points are tested. We // Always start with the previous point found. next.setNSP(old.sub(next)); // When we get back to the start break the loop if(next.equals(start)) break; points.add(next.toVertex()); } } public Pixel findNextBounearyPoint(Pixel p) { // Move clockwise around from previous point until we // hit another boundary cell for(int i=0; i<9; i++) { // Find the next pixel clockwise - the pixel remembers the last // position tested and will increment to the next position Pixel next = p.clockwise(); if(isBoundary(next)) { return next; } } LogMessage.log(TAG, "findNextBoundaryPoint", "Error next point not found"); return null; }
Firstly, we use the loopOverImage function to identify the first boundary pixel by brute force. This may not be the most efficient method but it makes up for that in robustness. Once we hit a boundary pixel the traverse boundary algorithm kicks in. This pixel looks at the neighbours of the current boundary pixel in a clockwise motion. It follows that any boundary pixel must have at least two neighbours which are boundary pixels as well. Once this algorithm finds the neighbouring boundary pixel the current pixel is saved and the process repeats. It's important that this clockwise search always starts with the last boundary pixel discovered. This is to prevent the program getting stuck in a loop. i.e.
If there are three boundary pixels a, b and c:
c
b
a
Our brute force method discovers (a) so we start scanning clockwise to find (b). Once we find (b) we again scan clockwise but we start our scanning with the location of (a) i.e. (a) is south west of (b). This means that we want to set the NSP value of (b) to SOUTH, WEST this can also be done by subtracting the next point from the old point.
The final thing of note is the clockwise function which is contained within the Pixel class:
public class Pixel { public static final int NORTH = 1; public static final int SOUTH = -1; public static final int EAST = 1; public static final int WEST = -1; public static final int CENTRE = 0; public int x; public int y; private int nspX = -1; private int nspY = 0; public Pixel(int x, int y) { this.x = x; this.y = y; } public Pixel(int x, int y, int nspX, int nspY) { this.x = x; this.y = y; this.nspX = nspX; this.nspY = nspY; } public void set(int x, int y) { this.x = x; this.y = y; } public Pixel add(Pixel p) { return new Pixel(x+p.x, y+p.y); } public Pixel sub(Pixel p) { return new Pixel(x-p.x, y-p.y); } public Vec2 toVec2 () { return new Vec2(x,y); } public Vertex toVertex () { return new Vertex(x,y); } public Pixel mult (int i) { return new Pixel(x*i, y*i); } return "x:"+x+" y:"+y; } public void setNSP (Pixel p) { nspX = p.x; nspY = p.y; } public Pixel clockwise () { Pixel nsp = clockwise(nspX, nspY); nspX = nsp.x; nspY = nsp.y; return add(nsp); } public Pixel clockwise(int x, int y) { return clockwise(new Pixel(x,y)); } public Pixel clockwise (Pixel sp) { if(sp.x==WEST) { if(sp.y==SOUTH) return new Pixel(WEST,CENTRE); else if(sp.y==CENTRE) return new Pixel(WEST,NORTH); else if(sp.y==NORTH) return new Pixel(CENTRE,NORTH); } if(sp.x==CENTRE) { if(sp.y==SOUTH) return new Pixel(WEST,SOUTH); else if(sp.y==NORTH) return new Pixel(EAST,NORTH); } if(sp.x==EAST) { if(sp.y==SOUTH) return new Pixel(CENTRE,SOUTH); else if(sp.y==CENTRE) return new Pixel(EAST,SOUTH); else if(sp.y==NORTH) return new Pixel(EAST,CENTRE); } return null; } public boolean equals (Pixel p) { if(x==p.x && y==p.y) return true; return false; } }
The Pixel class is just a container for a point with a means of finding neighbouring points. The clockwise function isn't very elegant but it's simple and it works. Depending on the current search point the function will return the next neighbouring point in a clockwise direction.
After all that we have a list of all the pixels around the border of our shape. Unfortunately this number would be too large to use in the Box2D simulation. There could easily be more than 3000 points. The next step which is the subject of my next blog post is how to reduce the number of points while still having a path which conforms to the outline of the shape.
Comments
mrsonej (not verified)
Sat, 07/14/2012 - 20:07
Permalink
Thanks!
Very simple! Thanks! Was very helpful
Add new comment