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:

  1. /*
  2. * Helper function to determine the alpha value of a pixel on the image where the variable img is a BufferedImage
  3. */
  4. public boolean hasAlpha (int x, int y) {
  5. if((img.getRGB(x, y) >>> 24)>0)
  6. return true;
  7. return false;
  8. }
  9. /*
  10. * Test a point to see if the alpha is greater than 0. If the point falls outside the image return false for no alpha.
  11. */
  12. public boolean pointHasAlpha (int x, int y) {
  13. if(x<0||x>(img.getWidth()-1)||y<0||y>(img.getHeight()-1)) {
  14. return false;
  15. } else {
  16. if(hasAlpha(x,y))
  17. return true;
  18. else
  19. return false;
  20. }
  21. }
  22.  
  23. /*
  24. * Test to see if a pixel on the image is a boundary pixel.
  25. */
  26. public boolean isBoundary (int x, int y) {
  27.  
  28. // If this point doesn't have alpha we're not interested
  29. if(!pointHasAlpha(x,y))
  30. return false;
  31.  
  32. // Look at the 8 adjoining points, if at least one has alpha then
  33. // it's a boundary
  34. for(int i=-1; i<2; i++) {
  35. for(int j=-1; j<2; j++) {
  36. if(!pointHasAlpha(x+i, y+j))
  37. return true;
  38. }
  39. }
  40.  
  41. // If this point has alpha and all of the adjoining points
  42. // have alpha then it's not a boundary
  43. return false;
  44. }

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.

  1. // function which loops over the image file until it identifies the first boundary pixel
  2. public int loopOverImage () {
  3. if(img!=null) {
  4. // Loop until we find a boundary pixel
  5. for (int cx=0;cx<img.getWidth();cx++) {
  6. for (int cy=0;cy<img.getHeight();cy++) {
  7. if(isBoundary(cx, cy)) {
  8. traverseBoundary(cx, cy);
  9. return 0;
  10. }
  11. }
  12. }
  13. } else {
  14. LogMessage.log(TAG, "loopOverImage", "image null");
  15. }
  16. return 0;
  17. }
  18.  
  19. public void traverseBoundary (int x, int y) {
  20.  
  21. Pixel start = new Pixel(x,y,Pixel.WEST,Pixel.CENTRE);
  22. Pixel next = start;
  23. Pixel old = new Pixel(-1,-1);
  24.  
  25. points.add(start.toVertex());
  26.  
  27. // Set arbitary limit to length of circumference
  28. for(int i=0; i<10000000; i++) {
  29. // Save off the last position
  30. old = next;
  31.  
  32. // Find the next clockwise boundary pixel
  33. next = findNextBounearyPoint(next);
  34.  
  35. // Set the search start point as the previous pixel
  36. // to avoid loops and continue traversing the shape
  37. // in the same direction i.e.
  38.  
  39. // edge: x first point second point 34x
  40. // x 23x 2x
  41. // x 1x 1
  42.  
  43. // In this diagram the numbers represent the order
  44. // in which the neighboring points are tested. We
  45. // Always start with the previous point found.
  46. next.setNSP(old.sub(next));
  47.  
  48. // When we get back to the start break the loop
  49. if(next.equals(start))
  50. break;
  51.  
  52. points.add(next.toVertex());
  53.  
  54. }
  55. }
  56.  
  57. public Pixel findNextBounearyPoint(Pixel p) {
  58. // Move clockwise around from previous point until we
  59. // hit another boundary cell
  60. for(int i=0; i<9; i++) {
  61. // Find the next pixel clockwise - the pixel remembers the last
  62. // position tested and will increment to the next position
  63. Pixel next = p.clockwise();
  64. if(isBoundary(next)) {
  65. return next;
  66. }
  67. }
  68. LogMessage.log(TAG, "findNextBoundaryPoint", "Error next point not found");
  69. return null;
  70. }

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:

  1. public class Pixel {
  2.  
  3. public static final int NORTH = 1;
  4. public static final int SOUTH = -1;
  5. public static final int EAST = 1;
  6. public static final int WEST = -1;
  7. public static final int CENTRE = 0;
  8.  
  9. public int x;
  10. public int y;
  11.  
  12. private int nspX = -1;
  13. private int nspY = 0;
  14.  
  15. public Pixel(int x, int y) {
  16. this.x = x;
  17. this.y = y;
  18. }
  19.  
  20. public Pixel(int x, int y, int nspX, int nspY) {
  21. this.x = x;
  22. this.y = y;
  23.  
  24. this.nspX = nspX;
  25. this.nspY = nspY;
  26. }
  27.  
  28. public void set(int x, int y) {
  29. this.x = x;
  30. this.y = y;
  31. }
  32.  
  33. public Pixel add(Pixel p) {
  34. return new Pixel(x+p.x, y+p.y);
  35. }
  36.  
  37. public Pixel sub(Pixel p) {
  38. return new Pixel(x-p.x, y-p.y);
  39. }
  40.  
  41. public Vec2 toVec2 () {
  42. return new Vec2(x,y);
  43. }
  44.  
  45. public Vertex toVertex () {
  46. return new Vertex(x,y);
  47. }
  48.  
  49. public Pixel mult (int i) {
  50. return new Pixel(x*i, y*i);
  51. }
  52.  
  53. public String toString () {
  54. return "x:"+x+" y:"+y;
  55. }
  56.  
  57. public void setNSP (Pixel p) {
  58. nspX = p.x;
  59. nspY = p.y;
  60. }
  61.  
  62. public Pixel clockwise () {
  63. Pixel nsp = clockwise(nspX, nspY);
  64. nspX = nsp.x;
  65. nspY = nsp.y;
  66. return add(nsp);
  67. }
  68.  
  69. public Pixel clockwise(int x, int y) {
  70. return clockwise(new Pixel(x,y));
  71. }
  72. public Pixel clockwise (Pixel sp) {
  73. if(sp.x==WEST) {
  74. if(sp.y==SOUTH)
  75. return new Pixel(WEST,CENTRE);
  76. else if(sp.y==CENTRE)
  77. return new Pixel(WEST,NORTH);
  78. else if(sp.y==NORTH)
  79. return new Pixel(CENTRE,NORTH);
  80. }
  81.  
  82. if(sp.x==CENTRE) {
  83. if(sp.y==SOUTH)
  84. return new Pixel(WEST,SOUTH);
  85. else if(sp.y==NORTH)
  86. return new Pixel(EAST,NORTH);
  87. }
  88.  
  89. if(sp.x==EAST) {
  90. if(sp.y==SOUTH)
  91. return new Pixel(CENTRE,SOUTH);
  92. else if(sp.y==CENTRE)
  93. return new Pixel(EAST,SOUTH);
  94. else if(sp.y==NORTH)
  95. return new Pixel(EAST,CENTRE);
  96. }
  97. return null;
  98. }
  99.  
  100. public boolean equals (Pixel p) {
  101. if(x==p.x && y==p.y)
  102. return true;
  103. return false;
  104. }
  105. }

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.

Tweet: 

Comments

Very simple! Thanks! Was very helpful

Add new comment

Filtered HTML

  • Web page addresses and e-mail addresses turn into links automatically.
  • You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>, <c>, <cpp>, <drupal5>, <drupal6>, <java>, <javascript>, <php>, <python>, <ruby>. The supported tag styles are: <foo>, [foo].
  • Allowed HTML tags: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

Plain text

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.