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:


		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


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


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


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


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