Creating levels in Box2D part 2 - Creating Bezier Curves in Java

In this post I'll continue my series on how create objects for Box2D using an SVG file created in a drawing program like Inkscape. In Part 1 I covered how to load the SVG file into Java. Before I explain how to extract the path data from the SVG file it's necessary to know how we are going to use this data to construct our paths. SVG paths can contain a number of different types of line: straight, quadratic bezier, cubic bezier and arc. In this tutorial I'm going to cover straight, quadratic bezier and cubic bezier lines.

A bezier curve is a curve defined by a cubic polynomial. The maths is pretty complicated but luckily it's quite easy to construct bezier curves geometrically.

Cubic bezier


A cubic bezier is a curve defined by it's start point P0, it's end point P3 and two control points. The control points P1, P2 define the gradient at the start and end of the line.

Quadratic bezier


A quadratic bezier is just a cubic bezier curve where control points P1 and P2 inhabit the same location.

Straight line

A straight line is just a cubic bezier curve where the control points P1 and P2 lie on the start and end points P0 and P3.

Constructing the line

From this analysis it can be seen that if we can draw a cubic bezier curve we can by definition use the same code to draw quadratic beziers and straight lines.

The diagram above shows how a cubic bezier curve can be constructed geometrically. We start out with a curve defined by two points and two control points P0 with control point P1 and P3 with control point (cp) P2. By performing a number of bisections we can find a new point on our line P0123. With this point we can split out bezier curve into two curves.

- Curve 1: P0 [cp: P01] -> P0123 [cp: P012]
- Curve 2: P0123 [cp: P123] -> P3 [P23]

Now we can repeat the process to find the mid point of these curves etc.. Using this technique we can find the bezier curve to any level of accuracy. To get a greater accuracy we just perform more bisections and generate more points.

The Code:

To generate this curve I use three classes:
- Vertex: this contains the position of one point
- Spline vertex: this contains three vertices - 1 point and 2 control points
- Spline: this class is responsible for generating the curve

Vertex class:

  1. public class Vertex {
  2. public final String TAG = this.getClass().getSimpleName();
  3.  
  4. public float x;
  5. public float y;
  6.  
  7. public Vertex(float x, float y) {
  8. this.x = x;
  9. this.y = y;
  10. }
  11. public Vertex(Vec2 v) {
  12. this.x = v.x;
  13. this.y = v.y;
  14. }
  15. public Vertex(double x, double y) {
  16. this.x = (float) x;
  17. this.y = (float) y;
  18. }
  19. public Vec2 toVec2() {
  20. return new Vec2(x,y);
  21. }
  22.  
  23. public Vec2 distance(Vertex v) {
  24. return new Vec2(x-v.x, y-v.y).abs();
  25. }
  26.  
  27. public String toString() {
  28. return "x:"+x+", y:"+y;
  29. }
  30.  
  31. public Vertex add(Vertex v) {
  32. return add(v.x, v.y);
  33. }
  34. public Vertex add(float x, float y) {
  35. return new Vertex(this.x+x, this.y+y);
  36. }
  37. public Vertex sub(Vertex v) {
  38. return sub(v.x, v.y);
  39. }
  40. public Vertex sub(float x, float y) {
  41. return new Vertex(this.x-x, this.y-y);
  42. }
  43.  
  44. public Vertex clone () {
  45. return new Vertex(x,y);
  46. }
  47.  
  48. public void set(float x, float y) {
  49. this.x = x;
  50. this.y = y;
  51. }
  52.  
  53. /*
  54. * Perform an affine transform on the vertex
  55. */
  56. public Vertex transform(AffineTransformation at) {
  57. Coordinate c = new Coordinate(x, y);
  58. at.transform(c, c);
  59. return new Vertex(c.x, c.y);
  60. }
  61.  
  62. public boolean equals(Vertex v) {
  63. if(x == v.x && y == v.y)
  64. return true;
  65. return false;
  66. }
  67.  
  68. }

