Another day, another shared code. (Although I actually have to finish and polish all my other little projects… I know… I know…)
According to Mathworldthe definition of a spline is: “A piecewise polynomial function that can have a locally very simple form, yet at the same time be globally flexible and smooth. Splines are very useful for modeling arbitrary functions, and are used extensively in computer graphics.”
Here is the page on Cubic Splines, the kind of splines we will be constructing.
but a picture says more than a thousand words:
http://mathworld.wolfram.com/images/eps-gif/CubicSpline.gif
Basically, you define a number of points in 2D or 3D space, and using these points to create a “spline”, a curve which smoothly goes through all points. What you can use this for, I will leave to your own imagination… (hint: the missile-movement in this game is created using splines) Using this code, you can define a “spline”, and get any point on that line (between [0…1]… where 0 is the start and 1 is the end point of the line)
How to use
Spline3D spline = new Spline3D();
spline.addPoint(new Vector3f(5.0f, 7.0f, 8.0f));
spline.addPoint(new Vector3f(2.0f, 11.0f, 6.0f));
spline.addPoint(new Vector3f(9.0f, 4.0f, 3.0f));
spline.calcSpline(); // call everytime a point on the spline has changed
Vector3f pointAtTwoThirds = spline.getPoint(2.0f / 3.0f); // getPoint is valid for 0.0f through 1.0f.
Easy, no? for 2D points, just replace Spline3D with Spline2D and add/get Vector2f points. In the missiles example, I create a Spline with 3 points, one at the origin (the space ship), one behind the space-ship (a bit randomized), and one at the target. After that, every time the enemy ship moves, I re-calculate the spline, while the missile continues along the spline’s trajectory.
Here follows the source code:
based on: http://www.cse.unsw.edu.au/~lambert/splines/
Cubic: holds and solves a Cubic Equasion
public class Cubic {
private float a,b,c,d;
public Cubic(float a, float b, float c, float d) {
this.a =a;
this.b =b;
this.c =c;
this.d =d;
}
public float eval(float u) {
return (((d*u) + c)*u + b)*u + a;
}
}
BasicSpline: The backbone, abstract class holding the function to solve a 1D spline (which is used to solve 2D and 3D splines)
public abstract class BasicSpline {
public static final Object[] EMPTYOBJLIST = new Object[] { };
public void calcNaturalCubic(List valueCollection, Method getVal, Collection<Cubic> cubicCollection) throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {
int num = valueCollection.size()-1;
float[] gamma = new float[num+1];
float[] delta = new float[num+1];
float[] D = new float[num+1];
int i;
/*
We 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< num; i++) {
gamma[i] = 1.0f/(4.0f - gamma[i-1]);
}
gamma[num] = 1.0f/(2.0f - gamma[num-1]);
Float p0 = (Float) getVal.invoke(valueCollection.get(0), EMPTYOBJLIST);
Float p1 = (Float) getVal.invoke(valueCollection.get(1), EMPTYOBJLIST);
delta[0] = 3.0f * (p1 - p0) * gamma[0];
for(i=1; i< num; i++) {
p0 = (Float) getVal.invoke(valueCollection.get(i-1), EMPTYOBJLIST);
p1 = (Float) getVal.invoke(valueCollection.get(i+1), EMPTYOBJLIST);
delta[i] = (3.0f * (p1 - p0) - delta[i - 1]) * gamma[i];
}
p0 = (Float) getVal.invoke(valueCollection.get(num-1), EMPTYOBJLIST);
p1 = (Float) getVal.invoke(valueCollection.get(num), EMPTYOBJLIST);
delta[num] = (3.0f * (p1 - p0) - delta[num - 1]) * gamma[num];
D[num] = delta[num];
for(i=num-1; i >= 0; i--) {
D[i] = delta[i] - gamma[i] * D[i+1];
}
/*
now compute the coefficients of the cubics
*/
cubicCollection.clear();
for(i=0; i<num; i++) {
p0 = (Float) getVal.invoke(valueCollection.get(i), EMPTYOBJLIST);
p1 = (Float) getVal.invoke(valueCollection.get(i+1), EMPTYOBJLIST);
cubicCollection.add(new Cubic(
p0,
D[i],
3*(p1 - p0) - 2*D[i] - D[i+1],
2*(p0 - p1) + D[i] + D[i+1]
)
);
}
}
}
Spline2D: Defines a 2D Spline
public class Spline2D extends BasicSpline{
private Vector<Vector2f> points;
private Vector<Cubic> xCubics;
private Vector<Cubic> yCubics;
private static final String vector2DgetXMethodName = "getX";
private static final String vector2DgetYMethodName = "getY";
private Method vector2DgetXMethod;
private Method vector2DgetYMethod;
private static final Object[] EMPTYOBJ = new Object[] { };
public Spline2D() {
this.points = new Vector<Vector2f>();
this.xCubics = new Vector<Cubic>();
this.yCubics = new Vector<Cubic>();
try {
vector2DgetXMethod = Vector2f.class.getDeclaredMethod(vector2DgetXMethodName, new Class[] { });
vector2DgetYMethod = Vector2f.class.getDeclaredMethod(vector2DgetYMethodName, new Class[] { });
} catch (SecurityException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (NoSuchMethodException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public void addPoint(Vector2f point) {
this.points.add(point);
}
public Vector<Vector2f> getPoints() {
return points;
}
public void calcSpline() {
try {
calcNaturalCubic(points, vector2DgetXMethod, xCubics);
calcNaturalCubic(points, vector2DgetYMethod, yCubics);
} catch (IllegalArgumentException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IllegalAccessException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (InvocationTargetException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public Vector2f getPoint(float position) {
position = position * xCubics.size(); // extrapolate to the arraysize
int cubicNum = (int) position;
float cubicPos = (position - cubicNum);
return new Vector2f(xCubics.get(cubicNum).eval(cubicPos),
yCubics.get(cubicNum).eval(cubicPos));
}
}
Spline3D: Defines a 3D Spline
public class Spline3D extends BasicSpline{
private Vector<Vector3f> points;
private Vector<Cubic> xCubics;
private Vector<Cubic> yCubics;
private Vector<Cubic> zCubics;
private static final String vector3DgetXMethodName = "getX";
private static final String vector3DgetYMethodName = "getY";
private static final String vector3DgetZMethodName = "getZ";
private Method vector2DgetXMethod;
private Method vector2DgetYMethod;
private Method vector2DgetZMethod;
private static final Object[] EMPTYOBJ = new Object[] { };
public Spline3D() {
this.points = new Vector<Vector3f>();
this.xCubics = new Vector<Cubic>();
this.yCubics = new Vector<Cubic>();
this.zCubics = new Vector<Cubic>();
try {
vector2DgetXMethod = Vector3f.class.getDeclaredMethod(vector3DgetXMethodName, new Class[] { });
vector2DgetYMethod = Vector3f.class.getDeclaredMethod(vector3DgetYMethodName, new Class[] { });
vector2DgetZMethod = Vector3f.class.getDeclaredMethod(vector3DgetZMethodName, new Class[] { });
} catch (SecurityException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (NoSuchMethodException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public void addPoint(Vector3f point) {
this.points.add(point);
}
public Vector<Vector3f> getPoints() {
return points;
}
public void calcSpline() {
try {
calcNaturalCubic(points, vector2DgetXMethod, xCubics);
calcNaturalCubic(points, vector2DgetYMethod, yCubics);
calcNaturalCubic(points, vector2DgetZMethod, zCubics);
} catch (IllegalArgumentException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IllegalAccessException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (InvocationTargetException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public Vector3f getPoint(float position) {
position = position * xCubics.size();
int cubicNum = (int) position;
float cubicPos = (position - cubicNum);
return new Vector3f(xCubics.get(cubicNum).eval(cubicPos),
yCubics.get(cubicNum).eval(cubicPos),
zCubics.get(cubicNum).eval(cubicPos));
}
}
