# 2D & 3D Spline (think smooth curve through n points) function

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.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);

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 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 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));
}
}

``````

very nice indeed!

Can you also add a method that gets the angle at a given point ?

## Mik

Well, in my game (For the missile direction) I just calculate the angle for the vector between point (n) and point (n + 0.0001f) on the spline.

Cheers!

Mik

Yes, I could, but in my game I use my own “Vector2D” class instead of LWJGL’s Vector2f class. Its a little different… I will rewrite my game code using the Vector2f class (was planning to do this anyway) and post the solution here. (my own vector2d class has more utility functions, but I can easily make them static functions in a “VectorTool” class or something)

Very good. I’ll stay tuned…

Mik

It looks superb and the game/demo is very good.

However, couldn’t you have just achieved the same effect by appling a force that is proporitional to the displacement between the vectors?

``````
Vector3f f1 = object1.getPosition();
Vector3f f2 = spaceship.getPosition();

Vector3f distance = f1.subtract(f2);
distance.normaliseLocal();
distance.multiplyLocal(MISSILE_COMMANDER.MISSILE_POWER);

``````

That will pretty much do what you have done using your splines (with a little tweaking). :

DP

Oh yer, you need an initial force so that it can start it off…A simple constant would do for each type of missile…

DP

and thus we can see why the principle of Least Action can be used to describe what Newtonian Physics also describes Cool topics. It’s up to you which to program ;D

Good stuff, but does it only provide calculating a position from a given t value (0, 1)? Just smoothly interpolating t will give you a bursty movement with variable speed which isn’t much good for missiles etc

Curves really need a calcPositionAtLength() to be practical, unfortunatly thats a right pain to write. :o

That is needed to use that with a physic engine with an object that is in the direction of its displacement.

Does the above code require the control points to be uniformly spaced?

I gave the code a big overhaul to support calculating the position at a certain distance from the origin, following the spline.

The initial version was “quite fast” but after some intelligent caching I managed to make the code 200x faster. Note that I’m not caching the calculated values, as they are not likely to be reusable, but I cache the values in the intermediate steps. In a reasonably large spline, containing 16 control-points measuring 3750 units, a position lookup for a random distance takes only 0.09ms on a 2.4GHz machine! (was 24.0ms when walking along the spline)

``````
Spline3D

Spline(Vector3f[] vecs)

public int pointCount()
public float getLength()

public void setAccuracy(float accuracy)
public void setMargin(float margin)

public void getPositionAt(float t, Vector3f r)
public Vector3f getPositionAt(float t)

public void getPositionAtDistance(float distance, Vector3f r)
public Vector3f getPositionAtDistance(float distance)

public float getDistanceAt(float distance)

``````

Now you can create objects that follow the spline at a custom speed!

I hope somebody has as much fun with this as I have

Note that the extremely sharp curve isn’t that sharp, because it’s 3d and moves straight into the screen.

Anarchotron: The control-points do not have to be uniformly spaced.

Here you go, works again

cool, thanks ;D

1. Changed step-algorithm to be 99.9% consistent for random intervals, instead of roughly 97% in previous version. This caused shaky spline-traversal…

2. 600% faster: random distance calc, now 15us, not ms, even 6.2us with server VM :o on 2.4GHz P4, first (uncached) calculation takes 36.3ms. After traversing a very long spline very slowly with high accuracy, only 512 float values are cached over time, so no need to worry about RAM consumption.

3. Changed constructor:

public Spline(Vector3f[] vecs, float accuracy, float margin)
accuracy works very smooth when using 0.001-0.010. the higher the rougher, cheaper in first calc, same speed (!) when cached.
margin defines the margin-of-error the actual answer. measured in units.

Source-code (still a bit messy) Spline3D.java 8.2kb

``````
Vector3f[] vecs = ...;

float accuracy = 0.001f;
float margin = 0.01f;
Spline3D spline = new Spline3D(vecs, accuracy, margin);

Vector3f pos = spline.getPositionAtDistance(...); // for moving along the spline
Vector3f pos = spline.getPositionAt(...); // 0.0F --> "spline.pointCount()"   -  for drawing the spline

