Splines for Math(s) deficient Coders. http://www.allegro.cc/forums/view/585707 Allegro.cc Forum Thread matthew@allegro.cc (Matthew Leverton) Thu, 01 Jun 2006 19:41:36 +0000

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?

]]> no-reply@allegro.cc (Thomas Fjellstrom) Thu, 01 Jun 2006 09:20:30 +0000

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 (B-Spline for 4 points). I don't know the equations by heart, but google does...

]]> no-reply@allegro.cc (miran) Thu, 01 Jun 2006 10:06:53 +0000

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.

]]> no-reply@allegro.cc (Thomas Fjellstrom) Thu, 01 Jun 2006 10:11:04 +0000

In that case I think you should forget about all that stuff...
Here's pseudocode anyway: 

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

]]> no-reply@allegro.cc (miran) Thu, 01 Jun 2006 10:17:01 +0000

Yeah, That I can understand, its the some_formula() that I need to understand.

I've already written a nice "arc" drawing routine:

1void draw_arc(BITMAP *bmp, point p1, point p2, double step)
2{
3 point mp;
4 
5 step = M_PI / step;
6 
7 mp.x = ( p1.x + p2.x ) / 2.0;
8 mp.y = ( p1.y + p2.y ) / 2.0;
9 
10 double w = fabs(p2.x - p1.x);
11 double h = fabs(p2.y - p1.y);
12 double ll = sqrt(w*w + h*h);
13 double r = ll / 2.0;
14 
15 double start = atan2( p1.y - mp.y , p1.x - mp.x );
16 double end = start+rad(180); //atan2( p2.y - mp.y , p2.x - mp.x );
17 //start + M_PI;
18 
19 double rw = ll;
20 double rh = ll;
21
22 // for testing only, real algo is below
23 arc(bmp, mp.x, mp.y, ftofix(deg(-start) * 256.0 / 360.0), ftofix(deg(-end) * 256.0 / 360.0), r, makecol(55,55,55));
24 
25 start -= rad(180);
26 double pheta = start;
27 end -= rad(180);
28 
29 printf("\rstart: %f, end: %f", deg(start), deg(end));
30 
31 double lx = rw/2 * cos( pheta ) + mp.x;
32 double ly = rh/2 * sin( pheta ) + mp.y;
33 double fx = lx;
34 double fy = ly;
35 
36 for(; pheta - ( end ) < 0.001; pheta += step) {
37 double x = rw/2 * cos( pheta ) + mp.x;
38 double y = rh/2 * sin( pheta ) + mp.y;
39 
40// if(lx && ly) {
41 line(bmp, lx, ly, x, y, makecol(255, 255, 255));
42 putpixel(bmp, lx, ly, makecol(255,0,0));
43 putpixel(bmp, x, y, makecol(255,0,0));
44// }
45 
46 lx = x;
47 ly = y;
48 }
49
50 if(lx != p1.x && ly != p1.y) {
51 line(bmp, lx, ly, p1.x, p1.y, makecol(100, 255, 100));
52 }
53 
54 if(fx != p2.x && fy != p2.y) {
55 line(bmp, fx, fy, p2.x, p2.y, makecol(100, 255, 100));
56 }
57 
58 
59// rect(bmp, p1.x, p1.y, p2.x, p2.y, makecol(100,100,100));
60 rect(bmp, mp.x-r, mp.y-r, mp.x+r, mp.y+r, makecol(150,150,150));
61 line(bmp, p1.x, p1.y, p2.x, p2.y, makecol(0,0,255));
62 putpixel(bmp, mp.x, mp.y, makecol(0,255,0));
63 
64}

]]> no-reply@allegro.cc (Thomas Fjellstrom) Thu, 01 Jun 2006 10:31:29 +0000

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

]]> no-reply@allegro.cc (CGamesPlay) Thu, 01 Jun 2006 16:06:12 +0000

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

]]> no-reply@allegro.cc (Thomas Fjellstrom) Thu, 01 Jun 2006 16:33:04 +0000

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

]]> no-reply@allegro.cc (miran) Thu, 01 Jun 2006 17:06:21 +0000

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.

]]> no-reply@allegro.cc (CGamesPlay) Thu, 01 Jun 2006 17:09:09 +0000

Here's a small test program I wrote when I was studying B-splines. 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.

#SelectExpand
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 B-spline curve 13Vertex *bspline; // a B-spline 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.0f-u)*(1.0f-u)*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.0f-u)*(1.0f-u)*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.0f-u)*(1.0f-u)*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.0f-u)*(1.0f-u)*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,k-1,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,k-1,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[n-1].x; 176 bspline[count].y = R[n-1].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_W-160, 10, makecol(128,128,128), -1, " left - decrease g"); 194 textprintf_ex(bmp, font, SCREEN_W-160, 20, makecol(128,128,128), -1, "right - increase g"); 195 textprintf_ex(bmp, font, SCREEN_W-160, 30, makecol(128,128,128), -1, " down - decrease k"); 196 textprintf_ex(bmp, font, SCREEN_W-160, 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<n-1; 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_periodic-1; 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_points-1; 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>n-1) k=n-1; 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();

]]> no-reply@allegro.cc (miran) Thu, 01 Jun 2006 19:41:36 +0000