git.hungrycats.org Git - xscreensaver/blob - hacks/glx/glhanoi.c

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