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 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
 892         if(bottomThickness > bottomRadius) {
 893                 bottomThickness = bottomRadius;
 894         }
 895         if(topThickness > topRadius) {
 896                 topThickness = topRadius;
 897         }
 898         if(bottomThickness < 0.0) {
 899                 bottomThickness = 0.0;
 900         }
 901         if(topThickness < 0.0) {
 902                 topThickness = 0.0;
 903         }
 904 /*      if(topRadius >= bottomRadius) {
 905                 maxRadius = topRadius;
 906         } else {
 907                 maxRadius = bottomRadius;
 908         } */
 909
 910         /* bottom */
 911         y = 0.0;
 912         radius = bottomRadius;
 913         innerRadius = bottomRadius - bottomThickness;
 914         /* innerTexCoordSize = texCoordSize * innerRadius / maxRadius; */
 915         /* outerTexCoordSize = texCoordSize * radius / maxRadius; */
 916         /* yTexCoord = minTexCoord; */
 917
 918         glBegin(GL_QUAD_STRIP);
 919
 920         glNormal3f(0.0, -1.0, 0.0);
 921
 922         /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + innerTexCoordSize); */
 923         glVertex3f(0.0, y, innerRadius);
 924
 925         /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + outerTexCoordSize); */
 926         glVertex3f(0.0, y, radius);
 927
 928         for(slice = lastSlice; slice >= 0; --slice) {
 929                 GLfloat theta = 2.0 * M_PI * (double)slice / nSlice;
 930
 931                 cosCache[slice] = cos(theta);
 932                 sinCache[slice] = sin(theta);
 933
 934                 /* glTexCoord3f(midTexCoord + sinCache[slice] * innerTexCoordSize, */
 935                 /* yTexCoord, */
 936                 /* midTexCoord + cosCache[slice] * innerTexCoordSize); */
 937                 glVertex3f(innerRadius * sinCache[slice], y,
 938                                    innerRadius * cosCache[slice]);
 939                 /* glTexCoord3f(midTexCoord + sinCache[slice] * outerTexCoordSize, */
 940                 /* yTexCoord, */
 941                 /* midTexCoord + cosCache[slice] * outerTexCoordSize); */
 942                 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
 943         polys++;
 944         }
 945         glEnd();
 946
 947         /* middle */
 948         for(loop = 0; loop < nLoop; ++loop) {
 949                 GLfloat lowerRadius =
 950                         bottomRadius + (topRadius -
 951                                                         bottomRadius) * (float)loop / (nLoop);
 952                 GLfloat upperRadius =
 953                         bottomRadius + (topRadius - bottomRadius) * (float)(loop +
 954                                                                                                                                 1) /
 955                         (nLoop);
 956                 GLfloat lowerY = height * (float)loop / (nLoop);
 957                 GLfloat upperY = height * (float)(loop + 1) / (nLoop);
 958                 GLfloat factor = (topRadius - topThickness) -
 959                         (bottomRadius - bottomThickness);
 960
 961                 /* outside */
 962                 glBegin(GL_QUAD_STRIP);
 963                 for(slice = 0; slice < nSlice; ++slice) {
 964                         glNormal3f(sinCache[slice], 0.0, cosCache[slice]);
 965                         glVertex3f(upperRadius * sinCache[slice], upperY,
 966                                            upperRadius * cosCache[slice]);
 967                         glVertex3f(lowerRadius * sinCache[slice], lowerY,
 968                                            lowerRadius * cosCache[slice]);
 969             polys++;
 970                 }
 971                 glNormal3f(0.0, 0.0, 1.0);
 972                 glVertex3f(0.0, upperY, upperRadius);
 973                 glVertex3f(0.0, lowerY, lowerRadius);
 974         polys++;
 975                 glEnd();
 976
 977                 /* inside */
 978                 lowerRadius = bottomRadius - bottomThickness +
 979                         factor * (float)loop / (nLoop);
 980                 upperRadius = bottomRadius - bottomThickness +
 981                         factor * (float)(loop + 1) / (nLoop);
 982
 983                 glBegin(GL_QUAD_STRIP);
 984                 glNormal3f(0.0, 0.0, -1.0);
 985                 glVertex3f(0.0, upperY, upperRadius);
 986                 glVertex3f(0.0, lowerY, lowerRadius);
 987                 for(slice = lastSlice; slice >= 0; --slice) {
 988                         glNormal3f(-sinCache[slice], 0.0, -cosCache[slice]);
 989                         glVertex3f(upperRadius * sinCache[slice], upperY,
 990                                            upperRadius * cosCache[slice]);
 991                         glVertex3f(lowerRadius * sinCache[slice], lowerY,
 992                                            lowerRadius * cosCache[slice]);
 993             polys++;
 994                 }
 995                 glEnd();
 996         }
 997
 998         /* top */
 999         y = height;
