1 /* $Id: curves.c,v 1.2 2004-12-19 14:52:48 btb Exp $ */
3 THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
4 SOFTWARE CORPORATION ("PARALLAX"). PARALLAX, IN DISTRIBUTING THE CODE TO
5 END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
6 ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
7 IN USING, DISPLAYING, AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
8 SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
9 FREE PURPOSES. IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
10 CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES. THE END-USER UNDERSTANDS
11 AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.
12 COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION. ALL RIGHTS RESERVED.
17 * curve generation stuff
22 static char rcsid[] = "$Id: curves.c,v 1.2 2004-12-19 14:52:48 btb Exp $";
44 #define ONE_OVER_SQRT2 F1_0 * 0.707106781
49 segment *OriginalMarkedSeg;
51 int OriginalMarkedSide;
52 segment *CurveSegs[MAX_SEGMENTS];
54 const fix Mh[4][4] = { { 2*F1_0, -2*F1_0, 1*F1_0, 1*F1_0 },
55 {-3*F1_0, 3*F1_0, -2*F1_0, -1*F1_0 },
56 { 0*F1_0, 0*F1_0, 1*F1_0, 0*F1_0 },
57 { 1*F1_0, 0*F1_0, 0*F1_0, 0*F1_0 } };
59 void generate_banked_curve(fix maxscale, vms_equation coeffs);
61 void create_curve(vms_vector *p1, vms_vector *p4, vms_vector *r1, vms_vector *r4, vms_equation *coeffs) {
62 // Q(t) = (2t^3 - 3t^2 + 1) p1 + (-2t^3 + 3t^2) p4 + (t~3 - 2t^2 + t) r1 + (t^3 - t^2 ) r4
64 coeffs->n.x3 = fixmul(2*F1_0,p1->x) - fixmul(2*F1_0,p4->x) + r1->x + r4->x;
65 coeffs->n.x2 = fixmul(-3*F1_0,p1->x) + fixmul(3*F1_0,p4->x) - fixmul(2*F1_0,r1->x) - fixmul(1*F1_0,r4->x);
68 coeffs->n.y3 = fixmul(2*F1_0,p1->y) - fixmul(2*F1_0,p4->y) + r1->y + r4->y;
69 coeffs->n.y2 = fixmul(-3*F1_0,p1->y) + fixmul(3*F1_0,p4->y) - fixmul(2*F1_0,r1->y) - fixmul(1*F1_0,r4->y);
72 coeffs->n.z3 = fixmul(2*F1_0,p1->z) - fixmul(2*F1_0,p4->z) + r1->z + r4->z;
73 coeffs->n.z2 = fixmul(-3*F1_0,p1->z) + fixmul(3*F1_0,p4->z) - fixmul(2*F1_0,r1->z) - fixmul(1*F1_0,r4->z);
79 vms_vector evaluate_curve(vms_equation *coeffs, int degree, fix t) {
83 if (degree!=3) printf("ERROR: for Hermite Curves degree must be 3\n");
85 t2 = fixmul(t,t); t3 = fixmul(t2,t);
87 coord.x = fixmul(coeffs->n.x3,t3) + fixmul(coeffs->n.x2,t2) + fixmul(coeffs->n.x1,t) + coeffs->n.x0;
88 coord.y = fixmul(coeffs->n.y3,t3) + fixmul(coeffs->n.y2,t2) + fixmul(coeffs->n.y1,t) + coeffs->n.y0;
89 coord.z = fixmul(coeffs->n.z3,t3) + fixmul(coeffs->n.z2,t2) + fixmul(coeffs->n.z1,t) + coeffs->n.z0;
95 fix curve_dist(vms_equation *coeffs, int degree, fix t0, vms_vector *p0, fix dist) {
99 if (degree!=3) printf("ERROR: for Hermite Curves degree must be 3\n");
101 for (t=t0;t<1*F1_0;t+=0.001*F1_0) {
102 coord = evaluate_curve(coeffs, 3, t);
103 diff = dist - vm_vec_dist(&coord, p0);
104 if (diff<ACCURACY) //&&(diff>-ACCURACY))
111 void curve_dir(vms_equation *coeffs, int degree, fix t0, vms_vector *dir) {
114 if (degree!=3) printf("ERROR: for Hermite Curves degree must be 3\n");
118 dir->x = fixmul(3*F1_0,fixmul(coeffs->n.x3,t2)) + fixmul(2*F1_0,fixmul(coeffs->n.x2,t0)) + coeffs->n.x1;
119 dir->y = fixmul(3*F1_0,fixmul(coeffs->n.y3,t2)) + fixmul(2*F1_0,fixmul(coeffs->n.y2,t0)) + coeffs->n.y1;
120 dir->z = fixmul(3*F1_0,fixmul(coeffs->n.z3,t2)) + fixmul(2*F1_0,fixmul(coeffs->n.z2,t0)) + coeffs->n.z1;
121 vm_vec_normalize( dir );
125 void plot_parametric(vms_equation *coeffs, fix min_t, fix max_t, fix del_t) {
126 vms_vector coord, dcoord;
130 gr_box( 75, 40, 325, 290 );
131 gr_box( 75, 310, 325, 560 );
132 gr_box( 475, 310, 725, 560 );
133 //gr_pal_fade_in( grd_curscreen->pal );
135 for (t=min_t;t<max_t-del_t;t+=del_t) {
138 coord = evaluate_curve(coeffs, 3, t);
139 dcoord = evaluate_curve(coeffs, 3, dt);
142 gr_line ( 75*F1_0 + coord.x, 290*F1_0 - coord.z, 75*F1_0 + dcoord.x, 290*F1_0 - dcoord.z );
144 gr_line ( 75*F1_0 + coord.x, 560*F1_0 - coord.y, 75*F1_0 + dcoord.x, 560*F1_0 - dcoord.y );
146 gr_line ( 475*F1_0 + coord.z, 560*F1_0 - coord.y, 475*F1_0 + dcoord.z, 560*F1_0 - dcoord.y );
153 vms_vector *vm_vec_interp(vms_vector *result, vms_vector *v0, vms_vector *v1, fix scale) {
156 vm_vec_sub(&tvec, v1, v0);
157 vm_vec_scale_add(result, v0, &tvec, scale);
158 vm_vec_normalize(result);
162 vms_vector p1, p4, r1, r4;
163 vms_vector r4t, r1save;
165 int generate_curve( fix r1scale, fix r4scale ) {
166 vms_vector vec_dir, tvec;
167 vms_vector coord,prev_point;
169 fix enddist, nextdist;
172 fixang rangle, uangle;
174 compute_center_point_on_side( &p1, Cursegp, Curside );
178 extract_right_vector_from_segment(Cursegp, &r1);
179 vm_vec_scale( &r1, -F1_0 );
182 extract_up_vector_from_segment(Cursegp, &r1);
185 extract_right_vector_from_segment(Cursegp, &r1);
188 extract_up_vector_from_segment(Cursegp, &r1);
189 vm_vec_scale( &r1, -F1_0 );
192 extract_forward_vector_from_segment(Cursegp, &r1);
195 extract_forward_vector_from_segment(Cursegp, &r1);
196 vm_vec_scale( &r1, -F1_0 );
200 compute_center_point_on_side( &p4, Markedsegp, Markedside );
202 switch( Markedside ) {
204 extract_right_vector_from_segment(Markedsegp, &r4);
205 extract_up_vector_from_segment(Markedsegp, &r4t);
208 extract_up_vector_from_segment(Markedsegp, &r4);
209 vm_vec_scale( &r4, -F1_0 );
210 extract_forward_vector_from_segment(Markedsegp, &r4t);
211 vm_vec_scale( &r4t, -F1_0 );
214 extract_right_vector_from_segment(Markedsegp, &r4);
215 vm_vec_scale( &r4, -F1_0 );
216 extract_up_vector_from_segment(Markedsegp, &r4t);
219 extract_up_vector_from_segment(Markedsegp, &r4);
220 extract_forward_vector_from_segment(Markedsegp, &r4t);
223 extract_forward_vector_from_segment(Markedsegp, &r4);
224 vm_vec_scale( &r4, -F1_0 );
225 extract_up_vector_from_segment(Markedsegp, &r4t);
228 extract_forward_vector_from_segment(Markedsegp, &r4);
229 extract_up_vector_from_segment(Markedsegp, &r4t);
235 vm_vec_scale(&r1,r1scale);
236 vm_vec_scale(&r4,r4scale);
238 create_curve( &p1, &p4, &r1, &r4, &coeffs );
239 OriginalSeg = Cursegp;
240 OriginalMarkedSeg = Markedsegp;
241 OriginalSide = Curside;
242 OriginalMarkedSide = Markedside;
244 coord = prev_point = p1;
248 enddist = F1_0; nextdist = 0;
249 while ( enddist > fixmul( nextdist, 1.5*F1_0 )) {
250 vms_matrix rotmat,rotmat2;
256 extract_forward_vector_from_segment(Cursegp, &tvec);
257 nextdist = vm_vec_mag(&tvec); // nextdist := distance to next point
258 t = curve_dist(&coeffs, 3, t, &prev_point, nextdist); // t = argument at which function is forward vector magnitude units away from prev_point (in 3-space, not along curve)
259 coord = evaluate_curve(&coeffs, 3, t); // coord := point about forward vector magnitude units away from prev_point
260 enddist = vm_vec_dist(&coord, &p4); // enddist := distance from current to end point, vec_dir used as a temporary variable
261 //vm_vec_normalize(vm_vec_sub(&vec_dir, &coord, &prev_point));
262 vm_vec_normalized_dir(&vec_dir, &coord, &prev_point);
263 if (!med_attach_segment( Cursegp, &New_segment, Curside, AttachSide )) {
264 med_extract_matrix_from_segment( Cursegp,&rotmat ); // rotmat := matrix describing orientation of Cursegp
265 vm_vec_rotate(&tdest,&vec_dir,&rotmat); // tdest := vec_dir in reference frame of Cursegp
268 vm_vector_2_matrix(&rotmat2,&vec_dir,NULL,NULL);
269 // mprintf(0, "[ [%6.2f %6.2f %6.2f]", f2fl(rotmat2.m1), f2fl(rotmat2.m2), f2fl(rotmat2.m3));
270 // mprintf(0, " [%6.2f %6.2f %6.2f]", f2fl(rotmat2.m4), f2fl(rotmat2.m5), f2fl(rotmat2.m6));
271 // mprintf(0, " [%6.2f %6.2f %6.2f] ]\n", f2fl(rotmat2.m7), f2fl(rotmat2.m8), f2fl(rotmat2.m9));
273 med_rotate_segment( Cursegp, &rotmat2 );
275 Curside = Side_opposite[AttachSide];
277 CurveSegs[CurveNumSegs]=Cursegp;
282 extract_up_vector_from_segment( Cursegp,&tvec );
283 uangle = vm_vec_delta_ang( &tvec, &r4t, &r4 );
284 if (uangle >= F1_0 * 1/8) uangle -= F1_0 * 1/4;
285 if (uangle >= F1_0 * 1/8) uangle -= F1_0 * 1/4;
286 if (uangle <= -F1_0 * 1/8) uangle += F1_0 * 1/4;
287 if (uangle <= -F1_0 * 1/8) uangle += F1_0 * 1/4;
288 extract_right_vector_from_segment( Cursegp,&tvec );
289 rangle = vm_vec_delta_ang( &tvec, &r4t, &r4 );
290 if (rangle >= F1_0/8) rangle -= F1_0/4;
291 if (rangle >= F1_0/8) rangle -= F1_0/4;
292 if (rangle <= -F1_0/8) rangle += F1_0/4;
293 if (rangle <= -F1_0/8) rangle += F1_0/4;
295 if ((uangle != 0) && (rangle != 0)) {
296 maxscale = CurveNumSegs*F1_0;
297 // mprintf(0, "Banked Curve Generation.. %f.\n", f2fl(maxscale));
298 generate_banked_curve(maxscale, coeffs);
302 med_form_bridge_segment( Cursegp, Side_opposite[AttachSide], Markedsegp, Markedside );
303 CurveSegs[CurveNumSegs] = &Segments[ Markedsegp->children[Markedside] ];
307 Cursegp = OriginalSeg;
308 Curside = OriginalSide;
310 med_create_new_segment_from_cursegp();
312 //warn_if_concave_segments();
314 if (CurveNumSegs) return 1;
318 void generate_banked_curve(fix maxscale, vms_equation coeffs) {
319 vms_vector vec_dir, tvec, b4r4t;
320 vms_vector coord,prev_point;
321 fix enddist, nextdist;
323 fixang rangle, uangle, angle, scaled_ang=0;
328 extract_up_vector_from_segment( Cursegp,&b4r4t );
329 uangle = vm_vec_delta_ang( &b4r4t, &r4t, &r4 );
330 if (uangle >= F1_0 * 1/8) uangle -= F1_0 * 1/4;
331 if (uangle >= F1_0 * 1/8) uangle -= F1_0 * 1/4;
332 if (uangle <= -F1_0 * 1/8) uangle += F1_0 * 1/4;
333 if (uangle <= -F1_0 * 1/8) uangle += F1_0 * 1/4;
334 // mprintf(0, "up angle %f\n", f2fl(uangle)*360);
336 extract_right_vector_from_segment( Cursegp,&b4r4t );
337 rangle = vm_vec_delta_ang( &b4r4t, &r4t, &r4 );
338 if (rangle >= F1_0/8) rangle -= F1_0/4;
339 if (rangle >= F1_0/8) rangle -= F1_0/4;
340 if (rangle <= -F1_0/8) rangle += F1_0/4;
341 if (rangle <= -F1_0/8) rangle += F1_0/4;
342 // mprintf(0, "right angle %f\n", f2fl(rangle)*360);
345 if (abs(rangle) < abs(uangle)) angle = rangle;
349 coord = prev_point = p1;
351 #define MAGIC_NUM 0.707*F1_0
354 scaled_ang = fixdiv(angle,fixmul(maxscale,MAGIC_NUM));
355 mprintf((0, "scaled angle = %f\n", f2fl(scaled_ang)));
360 enddist = F1_0; nextdist = 0;
361 while ( enddist > fixmul( nextdist, 1.5*F1_0 )) {
362 vms_matrix rotmat,rotmat2;
368 extract_forward_vector_from_segment(Cursegp, &tvec);
369 nextdist = vm_vec_mag(&tvec); // nextdist := distance to next point
370 t = curve_dist(&coeffs, 3, t, &prev_point, nextdist); // t = argument at which function is forward vector magnitude units away from prev_point (in 3-space, not along curve)
371 coord = evaluate_curve(&coeffs, 3, t); // coord := point about forward vector magnitude units away from prev_point
372 enddist = vm_vec_dist(&coord, &p4); // enddist := distance from current to end point, vec_dir used as a temporary variable
373 //vm_vec_normalize(vm_vec_sub(&vec_dir, &coord, &prev_point));
374 vm_vec_normalized_dir(&vec_dir, &coord, &prev_point);
375 if (!med_attach_segment( Cursegp, &New_segment, Curside, AttachSide )) {
376 med_extract_matrix_from_segment( Cursegp,&rotmat ); // rotmat := matrix describing orientation of Cursegp
377 vm_vec_rotate(&tdest,&vec_dir,&rotmat); // tdest := vec_dir in reference frame of Cursegp
379 vm_vec_ang_2_matrix(&rotmat2,&vec_dir,scaled_ang);
380 // mprintf((0, "[ [%6.2f %6.2f %6.2f]", f2fl(rotmat2.m1), f2fl(rotmat2.m2), f2fl(rotmat2.m3)));
381 // mprintf((0, " [%6.2f %6.2f %6.2f]", f2fl(rotmat2.m4), f2fl(rotmat2.m5), f2fl(rotmat2.m6)));
382 // mprintf((0, " [%6.2f %6.2f %6.2f] ]\n", f2fl(rotmat2.m7), f2fl(rotmat2.m8), f2fl(rotmat2.m9)));
384 med_rotate_segment( Cursegp, &rotmat2 );
386 Curside = Side_opposite[AttachSide];
388 CurveSegs[CurveNumSegs]=Cursegp;
396 void delete_curve() {
399 for (i=0; i<CurveNumSegs; i++) {
400 // mprintf((0, "[%d] %d\n", i, CurveSegs[i]->segnum ));
401 if (CurveSegs[i]->segnum != -1)
402 med_delete_segment(CurveSegs[i]);
404 Markedsegp = OriginalMarkedSeg;
405 Markedside = OriginalMarkedSide;
406 Cursegp = OriginalSeg;
407 Curside = OriginalSide;
408 med_create_new_segment_from_cursegp();
410 // mprintf((0, "Num_segments %d\n", Num_segments));
413 //warn_if_concave_segments();
424 vms_vector test, test2, tvec;
431 printf("Enter p1 (x,y,z): ");
432 scanf("%f %f %f", &x, &y, &z);
433 p1.x = x*F1_0; p1.y = y*F1_0; p1.z = z*F1_0;
434 printf("Enter p4 (x,y,z): ");
435 scanf("%f %f %f", &x, &y, &z);
436 p4.x = x*F1_0; p4.y = y*F1_0; p4.z = z*F1_0;
437 printf("Enter r1 <x,y,z>: ");
438 scanf("%f %f %f", &x, &y, &z);
439 r1.x = x*F1_0; r1.y = y*F1_0; r1.z = z*F1_0;
440 printf("Enter r4 <x,y,z>: ");
441 scanf("%f %f %f", &x, &y, &z);
442 r4.x = x*F1_0; r4.y = y*F1_0; r4.z = z*F1_0;
444 create_curve( &p1, &p4, &r1, &r4, &coeffs );
447 printf("x [%6.3f %6.3f %6.3f %6.3f]\n", f2fl(coeffs.n.x3), f2fl(coeffs.n.x2), f2fl(coeffs.n.x1), f2fl(coeffs.n.x0));
448 printf(" y [%6.3f %6.3f %6.3f %6.3f]\n", f2fl(coeffs.n.y3), f2fl(coeffs.n.y2), f2fl(coeffs.n.y1), f2fl(coeffs.n.y0));
449 printf(" z [%6.3f %6.3f %6.3f %6.3f]\n", f2fl(coeffs.n.z3), f2fl(coeffs.n.z2), f2fl(coeffs.n.z1), f2fl(coeffs.n.z0));
451 printf("\nChecking direction vectors.\n");
453 for (t=0*F1_0;t<1*F1_0;t+=0.1*F1_0) {
454 curve_dir(&coeffs, 3, t, &test);
455 printf(" t = %.3f dir = <%6.3f, %6.3f, %6.3f >\n", f2fl(t), f2fl(test.x), f2fl(test.y), f2fl(test.z) );
458 printf("\nChecking distance function.\n");
459 printf("Enter a distance: ");
462 printf("Enter a (0<t<1) value: ");
466 gr_init(15); // 800x600 mode
467 plot_parametric(&coeffs, 0*F1_0, 1*F1_0, 0.05*F1_0);
469 test = evaluate_curve(&coeffs, 3, t0);
470 t = curve_dist(&coeffs, 3, t0, &test, distance);
471 test2 = evaluate_curve(&coeffs, 3, t);
473 dist = vm_vec_mag(vm_vec_sub(&tvec, &test, &test2));
477 gr_rect( 74+f2fl(test.x), 289-f2fl(test.z), 76+f2fl(test.x), 291-f2fl(test.z) );
478 gr_rect( 74+f2fl(test.x), 559-f2fl(test.y), 76+f2fl(test.x), 561-f2fl(test.y) );
479 gr_rect( 474+f2fl(test.z), 559-f2fl(test.y), 476+f2fl(test.z), 561-f2fl(test.y) );
481 gr_rect( 74+f2fl(test2.x), 289-f2fl(test2.z), 76+f2fl(test2.x), 291-f2fl(test2.z) );
482 gr_rect( 74+f2fl(test2.x), 559-f2fl(test2.y), 76+f2fl(test2.x), 561-f2fl(test2.y) );
483 gr_rect( 474+f2fl(test2.z), 559-f2fl(test2.y), 476+f2fl(test2.z), 561-f2fl(test2.y) );
488 if (key == KEY_ESC) break;
489 else key = key_getch();
495 printf("From t=%.3f to t=1.000, ", f2fl(t0));
496 printf("two points separated by the distance %.3f\n do not exist on this curve.\n", x);
499 printf("\nThe distance between points at:\n");
500 printf(" t0 = %.3f ( %6.3f,%6.3f,%6.3f ) and\n", f2fl(t0), f2fl(test.x), f2fl(test.y), f2fl(test.z));
501 printf(" t = %.3f ( %6.3f,%6.3f,%6.3f ) is:\n", f2fl(t), f2fl(test2.x), f2fl(test2.y), f2fl(test2.z));
502 printf(" expected: %.3f\n", x);
503 printf(" actual : %.3f\n", f2fl(dist) );