Some general info about splines
Splines
... oh dear, you think, not splines again. Someone comes up with this topic every few months. How can that possibly be useful?
The fact is that 90% of demos nowadays still use the "easy" method of interpolating between two values in non-time critical routines. Yours truly is guilty of this too: Look at Sonolumineszenz and see how all the zooms, all the camera movement and object rotation is linear, so you can see it "jerk" whenever anything changes direction.
Of course simply drawing a line between two points is much less work for the processor to do, but in many cases much better effects can be achieved by using splines, and they are relatively easy to set up as long as you use the code I have supplied for you. Then I'll give some examples of a useful application of the routines.
Some general info about splines
(most of you will have heard this bit before, so skip it if necessary)
There are two main types of splines: Bezier splines and Hermite splines. The underlying formulas are the same, but the values you supply to control the curve have different meanings.
For simplicity we will define a curve in "one" dimension to start with. Imagine a 2D graph with 2 axes. The horizontal axis we shall call "t" and it shall vary between 0 and 1.
The vertical axis contains the scale of the two values that we want to interpolate between. In this case we shall interpolate between 2 and 4. This range of values can have multiple meanings: for example the "zoom" setting on my 3D camera routine.
Doing a linear interpolation gives the following result:
^
|
5 | ....X
| .....
4 | .....
| .....
3 | .....
| .....
2 X....
|
1 |
|
0 +---------------------------------+----> t
0 1This is OK, but gives little control and when you link 2 interpolations, there is a sudden change in gradient/direction at the "knots"
Instead we can define the line in terms of the start and end points, plus the gradients at the starts and ends. For instance, let's say that the gradients on the above example are both 0 (i.e. make them "flat"):
^
|
5 | ......X
| ......
4 | ...
| ...
3 | ....
| .....
2 X......
|
1 |
|
0 +---------------------------------+----> t
0 1This gives a nice smoother curve. Defining a curve like this is known as a Hermite Curve. The four values needed are:
- p_0 - start point value
- g_0 - start gradient
- g_1 - end gradient
- p_1 - end point value
(see the picture)
Alternatively we can define the curve in terms of 4 points. We have the equivalents of points p_0 and p_1 , but to define the curve gradients we let the gradient have the same direction as the line between p_0 and another, third, point. And the same with the end gradient.
(see the picture again)
This is known as the Bezier Curve.
Spline Matrices
We shall define the curve in terms of matrices, simply because it is easier to show in a document. First we define the matrix of points used to define the curve.
For a Hermite matrix this is
We can define a curve in more than one dimension. For example, this curve will start at (0,0) with a gradient of (10,20), and end at (50,100) with a gradient of (25,15):
... and so on for n dimensional points. For a Bezier matrix, the matrix is just [p_0] [p_1] [p_2] [p_3] where p0-p3 are shown in the supplied picture.
Now I won't bother explaining all the mathematics behind splines because they should be available in any good maths book. Instead I will give you the formula and show that this does give the correct output, and how to implement the curve in code.
OK, the interval that we define the curve over is 0<=t<=1. At t=0 we are at the starting point, at t=1 we are at the end point. To give the correct curve, the formula for both types of splines is of the form:
.. where p is the outcome point.
We can express this in matrices as:
a, b, c and d all depend on the point settings we have supplied. We let [ a b c d ] be our "basis" matrix which we calculate when first "initialising" the spline. It calculates the input matrix once, and this can be re-used for the whole spline.
For Hermite curves, the input matrix is calculated by:
And for Bezier curves:
... don't forget that the matrix [ p0 ... ] can have more than one dimension! For example, let's try our Hermite example from before:
We now save the basis matrix before calculating any points along the curve.
Now we can calculate a point on the curve using the formula above. Let's say that t =1 so that we calculate the end point. Using our formula,
bm = [ 2 -2 1 1][ 0 0 ] = [ -75 -155 ]
[ -3 3 -2 -1][ 50 100 ] [ 115 235 ]
[ 0 0 1 0][ 10 20 ] [ 10 20 ]
[ 1 0 0 0][ 15 25 ] [ 0 0 ]
p = [ t^3 t^2 t 1 ] . bm
[ 1^3 1^2 1 1 ][ 75 -155 ] = [ -75+115+10 ]
[ 115 235 ] [ -155+235+20 ]
[ 10 20 ]
[ 0 0 ]
= [ 50 ] .. which is the point we defined as p1
[ 100 ]Now all this looks like magic, but does work for all values of t between 0 and 1.
Deep breath
The code to implement this in assembler is supplied on disk! It is very small (easy to fit in a 4k demo). Here's how to use it:
1. Initialising the splines
There are two routines to initialise a spline, one for Hermite curves, another for Bezier. You supply the input matrix of points, the number of "columns" of the points, and the output buffer, which is always 4 * (the number of columns) words in size.
The important point is that you must supply the matrix of points in a "downwards" format, for example our test points above of
convert to the buffer and code:
; -----------------------------------------------------------------
my_test_matrix: dc.w 0,50,10,25
dc.w 0,100,20,15
my_basis_matrix:
ds.w 4*2
my_test_code:
lea my_test_matrix(pc),a0 ;input
lea my_basis_matrix(pc),a1 ;output
move.w #2,d0 ;matrix has 2
;columns
bsr spl_init_matrix_hermite ;go!
; -----------------------------------------------------------------Now you can calculate a point on the curve:
To do this we need to supply:
- the basis_matrix in a_0
- the number of dimensions of the basis matrix, ie 2 here, in d_1
- the value of "t" for the point, in d_0 . This is a word value.
For t=0, d0 = $0000
For t=0.99999 d0 = $7fff... a value of t=1 is "impossible" here, so use $7fff instead.
; -----------------------------------------------------------------
my_test_value: ds.w 2 ; has 2 dimensions
calc_my_test_point:
lea my_basis_matrix(pc),a0 ;input
lea my_test_value(pc),a1 ;
move.w #2,d1 ;matrix has 2
;columns
move.w #$4000,d0 ;t = 0.5
bsr spl_calc_spline_value ;go!
; -----------------------------------------------------------------Fin
... so there you go. I use this technique to give smooth camera movement in demos (the code is supplied on disk), but there are all kinds of uses. If you ensure that the gradients at start and end points of consecutive points have the same direction (not necessarily the same magnitude!) then several curves in succession will give a smooth "piecewise" curve where it is impossible to work out where the "knots" are.
Steven Tattersall
tattersall@zetnet.co.uk
http://www.users.zetnet.co.uk/tattersall
CAM.S
; CAM.S
;
; Spline-based camera movement
; 27/2/98
; Steven Tattersall
; tattersall@zetnet.co.uk
;
;
; An example of using the code in SPLINE.S
; One camera position consists of 7 values:
; - the x,y,z point in the world
; - the 3 rotation angles about this point
; - the distance of the camera from the x,y,z point
; cam_set initialises a table of camera positions, plus
; a "speed" of movement between each point
;
; cam_calc works out the next value of the camera position
; when called continually
; the 7 current values are stored in "cam_output_values"
; each time.
section text
cam_set:
move.w (a0)+,cam_start_x
move.w (a0)+,cam_start_y
move.w (a0)+,cam_start_z
move.w (a0)+,cam_start_anga
move.w (a0)+,cam_start_angb
move.w (a0)+,cam_start_angc
move.w (a0)+,cam_start_dist
move.w (a0)+,cam_start_tan_x
move.w (a0)+,cam_start_tan_y
move.w (a0)+,cam_start_tan_z
move.w (a0)+,cam_start_tan_anga
move.w (a0)+,cam_start_tan_angb
move.w (a0)+,cam_start_tan_angc
move.w (a0)+,cam_start_tan_dist
move.l a0,cam_address
move.l a1,cam_restart
bsr cam_get_ends
;bsr cam_calc
rts
cam_calc:
move.l #$7fff,d0
divu cam_interval,d0
muls.w cam_interval_pos,d0
lea cam_output_matrix,a0
lea cam_output_values,a1
move.w #7,d1 ;6 values
jsr spl_calc_spline_value
addq.w #1,cam_interval_pos
move.w cam_interval_pos,d0
cmp.w cam_interval,d0
bne.s .notnext
bsr cam_get_next
.notnext:
rts
cam_get_next:
move.l cam_address,a0
; Copy current end values to current start values:
move.w cam_end_x,cam_start_x
move.w cam_end_y,cam_start_y
move.w cam_end_z,cam_start_z
move.w cam_end_anga,cam_start_anga
move.w cam_end_angb,cam_start_angb
move.w cam_end_angc,cam_start_angc
move.w cam_end_dist,cam_start_dist
move.w cam_end_tan_x,cam_start_tan_x
move.w cam_end_tan_y,cam_start_tan_y
move.w cam_end_tan_z,cam_start_tan_z
move.w cam_end_tan_anga,cam_start_tan_anga
move.w cam_end_tan_angb,cam_start_tan_angb
move.w cam_end_tan_angc,cam_start_tan_angc
move.w cam_end_tan_dist,cam_start_tan_dist
; Get next values and put in our temporary matrix:
cam_get_ends:
move.w (a0)+,cam_interval
bmi.s cam_nomore
cam_fetch:
clr.w cam_interval_pos
move.w (a0)+,cam_end_x
move.w (a0)+,cam_end_y
move.w (a0)+,cam_end_z
move.w (a0)+,cam_end_anga
move.w (a0)+,cam_end_angb
move.w (a0)+,cam_end_angc
move.w (a0)+,cam_end_dist
move.w (a0)+,cam_end_tan_x
move.w (a0)+,cam_end_tan_y
move.w (a0)+,cam_end_tan_z
move.w (a0)+,cam_end_tan_anga
move.w (a0)+,cam_end_tan_angb
move.w (a0)+,cam_end_tan_angc
move.w (a0)+,cam_end_tan_dist
move.l a0,cam_address
; Make the matrix:
lea cam_geometry_matrix,a0
lea cam_output_matrix,a1
move.w #7,d0 ;number of rows
jsr spl_init_matrix_hermite
rts
cam_nomore:
move.l cam_restart,a0
move.l a0,cam_address
bra cam_get_ends
include splines.s
;-------------------------------------------------------------------------
section bss
cam_address ds.l 1
cam_interval ds.w 1
cam_interval_pos ds.w 1
cam_restart ds.l 1
cam_geometry_matrix:
cam_start_x ds.w 1
cam_end_x ds.w 1
cam_start_tan_x ds.w 1
cam_end_tan_x ds.w 1
cam_start_y ds.w 1
cam_end_y ds.w 1
cam_start_tan_y ds.w 1
cam_end_tan_y ds.w 1
cam_start_z ds.w 1
cam_end_z ds.w 1
cam_start_tan_z ds.w 1
cam_end_tan_z ds.w 1
cam_start_anga ds.w 1
cam_end_anga ds.w 1
cam_start_tan_anga ds.w 1
cam_end_tan_anga ds.w 1
cam_start_angb ds.w 1
cam_end_angb ds.w 1
cam_start_tan_angb ds.w 1
cam_end_tan_angb ds.w 1
cam_start_angc ds.w 1
cam_end_angc ds.w 1
cam_start_tan_angc ds.w 1
cam_end_tan_angc ds.w 1
cam_start_dist ds.w 1
cam_end_dist ds.w 1
cam_start_tan_dist ds.w 1
cam_end_tan_dist ds.w 1
cam_output_matrix ds.w 28
cam_output_values ds.w 7
section textSPLINES.S
; SPLINES.S
; General spline routines
; - occupy 198 bytes!
; Steven Tattersall, 1998
;
; CONTENTS
; spl_init_matrix_bezier
; spl_init_matrix_hermite
; spl_calc_spline_value
;
section text
spl_start:
;--------------------------------------------------------------------
; spl_init_matrix_bezier
; PURPOSE calculate a bezier basis matrix
; INPUT d0 no. of columns
; a0 input matrix (in "downwards" format)
; a1 output matrix
spl_init_matrix_bezier:
movem.l d0-a6,-(a7)
lea spl_matrix_bezier(pc),a2
bra spl_init_matrix
;--------------------------------------------------------------------
; spl_init_matrix_hermite
; PURPOSE calculate a hermite basis matrix
; INPUT d0 no. of columns
; a0 input matrix (in "downwards" format)
; a1 output matrix
spl_init_matrix_hermite:
; Our input matrix is a set of 4 points, each with 'n' dimensions
; We therefore have a n x 4 matrix (width n, height 4)
; i.e. [ a1 b1 ... ]
; [ a2 b2 ]
; [ a3 b3 ]
; [ a4 b4 ]
; This is multiplied by the matrix ( 2 -2 1 1)
; (-3 3 -2 -1)
; ( 0 0 1 0)
; ( 1 0 0 0) to give our ouput mtrx
; i.e. the first column is multiplied by 2,-2,1,1
; then -3,3,-2,-1 for the next value
movem.l d0-a6,-(a7)
lea spl_matrix_hermite(pc),a2
spl_init_matrix:
move.w d0,d7 ;save the no of rows
subq.w #1,d7
move.l a0,a4
.row_loop:
moveq #4-1,d6
move.l a2,a6 ;a6 - address of current input matrix
.column_loop:
move.l a4,a5 ;a5 - address of current input row
; Now multiply this by our column:
move.w (a5)+,d0
muls.w (a6)+,d0
move.w (a5)+,d1
muls.w (a6)+,d1
add.l d1,d0
move.w (a5)+,d1
muls.w (a6)+,d1
add.l d1,d0
move.w (a5)+,d1
muls.w (a6)+,d1
add.l d1,d0
move.w d0,(a1)+ ;output the column
; Move on to the next column:
dbf d6,.column_loop
; We have done each column, so move on to the next row of input
addq.l #4*2,a0
move.l a0,a4
dbf d7,.row_loop
movem.l (a7)+,d0-a6
rts
;--------------------------------------------------------------------
; spl_calc_spline_value
; PURPOSE calculate a single point on the curve, given the basis matrix
; INPUT
; d0 value of "t" ($0000 t=0, $7fff t=1)
; d1 no. of columns
; a0 basis matrix
; a1 output matrix
spl_calc_spline_value:
; first calculate our
; values of "t"
; and store in registers
ext.l d0
movem.l d0-d7,-(a7)
move.w d1,d7 ;counter
move.w d0,d1 ;d0 = t
muls.w d1,d1
add.l d1,d1
swap d1 ;d1 = t*t
move.w d1,d2
muls.w d0,d2 ;d2 = t*t*t
add.l d2,d2
swap d2
; now calculate "d7" values
subq.w #1,d7
.calcloop:
move.w (a0)+,d6 ;t*t*t term
muls.w d2,d6
move.w (a0)+,d5 ;t*t term
muls.w d1,d5
add.l d5,d6
move.w (a0)+,d5 ;t term
muls.w d0,d5
add.l d5,d6
add.l d6,d6
swap d6
add.w (a0)+,d6 ;1 term
move.w d6,(a1)+
dbf d7,.calcloop
movem.l (a7)+,d0-d7
rts
;--------------------------------------------------------------------
; The base matrices used
spl_matrix_hermite:
dc.w +2,-2,+1,+1
dc.w -3,+3,-2,-1
dc.w +0,+0,+1,+0
dc.w +1,+0,+0,+0
spl_matrix_bezier:
dc.w -1,+3,-3,+1
dc.w +3,-6,+3,+0
dc.w -3,+3,+0,+0
dc.w +1,+0,+0,+0
;--------------------------------------------------------------------
spl_end:
spl_size = spl_end-spl_startSPLTEST.S
; SPLTEST.S
; little test code for doc on splines
; assemble and run under MonST and check the 2 values
; stored in my_test_value
; it should give the values of 50 and 100
; (or just less than this)
; -----------------------------------------------------------------
value_of_t equ $7fff ; t = "1"
my_test_code:
lea my_test_matrix(pc),a0 ;input
lea my_basis_matrix(pc),a1 ;output
move.w #2,d0 ;matrix has 2
;columns
bsr spl_init_matrix_hermite ;go!
calc_my_test_point:
lea my_basis_matrix(pc),a0 ;input
lea my_test_value(pc),a1 ;
move.w #2,d1 ;matrix has 2
;columns
move.w #value_of_t,d0 ;t = ?
bsr spl_calc_spline_value ;go!
illegal
; -----------------------------------------------------------------
my_test_matrix: dc.w 0,50,10,25
dc.w 0,100,20,15
my_basis_matrix:
ds.w 4*2
my_test_value: ds.w 2 ; has 2 dimensions
include splines.s
Comments