
Splines for Math(s) deficient Coders. 
Thomas Fjellstrom
Member #476
June 2000

I've been looking up the algorithms and stuff for calculating and drawing splines, and while I can understand some of the explanations, all the images of way too small and incomplete (math) functions, and formulas/equations. Is there someone here who can explain it for a coder?  
miran
Member #2,407
June 2002

Yes. You have a set of points. Your goal is to draw a curve that starts in the first point and ends in the last. You can do that by drawing short straight segments, short enough so that it's not obvious they are straight. So you take a parameter that goes from 0 to 1 with small increments in a for loop. You feed this parameter into some sort of formula to get the next point. You draw a straight line from the previous point to the one you just calculated and move on. When the parameter is 0, the point you get is p0 (the starting points) and when it is 1, the point is your last point. So by the time your for loop ends, you will have drawn a smooth curve between p0 and p3 (if you have 4 points). There are a few different formulas to draw splines for different purposes (you want the line to go through all points or not, the kind of connectivity you want, how changing one point affects the curve, etc.) Bezier is a really simple kind of spline (BSpline for 4 points). I don't know the equations by heart, but google does...  
Thomas Fjellstrom
Member #476
June 2000

Thats the issue, I've read a few different explanations that had the equations in them, but I can't read any of them. English and code is fine, pictures of equations I can't do.  
miran
Member #2,407
June 2002

In that case I think you should forget about all that stuff... Point points[4]; Point p0 = points[0]; for (double p=0.0; p<=1.0; p+=0.01) { Point p1 = some_formula(points, p); draw_line(p0, p1); p0 = p1; }
 
Thomas Fjellstrom
Member #476
June 2000

Yeah, That I can understand, its the some_formula() that I need to understand. I've already written a nice "arc" drawing routine:
 
CGamesPlay
Member #2,559
July 2002

Hmm, I wouldn't bother with that function... It would work, I wager, but involves extra maths to compute the remaining splines. This is a very nice spline. I recommend you use it. To start, just go through and interpolate between two points, then you can move into more. That formula takes input as points (split into an x formula and a y formula). Take two arbitrary points, and for m1 use (1, 0) and for m2 use (1, 0).  Ryan Patterson  <http://cgamesplay.com/> 
Thomas Fjellstrom
Member #476
June 2000

I was looking at a bunch of links, and one that really looked neat was the NURB spline. course it had all kinds of corner cases that it had to take care of using extra nodes and such. [quote]Hmm, I wouldn't bother with that function...[/quote]If you mean my arc function, its for arcs and it only does 180° arcs, due to the start + 180 but that was intentional. It wwasn'tintended for use as a spline helper, just something to say that I'm not a complete idiot, just I can't read most of the "theoretical" equations, [b]especially[/b] when the images used are about 2x too small to show any of the smaller var names legibly. But thank you, I should be able to do something with that one.  
miran
Member #2,407
June 2002

NURBs are the most generalized kind of splines. All other kinds of splines are basically NURBs with some parts fixed or simplified or ommited or something...  
CGamesPlay
Member #2,559
July 2002

Good. This is a bump so you can psot back here once you get that sorted, and we can go into using more than 4 control points.  Ryan Patterson  <http://cgamesplay.com/> 
miran
Member #2,407
June 2002