The next class holds three vertices:

  1. public class SplineVertex {
  2.  
  3. // Path start point and control points cp1 and cp2
  4. public Vertex cp1;
  5. public Vertex p;
  6. public Vertex cp2;
  7.  
  8. /*
  9. * Create a new cubic spline
  10. */
  11. public SplineVertex(float x, float y, float x1, float y1, float x2, float y2) {
  12. construct(x,y,x1,y1,x2,y2);
  13. }
  14. public SplineVertex(Vertex p, Vertex cp1, Vertex cp2) {
  15. construct(p,cp1, cp2);
  16. }
  17.  
  18. /*
  19. * Used to represent a straight line i.e. the control points are the same as the line start and end points
  20. */
  21. public SplineVertex(float x, float y) {
  22. construct(x,y,x,y,x,y);
  23. }
  24. public SplineVertex(Vertex p) {
  25. construct(p,p,p);
  26. }
  27.  
  28. public void construct(float x, float y, float x1, float y1, float x2, float y2) {
  29. this.cp1 = new Vertex(x1, y1);
  30. this.p = new Vertex(x,y);
  31. this.cp2 = new Vertex(x2, y2);
  32. }
  33. public void construct(Vertex p, Vertex cp1, Vertex cp2) {
  34. this.cp1 = cp1;
  35. this.p = p;
  36. this.cp2 = cp2;
  37. }
  38.  
  39. public SplineVertex add(Vertex v) {
  40. return new SplineVertex(v.add(p));
  41. }
  42. public SplineVertex add(float x, float y) {
  43. return new SplineVertex(p.add(x,y));
  44. }
  45. /*
  46. * Perform an affine transform on the spline vertex by delegating to the child vertices
  47. */
  48. public SplineVertex transform (AffineTransformation at) {
  49. return new SplineVertex(p.transform(at), cp1.transform(at), cp2.transform(at));
  50. }
  51. }

Finally the class to create the spline. The constructor for this class is an array of spline vertices which represent the original path. By calling the refine method the function performs bisections to create a more accurate representation of the curve. The refine(float tol) method take a float as an argument. The float defines the target curvature. Once the curvature is reached the function will stop bisecting that curve segment. Putting a lower number will generate a smoother curve.

