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
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
19 #define DEF_LIGHT "True"
20 #define DEF_FOG "False"
21 #define DEF_TEXTURE "True"
22 #define DEF_POLES "0" /* choose random value */
24 #define DEF_TRAILS "2"
26 #define DEFAULTS "*delay: 15000\n" \
31 # define refresh_glhanoi 0
33 /* polygon resolution of poles and disks */
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
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
47 #define MAX_CAMERA_RADIUS 250.0
48 #define MIN_CAMERA_RADIUS 75.0
50 #define MARBLE_SCALE 1.01
53 /* Return a double precision number in [0...n], with bell curve distribution. */
54 #define BELLRAND(n) ((frand((n)) + frand((n)) + frand((n))) / 3)
61 #define MARBLE_TEXTURE_SIZE 256
64 #define countof(x) (sizeof((x))/sizeof((*x)))
67 #include "xlockmore.h"
69 #ifdef USE_GL /* whole file */
71 typedef struct timeval glhtime;
73 static double getTime(void)
76 #ifdef GETTIMEOFDAY_TWO_ARGS
77 gettimeofday(&t, NULL);
78 #else /* !GETTIMEOFDAY_TWO_ARGS */
80 #endif /* !GETTIMEOFDAY_TWO_ARGS */
81 return t.tv_sec + t.tv_usec / 1000000.0;
102 GLfloat xmin, xmax, ymin, zmin, zmax;
105 GLfloat ucostheta, usintheta;
107 GLdouble rotAngle; /* degree of "flipping" so far, during travel */
108 GLdouble phi; /* angle of motion in xz plane */
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'." */
125 unsigned long available; /* a bitmask of poles that have no smaller disks on them */
130 double startTime, endTime;
135 GLXContext *glx_context;
141 GLfloat trailDuration;
152 /* src, tmp, dst: index of pole that is source / storage / destination for
160 GLfloat speed; /* coefficient for how fast the disks move */
161 SubProblem *solveStack;
162 int solveStackSize, solveStackIdx;
171 float poleDist; /* distance of poles from center, for round layout */
174 float *diskPos; /* pre-computed disk positions on rods */
179 int floorpolys, basepolys, polepolys;
182 int trailQFront, trailQBack;
185 rotator *the_rotator;
188 GLuint textureNames[N_TEXTURES];
195 static glhcfg *glhanoi_cfg = NULL;
199 static GLfloat trails;
201 static GLfloat speed;
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 }
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}
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"}
233 ENTRYPOINT ModeSpecOpt glhanoi_opts = { countof(opts), opts, countof(vars), vars, desc };
237 ModStruct glhanoi_description = {
238 "glhanoi", "init_glhanoi", "draw_glhanoi", "release_glhanoi",
239 "draw_glhanoi", "init_glhanoi", NULL, &glhanoi_opts,
240 1000, 1, 2, 1, 4, 1.0, "",
241 "Towers of Hanoi", 0, NULL
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 };
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 };
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 };
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 };
271 static float g = 3.0 * 9.80665; /* hmm, looks like we need more gravity, Scotty... */
273 static void checkAllocAndExit(Bool item, char *descr) {
275 fprintf(stderr, "%s: unable to allocate memory for %s\n",
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)])
284 /* push disk d onto pole idx */
285 static Disk *push(glhcfg *glhanoi, int idx, Disk * d)
287 return DOPUSH(&glhanoi->pole[idx], d);
290 /* pop the top disk from pole idx */
291 static Disk *pop(glhcfg *glhanoi, int idx)
293 return DOPOP(&glhanoi->pole[idx]);
296 static inline void swap(int *x, int *y)
304 * magic - it's magic...
305 * Return 1 if the number of trailing zeroes on i is even, unless i is 1 or 0.
307 static int magic(int i)
312 while((i & 0x01) == 0) {
316 return count % 2 == 0;
319 static float distance(float *p0, float *p1)
325 return (float)sqrt(x * x + y * y + z * z);
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)))
333 static GLfloat A(GLfloat a, GLfloat b, GLfloat c)
336 return c / (a * b - 0.25 * sum * sum);
340 static void moveSetup(glhcfg *glhanoi, Disk * disk)
344 int src = glhanoi->src;
345 int dst = glhanoi->dst;
347 GLfloat sintheta, costheta;
349 double dx, dz; /* total x and z distances from src to dst */
350 Pole *poleSrc, *poleDst;
352 poleSrc = &(glhanoi->pole[src]);
353 poleDst = &(glhanoi->pole[dst]);
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];
363 dx = disk->xmax - disk->xmin;
364 dz = disk->zmax - disk->zmin;
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);
371 disk->rotAngle = xxx;
373 if(random() % 4 == 0) {
375 disk->rotAngle = -disk->rotAngle;
378 disk->rotAngle = -180.0;
381 disk->base0 = glhanoi->diskPos[poleSrc->count];
382 disk->base1 = (glhanoi->state == FINISHED) ?
383 disk->base0 : glhanoi->diskPos[poleDst->count];
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);
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);
399 costheta = cos(theta);
400 sintheta = sin(theta);
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;
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;
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 */
422 /* For debugging: show a value as a string of ones and zeroes
423 static const char *byteToBinary(int x) {
427 for (z = 128, i = 0; z > 0; z >>= 1, i++) {
428 b[i] = ((x & z) == z) ? '1' : '0';
436 static void pushMove(glhcfg *glhanoi, int n, int src, int dst, int avail) {
437 SubProblem *sp = &(glhanoi->solveStack[glhanoi->solveStackIdx++]);
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);
448 sp->available = avail & ~((unsigned long)(1 << src))
449 & ~((unsigned long)(1 << dst));
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));
456 static Bool solveStackEmpty(glhcfg *glhanoi) {
457 return (glhanoi->solveStackIdx < 1);
460 static SubProblem *popMove(glhcfg *glhanoi) {
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)); */
469 /* Return number of bits set in b */
470 static int numBits(unsigned long b) {
479 /* Return index (power of 2) of least significant 1 bit. */
480 static int bitScan(unsigned long b) {
482 for (count = 0; b; count++, b >>= 1) {
483 if (b & 0x1u) return count;
488 /* A bit pattern representing all poles */
489 #define ALL_POLES ((1 << glhanoi->numberOfPoles) - 1)
491 #define REMOVE_BIT(a, b) ((a) & ~(1 << (b)))
492 #define ADD_BIT(a, b) ((a) | (1 << (b)))
494 static void makeMove(glhcfg *glhanoi)
496 if (glhanoi->numberOfPoles == 3) {
497 int fudge = glhanoi->move + 2;
498 int magicNumber = magic(fudge);
501 glhanoi->currentDisk = pop(glhanoi, glhanoi->src);
502 moveSetup(glhanoi, glhanoi->currentDisk);
503 push(glhanoi, glhanoi->dst, glhanoi->currentDisk);
507 if(fudge == 1 || magicNumber) {
508 swap(&glhanoi->src, &glhanoi->tmp);
510 if(fudge == 0 || glhanoi->magicNumber) {
511 swap(&glhanoi->dst, &glhanoi->tmp);
513 glhanoi->magicNumber = magicNumber;
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));
527 while (!solveStackEmpty(glhanoi)) {
529 sp = *popMove(glhanoi);
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 */
538 glhanoi->currentDisk = pop(glhanoi, sp.src);
539 moveSetup(glhanoi, glhanoi->currentDisk);
540 push(glhanoi, sp.dst, glhanoi->currentDisk);
544 /* Divide and conquer, using Frame-Stewart algorithm, until we get to base case */
545 if (sp.nDisks == 1) break;
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));
553 if (k >= sp.nDisks) k = sp.nDisks - 1;
554 else if (k < 1) k = 1;
556 tmp = bitScan(sp.available);
557 /* fprintf(stderr, "Debug: k is %d, tmp is %d\n", k, tmp); */
559 fprintf(stderr, "Error: n > 1 (%d) and no poles available\n",
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));
571 /* Repeat until we've found a move we can make. */
577 static double lerp(double alpha, double start, double end)
579 return start + alpha * (end - start);
582 static void upfunc(GLdouble t, Disk * d)
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;
588 d->rotation[1] = 0.0;
591 static void parafunc(GLdouble t, Disk * d)
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;
598 d->rotation[1] = d->rotAngle * t / d->t2;
599 /* d->rotAngle * (d->position[0] - d->xmin) / (d->xmax - d->xmin); */
602 static void downfunc(GLdouble t, Disk * d)
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;
608 d->rotation[1] = 0.0;
611 #define normalizeQ(i) ((i) >= glhanoi->trailQSize ? (i) - glhanoi->trailQSize : (i))
612 #define normalizeQNeg(i) ((i) < 0 ? (i) + glhanoi->trailQSize : (i))
614 /* Add trail point at position posn at time t onto back of trail queue.
615 Removes old trails if necessary to make room. */
616 static void enQTrail(glhcfg *glhanoi, GLfloat *posn)
618 if (glhanoi->trailQSize && glhanoi->state != MONEY_SHOT) {
619 TrailPoint *tp = &(glhanoi->trailQ[glhanoi->trailQBack]);
620 double t = getTime();
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;
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);
637 /* Mark last trailpoint in queue as the end of a trail. */
638 /* was: #define endTrail(glh) ((glh)->trailQ[(glh)->trailQBack].isEnd = True) */
639 static void endTrail(glhcfg *glhanoi) {
640 if (glhanoi->trailQSize)
641 glhanoi->trailQ[normalizeQNeg(glhanoi->trailQBack - 1)].isEnd = True;
644 /* Update disk d's position and rotation based on time t.
645 Returns true iff move is finished. */
646 static Bool computePosition(glhcfg *glhanoi, GLfloat t, Disk * d)
648 Bool finished = False;
652 } else if(t < d->t1 + d->t2) {
653 parafunc(t - d->t1, d);
654 enQTrail(glhanoi, d->position);
656 downfunc(t - d->t1 - d->t2, d);
657 if(d->position[1] <= d->base1) {
658 d->position[1] = d->base1;
666 static void updateView(glhcfg *glhanoi)
668 double longitude, latitude, radius;
669 double a, b, c, A, B;
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);
683 latitude = 1.0 - latitude;
686 radius = 1.0 - radius;
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);
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));
705 static void changeState(glhcfg *glhanoi, State state)
707 glhanoi->state = state;
708 glhanoi->startTime = getTime();
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));
718 static void update_glhanoi(glhcfg *glhanoi)
720 double t = getTime() - glhanoi->startTime;
724 switch (glhanoi->state) {
726 if(t < glhanoi->duration) {
730 if(glhanoi->numberOfDisks % 2 == 0) {
731 swap(&glhanoi->tmp, &glhanoi->dst);
733 glhanoi->magicNumber = 1;
735 changeState(glhanoi, MOVE_DISK);
739 if(computePosition(glhanoi, t * glhanoi->currentDisk->speed, glhanoi->currentDisk)) {
740 changeState(glhanoi, MOVE_FINISHED);
746 if(!finishedHanoi(glhanoi)) {
748 changeState(glhanoi, MOVE_DISK);
750 glhanoi->duration = FINISH_DURATION;
751 changeState(glhanoi, FINISHED);
756 if (t < glhanoi->duration)
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);
765 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
766 push(glhanoi, glhanoi->dst, &glhanoi->disk[i]);
768 changeState(glhanoi, MONEY_SHOT);
773 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
774 double delay = 0.25 * i;
782 finished = computePosition(glhanoi, t - delay, &glhanoi->disk[i]);
783 glhanoi->disk[i].rotation[1] = 0.0;
790 glhanoi->src = glhanoi->oldsrc;
791 glhanoi->tmp = glhanoi->oldtmp;
792 glhanoi->dst = glhanoi->olddst;
793 changeState(glhanoi, START);
799 fprintf(stderr, "Invalid state\n");
804 static void HSVtoRGBf(GLfloat h, GLfloat s, GLfloat v,
805 GLfloat * r, GLfloat * g, GLfloat * b)
812 GLfloat i, f, p, q, t;
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 */
820 q = v * (1.0 - (s * f));
821 t = v * (1.0 - (s * (1.0 - f)));
857 static void HSVtoRGBv(GLfloat * hsv, GLfloat * rgb)
859 HSVtoRGBf(hsv[0], hsv[1], hsv[2], &rgb[0], &rgb[1], &rgb[2]);
862 static void setMaterial(const GLfloat color[3], const GLfloat hlite[3], int shininess)
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] */
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 :-( )
878 static int drawTube(GLdouble bottomRadius, GLdouble topRadius,
879 GLdouble bottomThickness, GLdouble topThickness,
880 GLdouble height, GLuint nSlice, GLuint nLoop)
884 GLfloat *cosCache = malloc(sizeof(GLfloat) * nSlice);
885 GLfloat *sinCache = malloc(sizeof(GLfloat) * nSlice);
888 GLint lastSlice = nSlice - 1;
892 if(bottomThickness > bottomRadius) {
893 bottomThickness = bottomRadius;
895 if(topThickness > topRadius) {
896 topThickness = topRadius;
898 if(bottomThickness < 0.0) {
899 bottomThickness = 0.0;
901 if(topThickness < 0.0) {
904 /* if(topRadius >= bottomRadius) {
905 maxRadius = topRadius;
907 maxRadius = bottomRadius;
912 radius = bottomRadius;
913 innerRadius = bottomRadius - bottomThickness;
914 /* innerTexCoordSize = texCoordSize * innerRadius / maxRadius; */
915 /* outerTexCoordSize = texCoordSize * radius / maxRadius; */
916 /* yTexCoord = minTexCoord; */
918 glBegin(GL_QUAD_STRIP);
920 glNormal3f(0.0, -1.0, 0.0);
922 /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + innerTexCoordSize); */
923 glVertex3f(0.0, y, innerRadius);
925 /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + outerTexCoordSize); */
926 glVertex3f(0.0, y, radius);
928 for(slice = lastSlice; slice >= 0; --slice) {
929 GLfloat theta = 2.0 * M_PI * (double)slice / nSlice;
931 cosCache[slice] = cos(theta);
932 sinCache[slice] = sin(theta);
934 /* glTexCoord3f(midTexCoord + sinCache[slice] * innerTexCoordSize, */
936 /* midTexCoord + cosCache[slice] * innerTexCoordSize); */
937 glVertex3f(innerRadius * sinCache[slice], y,
938 innerRadius * cosCache[slice]);
939 /* glTexCoord3f(midTexCoord + sinCache[slice] * outerTexCoordSize, */
941 /* midTexCoord + cosCache[slice] * outerTexCoordSize); */
942 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
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 +
956 GLfloat lowerY = height * (float)loop / (nLoop);
957 GLfloat upperY = height * (float)(loop + 1) / (nLoop);
958 GLfloat factor = (topRadius - topThickness) -
959 (bottomRadius - bottomThickness);
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]);
971 glNormal3f(0.0, 0.0, 1.0);
972 glVertex3f(0.0, upperY, upperRadius);
973 glVertex3f(0.0, lowerY, lowerRadius);
978 lowerRadius = bottomRadius - bottomThickness +
979 factor * (float)loop / (nLoop);
980 upperRadius = bottomRadius - bottomThickness +
981 factor * (float)(loop + 1) / (nLoop);
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]);
1001 innerRadius = topRadius - topThickness;
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]);
1009 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
1012 glVertex3f(0.0, y, innerRadius);
1013 glVertex3f(0.0, y, radius);
1018 static int drawPole(GLfloat radius, GLfloat length)
1020 return drawTube(radius, radius, radius, radius, length, NSLICE, NLOOPS);
1023 static int drawDisk3D(GLdouble inner_radius, GLdouble outer_radius,
1026 return drawTube(outer_radius, outer_radius, outer_radius - inner_radius,
1027 outer_radius - inner_radius, height, NSLICE, NLOOPS);
1030 /* used for drawing base */
1031 static int drawCuboid(GLfloat length, GLfloat width, GLfloat height)
1033 GLfloat xmin = -length / 2.0f;
1034 GLfloat xmax = length / 2.0f;
1035 GLfloat zmin = -width / 2.0f;
1036 GLfloat zmax = width / 2.0f;
1037 GLfloat ymin = 0.0f;
1038 GLfloat ymax = height;
1044 glVertex3f(xmin, ymin, zmax); /* 0 */
1045 glVertex3f(xmax, ymin, zmax); /* 1 */
1046 glVertex3f(xmax, ymax, zmax); /* 2 */
1047 glVertex3f(xmin, ymax, zmax); /* 3 */
1051 glVertex3f(xmax, ymin, zmax); /* 1 */
1052 glVertex3f(xmax, ymin, zmin); /* 5 */
1053 glVertex3f(xmax, ymax, zmin); /* 6 */
1054 glVertex3f(xmax, ymax, zmax); /* 2 */
1058 glVertex3f(xmax, ymin, zmin); /* 5 */
1059 glVertex3f(xmin, ymin, zmin); /* 4 */
1060 glVertex3f(xmin, ymax, zmin); /* 7 */
1061 glVertex3f(xmax, ymax, zmin); /* 6 */
1065 glVertex3f(xmin, ymin, zmin); /* 4 */
1066 glVertex3f(xmin, ymin, zmax); /* 0 */
1067 glVertex3f(xmin, ymax, zmax); /* 3 */
1068 glVertex3f(xmin, ymax, zmin); /* 7 */
1072 glVertex3f(xmin, ymax, zmax); /* 3 */
1073 glVertex3f(xmax, ymax, zmax); /* 2 */
1074 glVertex3f(xmax, ymax, zmin); /* 6 */
1075 glVertex3f(xmin, ymax, zmin); /* 7 */
1079 glVertex3f(xmin, ymin, zmin); /* 4 */
1080 glVertex3f(xmax, ymin, zmin); /* 5 */
1081 glVertex3f(xmax, ymin, zmax); /* 1 */
1082 glVertex3f(xmin, ymin, zmax); /* 0 */
1088 /* Set normal vector in xz plane, based on rotation around center. */
1089 static void setNormalV(glhcfg *glhanoi, GLfloat theta, int y1, int y2, int r1) {
1090 if (y1 == y2) /* up/down */
1091 glNormal3f(0.0, y1 ? 1.0 : -1.0, 0.0);
1092 else if (!r1) /* inward */
1093 glNormal3f(-cos(theta), 0.0, -sin(theta));
1095 glNormal3f(cos(theta), 0.0, sin(theta));
1098 /* y1, r1, y2, r2 are indices into y, r, beg, end */
1099 static int drawBaseStrip(glhcfg *glhanoi, int y1, int r1, int y2, int r2,
1100 GLfloat y[2], GLfloat r[2], GLfloat beg[2][2], GLfloat end[2][2]) {
1102 GLfloat theta, costh, sinth, x[2], z[2];
1103 GLfloat theta1 = (M_PI * 2) / (glhanoi->numberOfPoles + 1);
1105 glBegin(GL_QUAD_STRIP);
1107 /* beginning edge */
1108 glVertex3f(beg[r1][0], y[y1], beg[r1][1]);
1109 glVertex3f(beg[r2][0], y[y2], beg[r2][1]);
1110 setNormalV(glhanoi, theta1, y1, y2, r1);
1112 for (i = 1; i < glhanoi->numberOfPoles; i++) {
1113 theta = theta1 * (i + 0.5);
1116 x[0] = costh * r[0];
1117 x[1] = costh * r[1];
1118 z[0] = sinth * r[0];
1119 z[1] = sinth * r[1];
1121 glVertex3f(x[r1], y[y1], z[r1]);
1122 glVertex3f(x[r2], y[y2], z[r2]);
1124 setNormalV(glhanoi, theta1 * (i + 1), y1, y2, r1);
1128 glVertex3f(end[r1][0], y[y1], end[r1][1]);
1129 glVertex3f(end[r2][0], y[y2], end[r2][1]);
1130 setNormalV(glhanoi, glhanoi->numberOfPoles, y1, y2, r1);
1133 return glhanoi->numberOfPoles;
1136 /* Draw base such that poles are distributed around a regular polygon. */
1137 static int drawRoundBase(glhcfg *glhanoi) {
1139 GLfloat theta, sinth, costh;
1142 r[0] = (minimum) inner radius of base at vertices
1143 r[1] = (minimum) outer radius of base at vertices
1144 y[0] = bottom of base
1145 y[1] = top of base */
1147 /* positions of end points: beginning, end.
1148 beg[0] is inner corner of beginning of base, beg[1] is outer corner.
1149 beg[i][0] is x, [i][1] is z. */
1150 GLfloat beg[2][2], end[2][2], begNorm, endNorm;
1151 /* ratio of radius at base vertices to ratio at poles */
1152 GLfloat longer = 1.0 / cos(M_PI / (glhanoi->numberOfPoles + 1));
1154 r[0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * longer;
1155 r[1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * longer;
1157 y[1] = glhanoi->baseHeight;
1159 /* compute beg, end. Make the ends square. */
1160 theta = M_PI * 2 / (glhanoi->numberOfPoles + 1);
1164 beg[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh +
1165 glhanoi->maxDiskRadius * sinth;
1166 beg[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh +
1167 glhanoi->maxDiskRadius * sinth;
1168 beg[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth -
1169 glhanoi->maxDiskRadius * costh;
1170 beg[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth -
1171 glhanoi->maxDiskRadius * costh;
1172 begNorm = theta - M_PI * 0.5;
1174 theta = M_PI * 2 * glhanoi->numberOfPoles / (glhanoi->numberOfPoles + 1);
1178 end[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh -
1179 glhanoi->maxDiskRadius * sinth;
1180 end[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh -
1181 glhanoi->maxDiskRadius * sinth;
1182 end[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth +
1183 glhanoi->maxDiskRadius * costh;
1184 end[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth +
1185 glhanoi->maxDiskRadius * costh;
1186 endNorm = theta + M_PI * 0.5;
1188 /* bottom: never seen
1189 polys = drawBaseStrip(glhanoi, 0, 0, 0, 1, y, r, beg, end); */
1191 polys += drawBaseStrip(glhanoi, 0, 1, 1, 1, y, r, beg, end);
1193 polys += drawBaseStrip(glhanoi, 1, 1, 1, 0, y, r, beg, end);
1195 polys += drawBaseStrip(glhanoi, 1, 0, 0, 0, y, r, beg, end);
1200 glVertex3f(beg[0][0], y[1], beg[0][1]);
1201 glVertex3f(beg[1][0], y[1], beg[1][1]);
1202 glVertex3f(beg[1][0], y[0], beg[1][1]);
1203 glVertex3f(beg[0][0], y[0], beg[0][1]);
1204 glNormal3f(cos(begNorm), 0, sin(begNorm));
1206 glVertex3f(end[0][0], y[0], end[0][1]);
1207 glVertex3f(end[1][0], y[0], end[1][1]);
1208 glVertex3f(end[1][0], y[1], end[1][1]);
1209 glVertex3f(end[0][0], y[1], end[0][1]);
1210 glNormal3f(cos(endNorm), 0, sin(endNorm));
1219 static int drawDisks(glhcfg *glhanoi)
1225 glTranslatef(0.0f, glhanoi->baseHeight, 0.0f);
1226 for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1227 Disk *disk = &glhanoi->disk[i];
1228 GLfloat *pos = disk->position;
1229 GLfloat *rot = disk->rotation;
1232 glTranslatef(pos[0], pos[1], pos[2]);
1234 glTranslatef(0.0, glhanoi->diskHeight / 2.0, 0.0);
1235 /* rotate around different axis depending on phi */
1236 if (disk->phi != 0.0)
1237 glRotatef(-disk->phi, 0.0, 1.0, 0.0);
1238 glRotatef(rot[1], 0.0, 0.0, 1.0);
1239 if (disk->phi != 0.0)
1240 glRotatef(disk->phi, 0.0, 1.0, 0.0);
1241 glTranslatef(0.0, -glhanoi->diskHeight / 2.0, 0.0);
1243 glCallList(disk->displayList);
1244 polys += disk->polys;
1251 static GLfloat getDiskRadius(glhcfg *glhanoi, int i)
1253 GLfloat retVal = glhanoi->maxDiskRadius *
1254 ((GLfloat) i + 3.0) / (glhanoi->numberOfDisks + 3.0);
1258 static void initData(glhcfg *glhanoi)
1261 GLfloat sinPiOverNP;
1263 glhanoi->baseLength = BASE_LENGTH;
1264 if (glhanoi->layoutLinear) {
1265 glhanoi->maxDiskRadius = glhanoi->baseLength /
1266 (2 * 0.95 * glhanoi->numberOfPoles);
1268 sinPiOverNP = sin(M_PI / (glhanoi->numberOfPoles + 1));
1269 glhanoi->maxDiskRadius = (sinPiOverNP * glhanoi->baseLength * 0.5 * 0.95) / (1 + sinPiOverNP);
1272 glhanoi->poleDist = glhanoi->baseLength * 0.5 - glhanoi->maxDiskRadius;
1273 glhanoi->poleRadius = glhanoi->maxDiskRadius / (glhanoi->numberOfDisks + 3.0);
1274 /* fprintf(stderr, "Debug: baseL = %f, maxDiskR = %f, poleR = %f\n",
1275 glhanoi->baseLength, glhanoi->maxDiskRadius, glhanoi->poleRadius); */
1276 glhanoi->baseWidth = 2.0 * glhanoi->maxDiskRadius;
1277 glhanoi->poleOffset = 2.0 * getDiskRadius(glhanoi, glhanoi->maxDiskIdx);
1278 glhanoi->diskHeight = 2.0 * glhanoi->poleRadius;
1279 glhanoi->baseHeight = 2.0 * glhanoi->poleRadius;
1280 glhanoi->poleHeight = glhanoi->numberOfDisks *
1281 glhanoi->diskHeight + glhanoi->poleRadius;
1282 /* numberOfMoves only applies if numberOfPoles = 3 */
1283 glhanoi->numberOfMoves = (1 << glhanoi->numberOfDisks) - 1;
1284 /* use golden ratio */
1285 glhanoi->boardSize = glhanoi->baseLength * 0.5 * (1.0 + sqrt(5.0));
1287 glhanoi->pole = (Pole *)calloc(glhanoi->numberOfPoles, sizeof(Pole));
1288 checkAllocAndExit(!!glhanoi->pole, "poles");
1290 for(i = 0; i < glhanoi->numberOfPoles; i++) {
1292 !!(glhanoi->pole[i].data = calloc(glhanoi->numberOfDisks, sizeof(Disk *))),
1294 glhanoi->pole[i].size = glhanoi->numberOfDisks;
1297 !!(glhanoi->diskPos = calloc(glhanoi->numberOfDisks, sizeof(double))),
1300 if (glhanoi->trailQSize) {
1301 glhanoi->trailQ = (TrailPoint *)calloc(glhanoi->trailQSize, sizeof(TrailPoint));
1302 checkAllocAndExit(!!glhanoi->trailQ, "trail queue");
1303 } else glhanoi->trailQ = (TrailPoint *)NULL;
1304 glhanoi->trailQFront = glhanoi->trailQBack = 0;
1306 glhanoi->the_rotator = make_rotator(0.1, 0.025, 0, 1, 0.005, False);
1307 /* or glhanoi->the_rotator = make_rotator(0.025, 0.025, 0.025, 0.5, 0.005, False); */
1308 glhanoi->button_down_p = False;
1310 glhanoi->src = glhanoi->oldsrc = 0;
1311 glhanoi->tmp = glhanoi->oldtmp = 1;
1312 glhanoi->dst = glhanoi->olddst = glhanoi->numberOfPoles - 1;
1314 if (glhanoi->numberOfPoles > 3) {
1315 glhanoi->solveStackSize = glhanoi->numberOfDisks + 2;
1316 glhanoi->solveStack = (SubProblem *)calloc(glhanoi->solveStackSize, sizeof(SubProblem));
1317 checkAllocAndExit(!!glhanoi->solveStack, "solving stack");
1318 glhanoi->solveStackIdx = 0;
1322 static void initView(glhcfg *glhanoi)
1324 glhanoi->camera[0] = 0.0;
1325 glhanoi->camera[1] = 0.0;
1326 glhanoi->camera[2] = 0.0;
1327 glhanoi->centre[0] = 0.0;
1328 glhanoi->centre[1] = glhanoi->poleHeight * 3.0;
1329 glhanoi->centre[2] = 0.0;
1333 * noise_improved.c - based on ImprovedNoise.java
1334 * JAVA REFERENCE IMPLEMENTATION OF IMPROVED NOISE - COPYRIGHT 2002 KEN PERLIN.
1336 static double fade(double t)
1338 return t * t * t * (t * (t * 6 - 15) + 10);
1341 static double grad(int hash, double x, double y, double z)
1343 int h = hash & 15; /* CONVERT LO 4 BITS OF HASH CODE */
1344 double u = h < 8 ? x : y, /* INTO 12 GRADIENT DIRECTIONS. */
1345 v = h < 4 ? y : h == 12 || h == 14 ? x : z;
1346 return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
1349 static const int permutation[] = { 151, 160, 137, 91, 90, 15,
1350 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142,
1351 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 26,
1352 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237,
1353 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71,
1354 134, 139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60,
1355 211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 102, 143,
1356 54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89,
1357 18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 198,
1358 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118,
1359 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189,
1360 28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70,
1361 221, 153, 101, 155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108,
1362 110, 79, 113, 224, 232, 178, 185, 112, 104, 218, 246, 97, 228, 251,
1363 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241, 81, 51, 145,
1364 235, 249, 14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 157, 184,
1365 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205,
1366 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61,
1370 static void initNoise(glhcfg *glhanoi)
1373 for(i = 0; i < 256; i++)
1374 glhanoi->p[256 + i] = glhanoi->p[i] = permutation[i];
1377 static double improved_noise(glhcfg *glhanoi, double x, double y, double z)
1380 int A, AA, AB, B, BA, BB;
1381 int X = (int)floor(x) & 255, /* FIND UNIT CUBE THAT */
1382 Y = (int)floor(y) & 255, /* CONTAINS POINT. */
1383 Z = (int)floor(z) & 255;
1384 if(!glhanoi->noise_initted) {
1386 glhanoi->noise_initted = 1;
1388 x -= floor(x); /* FIND RELATIVE X,Y,Z */
1389 y -= floor(y); /* OF POINT IN CUBE. */
1391 u = fade(x), /* COMPUTE FADE CURVES */
1392 v = fade(y), /* FOR EACH OF X,Y,Z. */
1394 A = glhanoi->p[X] + Y;
1395 AA = glhanoi->p[A] + Z;
1396 AB = glhanoi->p[A + 1] + Z, /* HASH COORDINATES OF */
1397 B = glhanoi->p[X + 1] + Y;
1398 BA = glhanoi->p[B] + Z;
1399 BB = glhanoi->p[B + 1] + Z; /* THE 8 CUBE CORNERS, */
1400 return lerp(w, lerp(v, lerp(u, grad(glhanoi->p[AA], x, y, z),/* AND ADD */
1401 grad(glhanoi->p[BA], x - 1, y, z)),/* BLENDED */
1402 lerp(u, grad(glhanoi->p[AB], x, y - 1, z),/* RESULTS */
1403 grad(glhanoi->p[BB], x - 1, y - 1, z))),/* FROM 8 CORNERS */
1404 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 */
1405 lerp(u, grad(glhanoi->p[AB + 1], x, y - 1, z - 1),
1406 grad(glhanoi->p[BB + 1], x - 1, y - 1, z - 1))));
1410 * end noise_improved.c - based on ImprovedNoise.java
1415 /* GLfloat *points; */
1418 typedef struct tex_col_t tex_col_t;
1420 static GLubyte *makeTexture(glhcfg *glhanoi, int x_size, int y_size, int z_size,
1421 GLuint(*texFunc) (glhcfg *, double, double, double,
1422 tex_col_t *), tex_col_t * colours)
1425 GLubyte *textureData;
1431 calloc(x_size * y_size * z_size, sizeof(GLuint))) == NULL) {
1440 texturePtr = (void *)textureData;
1441 for(k = 0; k < z_size; k++, z += zi) {
1443 for(j = 0; j < y_size; j++, y += yi) {
1445 for(i = 0; i < x_size; i++, x += xi) {
1446 *texturePtr = texFunc(glhanoi, x, y, z, colours);
1454 static void freeTexCols(tex_col_t*p)
1460 static tex_col_t *makeMarbleColours(void)
1462 tex_col_t *marbleColours;
1465 marbleColours = malloc(sizeof(tex_col_t));
1466 if(marbleColours == NULL) return NULL;
1467 marbleColours->colours = calloc(sizeof(GLuint), ncols);
1468 if(marbleColours->colours == NULL) return NULL;
1469 marbleColours->ncols = ncols;
1471 marbleColours->colours[0] = 0x3f3f3f3f;
1472 marbleColours->colours[1] = 0xffffffff;
1474 return marbleColours;
1477 static double turb(glhcfg *glhanoi, double x, double y, double z, int octaves)
1482 for(oct = 0; oct < octaves; ++oct) {
1483 r += fabs(improved_noise(glhanoi, freq * x, freq * y, freq * z)) / freq;
1489 static void perturb(glhcfg *glhanoi, double *x, double *y, double *z, double scale)
1491 double t = scale * turb(glhanoi, *x, *y, *z, 4);
1497 static double f_m(double x, double y, double z)
1499 return sin(3.0 * M_PI * x);
1502 static GLuint C_m(double x, const tex_col_t * tex_cols)
1504 int r = tex_cols->colours[0] & 0xff;
1505 int g = tex_cols->colours[0] >> 8 & 0xff;
1506 int b = tex_cols->colours[0] >> 16 & 0xff;
1511 factor = (1.0 + sin(2.0 * M_PI * x)) / 2.0;
1513 r1 = (tex_cols->colours[1] & 0xff);
1514 g1 = (tex_cols->colours[1] >> 8 & 0xff);
1515 b1 = (tex_cols->colours[1] >> 16 & 0xff);
1517 r += (int)(factor * (r1 - r));
1518 g += (int)(factor * (g1 - g));
1519 b += (int)(factor * (b1 - b));
1521 return 0xff000000 | (b << 16) | (g << 8) | r;
1525 static GLuint makeMarbleTexture(glhcfg *glhanoi, double x, double y, double z, tex_col_t * colours)
1527 perturb(glhanoi, &x, &y, &z, MARBLE_SCALE);
1528 return C_m(f_m(x, y, z), colours);
1531 static void setTexture(glhcfg *glhanoi, int n)
1533 glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[n]);
1536 /* returns 1 on failure, 0 on success */
1537 static int makeTextures(glhcfg *glhanoi)
1539 GLubyte *marbleTexture;
1540 tex_col_t *marbleColours;
1542 glGenTextures(N_TEXTURES, glhanoi->textureNames);
1544 if((marbleColours = makeMarbleColours()) == NULL) {
1548 makeTexture(glhanoi, MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 1,
1549 makeMarbleTexture, marbleColours)) == NULL) {
1553 glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[0]);
1554 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
1555 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
1556 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
1557 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
1558 glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA,
1559 MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 0,
1560 GL_RGBA, GL_UNSIGNED_BYTE, marbleTexture);
1561 free(marbleTexture);
1562 freeTexCols(marbleColours);
1567 static void initFloor(glhcfg *glhanoi)
1570 float tileSize = glhanoi->boardSize / BOARD_SQUARES;
1571 float x0, x1, z0, z1;
1572 float tx0, tx1, tz0, tz1;
1573 const float *col = cWhite;
1574 float texIncr = 1.0 / BOARD_SQUARES;
1576 glhanoi->floorpolys = 0;
1577 checkAllocAndExit(!!(glhanoi->floorList = glGenLists(1)), "floor display list");
1578 glNewList(glhanoi->floorList, GL_COMPILE);
1579 x0 = -glhanoi->boardSize / 2.0;
1581 setMaterial(col, cWhite, 128);
1582 setTexture(glhanoi, 0);
1584 for(i = 0; i < BOARD_SQUARES; i++, x0 += tileSize, tx0 += texIncr) {
1586 tx1 = tx0 + texIncr;
1587 z0 = -glhanoi->boardSize / 2.0;
1589 for(j = 0; j < BOARD_SQUARES; j++, z0 += tileSize, tz0 += texIncr) {
1590 int colIndex = (i + j) & 0x1;
1593 tz1 = tz0 + texIncr;
1600 setMaterial(col, cWhite, 100);
1604 glTexCoord2d(tx0, tz0);
1605 glVertex3f(x0, 0.0, z0);
1607 glTexCoord2d(tx0, tz1);
1608 glVertex3f(x0, 0.0, z1);
1610 glTexCoord2d(tx1, tz1);
1611 glVertex3f(x1, 0.0, z1);
1613 glTexCoord2d(tx1, tz0);
1614 glVertex3f(x1, 0.0, z0);
1615 glhanoi->floorpolys++;
1622 static void initBase(glhcfg *glhanoi)
1624 checkAllocAndExit(!!(glhanoi->baseList = glGenLists(1)), "tower bases display list");
1626 glNewList(glhanoi->baseList, GL_COMPILE);
1627 setMaterial(baseColor, cWhite, 50);
1628 if (glhanoi->layoutLinear) {
1629 glhanoi->basepolys = drawCuboid(glhanoi->baseLength, glhanoi->baseWidth,
1630 glhanoi->baseHeight);
1632 glhanoi->basepolys = drawRoundBase(glhanoi);
1637 static void initTowers(glhcfg *glhanoi)
1641 checkAllocAndExit(!!(glhanoi->poleList = glGenLists(1)), "poles display list\n");
1643 glNewList(glhanoi->poleList, GL_COMPILE);
1644 /* glTranslatef(-glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5f, glhanoi->baseHeight, 0.0f); */
1645 setMaterial(poleColor, cWhite, 50);
1646 for (i = 0; i < glhanoi->numberOfPoles; i++) {
1647 GLfloat *p = glhanoi->pole[i].position;
1648 GLfloat rad = (M_PI * 2.0 * (i + 1)) / (glhanoi->numberOfPoles + 1);
1650 p[1] = glhanoi->baseHeight;
1652 if (glhanoi->layoutLinear) {
1654 p[0] = -glhanoi->poleOffset * ((glhanoi->numberOfPoles - 1) * 0.5f - i);
1657 /* Circular layout: */
1658 p[0] = cos(rad) * glhanoi->poleDist;
1659 p[2] = sin(rad) * glhanoi->poleDist;
1663 glTranslatef(p[0], p[1], p[2]);
1664 glhanoi->polepolys = drawPole(glhanoi->poleRadius, glhanoi->poleHeight);
1671 /* Parameterized hue based on input 0.0 - 1.0. */
1672 static double cfunc(double x)
1676 return (1.0 / 12.0) / (1.0 / 7.0) * x;
1680 return (1.0 + 1.0 / 6.0) * x - 1.0 / 6.0;
1683 return (2.0 + 1.0 / 3.0) * x - 2.0 / 3.0;
1686 return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1688 return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1691 static void initDisks(glhcfg *glhanoi)
1694 glhanoi->disk = (Disk *) calloc(glhanoi->numberOfDisks, sizeof(Disk));
1695 checkAllocAndExit(!!glhanoi->disk, "disks");
1697 for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1698 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1699 double f = cfunc((GLfloat) i / (GLfloat) glhanoi->numberOfDisks);
1700 GLfloat diskColor = f * 360.0;
1702 Disk *disk = &glhanoi->disk[i];
1705 disk->position[0] = glhanoi->pole[0].position[0]; /* -glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5; */
1706 disk->position[1] = glhanoi->diskHeight * height;
1707 disk->position[2] = glhanoi->pole[0].position[2];
1708 disk->rotation[0] = 0.0;
1709 disk->rotation[1] = 0.0;
1710 disk->rotation[2] = 0.0;
1713 /* make smaller disks move faster */
1714 disk->speed = lerp(((double)glhanoi->numberOfDisks - i) / glhanoi->numberOfDisks,
1715 1.0, glhanoi->speed);
1716 /* fprintf(stderr, "disk id: %d, alpha: %0.2f, speed: %0.2f\n", disk->id,
1717 ((double)(glhanoi->maxDiskIdx - i)) / glhanoi->numberOfDisks, disk->speed); */
1719 color[0] = diskColor;
1722 HSVtoRGBv(color, color);
1724 checkAllocAndExit(!!(disk->displayList = glGenLists(1)), "disk display list");
1725 glNewList(disk->displayList, GL_COMPILE);
1726 setMaterial(color, cWhite, 100.0);
1727 disk->polys += drawDisk3D(glhanoi->poleRadius,
1728 getDiskRadius(glhanoi, i),
1729 glhanoi->diskHeight);
1730 /*fprintf(stderr, "Debug: disk %d has radius %f\n", i,
1731 getDiskRadius(glhanoi, i)); */
1734 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
1735 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1736 int h = glhanoi->maxDiskIdx - i;
1737 glhanoi->diskPos[h] = glhanoi->diskHeight * height;
1738 push(glhanoi, glhanoi->src, &glhanoi->disk[i]);
1742 static void initLights(Bool state)
1745 glLightfv(GL_LIGHT0, GL_POSITION, pos0);
1746 glLightfv(GL_LIGHT0, GL_AMBIENT, amb0);
1747 glLightfv(GL_LIGHT0, GL_DIFFUSE, dif0);
1748 glLightfv(GL_LIGHT0, GL_SPECULAR, spc0);
1750 glLightfv(GL_LIGHT1, GL_POSITION, pos1);
1751 glLightfv(GL_LIGHT1, GL_AMBIENT, amb1);
1752 glLightfv(GL_LIGHT1, GL_DIFFUSE, dif1);
1753 glLightfv(GL_LIGHT1, GL_SPECULAR, spc1);
1755 glEnable(GL_LIGHTING);
1756 glEnable(GL_LIGHT0);
1757 glEnable(GL_LIGHT1);
1759 glDisable(GL_LIGHTING);
1763 static int drawFloor(glhcfg *glhanoi)
1765 glCallList(glhanoi->floorList);
1766 return glhanoi->floorpolys;
1769 static int drawTowers(glhcfg *glhanoi)
1771 glCallList(glhanoi->baseList);
1772 glCallList(glhanoi->poleList);
1773 return glhanoi->basepolys + glhanoi->polepolys;
1776 static int drawTrails1(glhcfg *glhanoi, double t, double thickness, double alpha) {
1777 int i, prev = -1, lines = 0;
1779 GLfloat trailDurInv = 1.0f / glhanoi->trailDuration;
1781 glLineWidth(thickness);
1785 for (i = glhanoi->trailQFront;
1786 i != glhanoi->trailQBack;
1787 i = normalizeQ(i + 1)) {
1788 TrailPoint *tqi = &(glhanoi->trailQ[i]);
1790 if (!fresh && t > tqi->endTime) {
1791 glhanoi->trailQFront = normalizeQ(i + 1);
1793 if (tqi->startTime > t) break;
1794 /* Found trails that haven't timed out. */
1795 if (!fresh) fresh = True;
1797 /* Fade to invisible with age */
1798 trailColor[3] = alpha * (tqi->endTime - t) * trailDurInv;
1799 /* Can't use setMaterial(trailColor, cBlack, 0) because our color needs an alpha value. */
1800 glColor4fv(trailColor);
1801 glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, trailColor);
1802 /* FUTURE: to really do this right, trails should be drawn in back-to-front
1803 order, so that blending is done correctly.
1804 Currently it looks poor when a faded trail is in front of, or coincident with,
1805 a bright trail but is drawn first.
1806 I think for now it's good enough to recommend shorter trails so they
1807 never/rarely overlap.
1808 A jitter per trail arc would also mitigate this problem, to a lesser degree. */
1809 glVertex3fv(glhanoi->trailQ[prev].position);
1810 glVertex3fv(glhanoi->trailQ[i].position);
1813 if (glhanoi->trailQ[i].isEnd)
1825 static int drawTrails(glhcfg *glhanoi) {
1827 double t = getTime();
1829 glEnable (GL_BLEND);
1830 glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1831 glMaterialfv(GL_FRONT, GL_SPECULAR, cBlack);
1832 glMateriali(GL_FRONT, GL_SHININESS, 0);
1834 /* Draw them twice, with different widths and opacities, to make them smoother. */
1835 lines = drawTrails1(glhanoi, t, 1.0, 0.75);
1836 lines += drawTrails1(glhanoi, t, 2.5, 0.5);
1838 glDisable (GL_BLEND);
1840 /* fprintf(stderr, "Drew trails: %d lines\n", lines); */
1844 /* Window management, etc
1846 ENTRYPOINT void reshape_glhanoi(ModeInfo * mi, int width, int height)
1848 glViewport(0, 0, (GLint) width, (GLint) height);
1850 glMatrixMode(GL_PROJECTION);
1852 gluPerspective(30.0, (GLdouble) width / (GLdouble) height, 1.0,
1853 2 * MAX_CAMERA_RADIUS);
1855 glMatrixMode(GL_MODELVIEW);
1858 glClear(GL_COLOR_BUFFER_BIT);
1861 ENTRYPOINT void init_glhanoi(ModeInfo * mi)
1866 (glhcfg *) calloc(MI_NUM_SCREENS(mi), sizeof(glhcfg));
1867 checkAllocAndExit(!!glhanoi_cfg, "configuration");
1870 glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1871 glhanoi->glx_context = init_GL(mi);
1872 glhanoi->numberOfDisks = MI_BATCHCOUNT(mi);
1874 if (glhanoi->numberOfDisks <= 1)
1875 glhanoi->numberOfDisks = 3 + (int) BELLRAND(9);
1877 /* magicnumber is a bitfield, so we can't have more than 31 discs
1878 on a system with 4-byte ints. */
1879 if (glhanoi->numberOfDisks >= 8 * sizeof(int))
1880 glhanoi->numberOfDisks = (8 * sizeof(int)) - 1;
1882 glhanoi->maxDiskIdx = glhanoi->numberOfDisks - 1;
1884 glhanoi->numberOfPoles = get_integer_resource(MI_DISPLAY(mi), "poles", "Integer");
1885 /* Set a number of poles from 3 to numberOfDisks + 1, biased toward lower values,
1886 with probability decreasing linearly. */
1887 if (glhanoi->numberOfPoles <= 2)
1888 glhanoi->numberOfPoles = 3 +
1889 (int)((1 - sqrt(frand(1.0))) * (glhanoi->numberOfDisks - 1));
1891 glhanoi->wire = MI_IS_WIREFRAME(mi);
1893 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
1897 glhanoi->light = light;
1899 glhanoi->texture = texture;
1900 glhanoi->speed = speed;
1901 glhanoi->trailDuration = trails;
1902 /* set trailQSize based on 60 fps (a maximum, more or less) */
1903 /* FUTURE: Should clamp framerate to 60 fps? See flurry.c's draw_flurry().
1904 The only bad effect if we don't is that trail-ends could
1905 show "unnatural" pauses at high fps. */
1906 glhanoi->trailQSize = (int)(trails * 60.0);
1908 reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
1911 glhanoi->light = False;
1912 glhanoi->fog = False;
1913 glhanoi->texture = False;
1916 initLights(!glhanoi->wire && glhanoi->light);
1917 checkAllocAndExit(!makeTextures(glhanoi), "textures\n");
1919 /* Choose linear or circular layout. Could make this a user option. */
1920 glhanoi->layoutLinear = (glhanoi->numberOfPoles == 3);
1926 initTowers(glhanoi);
1929 glEnable(GL_DEPTH_TEST);
1930 glEnable(GL_NORMALIZE);
1931 glEnable(GL_CULL_FACE);
1932 glShadeModel(GL_SMOOTH);
1934 glClearColor(fogcolor[0], fogcolor[1], fogcolor[2], 1.0);
1935 glFogi(GL_FOG_MODE, GL_LINEAR);
1936 glFogfv(GL_FOG_COLOR, fogcolor);
1937 glFogf(GL_FOG_DENSITY, 0.35f);
1938 glHint(GL_FOG_HINT, GL_NICEST);
1939 glFogf(GL_FOG_START, MIN_CAMERA_RADIUS);
1940 glFogf(GL_FOG_END, MAX_CAMERA_RADIUS / 1.9);
1944 glhanoi->duration = START_DURATION;
1945 changeState(glhanoi, START);
1948 ENTRYPOINT void draw_glhanoi(ModeInfo * mi)
1950 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1951 Display *dpy = MI_DISPLAY(mi);
1952 Window window = MI_WINDOW(mi);
1954 if(!glhanoi->glx_context)
1957 glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context));
1959 glPolygonMode(GL_FRONT, glhanoi->wire ? GL_LINE : GL_FILL);
1961 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1962 mi->polygon_count = 0;
1965 glRotatef(current_device_rotation(), 0, 0, 1);
1967 update_glhanoi(glhanoi);
1968 updateView(glhanoi);
1970 # ifdef HAVE_MOBILE /* Keep it the same relative size when rotated. */
1972 GLfloat h = MI_HEIGHT(mi) / (GLfloat) MI_WIDTH(mi);
1973 int o = (int) current_device_rotation();
1974 if (o != 0 && o != 180 && o != -180)
1975 glScalef (1/h, 1/h, 1/h);
1979 if(!glhanoi->wire && glhanoi->texture) {
1980 glEnable(GL_TEXTURE_2D);
1982 mi->polygon_count += drawFloor(glhanoi);
1983 glDisable(GL_TEXTURE_2D);
1985 mi->polygon_count += drawTowers(glhanoi);
1986 mi->polygon_count += drawDisks(glhanoi);
1988 if (glhanoi->trailQSize) {
1989 /* No polygons, just lines. So ignore the return count. */
1990 (void)drawTrails(glhanoi);
1998 glXSwapBuffers(dpy, window);
2001 ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event)
2003 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
2005 /* #### this is all wrong on iOS -- should be using gltrackball. */
2007 if(event->xany.type == ButtonPress && event->xbutton.button == Button1) {
2008 glhanoi->button_down_p = True;
2009 glhanoi->drag_x = event->xbutton.x;
2010 glhanoi->drag_y = event->xbutton.y;
2012 } else if(event->xany.type == ButtonRelease
2013 && event->xbutton.button == Button1) {
2014 glhanoi->button_down_p = False;
2016 } else if(event->xany.type == ButtonPress &&
2017 (event->xbutton.button == Button4
2018 || event->xbutton.button == Button5)) {
2019 switch (event->xbutton.button) {
2021 glhanoi->camera[2] += 0.01;
2024 glhanoi->camera[2] -= 0.01;
2028 "glhanoi: unknown button in mousewheel handler\n");
2031 } else if(event->xany.type == MotionNotify
2032 && glhanoi_cfg->button_down_p) {
2035 x_diff = event->xbutton.x - glhanoi->drag_x;
2036 y_diff = event->xbutton.y - glhanoi->drag_y;
2038 glhanoi->camera[0] = (float)x_diff / (float)MI_WIDTH(mi);
2039 glhanoi->camera[1] = (float)y_diff / (float)MI_HEIGHT(mi);
2043 #if 0 /* #### doesn't work */
2044 else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
2046 changeState(glhanoi, START);
2053 ENTRYPOINT void release_glhanoi(ModeInfo * mi)
2055 if(glhanoi_cfg != NULL) {
2057 for(screen = 0; screen < MI_NUM_SCREENS(mi); screen++) {
2060 glhcfg *glh = &glhanoi_cfg[screen];
2061 glDeleteLists(glh->floorList, 1);
2062 glDeleteLists(glh->baseList, 1);
2063 glDeleteLists(glh->poleList, 1);
2064 glDeleteLists(glh->textureNames[0], 2);
2065 for(j = 0; j < glh->numberOfDisks; ++j) {
2066 glDeleteLists(glh->disk[j].displayList, 1);
2069 for(i = 0; i < glh->numberOfPoles; i++) {
2070 if(glh->pole[i].data != NULL) {
2071 free(glh->pole[i].data);
2080 XSCREENSAVER_MODULE ("GLHanoi", glhanoi)