Tracing images to create Box2D objects - part 2

Now that we have our outline we need to find a way of reducing the number of points whilst keeping the path accurate to the outline of the shape.

To do this we want the number of points to be dependent on the curvature of the path. Points of greater curvature need to have more points and sections which are "straighter" need to have fewer points. This can be done by measuring the curvature of the line - when the line has a greater curvature we add more points. One difficulty is that because the line follows every pixel it's has lots of small duration high curvature sections. We need some way to average the curvature. As yet I've not found a perfect solution but I've written an algorithm which seems to do a job which is good enough.

Algorithm 1

Average the points

To get rid of local areas high curvatures we need to average the points. The average can be found by adding the coordinates of a number of points and then dividing by the number of points.

The slight problem with this is that the new line will diverge slightly from the old line due to the nature of averaging. The averaging function just loops over the points and computes a new average point based on a number of points.

  1. private Vertex average (ArrayList<Vertex> vertices) {
  2. Vertex average = new Vertex(0,0);
  3. for(Vertex v: vertices) {
  4. average = average.add(v);
  5. }
  6. average.set(average.x / vertices.size(), average.y / vertices.size());
  7. return average;
  8. }

Here we can see a comparison before and after smoothing:

This smoothing was achieved by averaging over 4 points.

Remove points based on line curvature

The final step to simplify the shape is to remove points based on the lines curvature. Curvature is the amount a line changes it's direction in a given space. A useful analogy can be made with driving a car around a corner. A tight corner requires that the car changes it's direction abruptly - hence you have to slow down, whereas a more gentil corner changes it's direction at a lower rate.

Curvature can be determined by looking at three points:

  1. private float curvature (Vertex v1, Vertex v2, Vertex v3) {
  2. Vertex midPoint = midPoint(v1, v3);
  3. return sq(midPoint.x - v2.x) + sq(midPoint.y - v2.y);
  4. }

This function takes three vertices, it finds the midpoint between the first and last vertex and then looks at the distance between this new point and the middle vertex. If this distance is great then there is a high curvature, if it's small then there's a small curvature.

The following algorithm uses the curvature of the smoothed line to determine when to remove points. If the curvature is high then more points are included, if it's small fewer points are included.

  1. public ArrayList<Vertex> simplify3 (float lim, int average) {
  2. ArrayList<Vertex> smoothedLine = new ArrayList<Vertex> ();
  3. ArrayList<Vertex> simplifiedLine = new ArrayList<Vertex> ();
  4.  
  5. // Add the first point
  6. smoothedLine.add(points.get(0));
  7.  
  8. ArrayList<Vertex> averageVertices = new ArrayList<Vertex>();
  9.  
  10. // Loop over the next [average] vertices and
  11. // add the result to the array of smoothed points
  12. for(int i=0; i<points.size()-average; i++) {
  13.  
  14. averageVertices.clear();
  15. for(int j=0; j<average; j++) {
  16. averageVertices.add(points.get(i+j));
  17. }
  18. smoothedLine.add(average(averageVertices));
  19. }
  20.  
  21. float curvatureTotal = 0;
  22. float curvature = 0;
  23.  
  24. for(int i=0; i<smoothedLine.size()-3; i++) {
  25. // Calculate the curvature
  26. curvature = curvature(smoothedLine.get(i), smoothedLine.get(i+1), smoothedLine.get(i+2));
  27.  
  28. // Use a curvature accumulator to prevent cases
  29. // where a line curves gradually - this would be
  30. // be picked up if we just used the curvature because
  31. // each individual curvature may be less than our limit
  32. curvatureTotal += curvature;
  33.  
  34. // If the total curvature is greater than our set
  35. // limit then add the point to our simplified line
  36. if(curvatureTotal > lim ) {
  37. curvatureTotal = 0;
  38. simplifiedLine.add(smoothedLine.get(i));
  39. }
  40. }
  41. return simplifiedLine;
  42. }

I think the comments for this function make it pretty straightforward to understand. This algorithm allows us to both smooth the line and reduce the number of points. Below are a number of examples with different levels of smoothing:

This uses a curvature limit of 0.2 and averages over 2 points.

This uses a curvature limit of 0.07 and averages over 3 points.

This uses a curvature limit of 0.1 and averages over 4 points.

As you can see it's possible to get different levels of accuracy by using different parameters. The results aren't perfect but I've found them to be good enough to use in my games especially mobile games where because of the small screen you don't notice if the collisions are a couple of pixels out.

I'm including a link to the complete source code here if you want to compile the code you'll also need to download this bundle. You're welcome to use the code in your own projects but I would appreciate if if you could include a reference to my blog.

I'm writing a small java application to convert images to box2d paths so I'll update the post when it's complete. If you come up with any improvements to my algorithm or have solved this problem a different way I'd be very interested in hearing about it.

Tweet: 

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.