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);
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;
893 if(bottomThickness > bottomRadius) {
894 bottomThickness = bottomRadius;
896 if(topThickness > topRadius) {
897 topThickness = topRadius;
899 if(bottomThickness < 0.0) {
900 bottomThickness = 0.0;
902 if(topThickness < 0.0) {
905 if(topRadius >= bottomRadius) {
906 maxRadius = topRadius;
908 maxRadius = bottomRadius;
913 radius = bottomRadius;
914 innerRadius = bottomRadius - bottomThickness;
915 /* innerTexCoordSize = texCoordSize * innerRadius / maxRadius; */
916 /* outerTexCoordSize = texCoordSize * radius / maxRadius; */
917 /* yTexCoord = minTexCoord; */
919 glBegin(GL_QUAD_STRIP);
921 glNormal3f(0.0, -1.0, 0.0);
923 /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + innerTexCoordSize); */
924 glVertex3f(0.0, y, innerRadius);
926 /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + outerTexCoordSize); */
927 glVertex3f(0.0, y, radius);
929 for(slice = lastSlice; slice >= 0; --slice) {
930 GLfloat theta = 2.0 * M_PI * (double)slice / nSlice;
932 cosCache[slice] = cos(theta);
933 sinCache[slice] = sin(theta);
935 /* glTexCoord3f(midTexCoord + sinCache[slice] * innerTexCoordSize, */
937 /* midTexCoord + cosCache[slice] * innerTexCoordSize); */
938 glVertex3f(innerRadius * sinCache[slice], y,
939 innerRadius * cosCache[slice]);
940 /* glTexCoord3f(midTexCoord + sinCache[slice] * outerTexCoordSize, */
942 /* midTexCoord + cosCache[slice] * outerTexCoordSize); */
943 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
949 for(loop = 0; loop < nLoop; ++loop) {
950 GLfloat lowerRadius =
951 bottomRadius + (topRadius -
952 bottomRadius) * (float)loop / (nLoop);
953 GLfloat upperRadius =
954 bottomRadius + (topRadius - bottomRadius) * (float)(loop +
957 GLfloat lowerY = height * (float)loop / (nLoop);
958 GLfloat upperY = height * (float)(loop + 1) / (nLoop);
959 GLfloat factor = (topRadius - topThickness) -
960 (bottomRadius - bottomThickness);
963 glBegin(GL_QUAD_STRIP);
964 for(slice = 0; slice < nSlice; ++slice) {
965 glNormal3f(sinCache[slice], 0.0, cosCache[slice]);
966 glVertex3f(upperRadius * sinCache[slice], upperY,
967 upperRadius * cosCache[slice]);
968 glVertex3f(lowerRadius * sinCache[slice], lowerY,
969 lowerRadius * cosCache[slice]);
972 glNormal3f(0.0, 0.0, 1.0);
973 glVertex3f(0.0, upperY, upperRadius);
974 glVertex3f(0.0, lowerY, lowerRadius);
979 lowerRadius = bottomRadius - bottomThickness +
980 factor * (float)loop / (nLoop);
981 upperRadius = bottomRadius - bottomThickness +
982 factor * (float)(loop + 1) / (nLoop);
984 glBegin(GL_QUAD_STRIP);
985 glNormal3f(0.0, 0.0, -1.0);
986 glVertex3f(0.0, upperY, upperRadius);
987 glVertex3f(0.0, lowerY, lowerRadius);
988 for(slice = lastSlice; slice >= 0; --slice) {
989 glNormal3f(-sinCache[slice], 0.0, -cosCache[slice]);
990 glVertex3f(upperRadius * sinCache[slice], upperY,
991 upperRadius * cosCache[slice]);
992 glVertex3f(lowerRadius * sinCache[slice], lowerY,
993 lowerRadius * cosCache[slice]);
1002 innerRadius = topRadius - topThickness;
1004 glBegin(GL_QUAD_STRIP);
1005 glNormal3f(0.0, 1.0, 0.0);
1006 for(slice = 0; slice < nSlice; ++slice) {
1007 glVertex3f(innerRadius * sinCache[slice], y,
1008 innerRadius * cosCache[slice]);
1010 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
1013 glVertex3f(0.0, y, innerRadius);
1014 glVertex3f(0.0, y, radius);
1019 static int drawPole(GLfloat radius, GLfloat length)
1021 return drawTube(radius, radius, radius, radius, length, NSLICE, NLOOPS);
1024 static int drawDisk3D(GLdouble inner_radius, GLdouble outer_radius,
1027 return drawTube(outer_radius, outer_radius, outer_radius - inner_radius,
1028 outer_radius - inner_radius, height, NSLICE, NLOOPS);
1031 /* used for drawing base */
1032 static int drawCuboid(GLfloat length, GLfloat width, GLfloat height)
1034 GLfloat xmin = -length / 2.0f;
1035 GLfloat xmax = length / 2.0f;
1036 GLfloat zmin = -width / 2.0f;
1037 GLfloat zmax = width / 2.0f;
1038 GLfloat ymin = 0.0f;
1039 GLfloat ymax = height;
1045 glVertex3f(xmin, ymin, zmax); /* 0 */
1046 glVertex3f(xmax, ymin, zmax); /* 1 */
1047 glVertex3f(xmax, ymax, zmax); /* 2 */
1048 glVertex3f(xmin, ymax, zmax); /* 3 */
1052 glVertex3f(xmax, ymin, zmax); /* 1 */
1053 glVertex3f(xmax, ymin, zmin); /* 5 */
1054 glVertex3f(xmax, ymax, zmin); /* 6 */
1055 glVertex3f(xmax, ymax, zmax); /* 2 */
1059 glVertex3f(xmax, ymin, zmin); /* 5 */
1060 glVertex3f(xmin, ymin, zmin); /* 4 */
1061 glVertex3f(xmin, ymax, zmin); /* 7 */
1062 glVertex3f(xmax, ymax, zmin); /* 6 */
1066 glVertex3f(xmin, ymin, zmin); /* 4 */
1067 glVertex3f(xmin, ymin, zmax); /* 0 */
1068 glVertex3f(xmin, ymax, zmax); /* 3 */
1069 glVertex3f(xmin, ymax, zmin); /* 7 */
1073 glVertex3f(xmin, ymax, zmax); /* 3 */
1074 glVertex3f(xmax, ymax, zmax); /* 2 */
1075 glVertex3f(xmax, ymax, zmin); /* 6 */
1076 glVertex3f(xmin, ymax, zmin); /* 7 */
1080 glVertex3f(xmin, ymin, zmin); /* 4 */
1081 glVertex3f(xmax, ymin, zmin); /* 5 */
1082 glVertex3f(xmax, ymin, zmax); /* 1 */
1083 glVertex3f(xmin, ymin, zmax); /* 0 */
1089 /* Set normal vector in xz plane, based on rotation around center. */
1090 static void setNormalV(glhcfg *glhanoi, GLfloat theta, int y1, int y2, int r1) {
1091 if (y1 == y2) /* up/down */
1092 glNormal3f(0.0, y1 ? 1.0 : -1.0, 0.0);
1093 else if (!r1) /* inward */
1094 glNormal3f(-cos(theta), 0.0, -sin(theta));
1096 glNormal3f(cos(theta), 0.0, sin(theta));
1099 /* y1, r1, y2, r2 are indices into y, r, beg, end */
1100 static int drawBaseStrip(glhcfg *glhanoi, int y1, int r1, int y2, int r2,
1101 GLfloat y[2], GLfloat r[2], GLfloat beg[2][2], GLfloat end[2][2]) {
1103 GLfloat theta, costh, sinth, x[2], z[2];
1104 GLfloat theta1 = (M_PI * 2) / (glhanoi->numberOfPoles + 1);
1106 glBegin(GL_QUAD_STRIP);
1108 /* beginning edge */
1109 glVertex3f(beg[r1][0], y[y1], beg[r1][1]);
1110 glVertex3f(beg[r2][0], y[y2], beg[r2][1]);
1111 setNormalV(glhanoi, theta1, y1, y2, r1);
1113 for (i = 1; i < glhanoi->numberOfPoles; i++) {
1114 theta = theta1 * (i + 0.5);
1117 x[0] = costh * r[0];
1118 x[1] = costh * r[1];
1119 z[0] = sinth * r[0];
1120 z[1] = sinth * r[1];
1122 glVertex3f(x[r1], y[y1], z[r1]);
1123 glVertex3f(x[r2], y[y2], z[r2]);
1125 setNormalV(glhanoi, theta1 * (i + 1), y1, y2, r1);
1129 glVertex3f(end[r1][0], y[y1], end[r1][1]);
1130 glVertex3f(end[r2][0], y[y2], end[r2][1]);
1131 setNormalV(glhanoi, glhanoi->numberOfPoles, y1, y2, r1);
1134 return glhanoi->numberOfPoles;
1137 /* Draw base such that poles are distributed around a regular polygon. */
1138 static int drawRoundBase(glhcfg *glhanoi) {
1140 GLfloat theta, sinth, costh;
1143 r[0] = (minimum) inner radius of base at vertices
1144 r[1] = (minimum) outer radius of base at vertices
1145 y[0] = bottom of base
1146 y[1] = top of base */
1148 /* positions of end points: beginning, end.
1149 beg[0] is inner corner of beginning of base, beg[1] is outer corner.
1150 beg[i][0] is x, [i][1] is z. */
1151 GLfloat beg[2][2], end[2][2], begNorm, endNorm;
1152 /* ratio of radius at base vertices to ratio at poles */
1153 GLfloat longer = 1.0 / cos(M_PI / (glhanoi->numberOfPoles + 1));
1155 r[0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * longer;
1156 r[1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * longer;
1158 y[1] = glhanoi->baseHeight;
1160 /* compute beg, end. Make the ends square. */
1161 theta = M_PI * 2 / (glhanoi->numberOfPoles + 1);
1165 beg[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh +
1166 glhanoi->maxDiskRadius * sinth;
1167 beg[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh +
1168 glhanoi->maxDiskRadius * sinth;
1169 beg[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth -
1170 glhanoi->maxDiskRadius * costh;
1171 beg[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth -
1172 glhanoi->maxDiskRadius * costh;
1173 begNorm = theta - M_PI * 0.5;
1175 theta = M_PI * 2 * glhanoi->numberOfPoles / (glhanoi->numberOfPoles + 1);
1179 end[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh -
1180 glhanoi->maxDiskRadius * sinth;
1181 end[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh -
1182 glhanoi->maxDiskRadius * sinth;
1183 end[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth +
1184 glhanoi->maxDiskRadius * costh;
1185 end[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth +
1186 glhanoi->maxDiskRadius * costh;
1187 endNorm = theta + M_PI * 0.5;
1189 /* bottom: never seen
1190 polys = drawBaseStrip(glhanoi, 0, 0, 0, 1, y, r, beg, end); */
1192 polys += drawBaseStrip(glhanoi, 0, 1, 1, 1, y, r, beg, end);
1194 polys += drawBaseStrip(glhanoi, 1, 1, 1, 0, y, r, beg, end);
1196 polys += drawBaseStrip(glhanoi, 1, 0, 0, 0, y, r, beg, end);
1201 glVertex3f(beg[0][0], y[1], beg[0][1]);
1202 glVertex3f(beg[1][0], y[1], beg[1][1]);
1203 glVertex3f(beg[1][0], y[0], beg[1][1]);
1204 glVertex3f(beg[0][0], y[0], beg[0][1]);
1205 glNormal3f(cos(begNorm), 0, sin(begNorm));
1207 glVertex3f(end[0][0], y[0], end[0][1]);
1208 glVertex3f(end[1][0], y[0], end[1][1]);
1209 glVertex3f(end[1][0], y[1], end[1][1]);
1210 glVertex3f(end[0][0], y[1], end[0][1]);
1211 glNormal3f(cos(endNorm), 0, sin(endNorm));
1220 static int drawDisks(glhcfg *glhanoi)
1226 glTranslatef(0.0f, glhanoi->baseHeight, 0.0f);
1227 for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1228 Disk *disk = &glhanoi->disk[i];
1229 GLfloat *pos = disk->position;
1230 GLfloat *rot = disk->rotation;
1233 glTranslatef(pos[0], pos[1], pos[2]);
1235 glTranslatef(0.0, glhanoi->diskHeight / 2.0, 0.0);
1236 /* rotate around different axis depending on phi */
1237 if (disk->phi != 0.0)
1238 glRotatef(-disk->phi, 0.0, 1.0, 0.0);
1239 glRotatef(rot[1], 0.0, 0.0, 1.0);
1240 if (disk->phi != 0.0)
1241 glRotatef(disk->phi, 0.0, 1.0, 0.0);
1242 glTranslatef(0.0, -glhanoi->diskHeight / 2.0, 0.0);
1244 glCallList(disk->displayList);
1245 polys += disk->polys;
1252 static GLfloat getDiskRadius(glhcfg *glhanoi, int i)
1254 GLfloat retVal = glhanoi->maxDiskRadius *
1255 ((GLfloat) i + 3.0) / (glhanoi->numberOfDisks + 3.0);
1259 static void initData(glhcfg *glhanoi)
1262 GLfloat sinPiOverNP;
1264 glhanoi->baseLength = BASE_LENGTH;
1265 if (glhanoi->layoutLinear) {
1266 glhanoi->maxDiskRadius = glhanoi->baseLength /
1267 (2 * 0.95 * glhanoi->numberOfPoles);
1269 sinPiOverNP = sin(M_PI / (glhanoi->numberOfPoles + 1));
1270 glhanoi->maxDiskRadius = (sinPiOverNP * glhanoi->baseLength * 0.5 * 0.95) / (1 + sinPiOverNP);
1273 glhanoi->poleDist = glhanoi->baseLength * 0.5 - glhanoi->maxDiskRadius;
1274 glhanoi->poleRadius = glhanoi->maxDiskRadius / (glhanoi->numberOfDisks + 3.0);
1275 /* fprintf(stderr, "Debug: baseL = %f, maxDiskR = %f, poleR = %f\n",
1276 glhanoi->baseLength, glhanoi->maxDiskRadius, glhanoi->poleRadius); */
1277 glhanoi->baseWidth = 2.0 * glhanoi->maxDiskRadius;
1278 glhanoi->poleOffset = 2.0 * getDiskRadius(glhanoi, glhanoi->maxDiskIdx);
1279 glhanoi->diskHeight = 2.0 * glhanoi->poleRadius;
1280 glhanoi->baseHeight = 2.0 * glhanoi->poleRadius;
1281 glhanoi->poleHeight = glhanoi->numberOfDisks *
1282 glhanoi->diskHeight + glhanoi->poleRadius;
1283 /* numberOfMoves only applies if numberOfPoles = 3 */
1284 glhanoi->numberOfMoves = (1 << glhanoi->numberOfDisks) - 1;
1285 /* use golden ratio */
1286 glhanoi->boardSize = glhanoi->baseLength * 0.5 * (1.0 + sqrt(5.0));
1288 glhanoi->pole = (Pole *)calloc(glhanoi->numberOfPoles, sizeof(Pole));
1289 checkAllocAndExit(!!glhanoi->pole, "poles");
1291 for(i = 0; i < glhanoi->numberOfPoles; i++) {
1293 !!(glhanoi->pole[i].data = calloc(glhanoi->numberOfDisks, sizeof(Disk *))),
1295 glhanoi->pole[i].size = glhanoi->numberOfDisks;
1298 !!(glhanoi->diskPos = calloc(glhanoi->numberOfDisks, sizeof(double))),
1301 if (glhanoi->trailQSize) {
1302 glhanoi->trailQ = (TrailPoint *)calloc(glhanoi->trailQSize, sizeof(TrailPoint));
1303 checkAllocAndExit(!!glhanoi->trailQ, "trail queue");
1304 } else glhanoi->trailQ = (TrailPoint *)NULL;
1305 glhanoi->trailQFront = glhanoi->trailQBack = 0;
1307 glhanoi->the_rotator = make_rotator(0.1, 0.025, 0, 1, 0.005, False);
1308 /* or glhanoi->the_rotator = make_rotator(0.025, 0.025, 0.025, 0.5, 0.005, False); */
1309 glhanoi->button_down_p = False;
1311 glhanoi->src = glhanoi->oldsrc = 0;
1312 glhanoi->tmp = glhanoi->oldtmp = 1;
1313 glhanoi->dst = glhanoi->olddst = glhanoi->numberOfPoles - 1;
1315 if (glhanoi->numberOfPoles > 3) {
1316 glhanoi->solveStackSize = glhanoi->numberOfDisks + 2;
1317 glhanoi->solveStack = (SubProblem *)calloc(glhanoi->solveStackSize, sizeof(SubProblem));
1318 checkAllocAndExit(!!glhanoi->solveStack, "solving stack");
1319 glhanoi->solveStackIdx = 0;
1323 static void initView(glhcfg *glhanoi)
1325 glhanoi->camera[0] = 0.0;
1326 glhanoi->camera[1] = 0.0;
1327 glhanoi->camera[2] = 0.0;
1328 glhanoi->centre[0] = 0.0;
1329 glhanoi->centre[1] = glhanoi->poleHeight * 3.0;
1330 glhanoi->centre[2] = 0.0;
1334 * noise_improved.c - based on ImprovedNoise.java
1335 * JAVA REFERENCE IMPLEMENTATION OF IMPROVED NOISE - COPYRIGHT 2002 KEN PERLIN.
1337 static double fade(double t)
1339 return t * t * t * (t * (t * 6 - 15) + 10);
1342 static double grad(int hash, double x, double y, double z)
1344 int h = hash & 15; /* CONVERT LO 4 BITS OF HASH CODE */
1345 double u = h < 8 ? x : y, /* INTO 12 GRADIENT DIRECTIONS. */
1346 v = h < 4 ? y : h == 12 || h == 14 ? x : z;
1347 return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
1350 static const int permutation[] = { 151, 160, 137, 91, 90, 15,
1351 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142,
1352 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 26,
1353 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237,
1354 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71,
1355 134, 139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60,
1356 211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 102, 143,
1357 54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89,
1358 18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 198,
1359 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118,
1360 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189,
1361 28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70,
1362 221, 153, 101, 155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108,
1363 110, 79, 113, 224, 232, 178, 185, 112, 104, 218, 246, 97, 228, 251,
1364 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241, 81, 51, 145,
1365 235, 249, 14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 157, 184,
1366 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205,
1367 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61,
1371 static void initNoise(glhcfg *glhanoi)
1374 for(i = 0; i < 256; i++)
1375 glhanoi->p[256 + i] = glhanoi->p[i] = permutation[i];
1378 static double improved_noise(glhcfg *glhanoi, double x, double y, double z)
1381 int A, AA, AB, B, BA, BB;
1382 int X = (int)floor(x) & 255, /* FIND UNIT CUBE THAT */
1383 Y = (int)floor(y) & 255, /* CONTAINS POINT. */
1384 Z = (int)floor(z) & 255;
1385 if(!glhanoi->noise_initted) {
1387 glhanoi->noise_initted = 1;
1389 x -= floor(x); /* FIND RELATIVE X,Y,Z */
1390 y -= floor(y); /* OF POINT IN CUBE. */
1392 u = fade(x), /* COMPUTE FADE CURVES */
1393 v = fade(y), /* FOR EACH OF X,Y,Z. */
1395 A = glhanoi->p[X] + Y;
1396 AA = glhanoi->p[A] + Z;
1397 AB = glhanoi->p[A + 1] + Z, /* HASH COORDINATES OF */
1398 B = glhanoi->p[X + 1] + Y;
1399 BA = glhanoi->p[B] + Z;
1400 BB = glhanoi->p[B + 1] + Z; /* THE 8 CUBE CORNERS, */
1401 return lerp(w, lerp(v, lerp(u, grad(glhanoi->p[AA], x, y, z),/* AND ADD */
1402 grad(glhanoi->p[BA], x - 1, y, z)),/* BLENDED */
1403 lerp(u, grad(glhanoi->p[AB], x, y - 1, z),/* RESULTS */
1404 grad(glhanoi->p[BB], x - 1, y - 1, z))),/* FROM 8 CORNERS */
1405 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 */
1406 lerp(u, grad(glhanoi->p[AB + 1], x, y - 1, z - 1),
1407 grad(glhanoi->p[BB + 1], x - 1, y - 1, z - 1))));
1411 * end noise_improved.c - based on ImprovedNoise.java
1416 /* GLfloat *points; */
1419 typedef struct tex_col_t tex_col_t;
1421 static GLubyte *makeTexture(glhcfg *glhanoi, int x_size, int y_size, int z_size,
1422 GLuint(*texFunc) (glhcfg *, double, double, double,
1423 tex_col_t *), tex_col_t * colours)
1426 GLubyte *textureData;
1432 calloc(x_size * y_size * z_size, sizeof(GLuint))) == NULL) {
1441 texturePtr = (void *)textureData;
1442 for(k = 0; k < z_size; k++, z += zi) {
1444 for(j = 0; j < y_size; j++, y += yi) {
1446 for(i = 0; i < x_size; i++, x += xi) {
1447 *texturePtr = texFunc(glhanoi, x, y, z, colours);
1455 static void freeTexCols(tex_col_t*p)
1461 static tex_col_t *makeMarbleColours(void)
1463 tex_col_t *marbleColours;
1466 marbleColours = malloc(sizeof(tex_col_t));
1467 if(marbleColours == NULL) return NULL;
1468 marbleColours->colours = calloc(sizeof(GLuint), ncols);
1469 if(marbleColours->colours == NULL) return NULL;
1470 marbleColours->ncols = ncols;
1472 marbleColours->colours[0] = 0x3f3f3f3f;
1473 marbleColours->colours[1] = 0xffffffff;
1475 return marbleColours;
1478 static double turb(glhcfg *glhanoi, double x, double y, double z, int octaves)
1483 for(oct = 0; oct < octaves; ++oct) {
1484 r += fabs(improved_noise(glhanoi, freq * x, freq * y, freq * z)) / freq;
1490 static void perturb(glhcfg *glhanoi, double *x, double *y, double *z, double scale)
1492 double t = scale * turb(glhanoi, *x, *y, *z, 4);
1498 static double f_m(double x, double y, double z)
1500 return sin(3.0 * M_PI * x);
1503 static GLuint C_m(double x, const tex_col_t * tex_cols)
1505 int r = tex_cols->colours[0] & 0xff;
1506 int g = tex_cols->colours[0] >> 8 & 0xff;
1507 int b = tex_cols->colours[0] >> 16 & 0xff;
1512 factor = (1.0 + sin(2.0 * M_PI * x)) / 2.0;
1514 r1 = (tex_cols->colours[1] & 0xff);
1515 g1 = (tex_cols->colours[1] >> 8 & 0xff);
1516 b1 = (tex_cols->colours[1] >> 16 & 0xff);
1518 r += (int)(factor * (r1 - r));
1519 g += (int)(factor * (g1 - g));
1520 b += (int)(factor * (b1 - b));
1522 return 0xff000000 | (b << 16) | (g << 8) | r;
1526 static GLuint makeMarbleTexture(glhcfg *glhanoi, double x, double y, double z, tex_col_t * colours)
1528 perturb(glhanoi, &x, &y, &z, MARBLE_SCALE);
1529 return C_m(f_m(x, y, z), colours);
1532 static void setTexture(glhcfg *glhanoi, int n)
1534 glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[n]);
1537 /* returns 1 on failure, 0 on success */
1538 static int makeTextures(glhcfg *glhanoi)
1540 GLubyte *marbleTexture;
1541 tex_col_t *marbleColours;
1543 glGenTextures(N_TEXTURES, glhanoi->textureNames);
1545 if((marbleColours = makeMarbleColours()) == NULL) {
1549 makeTexture(glhanoi, MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 1,
1550 makeMarbleTexture, marbleColours)) == NULL) {
1554 glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[0]);
1555 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
1556 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
1557 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
1558 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
1559 glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA,
1560 MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 0,
1561 GL_RGBA, GL_UNSIGNED_BYTE, marbleTexture);
1562 free(marbleTexture);
1563 freeTexCols(marbleColours);
1568 static void initFloor(glhcfg *glhanoi)
1571 float tileSize = glhanoi->boardSize / BOARD_SQUARES;
1572 float x0, x1, z0, z1;
1573 float tx0, tx1, tz0, tz1;
1574 const float *col = cWhite;
1575 float texIncr = 1.0 / BOARD_SQUARES;
1577 glhanoi->floorpolys = 0;
1578 checkAllocAndExit(!!(glhanoi->floorList = glGenLists(1)), "floor display list");
1579 glNewList(glhanoi->floorList, GL_COMPILE);
1580 x0 = -glhanoi->boardSize / 2.0;
1582 setMaterial(col, cWhite, 128);
1583 setTexture(glhanoi, 0);
1585 for(i = 0; i < BOARD_SQUARES; i++, x0 += tileSize, tx0 += texIncr) {
1587 tx1 = tx0 + texIncr;
1588 z0 = -glhanoi->boardSize / 2.0;
1590 for(j = 0; j < BOARD_SQUARES; j++, z0 += tileSize, tz0 += texIncr) {
1591 int colIndex = (i + j) & 0x1;
1594 tz1 = tz0 + texIncr;
1601 setMaterial(col, cWhite, 100);
1605 glTexCoord2d(tx0, tz0);
1606 glVertex3f(x0, 0.0, z0);
1608 glTexCoord2d(tx0, tz1);
1609 glVertex3f(x0, 0.0, z1);
1611 glTexCoord2d(tx1, tz1);
1612 glVertex3f(x1, 0.0, z1);
1614 glTexCoord2d(tx1, tz0);
1615 glVertex3f(x1, 0.0, z0);
1616 glhanoi->floorpolys++;
1623 static void initBase(glhcfg *glhanoi)
1625 checkAllocAndExit(!!(glhanoi->baseList = glGenLists(1)), "tower bases display list");
1627 glNewList(glhanoi->baseList, GL_COMPILE);
1628 setMaterial(baseColor, cWhite, 50);
1629 if (glhanoi->layoutLinear) {
1630 glhanoi->basepolys = drawCuboid(glhanoi->baseLength, glhanoi->baseWidth,
1631 glhanoi->baseHeight);
1633 glhanoi->basepolys = drawRoundBase(glhanoi);
1638 static void initTowers(glhcfg *glhanoi)
1642 checkAllocAndExit(!!(glhanoi->poleList = glGenLists(1)), "poles display list\n");
1644 glNewList(glhanoi->poleList, GL_COMPILE);
1645 /* glTranslatef(-glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5f, glhanoi->baseHeight, 0.0f); */
1646 setMaterial(poleColor, cWhite, 50);
1647 for (i = 0; i < glhanoi->numberOfPoles; i++) {
1648 GLfloat *p = glhanoi->pole[i].position;
1649 GLfloat rad = (M_PI * 2.0 * (i + 1)) / (glhanoi->numberOfPoles + 1);
1651 p[1] = glhanoi->baseHeight;
1653 if (glhanoi->layoutLinear) {
1655 p[0] = -glhanoi->poleOffset * ((glhanoi->numberOfPoles - 1) * 0.5f - i);
1658 /* Circular layout: */
1659 p[0] = cos(rad) * glhanoi->poleDist;
1660 p[2] = sin(rad) * glhanoi->poleDist;
1664 glTranslatef(p[0], p[1], p[2]);
1665 glhanoi->polepolys = drawPole(glhanoi->poleRadius, glhanoi->poleHeight);
1672 /* Parameterized hue based on input 0.0 - 1.0. */
1673 static double cfunc(double x)
1677 return (1.0 / 12.0) / (1.0 / 7.0) * x;
1681 return (1.0 + 1.0 / 6.0) * x - 1.0 / 6.0;
1684 return (2.0 + 1.0 / 3.0) * x - 2.0 / 3.0;
1687 return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1689 return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1692 static void initDisks(glhcfg *glhanoi)
1695 glhanoi->disk = (Disk *) calloc(glhanoi->numberOfDisks, sizeof(Disk));
1696 checkAllocAndExit(!!glhanoi->disk, "disks");
1698 for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1699 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1700 double f = cfunc((GLfloat) i / (GLfloat) glhanoi->numberOfDisks);
1701 GLfloat diskColor = f * 360.0;
1703 Disk *disk = &glhanoi->disk[i];
1706 disk->position[0] = glhanoi->pole[0].position[0]; /* -glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5; */
1707 disk->position[1] = glhanoi->diskHeight * height;
1708 disk->position[2] = glhanoi->pole[0].position[2];
1709 disk->rotation[0] = 0.0;
1710 disk->rotation[1] = 0.0;
1711 disk->rotation[2] = 0.0;
1714 /* make smaller disks move faster */
1715 disk->speed = lerp(((double)glhanoi->numberOfDisks - i) / glhanoi->numberOfDisks,
1716 1.0, glhanoi->speed);
1717 /* fprintf(stderr, "disk id: %d, alpha: %0.2f, speed: %0.2f\n", disk->id,
1718 ((double)(glhanoi->maxDiskIdx - i)) / glhanoi->numberOfDisks, disk->speed); */
1720 color[0] = diskColor;
1723 HSVtoRGBv(color, color);
1725 checkAllocAndExit(!!(disk->displayList = glGenLists(1)), "disk display list");
1726 glNewList(disk->displayList, GL_COMPILE);
1727 setMaterial(color, cWhite, 100.0);
1728 disk->polys += drawDisk3D(glhanoi->poleRadius,
1729 getDiskRadius(glhanoi, i),
1730 glhanoi->diskHeight);
1731 /*fprintf(stderr, "Debug: disk %d has radius %f\n", i,
1732 getDiskRadius(glhanoi, i)); */
1735 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
1736 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1737 int h = glhanoi->maxDiskIdx - i;
1738 glhanoi->diskPos[h] = glhanoi->diskHeight * height;
1739 push(glhanoi, glhanoi->src, &glhanoi->disk[i]);
1743 static void initLights(Bool state)
1746 glLightfv(GL_LIGHT0, GL_POSITION, pos0);
1747 glLightfv(GL_LIGHT0, GL_AMBIENT, amb0);
1748 glLightfv(GL_LIGHT0, GL_DIFFUSE, dif0);
1749 glLightfv(GL_LIGHT0, GL_SPECULAR, spc0);
1751 glLightfv(GL_LIGHT1, GL_POSITION, pos1);
1752 glLightfv(GL_LIGHT1, GL_AMBIENT, amb1);
1753 glLightfv(GL_LIGHT1, GL_DIFFUSE, dif1);
1754 glLightfv(GL_LIGHT1, GL_SPECULAR, spc1);
1756 glEnable(GL_LIGHTING);
1757 glEnable(GL_LIGHT0);
1758 glEnable(GL_LIGHT1);
1760 glDisable(GL_LIGHTING);
1764 static int drawFloor(glhcfg *glhanoi)
1766 glCallList(glhanoi->floorList);
1767 return glhanoi->floorpolys;
1770 static int drawTowers(glhcfg *glhanoi)
1772 glCallList(glhanoi->baseList);
1773 glCallList(glhanoi->poleList);
1774 return glhanoi->basepolys + glhanoi->polepolys;
1777 static int drawTrails1(glhcfg *glhanoi, double t, double thickness, double alpha) {
1778 int i, prev = -1, lines = 0;
1780 GLfloat trailDurInv = 1.0f / glhanoi->trailDuration;
1782 glLineWidth(thickness);
1786 for (i = glhanoi->trailQFront;
1787 i != glhanoi->trailQBack;
1788 i = normalizeQ(i + 1)) {
1789 TrailPoint *tqi = &(glhanoi->trailQ[i]);
1791 if (!fresh && t > tqi->endTime) {
1792 glhanoi->trailQFront = normalizeQ(i + 1);
1794 if (tqi->startTime > t) break;
1795 /* Found trails that haven't timed out. */
1796 if (!fresh) fresh = True;
1798 /* Fade to invisible with age */
1799 trailColor[3] = alpha * (tqi->endTime - t) * trailDurInv;
1800 /* Can't use setMaterial(trailColor, cBlack, 0) because our color needs an alpha value. */
1801 glColor4fv(trailColor);
1802 glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, trailColor);
1803 /* FUTURE: to really do this right, trails should be drawn in back-to-front
1804 order, so that blending is done correctly.
1805 Currently it looks poor when a faded trail is in front of, or coincident with,
1806 a bright trail but is drawn first.
1807 I think for now it's good enough to recommend shorter trails so they
1808 never/rarely overlap.
1809 A jitter per trail arc would also mitigate this problem, to a lesser degree. */
1810 glVertex3fv(glhanoi->trailQ[prev].position);
1811 glVertex3fv(glhanoi->trailQ[i].position);
1814 if (glhanoi->trailQ[i].isEnd)
1826 static int drawTrails(glhcfg *glhanoi) {
1828 double t = getTime();
1830 glEnable (GL_BLEND);
1831 glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1832 glMaterialfv(GL_FRONT, GL_SPECULAR, cBlack);
1833 glMateriali(GL_FRONT, GL_SHININESS, 0);
1835 /* Draw them twice, with different widths and opacities, to make them smoother. */
1836 lines = drawTrails1(glhanoi, t, 1.0, 0.75);
1837 lines += drawTrails1(glhanoi, t, 2.5, 0.5);
1839 glDisable (GL_BLEND);
1841 /* fprintf(stderr, "Drew trails: %d lines\n", lines); */
1845 /* Window management, etc
1847 ENTRYPOINT void reshape_glhanoi(ModeInfo * mi, int width, int height)
1849 glViewport(0, 0, (GLint) width, (GLint) height);
1851 glMatrixMode(GL_PROJECTION);
1853 gluPerspective(30.0, (GLdouble) width / (GLdouble) height, 1.0,
1854 2 * MAX_CAMERA_RADIUS);
1856 glMatrixMode(GL_MODELVIEW);
1859 glClear(GL_COLOR_BUFFER_BIT);
1862 ENTRYPOINT void init_glhanoi(ModeInfo * mi)
1867 (glhcfg *) calloc(MI_NUM_SCREENS(mi), sizeof(glhcfg));
1868 checkAllocAndExit(!!glhanoi_cfg, "configuration");
1871 glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1872 glhanoi->glx_context = init_GL(mi);
1873 glhanoi->numberOfDisks = MI_BATCHCOUNT(mi);
1875 if (glhanoi->numberOfDisks <= 1)
1876 glhanoi->numberOfDisks = 3 + (int) BELLRAND(9);
1878 /* magicnumber is a bitfield, so we can't have more than 31 discs
1879 on a system with 4-byte ints. */
1880 if (glhanoi->numberOfDisks >= 8 * sizeof(int))
1881 glhanoi->numberOfDisks = (8 * sizeof(int)) - 1;
1883 glhanoi->maxDiskIdx = glhanoi->numberOfDisks - 1;
1885 glhanoi->numberOfPoles = get_integer_resource(MI_DISPLAY(mi), "poles", "Integer");
1886 /* Set a number of poles from 3 to numberOfDisks + 1, biased toward lower values,
1887 with probability decreasing linearly. */
1888 if (glhanoi->numberOfPoles <= 2)
1889 glhanoi->numberOfPoles = 3 +
1890 (int)((1 - sqrt(frand(1.0))) * (glhanoi->numberOfDisks - 1));
1892 glhanoi->wire = MI_IS_WIREFRAME(mi);
1894 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
1898 glhanoi->light = light;
1900 glhanoi->texture = texture;
1901 glhanoi->speed = speed;
1902 glhanoi->trailDuration = trails;
1903 /* set trailQSize based on 60 fps (a maximum, more or less) */
1904 /* FUTURE: Should clamp framerate to 60 fps? See flurry.c's draw_flurry().
1905 The only bad effect if we don't is that trail-ends could
1906 show "unnatural" pauses at high fps. */
1907 glhanoi->trailQSize = (int)(trails * 60.0);
1909 reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
1912 glhanoi->light = False;
1913 glhanoi->fog = False;
1914 glhanoi->texture = False;
1917 initLights(!glhanoi->wire && glhanoi->light);
1918 checkAllocAndExit(!makeTextures(glhanoi), "textures\n");
1920 /* Choose linear or circular layout. Could make this a user option. */
1921 glhanoi->layoutLinear = (glhanoi->numberOfPoles == 3);
1927 initTowers(glhanoi);
1930 glEnable(GL_DEPTH_TEST);
1931 glEnable(GL_NORMALIZE);
1932 glEnable(GL_CULL_FACE);
1933 glShadeModel(GL_SMOOTH);
1935 glClearColor(fogcolor[0], fogcolor[1], fogcolor[2], 1.0);
1936 glFogi(GL_FOG_MODE, GL_LINEAR);
1937 glFogfv(GL_FOG_COLOR, fogcolor);
1938 glFogf(GL_FOG_DENSITY, 0.35f);
1939 glHint(GL_FOG_HINT, GL_NICEST);
1940 glFogf(GL_FOG_START, MIN_CAMERA_RADIUS);
1941 glFogf(GL_FOG_END, MAX_CAMERA_RADIUS / 1.9);
1945 glhanoi->duration = START_DURATION;
1946 changeState(glhanoi, START);
1949 ENTRYPOINT void draw_glhanoi(ModeInfo * mi)
1951 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1952 Display *dpy = MI_DISPLAY(mi);
1953 Window window = MI_WINDOW(mi);
1955 if(!glhanoi->glx_context)
1958 glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context));
1960 glPolygonMode(GL_FRONT, glhanoi->wire ? GL_LINE : GL_FILL);
1962 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1963 mi->polygon_count = 0;
1966 glRotatef(current_device_rotation(), 0, 0, 1);
1968 update_glhanoi(glhanoi);
1969 updateView(glhanoi);
1971 if(!glhanoi->wire && glhanoi->texture) {
1972 glEnable(GL_TEXTURE_2D);
1974 mi->polygon_count += drawFloor(glhanoi);
1975 glDisable(GL_TEXTURE_2D);
1977 mi->polygon_count += drawTowers(glhanoi);
1978 mi->polygon_count += drawDisks(glhanoi);
1980 if (glhanoi->trailQSize) {
1981 /* No polygons, just lines. So ignore the return count. */
1982 (void)drawTrails(glhanoi);
1990 glXSwapBuffers(dpy, window);
1993 ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event)
1995 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1997 if(event->xany.type == ButtonPress && event->xbutton.button == Button1) {
1998 glhanoi->button_down_p = True;
1999 glhanoi->drag_x = event->xbutton.x;
2000 glhanoi->drag_y = event->xbutton.y;
2002 } else if(event->xany.type == ButtonRelease
2003 && event->xbutton.button == Button1) {
2004 glhanoi->button_down_p = False;
2006 } else if(event->xany.type == ButtonPress &&
2007 (event->xbutton.button == Button4
2008 || event->xbutton.button == Button5)) {
2009 switch (event->xbutton.button) {
2011 glhanoi->camera[2] += 0.01;
2014 glhanoi->camera[2] -= 0.01;
2018 "glhanoi: unknown button in mousewheel handler\n");
2021 } else if(event->xany.type == MotionNotify
2022 && glhanoi_cfg->button_down_p) {
2025 x_diff = event->xbutton.x - glhanoi->drag_x;
2026 y_diff = event->xbutton.y - glhanoi->drag_y;
2028 glhanoi->camera[0] = (float)x_diff / (float)MI_WIDTH(mi);
2029 glhanoi->camera[1] = (float)y_diff / (float)MI_HEIGHT(mi);
2036 ENTRYPOINT void release_glhanoi(ModeInfo * mi)
2038 if(glhanoi_cfg != NULL) {
2040 for(screen = 0; screen < MI_NUM_SCREENS(mi); screen++) {
2043 glhcfg *glh = &glhanoi_cfg[screen];
2044 glDeleteLists(glh->floorList, 1);
2045 glDeleteLists(glh->baseList, 1);
2046 glDeleteLists(glh->poleList, 1);
2047 glDeleteLists(glh->textureNames[0], 2);
2048 for(j = 0; j < glh->numberOfDisks; ++j) {
2049 glDeleteLists(glh->disk[j].displayList, 1);
2052 for(i = 0; i < glh->numberOfPoles; i++) {
2053 if(glh->pole[i].data != NULL) {
2054 free(glh->pole[i].data);
2063 XSCREENSAVER_MODULE ("GLHanoi", glhanoi)