1000         radius = topRadius;
1001         innerRadius = topRadius - topThickness;
1002
1003         glBegin(GL_QUAD_STRIP);
1004         glNormal3f(0.0, 1.0, 0.0);
1005         for(slice = 0; slice < nSlice; ++slice) {
1006                 glVertex3f(innerRadius * sinCache[slice], y,
1007                                    innerRadius * cosCache[slice]);
1008
1009                 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
1010         polys++;
1011         }
1012         glVertex3f(0.0, y, innerRadius);
1013         glVertex3f(0.0, y, radius);
1014         glEnd();
1015     return polys;
1016 }
1017
1018 static int drawPole(GLfloat radius, GLfloat length)
1019 {
1020   return drawTube(radius, radius, radius, radius, length, NSLICE, NLOOPS);
1021 }
1022
1023 static int drawDisk3D(GLdouble inner_radius, GLdouble outer_radius,
1024                       GLdouble height)
1025 {
1026   return drawTube(outer_radius, outer_radius, outer_radius - inner_radius,
1027                   outer_radius - inner_radius, height, NSLICE, NLOOPS);
1028 }
1029
1030 /* used for drawing base */
1031 static int drawCuboid(GLfloat length, GLfloat width, GLfloat height)
1032 {
1033         GLfloat xmin = -length / 2.0f;
1034         GLfloat xmax = length / 2.0f;
1035         GLfloat zmin = -width / 2.0f;
1036         GLfloat zmax = width / 2.0f;
1037         GLfloat ymin = 0.0f;
1038         GLfloat ymax = height;
1039     int polys = 0;
1040
1041         glBegin(GL_QUADS);
1042         /* front */
1043         glNormal3fv(front);
1044         glVertex3f(xmin, ymin, zmax);   /* 0 */
1045         glVertex3f(xmax, ymin, zmax);   /* 1 */
1046         glVertex3f(xmax, ymax, zmax);   /* 2 */
1047         glVertex3f(xmin, ymax, zmax);   /* 3 */
1048     polys++;
1049         /* right */
1050         glNormal3fv(right);
1051         glVertex3f(xmax, ymin, zmax);   /* 1 */
1052         glVertex3f(xmax, ymin, zmin);   /* 5 */
1053         glVertex3f(xmax, ymax, zmin);   /* 6 */
1054         glVertex3f(xmax, ymax, zmax);   /* 2 */
1055     polys++;
1056         /* back */
1057         glNormal3fv(back);
1058         glVertex3f(xmax, ymin, zmin);   /* 5 */
1059         glVertex3f(xmin, ymin, zmin);   /* 4 */
1060         glVertex3f(xmin, ymax, zmin);   /* 7 */
1061         glVertex3f(xmax, ymax, zmin);   /* 6 */
1062     polys++;
1063         /* left */
1064         glNormal3fv(left);
1065         glVertex3f(xmin, ymin, zmin);   /* 4 */
1066         glVertex3f(xmin, ymin, zmax);   /* 0 */
1067         glVertex3f(xmin, ymax, zmax);   /* 3 */
1068         glVertex3f(xmin, ymax, zmin);   /* 7 */
1069     polys++;
1070         /* top */
1071         glNormal3fv(up);
1072         glVertex3f(xmin, ymax, zmax);   /* 3 */
1073         glVertex3f(xmax, ymax, zmax);   /* 2 */
1074         glVertex3f(xmax, ymax, zmin);   /* 6 */
1075         glVertex3f(xmin, ymax, zmin);   /* 7 */
1076     polys++;
1077         /* bottom */
1078         glNormal3fv(down);
1079         glVertex3f(xmin, ymin, zmin);   /* 4 */
1080         glVertex3f(xmax, ymin, zmin);   /* 5 */
1081         glVertex3f(xmax, ymin, zmax);   /* 1 */
1082         glVertex3f(xmin, ymin, zmax);   /* 0 */
1083     polys++;
1084         glEnd();
1085     return polys;
1086 }
1087
1088 /* Set normal vector in xz plane, based on rotation around center. */
1089 static void setNormalV(glhcfg *glhanoi, GLfloat theta, int y1, int y2, int r1) {
1090         if (y1 == y2) /* up/down */
1091                 glNormal3f(0.0, y1 ? 1.0 : -1.0, 0.0);
1092         else if (!r1) /* inward */
1093                 glNormal3f(-cos(theta), 0.0, -sin(theta));
1094         else /* outward */
1095                 glNormal3f(cos(theta), 0.0, sin(theta));
1096 }
1097
1098 /* y1, r1, y2, r2 are indices into y, r, beg, end */
1099 static int drawBaseStrip(glhcfg *glhanoi, int y1, int r1, int y2, int r2,
1100                 GLfloat y[2], GLfloat r[2], GLfloat beg[2][2], GLfloat end[2][2]) {
1101         int i;
1102         GLfloat theta, costh, sinth, x[2], z[2];
1103         GLfloat theta1 = (M_PI * 2) / (glhanoi->numberOfPoles + 1);
1104
1105         glBegin(GL_QUAD_STRIP);
1106
1107         /* beginning edge */
1108         glVertex3f(beg[r1][0], y[y1], beg[r1][1]);
1109         glVertex3f(beg[r2][0], y[y2], beg[r2][1]);
1110         setNormalV(glhanoi, theta1, y1, y2, r1);
1111
1112         for (i = 1; i < glhanoi->numberOfPoles; i++) {
1113                 theta = theta1 * (i + 0.5);
1114                 costh = cos(theta);
1115                 sinth = sin(theta);
1116                 x[0] = costh * r[0];
1117                 x[1] = costh * r[1];
1118                 z[0] = sinth * r[0];
1119                 z[1] = sinth * r[1];
1120
1121                 glVertex3f(x[r1], y[y1], z[r1]);
1122                 glVertex3f(x[r2], y[y2], z[r2]);
1123
1124                 setNormalV(glhanoi, theta1 * (i + 1), y1, y2, r1);
1125         }
1126
1127         /* end edge */
1128         glVertex3f(end[r1][0], y[y1], end[r1][1]);
1129         glVertex3f(end[r2][0], y[y2], end[r2][1]);
1130         setNormalV(glhanoi, glhanoi->numberOfPoles, y1, y2, r1);
1131
1132         glEnd();
1133     return glhanoi->numberOfPoles;
1134 }
1135
1136 /* Draw base such that poles are distributed around a regular polygon. */
1137 static int drawRoundBase(glhcfg *glhanoi) {
1138         int polys = 0;
1139         GLfloat theta, sinth, costh;
1140
1141         /*
1142                 r[0] = (minimum) inner radius of base at vertices
1143                 r[1] = (minimum) outer radius of base at vertices
1144                 y[0] = bottom of base
1145                 y[1] = top of base */
1146         GLfloat r[2], y[2];
1147         /* positions of end points: beginning, end.
1148                 beg[0] is inner corner of beginning of base, beg[1] is outer corner.
1149                 beg[i][0] is x, [i][1] is z. */
1150         GLfloat beg[2][2], end[2][2], begNorm, endNorm;
1151         /* ratio of radius at base vertices to ratio at poles */
1152         GLfloat longer = 1.0 / cos(M_PI / (glhanoi->numberOfPoles + 1));
1153
1154         r[0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * longer;
1155         r[1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * longer;
1156         y[0] = 0;
1157         y[1] = glhanoi->baseHeight;
1158
1159         /* compute beg, end. Make the ends square. */
1160         theta = M_PI * 2 / (glhanoi->numberOfPoles + 1);
1161
1162         costh = cos(theta);
1163         sinth = sin(theta);
1164         beg[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh +
1165                 glhanoi->maxDiskRadius * sinth;
1166         beg[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh +
1167                 glhanoi->maxDiskRadius * sinth;
1168         beg[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth -
1169                 glhanoi->maxDiskRadius * costh;
1170         beg[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth -
1171                 glhanoi->maxDiskRadius * costh;
1172         begNorm = theta - M_PI * 0.5;
1173
1174         theta = M_PI * 2 * glhanoi->numberOfPoles / (glhanoi->numberOfPoles + 1);
1175
1176         costh = cos(theta);
1177         sinth = sin(theta);
1178         end[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh -
1179                 glhanoi->maxDiskRadius * sinth;
1180         end[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh -
1181                 glhanoi->maxDiskRadius * sinth;
1182         end[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth +
1183                 glhanoi->maxDiskRadius * costh;
1184         end[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth +
1185                 glhanoi->maxDiskRadius * costh;
1186         endNorm = theta + M_PI * 0.5;
1187
1188         /* bottom: never seen
1189         polys  = drawBaseStrip(glhanoi, 0, 0, 0, 1, y, r, beg, end); */
1190         /* outside edge */
1191         polys += drawBaseStrip(glhanoi, 0, 1, 1, 1, y, r, beg, end);
1192         /* top */
1193         polys += drawBaseStrip(glhanoi, 1, 1, 1, 0, y, r, beg, end);
1194         /* inside edge */
1195         polys += drawBaseStrip(glhanoi, 1, 0, 0, 0, y, r, beg, end);
1196
1197         /* Draw ends */
1198         glBegin(GL_QUADS);
1199
1200         glVertex3f(beg[0][0], y[1], beg[0][1]);
1201         glVertex3f(beg[1][0], y[1], beg[1][1]);
1202         glVertex3f(beg[1][0], y[0], beg[1][1]);
1203         glVertex3f(beg[0][0], y[0], beg[0][1]);
1204         glNormal3f(cos(begNorm), 0, sin(begNorm));
1205
1206         glVertex3f(end[0][0], y[0], end[0][1]);
1207         glVertex3f(end[1][0], y[0], end[1][1]);
1208         glVertex3f(end[1][0], y[1], end[1][1]);
1209         glVertex3f(end[0][0], y[1], end[0][1]);
1210         glNormal3f(cos(endNorm), 0, sin(endNorm));
1211
1212         polys += 2;
1213
1214         glEnd();
1215
1216         return polys;
1217 }
1218
1219 static int drawDisks(glhcfg *glhanoi)
1220 {
1221         int i;
1222     int polys = 0;
1223
1224         glPushMatrix();
1225         glTranslatef(0.0f, glhanoi->baseHeight, 0.0f);
1226         for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1227                 Disk *disk = &glhanoi->disk[i];
1228                 GLfloat *pos = disk->position;
1229                 GLfloat *rot = disk->rotation;
1230
1231                 glPushMatrix();
1232                 glTranslatef(pos[0], pos[1], pos[2]);
1233                 if(rot[1] != 0.0) {
1234                         glTranslatef(0.0, glhanoi->diskHeight / 2.0, 0.0);
1235                         /* rotate around different axis depending on phi */
1236                         if (disk->phi != 0.0)
1237                                 glRotatef(-disk->phi, 0.0, 1.0, 0.0);
1238                         glRotatef(rot[1], 0.0, 0.0, 1.0);
1239                         if (disk->phi != 0.0)
1240                                 glRotatef(disk->phi, 0.0, 1.0, 0.0);
1241                         glTranslatef(0.0, -glhanoi->diskHeight / 2.0, 0.0);
1242                 }
1243                 glCallList(disk->displayList);
1244         polys += disk->polys;
1245                 glPopMatrix();
1246         }
1247         glPopMatrix();
1248     return polys;
1249 }
1250
1251 static GLfloat getDiskRadius(glhcfg *glhanoi, int i)
1252 {
1253         GLfloat retVal = glhanoi->maxDiskRadius *
1254                 ((GLfloat) i + 3.0) / (glhanoi->numberOfDisks + 3.0);
1255         return retVal;
1256 }
1257
1258 static void initData(glhcfg *glhanoi)
1259 {
1260         int i;
1261         GLfloat sinPiOverNP;
1262
1263         glhanoi->baseLength = BASE_LENGTH;
1264         if (glhanoi->layoutLinear) {
1265                 glhanoi->maxDiskRadius = glhanoi->baseLength /
1266                         (2 * 0.95 * glhanoi->numberOfPoles);
1267         } else {
1268             sinPiOverNP = sin(M_PI / (glhanoi->numberOfPoles + 1));
1269                 glhanoi->maxDiskRadius = (sinPiOverNP * glhanoi->baseLength * 0.5 * 0.95) / (1 + sinPiOverNP);
1270         }
1271
1272         glhanoi->poleDist = glhanoi->baseLength * 0.5 - glhanoi->maxDiskRadius;
1273         glhanoi->poleRadius = glhanoi->maxDiskRadius / (glhanoi->numberOfDisks + 3.0);
1274         /* fprintf(stderr, "Debug: baseL = %f, maxDiskR = %f, poleR = %f\n",
1275                 glhanoi->baseLength, glhanoi->maxDiskRadius, glhanoi->poleRadius); */
1276         glhanoi->baseWidth  = 2.0 * glhanoi->maxDiskRadius;
1277         glhanoi->poleOffset = 2.0 * getDiskRadius(glhanoi, glhanoi->maxDiskIdx);
1278         glhanoi->diskHeight = 2.0 * glhanoi->poleRadius;
1279         glhanoi->baseHeight = 2.0 * glhanoi->poleRadius;
1280         glhanoi->poleHeight = glhanoi->numberOfDisks *
1281                 glhanoi->diskHeight + glhanoi->poleRadius;
1282         /* numberOfMoves only applies if numberOfPoles = 3 */
1283         glhanoi->numberOfMoves = (1 << glhanoi->numberOfDisks) - 1;
1284         /* use golden ratio */
1285         glhanoi->boardSize = glhanoi->baseLength * 0.5 * (1.0 + sqrt(5.0));
1286
1287         glhanoi->pole = (Pole *)calloc(glhanoi->numberOfPoles, sizeof(Pole));
1288         checkAllocAndExit(!!glhanoi->pole, "poles");
1289
1290         for(i = 0; i < glhanoi->numberOfPoles; i++) {
1291                 checkAllocAndExit(
1292                         !!(glhanoi->pole[i].data = calloc(glhanoi->numberOfDisks, sizeof(Disk *))),
1293                         "disk stack");
1294                 glhanoi->pole[i].size = glhanoi->numberOfDisks;
1295         }
1296         checkAllocAndExit(
1297                         !!(glhanoi->diskPos = calloc(glhanoi->numberOfDisks, sizeof(double))),
1298                         "diskPos");
1299
1300         if (glhanoi->trailQSize) {
1301                 glhanoi->trailQ = (TrailPoint *)calloc(glhanoi->trailQSize, sizeof(TrailPoint));
1302                 checkAllocAndExit(!!glhanoi->trailQ, "trail queue");
1303         } else glhanoi->trailQ = (TrailPoint *)NULL;
1304         glhanoi->trailQFront = glhanoi->trailQBack = 0;
1305
1306         glhanoi->the_rotator = make_rotator(0.1, 0.025, 0, 1, 0.005, False);
1307         /* or glhanoi->the_rotator = make_rotator(0.025, 0.025, 0.025, 0.5, 0.005, False); */
1308         glhanoi->button_down_p = False;
1309
1310         glhanoi->src = glhanoi->oldsrc = 0;
1311         glhanoi->tmp = glhanoi->oldtmp = 1;
1312         glhanoi->dst = glhanoi->olddst = glhanoi->numberOfPoles - 1;
1313
1314         if (glhanoi->numberOfPoles > 3) {
1315                 glhanoi->solveStackSize = glhanoi->numberOfDisks + 2;
1316                 glhanoi->solveStack = (SubProblem *)calloc(glhanoi->solveStackSize, sizeof(SubProblem));
1317                 checkAllocAndExit(!!glhanoi->solveStack, "solving stack");
1318                 glhanoi->solveStackIdx = 0;
1319         }
1320 }
1321
1322 static void initView(glhcfg *glhanoi)
1323 {
1324         glhanoi->camera[0] = 0.0;
1325         glhanoi->camera[1] = 0.0;
1326         glhanoi->camera[2] = 0.0;
1327         glhanoi->centre[0] = 0.0;
1328         glhanoi->centre[1] = glhanoi->poleHeight * 3.0;
1329         glhanoi->centre[2] = 0.0;
1330 }
1331
1332 /*
1333  * noise_improved.c - based on ImprovedNoise.java
1334  * JAVA REFERENCE IMPLEMENTATION OF IMPROVED NOISE - COPYRIGHT 2002 KEN PERLIN.
1335  */
1336 static double fade(double t)
1337 {
1338         return t * t * t * (t * (t * 6 - 15) + 10);
1339 }
1340
1341 static double grad(int hash, double x, double y, double z)
1342 {
1343         int h = hash & 15;                      /* CONVERT LO 4 BITS OF HASH CODE */
1344         double u = h < 8 ? x : y,       /* INTO 12 GRADIENT DIRECTIONS. */
1345                 v = h < 4 ? y : h == 12 || h == 14 ? x : z;
1346         return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
1347 }
1348
1349 static const int permutation[] = { 151, 160, 137, 91, 90, 15,
1350         131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142,
1351         8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 26,
1352         197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237,
1353         149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71,
1354         134, 139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60,
1355         211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 102, 143,
1356         54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89,
1357         18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 198,
1358         173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118,
1359         126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189,
1360         28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70,
1361         221, 153, 101, 155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108,
1362         110, 79, 113, 224, 232, 178, 185, 112, 104, 218, 246, 97, 228, 251,
1363         34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241, 81, 51, 145,
1364         235, 249, 14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 157, 184,
1365         84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205,
1366         93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61,
1367         156, 180
1368 };
1369
1370 static void initNoise(glhcfg *glhanoi)
1371 {
1372         int i;
1373         for(i = 0; i < 256; i++)
1374                 glhanoi->p[256 + i] = glhanoi->p[i] = permutation[i];
1375 }
1376
1377 static double improved_noise(glhcfg *glhanoi, double x, double y, double z)
1378 {
1379         double u, v, w;
1380         int A, AA, AB, B, BA, BB;
1381         int X = (int)floor(x) & 255,    /* FIND UNIT CUBE THAT */
1382                 Y = (int)floor(y) & 255,        /* CONTAINS POINT. */
1383                 Z = (int)floor(z) & 255;
1384         if(!glhanoi->noise_initted) {
1385                 initNoise(glhanoi);
1386                 glhanoi->noise_initted = 1;
1387         }
1388         x -= floor(x);                          /* FIND RELATIVE X,Y,Z */
1389         y -= floor(y);                          /* OF POINT IN CUBE. */
1390         z -= floor(z);
1391         u  = fade(x),                           /* COMPUTE FADE CURVES */
1392         v  = fade(y),                           /* FOR EACH OF X,Y,Z. */
1393         w  = fade(z);
1394         A  = glhanoi->p[X] + Y;
1395         AA = glhanoi->p[A] + Z;
1396         AB = glhanoi->p[A + 1] + Z,     /* HASH COORDINATES OF */
1397         B  = glhanoi->p[X + 1] + Y;
1398         BA = glhanoi->p[B] + Z;
1399         BB = glhanoi->p[B + 1] + Z;     /* THE 8 CUBE CORNERS, */
1400         return lerp(w, lerp(v, lerp(u, grad(glhanoi->p[AA], x, y, z),/* AND ADD */
1401                                                                 grad(glhanoi->p[BA], x - 1, y, z)),/* BLENDED */
1402                                                 lerp(u, grad(glhanoi->p[AB], x, y - 1, z),/* RESULTS */
1403                                                          grad(glhanoi->p[BB], x - 1, y - 1, z))),/* FROM 8 CORNERS */
1404                                 lerp(v, lerp(u, grad(glhanoi->p[AA + 1], x, y, z - 1), grad(glhanoi->p[BA + 1], x - 1, y, z - 1)),      /* OF CUBE */
1405                                          lerp(u, grad(glhanoi->p[AB + 1], x, y - 1, z - 1),
1406                                                   grad(glhanoi->p[BB + 1], x - 1, y - 1, z - 1))));
1407 }
1408
1409 /*
1410  * end noise_improved.c - based on ImprovedNoise.java
1411  */
1412
1413 struct tex_col_t {
1414         GLuint *colours;
1415         /* GLfloat *points; */
1416         unsigned int ncols;
1417 };
1418 typedef struct tex_col_t tex_col_t;
1419
1420 static GLubyte *makeTexture(glhcfg *glhanoi, int x_size, int y_size, int z_size,
1421                                          GLuint(*texFunc) (glhcfg *, double, double, double,
1422                                                                            tex_col_t *), tex_col_t * colours)
1423 {
1424         int i, j, k;
1425         GLubyte *textureData;
1426         GLuint *texturePtr;
1427         double x, y, z;
1428         double xi, yi, zi;
1429
1430         if((textureData =
1431                 calloc(x_size * y_size * z_size, sizeof(GLuint))) == NULL) {
1432                 return NULL;
1433         }
1434
1435         xi = 1.0 / x_size;
1436         yi = 1.0 / y_size;
1437         zi = 1.0 / z_size;
1438
1439         z = 0.0;
1440         texturePtr = (void *)textureData;
1441         for(k = 0; k < z_size; k++, z += zi) {
1442                 y = 0.0;
1443                 for(j = 0; j < y_size; j++, y += yi) {
1444                         x = 0.0;
1445                         for(i = 0; i < x_size; i++, x += xi) {
1446                                 *texturePtr = texFunc(glhanoi, x, y, z, colours);
1447                                 ++texturePtr;
1448                         }
1449                 }
1450         }
1451         return textureData;
1452 }
1453
1454 static void freeTexCols(tex_col_t*p)
1455 {
1456         free(p->colours);
1457         free(p);
1458 }
1459
1460 static tex_col_t *makeMarbleColours(void)
1461 {
1462         tex_col_t *marbleColours;
1463         int ncols = 2;
1464
1465         marbleColours = malloc(sizeof(tex_col_t));
1466         if(marbleColours == NULL) return NULL;
1467         marbleColours->colours = calloc(sizeof(GLuint), ncols);
1468         if(marbleColours->colours == NULL) return NULL;
1469         marbleColours->ncols = ncols;
1470
1471         marbleColours->colours[0] = 0x3f3f3f3f;
1472         marbleColours->colours[1] = 0xffffffff;
1473
1474         return marbleColours;
1475 }
1476
1477 static double turb(glhcfg *glhanoi, double x, double y, double z, int octaves)
1478 {
1479         int oct, freq = 1;
1480         double r = 0.0;
1481
1482         for(oct = 0; oct < octaves; ++oct) {
1483                 r += fabs(improved_noise(glhanoi, freq * x, freq * y, freq * z)) / freq;
1484                 freq <<= 1;
1485         }
1486         return r / 2.0;
1487 }
1488
1489 static void perturb(glhcfg *glhanoi, double *x, double *y, double *z, double scale)
1490 {
1491         double t = scale * turb(glhanoi, *x, *y, *z, 4);
1492         *x += t;
1493         *y += t;
1494         *z += t;
1495 }
1496
1497 static double f_m(double x, double y, double z)
1498 {
1499         return sin(3.0 * M_PI * x);
1500 }
1501
1502 static GLuint C_m(double x, const tex_col_t * tex_cols)
1503 {
1504         int r = tex_cols->colours[0] & 0xff;
1505         int g = tex_cols->colours[0] >> 8 & 0xff;
1506         int b = tex_cols->colours[0] >> 16 & 0xff;
1507         double factor;
1508         int r1, g1, b1;
1509         x = x - floor(x);
1510
1511         factor = (1.0 + sin(2.0 * M_PI * x)) / 2.0;
1512
1513         r1 = (tex_cols->colours[1] & 0xff);
1514         g1 = (tex_cols->colours[1] >> 8 & 0xff);
1515         b1 = (tex_cols->colours[1] >> 16 & 0xff);
1516
1517         r += (int)(factor * (r1 - r));
1518         g += (int)(factor * (g1 - g));
1519         b += (int)(factor * (b1 - b));
1520
1521         return 0xff000000 | (b << 16) | (g << 8) | r;
1522 }
1523
1524
1525 static GLuint makeMarbleTexture(glhcfg *glhanoi, double x, double y, double z, tex_col_t * colours)
1526 {
1527         perturb(glhanoi, &x, &y, &z, MARBLE_SCALE);
1528         return C_m(f_m(x, y, z), colours);
1529 }
1530
1531 static void setTexture(glhcfg *glhanoi, int n)
1532 {
1533         glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[n]);
1534 }
1535
1536 /* returns 1 on failure, 0 on success */
1537 static int makeTextures(glhcfg *glhanoi)
1538 {
1539         GLubyte *marbleTexture;
1540         tex_col_t *marbleColours;
1541
1542         glGenTextures(N_TEXTURES, glhanoi->textureNames);
1543
1544         if((marbleColours = makeMarbleColours()) == NULL) {
1545                 return 1;
1546         }
1547         if((marbleTexture =
1548                 makeTexture(glhanoi, MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 1,
1549                                         makeMarbleTexture, marbleColours)) == NULL) {
1550                 return 1;
1551         }
1552
1553         glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[0]);
1554         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
1555         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
1556         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
1557         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
1558         glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA,
1559                                  MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 0,
1560                                  GL_RGBA, GL_UNSIGNED_BYTE, marbleTexture);
1561         free(marbleTexture);
1562         freeTexCols(marbleColours);
1563
1564         return 0;
1565 }
1566
1567 static void initFloor(glhcfg *glhanoi)
1568 {
1569         int i, j;
1570         float tileSize = glhanoi->boardSize / BOARD_SQUARES;
1571         float x0, x1, z0, z1;
1572         float tx0, tx1, tz0, tz1;
1573         const float *col = cWhite;
1574         float texIncr = 1.0 / BOARD_SQUARES;
1575
1576     glhanoi->floorpolys = 0;
1577         checkAllocAndExit(!!(glhanoi->floorList = glGenLists(1)), "floor display list");
1578         glNewList(glhanoi->floorList, GL_COMPILE);
1579         x0 = -glhanoi->boardSize / 2.0;
1580         tx0 = 0.0f;
1581         setMaterial(col, cWhite, 128);
1582         setTexture(glhanoi, 0);
1583         glNormal3fv(up);
1584         for(i = 0; i < BOARD_SQUARES; i++, x0 += tileSize, tx0 += texIncr) {
1585                 x1 = x0 + tileSize;
1586                 tx1 = tx0 + texIncr;
1587                 z0 = -glhanoi->boardSize / 2.0;
1588                 tz0 = 0.0f;
1589                 for(j = 0; j < BOARD_SQUARES; j++, z0 += tileSize, tz0 += texIncr) {
1590                         int colIndex = (i + j) & 0x1;
1591
1592                         z1 = z0 + tileSize;
1593                         tz1 = tz0 + texIncr;
1594
1595                         if(colIndex)
1596                                 col = cWhite;
1597                         else
1598                                 col = cBlack;
1599
1600                         setMaterial(col, cWhite, 100);
1601
1602                         glBegin(GL_QUADS);
1603
1604                         glTexCoord2d(tx0, tz0);
1605                         glVertex3f(x0, 0.0, z0);
1606
1607                         glTexCoord2d(tx0, tz1);
1608                         glVertex3f(x0, 0.0, z1);
1609
1610                         glTexCoord2d(tx1, tz1);
1611                         glVertex3f(x1, 0.0, z1);
1612
1613                         glTexCoord2d(tx1, tz0);
1614                         glVertex3f(x1, 0.0, z0);
1615             glhanoi->floorpolys++;
1616                         glEnd();
1617                 }
1618         }
1619         glEndList();
1620 }
1621
1622 static void initBase(glhcfg *glhanoi)
1623 {
1624         checkAllocAndExit(!!(glhanoi->baseList = glGenLists(1)), "tower bases display list");
1625
1626         glNewList(glhanoi->baseList, GL_COMPILE);
1627         setMaterial(baseColor, cWhite, 50);
1628         if (glhanoi->layoutLinear) {
1629                 glhanoi->basepolys = drawCuboid(glhanoi->baseLength, glhanoi->baseWidth,
1630                                                                                 glhanoi->baseHeight);
1631         } else {
1632                 glhanoi->basepolys = drawRoundBase(glhanoi);
1633         }
1634         glEndList();
1635 }
1636
1637 static void initTowers(glhcfg *glhanoi)
1638 {
1639         int i;
1640
1641         checkAllocAndExit(!!(glhanoi->poleList = glGenLists(1)), "poles display list\n");
1642
1643         glNewList(glhanoi->poleList, GL_COMPILE);
1644         /* glTranslatef(-glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5f, glhanoi->baseHeight, 0.0f); */
1645         setMaterial(poleColor, cWhite, 50);
1646         for (i = 0; i < glhanoi->numberOfPoles; i++) {
1647                 GLfloat *p = glhanoi->pole[i].position;
1648                 GLfloat rad = (M_PI * 2.0 * (i + 1)) / (glhanoi->numberOfPoles + 1);
1649
1650                 p[1] = glhanoi->baseHeight;
1651
1652                 if (glhanoi->layoutLinear) {
1653                         /* Linear: */
1654                         p[0] = -glhanoi->poleOffset * ((glhanoi->numberOfPoles - 1) * 0.5f - i);
1655                         p[2] = 0.0f;
1656                 } else {
1657                         /* Circular layout: */
1658                         p[0] = cos(rad) * glhanoi->poleDist;
1659                         p[2] = sin(rad) * glhanoi->poleDist;
1660                 }
1661
1662                 glPushMatrix();
1663                 glTranslatef(p[0], p[1], p[2]);
1664                 glhanoi->polepolys = drawPole(glhanoi->poleRadius, glhanoi->poleHeight);
1665                 glPopMatrix();
1666
1667         }
1668         glEndList();
1669 }
1670
1671 /* Parameterized hue based on input 0.0 - 1.0. */
1672 static double cfunc(double x)
1673 {
1674 #define COMP <
1675         if(x < 2.0 / 7.0) {
1676                 return (1.0 / 12.0) / (1.0 / 7.0) * x;
1677         }
1678         if(x < 3.0 / 7.0) {
1679                 /* (7x - 1) / 6 */
1680                 return (1.0 + 1.0 / 6.0) * x - 1.0 / 6.0;
1681         }
1682         if(x < 4.0 / 7.0) {
1683                 return (2.0 + 1.0 / 3.0) * x - 2.0 / 3.0;
1684         }
1685         if(x < 5.0 / 7.0) {
1686                 return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1687         }
1688         return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1689 }
1690
1691 static void initDisks(glhcfg *glhanoi)
1692 {
1693         int i;
1694         glhanoi->disk = (Disk *) calloc(glhanoi->numberOfDisks, sizeof(Disk));
1695         checkAllocAndExit(!!glhanoi->disk, "disks");
1696
1697         for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1698                 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1699                 double f = cfunc((GLfloat) i / (GLfloat) glhanoi->numberOfDisks);
1700                 GLfloat diskColor = f * 360.0;
1701                 GLfloat color[3];
1702                 Disk *disk = &glhanoi->disk[i];
1703
1704                 disk->id = i;
1705                 disk->position[0] = glhanoi->pole[0].position[0]; /* -glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5; */
1706                 disk->position[1] = glhanoi->diskHeight * height;
1707                 disk->position[2] = glhanoi->pole[0].position[2];
1708                 disk->rotation[0] = 0.0;
1709                 disk->rotation[1] = 0.0;
1710                 disk->rotation[2] = 0.0;
1711                 disk->polys = 0;
1712
1713                 /* make smaller disks move faster */
1714                 disk->speed = lerp(((double)glhanoi->numberOfDisks - i) / glhanoi->numberOfDisks,
1715                         1.0, glhanoi->speed);
1716                 /* fprintf(stderr, "disk id: %d, alpha: %0.2f, speed: %0.2f\n", disk->id,
1717                         ((double)(glhanoi->maxDiskIdx - i)) / glhanoi->numberOfDisks, disk->speed); */
1718
1719                 color[0] = diskColor;
1720                 color[1] = 1.0f;
1721                 color[2] = 1.0f;
1722                 HSVtoRGBv(color, color);
1723
1724                 checkAllocAndExit(!!(disk->displayList = glGenLists(1)), "disk display list");
1725                 glNewList(disk->displayList, GL_COMPILE);
1726                 setMaterial(color, cWhite, 100.0);
1727                 disk->polys += drawDisk3D(glhanoi->poleRadius,
1728                                   getDiskRadius(glhanoi, i),
1729                                   glhanoi->diskHeight);
1730                 /*fprintf(stderr, "Debug: disk %d has radius %f\n", i,
1731                         getDiskRadius(glhanoi, i)); */
1732                 glEndList();
1733         }
1734         for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
1735                 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1736                 int h = glhanoi->maxDiskIdx - i;
1737                 glhanoi->diskPos[h] = glhanoi->diskHeight * height;
1738                 push(glhanoi, glhanoi->src, &glhanoi->disk[i]);
1739         }
1740 }
1741
1742 static void initLights(Bool state)
1743 {
1744         if(state) {
1745                 glLightfv(GL_LIGHT0, GL_POSITION, pos0);
1746                 glLightfv(GL_LIGHT0, GL_AMBIENT, amb0);
1747                 glLightfv(GL_LIGHT0, GL_DIFFUSE, dif0);
1748                 glLightfv(GL_LIGHT0, GL_SPECULAR, spc0);
1749
1750                 glLightfv(GL_LIGHT1, GL_POSITION, pos1);
1751                 glLightfv(GL_LIGHT1, GL_AMBIENT, amb1);
1752                 glLightfv(GL_LIGHT1, GL_DIFFUSE, dif1);
1753                 glLightfv(GL_LIGHT1, GL_SPECULAR, spc1);
1754
1755                 glEnable(GL_LIGHTING);
1756                 glEnable(GL_LIGHT0);
1757                 glEnable(GL_LIGHT1);
1758         } else {
1759                 glDisable(GL_LIGHTING);
1760         }
1761 }
1762
1763 static int drawFloor(glhcfg *glhanoi)
1764 {
1765         glCallList(glhanoi->floorList);
1766     return glhanoi->floorpolys;
1767 }
1768
1769 static int drawTowers(glhcfg *glhanoi)
1770 {
1771         glCallList(glhanoi->baseList);
1772         glCallList(glhanoi->poleList);
1773     return glhanoi->basepolys + glhanoi->polepolys;
1774 }
1775
1776 static int drawTrails1(glhcfg *glhanoi, double t, double thickness, double alpha) {
1777         int i, prev = -1, lines = 0;
1778         Bool fresh = False;
1779         GLfloat trailDurInv = 1.0f / glhanoi->trailDuration;
1780
1781         glLineWidth(thickness);
1782
1783         glBegin(GL_LINES);
1784
1785         for (i = glhanoi->trailQFront;
1786                         i != glhanoi->trailQBack;
1787                         i = normalizeQ(i + 1)) {
1788                 TrailPoint *tqi = &(glhanoi->trailQ[i]);
1789
1790                 if (!fresh && t > tqi->endTime) {
1791                         glhanoi->trailQFront = normalizeQ(i + 1);
1792                 } else {
1793                         if (tqi->startTime > t) break;
1794                         /* Found trails that haven't timed out. */
1795                         if (!fresh) fresh = True;
1796                         if (prev > -1) {
1797                                 /* Fade to invisible with age */
1798                                 trailColor[3] = alpha * (tqi->endTime - t) * trailDurInv;
1799                                 /* Can't use setMaterial(trailColor, cBlack, 0) because our color needs an alpha value. */
1800                                 glColor4fv(trailColor);
1801                                 glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, trailColor);
1802                                 /* FUTURE: to really do this right, trails should be drawn in back-to-front
1803                                         order, so that blending is done correctly.
1804                                         Currently it looks poor when a faded trail is in front of, or coincident with,
1805                                         a bright trail but is drawn first.
1806                                         I think for now it's good enough to recommend shorter trails so they
1807                                         never/rarely overlap.
1808                                         A jitter per trail arc would also mitigate this problem, to a lesser degree. */
1809                                 glVertex3fv(glhanoi->trailQ[prev].position);
1810                                 glVertex3fv(glhanoi->trailQ[i].position);
1811                                 lines++;
1812                         }
1813                         if (glhanoi->trailQ[i].isEnd)
1814                                 prev = -1;
1815                         else
1816                                 prev = i;
1817                 }
1818         }
1819
1820         glEnd();
1821
1822         return lines;
1823 }
1824
1825 static int drawTrails(glhcfg *glhanoi) {
1826         int lines = 0;
1827         double t = getTime();
1828
1829         glEnable (GL_BLEND);
1830         glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1831         glMaterialfv(GL_FRONT, GL_SPECULAR, cBlack);
1832         glMateriali(GL_FRONT, GL_SHININESS, 0);
1833
1834         /* Draw them twice, with different widths and opacities, to make them smoother. */
1835         lines = drawTrails1(glhanoi, t, 1.0, 0.75);
1836         lines += drawTrails1(glhanoi, t, 2.5, 0.5);
1837
1838         glDisable (GL_BLEND);
1839
1840         /* fprintf(stderr, "Drew trails: %d lines\n", lines); */
1841         return lines;
1842 }
1843
1844 /* Window management, etc
1845  */
1846 ENTRYPOINT void reshape_glhanoi(ModeInfo * mi, int width, int height)
1847 {
1848         glViewport(0, 0, (GLint) width, (GLint) height);
1849
1850         glMatrixMode(GL_PROJECTION);
1851         glLoadIdentity();
1852         gluPerspective(30.0, (GLdouble) width / (GLdouble) height, 1.0,
1853                                    2 * MAX_CAMERA_RADIUS);
1854
1855         glMatrixMode(GL_MODELVIEW);
1856         glLoadIdentity();
1857
1858         glClear(GL_COLOR_BUFFER_BIT);
1859 }
1860
1861 ENTRYPOINT void init_glhanoi(ModeInfo * mi)
1862 {
1863         glhcfg *glhanoi;
1864         if(!glhanoi_cfg) {
1865                 glhanoi_cfg =
1866                         (glhcfg *) calloc(MI_NUM_SCREENS(mi), sizeof(glhcfg));
1867                 checkAllocAndExit(!!glhanoi_cfg, "configuration");
1868         }
1869
1870         glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1871         glhanoi->glx_context = init_GL(mi);
1872         glhanoi->numberOfDisks = MI_BATCHCOUNT(mi);
1873
1874     if (glhanoi->numberOfDisks <= 1)
1875       glhanoi->numberOfDisks = 3 + (int) BELLRAND(9);
1876
1877         /* magicnumber is a bitfield, so we can't have more than 31 discs
1878            on a system with 4-byte ints. */
1879         if (glhanoi->numberOfDisks >= 8 * sizeof(int))
1880                 glhanoi->numberOfDisks = (8 * sizeof(int)) - 1;
1881
1882         glhanoi->maxDiskIdx = glhanoi->numberOfDisks - 1;
1883
1884         glhanoi->numberOfPoles = get_integer_resource(MI_DISPLAY(mi), "poles", "Integer");
1885         /* Set a number of poles from 3 to numberOfDisks + 1, biased toward lower values,
1886                 with probability decreasing linearly. */
1887     if (glhanoi->numberOfPoles <= 2)
1888       glhanoi->numberOfPoles = 3 +
1889                 (int)((1 - sqrt(frand(1.0))) * (glhanoi->numberOfDisks - 1));
1890
1891         glhanoi->wire = MI_IS_WIREFRAME(mi);
1892
1893 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
1894     glhanoi->wire = 0;
1895 # endif
1896
1897         glhanoi->light = light;
1898         glhanoi->fog = fog;
1899         glhanoi->texture = texture;
1900         glhanoi->speed = speed;
1901         glhanoi->trailDuration = trails;
1902         /* set trailQSize based on 60 fps (a maximum, more or less) */
1903         /* FUTURE: Should clamp framerate to 60 fps? See flurry.c's draw_flurry().
1904                 The only bad effect if we don't is that trail-ends could
1905                 show "unnatural" pauses at high fps. */
1906         glhanoi->trailQSize = (int)(trails * 60.0);
1907
1908         reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
1909
1910         if(glhanoi->wire) {
1911                 glhanoi->light = False;
1912                 glhanoi->fog = False;
1913                 glhanoi->texture = False;
1914         }
1915
1916         initLights(!glhanoi->wire && glhanoi->light);
1917         checkAllocAndExit(!makeTextures(glhanoi), "textures\n");
1918
1919         /* Choose linear or circular layout. Could make this a user option. */
1920         glhanoi->layoutLinear = (glhanoi->numberOfPoles == 3);
1921
1922         initData(glhanoi);
1923         initView(glhanoi);
1924         initFloor(glhanoi);
1925         initBase(glhanoi);
1926         initTowers(glhanoi);
1927         initDisks(glhanoi);
1928
1929         glEnable(GL_DEPTH_TEST);
1930         glEnable(GL_NORMALIZE);
1931         glEnable(GL_CULL_FACE);
1932         glShadeModel(GL_SMOOTH);
1933         if(glhanoi->fog) {
1934                 glClearColor(fogcolor[0], fogcolor[1], fogcolor[2], 1.0);
1935                 glFogi(GL_FOG_MODE, GL_LINEAR);
1936                 glFogfv(GL_FOG_COLOR, fogcolor);
1937                 glFogf(GL_FOG_DENSITY, 0.35f);
1938                 glHint(GL_FOG_HINT, GL_NICEST);
1939                 glFogf(GL_FOG_START, MIN_CAMERA_RADIUS);
1940                 glFogf(GL_FOG_END, MAX_CAMERA_RADIUS / 1.9);
1941                 glEnable(GL_FOG);
1942         }
1943
1944         glhanoi->duration = START_DURATION;
1945         changeState(glhanoi, START);
1946 }
1947
1948 ENTRYPOINT void draw_glhanoi(ModeInfo * mi)
1949 {
1950         glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1951         Display *dpy = MI_DISPLAY(mi);
1952         Window window = MI_WINDOW(mi);
1953
1954         if(!glhanoi->glx_context)
1955                 return;
1956
1957     glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context));
1958
1959         glPolygonMode(GL_FRONT, glhanoi->wire ? GL_LINE : GL_FILL);
1960
1961         glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1962     mi->polygon_count = 0;
1963
1964         glLoadIdentity();
1965     glRotatef(current_device_rotation(), 0, 0, 1);
1966
1967         update_glhanoi(glhanoi);
1968         updateView(glhanoi);
1969
1970 # ifdef HAVE_MOBILE     /* Keep it the same relative size when rotated. */
1971     {
1972       GLfloat h = MI_HEIGHT(mi) / (GLfloat) MI_WIDTH(mi);
1973       int o = (int) current_device_rotation();
1974       if (o != 0 && o != 180 && o != -180)
1975         glScalef (1/h, 1/h, 1/h);
1976     }
1977 # endif
1978
1979         if(!glhanoi->wire && glhanoi->texture) {
1980                 glEnable(GL_TEXTURE_2D);
1981         }
1982     mi->polygon_count += drawFloor(glhanoi);
1983         glDisable(GL_TEXTURE_2D);
1984
1985         mi->polygon_count += drawTowers(glhanoi);
1986         mi->polygon_count += drawDisks(glhanoi);
1987
1988         if (glhanoi->trailQSize) {
1989                 /* No polygons, just lines. So ignore the return count. */
1990                 (void)drawTrails(glhanoi);
1991         }
1992
1993         if(mi->fps_p) {
1994                 do_fps(mi);
1995         }
1996         glFinish();
1997
1998         glXSwapBuffers(dpy, window);
1999 }
2000
2001 ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event)
2002 {
2003         glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
2004
2005     /* #### this is all wrong on iOS -- should be using gltrackball. */
2006
2007         if(event->xany.type == ButtonPress && event->xbutton.button == Button1) {
2008                 glhanoi->button_down_p = True;
2009                 glhanoi->drag_x = event->xbutton.x;
2010                 glhanoi->drag_y = event->xbutton.y;
2011                 return True;
2012         } else if(event->xany.type == ButtonRelease
2013                           && event->xbutton.button == Button1) {
2014                 glhanoi->button_down_p = False;
2015                 return True;
2016         } else if(event->xany.type == ButtonPress &&
2017                           (event->xbutton.button == Button4
2018                            || event->xbutton.button == Button5)) {
2019                 switch (event->xbutton.button) {
2020                 case Button4:
2021                         glhanoi->camera[2] += 0.01;
2022                         break;
2023                 case Button5:
2024                         glhanoi->camera[2] -= 0.01;
2025                         break;
2026                 default:
2027                         fprintf(stderr,
2028                                         "glhanoi: unknown button in mousewheel handler\n");
2029                 }
2030                 return True;
2031         } else if(event->xany.type == MotionNotify
2032                           && glhanoi_cfg->button_down_p) {
2033                 int x_diff, y_diff;
2034
2035                 x_diff = event->xbutton.x - glhanoi->drag_x;
2036                 y_diff = event->xbutton.y - glhanoi->drag_y;
2037
2038                 glhanoi->camera[0] = (float)x_diff / (float)MI_WIDTH(mi);
2039                 glhanoi->camera[1] = (float)y_diff / (float)MI_HEIGHT(mi);
2040
2041                 return True;
2042         }
2043 #if 0 /* #### doesn't work */
2044   else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
2045     {
2046       changeState(glhanoi, START);
2047       return True;
2048     }
2049 #endif
2050         return False;
2051 }
2052
2053 ENTRYPOINT void release_glhanoi(ModeInfo * mi)
2054 {
2055         if(glhanoi_cfg != NULL) {
2056                 int screen;
2057                 for(screen = 0; screen < MI_NUM_SCREENS(mi); screen++) {
2058                         int i;
2059                         int j;
2060                         glhcfg *glh = &glhanoi_cfg[screen];
2061                         glDeleteLists(glh->floorList, 1);
2062                         glDeleteLists(glh->baseList, 1);
2063                         glDeleteLists(glh->poleList, 1);
2064                         glDeleteLists(glh->textureNames[0], 2);
2065                         for(j = 0; j < glh->numberOfDisks; ++j) {
2066                                 glDeleteLists(glh->disk[j].displayList, 1);
2067                         }
2068                         free(glh->disk);
2069                         for(i = 0; i < glh->numberOfPoles; i++) {
2070                                 if(glh->pole[i].data != NULL) {
2071                                         free(glh->pole[i].data);
2072                                 }
2073                         }
2074                 }
2075         }
2076         free(glhanoi_cfg);
2077         glhanoi_cfg = NULL;
2078 }
2079
2080 XSCREENSAVER_MODULE ("GLHanoi", glhanoi)
2081
2082 #endif                                                  /* USE_GL */