NewsForumsCodeLogsGallerySpecsSearch

Splines or curves

BlitzMax Forums/BlitzMax Programming/Splines or curves

JoshK(Posted 2009) [#1]
You have two points, two normals, and an interpolation value between them. If the interpolation value is 0, the result is the first point and normal. If the interpolation value is 1, the result is the second point and normal.

How do you calculate a curved path between the two points, so that the function can return a value for any interpolation? For example, if I got the values for interpolations of 0.0, 0.2, 0.4, 0.6, 0.8, and 1.0, and created a line from one to the next, it would form a curved path with 5 segments.

Function Curve( point0:TVec3, normal0:TVec3, point1:TVec3, normal1:TVec3, interpolation:Float, resultpoint:TVec3, resultnormal:TVec3 )

EndFunction


SSS(Posted 2009) [#2]
So in principle I think the problem is pretty easy, but to do it efficiently might not be. Consider the function,

f(t) = at^3 + bt^2 + ct + d

where a,b,c,d are 3-vectors. Then essentially the problem that you've posed is to solve the equations,

f(0) = point0
f'(0) = tangent0
f(1) = point1
f'(1) = tangent1

where I've used tangent0 and tangent1 as opposed to normal0 and normal1 since these do not generate a unique line. Thus, you must simply solve two cubic equations and two quadratic. The former are going to be (as functions go) quite computationally intensive, but if you're not doing too many it should be OK.


BlitzSupport(Posted 2009) [#3]
Cubic splines [pdf] are something I've been learning recently, in my quest to deal with network lag prediction, and they're very simple. (Applying them to physical movement/timing is the part that's holding me back.)



You can just replace the For/Next loop (For t# = 0.0 To 1.0 Step 0.1) with your interpolation value to get any point along the curve (eg. t# = 0.5 is halfway).

Here's an animated visualisation -- use mouse, plus -/+ to select the point to be moved.



This Blitz3D code shows how to 'chain' splines to form smooth sequences -- the first two points in the second spline are derived from the last two points in the first.



Lastly, some alternative splines that may be of interest:

Java demos
Java code


SSS(Posted 2009) [#4]
Ah what I said before was totally wrong, you don't need to solve a cubic just a few linear equations. You have,

d = point0
c = tangent 0 (from the first two equations)

a+b+tangent0+point0 = point1
3a+2b+tangent0 = tangent1.

These two equations can be easily solved to give the equation that you need efficiently.


JoshK(Posted 2009) [#5]
Thanks, here is my 3D version:
Type TSpline

	Field A:Float, B:Float, C:Float, D:Float
	Field E:Float, F:Float, G:Float, H:Float
	Field I:Float, J:Float, K:Float, L:Float

	Method Init(p0:TVec3,n0:TVec3,p1:TVec3,n1:TVec3,mag:Float=1)
		Local x0:Float, y0:Float, z0:Float, x1:Float, y1:Float, z1:Float, x2:Float, y2:Float, z2:Float, x3:Float, y3:Float, z3:Float
		
		x0=p0.x
		y0=p0.y
		z0=p0.z

		x1=n0.x*mag+p0.x
		y1=n0.y*mag+p0.y
		z1=n0.z*mag+p0.z

		x2=n1.x*mag+p1.x
		y2=n1.y*mag+p1.y
		z2=n1.z*mag+p1.z

		x3=p1.x
		y3=p1.y
		z3=p1.z
				
		' x coefficients...
		A = x3 - (3.0 * x2) + (3.0 * x1) - x0
		B = (3.0 * x2) - (6.0 * x1) + (3.0 * x0)
		C = (3.0 * x1) - (3.0 * x0)
		D = x0
		
		' y coefficients...
		E = y3 - (3.0 * y2) + (3.0 * y1) - y0
		F = (3.0 * y2) - (6.0 * y1) + (3.0 * y0)
		G = (3.0 * y1) - (3.0 * y0)
		H = y0
		
		' z coefficients...
		I = z3 - (3.0 * z2) + (3.0 * z1) - z0
		J = (3.0 * z2) - (6.0 * z1) + (3.0 * z0)
		K = (3.0 * z1) - (3.0 * z0)
		L = z0
	EndMethod

	Method Interpolate(t:Float,v:TVec3)
		v.x = Float((A * (t ^ 3.0)) + (B * (t ^ 2.0)) + (C * t) + D)
		v.y = Float((E * (t ^ 3.0)) + (F * (t ^ 2.0)) + (G * t) + H)
		v.z = Float((I * (t ^ 3.0)) + (J * (t ^ 2.0)) + (K * t) + L)
	EndMethod

EndType