The vertices of the curve can be accessed by calling the getVertices() method.

  1. public class Spline {
  2. public final String TAG = this.getClass().getSimpleName();
  3.  
  4. // Stores the vertices which make up the curve
  5. public ArrayList<SplineVertex> splineVertices = new ArrayList<SplineVertex>();
  6.  
  7. // When we are refining the curve we use this array to store the new points
  8. private ArrayList<SplineVertex> newArray = new ArrayList<SplineVertex> ();
  9.  
  10. // Constructor: an array of spline vertices
  11. public Spline (ArrayList<SplineVertex> v) {
  12. splineVertices = v;
  13. }
  14.  
  15. // Add a new spline vertex
  16. public void addPoint(SplineVertex v) {
  17. splineVertices.add(v);
  18. }
  19.  
  20. /*
  21. * This is a private method used to perform the bisection described above
  22. */
  23. private SplineVertex newPoint(SplineVertex sp1, SplineVertex sp2) {
  24.  
  25. /* x----v2----x
  26. * / . . \
  27. * / v12--ns--v23 \
  28. * /. .\
  29. * v1 v3
  30. * / \
  31. * / \
  32. * / \
  33. * sp1 sp2
  34. *
  35. * ns - new spline point
  36. * x - control point
  37. */
  38.  
  39. Vertex v1 = midPoint(sp1.p, sp1.cp2);
  40. Vertex v2 = midPoint(sp1.cp2, sp2.cp1);
  41. Vertex v3 = midPoint(sp2.cp1, sp2.p);
  42.  
  43. Vertex v12 = midPoint(v1, v2);
  44. Vertex v23 = midPoint(v2, v3);
  45.  
  46. sp1.cp2 = v1;
  47. sp2.cp1 = v3;
  48.  
  49. return new SplineVertex(midPoint(v12, v23), v12, v23);
  50. }
  51.  
  52. /*
  53. * Refine will loop over the curve creating new points until the curvature of each line segment is less than the input amount
  54. */
  55. public void refine (float tol) {
  56. boolean complete = false;
  57.  
  58. if(tol==0)
  59. tol = 0.01f;
  60. // Loop until the curvature is within
  61. // tolerance
  62. while(complete==false) {
  63.  
  64. complete = true;
  65. int size = splineVertices.size()-1;
  66.  
  67. // Loop over the spline points and create a new point
  68. // as per diagram for each point. Then test the curvature
  69. // if the curvature is greater than the tolerance add the
  70. // point to our new refined line
  71. newArray = new ArrayList<SplineVertex>();
  72. for(int i=0; i<size; i++ ) {
  73. SplineVertex sp1 = splineVertices.get(i);
  74. SplineVertex sp2 = splineVertices.get(i+1);
  75. SplineVertex n1 = newPoint(sp1, sp2);
  76.  
  77. newArray.add(sp1);
  78.  
  79. if(curvature(sp1.p, sp2.p, n1.p)>tol) {
  80. newArray.add(n1);
  81. complete = false;
  82. }
  83.  
  84. // Because we're working on a i+1 basis
  85. // it's necessary to add the last point
  86. // at the end
  87. if (i==size-1) {
  88. newArray.add(sp2);
  89. }
  90. }
  91. // Update the array which contains out line with the new refined spline
  92. splineVertices = newArray;
  93. }
  94. }
  95.  
  96. // Get the vertices which make up the curve
  97. public ArrayList<Vertex> getVertices () {
  98.  
  99. ArrayList<Vertex> v = new ArrayList<Vertex>();
  100. for(SplineVertex sp: splineVertices) {
  101. v.add(sp.p);
  102. }
  103.  
  104. return v;
  105. }
  106.  
  107. /*
  108. *Get a list of vertices but don't duplicate the final point because it can it will break the triangulation algorithm
  109. */
  110. public ArrayList<Vertex> getPolygon () {
  111.  
  112. ArrayList<Vertex> v = getVertices();
  113.  
  114. if(v.get(0).equals(v.get(v.size()-1)))
  115. v.remove(v.size()-1);
  116.  
  117. return v;
  118. }
  119.  
  120.  
  121. /*
  122. * Find the mid point between two vertices
  123. */
  124. private Vertex midPoint (Vertex v1, Vertex v2) {
  125. return new Vertex((v1.x + v2.x)/2, (v1.y+v2.y)/2);
  126. }
  127.  
  128. /*
  129. * Find the square of the curvature
  130. */
  131. private float curvature (Vertex v1, Vertex v2, Vertex vc) {
  132. Vertex midPoint = midPoint(v1, v2);
  133. return sq(midPoint.x - vc.x) + sq(midPoint.y - vc.y);
  134. }
  135.  
  136. private float sq (float f1) {
  137. return f1 * f1;
  138. }
  139.  
  140. /*
  141. * Get the number of vertices
  142. */
  143. public int size() {
  144. return splineVertices.size();
  145. }
  146.  
  147. /*
  148. * Get the first point
  149. */
  150. public SplineVertex getFirst() {
  151. return splineVertices.get(0);
  152. }
  153.  
  154. /*
  155. * Perform an affine transformation on the spline
  156. */
  157. public void transfrom (AffineTransformation at) {
  158. for(int i=0; i< splineVertices.size(); i++) {
  159. SplineVertex v = splineVertices.get(i);
  160. splineVertices.set(i, v.transform(at));
  161. }
  162. }
  163.  
  164. /*
  165. * To string method for debugging
  166. */
  167. public String toString () {
  168. String s = new String();
  169. for(Vertex v: getVertices()) {
  170. s += v.toString()+"\n";
  171. }
  172. return s;
  173. }
  174. }

There we have it, this code can be used to refine a spline to an arbitrary level of accuracy. If you want to use the affine transform functionality you will need to download the Java Topology Suite library here. If not just delete these methods from the three classes.

In the next section I'll describe how to use these classes to construct cubic splines and straight lines by parsing the inkscape SVG file.

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.