``````

Sorry for the messy post-layout

For anybody using my previous code (and today I found out somebody was actually using it!) and wondered where the heck that initial lag came from, here is an update!

It has a main method, which acts as a nice visualizer.

``````/*
* Created on Sep 23, 2005
*/

package craterstudio.math;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.SystemColor;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

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

public class Spline2D
{
public static void main(String[] args)
{
final float[][] points = new float[16][2];
Random r = new Random(123456L);
for (int i = 0; i < points.length; i++)
{
points[i][0] = 32 + r.nextInt(384);
points[i][1] = 32 + r.nextInt(384);
}

final Spline2D growingSpline = new Spline2D(points);
final Spline2D fixedSpline = new Spline2D(points);
growingSpline.enabledTripCaching(16.0f, 0.001f);
fixedSpline.enabledTripCaching(16.0f, 0.001f);

for (int i = 0; i < 8; i++)
{
while (fixedSpline.travelCache.size() > 1)
fixedSpline.travelCache.remove(fixedSpline.travelCache.size() - 1);
long t1 = System.currentTimeMillis();
fixedSpline.getTripPosition(4000.0f);
long t2 = System.currentTimeMillis();
System.out.println("full trip took: " + (t2 - t1) + "ms");
}

JPanel panel = new JPanel()
{
float travelled  = 0.0f;
float travelStep = (float) Math.PI;

@Override
protected void paintComponent(Graphics g)
{
super.paintComponent(g);

g.setColor(SystemColor.control);
g.fillRect(0, 0, this.getWidth(), this.getHeight());

// draw full spline

g.setColor(Color.BLUE);

float d = 0.0f;
while (d < points.length)
{
float[] at = fixedSpline.getPositionAt(d);

this.drawCircle(g, at[0], at[1], 2);

d += 0.002f;
}

// draw GROWING cache
g.setColor(Color.RED);

for (CacheItem item : growingSpline.travelCache)
{
this.drawCircle(g, item.xpos, item.ypos, 3);
}

// draw GROWING spline
g.setColor(Color.GREEN);

float[] xy;
for (int i = 0; i < 25; i++)
{
xy = growingSpline.getTripPosition(this.travelled * i / 25.0f);
this.drawCircle(g, xy[0], xy[1], 3);
}

this.travelled += this.travelStep;

this.repaint();
}

private void drawCircle(Graphics g, float x, float y, int r)
{
g.fillOval((int) x - r, (int) y - r, r * 2, r * 2);
}
};
panel.setPreferredSize(new Dimension(512, 512));
JFrame frame = new JFrame();
JPanel cp = (JPanel) frame.getContentPane();
cp.setLayout(new BorderLayout());
frame.pack();
frame.setResizable(false);
frame.setLocationRelativeTo(null);
frame.setVisible(true);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}

public Spline2D(float[][] points)
{
this.count = points.length;

float[] x = new float[count];
float[] y = new float[count];

for (int i = 0; i < count; i++)
{
x[i] = points[i][0];
y[i] = points[i][1];
}

this.x = Curve.calcCurve(count - 1, x);
this.y = Curve.calcCurve(count - 1, y);
}

//

final int count;
private final Cubic[] x, y;

/**
* POINT COUNT
*/

public final int pointCount()
{
return count;
}

/**
* POSITION
*/

public final float[] getPositionAt(float param)
{
float[] v = new float[2];
this.getPositionAt(param, v);
return v;
}

public final void getPositionAt(float param, float[] result)
{
// clamp
if (param < 0.0f)
param = 0.0f;
if (param >= count - 1)
param = (count - 1) - Math.ulp(count - 1);

// split
int ti = (int) param;
float tf = param - ti;

// eval
result[0] = x[ti].eval(tf);
result[1] = y[ti].eval(tf);
}

/**
* CURVE CLASS
*/

private static class Curve
{
static final Cubic[] calcCurve(int n, float[] axis)
{
float[] gamma = new float[n + 1];
float[] delta = new float[n + 1];
float[] d = new float[n + 1];
Cubic[] c = new Cubic[n + 0];

// gamma
gamma[0] = 0.5f;
for (int i = 1; i < n; i++)
gamma[i] = 1.0f / (4.0f - gamma[i - 1]);
gamma[n] = 1.0f / (2.0f - gamma[n - 1]);

// delta
delta[0] = 3.0f * (axis[1] - axis[0]) * gamma[0];
for (int i = 1; i < n; i++)
delta[i] = (3.0f * (axis[i + 1] - axis[i - 1]) - delta[i - 1]) * gamma[i];
delta[n] = (3.0f * (axis[n] - axis[n - 1]) - delta[n - 1]) * gamma[n];

// d
d[n] = delta[n];
for (int i = n - 1; i >= 0; i--)
d[i] = delta[i] - gamma[i] * d[i + 1];

// c
for (int i = 0; i < n; i++)
{
float x0 = axis[i + 0];
float x1 = axis[i + 1];
float d0 = d[i + 0];
float d1 = d[i + 1];
c[i] = new Cubic(x0, d0, 3.0f * (x1 - x0) - 2.0f * d0 - d1, 2.0f * (x0 - x1) + d0 + d1);
}
return c;
}
}

/**
* CUBIC CLASS
*/

static class Cubic
{
private final float a, b, c, d;

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

final float eval(float u)
{
return (((d * u) + c) * u + b) * u + a;
}
}

private List<CacheItem> travelCache;
private float           maxTravelStep;
private float           posStep;

public void enabledTripCaching(float maxTravelStep, float posStep)
{
this.maxTravelStep = maxTravelStep;
this.posStep = posStep;

float x = this.x[0].eval(0.0f);
float y = this.y[0].eval(0.0f);

this.travelCache = new ArrayList<CacheItem>();
}

public float[] getTripPosition(float totalTrip)
{
CacheItem last = this.travelCache.get(this.travelCache.size() - 1);

// build cache
while (last.travelled < totalTrip)
{
if (totalTrip == 0.0f)
{
// don't even bother
break;
}

float travel = Math.min(totalTrip - last.travelled, maxTravelStep);

CacheItem curr = this.getSteppingPosition(last.position, travel, posStep);

if (curr.position >= this.count)
{
// reached end of spline
break;
}

// only cache if we travelled far enough
if (curr.travelled > this.maxTravelStep * 0.95f)
{
}

curr.travelled += last.travelled;

last = curr;
}

// figure out position

int lo = 0;
int hi = this.travelCache.size() - 1;

while (true)
{
int mid = (lo + hi) / 2;

last = this.travelCache.get(mid);

if (last.travelled < totalTrip)
{
if (lo == mid)
break;
lo = mid;
}
else
{
if (hi == mid)
break;
hi = mid;
}
}

for (int i = lo; i <= hi; i++)
{
CacheItem item = this.travelCache.get(i);

if (item.travelled <= totalTrip)
{
last = item;
}
else
{
break;
}
}

float travel = totalTrip - last.travelled;
last = this.getSteppingPosition(last.position, travel, posStep);
return new float[] { last.xpos, last.ypos };
}

private CacheItem getSteppingPosition(float posOffset, float travel, float segmentStep)
{
float pos = posOffset;
float[] last = this.getPositionAt(pos);

float travelled = 0.0f;

while (travelled < travel && pos < this.count)
{
float[] curr = this.getPositionAt(pos += segmentStep);
travelled += Spline2D.dist(last, curr);
last = curr;
}

CacheItem item = new CacheItem(last[0], last[1], 0.0f);
item.position = pos;
item.travelled = travelled;
return item;
}

private static float dist(float[] a, float[] b)
{
float dx = b[0] - a[0];
float dy = b[1] - a[1];

return (float) Math.sqrt(dx * dx + dy * dy);
}
}
``````

Wow, this looks very cool, thanks. Have you got a class file for CacheItem, it’s not compiling on its own without it. Cheers

Sorry :persecutioncomplex:

``````
class CacheItem
{
public CacheItem(float xpos, float ypos, float zpos)
{
this.xpos = xpos;
this.ypos = ypos;
this.zpos = zpos;
}

float position;
float xpos, ypos, zpos;
float travelled;
}

``````