Report

# Some general info about splines Published in
atari
· 11 Nov 2023
2

## 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                                 1

This 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                                 1

This gives a nice smoother curve. Defining a curve like this is known as a Hermite Curve. The four values needed are:

• p0 - start point value
• p1 - end point value

(see the picture)

Alternatively we can define the curve in terms of 4 points. We have the equivalents of points p0 and p1, but to define the curve gradients we let the gradient have the same direction as the line between p0 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

\begin{bmatrix}
p_0 \\
p_1 \\
g_0 \\
g_1 \\
\end{bmatrix}

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):

\begin{bmatrix}
0 & 0 \\
50 & 100 \\
10 & 20 \\
25 & 15 \\
\end{bmatrix}

... 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:

p = a \cdot t^3 + b \cdot t^2 + c \cdot t + d

.. where p is the outcome point.

We can express this in matrices as:

p = \begin{bmatrix} t^3 & t^2 & t & 1 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix}

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:

bm = \begin{bmatrix}
2 & -2 & 1 & 1 \\
-3 & 3 & -2 & -1 \\
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
p_0 \\
p_1 \\
g_0 \\
g_1 \\
\end{bmatrix}

And for Bezier curves:

bm = \begin{bmatrix}
1 & 3 & -3 & 1 \\
3 & -6 & 3 & 0 \\
-3 & 3 & 0 & 0 \\
1 & 0 & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
p_0 \\
p_1 \\
p_2 \\
p_3 \\
\end{bmatrix}

... don't forget that the matrix [ p0 ... ] can have more than one dimension! For example, let's try our Hermite example from before:

bm = \begin{bmatrix}
2 & -2 & 1 & 1 \\
-3 & 3 & -2 & -1 \\
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
0 & 0 \\
50 & 100 \\
10 & 20 \\
15 & 25 \\
\end{bmatrix}
=
\begin{bmatrix}
-75 & -155 \\
115 & 235 \\
10 & 20 \\
0 & 0 \\
\end{bmatrix}

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

\begin{bmatrix}
0 & 0 \\
50 & 100 \\
10 & 20 \\
25 & 15 \\
\end{bmatrix}

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 a0
• the number of dimensions of the basis matrix, ie 2 here, in d1
• the value of "t" for the point, in d0. 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 ; ; 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 text ## SPLINES.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_start ## SPLTEST.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

← previous
next →

2 DrWatson

I'm testing the math formulas. The editor seems to work well

12 Nov 2023 AniphaeS

I agree, formulas now are so cool

22 Nov 2023 sending ... This website uses cookies to store your preferences and improve the service. Cookies authorization will allow me and / or my partners to process personal data such as browsing behaviour.