1 /* -*- Mode: C; tab-width: 4 -*- */
2 /* glhanoi, Copyright (c) 2005, 2009 Dave Atkinson <da@davea.org.uk>
3 * except noise function code Copyright (c) 2002 Ken Perlin
4 * Modified by Lars Huttar (c) 2010, to generalize to 4 or more poles
5 *
6 * Permission to use, copy, modify, distribute, and sell this software and its
7 * documentation for any purpose is hereby granted without fee, provided that
8 * the above copyright notice appear in all copies and that both that
9 * copyright notice and this permission notice appear in supporting
10 * documentation. No representations are made about the suitability of this
11 * software for any purpose. It is provided "as is" without express or
12 * implied warranty.
13 */
14
15 #include <assert.h>
16
17 #include "rotator.h"
18
19 #define DEF_LIGHT "True"
20 #define DEF_FOG "False"
21 #define DEF_TEXTURE "True"
22 #define DEF_POLES "0" /* choose random value */
23 #define DEF_SPEED "1"
24 #define DEF_TRAILS "2"
25
26 #define DEFAULTS "*delay: 15000\n" \
27 "*count: 0\n" \
28 "*showFPS: False\n" \
29 "*wireframe: False\n"
30
31 # define release_glhanoi 0
32
33 /* polygon resolution of poles and disks */
34 #define NSLICE 32
35 #define NLOOPS 1
36
37 /* How long to wait at start and finish (seconds). */
38 #define START_DURATION 1.0
39 #define FINISH_DURATION 1.0
40 #define BASE_LENGTH 30.0
41 #define BOARD_SQUARES 8
42
43 /* Don't draw trail lines till they're this old (sec).
44 Helps trails not be "attached" to the disks. */
45 #define TRAIL_START_DELAY 0.1
46
47 #define MAX_CAMERA_RADIUS 250.0
48 #define MIN_CAMERA_RADIUS 75.0
49
50 #define MARBLE_SCALE 1.01
51
52 #undef BELLRAND
53 /* Return a double precision number in [0...n], with bell curve distribution. */
54 #define BELLRAND(n) ((frand((n)) + frand((n)) + frand((n))) / 3)
55
56 enum {
57 MARBLE_TEXURE,
58 N_TEXTURES
59 };
60
61 #define MARBLE_TEXTURE_SIZE 256
62
63 #undef countof
64 #define countof(x) (sizeof((x))/sizeof((*x)))
65
66 #include <math.h>
67 #include "xlockmore.h"
68
69 #ifdef USE_GL /* whole file */
70
71 typedef struct timeval glhtime;
72
getTime(void)73 static double getTime(void)
74 {
75 struct timeval t;
76 #ifdef GETTIMEOFDAY_TWO_ARGS
77 gettimeofday(&t, NULL);
78 #else /* !GETTIMEOFDAY_TWO_ARGS */
79 gettimeofday(&t);
80 #endif /* !GETTIMEOFDAY_TWO_ARGS */
81 return t.tv_sec + t.tv_usec / 1000000.0;
82 }
83
84 typedef enum {
85 START,
86 MOVE_DISK,
87 MOVE_FINISHED,
88 FINISHED,
89 MONEY_SHOT,
90 INVALID = -1
91 } State;
92
93 typedef struct {
94 int id;
95 GLuint displayList;
96 GLfloat position[3];
97 GLfloat rotation[3];
98 GLfloat color[4];
99 GLfloat base0;
100 GLfloat base1;
101 GLfloat height;
102 GLfloat xmin, xmax, ymin, zmin, zmax;
103 GLfloat u1, u2;
104 GLfloat t1, t2;
105 GLfloat ucostheta, usintheta;
106 GLfloat dx, dz;
107 GLdouble rotAngle; /* degree of "flipping" so far, during travel */
108 GLdouble phi; /* angle of motion in xz plane */
109 GLfloat speed;
110 int polys;
111 } Disk;
112
113 typedef struct {
114 Disk **data;
115 int count;
116 int size;
117 GLfloat position[3];
118 } Pole;
119
120 /* A SubProblem is a recursive subdivision of the problem, and means
121 "Move nDisks disks from src pole to dst pole, using the poles indicated in 'available'." */
122 typedef struct {
123 int nDisks;
124 int src, dst;
125 unsigned long available; /* a bitmask of poles that have no smaller disks on them */
126 } SubProblem;
127
128 typedef struct {
129 GLfloat position[3];
130 double startTime, endTime;
131 Bool isEnd;
132 } TrailPoint;
133
134 typedef struct {
135 GLXContext *glx_context;
136 State state;
137 Bool wire;
138 Bool fog;
139 Bool light;
140 Bool layoutLinear;
141 GLfloat trailDuration;
142 double startTime;
143 double lastTime;
144 double duration;
145 int numberOfDisks;
146 int numberOfPoles;
147 int numberOfMoves;
148 int maxDiskIdx;
149 int magicNumber;
150 Disk *currentDisk;
151 int move;
152 /* src, tmp, dst: index of pole that is source / storage / destination for
153 current move */
154 int src;
155 int tmp;
156 int dst;
157 int oldsrc;
158 int oldtmp;
159 int olddst;
160 GLfloat speed; /* coefficient for how fast the disks move */
161 SubProblem *solveStack;
162 int solveStackSize, solveStackIdx;
163 Pole *pole;
164 float boardSize;
165 float baseLength;
166 float baseWidth;
167 float baseHeight;
168 float poleRadius;
169 float poleHeight;
170 float poleOffset;
171 float poleDist; /* distance of poles from center, for round layout */
172 float diskHeight;
173 float maxDiskRadius;
174 float *diskPos; /* pre-computed disk positions on rods */
175 Disk *disk;
176 GLint floorList;
177 GLint baseList;
178 GLint poleList;
179 int floorpolys, basepolys, polepolys;
180 int trailQSize;
181 TrailPoint *trailQ;
182 int trailQFront, trailQBack;
183 GLfloat camera[3];
184 GLfloat centre[3];
185 rotator *the_rotator;
186 Bool button_down_p;
187 Bool texture;
188 GLuint textureNames[N_TEXTURES];
189 int drag_x;
190 int drag_y;
191 int noise_initted;
192 int p[512];
193 } glhcfg;
194
195 static glhcfg *glhanoi_cfg = NULL;
196 static Bool fog;
197 static Bool light;
198 static Bool texture;
199 static GLfloat trails;
200 static int poles;
201 static GLfloat speed;
202
203 static XrmOptionDescRec opts[] = {
204 {"-light", ".glhanoi.light", XrmoptionNoArg, "true"},
205 {"+light", ".glhanoi.light", XrmoptionNoArg, "false"},
206 {"-fog", ".glhanoi.fog", XrmoptionNoArg, "true"},
207 {"+fog", ".glhanoi.fog", XrmoptionNoArg, "false"},
208 {"-texture", ".glhanoi.texture", XrmoptionNoArg, "true"},
209 {"+texture", ".glhanoi.texture", XrmoptionNoArg, "false"},
210 {"-trails", ".glhanoi.trails", XrmoptionSepArg, 0},
211 {"-poles", ".glhanoi.poles", XrmoptionSepArg, 0 },
212 {"-speed", ".glhanoi.speed", XrmoptionSepArg, 0 }
213 };
214
215 static argtype vars[] = {
216 {&light, "light", "Light", DEF_LIGHT, t_Bool},
217 {&fog, "fog", "Fog", DEF_FOG, t_Bool},
218 {&texture, "texture", "Texture", DEF_TEXTURE, t_Bool},
219 {&trails, "trails", "Trails", DEF_TRAILS, t_Float},
220 {&poles, "poles", "Poles", DEF_POLES, t_Int},
221 {&speed, "speed", "Speed", DEF_SPEED, t_Float}
222 };
223
224 static OptionStruct desc[] = {
225 {"+/-light", "whether to light the scene"},
226 {"+/-fog", "whether to apply fog to the scene"},
227 {"+/-texture", "whether to apply texture to the scene"},
228 {"-trails t", "how long of disk trails to show (sec.)"},
229 {"-poles r", "number of poles to move disks between"},
230 {"-speed s", "speed multiplier"}
231 };
232
233 ENTRYPOINT ModeSpecOpt glhanoi_opts = { countof(opts), opts, countof(vars), vars, desc };
234
235 #ifdef USE_MODULES
236
237 ModStruct glhanoi_description = {
238 "glhanoi", "init_glhanoi", "draw_glhanoi", NULL,
239 "draw_glhanoi", "init_glhanoi", "free_glhanoi", &glhanoi_opts,
240 1000, 1, 2, 1, 4, 1.0, "",
241 "Towers of Hanoi", 0, NULL
242 };
243
244 #endif
245
246 static const GLfloat cBlack[] = { 0.0, 0.0, 0.0, 1.0 };
247 static const GLfloat cWhite[] = { 1.0, 1.0, 1.0, 1.0 };
248 static const GLfloat poleColor[] = { 0.545, 0.137, 0.137 };
249 static const GLfloat baseColor[] = { 0.34, 0.34, 0.48 };
250 /* static const GLfloat baseColor[] = { 0.545, 0.137, 0.137 }; */
251 static const GLfloat fogcolor[] = { 0.5, 0.5, 0.5 };
252 static GLfloat trailColor[] = { 1.0, 1.0, 1.0, 0.5 };
253
254 static const float left[] = { 1.0, 0.0, 0.0 };
255 static const float up[] = { 0.0, 1.0, 0.0 };
256 static const float front[] = { 0.0, 0.0, 1.0 };
257 static const float right[] = { -1.0, 0.0, 0.0 };
258 static const float down[] = { 0.0, -1.0, 0.0 };
259 static const float back[] = { 0.0, 0.0, -1.0 };
260
261 static const GLfloat pos0[4] = { 50.0, 50.0, 50.0, 0.0 };
262 static const GLfloat amb0[4] = { 0.0, 0.0, 0.0, 1.0 };
263 static const GLfloat dif0[4] = { 1.0, 1.0, 1.0, 1.0 };
264 static const GLfloat spc0[4] = { 0.0, 1.0, 1.0, 1.0 };
265
266 static const GLfloat pos1[4] = { -50.0, 50.0, -50.0, 0.0 };
267 static const GLfloat amb1[4] = { 0.0, 0.0, 0.0, 1.0 };
268 static const GLfloat dif1[4] = { 1.0, 1.0, 1.0, 1.0 };
269 static const GLfloat spc1[4] = { 1.0, 1.0, 1.0, 1.0 };
270
271 static float g = 3.0 * 9.80665; /* hmm, looks like we need more gravity, Scotty... */
272
checkAllocAndExit(Bool item,char * descr)273 static void checkAllocAndExit(Bool item, char *descr) {
274 if (!item) {
275 fprintf(stderr, "%s: unable to allocate memory for %s\n",
276 progname, descr);
277 exit(EXIT_FAILURE);
278 }
279 }
280
281 #define DOPUSH(X, Y) (((X)->count) >= ((X)->size)) ? NULL : ((X)->data[(X)->count++] = (Y))
282 #define DOPOP(X) (X)->count <= 0 ? NULL : ((X)->data[--((X)->count)])
283
284 /* push disk d onto pole idx */
push(glhcfg * glhanoi,int idx,Disk * d)285 static Disk *push(glhcfg *glhanoi, int idx, Disk * d)
286 {
287 return DOPUSH(&glhanoi->pole[idx], d);
288 }
289
290 /* pop the top disk from pole idx */
pop(glhcfg * glhanoi,int idx)291 static Disk *pop(glhcfg *glhanoi, int idx)
292 {
293 return DOPOP(&glhanoi->pole[idx]);
294 }
295
swap(int * x,int * y)296 static inline void swap(int *x, int *y)
297 {
298 *x = *x ^ *y;
299 *y = *x ^ *y;
300 *x = *x ^ *y;
301 }
302
303 /*
304 * magic - it's magic...
305 * Return 1 if the number of trailing zeroes on i is even, unless i is 1 or 0.
306 */
magic(int i)307 static int magic(int i)
308 {
309 int count = 0;
310 if(i <= 1)
311 return 0;
312 while((i & 0x01) == 0) {
313 i >>= 1;
314 count++;
315 }
316 return count % 2 == 0;
317 }
318
distance(float * p0,float * p1)319 static float distance(float *p0, float *p1)
320 {
321 float x, y, z;
322 x = p1[0] - p0[0];
323 y = p1[1] - p0[1];
324 z = p1[2] - p0[2];
325 return (float)sqrt(x * x + y * y + z * z);
326 }
327
328 /* What is this for?
329 = c / (a b - 0.25 (a^2 + 2 a b + b^2) )
330 = c / (-0.25 (a^2 - 2 a b + b^2) )
331 = c / (-0.25 ((a - b)(a - b)))
332 = -4 c / (a - b)^2
333 static GLfloat A(GLfloat a, GLfloat b, GLfloat c)
334 {
335 GLfloat sum = a + b;
336 return c / (a * b - 0.25 * sum * sum);
337 }
338 */
339
moveSetup(glhcfg * glhanoi,Disk * disk)340 static void moveSetup(glhcfg *glhanoi, Disk * disk)
341 {
342 float h, ymax;
343 float u;
344 int src = glhanoi->src;
345 int dst = glhanoi->dst;
346 GLfloat theta;
347 GLfloat sintheta, costheta;
348 double dh;
349 double dx, dz; /* total x and z distances from src to dst */
350 Pole *poleSrc, *poleDst;
351
352 poleSrc = &(glhanoi->pole[src]);
353 poleDst = &(glhanoi->pole[dst]);
354
355 disk->xmin = poleSrc->position[0];
356 /* glhanoi->poleOffset * (src - (glhanoi->numberOfPoles - 1.0f) * 0.5); */
357 disk->xmax = poleDst->position[0];
358 /* disk->xmax = glhanoi->poleOffset * (dst - (glhanoi->numberOfPoles - 1.0f) * 0.5); */
359 disk->ymin = glhanoi->poleHeight;
360 disk->zmin = poleSrc->position[2];
361 disk->zmax = poleDst->position[2];
362
363 dx = disk->xmax - disk->xmin;
364 dz = disk->zmax - disk->zmin;
365
366 if(glhanoi->state != FINISHED) {
367 double xxx = ((dx < 0) ? 180.0 : -180.0);
368 if(random() % 6 == 0) {
369 disk->rotAngle = xxx * (2 - 2 * random() % 2) * (random() % 3 + 1);
370 } else {
371 disk->rotAngle = xxx;
372 }
373 if(random() % 4 == 0) {
374 /* Backflip */
375 disk->rotAngle = -disk->rotAngle;
376 }
377 } else {
378 disk->rotAngle = -180.0;
379 }
380
381 disk->base0 = glhanoi->diskPos[poleSrc->count];
382 disk->base1 = (glhanoi->state == FINISHED) ?
383 disk->base0 : glhanoi->diskPos[poleDst->count];
384
385 /* horizontal distance to travel? */
386 /* was: absx = sqrt(disk->xmax - disk->xmin); */
387 dh = distance(poleSrc->position, poleDst->position);
388 /* absx = sqrt(dh); */
389 ymax = glhanoi->poleHeight + dh;
390 if(glhanoi->state == FINISHED) {
391 ymax += dh * (double)(glhanoi->numberOfDisks - disk->id);
392 }
393 h = ymax - disk->ymin;
394 /* A(a, b, c) = -4 c / (a - b)^2 */
395 /* theta = atan(4 h / (b - a)) */
396 theta = atan(4 * h / dh);
397 if(theta < 0.0)
398 theta += M_PI;
399 costheta = cos(theta);
400 sintheta = sin(theta);
401 u = (float)
402 sqrt(fabs
403 (-g /
404 /* (2.0 * A(disk->xmin, disk->xmax, h) * costheta * costheta))); */
405 (2.0 * -4 * h / (dh * dh) * costheta * costheta)));
406 disk->usintheta = u * sintheta;
407 disk->ucostheta = u * costheta;
408 /* Not to be confused: disk->dx is the per-time-unit portion of dx */
409 disk->dx = disk->ucostheta * dx / dh;
410 disk->dz = disk->ucostheta * dz / dh;
411 disk->t1 =
412 (-u + sqrt(u * u + 2.0 * g * fabs(disk->ymin - disk->base0))) / g;
413 disk->u1 = u + g * disk->t1;
414 disk->t2 = 2.0 * disk->usintheta / g;
415 disk->u2 = disk->usintheta - g * disk->t2;
416
417 /* Compute direction of travel, in the XZ plane. */
418 disk->phi = atan(dz / dx);
419 disk->phi *= 180.0 / M_PI; /* convert radians to degrees */
420 }
421
422 /* For debugging: show a value as a string of ones and zeroes
423 static const char *byteToBinary(int x) {
424 static char b[9];
425 int i, z;
426
427 for (z = 128, i = 0; z > 0; z >>= 1, i++) {
428 b[i] = ((x & z) == z) ? '1' : '0';
429 }
430 b[i] = '\0';
431
432 return b;
433 }
434 */
435
pushMove(glhcfg * glhanoi,int n,int src,int dst,int avail)436 static void pushMove(glhcfg *glhanoi, int n, int src, int dst, int avail) {
437 SubProblem *sp = &(glhanoi->solveStack[glhanoi->solveStackIdx++]);
438
439 if (glhanoi->solveStackIdx > glhanoi->solveStackSize) {
440 fprintf(stderr, "solveStack overflow: pushed index %d: %d from %d to %d, using %d\n",
441 glhanoi->solveStackIdx, n, src, dst, avail);
442 exit(EXIT_FAILURE);
443 }
444
445 sp->nDisks = n;
446 sp->src = src;
447 sp->dst = dst;
448 sp->available = avail & ~((unsigned long)(1 << src))
449 & ~((unsigned long)(1 << dst));
450 /*
451 fprintf(stderr, "Debug: > pushed solveStack %d: %d from %d to %d, using %s\n",
452 glhanoi->solveStackIdx - 1, n, src, dst, byteToBinary(sp->available));
453 */
454 }
455
solveStackEmpty(glhcfg * glhanoi)456 static Bool solveStackEmpty(glhcfg *glhanoi) {
457 return (glhanoi->solveStackIdx < 1);
458 }
459
popMove(glhcfg * glhanoi)460 static SubProblem *popMove(glhcfg *glhanoi) {
461 SubProblem *sp;
462 if (solveStackEmpty(glhanoi)) return (SubProblem *)NULL;
463 sp = &(glhanoi->solveStack[--glhanoi->solveStackIdx]);
464 /* fprintf(stderr, "Debug: < popped solveStack %d: %d from %d to %d, using %s\n",
465 glhanoi->solveStackIdx, sp->nDisks, sp->src, sp->dst, byteToBinary(sp->available)); */
466 return sp;
467 }
468
469 /* Return number of bits set in b */
numBits(unsigned long b)470 static int numBits(unsigned long b) {
471 int count = 0;
472 while (b) {
473 count += b & 0x1u;
474 b >>= 1;
475 }
476 return count;
477 }
478
479 /* Return index (power of 2) of least significant 1 bit. */
bitScan(unsigned long b)480 static int bitScan(unsigned long b) {
481 int count;
482 for (count = 0; b; count++, b >>= 1) {
483 if (b & 0x1u) return count;
484 }
485 return -1;
486 }
487
488 /* A bit pattern representing all poles */
489 #define ALL_POLES ((1 << glhanoi->numberOfPoles) - 1)
490
491 #define REMOVE_BIT(a, b) ((a) & ~(1 << (b)))
492 #define ADD_BIT(a, b) ((a) | (1 << (b)))
493
makeMove(glhcfg * glhanoi)494 static void makeMove(glhcfg *glhanoi)
495 {
496 if (glhanoi->numberOfPoles == 3) {
497 int fudge = glhanoi->move + 2;
498 int magicNumber = magic(fudge);
499
500
501 glhanoi->currentDisk = pop(glhanoi, glhanoi->src);
502 moveSetup(glhanoi, glhanoi->currentDisk);
503 push(glhanoi, glhanoi->dst, glhanoi->currentDisk);
504
505 fudge = fudge % 2;
506
507 if(fudge == 1 || magicNumber) {
508 swap(&glhanoi->src, &glhanoi->tmp);
509 }
510 if(fudge == 0 || glhanoi->magicNumber) {
511 swap(&glhanoi->dst, &glhanoi->tmp);
512 }
513 glhanoi->magicNumber = magicNumber;
514 } else {
515 SubProblem sp;
516 int tmp = 0;
517
518 if (glhanoi->move == 0) {
519 /* Initialize the solution stack. Original problem:
520 move all disks from pole 0 to furthest pole,
521 using all other poles. */
522 pushMove(glhanoi, glhanoi->numberOfDisks, 0,
523 glhanoi->numberOfPoles - 1,
524 REMOVE_BIT(REMOVE_BIT(ALL_POLES, 0), glhanoi->numberOfPoles - 1));
525 }
526
527 while (!solveStackEmpty(glhanoi)) {
528 int k, numAvail;
529 sp = *popMove(glhanoi);
530
531 if (sp.nDisks == 1) {
532 /* We have a single, concrete move to do. */
533 /* moveSetup uses glhanoi->src, dst. */
534 glhanoi->src = sp.src;
535 glhanoi->dst = sp.dst;
536 glhanoi->tmp = tmp; /* Probably unnecessary */
537
538 glhanoi->currentDisk = pop(glhanoi, sp.src);
539 moveSetup(glhanoi, glhanoi->currentDisk);
540 push(glhanoi, sp.dst, glhanoi->currentDisk);
541
542 return;
543 } else {
544 /* Divide and conquer, using Frame-Stewart algorithm, until we get to base case */
545 if (sp.nDisks == 1) break;
546
547 numAvail = numBits(sp.available);
548 if (numAvail < 2) k = sp.nDisks - 1;
549 else if(numAvail >= sp.nDisks - 2) k = 1;
550 /* heuristic for optimal k: sqrt(2n) (see http://www.cs.wm.edu/~pkstoc/boca.pdf) */
551 else k = (int)(sqrt(2 * sp.nDisks));
552
553 if (k >= sp.nDisks) k = sp.nDisks - 1;
554 else if (k < 1) k = 1;
555
556 tmp = bitScan(sp.available);
557 /* fprintf(stderr, "Debug: k is %d, tmp is %d\n", k, tmp); */
558 if (tmp == -1) {
559 fprintf(stderr, "Error: n > 1 (%d) and no poles available\n",
560 sp.nDisks);
561 }
562
563 /* Push on moves in reverse order, since this is a stack. */
564 pushMove(glhanoi, k, tmp, sp.dst,
565 REMOVE_BIT(ADD_BIT(sp.available, sp.src), tmp));
566 pushMove(glhanoi, sp.nDisks - k, sp.src, sp.dst,
567 REMOVE_BIT(sp.available, tmp));
568 pushMove(glhanoi, k, sp.src, tmp,
569 REMOVE_BIT(ADD_BIT(sp.available, sp.dst), tmp));
570
571 /* Repeat until we've found a move we can make. */
572 }
573 }
574 }
575 }
576
lerp(double alpha,double start,double end)577 static double lerp(double alpha, double start, double end)
578 {
579 return start + alpha * (end - start);
580 }
581
upfunc(GLdouble t,Disk * d)582 static void upfunc(GLdouble t, Disk * d)
583 {
584 d->position[0] = d->xmin;
585 d->position[1] = d->base0 + (d->u1 - 0.5 * g * t) * t;
586 d->position[2] = d->zmin;
587
588 d->rotation[1] = 0.0;
589 }
590
parafunc(GLdouble t,Disk * d)591 static void parafunc(GLdouble t, Disk * d)
592 {
593 /* ##was: d->position[0] = d->xmin + d->ucostheta * t; */
594 d->position[0] = d->xmin + d->dx * t;
595 d->position[2] = d->zmin + d->dz * t;
596 d->position[1] = d->ymin + (d->usintheta - 0.5 * g * t) * t;
597
598 d->rotation[1] = d->rotAngle * t / d->t2;
599 /* d->rotAngle * (d->position[0] - d->xmin) / (d->xmax - d->xmin); */
600 }
601
downfunc(GLdouble t,Disk * d)602 static void downfunc(GLdouble t, Disk * d)
603 {
604 d->position[0] = d->xmax;
605 d->position[1] = d->ymin + (d->u2 - 0.5 * g * t) * t;
606 d->position[2] = d->zmax;
607
608 d->rotation[1] = 0.0;
609 }
610
611 #define normalizeQ(i) ((i) >= glhanoi->trailQSize ? (i) - glhanoi->trailQSize : (i))
612 #define normalizeQNeg(i) ((i) < 0 ? (i) + glhanoi->trailQSize : (i))
613
614 /* Add trail point at position posn at time t onto back of trail queue.
615 Removes old trails if necessary to make room. */
enQTrail(glhcfg * glhanoi,GLfloat * posn)616 static void enQTrail(glhcfg *glhanoi, GLfloat *posn)
617 {
618 if (glhanoi->trailQSize && glhanoi->state != MONEY_SHOT) {
619 TrailPoint *tp = &(glhanoi->trailQ[glhanoi->trailQBack]);
620 double t = getTime();
621
622 tp->position[0] = posn[0];
623 tp->position[1] = posn[1] + glhanoi->diskHeight;
624 /* Slight jitter to prevent clashing with other trails */
625 tp->position[2] = posn[2] + (glhanoi->move % 23) * 0.01;
626 tp->startTime = t + TRAIL_START_DELAY;
627 tp->endTime = t + TRAIL_START_DELAY + glhanoi->trailDuration;
628 tp->isEnd = False;
629
630 /* Update queue back/front indices */
631 glhanoi->trailQBack = normalizeQ(glhanoi->trailQBack + 1);
632 if (glhanoi->trailQBack == glhanoi->trailQFront)
633 glhanoi->trailQFront = normalizeQ(glhanoi->trailQFront + 1);
634 }
635 }
636
637 /* Mark last trailpoint in queue as the end of a trail. */
638 /* was: #define endTrail(glh) ((glh)->trailQ[(glh)->trailQBack].isEnd = True) */
endTrail(glhcfg * glhanoi)639 static void endTrail(glhcfg *glhanoi) {
640 if (glhanoi->trailQSize)
641 glhanoi->trailQ[normalizeQNeg(glhanoi->trailQBack - 1)].isEnd = True;
642 }
643
644 /* Update disk d's position and rotation based on time t.
645 Returns true iff move is finished. */
computePosition(glhcfg * glhanoi,GLfloat t,Disk * d)646 static Bool computePosition(glhcfg *glhanoi, GLfloat t, Disk * d)
647 {
648 Bool finished = False;
649
650 if(t < d->t1) {
651 upfunc(t, d);
652 } else if(t < d->t1 + d->t2) {
653 parafunc(t - d->t1, d);
654 enQTrail(glhanoi, d->position);
655 } else {
656 downfunc(t - d->t1 - d->t2, d);
657 if(d->position[1] <= d->base1) {
658 d->position[1] = d->base1;
659 finished = True;
660 endTrail(glhanoi);
661 }
662 }
663 return finished;
664 }
665
updateView(glhcfg * glhanoi)666 static void updateView(glhcfg *glhanoi)
667 {
668 double longitude, latitude, radius;
669 double a, b, c, A, B;
670
671 get_position(glhanoi->the_rotator, NULL, NULL, &radius,
672 !glhanoi->button_down_p);
673 get_rotation(glhanoi->the_rotator, &longitude, &latitude, NULL,
674 !glhanoi->button_down_p);
675 longitude += glhanoi->camera[0];
676 latitude += glhanoi->camera[1];
677 radius += glhanoi->camera[2];
678 /* FUTURE: tweak this to be smooth: */
679 longitude = longitude - floor(longitude);
680 latitude = latitude - floor(latitude);
681 radius = radius - floor(radius);
682 if(latitude > 0.5) {
683 latitude = 1.0 - latitude;
684 }
685 if(radius > 0.5) {
686 radius = 1.0 - radius;
687 }
688
689 b = glhanoi->centre[1];
690 c = (MIN_CAMERA_RADIUS +
691 radius * (MAX_CAMERA_RADIUS - MIN_CAMERA_RADIUS));
692 A = M_PI / 4.0 * (1.0 - latitude);
693 a = sqrt(b * b + c * c - 2.0 * b * c * cos(A));
694 B = asin(sin(A) * b / a);
695 glRotatef(-B * 180 / M_PI, 1.0, 0.0, 0.0);
696
697 glTranslatef(0.0f, 0.0f,
698 -(MIN_CAMERA_RADIUS +
699 radius * (MAX_CAMERA_RADIUS - MIN_CAMERA_RADIUS)));
700 glRotatef(longitude * 360.0, 0.0f, 1.0f, 0.0f);
701 glRotatef(latitude * 180.0, cos(longitude * 2.0 * M_PI), 0.0,
702 sin(longitude * 2.0 * M_PI));
703 }
704
changeState(glhcfg * glhanoi,State state)705 static void changeState(glhcfg *glhanoi, State state)
706 {
707 glhanoi->state = state;
708 glhanoi->startTime = getTime();
709 }
710
finishedHanoi(glhcfg * glhanoi)711 static Bool finishedHanoi(glhcfg *glhanoi) {
712 /* use different criteria depending on algorithm */
713 return (glhanoi->numberOfPoles == 3 ?
714 glhanoi->move >= glhanoi->numberOfMoves :
715 solveStackEmpty(glhanoi));
716 }
717
update_glhanoi(glhcfg * glhanoi)718 static void update_glhanoi(glhcfg *glhanoi)
719 {
720 double t = getTime() - glhanoi->startTime;
721 int i;
722 Bool done;
723
724 switch (glhanoi->state) {
725 case START:
726 if(t < glhanoi->duration) {
727 break;
728 }
729 glhanoi->move = 0;
730 if(glhanoi->numberOfDisks % 2 == 0) {
731 swap(&glhanoi->tmp, &glhanoi->dst);
732 }
733 glhanoi->magicNumber = 1;
734 makeMove(glhanoi);
735 changeState(glhanoi, MOVE_DISK);
736 break;
737
738 case MOVE_DISK:
739 if(computePosition(glhanoi, t * glhanoi->currentDisk->speed, glhanoi->currentDisk)) {
740 changeState(glhanoi, MOVE_FINISHED);
741 }
742 break;
743
744 case MOVE_FINISHED:
745 ++glhanoi->move;
746 if(!finishedHanoi(glhanoi)) {
747 makeMove(glhanoi);
748 changeState(glhanoi, MOVE_DISK);
749 } else {
750 glhanoi->duration = FINISH_DURATION;
751 changeState(glhanoi, FINISHED);
752 }
753 break;
754
755 case FINISHED:
756 if (t < glhanoi->duration)
757 break;
758 glhanoi->src = glhanoi->olddst;
759 glhanoi->dst = glhanoi->oldsrc;
760 for(i = 0; i < glhanoi->numberOfDisks; ++i) {
761 Disk *disk = pop(glhanoi, glhanoi->src);
762 assert(disk != NULL);
763 moveSetup(glhanoi, disk);
764 }
765 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
766 push(glhanoi, glhanoi->dst, &glhanoi->disk[i]);
767 }
768 changeState(glhanoi, MONEY_SHOT);
769 break;
770
771 case MONEY_SHOT:
772 done = True;
773 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
774 double delay = 0.25 * i;
775 int finished;
776
777 if(t - delay < 0) {
778 done = False;
779 continue;
780 }
781
782 finished = computePosition(glhanoi, t - delay, &glhanoi->disk[i]);
783 glhanoi->disk[i].rotation[1] = 0.0;
784
785 if(!finished) {
786 done = False;
787 }
788 }
789 if(done) {
790 glhanoi->src = glhanoi->oldsrc;
791 glhanoi->tmp = glhanoi->oldtmp;
792 glhanoi->dst = glhanoi->olddst;
793 changeState(glhanoi, START);
794 }
795 break;
796
797 case INVALID:
798 default:
799 fprintf(stderr, "Invalid state\n");
800 break;
801 }
802 }
803
HSVtoRGBf(GLfloat h,GLfloat s,GLfloat v,GLfloat * r,GLfloat * g,GLfloat * b)804 static void HSVtoRGBf(GLfloat h, GLfloat s, GLfloat v,
805 GLfloat * r, GLfloat * g, GLfloat * b)
806 {
807 if(s == 0.0) {
808 *r = v;
809 *g = v;
810 *b = v;
811 } else {
812 GLfloat i, f, p, q, t;
813 if(h >= 360.0) {
814 h = 0.0;
815 }
816 h /= 60.0; /* h now in [0,6). */
817 i = floor((double)h); /* i now largest integer <= h */
818 f = h - i; /* f is no fractional part of h */
819 p = v * (1.0 - s);
820 q = v * (1.0 - (s * f));
821 t = v * (1.0 - (s * (1.0 - f)));
822 switch ((int)i) {
823 case 0:
824 *r = v;
825 *g = t;
826 *b = p;
827 break;
828 case 1:
829 *r = q;
830 *g = v;
831 *b = p;
832 break;
833 case 2:
834 *r = p;
835 *g = v;
836 *b = t;
837 break;
838 case 3:
839 *r = p;
840 *g = q;
841 *b = v;
842 break;
843 case 4:
844 *r = t;
845 *g = p;
846 *b = v;
847 break;
848 case 5:
849 *r = v;
850 *g = p;
851 *b = q;
852 break;
853 }
854 }
855 }
856
HSVtoRGBv(GLfloat * hsv,GLfloat * rgb)857 static void HSVtoRGBv(GLfloat * hsv, GLfloat * rgb)
858 {
859 HSVtoRGBf(hsv[0], hsv[1], hsv[2], &rgb[0], &rgb[1], &rgb[2]);
860 }
861
setMaterial(const GLfloat color[3],const GLfloat hlite[3],int shininess)862 static void setMaterial(const GLfloat color[3], const GLfloat hlite[3], int shininess)
863 {
864 glColor3fv(color);
865 glMaterialfv(GL_FRONT, GL_SPECULAR, hlite);
866 glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color);
867 glMateriali(GL_FRONT, GL_SHININESS, shininess); /* [0,128] */
868 }
869
870 /*
871 * drawTube: I know all this stuff is available in gluQuadrics
872 * but I'd originally intended to texture the poles with a 3D wood
873 * texture, but I was having difficulty getting wood... what? Why
874 * are all you Amercians laughing..? Anyway, I don't know if enough
875 * people's hardware supports 3D textures, so I didn't bother (xorg
876 * ATI server doesn't :-( )
877 */
drawTube(GLdouble bottomRadius,GLdouble topRadius,GLdouble bottomThickness,GLdouble topThickness,GLdouble height,GLuint nSlice,GLuint nLoop)878 static int drawTube(GLdouble bottomRadius, GLdouble topRadius,
879 GLdouble bottomThickness, GLdouble topThickness,
880 GLdouble height, GLuint nSlice, GLuint nLoop)
881 {
882 int polys = 0;
883 GLfloat y;
884 GLfloat *cosCache = malloc(sizeof(GLfloat) * nSlice);
885 GLfloat *sinCache = malloc(sizeof(GLfloat) * nSlice);
886 GLint slice;
887 GLuint loop;
888 GLint lastSlice = nSlice - 1;
889 GLfloat radius;
890 GLfloat innerRadius;
891
892 if(bottomThickness > bottomRadius) {
893 bottomThickness = bottomRadius;
894 }
895 if(topThickness > topRadius) {
896 topThickness = topRadius;
897 }
898 if(bottomThickness < 0.0) {
899 bottomThickness = 0.0;
900 }
901 if(topThickness < 0.0) {
902 topThickness = 0.0;
903 }
904 /* if(topRadius >= bottomRadius) {
905 maxRadius = topRadius;
906 } else {
907 maxRadius = bottomRadius;
908 } */
909
910 /* bottom */
911 y = 0.0;
912 radius = bottomRadius;
913 innerRadius = bottomRadius - bottomThickness;
914 /* innerTexCoordSize = texCoordSize * innerRadius / maxRadius; */
915 /* outerTexCoordSize = texCoordSize * radius / maxRadius; */
916 /* yTexCoord = minTexCoord; */
917
918 glBegin(GL_QUAD_STRIP);
919
920 glNormal3f(0.0, -1.0, 0.0);
921
922 /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + innerTexCoordSize); */
923 glVertex3f(0.0, y, innerRadius);
924
925 /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + outerTexCoordSize); */
926 glVertex3f(0.0, y, radius);
927
928 for(slice = lastSlice; slice >= 0; --slice) {
929 GLfloat theta = 2.0 * M_PI * (double)slice / nSlice;
930
931 cosCache[slice] = cos(theta);
932 sinCache[slice] = sin(theta);
933
934 /* glTexCoord3f(midTexCoord + sinCache[slice] * innerTexCoordSize, */
935 /* yTexCoord, */
936 /* midTexCoord + cosCache[slice] * innerTexCoordSize); */
937 glVertex3f(innerRadius * sinCache[slice], y,
938 innerRadius * cosCache[slice]);
939 /* glTexCoord3f(midTexCoord + sinCache[slice] * outerTexCoordSize, */
940 /* yTexCoord, */
941 /* midTexCoord + cosCache[slice] * outerTexCoordSize); */
942 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
943 polys++;
944 }
945 glEnd();
946
947 /* middle */
948 for(loop = 0; loop < nLoop; ++loop) {
949 GLfloat lowerRadius =
950 bottomRadius + (topRadius -
951 bottomRadius) * (float)loop / (nLoop);
952 GLfloat upperRadius =
953 bottomRadius + (topRadius - bottomRadius) * (float)(loop +
954 1) /
955 (nLoop);
956 GLfloat lowerY = height * (float)loop / (nLoop);
957 GLfloat upperY = height * (float)(loop + 1) / (nLoop);
958 GLfloat factor = (topRadius - topThickness) -
959 (bottomRadius - bottomThickness);
960
961 /* outside */
962 glBegin(GL_QUAD_STRIP);
963 for(slice = 0; slice < nSlice; ++slice) {
964 glNormal3f(sinCache[slice], 0.0, cosCache[slice]);
965 glVertex3f(upperRadius * sinCache[slice], upperY,
966 upperRadius * cosCache[slice]);
967 glVertex3f(lowerRadius * sinCache[slice], lowerY,
968 lowerRadius * cosCache[slice]);
969 polys++;
970 }
971 glNormal3f(0.0, 0.0, 1.0);
972 glVertex3f(0.0, upperY, upperRadius);
973 glVertex3f(0.0, lowerY, lowerRadius);
974 polys++;
975 glEnd();
976
977 /* inside */
978 lowerRadius = bottomRadius - bottomThickness +
979 factor * (float)loop / (nLoop);
980 upperRadius = bottomRadius - bottomThickness +
981 factor * (float)(loop + 1) / (nLoop);
982
983 glBegin(GL_QUAD_STRIP);
984 glNormal3f(0.0, 0.0, -1.0);
985 glVertex3f(0.0, upperY, upperRadius);
986 glVertex3f(0.0, lowerY, lowerRadius);
987 for(slice = lastSlice; slice >= 0; --slice) {
988 glNormal3f(-sinCache[slice], 0.0, -cosCache[slice]);
989 glVertex3f(upperRadius * sinCache[slice], upperY,
990 upperRadius * cosCache[slice]);
991 glVertex3f(lowerRadius * sinCache[slice], lowerY,
992 lowerRadius * cosCache[slice]);
993 polys++;
994 }
995 glEnd();
996 }
997
998 /* top */
999 y = height;
1000 radius = topRadius;
1001 innerRadius = topRadius - topThickness;
1002
1003 glBegin(GL_QUAD_STRIP);
1004 glNormal3f(0.0, 1.0, 0.0);
1005 for(slice = 0; slice < nSlice; ++slice) {
1006 glVertex3f(innerRadius * sinCache[slice], y,
1007 innerRadius * cosCache[slice]);
1008
1009 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
1010 polys++;
1011 }
1012 glVertex3f(0.0, y, innerRadius);
1013 glVertex3f(0.0, y, radius);
1014 glEnd();
1015 free (cosCache);
1016 free (sinCache);
1017 return polys;
1018 }
1019
drawPole(GLfloat radius,GLfloat length)1020 static int drawPole(GLfloat radius, GLfloat length)
1021 {
1022 return drawTube(radius, radius, radius, radius, length, NSLICE, NLOOPS);
1023 }
1024
drawDisk3D(GLdouble inner_radius,GLdouble outer_radius,GLdouble height)1025 static int drawDisk3D(GLdouble inner_radius, GLdouble outer_radius,
1026 GLdouble height)
1027 {
1028 return drawTube(outer_radius, outer_radius, outer_radius - inner_radius,
1029 outer_radius - inner_radius, height, NSLICE, NLOOPS);
1030 }
1031
1032 /* used for drawing base */
drawCuboid(GLfloat length,GLfloat width,GLfloat height)1033 static int drawCuboid(GLfloat length, GLfloat width, GLfloat height)
1034 {
1035 GLfloat xmin = -length / 2.0f;
1036 GLfloat xmax = length / 2.0f;
1037 GLfloat zmin = -width / 2.0f;
1038 GLfloat zmax = width / 2.0f;
1039 GLfloat ymin = 0.0f;
1040 GLfloat ymax = height;
1041 int polys = 0;
1042
1043 glBegin(GL_QUADS);
1044 /* front */
1045 glNormal3fv(front);
1046 glVertex3f(xmin, ymin, zmax); /* 0 */
1047 glVertex3f(xmax, ymin, zmax); /* 1 */
1048 glVertex3f(xmax, ymax, zmax); /* 2 */
1049 glVertex3f(xmin, ymax, zmax); /* 3 */
1050 polys++;
1051 /* right */
1052 glNormal3fv(right);
1053 glVertex3f(xmax, ymin, zmax); /* 1 */
1054 glVertex3f(xmax, ymin, zmin); /* 5 */
1055 glVertex3f(xmax, ymax, zmin); /* 6 */
1056 glVertex3f(xmax, ymax, zmax); /* 2 */
1057 polys++;
1058 /* back */
1059 glNormal3fv(back);
1060 glVertex3f(xmax, ymin, zmin); /* 5 */
1061 glVertex3f(xmin, ymin, zmin); /* 4 */
1062 glVertex3f(xmin, ymax, zmin); /* 7 */
1063 glVertex3f(xmax, ymax, zmin); /* 6 */
1064 polys++;
1065 /* left */
1066 glNormal3fv(left);
1067 glVertex3f(xmin, ymin, zmin); /* 4 */
1068 glVertex3f(xmin, ymin, zmax); /* 0 */
1069 glVertex3f(xmin, ymax, zmax); /* 3 */
1070 glVertex3f(xmin, ymax, zmin); /* 7 */
1071 polys++;
1072 /* top */
1073 glNormal3fv(up);
1074 glVertex3f(xmin, ymax, zmax); /* 3 */
1075 glVertex3f(xmax, ymax, zmax); /* 2 */
1076 glVertex3f(xmax, ymax, zmin); /* 6 */
1077 glVertex3f(xmin, ymax, zmin); /* 7 */
1078 polys++;
1079 /* bottom */
1080 glNormal3fv(down);
1081 glVertex3f(xmin, ymin, zmin); /* 4 */
1082 glVertex3f(xmax, ymin, zmin); /* 5 */
1083 glVertex3f(xmax, ymin, zmax); /* 1 */
1084 glVertex3f(xmin, ymin, zmax); /* 0 */
1085 polys++;
1086 glEnd();
1087 return polys;
1088 }
1089
1090 /* Set normal vector in xz plane, based on rotation around center. */
setNormalV(glhcfg * glhanoi,GLfloat theta,int y1,int y2,int r1)1091 static void setNormalV(glhcfg *glhanoi, GLfloat theta, int y1, int y2, int r1) {
1092 if (y1 == y2) /* up/down */
1093 glNormal3f(0.0, y1 ? 1.0 : -1.0, 0.0);
1094 else if (!r1) /* inward */
1095 glNormal3f(-cos(theta), 0.0, -sin(theta));
1096 else /* outward */
1097 glNormal3f(cos(theta), 0.0, sin(theta));
1098 }
1099
1100 /* y1, r1, y2, r2 are indices into y, r, beg, end */
drawBaseStrip(glhcfg * glhanoi,int y1,int r1,int y2,int r2,GLfloat y[2],GLfloat r[2],GLfloat beg[2][2],GLfloat end[2][2])1101 static int drawBaseStrip(glhcfg *glhanoi, int y1, int r1, int y2, int r2,
1102 GLfloat y[2], GLfloat r[2], GLfloat beg[2][2], GLfloat end[2][2]) {
1103 int i;
1104 GLfloat theta, costh, sinth, x[2], z[2];
1105 GLfloat theta1 = (M_PI * 2) / (glhanoi->numberOfPoles + 1);
1106
1107 glBegin(GL_QUAD_STRIP);
1108
1109 /* beginning edge */
1110 glVertex3f(beg[r1][0], y[y1], beg[r1][1]);
1111 glVertex3f(beg[r2][0], y[y2], beg[r2][1]);
1112 setNormalV(glhanoi, theta1, y1, y2, r1);
1113
1114 for (i = 1; i < glhanoi->numberOfPoles; i++) {
1115 theta = theta1 * (i + 0.5);
1116 costh = cos(theta);
1117 sinth = sin(theta);
1118 x[0] = costh * r[0];
1119 x[1] = costh * r[1];
1120 z[0] = sinth * r[0];
1121 z[1] = sinth * r[1];
1122
1123 glVertex3f(x[r1], y[y1], z[r1]);
1124 glVertex3f(x[r2], y[y2], z[r2]);
1125
1126 setNormalV(glhanoi, theta1 * (i + 1), y1, y2, r1);
1127 }
1128
1129 /* end edge */
1130 glVertex3f(end[r1][0], y[y1], end[r1][1]);
1131 glVertex3f(end[r2][0], y[y2], end[r2][1]);
1132 setNormalV(glhanoi, glhanoi->numberOfPoles, y1, y2, r1);
1133
1134 glEnd();
1135 return glhanoi->numberOfPoles;
1136 }
1137
1138 /* Draw base such that poles are distributed around a regular polygon. */
drawRoundBase(glhcfg * glhanoi)1139 static int drawRoundBase(glhcfg *glhanoi) {
1140 int polys = 0;
1141 GLfloat theta, sinth, costh;
1142
1143 /*
1144 r[0] = (minimum) inner radius of base at vertices
1145 r[1] = (minimum) outer radius of base at vertices
1146 y[0] = bottom of base
1147 y[1] = top of base */
1148 GLfloat r[2], y[2];
1149 /* positions of end points: beginning, end.
1150 beg[0] is inner corner of beginning of base, beg[1] is outer corner.
1151 beg[i][0] is x, [i][1] is z. */
1152 GLfloat beg[2][2], end[2][2], begNorm, endNorm;
1153 /* ratio of radius at base vertices to ratio at poles */
1154 GLfloat longer = 1.0 / cos(M_PI / (glhanoi->numberOfPoles + 1));
1155
1156 r[0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * longer;
1157 r[1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * longer;
1158 y[0] = 0;
1159 y[1] = glhanoi->baseHeight;
1160
1161 /* compute beg, end. Make the ends square. */
1162 theta = M_PI * 2 / (glhanoi->numberOfPoles + 1);
1163
1164 costh = cos(theta);
1165 sinth = sin(theta);
1166 beg[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh +
1167 glhanoi->maxDiskRadius * sinth;
1168 beg[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh +
1169 glhanoi->maxDiskRadius * sinth;
1170 beg[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth -
1171 glhanoi->maxDiskRadius * costh;
1172 beg[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth -
1173 glhanoi->maxDiskRadius * costh;
1174 begNorm = theta - M_PI * 0.5;
1175
1176 theta = M_PI * 2 * glhanoi->numberOfPoles / (glhanoi->numberOfPoles + 1);
1177
1178 costh = cos(theta);
1179 sinth = sin(theta);
1180 end[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh -
1181 glhanoi->maxDiskRadius * sinth;
1182 end[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh -
1183 glhanoi->maxDiskRadius * sinth;
1184 end[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth +
1185 glhanoi->maxDiskRadius * costh;
1186 end[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth +
1187 glhanoi->maxDiskRadius * costh;
1188 endNorm = theta + M_PI * 0.5;
1189
1190 /* bottom: never seen
1191 polys = drawBaseStrip(glhanoi, 0, 0, 0, 1, y, r, beg, end); */
1192 /* outside edge */
1193 polys += drawBaseStrip(glhanoi, 0, 1, 1, 1, y, r, beg, end);
1194 /* top */
1195 polys += drawBaseStrip(glhanoi, 1, 1, 1, 0, y, r, beg, end);
1196 /* inside edge */
1197 polys += drawBaseStrip(glhanoi, 1, 0, 0, 0, y, r, beg, end);
1198
1199 /* Draw ends */
1200 glBegin(GL_QUADS);
1201
1202 glVertex3f(beg[0][0], y[1], beg[0][1]);
1203 glVertex3f(beg[1][0], y[1], beg[1][1]);
1204 glVertex3f(beg[1][0], y[0], beg[1][1]);
1205 glVertex3f(beg[0][0], y[0], beg[0][1]);
1206 glNormal3f(cos(begNorm), 0, sin(begNorm));
1207
1208 glVertex3f(end[0][0], y[0], end[0][1]);
1209 glVertex3f(end[1][0], y[0], end[1][1]);
1210 glVertex3f(end[1][0], y[1], end[1][1]);
1211 glVertex3f(end[0][0], y[1], end[0][1]);
1212 glNormal3f(cos(endNorm), 0, sin(endNorm));
1213
1214 polys += 2;
1215
1216 glEnd();
1217
1218 return polys;
1219 }
1220
drawDisks(glhcfg * glhanoi)1221 static int drawDisks(glhcfg *glhanoi)
1222 {
1223 int i;
1224 int polys = 0;
1225
1226 glPushMatrix();
1227 glTranslatef(0.0f, glhanoi->baseHeight, 0.0f);
1228 for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1229 Disk *disk = &glhanoi->disk[i];
1230 GLfloat *pos = disk->position;
1231 GLfloat *rot = disk->rotation;
1232
1233 glPushMatrix();
1234 glTranslatef(pos[0], pos[1], pos[2]);
1235 if(rot[1] != 0.0) {
1236 glTranslatef(0.0, glhanoi->diskHeight / 2.0, 0.0);
1237 /* rotate around different axis depending on phi */
1238 if (disk->phi != 0.0)
1239 glRotatef(-disk->phi, 0.0, 1.0, 0.0);
1240 glRotatef(rot[1], 0.0, 0.0, 1.0);
1241 if (disk->phi != 0.0)
1242 glRotatef(disk->phi, 0.0, 1.0, 0.0);
1243 glTranslatef(0.0, -glhanoi->diskHeight / 2.0, 0.0);
1244 }
1245 glCallList(disk->displayList);
1246 polys += disk->polys;
1247 glPopMatrix();
1248 }
1249 glPopMatrix();
1250 return polys;
1251 }
1252
getDiskRadius(glhcfg * glhanoi,int i)1253 static GLfloat getDiskRadius(glhcfg *glhanoi, int i)
1254 {
1255 GLfloat retVal = glhanoi->maxDiskRadius *
1256 ((GLfloat) i + 3.0) / (glhanoi->numberOfDisks + 3.0);
1257 return retVal;
1258 }
1259
initData(glhcfg * glhanoi)1260 static void initData(glhcfg *glhanoi)
1261 {
1262 int i;
1263 GLfloat sinPiOverNP;
1264
1265 glhanoi->baseLength = BASE_LENGTH;
1266 if (glhanoi->layoutLinear) {
1267 glhanoi->maxDiskRadius = glhanoi->baseLength /
1268 (2 * 0.95 * glhanoi->numberOfPoles);
1269 } else {
1270 sinPiOverNP = sin(M_PI / (glhanoi->numberOfPoles + 1));
1271 glhanoi->maxDiskRadius = (sinPiOverNP * glhanoi->baseLength * 0.5 * 0.95) / (1 + sinPiOverNP);
1272 }
1273
1274 glhanoi->poleDist = glhanoi->baseLength * 0.5 - glhanoi->maxDiskRadius;
1275 glhanoi->poleRadius = glhanoi->maxDiskRadius / (glhanoi->numberOfDisks + 3.0);
1276 /* fprintf(stderr, "Debug: baseL = %f, maxDiskR = %f, poleR = %f\n",
1277 glhanoi->baseLength, glhanoi->maxDiskRadius, glhanoi->poleRadius); */
1278 glhanoi->baseWidth = 2.0 * glhanoi->maxDiskRadius;
1279 glhanoi->poleOffset = 2.0 * getDiskRadius(glhanoi, glhanoi->maxDiskIdx);
1280 glhanoi->diskHeight = 2.0 * glhanoi->poleRadius;
1281 glhanoi->baseHeight = 2.0 * glhanoi->poleRadius;
1282 glhanoi->poleHeight = glhanoi->numberOfDisks *
1283 glhanoi->diskHeight + glhanoi->poleRadius;
1284 /* numberOfMoves only applies if numberOfPoles = 3 */
1285 glhanoi->numberOfMoves = (1 << glhanoi->numberOfDisks) - 1;
1286 /* use golden ratio */
1287 glhanoi->boardSize = glhanoi->baseLength * 0.5 * (1.0 + sqrt(5.0));
1288
1289 glhanoi->pole = (Pole *)calloc(glhanoi->numberOfPoles, sizeof(Pole));
1290 checkAllocAndExit(!!glhanoi->pole, "poles");
1291
1292 for(i = 0; i < glhanoi->numberOfPoles; i++) {
1293 checkAllocAndExit(
1294 !!(glhanoi->pole[i].data = calloc(glhanoi->numberOfDisks, sizeof(Disk *))),
1295 "disk stack");
1296 glhanoi->pole[i].size = glhanoi->numberOfDisks;
1297 }
1298 checkAllocAndExit(
1299 !!(glhanoi->diskPos = calloc(glhanoi->numberOfDisks, sizeof(float))),
1300 "diskPos");
1301
1302 if (glhanoi->trailQSize) {
1303 glhanoi->trailQ = (TrailPoint *)calloc(glhanoi->trailQSize, sizeof(TrailPoint));
1304 checkAllocAndExit(!!glhanoi->trailQ, "trail queue");
1305 } else glhanoi->trailQ = (TrailPoint *)NULL;
1306 glhanoi->trailQFront = glhanoi->trailQBack = 0;
1307
1308 glhanoi->the_rotator = make_rotator(0.1, 0.025, 0, 1, 0.005, False);
1309 /* or glhanoi->the_rotator = make_rotator(0.025, 0.025, 0.025, 0.5, 0.005, False); */
1310 glhanoi->button_down_p = False;
1311
1312 glhanoi->src = glhanoi->oldsrc = 0;
1313 glhanoi->tmp = glhanoi->oldtmp = 1;
1314 glhanoi->dst = glhanoi->olddst = glhanoi->numberOfPoles - 1;
1315
1316 if (glhanoi->numberOfPoles > 3) {
1317 glhanoi->solveStackSize = glhanoi->numberOfDisks + 2;
1318 glhanoi->solveStack = (SubProblem *)calloc(glhanoi->solveStackSize, sizeof(SubProblem));
1319 checkAllocAndExit(!!glhanoi->solveStack, "solving stack");
1320 glhanoi->solveStackIdx = 0;
1321 }
1322 }
1323
initView(glhcfg * glhanoi)1324 static void initView(glhcfg *glhanoi)
1325 {
1326 glhanoi->camera[0] = 0.0;
1327 glhanoi->camera[1] = 0.0;
1328 glhanoi->camera[2] = 0.0;
1329 glhanoi->centre[0] = 0.0;
1330 glhanoi->centre[1] = glhanoi->poleHeight * 3.0;
1331 glhanoi->centre[2] = 0.0;
1332 }
1333
1334 /*
1335 * noise_improved.c - based on ImprovedNoise.java
1336 * JAVA REFERENCE IMPLEMENTATION OF IMPROVED NOISE - COPYRIGHT 2002 KEN PERLIN.
1337 */
fade(double t)1338 static double fade(double t)
1339 {
1340 return t * t * t * (t * (t * 6 - 15) + 10);
1341 }
1342
grad(int hash,double x,double y,double z)1343 static double grad(int hash, double x, double y, double z)
1344 {
1345 int h = hash & 15; /* CONVERT LO 4 BITS OF HASH CODE */
1346 double u = h < 8 ? x : y, /* INTO 12 GRADIENT DIRECTIONS. */
1347 v = h < 4 ? y : h == 12 || h == 14 ? x : z;
1348 return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
1349 }
1350
1351 static const int permutation[] = { 151, 160, 137, 91, 90, 15,
1352 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142,
1353 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 26,
1354 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237,
1355 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71,
1356 134, 139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60,
1357 211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 102, 143,
1358 54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89,
1359 18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 198,
1360 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118,
1361 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189,
1362 28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70,
1363 221, 153, 101, 155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108,
1364 110, 79, 113, 224, 232, 178, 185, 112, 104, 218, 246, 97, 228, 251,
1365 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241, 81, 51, 145,
1366 235, 249, 14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 157, 184,
1367 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205,
1368 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61,
1369 156, 180
1370 };
1371
initNoise(glhcfg * glhanoi)1372 static void initNoise(glhcfg *glhanoi)
1373 {
1374 int i;
1375 for(i = 0; i < 256; i++)
1376 glhanoi->p[256 + i] = glhanoi->p[i] = permutation[i];
1377 }
1378
improved_noise(glhcfg * glhanoi,double x,double y,double z)1379 static double improved_noise(glhcfg *glhanoi, double x, double y, double z)
1380 {
1381 double u, v, w;
1382 int A, AA, AB, B, BA, BB;
1383 int X = (int)floor(x) & 255, /* FIND UNIT CUBE THAT */
1384 Y = (int)floor(y) & 255, /* CONTAINS POINT. */
1385 Z = (int)floor(z) & 255;
1386 if(!glhanoi->noise_initted) {
1387 initNoise(glhanoi);
1388 glhanoi->noise_initted = 1;
1389 }
1390 x -= floor(x); /* FIND RELATIVE X,Y,Z */
1391 y -= floor(y); /* OF POINT IN CUBE. */
1392 z -= floor(z);
1393 u = fade(x), /* COMPUTE FADE CURVES */
1394 v = fade(y), /* FOR EACH OF X,Y,Z. */
1395 w = fade(z);
1396 A = glhanoi->p[X] + Y;
1397 AA = glhanoi->p[A] + Z;
1398 AB = glhanoi->p[A + 1] + Z, /* HASH COORDINATES OF */
1399 B = glhanoi->p[X + 1] + Y;
1400 BA = glhanoi->p[B] + Z;
1401 BB = glhanoi->p[B + 1] + Z; /* THE 8 CUBE CORNERS, */
1402 return lerp(w, lerp(v, lerp(u, grad(glhanoi->p[AA], x, y, z),/* AND ADD */
1403 grad(glhanoi->p[BA], x - 1, y, z)),/* BLENDED */
1404 lerp(u, grad(glhanoi->p[AB], x, y - 1, z),/* RESULTS */
1405 grad(glhanoi->p[BB], x - 1, y - 1, z))),/* FROM 8 CORNERS */
1406 lerp(v, lerp(u, grad(glhanoi->p[AA + 1], x, y, z - 1), grad(glhanoi->p[BA + 1], x - 1, y, z - 1)), /* OF CUBE */
1407 lerp(u, grad(glhanoi->p[AB + 1], x, y - 1, z - 1),
1408 grad(glhanoi->p[BB + 1], x - 1, y - 1, z - 1))));
1409 }
1410
1411 /*
1412 * end noise_improved.c - based on ImprovedNoise.java
1413 */
1414
1415 struct tex_col_t {
1416 GLuint *colours;
1417 /* GLfloat *points; */
1418 unsigned int ncols;
1419 };
1420 typedef struct tex_col_t tex_col_t;
1421
makeTexture(glhcfg * glhanoi,int x_size,int y_size,int z_size,GLuint (* texFunc)(glhcfg *,double,double,double,tex_col_t *),tex_col_t * colours)1422 static GLubyte *makeTexture(glhcfg *glhanoi, int x_size, int y_size, int z_size,
1423 GLuint(*texFunc) (glhcfg *, double, double, double,
1424 tex_col_t *), tex_col_t * colours)
1425 {
1426 int i, j, k;
1427 GLuint *textureData;
1428 GLuint *texturePtr;
1429 double x, y, z;
1430 double xi, yi, zi;
1431
1432 /* As we use GL_RGBA format, we must assign 4 bytes per element */
1433 if((textureData =
1434 calloc(x_size * y_size * z_size, sizeof(*texturePtr))) == NULL) {
1435 return NULL;
1436 }
1437
1438 xi = 1.0 / x_size;
1439 yi = 1.0 / y_size;
1440 zi = 1.0 / z_size;
1441
1442 z = 0.0;
1443 texturePtr = textureData;
1444 for(k = 0; k < z_size; k++, z += zi) {
1445 y = 0.0;
1446 for(j = 0; j < y_size; j++, y += yi) {
1447 x = 0.0;
1448 for(i = 0; i < x_size; i++, x += xi) {
1449 *texturePtr = texFunc(glhanoi, x, y, z, colours);
1450 ++texturePtr;
1451 }
1452 }
1453 }
1454 return (GLubyte *)textureData;
1455 }
1456
freeTexCols(tex_col_t * p)1457 static void freeTexCols(tex_col_t*p)
1458 {
1459 free(p->colours);
1460 free(p);
1461 }
1462
makeMarbleColours(void)1463 static tex_col_t *makeMarbleColours(void)
1464 {
1465 tex_col_t *marbleColours;
1466 int ncols = 2;
1467
1468 marbleColours = malloc(sizeof(tex_col_t));
1469 if(marbleColours == NULL) return NULL;
1470 marbleColours->colours = calloc(sizeof(GLuint), ncols);
1471 if(marbleColours->colours == NULL) return NULL;
1472 marbleColours->ncols = ncols;
1473
1474 marbleColours->colours[0] = 0x3f3f3f3f;
1475 marbleColours->colours[1] = 0xffffffff;
1476
1477 return marbleColours;
1478 }
1479
turb(glhcfg * glhanoi,double x,double y,double z,int octaves)1480 static double turb(glhcfg *glhanoi, double x, double y, double z, int octaves)
1481 {
1482 int oct, freq = 1;
1483 double r = 0.0;
1484
1485 for(oct = 0; oct < octaves; ++oct) {
1486 r += fabs(improved_noise(glhanoi, freq * x, freq * y, freq * z)) / freq;
1487 freq <<= 1;
1488 }
1489 return r / 2.0;
1490 }
1491
perturb(glhcfg * glhanoi,double * x,double * y,double * z,double scale)1492 static void perturb(glhcfg *glhanoi, double *x, double *y, double *z, double scale)
1493 {
1494 double t = scale * turb(glhanoi, *x, *y, *z, 4);
1495 *x += t;
1496 *y += t;
1497 *z += t;
1498 }
1499
f_m(double x,double y,double z)1500 static double f_m(double x, double y, double z)
1501 {
1502 return sin(3.0 * M_PI * x);
1503 }
1504
C_m(double x,const tex_col_t * tex_cols)1505 static GLuint C_m(double x, const tex_col_t * tex_cols)
1506 {
1507 int r = tex_cols->colours[0] & 0xff;
1508 int g = tex_cols->colours[0] >> 8 & 0xff;
1509 int b = tex_cols->colours[0] >> 16 & 0xff;
1510 double factor;
1511 int r1, g1, b1;
1512 x = x - floor(x);
1513
1514 factor = (1.0 + sin(2.0 * M_PI * x)) / 2.0;
1515
1516 r1 = (tex_cols->colours[1] & 0xff);
1517 g1 = (tex_cols->colours[1] >> 8 & 0xff);
1518 b1 = (tex_cols->colours[1] >> 16 & 0xff);
1519
1520 r += (int)(factor * (r1 - r));
1521 g += (int)(factor * (g1 - g));
1522 b += (int)(factor * (b1 - b));
1523
1524 return 0xff000000 | (b << 16) | (g << 8) | r;
1525 }
1526
1527
makeMarbleTexture(glhcfg * glhanoi,double x,double y,double z,tex_col_t * colours)1528 static GLuint makeMarbleTexture(glhcfg *glhanoi, double x, double y, double z, tex_col_t * colours)
1529 {
1530 perturb(glhanoi, &x, &y, &z, MARBLE_SCALE);
1531 return C_m(f_m(x, y, z), colours);
1532 }
1533
setTexture(glhcfg * glhanoi,int n)1534 static void setTexture(glhcfg *glhanoi, int n)
1535 {
1536 glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[n]);
1537 }
1538
1539 /* returns 1 on failure, 0 on success */
makeTextures(glhcfg * glhanoi)1540 static int makeTextures(glhcfg *glhanoi)
1541 {
1542 GLubyte *marbleTexture;
1543 tex_col_t *marbleColours;
1544
1545 glGenTextures(N_TEXTURES, glhanoi->textureNames);
1546
1547 if((marbleColours = makeMarbleColours()) == NULL) {
1548 return 1;
1549 }
1550 if((marbleTexture =
1551 makeTexture(glhanoi, MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 1,
1552 makeMarbleTexture, marbleColours)) == NULL) {
1553 return 1;
1554 }
1555
1556 glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[0]);
1557 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
1558 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
1559 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
1560 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
1561 glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA,
1562 MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 0,
1563 GL_RGBA, GL_UNSIGNED_BYTE, marbleTexture);
1564 free(marbleTexture);
1565 freeTexCols(marbleColours);
1566
1567 return 0;
1568 }
1569
initFloor(glhcfg * glhanoi)1570 static void initFloor(glhcfg *glhanoi)
1571 {
1572 int i, j;
1573 float tileSize = glhanoi->boardSize / BOARD_SQUARES;
1574 float x0, x1, z0, z1;
1575 float tx0, tx1, tz0, tz1;
1576 const float *col = cWhite;
1577 float texIncr = 1.0 / BOARD_SQUARES;
1578
1579 glhanoi->floorpolys = 0;
1580 checkAllocAndExit(!!(glhanoi->floorList = glGenLists(1)), "floor display list");
1581 glNewList(glhanoi->floorList, GL_COMPILE);
1582 x0 = -glhanoi->boardSize / 2.0;
1583 tx0 = 0.0f;
1584 setMaterial(col, cWhite, 128);
1585 setTexture(glhanoi, 0);
1586 glNormal3fv(up);
1587 for(i = 0; i < BOARD_SQUARES; i++, x0 += tileSize, tx0 += texIncr) {
1588 x1 = x0 + tileSize;
1589 tx1 = tx0 + texIncr;
1590 z0 = -glhanoi->boardSize / 2.0;
1591 tz0 = 0.0f;
1592 for(j = 0; j < BOARD_SQUARES; j++, z0 += tileSize, tz0 += texIncr) {
1593 int colIndex = (i + j) & 0x1;
1594
1595 z1 = z0 + tileSize;
1596 tz1 = tz0 + texIncr;
1597
1598 if(colIndex)
1599 col = cWhite;
1600 else
1601 col = cBlack;
1602
1603 setMaterial(col, cWhite, 100);
1604
1605 glBegin(GL_QUADS);
1606
1607 glTexCoord2d(tx0, tz0);
1608 glVertex3f(x0, 0.0, z0);
1609
1610 glTexCoord2d(tx0, tz1);
1611 glVertex3f(x0, 0.0, z1);
1612
1613 glTexCoord2d(tx1, tz1);
1614 glVertex3f(x1, 0.0, z1);
1615
1616 glTexCoord2d(tx1, tz0);
1617 glVertex3f(x1, 0.0, z0);
1618 glhanoi->floorpolys++;
1619 glEnd();
1620 }
1621 }
1622 glEndList();
1623 }
1624
initBase(glhcfg * glhanoi)1625 static void initBase(glhcfg *glhanoi)
1626 {
1627 checkAllocAndExit(!!(glhanoi->baseList = glGenLists(1)), "tower bases display list");
1628
1629 glNewList(glhanoi->baseList, GL_COMPILE);
1630 setMaterial(baseColor, cWhite, 50);
1631 if (glhanoi->layoutLinear) {
1632 glhanoi->basepolys = drawCuboid(glhanoi->baseLength, glhanoi->baseWidth,
1633 glhanoi->baseHeight);
1634 } else {
1635 glhanoi->basepolys = drawRoundBase(glhanoi);
1636 }
1637 glEndList();
1638 }
1639
initTowers(glhcfg * glhanoi)1640 static void initTowers(glhcfg *glhanoi)
1641 {
1642 int i;
1643
1644 checkAllocAndExit(!!(glhanoi->poleList = glGenLists(1)), "poles display list\n");
1645
1646 glNewList(glhanoi->poleList, GL_COMPILE);
1647 /* glTranslatef(-glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5f, glhanoi->baseHeight, 0.0f); */
1648 setMaterial(poleColor, cWhite, 50);
1649 for (i = 0; i < glhanoi->numberOfPoles; i++) {
1650 GLfloat *p = glhanoi->pole[i].position;
1651 GLfloat rad = (M_PI * 2.0 * (i + 1)) / (glhanoi->numberOfPoles + 1);
1652
1653 p[1] = glhanoi->baseHeight;
1654
1655 if (glhanoi->layoutLinear) {
1656 /* Linear: */
1657 p[0] = -glhanoi->poleOffset * ((glhanoi->numberOfPoles - 1) * 0.5f - i);
1658 p[2] = 0.0f;
1659 } else {
1660 /* Circular layout: */
1661 p[0] = cos(rad) * glhanoi->poleDist;
1662 p[2] = sin(rad) * glhanoi->poleDist;
1663 }
1664
1665 glPushMatrix();
1666 glTranslatef(p[0], p[1], p[2]);
1667 glhanoi->polepolys = drawPole(glhanoi->poleRadius, glhanoi->poleHeight);
1668 glPopMatrix();
1669
1670 }
1671 glEndList();
1672 }
1673
1674 /* Parameterized hue based on input 0.0 - 1.0. */
cfunc(double x)1675 static double cfunc(double x)
1676 {
1677 #define COMP <
1678 if(x < 2.0 / 7.0) {
1679 return (1.0 / 12.0) / (1.0 / 7.0) * x;
1680 }
1681 if(x < 3.0 / 7.0) {
1682 /* (7x - 1) / 6 */
1683 return (1.0 + 1.0 / 6.0) * x - 1.0 / 6.0;
1684 }
1685 if(x < 4.0 / 7.0) {
1686 return (2.0 + 1.0 / 3.0) * x - 2.0 / 3.0;
1687 }
1688 if(x < 5.0 / 7.0) {
1689 return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1690 }
1691 return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1692 }
1693
initDisks(glhcfg * glhanoi)1694 static void initDisks(glhcfg *glhanoi)
1695 {
1696 int i;
1697 glhanoi->disk = (Disk *) calloc(glhanoi->numberOfDisks, sizeof(Disk));
1698 checkAllocAndExit(!!glhanoi->disk, "disks");
1699
1700 for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1701 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1702 double f = cfunc((GLfloat) i / (GLfloat) glhanoi->numberOfDisks);
1703 GLfloat diskColor = f * 360.0;
1704 GLfloat color[3];
1705 Disk *disk = &glhanoi->disk[i];
1706
1707 disk->id = i;
1708 disk->position[0] = glhanoi->pole[0].position[0]; /* -glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5; */
1709 disk->position[1] = glhanoi->diskHeight * height;
1710 disk->position[2] = glhanoi->pole[0].position[2];
1711 disk->rotation[0] = 0.0;
1712 disk->rotation[1] = 0.0;
1713 disk->rotation[2] = 0.0;
1714 disk->polys = 0;
1715
1716 /* make smaller disks move faster */
1717 disk->speed = lerp(((double)glhanoi->numberOfDisks - i) / glhanoi->numberOfDisks,
1718 1.0, glhanoi->speed);
1719 /* fprintf(stderr, "disk id: %d, alpha: %0.2f, speed: %0.2f\n", disk->id,
1720 ((double)(glhanoi->maxDiskIdx - i)) / glhanoi->numberOfDisks, disk->speed); */
1721
1722 color[0] = diskColor;
1723 color[1] = 1.0f;
1724 color[2] = 1.0f;
1725 HSVtoRGBv(color, color);
1726
1727 checkAllocAndExit(!!(disk->displayList = glGenLists(1)), "disk display list");
1728 glNewList(disk->displayList, GL_COMPILE);
1729 setMaterial(color, cWhite, 100.0);
1730 disk->polys += drawDisk3D(glhanoi->poleRadius,
1731 getDiskRadius(glhanoi, i),
1732 glhanoi->diskHeight);
1733 /*fprintf(stderr, "Debug: disk %d has radius %f\n", i,
1734 getDiskRadius(glhanoi, i)); */
1735 glEndList();
1736 }
1737 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
1738 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1739 int h = glhanoi->maxDiskIdx - i;
1740 glhanoi->diskPos[h] = glhanoi->diskHeight * height;
1741 push(glhanoi, glhanoi->src, &glhanoi->disk[i]);
1742 }
1743 }
1744
initLights(Bool state)1745 static void initLights(Bool state)
1746 {
1747 if(state) {
1748 glLightfv(GL_LIGHT0, GL_POSITION, pos0);
1749 glLightfv(GL_LIGHT0, GL_AMBIENT, amb0);
1750 glLightfv(GL_LIGHT0, GL_DIFFUSE, dif0);
1751 glLightfv(GL_LIGHT0, GL_SPECULAR, spc0);
1752
1753 glLightfv(GL_LIGHT1, GL_POSITION, pos1);
1754 glLightfv(GL_LIGHT1, GL_AMBIENT, amb1);
1755 glLightfv(GL_LIGHT1, GL_DIFFUSE, dif1);
1756 glLightfv(GL_LIGHT1, GL_SPECULAR, spc1);
1757
1758 glEnable(GL_LIGHTING);
1759 glEnable(GL_LIGHT0);
1760 glEnable(GL_LIGHT1);
1761 } else {
1762 glDisable(GL_LIGHTING);
1763 }
1764 }
1765
drawFloor(glhcfg * glhanoi)1766 static int drawFloor(glhcfg *glhanoi)
1767 {
1768 glCallList(glhanoi->floorList);
1769 return glhanoi->floorpolys;
1770 }
1771
drawTowers(glhcfg * glhanoi)1772 static int drawTowers(glhcfg *glhanoi)
1773 {
1774 glCallList(glhanoi->baseList);
1775 glCallList(glhanoi->poleList);
1776 return glhanoi->basepolys + glhanoi->polepolys;
1777 }
1778
drawTrails1(glhcfg * glhanoi,double t,double thickness,double alpha)1779 static int drawTrails1(glhcfg *glhanoi, double t, double thickness, double alpha) {
1780 int i, prev = -1, lines = 0;
1781 Bool fresh = False;
1782 GLfloat trailDurInv = 1.0f / glhanoi->trailDuration;
1783
1784 glLineWidth(thickness);
1785
1786 glBegin(GL_LINES);
1787
1788 for (i = glhanoi->trailQFront;
1789 i != glhanoi->trailQBack;
1790 i = normalizeQ(i + 1)) {
1791 TrailPoint *tqi = &(glhanoi->trailQ[i]);
1792
1793 if (!fresh && t > tqi->endTime) {
1794 glhanoi->trailQFront = normalizeQ(i + 1);
1795 } else {
1796 if (tqi->startTime > t) break;
1797 /* Found trails that haven't timed out. */
1798 if (!fresh) fresh = True;
1799 if (prev > -1) {
1800 /* Fade to invisible with age */
1801 trailColor[3] = alpha * (tqi->endTime - t) * trailDurInv;
1802 /* Can't use setMaterial(trailColor, cBlack, 0) because our color needs an alpha value. */
1803 glColor4fv(trailColor);
1804 glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, trailColor);
1805 /* FUTURE: to really do this right, trails should be drawn in back-to-front
1806 order, so that blending is done correctly.
1807 Currently it looks poor when a faded trail is in front of, or coincident with,
1808 a bright trail but is drawn first.
1809 I think for now it's good enough to recommend shorter trails so they
1810 never/rarely overlap.
1811 A jitter per trail arc would also mitigate this problem, to a lesser degree. */
1812 glVertex3fv(glhanoi->trailQ[prev].position);
1813 glVertex3fv(glhanoi->trailQ[i].position);
1814 lines++;
1815 }
1816 if (glhanoi->trailQ[i].isEnd)
1817 prev = -1;
1818 else
1819 prev = i;
1820 }
1821 }
1822
1823 glEnd();
1824
1825 return lines;
1826 }
1827
drawTrails(glhcfg * glhanoi)1828 static int drawTrails(glhcfg *glhanoi) {
1829 int lines = 0;
1830 double t = getTime();
1831
1832 glEnable (GL_BLEND);
1833 glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1834 glMaterialfv(GL_FRONT, GL_SPECULAR, cBlack);
1835 glMateriali(GL_FRONT, GL_SHININESS, 0);
1836
1837 /* Draw them twice, with different widths and opacities, to make them smoother. */
1838 lines = drawTrails1(glhanoi, t, 1.0, 0.75);
1839 lines += drawTrails1(glhanoi, t, 2.5, 0.5);
1840
1841 glDisable (GL_BLEND);
1842
1843 /* fprintf(stderr, "Drew trails: %d lines\n", lines); */
1844 return lines;
1845 }
1846
1847 /* Window management, etc
1848 */
reshape_glhanoi(ModeInfo * mi,int width,int height)1849 ENTRYPOINT void reshape_glhanoi(ModeInfo * mi, int width, int height)
1850 {
1851 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1852 double h = (GLfloat) height / (GLfloat) width;
1853 int y = 0;
1854
1855 if (width > height * 5) { /* tiny window: show middle */
1856 height = width * 9/16;
1857 y = -height/2;
1858 h = height / (GLfloat) width;
1859 }
1860
1861 glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *glhanoi->glx_context);
1862
1863 glViewport(0, y, (GLint) width, (GLint) height);
1864
1865 glMatrixMode(GL_PROJECTION);
1866 glLoadIdentity();
1867 gluPerspective(30.0, 1/h, 1.0,
1868 2 * MAX_CAMERA_RADIUS);
1869
1870 glMatrixMode(GL_MODELVIEW);
1871 glLoadIdentity();
1872
1873 glClear(GL_COLOR_BUFFER_BIT);
1874 }
1875
init_glhanoi(ModeInfo * mi)1876 ENTRYPOINT void init_glhanoi(ModeInfo * mi)
1877 {
1878 glhcfg *glhanoi;
1879 MI_INIT(mi, glhanoi_cfg);
1880
1881 glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1882 glhanoi->glx_context = init_GL(mi);
1883 glhanoi->numberOfDisks = MI_BATCHCOUNT(mi);
1884
1885 if (glhanoi->numberOfDisks <= 1)
1886 glhanoi->numberOfDisks = 3 + (int) BELLRAND(9);
1887
1888 /* magicnumber is a bitfield, so we can't have more than 31 discs
1889 on a system with 4-byte ints. */
1890 if (glhanoi->numberOfDisks >= 8 * sizeof(int))
1891 glhanoi->numberOfDisks = (8 * sizeof(int)) - 1;
1892
1893 glhanoi->maxDiskIdx = glhanoi->numberOfDisks - 1;
1894
1895 glhanoi->numberOfPoles = get_integer_resource(MI_DISPLAY(mi), "poles", "Integer");
1896 /* Set a number of poles from 3 to numberOfDisks + 1, biased toward lower values,
1897 with probability decreasing linearly. */
1898 if (glhanoi->numberOfPoles <= 2)
1899 glhanoi->numberOfPoles = 3 +
1900 (int)((1 - sqrt(frand(1.0))) * (glhanoi->numberOfDisks - 1));
1901
1902 glhanoi->wire = MI_IS_WIREFRAME(mi);
1903
1904 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
1905 glhanoi->wire = 0;
1906 # endif
1907
1908 glhanoi->light = light;
1909 glhanoi->fog = fog;
1910 glhanoi->texture = texture;
1911 glhanoi->speed = speed;
1912 glhanoi->trailDuration = trails;
1913 /* set trailQSize based on 60 fps (a maximum, more or less) */
1914 /* FUTURE: Should clamp framerate to 60 fps? See flurry.c's draw_flurry().
1915 The only bad effect if we don't is that trail-ends could
1916 show "unnatural" pauses at high fps. */
1917 glhanoi->trailQSize = (int)(trails * 60.0);
1918
1919 reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
1920
1921 if(glhanoi->wire) {
1922 glhanoi->light = False;
1923 glhanoi->fog = False;
1924 glhanoi->texture = False;
1925 }
1926
1927 initLights(!glhanoi->wire && glhanoi->light);
1928 checkAllocAndExit(!makeTextures(glhanoi), "textures\n");
1929
1930 /* Choose linear or circular layout. Could make this a user option. */
1931 glhanoi->layoutLinear = (glhanoi->numberOfPoles == 3);
1932
1933 initData(glhanoi);
1934 initView(glhanoi);
1935 initFloor(glhanoi);
1936 initBase(glhanoi);
1937 initTowers(glhanoi);
1938 initDisks(glhanoi);
1939
1940 glEnable(GL_DEPTH_TEST);
1941 glEnable(GL_NORMALIZE);
1942 glEnable(GL_CULL_FACE);
1943 glShadeModel(GL_SMOOTH);
1944 if(glhanoi->fog) {
1945 glClearColor(fogcolor[0], fogcolor[1], fogcolor[2], 1.0);
1946 glFogi(GL_FOG_MODE, GL_LINEAR);
1947 glFogfv(GL_FOG_COLOR, fogcolor);
1948 glFogf(GL_FOG_DENSITY, 0.35f);
1949 glHint(GL_FOG_HINT, GL_NICEST);
1950 glFogf(GL_FOG_START, MIN_CAMERA_RADIUS);
1951 glFogf(GL_FOG_END, MAX_CAMERA_RADIUS / 1.9);
1952 glEnable(GL_FOG);
1953 }
1954
1955 glhanoi->duration = START_DURATION;
1956 changeState(glhanoi, START);
1957 }
1958
draw_glhanoi(ModeInfo * mi)1959 ENTRYPOINT void draw_glhanoi(ModeInfo * mi)
1960 {
1961 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1962 Display *dpy = MI_DISPLAY(mi);
1963 Window window = MI_WINDOW(mi);
1964
1965 if(!glhanoi->glx_context)
1966 return;
1967
1968 glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *glhanoi->glx_context);
1969
1970 glPolygonMode(GL_FRONT, glhanoi->wire ? GL_LINE : GL_FILL);
1971
1972 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1973 mi->polygon_count = 0;
1974
1975 glLoadIdentity();
1976 glRotatef(current_device_rotation(), 0, 0, 1);
1977
1978 update_glhanoi(glhanoi);
1979 updateView(glhanoi);
1980
1981 # ifdef HAVE_MOBILE /* Keep it the same relative size when rotated. */
1982 {
1983 GLfloat h = MI_HEIGHT(mi) / (GLfloat) MI_WIDTH(mi);
1984 int o = (int) current_device_rotation();
1985 if (o != 0 && o != 180 && o != -180)
1986 glScalef (1/h, 1/h, 1/h);
1987 }
1988 # endif
1989
1990 if(!glhanoi->wire && glhanoi->texture) {
1991 glEnable(GL_TEXTURE_2D);
1992 }
1993 mi->polygon_count += drawFloor(glhanoi);
1994 glDisable(GL_TEXTURE_2D);
1995
1996 mi->polygon_count += drawTowers(glhanoi);
1997 mi->polygon_count += drawDisks(glhanoi);
1998
1999 if (glhanoi->trailQSize) {
2000 /* No polygons, just lines. So ignore the return count. */
2001 (void)drawTrails(glhanoi);
2002 }
2003
2004 if(mi->fps_p) {
2005 do_fps(mi);
2006 }
2007 glFinish();
2008
2009 glXSwapBuffers(dpy, window);
2010 }
2011
glhanoi_handle_event(ModeInfo * mi,XEvent * event)2012 ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event)
2013 {
2014 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
2015
2016 /* #### this is all wrong on iOS -- should be using gltrackball. */
2017
2018 if(event->xany.type == ButtonPress && event->xbutton.button == Button1) {
2019 glhanoi->button_down_p = True;
2020 glhanoi->drag_x = event->xbutton.x;
2021 glhanoi->drag_y = event->xbutton.y;
2022 return True;
2023 } else if(event->xany.type == ButtonRelease
2024 && event->xbutton.button == Button1) {
2025 glhanoi->button_down_p = False;
2026 return True;
2027 } else if(event->xany.type == ButtonPress &&
2028 (event->xbutton.button == Button4
2029 || event->xbutton.button == Button5)) {
2030 switch (event->xbutton.button) {
2031 case Button4:
2032 glhanoi->camera[2] += 0.01;
2033 break;
2034 case Button5:
2035 glhanoi->camera[2] -= 0.01;
2036 break;
2037 default:
2038 fprintf(stderr,
2039 "glhanoi: unknown button in mousewheel handler\n");
2040 }
2041 return True;
2042 } else if(event->xany.type == MotionNotify
2043 && glhanoi_cfg->button_down_p) {
2044 int x_diff, y_diff;
2045
2046 x_diff = event->xbutton.x - glhanoi->drag_x;
2047 y_diff = event->xbutton.y - glhanoi->drag_y;
2048
2049 glhanoi->camera[0] = (float)x_diff / (float)MI_WIDTH(mi);
2050 glhanoi->camera[1] = (float)y_diff / (float)MI_HEIGHT(mi);
2051
2052 return True;
2053 }
2054 #if 0 /* #### doesn't work */
2055 else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
2056 {
2057 changeState(glhanoi, START);
2058 return True;
2059 }
2060 #endif
2061 return False;
2062 }
2063
free_glhanoi(ModeInfo * mi)2064 ENTRYPOINT void free_glhanoi(ModeInfo * mi)
2065 {
2066 glhcfg *glh = &glhanoi_cfg[MI_SCREEN(mi)];
2067 int i;
2068 int j;
2069
2070 if (!glh->glx_context) return;
2071 glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *glh->glx_context);
2072
2073 free_rotator (glh->the_rotator);
2074 if (glh->pole) {
2075 for (i = 0; i < glh->numberOfPoles; i++)
2076 if (glh->pole[i].data) free (glh->pole[i].data);
2077 free (glh->pole);
2078 }
2079 if (glh->diskPos) free (glh->diskPos);
2080 if (glh->trailQ) free (glh->trailQ);
2081 if (glh->solveStack) free (glh->solveStack);
2082
2083 glDeleteLists(glh->floorList, 1);
2084 glDeleteLists(glh->baseList, 1);
2085 glDeleteLists(glh->poleList, 1);
2086 glDeleteLists(glh->textureNames[0], 2);
2087 for(j = 0; j < glh->numberOfDisks; ++j) {
2088 glDeleteLists(glh->disk[j].displayList, 1);
2089 }
2090 free(glh->disk);
2091 glDeleteTextures (N_TEXTURES, glh->textureNames);
2092 }
2093
2094 XSCREENSAVER_MODULE ("GLHanoi", glhanoi)
2095
2096 #endif /* USE_GL */
2097