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
32 # define release_glhanoi 0
34 /* polygon resolution of poles and disks */
38 /* How long to wait at start and finish (seconds). */
39 #define START_DURATION 1.0
40 #define FINISH_DURATION 1.0
41 #define BASE_LENGTH 30.0
42 #define BOARD_SQUARES 8
44 /* Don't draw trail lines till they're this old (sec).
45 Helps trails not be "attached" to the disks. */
46 #define TRAIL_START_DELAY 0.1
48 #define MAX_CAMERA_RADIUS 250.0
49 #define MIN_CAMERA_RADIUS 75.0
51 #define MARBLE_SCALE 1.01
54 /* Return a double precision number in [0...n], with bell curve distribution. */
55 #define BELLRAND(n) ((frand((n)) + frand((n)) + frand((n))) / 3)
62 #define MARBLE_TEXTURE_SIZE 256
65 #define countof(x) (sizeof((x))/sizeof((*x)))
68 #include "xlockmore.h"
70 #ifdef USE_GL /* whole file */
72 typedef struct timeval glhtime;
74 static double getTime(void)
77 #ifdef GETTIMEOFDAY_TWO_ARGS
78 gettimeofday(&t, NULL);
79 #else /* !GETTIMEOFDAY_TWO_ARGS */
81 #endif /* !GETTIMEOFDAY_TWO_ARGS */
82 return t.tv_sec + t.tv_usec / 1000000.0;
103 GLfloat xmin, xmax, ymin, zmin, zmax;
106 GLfloat ucostheta, usintheta;
108 GLdouble rotAngle; /* degree of "flipping" so far, during travel */
109 GLdouble phi; /* angle of motion in xz plane */
121 /* A SubProblem is a recursive subdivision of the problem, and means
122 "Move nDisks disks from src pole to dst pole, using the poles indicated in 'available'." */
126 unsigned long available; /* a bitmask of poles that have no smaller disks on them */
131 double startTime, endTime;
136 GLXContext *glx_context;
142 GLfloat trailDuration;
153 /* src, tmp, dst: index of pole that is source / storage / destination for
161 GLfloat speed; /* coefficient for how fast the disks move */
162 SubProblem *solveStack;
163 int solveStackSize, solveStackIdx;
172 float poleDist; /* distance of poles from center, for round layout */
175 float *diskPos; /* pre-computed disk positions on rods */
180 int floorpolys, basepolys, polepolys;
183 int trailQFront, trailQBack;
186 rotator *the_rotator;
189 GLuint textureNames[N_TEXTURES];
196 static glhcfg *glhanoi_cfg = NULL;
200 static GLfloat trails;
202 static GLfloat speed;
204 static XrmOptionDescRec opts[] = {
205 {"-light", ".glhanoi.light", XrmoptionNoArg, "true"},
206 {"+light", ".glhanoi.light", XrmoptionNoArg, "false"},
207 {"-fog", ".glhanoi.fog", XrmoptionNoArg, "true"},
208 {"+fog", ".glhanoi.fog", XrmoptionNoArg, "false"},
209 {"-texture", ".glhanoi.texture", XrmoptionNoArg, "true"},
210 {"+texture", ".glhanoi.texture", XrmoptionNoArg, "false"},
211 {"-trails", ".glhanoi.trails", XrmoptionSepArg, 0},
212 {"-poles", ".glhanoi.poles", XrmoptionSepArg, 0 },
213 {"-speed", ".glhanoi.speed", XrmoptionSepArg, 0 }
216 static argtype vars[] = {
217 {&light, "light", "Light", DEF_LIGHT, t_Bool},
218 {&fog, "fog", "Fog", DEF_FOG, t_Bool},
219 {&texture, "texture", "Texture", DEF_TEXTURE, t_Bool},
220 {&trails, "trails", "Trails", DEF_TRAILS, t_Float},
221 {&poles, "poles", "Poles", DEF_POLES, t_Int},
222 {&speed, "speed", "Speed", DEF_SPEED, t_Float}
225 static OptionStruct desc[] = {
226 {"+/-light", "whether to light the scene"},
227 {"+/-fog", "whether to apply fog to the scene"},
228 {"+/-texture", "whether to apply texture to the scene"},
229 {"-trails t", "how long of disk trails to show (sec.)"},
230 {"-poles r", "number of poles to move disks between"},
231 {"-speed s", "speed multiplier"}
234 ENTRYPOINT ModeSpecOpt glhanoi_opts = { countof(opts), opts, countof(vars), vars, desc };
238 ModStruct glhanoi_description = {
239 "glhanoi", "init_glhanoi", "draw_glhanoi", NULL,
240 "draw_glhanoi", "init_glhanoi", NULL, &glhanoi_opts,
241 1000, 1, 2, 1, 4, 1.0, "",
242 "Towers of Hanoi", 0, NULL
247 static const GLfloat cBlack[] = { 0.0, 0.0, 0.0, 1.0 };
248 static const GLfloat cWhite[] = { 1.0, 1.0, 1.0, 1.0 };
249 static const GLfloat poleColor[] = { 0.545, 0.137, 0.137 };
250 static const GLfloat baseColor[] = { 0.34, 0.34, 0.48 };
251 /* static const GLfloat baseColor[] = { 0.545, 0.137, 0.137 }; */
252 static const GLfloat fogcolor[] = { 0.5, 0.5, 0.5 };
253 static GLfloat trailColor[] = { 1.0, 1.0, 1.0, 0.5 };
255 static const float left[] = { 1.0, 0.0, 0.0 };
256 static const float up[] = { 0.0, 1.0, 0.0 };
257 static const float front[] = { 0.0, 0.0, 1.0 };
258 static const float right[] = { -1.0, 0.0, 0.0 };
259 static const float down[] = { 0.0, -1.0, 0.0 };
260 static const float back[] = { 0.0, 0.0, -1.0 };
262 static const GLfloat pos0[4] = { 50.0, 50.0, 50.0, 0.0 };
263 static const GLfloat amb0[4] = { 0.0, 0.0, 0.0, 1.0 };
264 static const GLfloat dif0[4] = { 1.0, 1.0, 1.0, 1.0 };
265 static const GLfloat spc0[4] = { 0.0, 1.0, 1.0, 1.0 };
267 static const GLfloat pos1[4] = { -50.0, 50.0, -50.0, 0.0 };
268 static const GLfloat amb1[4] = { 0.0, 0.0, 0.0, 1.0 };
269 static const GLfloat dif1[4] = { 1.0, 1.0, 1.0, 1.0 };
270 static const GLfloat spc1[4] = { 1.0, 1.0, 1.0, 1.0 };
272 static float g = 3.0 * 9.80665; /* hmm, looks like we need more gravity, Scotty... */
274 static void checkAllocAndExit(Bool item, char *descr) {
276 fprintf(stderr, "%s: unable to allocate memory for %s\n",
282 #define DOPUSH(X, Y) (((X)->count) >= ((X)->size)) ? NULL : ((X)->data[(X)->count++] = (Y))
283 #define DOPOP(X) (X)->count <= 0 ? NULL : ((X)->data[--((X)->count)])
285 /* push disk d onto pole idx */
286 static Disk *push(glhcfg *glhanoi, int idx, Disk * d)
288 return DOPUSH(&glhanoi->pole[idx], d);
291 /* pop the top disk from pole idx */
292 static Disk *pop(glhcfg *glhanoi, int idx)
294 return DOPOP(&glhanoi->pole[idx]);
297 static inline void swap(int *x, int *y)
305 * magic - it's magic...
306 * Return 1 if the number of trailing zeroes on i is even, unless i is 1 or 0.
308 static int magic(int i)
313 while((i & 0x01) == 0) {
317 return count % 2 == 0;
320 static float distance(float *p0, float *p1)
326 return (float)sqrt(x * x + y * y + z * z);
330 = c / (a b - 0.25 (a^2 + 2 a b + b^2) )
331 = c / (-0.25 (a^2 - 2 a b + b^2) )
332 = c / (-0.25 ((a - b)(a - b)))
334 static GLfloat A(GLfloat a, GLfloat b, GLfloat c)
337 return c / (a * b - 0.25 * sum * sum);
341 static void moveSetup(glhcfg *glhanoi, Disk * disk)
345 int src = glhanoi->src;
346 int dst = glhanoi->dst;
348 GLfloat sintheta, costheta;
350 double dx, dz; /* total x and z distances from src to dst */
351 Pole *poleSrc, *poleDst;
353 poleSrc = &(glhanoi->pole[src]);
354 poleDst = &(glhanoi->pole[dst]);
356 disk->xmin = poleSrc->position[0];
357 /* glhanoi->poleOffset * (src - (glhanoi->numberOfPoles - 1.0f) * 0.5); */
358 disk->xmax = poleDst->position[0];
359 /* disk->xmax = glhanoi->poleOffset * (dst - (glhanoi->numberOfPoles - 1.0f) * 0.5); */
360 disk->ymin = glhanoi->poleHeight;
361 disk->zmin = poleSrc->position[2];
362 disk->zmax = poleDst->position[2];
364 dx = disk->xmax - disk->xmin;
365 dz = disk->zmax - disk->zmin;
367 if(glhanoi->state != FINISHED) {
368 double xxx = ((dx < 0) ? 180.0 : -180.0);
369 if(random() % 6 == 0) {
370 disk->rotAngle = xxx * (2 - 2 * random() % 2) * (random() % 3 + 1);
372 disk->rotAngle = xxx;
374 if(random() % 4 == 0) {
376 disk->rotAngle = -disk->rotAngle;
379 disk->rotAngle = -180.0;
382 disk->base0 = glhanoi->diskPos[poleSrc->count];
383 disk->base1 = (glhanoi->state == FINISHED) ?
384 disk->base0 : glhanoi->diskPos[poleDst->count];
386 /* horizontal distance to travel? */
387 /* was: absx = sqrt(disk->xmax - disk->xmin); */
388 dh = distance(poleSrc->position, poleDst->position);
389 /* absx = sqrt(dh); */
390 ymax = glhanoi->poleHeight + dh;
391 if(glhanoi->state == FINISHED) {
392 ymax += dh * (double)(glhanoi->numberOfDisks - disk->id);
394 h = ymax - disk->ymin;
395 /* A(a, b, c) = -4 c / (a - b)^2 */
396 /* theta = atan(4 h / (b - a)) */
397 theta = atan(4 * h / dh);
400 costheta = cos(theta);
401 sintheta = sin(theta);
405 /* (2.0 * A(disk->xmin, disk->xmax, h) * costheta * costheta))); */
406 (2.0 * -4 * h / (dh * dh) * costheta * costheta)));
407 disk->usintheta = u * sintheta;
408 disk->ucostheta = u * costheta;
409 /* Not to be confused: disk->dx is the per-time-unit portion of dx */
410 disk->dx = disk->ucostheta * dx / dh;
411 disk->dz = disk->ucostheta * dz / dh;
413 (-u + sqrt(u * u + 2.0 * g * fabs(disk->ymin - disk->base0))) / g;
414 disk->u1 = u + g * disk->t1;
415 disk->t2 = 2.0 * disk->usintheta / g;
416 disk->u2 = disk->usintheta - g * disk->t2;
418 /* Compute direction of travel, in the XZ plane. */
419 disk->phi = atan(dz / dx);
420 disk->phi *= 180.0 / M_PI; /* convert radians to degrees */
423 /* For debugging: show a value as a string of ones and zeroes
424 static const char *byteToBinary(int x) {
428 for (z = 128, i = 0; z > 0; z >>= 1, i++) {
429 b[i] = ((x & z) == z) ? '1' : '0';
437 static void pushMove(glhcfg *glhanoi, int n, int src, int dst, int avail) {
438 SubProblem *sp = &(glhanoi->solveStack[glhanoi->solveStackIdx++]);
440 if (glhanoi->solveStackIdx > glhanoi->solveStackSize) {
441 fprintf(stderr, "solveStack overflow: pushed index %d: %d from %d to %d, using %d\n",
442 glhanoi->solveStackIdx, n, src, dst, avail);
449 sp->available = avail & ~((unsigned long)(1 << src))
450 & ~((unsigned long)(1 << dst));
452 fprintf(stderr, "Debug: > pushed solveStack %d: %d from %d to %d, using %s\n",
453 glhanoi->solveStackIdx - 1, n, src, dst, byteToBinary(sp->available));
457 static Bool solveStackEmpty(glhcfg *glhanoi) {
458 return (glhanoi->solveStackIdx < 1);
461 static SubProblem *popMove(glhcfg *glhanoi) {
463 if (solveStackEmpty(glhanoi)) return (SubProblem *)NULL;
464 sp = &(glhanoi->solveStack[--glhanoi->solveStackIdx]);
465 /* fprintf(stderr, "Debug: < popped solveStack %d: %d from %d to %d, using %s\n",
466 glhanoi->solveStackIdx, sp->nDisks, sp->src, sp->dst, byteToBinary(sp->available)); */
470 /* Return number of bits set in b */
471 static int numBits(unsigned long b) {
480 /* Return index (power of 2) of least significant 1 bit. */
481 static int bitScan(unsigned long b) {
483 for (count = 0; b; count++, b >>= 1) {
484 if (b & 0x1u) return count;
489 /* A bit pattern representing all poles */
490 #define ALL_POLES ((1 << glhanoi->numberOfPoles) - 1)
492 #define REMOVE_BIT(a, b) ((a) & ~(1 << (b)))
493 #define ADD_BIT(a, b) ((a) | (1 << (b)))
495 static void makeMove(glhcfg *glhanoi)
497 if (glhanoi->numberOfPoles == 3) {
498 int fudge = glhanoi->move + 2;
499 int magicNumber = magic(fudge);
502 glhanoi->currentDisk = pop(glhanoi, glhanoi->src);
503 moveSetup(glhanoi, glhanoi->currentDisk);
504 push(glhanoi, glhanoi->dst, glhanoi->currentDisk);
508 if(fudge == 1 || magicNumber) {
509 swap(&glhanoi->src, &glhanoi->tmp);
511 if(fudge == 0 || glhanoi->magicNumber) {
512 swap(&glhanoi->dst, &glhanoi->tmp);
514 glhanoi->magicNumber = magicNumber;
519 if (glhanoi->move == 0) {
520 /* Initialize the solution stack. Original problem:
521 move all disks from pole 0 to furthest pole,
522 using all other poles. */
523 pushMove(glhanoi, glhanoi->numberOfDisks, 0,
524 glhanoi->numberOfPoles - 1,
525 REMOVE_BIT(REMOVE_BIT(ALL_POLES, 0), glhanoi->numberOfPoles - 1));
528 while (!solveStackEmpty(glhanoi)) {
530 sp = *popMove(glhanoi);
532 if (sp.nDisks == 1) {
533 /* We have a single, concrete move to do. */
534 /* moveSetup uses glhanoi->src, dst. */
535 glhanoi->src = sp.src;
536 glhanoi->dst = sp.dst;
537 glhanoi->tmp = tmp; /* Probably unnecessary */
539 glhanoi->currentDisk = pop(glhanoi, sp.src);
540 moveSetup(glhanoi, glhanoi->currentDisk);
541 push(glhanoi, sp.dst, glhanoi->currentDisk);
545 /* Divide and conquer, using Frame-Stewart algorithm, until we get to base case */
546 if (sp.nDisks == 1) break;
548 numAvail = numBits(sp.available);
549 if (numAvail < 2) k = sp.nDisks - 1;
550 else if(numAvail >= sp.nDisks - 2) k = 1;
551 /* heuristic for optimal k: sqrt(2n) (see http://www.cs.wm.edu/~pkstoc/boca.pdf) */
552 else k = (int)(sqrt(2 * sp.nDisks));
554 if (k >= sp.nDisks) k = sp.nDisks - 1;
555 else if (k < 1) k = 1;
557 tmp = bitScan(sp.available);
558 /* fprintf(stderr, "Debug: k is %d, tmp is %d\n", k, tmp); */
560 fprintf(stderr, "Error: n > 1 (%d) and no poles available\n",
564 /* Push on moves in reverse order, since this is a stack. */
565 pushMove(glhanoi, k, tmp, sp.dst,
566 REMOVE_BIT(ADD_BIT(sp.available, sp.src), tmp));
567 pushMove(glhanoi, sp.nDisks - k, sp.src, sp.dst,
568 REMOVE_BIT(sp.available, tmp));
569 pushMove(glhanoi, k, sp.src, tmp,
570 REMOVE_BIT(ADD_BIT(sp.available, sp.dst), tmp));
572 /* Repeat until we've found a move we can make. */
578 static double lerp(double alpha, double start, double end)
580 return start + alpha * (end - start);
583 static void upfunc(GLdouble t, Disk * d)
585 d->position[0] = d->xmin;
586 d->position[1] = d->base0 + (d->u1 - 0.5 * g * t) * t;
587 d->position[2] = d->zmin;
589 d->rotation[1] = 0.0;
592 static void parafunc(GLdouble t, Disk * d)
594 /* ##was: d->position[0] = d->xmin + d->ucostheta * t; */
595 d->position[0] = d->xmin + d->dx * t;
596 d->position[2] = d->zmin + d->dz * t;
597 d->position[1] = d->ymin + (d->usintheta - 0.5 * g * t) * t;
599 d->rotation[1] = d->rotAngle * t / d->t2;
600 /* d->rotAngle * (d->position[0] - d->xmin) / (d->xmax - d->xmin); */
603 static void downfunc(GLdouble t, Disk * d)
605 d->position[0] = d->xmax;
606 d->position[1] = d->ymin + (d->u2 - 0.5 * g * t) * t;
607 d->position[2] = d->zmax;
609 d->rotation[1] = 0.0;
612 #define normalizeQ(i) ((i) >= glhanoi->trailQSize ? (i) - glhanoi->trailQSize : (i))
613 #define normalizeQNeg(i) ((i) < 0 ? (i) + glhanoi->trailQSize : (i))
615 /* Add trail point at position posn at time t onto back of trail queue.
616 Removes old trails if necessary to make room. */
617 static void enQTrail(glhcfg *glhanoi, GLfloat *posn)
619 if (glhanoi->trailQSize && glhanoi->state != MONEY_SHOT) {
620 TrailPoint *tp = &(glhanoi->trailQ[glhanoi->trailQBack]);
621 double t = getTime();
623 tp->position[0] = posn[0];
624 tp->position[1] = posn[1] + glhanoi->diskHeight;
625 /* Slight jitter to prevent clashing with other trails */
626 tp->position[2] = posn[2] + (glhanoi->move % 23) * 0.01;
627 tp->startTime = t + TRAIL_START_DELAY;
628 tp->endTime = t + TRAIL_START_DELAY + glhanoi->trailDuration;
631 /* Update queue back/front indices */
632 glhanoi->trailQBack = normalizeQ(glhanoi->trailQBack + 1);
633 if (glhanoi->trailQBack == glhanoi->trailQFront)
634 glhanoi->trailQFront = normalizeQ(glhanoi->trailQFront + 1);
638 /* Mark last trailpoint in queue as the end of a trail. */
639 /* was: #define endTrail(glh) ((glh)->trailQ[(glh)->trailQBack].isEnd = True) */
640 static void endTrail(glhcfg *glhanoi) {
641 if (glhanoi->trailQSize)
642 glhanoi->trailQ[normalizeQNeg(glhanoi->trailQBack - 1)].isEnd = True;
645 /* Update disk d's position and rotation based on time t.
646 Returns true iff move is finished. */
647 static Bool computePosition(glhcfg *glhanoi, GLfloat t, Disk * d)
649 Bool finished = False;
653 } else if(t < d->t1 + d->t2) {
654 parafunc(t - d->t1, d);
655 enQTrail(glhanoi, d->position);
657 downfunc(t - d->t1 - d->t2, d);
658 if(d->position[1] <= d->base1) {
659 d->position[1] = d->base1;
667 static void updateView(glhcfg *glhanoi)
669 double longitude, latitude, radius;
670 double a, b, c, A, B;
672 get_position(glhanoi->the_rotator, NULL, NULL, &radius,
673 !glhanoi->button_down_p);
674 get_rotation(glhanoi->the_rotator, &longitude, &latitude, NULL,
675 !glhanoi->button_down_p);
676 longitude += glhanoi->camera[0];
677 latitude += glhanoi->camera[1];
678 radius += glhanoi->camera[2];
679 /* FUTURE: tweak this to be smooth: */
680 longitude = longitude - floor(longitude);
681 latitude = latitude - floor(latitude);
682 radius = radius - floor(radius);
684 latitude = 1.0 - latitude;
687 radius = 1.0 - radius;
690 b = glhanoi->centre[1];
691 c = (MIN_CAMERA_RADIUS +
692 radius * (MAX_CAMERA_RADIUS - MIN_CAMERA_RADIUS));
693 A = M_PI / 4.0 * (1.0 - latitude);
694 a = sqrt(b * b + c * c - 2.0 * b * c * cos(A));
695 B = asin(sin(A) * b / a);
696 glRotatef(-B * 180 / M_PI, 1.0, 0.0, 0.0);
698 glTranslatef(0.0f, 0.0f,
699 -(MIN_CAMERA_RADIUS +
700 radius * (MAX_CAMERA_RADIUS - MIN_CAMERA_RADIUS)));
701 glRotatef(longitude * 360.0, 0.0f, 1.0f, 0.0f);
702 glRotatef(latitude * 180.0, cos(longitude * 2.0 * M_PI), 0.0,
703 sin(longitude * 2.0 * M_PI));
706 static void changeState(glhcfg *glhanoi, State state)
708 glhanoi->state = state;
709 glhanoi->startTime = getTime();
712 static Bool finishedHanoi(glhcfg *glhanoi) {
713 /* use different criteria depending on algorithm */
714 return (glhanoi->numberOfPoles == 3 ?
715 glhanoi->move >= glhanoi->numberOfMoves :
716 solveStackEmpty(glhanoi));
719 static void update_glhanoi(glhcfg *glhanoi)
721 double t = getTime() - glhanoi->startTime;
725 switch (glhanoi->state) {
727 if(t < glhanoi->duration) {
731 if(glhanoi->numberOfDisks % 2 == 0) {
732 swap(&glhanoi->tmp, &glhanoi->dst);
734 glhanoi->magicNumber = 1;
736 changeState(glhanoi, MOVE_DISK);
740 if(computePosition(glhanoi, t * glhanoi->currentDisk->speed, glhanoi->currentDisk)) {
741 changeState(glhanoi, MOVE_FINISHED);
747 if(!finishedHanoi(glhanoi)) {
749 changeState(glhanoi, MOVE_DISK);
751 glhanoi->duration = FINISH_DURATION;
752 changeState(glhanoi, FINISHED);
757 if (t < glhanoi->duration)
759 glhanoi->src = glhanoi->olddst;
760 glhanoi->dst = glhanoi->oldsrc;
761 for(i = 0; i < glhanoi->numberOfDisks; ++i) {
762 Disk *disk = pop(glhanoi, glhanoi->src);
763 assert(disk != NULL);
764 moveSetup(glhanoi, disk);
766 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
767 push(glhanoi, glhanoi->dst, &glhanoi->disk[i]);
769 changeState(glhanoi, MONEY_SHOT);
774 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
775 double delay = 0.25 * i;
783 finished = computePosition(glhanoi, t - delay, &glhanoi->disk[i]);
784 glhanoi->disk[i].rotation[1] = 0.0;
791 glhanoi->src = glhanoi->oldsrc;
792 glhanoi->tmp = glhanoi->oldtmp;
793 glhanoi->dst = glhanoi->olddst;
794 changeState(glhanoi, START);
800 fprintf(stderr, "Invalid state\n");
805 static void HSVtoRGBf(GLfloat h, GLfloat s, GLfloat v,
806 GLfloat * r, GLfloat * g, GLfloat * b)
813 GLfloat i, f, p, q, t;
817 h /= 60.0; /* h now in [0,6). */
818 i = floor((double)h); /* i now largest integer <= h */
819 f = h - i; /* f is no fractional part of h */
821 q = v * (1.0 - (s * f));
822 t = v * (1.0 - (s * (1.0 - f)));
858 static void HSVtoRGBv(GLfloat * hsv, GLfloat * rgb)
860 HSVtoRGBf(hsv[0], hsv[1], hsv[2], &rgb[0], &rgb[1], &rgb[2]);
863 static void setMaterial(const GLfloat color[3], const GLfloat hlite[3], int shininess)
866 glMaterialfv(GL_FRONT, GL_SPECULAR, hlite);
867 glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color);
868 glMateriali(GL_FRONT, GL_SHININESS, shininess); /* [0,128] */
872 * drawTube: I know all this stuff is available in gluQuadrics
873 * but I'd originally intended to texture the poles with a 3D wood
874 * texture, but I was having difficulty getting wood... what? Why
875 * are all you Amercians laughing..? Anyway, I don't know if enough
876 * people's hardware supports 3D textures, so I didn't bother (xorg
877 * ATI server doesn't :-( )
879 static int drawTube(GLdouble bottomRadius, GLdouble topRadius,
880 GLdouble bottomThickness, GLdouble topThickness,
881 GLdouble height, GLuint nSlice, GLuint nLoop)
885 GLfloat *cosCache = malloc(sizeof(GLfloat) * nSlice);
886 GLfloat *sinCache = malloc(sizeof(GLfloat) * nSlice);
889 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 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1850 glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context));
1852 glViewport(0, 0, (GLint) width, (GLint) height);
1854 glMatrixMode(GL_PROJECTION);
1856 gluPerspective(30.0, (GLdouble) width / (GLdouble) height, 1.0,
1857 2 * MAX_CAMERA_RADIUS);
1859 glMatrixMode(GL_MODELVIEW);
1862 glClear(GL_COLOR_BUFFER_BIT);
1865 static void free_glhanoi(ModeInfo * mi);
1867 ENTRYPOINT void init_glhanoi(ModeInfo * mi)
1870 MI_INIT(mi, glhanoi_cfg, free_glhanoi);
1872 glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1873 glhanoi->glx_context = init_GL(mi);
1874 glhanoi->numberOfDisks = MI_BATCHCOUNT(mi);
1876 if (glhanoi->numberOfDisks <= 1)
1877 glhanoi->numberOfDisks = 3 + (int) BELLRAND(9);
1879 /* magicnumber is a bitfield, so we can't have more than 31 discs
1880 on a system with 4-byte ints. */
1881 if (glhanoi->numberOfDisks >= 8 * sizeof(int))
1882 glhanoi->numberOfDisks = (8 * sizeof(int)) - 1;
1884 glhanoi->maxDiskIdx = glhanoi->numberOfDisks - 1;
1886 glhanoi->numberOfPoles = get_integer_resource(MI_DISPLAY(mi), "poles", "Integer");
1887 /* Set a number of poles from 3 to numberOfDisks + 1, biased toward lower values,
1888 with probability decreasing linearly. */
1889 if (glhanoi->numberOfPoles <= 2)
1890 glhanoi->numberOfPoles = 3 +
1891 (int)((1 - sqrt(frand(1.0))) * (glhanoi->numberOfDisks - 1));
1893 glhanoi->wire = MI_IS_WIREFRAME(mi);
1895 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
1899 glhanoi->light = light;
1901 glhanoi->texture = texture;
1902 glhanoi->speed = speed;
1903 glhanoi->trailDuration = trails;
1904 /* set trailQSize based on 60 fps (a maximum, more or less) */
1905 /* FUTURE: Should clamp framerate to 60 fps? See flurry.c's draw_flurry().
1906 The only bad effect if we don't is that trail-ends could
1907 show "unnatural" pauses at high fps. */
1908 glhanoi->trailQSize = (int)(trails * 60.0);
1910 reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
1913 glhanoi->light = False;
1914 glhanoi->fog = False;
1915 glhanoi->texture = False;
1918 initLights(!glhanoi->wire && glhanoi->light);
1919 checkAllocAndExit(!makeTextures(glhanoi), "textures\n");
1921 /* Choose linear or circular layout. Could make this a user option. */
1922 glhanoi->layoutLinear = (glhanoi->numberOfPoles == 3);
1928 initTowers(glhanoi);
1931 glEnable(GL_DEPTH_TEST);
1932 glEnable(GL_NORMALIZE);
1933 glEnable(GL_CULL_FACE);
1934 glShadeModel(GL_SMOOTH);
1936 glClearColor(fogcolor[0], fogcolor[1], fogcolor[2], 1.0);
1937 glFogi(GL_FOG_MODE, GL_LINEAR);
1938 glFogfv(GL_FOG_COLOR, fogcolor);
1939 glFogf(GL_FOG_DENSITY, 0.35f);
1940 glHint(GL_FOG_HINT, GL_NICEST);
1941 glFogf(GL_FOG_START, MIN_CAMERA_RADIUS);
1942 glFogf(GL_FOG_END, MAX_CAMERA_RADIUS / 1.9);
1946 glhanoi->duration = START_DURATION;
1947 changeState(glhanoi, START);
1950 ENTRYPOINT void draw_glhanoi(ModeInfo * mi)
1952 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1953 Display *dpy = MI_DISPLAY(mi);
1954 Window window = MI_WINDOW(mi);
1956 if(!glhanoi->glx_context)
1959 glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context));
1961 glPolygonMode(GL_FRONT, glhanoi->wire ? GL_LINE : GL_FILL);
1963 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1964 mi->polygon_count = 0;
1967 glRotatef(current_device_rotation(), 0, 0, 1);
1969 update_glhanoi(glhanoi);
1970 updateView(glhanoi);
1972 # ifdef HAVE_MOBILE /* Keep it the same relative size when rotated. */
1974 GLfloat h = MI_HEIGHT(mi) / (GLfloat) MI_WIDTH(mi);
1975 int o = (int) current_device_rotation();
1976 if (o != 0 && o != 180 && o != -180)
1977 glScalef (1/h, 1/h, 1/h);
1981 if(!glhanoi->wire && glhanoi->texture) {
1982 glEnable(GL_TEXTURE_2D);
1984 mi->polygon_count += drawFloor(glhanoi);
1985 glDisable(GL_TEXTURE_2D);
1987 mi->polygon_count += drawTowers(glhanoi);
1988 mi->polygon_count += drawDisks(glhanoi);
1990 if (glhanoi->trailQSize) {
1991 /* No polygons, just lines. So ignore the return count. */
1992 (void)drawTrails(glhanoi);
2000 glXSwapBuffers(dpy, window);
2003 ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event)
2005 glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
2007 /* #### this is all wrong on iOS -- should be using gltrackball. */
2009 if(event->xany.type == ButtonPress && event->xbutton.button == Button1) {
2010 glhanoi->button_down_p = True;
2011 glhanoi->drag_x = event->xbutton.x;
2012 glhanoi->drag_y = event->xbutton.y;
2014 } else if(event->xany.type == ButtonRelease
2015 && event->xbutton.button == Button1) {
2016 glhanoi->button_down_p = False;
2018 } else if(event->xany.type == ButtonPress &&
2019 (event->xbutton.button == Button4
2020 || event->xbutton.button == Button5)) {
2021 switch (event->xbutton.button) {
2023 glhanoi->camera[2] += 0.01;
2026 glhanoi->camera[2] -= 0.01;
2030 "glhanoi: unknown button in mousewheel handler\n");
2033 } else if(event->xany.type == MotionNotify
2034 && glhanoi_cfg->button_down_p) {
2037 x_diff = event->xbutton.x - glhanoi->drag_x;
2038 y_diff = event->xbutton.y - glhanoi->drag_y;
2040 glhanoi->camera[0] = (float)x_diff / (float)MI_WIDTH(mi);
2041 glhanoi->camera[1] = (float)y_diff / (float)MI_HEIGHT(mi);
2045 #if 0 /* #### doesn't work */
2046 else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
2048 changeState(glhanoi, START);
2055 static void free_glhanoi(ModeInfo * mi)
2059 glhcfg *glh = &glhanoi_cfg[MI_SCREEN(mi)];
2060 if (glh->glx_context) {
2061 glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glh->glx_context));
2062 glDeleteLists(glh->floorList, 1);
2063 glDeleteLists(glh->baseList, 1);
2064 glDeleteLists(glh->poleList, 1);
2065 glDeleteLists(glh->textureNames[0], 2);
2066 for(j = 0; j < glh->numberOfDisks; ++j) {
2067 glDeleteLists(glh->disk[j].displayList, 1);
2070 for(i = 0; i < glh->numberOfPoles; i++) {
2071 if(glh->pole[i].data != NULL) {
2072 free(glh->pole[i].data);
2078 XSCREENSAVER_MODULE ("GLHanoi", glhanoi)