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         glEndList();
1670 }
1671
1672 /* Parameterized hue based on input 0.0 - 1.0. */
1673 static double cfunc(double x)
1674 {
1675 #define COMP <
1676         if(x < 2.0 / 7.0) {
1677                 return (1.0 / 12.0) / (1.0 / 7.0) * x;
1678         }
1679         if(x < 3.0 / 7.0) {
1680                 /* (7x - 1) / 6 */
1681                 return (1.0 + 1.0 / 6.0) * x - 1.0 / 6.0;
1682         }
1683         if(x < 4.0 / 7.0) {
1684                 return (2.0 + 1.0 / 3.0) * x - 2.0 / 3.0;
1685         }
1686         if(x < 5.0 / 7.0) {
1687                 return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1688         }
1689         return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1690 }
1691
1692 static void initDisks(glhcfg *glhanoi)
1693 {
1694         int i;
1695         glhanoi->disk = (Disk *) calloc(glhanoi->numberOfDisks, sizeof(Disk));
1696         checkAllocAndExit(!!glhanoi->disk, "disks");
1697
1698         for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1699                 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1700                 double f = cfunc((GLfloat) i / (GLfloat) glhanoi->numberOfDisks);
1701                 GLfloat diskColor = f * 360.0;
1702                 GLfloat color[3];
1703                 Disk *disk = &glhanoi->disk[i];
1704
1705                 disk->id = i;
1706                 disk->position[0] = glhanoi->pole[0].position[0]; /* -glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5; */
1707                 disk->position[1] = glhanoi->diskHeight * height;
1708                 disk->position[2] = glhanoi->pole[0].position[2];
1709                 disk->rotation[0] = 0.0;
1710                 disk->rotation[1] = 0.0;
1711                 disk->rotation[2] = 0.0;
1712                 disk->polys = 0;
1713
1714                 /* make smaller disks move faster */
1715                 disk->speed = lerp(((double)glhanoi->numberOfDisks - i) / glhanoi->numberOfDisks,
1716                         1.0, glhanoi->speed);
1717                 /* fprintf(stderr, "disk id: %d, alpha: %0.2f, speed: %0.2f\n", disk->id,
1718                         ((double)(glhanoi->maxDiskIdx - i)) / glhanoi->numberOfDisks, disk->speed); */
1719
1720                 color[0] = diskColor;
1721                 color[1] = 1.0f;
1722                 color[2] = 1.0f;
1723                 HSVtoRGBv(color, color);
1724
1725                 checkAllocAndExit(!!(disk->displayList = glGenLists(1)), "disk display list");
1726                 glNewList(disk->displayList, GL_COMPILE);
1727                 setMaterial(color, cWhite, 100.0);
1728                 disk->polys += drawDisk3D(glhanoi->poleRadius,
1729                                   getDiskRadius(glhanoi, i),
1730                                   glhanoi->diskHeight);
1731                 /*fprintf(stderr, "Debug: disk %d has radius %f\n", i,
1732                         getDiskRadius(glhanoi, i)); */
1733                 glEndList();
1734         }
1735         for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
1736                 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1737                 int h = glhanoi->maxDiskIdx - i;
1738                 glhanoi->diskPos[h] = glhanoi->diskHeight * height;
1739                 push(glhanoi, glhanoi->src, &glhanoi->disk[i]);
1740         }
1741 }
1742
1743 static void initLights(Bool state)
1744 {
1745         if(state) {
1746                 glLightfv(GL_LIGHT0, GL_POSITION, pos0);
1747                 glLightfv(GL_LIGHT0, GL_AMBIENT, amb0);
1748                 glLightfv(GL_LIGHT0, GL_DIFFUSE, dif0);
1749                 glLightfv(GL_LIGHT0, GL_SPECULAR, spc0);
1750
1751                 glLightfv(GL_LIGHT1, GL_POSITION, pos1);
1752                 glLightfv(GL_LIGHT1, GL_AMBIENT, amb1);
1753                 glLightfv(GL_LIGHT1, GL_DIFFUSE, dif1);
1754                 glLightfv(GL_LIGHT1, GL_SPECULAR, spc1);
1755
1756                 glEnable(GL_LIGHTING);
1757                 glEnable(GL_LIGHT0);
1758                 glEnable(GL_LIGHT1);
1759         } else {
1760                 glDisable(GL_LIGHTING);
1761         }
1762 }
1763
1764 static int drawFloor(glhcfg *glhanoi)
1765 {
1766         glCallList(glhanoi->floorList);
1767     return glhanoi->floorpolys;
1768 }
1769
1770 static int drawTowers(glhcfg *glhanoi)
1771 {
1772         glCallList(glhanoi->baseList);
1773         glCallList(glhanoi->poleList);
1774     return glhanoi->basepolys + glhanoi->polepolys;
1775 }
1776
1777 static int drawTrails1(glhcfg *glhanoi, double t, double thickness, double alpha) {
1778         int i, prev = -1, lines = 0;
1779         Bool fresh = False;
1780         GLfloat trailDurInv = 1.0f / glhanoi->trailDuration;
1781
1782         glLineWidth(thickness);
1783
1784         glBegin(GL_LINES);
1785
1786         for (i = glhanoi->trailQFront;
1787                         i != glhanoi->trailQBack;
1788                         i = normalizeQ(i + 1)) {
1789                 TrailPoint *tqi = &(glhanoi->trailQ[i]);
1790
1791                 if (!fresh && t > tqi->endTime) {
1792                         glhanoi->trailQFront = normalizeQ(i + 1);
1793                 } else {
1794                         if (tqi->startTime > t) break;
1795                         /* Found trails that haven't timed out. */
1796                         if (!fresh) fresh = True;
1797                         if (prev > -1) {
1798                                 /* Fade to invisible with age */
1799                                 trailColor[3] = alpha * (tqi->endTime - t) * trailDurInv;
1800                                 /* Can't use setMaterial(trailColor, cBlack, 0) because our color needs an alpha value. */
1801                                 glColor4fv(trailColor);
1802                                 glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, trailColor);
1803                                 /* FUTURE: to really do this right, trails should be drawn in back-to-front
1804                                         order, so that blending is done correctly.
1805                                         Currently it looks poor when a faded trail is in front of, or coincident with,
1806                                         a bright trail but is drawn first.
1807                                         I think for now it's good enough to recommend shorter trails so they
1808                                         never/rarely overlap.
1809                                         A jitter per trail arc would also mitigate this problem, to a lesser degree. */
1810                                 glVertex3fv(glhanoi->trailQ[prev].position);
1811                                 glVertex3fv(glhanoi->trailQ[i].position);
1812                                 lines++;
1813                         }
1814                         if (glhanoi->trailQ[i].isEnd)
1815                                 prev = -1;
1816                         else
1817                                 prev = i;
1818                 }
1819         }
1820
1821         glEnd();
1822
1823         return lines;
1824 }
1825
1826 static int drawTrails(glhcfg *glhanoi) {
1827         int lines = 0;
1828         double t = getTime();
1829
1830         glEnable (GL_BLEND);
1831         glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1832         glMaterialfv(GL_FRONT, GL_SPECULAR, cBlack);
1833         glMateriali(GL_FRONT, GL_SHININESS, 0);
1834
1835         /* Draw them twice, with different widths and opacities, to make them smoother. */
1836         lines = drawTrails1(glhanoi, t, 1.0, 0.75);
1837         lines += drawTrails1(glhanoi, t, 2.5, 0.5);
1838
1839         glDisable (GL_BLEND);
1840
1841         /* fprintf(stderr, "Drew trails: %d lines\n", lines); */
1842         return lines;
1843 }
1844
1845 /* Window management, etc
1846  */
1847 ENTRYPOINT void reshape_glhanoi(ModeInfo * mi, int width, int height)
1848 {
1849         glViewport(0, 0, (GLint) width, (GLint) height);
1850
1851         glMatrixMode(GL_PROJECTION);
1852         glLoadIdentity();
1853         gluPerspective(30.0, (GLdouble) width / (GLdouble) height, 1.0,
1854                                    2 * MAX_CAMERA_RADIUS);
1855
1856         glMatrixMode(GL_MODELVIEW);
1857         glLoadIdentity();
1858
1859         glClear(GL_COLOR_BUFFER_BIT);
1860 }
1861
1862 ENTRYPOINT void init_glhanoi(ModeInfo * mi)
1863 {
1864         glhcfg *glhanoi;
1865         if(!glhanoi_cfg) {
1866                 glhanoi_cfg =
1867                         (glhcfg *) calloc(MI_NUM_SCREENS(mi), sizeof(glhcfg));
1868                 checkAllocAndExit(!!glhanoi_cfg, "configuration");
1869         }
1870
1871         glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1872         glhanoi->glx_context = init_GL(mi);
1873         glhanoi->numberOfDisks = MI_BATCHCOUNT(mi);
1874
1875     if (glhanoi->numberOfDisks <= 1)
1876       glhanoi->numberOfDisks = 3 + (int) BELLRAND(9);
1877
1878         /* magicnumber is a bitfield, so we can't have more than 31 discs
1879            on a system with 4-byte ints. */
1880         if (glhanoi->numberOfDisks >= 8 * sizeof(int))
1881                 glhanoi->numberOfDisks = (8 * sizeof(int)) - 1;
1882
1883         glhanoi->maxDiskIdx = glhanoi->numberOfDisks - 1;
1884
1885         glhanoi->numberOfPoles = get_integer_resource(MI_DISPLAY(mi), "poles", "Integer");
1886         /* Set a number of poles from 3 to numberOfDisks + 1, biased toward lower values,
1887                 with probability decreasing linearly. */
1888     if (glhanoi->numberOfPoles <= 2)
1889       glhanoi->numberOfPoles = 3 +
1890                 (int)((1 - sqrt(frand(1.0))) * (glhanoi->numberOfDisks - 1));
1891
1892         glhanoi->wire = MI_IS_WIREFRAME(mi);
1893
1894 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
1895     glhanoi->wire = 0;
1896 # endif
1897
1898         glhanoi->light = light;
1899         glhanoi->fog = fog;
1900         glhanoi->texture = texture;
1901         glhanoi->speed = speed;
1902         glhanoi->trailDuration = trails;
1903         /* set trailQSize based on 60 fps (a maximum, more or less) */
1904         /* FUTURE: Should clamp framerate to 60 fps? See flurry.c's draw_flurry().
1905                 The only bad effect if we don't is that trail-ends could
1906                 show "unnatural" pauses at high fps. */
1907         glhanoi->trailQSize = (int)(trails * 60.0);
1908
1909         reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
1910
1911         if(glhanoi->wire) {
1912                 glhanoi->light = False;
1913                 glhanoi->fog = False;
1914                 glhanoi->texture = False;
1915         }
1916
1917         initLights(!glhanoi->wire && glhanoi->light);
1918         checkAllocAndExit(!makeTextures(glhanoi), "textures\n");
1919
1920         /* Choose linear or circular layout. Could make this a user option. */
1921         glhanoi->layoutLinear = (glhanoi->numberOfPoles == 3);
1922
1923         initData(glhanoi);
1924         initView(glhanoi);
1925         initFloor(glhanoi);
1926         initBase(glhanoi);
1927         initTowers(glhanoi);
1928         initDisks(glhanoi);
1929
1930         glEnable(GL_DEPTH_TEST);
1931         glEnable(GL_NORMALIZE);
1932         glEnable(GL_CULL_FACE);
1933         glShadeModel(GL_SMOOTH);
1934         if(glhanoi->fog) {
1935                 glClearColor(fogcolor[0], fogcolor[1], fogcolor[2], 1.0);
1936                 glFogi(GL_FOG_MODE, GL_LINEAR);
1937                 glFogfv(GL_FOG_COLOR, fogcolor);
1938                 glFogf(GL_FOG_DENSITY, 0.35f);
1939                 glHint(GL_FOG_HINT, GL_NICEST);
1940                 glFogf(GL_FOG_START, MIN_CAMERA_RADIUS);
1941                 glFogf(GL_FOG_END, MAX_CAMERA_RADIUS / 1.9);
1942                 glEnable(GL_FOG);
1943         }
1944
1945         glhanoi->duration = START_DURATION;
1946         changeState(glhanoi, START);
1947 }
1948
1949 ENTRYPOINT void draw_glhanoi(ModeInfo * mi)
1950 {
1951         glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1952         Display *dpy = MI_DISPLAY(mi);
1953         Window window = MI_WINDOW(mi);
1954
1955         if(!glhanoi->glx_context)
1956                 return;
1957
1958     glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context));
1959
1960         glPolygonMode(GL_FRONT, glhanoi->wire ? GL_LINE : GL_FILL);
1961
1962         glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1963     mi->polygon_count = 0;
1964
1965         glLoadIdentity();
1966     glRotatef(current_device_rotation(), 0, 0, 1);
1967
1968         update_glhanoi(glhanoi);
1969         updateView(glhanoi);
1970
1971         if(!glhanoi->wire && glhanoi->texture) {
1972                 glEnable(GL_TEXTURE_2D);
1973         }
1974     mi->polygon_count += drawFloor(glhanoi);
1975         glDisable(GL_TEXTURE_2D);
1976
1977         mi->polygon_count += drawTowers(glhanoi);
1978         mi->polygon_count += drawDisks(glhanoi);
1979
1980         if (glhanoi->trailQSize) {
1981                 /* No polygons, just lines. So ignore the return count. */
1982                 (void)drawTrails(glhanoi);
1983         }
1984
1985         if(mi->fps_p) {
1986                 do_fps(mi);
1987         }
1988         glFinish();
1989
1990         glXSwapBuffers(dpy, window);
1991 }
1992
1993 ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event)
1994 {
1995         glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1996
1997         if(event->xany.type == ButtonPress && event->xbutton.button == Button1) {
1998                 glhanoi->button_down_p = True;
1999                 glhanoi->drag_x = event->xbutton.x;
2000                 glhanoi->drag_y = event->xbutton.y;
2001                 return True;
2002         } else if(event->xany.type == ButtonRelease
2003                           && event->xbutton.button == Button1) {
2004                 glhanoi->button_down_p = False;
2005                 return True;
2006         } else if(event->xany.type == ButtonPress &&
2007                           (event->xbutton.button == Button4
2008                            || event->xbutton.button == Button5)) {
2009                 switch (event->xbutton.button) {
2010                 case Button4:
2011                         glhanoi->camera[2] += 0.01;
2012                         break;
2013                 case Button5:
2014                         glhanoi->camera[2] -= 0.01;
2015                         break;
2016                 default:
2017                         fprintf(stderr,
2018                                         "glhanoi: unknown button in mousewheel handler\n");
2019                 }
2020                 return True;
2021         } else if(event->xany.type == MotionNotify
2022                           && glhanoi_cfg->button_down_p) {
2023                 int x_diff, y_diff;
2024
2025                 x_diff = event->xbutton.x - glhanoi->drag_x;
2026                 y_diff = event->xbutton.y - glhanoi->drag_y;
2027
2028                 glhanoi->camera[0] = (float)x_diff / (float)MI_WIDTH(mi);
2029                 glhanoi->camera[1] = (float)y_diff / (float)MI_HEIGHT(mi);
2030
2031                 return True;
2032         }
2033 #if 0 /* #### doesn't work */
2034   else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
2035     {
2036       changeState(glhanoi, START);
2037       return True;
2038     }
2039 #endif
2040         return False;
2041 }
2042
2043 ENTRYPOINT void release_glhanoi(ModeInfo * mi)
2044 {
2045         if(glhanoi_cfg != NULL) {
2046                 int screen;
2047                 for(screen = 0; screen < MI_NUM_SCREENS(mi); screen++) {
2048                         int i;
2049                         int j;
2050                         glhcfg *glh = &glhanoi_cfg[screen];
2051                         glDeleteLists(glh->floorList, 1);
2052                         glDeleteLists(glh->baseList, 1);
2053                         glDeleteLists(glh->poleList, 1);
2054                         glDeleteLists(glh->textureNames[0], 2);
2055                         for(j = 0; j < glh->numberOfDisks; ++j) {
2056                                 glDeleteLists(glh->disk[j].displayList, 1);
2057                         }
2058                         free(glh->disk);
2059                         for(i = 0; i < glh->numberOfPoles; i++) {
2060                                 if(glh->pole[i].data != NULL) {
2061                                         free(glh->pole[i].data);
2062                                 }
2063                         }
2064                 }
2065         }
2066         free(glhanoi_cfg);
2067         glhanoi_cfg = NULL;
2068 }
2069
2070 XSCREENSAVER_MODULE ("GLHanoi", glhanoi)
2071
2072 #endif                                                  /* USE_GL */