Here's a small test program I wrote when I was studying Bsplines. The code is not well organized but the important part is nice and easy to read. The functions you're interested in are make_spline() and N() plus some global variables. 1#include <allegro.h>
2
3typedef struct Vertex {
4 int x;
5 int y;
6} Vertex;
7
8const int n = 12; // number of control points (4 for a Bezier)
9int k = 2; // degree of the spline polynomial
10int g = 16; // density of the interpolation
11Vertex R[n]; // the control grid
12Vertex *pbspline; // a periodic Bspline curve
13Vertex *bspline; // a Bspline curve
14int n_points_periodic; // number of vertices in pbspline
15int n_points; // number of vertices in bspline
16int *U; // the knot vector
17int u; // the number of knots
18
19int selectedPoint = 1;
20bool mouseDown = false;
21int grip_x, grip_y;
22
23bool handle_mouse() {
24 int mx = mouse_x;
25 int my = mouse_y;
26 int mb = mouse_b;
27
28 bool ret = false;
29 int oldSel = selectedPoint;
30
31 if (!mb) {
32 mouseDown = false;
33 selectedPoint = 1;
34 for (int i=0; i<n; i++) {
35 int dx = mx  R<i>.x;
36 int dy = my  R<i>.y;
37 int d2 = dx*dx + dy*dy;
38 if (d2 < 4*4) {
39 selectedPoint = i;
40 break;
41 }
42 }
43 }
44 else {
45 if (!mouseDown) {
46 mouseDown = true;
47 grip_x = mx;
48 grip_y = my;
49 }
50
51 if (selectedPoint != 1) {
52 int dx = mx  grip_x;
53 int dy = my  grip_y;
54 if (dx  dy) {
55 R[selectedPoint].x += dx;
56 R[selectedPoint].y += dy;
57 grip_x += dx;
58 grip_y += dy;
59 ret = true;
60 }
61 }
62 }
63
64 ret = selectedPoint != oldSel;
65 return ret;
66}
67
68// make a predefined control line
69void initialize() {
70 R[0].x = 50; R[0].y = 100;
71 R[1].x = 100; R[1].y = 450;
72 R[2].x = 300; R[2].y = 550;
73 R[3].x = 200; R[3].y = 350;
74 R[4].x = 200; R[4].y = 150;
75 R[5].x = 300; R[5].y = 350;
76 R[6].x = 450; R[6].y = 500;
77 R[7].x = 400; R[7].y = 250;
78 R[8].x = 550; R[8].y = 50;
79 R[9].x = 700; R[9].y = 550;
80 R[10].x = 750; R[10].y = 300;
81 R[11].x = 700; R[11].y = 150;
82
83 bspline = NULL;
84 pbspline = NULL;
85 U = NULL;
86}
87
88
89void make_periodic_spline() {
90 int n_sections = n  2;
91 int i, j, k;
92 float u;
93 float delta;
94
95 n_points_periodic = n_sections*g + 1;
96 if (pbspline) delete [] pbspline;
97 pbspline = new Vertex[n_points_periodic];
98
99 delta = 1.0f/g;
100 k = 0;
101 for (i=0; i<n_sections; i++) {
102 u = 0.0f;
103 for (j=0; j<g; j++) {
104 pbspline[k].x = (int)(0.5f * ((1.0fu)*(1.0fu)*R<i>.x + (2.0f*u*u + 2.0f*u + 1.0f)*R[i+1].x + u*u*R[i+2].x));
105 pbspline[k].y = (int)(0.5f * ((1.0fu)*(1.0fu)*R<i>.y + (2.0f*u*u + 2.0f*u + 1.0f)*R[i+1].y + u*u*R[i+2].y));
106 u += delta;
107 k++;
108 }
109 }
110 i;
111 pbspline[k].x = (int)(0.5f * ((1.0fu)*(1.0fu)*R<i>.x + (2.0f*u*u + 2.0f*u + 1.0f)*R[i+1].x + u*u*R[i+2].x));
112 pbspline[k].y = (int)(0.5f * ((1.0fu)*(1.0fu)*R<i>.y + (2.0f*u*u + 2.0f*u + 1.0f)*R[i+1].y + u*u*R[i+2].y));
113}
114
115
116float N(int i, int k, float u) {
117 if (k==0) {
118 if (u >= U<i> && u < U[i+1]) return 1.0f;
119 else return 0.0f;
120 }
121
122 float f1;
123 float f2;
124
125 if (U[i+k]  U<i> == 0)
126 f1 = 0.0f;
127 else
128 f1 = ((u  U<i>)*N(i,k1,u))/(U[i+k]  U<i>);
129
130 if (U[i+k+1]  U[i+1] == 0)
131 f2 = 0.0f;
132 else
133 f2 = ((U[i+k+1]  u)*N(i+1,k1,u))/(U[i+k+1]  U[i+1]);
134
135 return f1 + f2;
136}
137
138
139void make_spline() {
140 int i, j, l;
141 int n_sections = n  k;
142 float delta;
143 float uf;
144 float tx, ty;
145
146 if (U) delete U;
147 u = k + n + 1;
148 U = new int<u>;
149
150 for (i=0; i<k+1; i++) U<i> = 0;
151 for (i=k+1; i<n; i++) U<i> = i  k;
152 for (i=n; i<u; i++) U<i> = n  k;
153
154 n_points = n_sections*g + 1;
155 if (bspline) delete [] bspline;
156 bspline = new Vertex[n_points];
157
158 delta = 1.0f/g;
159 uf = 0.0;
160 int count=0;
161 for (i=0; i<n_sections; i++) {
162 for (j=0; j<g; j++) {
163 tx = 0;
164 ty = 0;
165 for (l=0; l<k+1; l++) {
166 tx += N(i+l,k,uf)*R[i+l].x;
167 ty += N(i+l,k,uf)*R[i+l].y;
168 }
169 bspline[count].x = (int)tx;
170 bspline[count].y = (int)ty;
171 uf += delta;
172 count++;
173 }
174 }
175 bspline[count].x = R[n1].x;
176 bspline[count].y = R[n1].y;
177}
178
179
180void draw_grid(BITMAP *bmp) {
181 int i;
182
183 clear_to_color(bmp, makecol(0,0,0));
184 for (i=0; i<SCREEN_W; i+=50) vline(bmp, i, 0, SCREEN_H, makecol(60, 60, 60));
185 for (i=0; i<SCREEN_H; i+=50) hline(bmp, 0, i, SCREEN_W, makecol(60, 60, 60));
186 for (i=0; i<SCREEN_W; i+=200) vline(bmp, i, 0, SCREEN_H, makecol(80, 80, 80));
187 for (i=0; i<SCREEN_H; i+=200) hline(bmp, 0, i, SCREEN_W, makecol(80, 80, 80));
188 textprintf_ex(bmp, font, 10, 10, makecol(128,128,128), 1, "n = %d", n);
189 textprintf_ex(bmp, font, 10, 20, makecol(128,128,128), 1, "k = %d", k);
190 textprintf_ex(bmp, font, 10, 30, makecol(128,128,128), 1, "u = %d", u);
191 textprintf_ex(bmp, font, 10, 40, makecol(128,128,128), 1, "g = %d", g);
192
193 textprintf_ex(bmp, font, SCREEN_W160, 10, makecol(128,128,128), 1, " left  decrease g");
194 textprintf_ex(bmp, font, SCREEN_W160, 20, makecol(128,128,128), 1, "right  increase g");
195 textprintf_ex(bmp, font, SCREEN_W160, 30, makecol(128,128,128), 1, " down  decrease k");
196 textprintf_ex(bmp, font, SCREEN_W160, 40, makecol(128,128,128), 1, " up  increase k");
197}
198
199
200void draw_control_grid(BITMAP *bmp) {
201 int i;
202
203 for (i=0; i<n; i++) {
204 if (i == selectedPoint) {
205 circlefill(bmp, R<i>.x, R<i>.y, 3, makecol(240, 128, 128));
206 circle(bmp, R<i>.x, R<i>.y, 3, makecol(200, 64, 64));
207 }
208 else {
209 circle(bmp, R<i>.x, R<i>.y, 2, makecol(200, 64, 64));
210 }
211 }
212
213 for (i=0; i<n1; i++) {
214 line(bmp, R<i>.x, R<i>.y, R[i+1].x, R[i+1].y, makecol(160, 120, 120));
215 }
216}
217
218
219void draw_periodic_spline(BITMAP *bmp) {
220 int i;
221 for (i=0; i<n_points_periodic; i++) circle(bmp, pbspline<i>.x, pbspline<i>.y, 1, makecol(200, 200, 64));
222 for (i=0; i<n_points_periodic1; i++) line(bmp, pbspline<i>.x, pbspline<i>.y, pbspline[i+1].x, pbspline[i+1].y, makecol(180, 180, 120));
223}
224
225
226void draw_spline(BITMAP *bmp) {
227 int i;
228 for (i=0; i<n_points; i++) circle(bmp, bspline<i>.x, bspline<i>.y, 1, makecol(64, 200, 64));
229 for (i=0; i<n_points1; i++) line(bmp, bspline<i>.x, bspline<i>.y, bspline[i+1].x, bspline[i+1].y, makecol(120, 180, 120));
230 for (i=0; i<u; i++) textprintf_ex(bmp, font, 10, i*10 + 60, makecol(128,128,128), 1, "%d", U<i>);
231}
232
233
234void destroy() {
235 if (bspline) delete [] bspline;
236 if (pbspline) delete [] pbspline;
237 if (U) delete [] U;
238}
239
240
241int main() {
242 allegro_init();
243 set_color_depth(32);
244 set_gfx_mode(GFX_AUTODETECT_WINDOWED, 800, 600, 0, 0);
245 install_keyboard();
246 install_mouse();
247 enable_hardware_cursor();
248 show_mouse(screen);
249
250
251 initialize();
252
253 bool redraw = true;
254 bool done = false;
255 BITMAP *bmp = create_bitmap(SCREEN_W, SCREEN_H);
256
257 while (!done) {
258 while (keypressed()) {
259 switch (readkey()>>8) {
260 case KEY_LEFT:
261 g>>=1;
262 if (g<4) g = 4;
263 else redraw = true;
264 break;
265 case KEY_RIGHT:
266 g<<=1;
267 if (g>64) g = 64;
268 else redraw = true;
269 break;
270 case KEY_UP:
271 k++;
272 if (k>n1) k=n1;
273 else redraw = true;
274 break;
275 case KEY_DOWN:
276 k;
277 if (k<0) k=0;
278 else redraw = true;
279 break;
280 case KEY_ESC:
281 done = true;
282 };
283 }
284
285 redraw = handle_mouse();
286
287 if (redraw) {
288 make_periodic_spline();
289 make_spline();
290 draw_grid(bmp);
291 draw_control_grid(bmp);
292 //draw_periodic_spline(bmp);
293 draw_spline(bmp);
294 blit(bmp, screen, 0, 0, 0, 0, SCREEN_W, SCREEN_H);
295 }
296
297 redraw = false;
298 }
299
300 destroy();
301 destroy_bitmap(bmp);
302 return 0;
303}
304END_OF_MAIN();
 
