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