static Path builder Object for 2D

Hi guys

after some work and some suggestione from someone of you, i created finally a gerator path builder object based
on the B-spline, so i'm happy to share it

the implementation is for 2D game this is one example of utilization:

1
2
3
4
5
6
7
8
9
10
11
12
13

      List<Point> points;
      
      curve = new NatCubicSpline();
      curve.addPoint(0, 350);      
      curve.addPoint(100, 200);
      curve.addPoint(300, 100);
      curve.addPoint(200, 300);      
      curve.addPoint(100, 100);      
      curve.addPoint(500, 300);
      curve.addPoint(700, 50);      
      curve.addPoint(850, 200);   
      
      points = curve.generatePoints(); //return the list of point interpolated

it is based on 3 class:
Cubic --> able to resolve cubic functions
ControlCurve --> basic class control curve that should be extended by specific algorithms
NatCubicSpline --> implementation of B-Spline

at the end i will add also a easy main to see the result
BSplineWindow --> main class to run an example

hope that can help someone of you

cubic class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

package it.test.bspline;

/**
 * this class represents a cubic polynomial semplified
 * 
 * 
 * @author Alessandro D'Ottavio
 *
 */
public class Cubic {

  float a,b,c,d;  /* a + b*x + c*x^2 +d*x^3 */

  public Cubic(float a, float b, float c, float d){
    this.a = a;
    this.b = b;
    this.c = c;
    this.d = d;
  }

  /**
   * evaluate the polynomial for in the x
   * 
   * @param x
   * @return
   */
  public float eval(float x) {
    return (((d*x) + c)*x + b)*x + a;
  }
}

ControlCurve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

package it.test.bspline;

import java.awt.*;

/**
 * 
 * 
 * 
 * @author Alessandro D'Ottavio
 *
 */
public class ControlCurve {

  protected Polygon pts;
  
  public ControlCurve() {
    pts = new Polygon();
  }
  
  /**
   * add a point to the control curve
   * 
   * @param x
   * @param y
   */
  public void addPoint(int x, int y) {
    pts.addPoint(x,y);
  }


}

NatCubicSpline

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

package it.test.bspline;

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

/**
 * 
 * 
 * @author Alessandro D'Ottavio
 *
 */
public class NatCubicSpline extends ControlCurve{
   
   /**
    * calculates the natural cubic spline that interpolates
    * y[0], y[1], ... y[n]
    * The first segment is returned as
    * C[0].a + C[0].b*u + C[0].c*u^2 + C[0].d*u^3 0<=u <1
    * the other segments are in C[1], C[2], ...  C[n-1]
    * 
    *  
    **/
   Cubic[] calcNaturalCubic(int n, int[] x) {
      float[] gamma = new float[n+1];
      float[] delta = new float[n+1];
      float[] D = new float[n+1];
      int i;
      
      /* solve the equation
       [2 1       ] [D[0]]   [3(x[1] - x[0])  ]
       |1 4 1     | |D[1]|   |3(x[2] - x[0])  |
       |  1 4 1   | | .  | = |      .         |
       |    ..... | | .  |   |      .         |
       |     1 4 1| | .  |   |3(x[n] - x[n-2])|
       [       1 2] [D[n]]   [3(x[n] - x[n-1])]

       by using row operations to convert the matrix to upper triangular
       and then back sustitution.  The D[i] are the derivatives at the knots.
       */

      gamma[0] = 1.0f/2.0f;
      for ( i = 1; i < n; i++) {
         gamma[i] = 1/(4-gamma[i-1]);
      }
      gamma[n] = 1/(2-gamma[n-1]);

      delta[0] = 3*(x[1]-x[0])*gamma[0];
      for ( i = 1; i < n; i++) {
         delta[i] = (3*(x[i+1]-x[i-1])-delta[i-1])*gamma[i];
      }
      delta[n] = (3*(x[n]-x[n-1])-delta[n-1])*gamma[n];

      D[n] = delta[n];
      for ( i = n-1; i >= 0; i--) {
         D[i] = delta[i] - gamma[i]*D[i+1];
      }

      /* now compute the coefficients of the cubics */
      Cubic[] C = new Cubic[n];
      for ( i = 0; i < n; i++) {
         C[i] = new Cubic((float)x[i], D[i], 3*(x[i+1] - x[i]) - 2*D[i] - D[i+1],
               2*(x[i] - x[i+1]) + D[i] + D[i+1]);
      }
      return C;
   }


   public List<Point> generatePoints(){
      List<Point> points = new ArrayList<Point>();
      
      Point next;
      if (pts.npoints >= 2) {
         Cubic[] xPolyn = calcNaturalCubic(pts.npoints-1, pts.xpoints);
         Cubic[] yPolyn = calcNaturalCubic(pts.npoints-1, pts.ypoints);
         next = new Point((int) Math.round(xPolyn[0].eval(0)),(int) Math.round(yPolyn[0].eval(0)));
         points.add(next);
      
         for (int i = 0; i < xPolyn.length; i++) {   //for each cubic calculated

            int stepxForSegment = Math.abs(pts.xpoints[i+1]-pts.xpoints[i]);   //evaluated the max distance to calculate the point to draw for each interval
            int stepyForSegment = Math.abs(pts.ypoints[i+1]-pts.ypoints[i]);   //this is done to maintain constant the number of point used to draw the line
            int stepForSegment = Math.max(stepxForSegment, stepyForSegment);    
            
            //int stepForSegment = 12                                 //uncoment this row if u want to see the difference and comment the upper row   
            
            for (int j = 1; j <= stepForSegment; j++) {
               float u = j / (float) stepForSegment;
               next = new Point(Math.round(xPolyn[i].eval(u)),Math.round(yPolyn[i].eval(u)));
               points.add(next);
            }
         }
      }
      return points;
   }
   
}

BSplineWindow class main example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

package it.test;


import it.test.bspline.NatCubicSpline;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;


public class BSplineWindow extends JPanel implements ActionListener{

   private static final int PERIOD = 100;    // 0.1 secs
   private static final int PWIDTH = 850;     
   private static final int PHEIGHT = 400;

   //B-spline variables
   protected NatCubicSpline curve;
   protected List<Point> points;      

   public BSplineWindow(){

      setBackground(Color.white);
      setPreferredSize( new Dimension(PWIDTH, PHEIGHT) );      
      
      curve = new NatCubicSpline();
      curve.addPoint(0, 350);      
      curve.addPoint(100, 200);
      curve.addPoint(300, 100);
      curve.addPoint(200, 300);      
      curve.addPoint(100, 100);      
      curve.addPoint(500, 300);
      curve.addPoint(700, 50);      
      curve.addPoint(850, 200);   
      
      points = curve.generatePoints();

      
      new Timer(PERIOD, this).start(); 
   } 

   public void actionPerformed(ActionEvent e){ 
      repaint();  
   }

   public void paintComponent(Graphics g){
      super.paintComponent(g);
      Graphics2D g2d = (Graphics2D)g;
      Long timeb = System.nanoTime();
      for (Point point : points) {
         g2d.drawLine((int)point.getX(), (int)point.getY(), (int)point.getX(), (int)point.getY());
      }
      
   }


   public static void main(String args[]){

      BSplineWindow ttPanel = new BSplineWindow();
      JFrame app = new JFrame("B-Spline test");
      app.getContentPane().add(ttPanel, BorderLayout.CENTER);
      app.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

      app.pack();
      app.setResizable(false);  
      app.setVisible(true);
   }

}

good work