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 # define release_glhanoi 0
  33
  34 /* polygon resolution of poles and disks */
  35 #define NSLICE 32
  36 #define NLOOPS 1
  37
  38 /* How long to wait at start and finish (seconds). */
  39 #define START_DURATION 1.0
  40 #define FINISH_DURATION 1.0
  41 #define BASE_LENGTH 30.0
  42 #define BOARD_SQUARES 8
  43
  44 /* Don't draw trail lines till they're this old (sec).
  45         Helps trails not be "attached" to the disks. */
  46 #define TRAIL_START_DELAY 0.1
  47
  48 #define MAX_CAMERA_RADIUS 250.0
  49 #define MIN_CAMERA_RADIUS 75.0
  50
  51 #define MARBLE_SCALE 1.01
  52
  53 #undef BELLRAND
  54 /* Return a double precision number in [0...n], with bell curve distribution. */
  55 #define BELLRAND(n) ((frand((n)) + frand((n)) + frand((n))) / 3)
  56
  57 enum {
  58         MARBLE_TEXURE,
  59         N_TEXTURES
  60 };
  61
  62 #define MARBLE_TEXTURE_SIZE 256
  63
  64 #undef countof
  65 #define countof(x) (sizeof((x))/sizeof((*x)))
  66
  67 #include <math.h>
  68 #include "xlockmore.h"
  69
  70 #ifdef USE_GL                                   /* whole file */
  71
  72 typedef struct timeval glhtime;
  73
  74 static double getTime(void)
  75 {
  76         struct timeval t;
  77 #ifdef GETTIMEOFDAY_TWO_ARGS
  78         gettimeofday(&t, NULL);
  79 #else                                                   /* !GETTIMEOFDAY_TWO_ARGS */
  80         gettimeofday(&t);
  81 #endif                                                  /* !GETTIMEOFDAY_TWO_ARGS */
  82         return t.tv_sec + t.tv_usec / 1000000.0;
  83 }
  84
  85 typedef enum {
  86         START,
  87         MOVE_DISK,
  88         MOVE_FINISHED,
  89         FINISHED,
  90         MONEY_SHOT,
  91         INVALID = -1
  92 } State;
  93
  94 typedef struct {
  95         int id;
  96         GLuint displayList;
  97         GLfloat position[3];
  98         GLfloat rotation[3];
  99         GLfloat color[4];
 100         GLfloat base0;
 101         GLfloat base1;
 102         GLfloat height;
 103         GLfloat xmin, xmax, ymin, zmin, zmax;
 104         GLfloat u1, u2;
 105         GLfloat t1, t2;
 106         GLfloat ucostheta, usintheta;
 107         GLfloat dx, dz;
 108         GLdouble rotAngle; /* degree of "flipping" so far, during travel */
 109         GLdouble phi; /* angle of motion in xz plane */
 110         GLfloat speed;
 111     int polys;
 112 } Disk;
 113
 114 typedef struct {
 115         Disk **data;
 116         int count;
 117         int size;
 118         GLfloat position[3];
 119 } Pole;
 120
 121 /* A SubProblem is a recursive subdivision of the problem, and means
 122   "Move nDisks disks from src pole to dst pole, using the poles indicated in 'available'." */
 123 typedef struct {
 124         int nDisks;
 125         int src, dst;
 126         unsigned long available; /* a bitmask of poles that have no smaller disks on them */
 127 } SubProblem;
 128
 129 typedef struct {
 130         GLfloat position[3];
 131         double startTime, endTime;
 132         Bool isEnd;
 133 } TrailPoint;
 134
 135 typedef struct {
 136         GLXContext *glx_context;
 137         State state;
 138         Bool wire;
 139         Bool fog;
 140         Bool light;
 141         Bool layoutLinear;
 142         GLfloat trailDuration;
 143         double startTime;
 144         double lastTime;
 145         double duration;
 146         int numberOfDisks;
 147         int numberOfPoles;
 148         int numberOfMoves;
 149         int maxDiskIdx;
 150         int magicNumber;
 151         Disk *currentDisk;
 152         int move;
 153         /* src, tmp, dst: index of pole that is source / storage / destination for
 154                 current move */
 155         int src;
 156         int tmp;
 157         int dst;
 158         int oldsrc;
 159         int oldtmp;
 160         int olddst;
 161         GLfloat speed; /* coefficient for how fast the disks move */
 162         SubProblem *solveStack;
 163         int solveStackSize, solveStackIdx;
 164         Pole *pole;
 165         float boardSize;
 166         float baseLength;
 167         float baseWidth;
 168         float baseHeight;
 169         float poleRadius;
 170         float poleHeight;
 171         float poleOffset;
 172         float poleDist; /* distance of poles from center, for round layout */
 173         float diskHeight;
 174         float maxDiskRadius;
 175         float *diskPos;                         /* pre-computed disk positions on rods */
 176         Disk *disk;
 177         GLint floorList;
 178         GLint baseList;
 179         GLint poleList;
 180     int floorpolys, basepolys, polepolys;
 181         int trailQSize;
 182         TrailPoint *trailQ;
 183         int trailQFront, trailQBack;
 184         GLfloat camera[3];
 185         GLfloat centre[3];
 186         rotator *the_rotator;
 187         Bool button_down_p;
 188         Bool texture;
 189         GLuint textureNames[N_TEXTURES];
 190         int drag_x;
 191         int drag_y;
 192         int noise_initted;
 193         int p[512];
 194 } glhcfg;
 195
 196 static glhcfg *glhanoi_cfg = NULL;
 197 static Bool fog;
 198 static Bool light;
 199 static Bool texture;
 200 static GLfloat trails;
 201 static int poles;
 202 static GLfloat speed;
 203
 204 static XrmOptionDescRec opts[] = {
 205         {"-light", ".glhanoi.light", XrmoptionNoArg, "true"},
 206         {"+light", ".glhanoi.light", XrmoptionNoArg, "false"},
 207         {"-fog", ".glhanoi.fog", XrmoptionNoArg, "true"},
 208         {"+fog", ".glhanoi.fog", XrmoptionNoArg, "false"},
 209         {"-texture", ".glhanoi.texture", XrmoptionNoArg, "true"},
 210         {"+texture", ".glhanoi.texture", XrmoptionNoArg, "false"},
 211         {"-trails", ".glhanoi.trails", XrmoptionSepArg, 0},
 212         {"-poles", ".glhanoi.poles", XrmoptionSepArg, 0 },
 213         {"-speed", ".glhanoi.speed", XrmoptionSepArg, 0 }
 214 };
 215
 216 static argtype vars[] = {
 217         {&light, "light", "Light", DEF_LIGHT, t_Bool},
 218         {&fog, "fog", "Fog", DEF_FOG, t_Bool},
 219         {&texture, "texture", "Texture", DEF_TEXTURE, t_Bool},
 220         {&trails, "trails", "Trails", DEF_TRAILS, t_Float},
 221         {&poles, "poles", "Poles", DEF_POLES, t_Int},
 222         {&speed, "speed", "Speed", DEF_SPEED, t_Float}
 223 };
 224
 225 static OptionStruct desc[] = {
 226         {"+/-light", "whether to light the scene"},
 227         {"+/-fog", "whether to apply fog to the scene"},
 228         {"+/-texture", "whether to apply texture to the scene"},
 229         {"-trails t", "how long of disk trails to show (sec.)"},
 230         {"-poles r", "number of poles to move disks between"},
 231         {"-speed s", "speed multiplier"}
 232 };
 233
 234 ENTRYPOINT ModeSpecOpt glhanoi_opts = { countof(opts), opts, countof(vars), vars, desc };
 235
 236 #ifdef USE_MODULES
 237
 238 ModStruct glhanoi_description = {
 239         "glhanoi", "init_glhanoi", "draw_glhanoi", NULL,
 240         "draw_glhanoi", "init_glhanoi", NULL, &glhanoi_opts,
 241         1000, 1, 2, 1, 4, 1.0, "",
 242         "Towers of Hanoi", 0, NULL
 243 };
 244
 245 #endif
 246
 247 static const GLfloat cBlack[] = { 0.0, 0.0, 0.0, 1.0 };
 248 static const GLfloat cWhite[] = { 1.0, 1.0, 1.0, 1.0 };
 249 static const GLfloat poleColor[] = { 0.545, 0.137, 0.137 };
 250 static const GLfloat baseColor[] = { 0.34, 0.34, 0.48 };
 251 /* static const GLfloat baseColor[] = { 0.545, 0.137, 0.137 }; */
 252 static const GLfloat fogcolor[] = { 0.5, 0.5, 0.5 };
 253 static GLfloat trailColor[] = { 1.0, 1.0, 1.0, 0.5 };
 254
 255 static const float left[] = { 1.0, 0.0, 0.0 };
 256 static const float up[] = { 0.0, 1.0, 0.0 };
 257 static const float front[] = { 0.0, 0.0, 1.0 };
 258 static const float right[] = { -1.0, 0.0, 0.0 };
 259 static const float down[] = { 0.0, -1.0, 0.0 };
 260 static const float back[] = { 0.0, 0.0, -1.0 };
 261
 262 static const GLfloat pos0[4] = { 50.0, 50.0, 50.0, 0.0 };
 263 static const GLfloat amb0[4] = { 0.0, 0.0, 0.0, 1.0 };
 264 static const GLfloat dif0[4] = { 1.0, 1.0, 1.0, 1.0 };
 265 static const GLfloat spc0[4] = { 0.0, 1.0, 1.0, 1.0 };
 266
 267 static const GLfloat pos1[4] = { -50.0, 50.0, -50.0, 0.0 };
 268 static const GLfloat amb1[4] = { 0.0, 0.0, 0.0, 1.0 };
 269 static const GLfloat dif1[4] = { 1.0, 1.0, 1.0, 1.0 };
 270 static const GLfloat spc1[4] = { 1.0, 1.0, 1.0, 1.0 };
 271
 272 static float g = 3.0 * 9.80665;         /* hmm, looks like we need more gravity, Scotty... */
 273
 274 static void checkAllocAndExit(Bool item, char *descr) {
 275         if (!item) {
 276                 fprintf(stderr, "%s: unable to allocate memory for %s\n",
 277                                 progname, descr);
 278                 exit(EXIT_FAILURE);
 279         }
 280 }
 281
 282 #define DOPUSH(X, Y)    (((X)->count) >= ((X)->size)) ? NULL : ((X)->data[(X)->count++] = (Y))
 283 #define DOPOP(X)        (X)->count <= 0 ? NULL : ((X)->data[--((X)->count)])
 284
 285 /* push disk d onto pole idx */
 286 static Disk *push(glhcfg *glhanoi, int idx, Disk * d)
 287 {
 288         return DOPUSH(&glhanoi->pole[idx], d);
 289 }
 290
 291 /* pop the top disk from pole idx */
 292 static Disk *pop(glhcfg *glhanoi, int idx)
 293 {
 294         return DOPOP(&glhanoi->pole[idx]);
 295 }
 296
 297 static inline void swap(int *x, int *y)
 298 {
 299         *x = *x ^ *y;
 300         *y = *x ^ *y;
 301         *x = *x ^ *y;
 302 }
 303
 304 /*
 305  * magic - it's magic...
 306  *  Return 1 if the number of trailing zeroes on i is even, unless i is 1 or 0.
 307  */
 308 static int magic(int i)
 309 {
 310         int count = 0;
 311         if(i <= 1)
 312                 return 0;
 313         while((i & 0x01) == 0) {
 314                 i >>= 1;
 315                 count++;
 316         }
 317         return count % 2 == 0;
 318 }
 319
 320 static float distance(float *p0, float *p1)
 321 {
 322         float x, y, z;
 323         x = p1[0] - p0[0];
 324         y = p1[1] - p0[1];
 325         z = p1[2] - p0[2];
 326         return (float)sqrt(x * x + y * y + z * z);
 327 }
 328
 329 /* What is this for?
 330   = c / (a b - 0.25 (a^2 + 2 a b + b^2) )
 331   = c / (-0.25 (a^2 - 2 a b + b^2) )
 332   = c / (-0.25 ((a - b)(a - b)))
 333   = -4 c / (a - b)^2
 334 static GLfloat A(GLfloat a, GLfloat b, GLfloat c)
 335 {
 336         GLfloat sum = a + b;
 337         return c / (a * b - 0.25 * sum * sum);
 338 }
 339 */
 340
 341 static void moveSetup(glhcfg *glhanoi, Disk * disk)
 342 {
 343         float h, ymax;
 344         float u;
 345         int src = glhanoi->src;
 346         int dst = glhanoi->dst;
 347         GLfloat theta;
 348         GLfloat sintheta, costheta;
 349         double dh;
 350         double dx, dz; /* total x and z distances from src to dst */
 351         Pole *poleSrc, *poleDst;
 352
 353         poleSrc = &(glhanoi->pole[src]);
 354         poleDst = &(glhanoi->pole[dst]);
 355
 356         disk->xmin = poleSrc->position[0];
 357         /* glhanoi->poleOffset * (src - (glhanoi->numberOfPoles - 1.0f) * 0.5); */
 358         disk->xmax = poleDst->position[0];
 359         /* disk->xmax = glhanoi->poleOffset * (dst - (glhanoi->numberOfPoles - 1.0f) * 0.5); */
 360         disk->ymin = glhanoi->poleHeight;
 361         disk->zmin = poleSrc->position[2];
 362         disk->zmax = poleDst->position[2];
 363
 364         dx = disk->xmax - disk->xmin;
 365         dz = disk->zmax - disk->zmin;
 366
 367         if(glhanoi->state != FINISHED) {
 368                 double xxx = ((dx < 0) ? 180.0 : -180.0);
 369                 if(random() % 6 == 0) {
 370                         disk->rotAngle = xxx * (2 - 2 * random() % 2) * (random() % 3 + 1);
 371                 } else {
 372                         disk->rotAngle = xxx;
 373                 }
 374                 if(random() % 4 == 0) {
 375                         /* Backflip */
 376                         disk->rotAngle = -disk->rotAngle;
 377                 }
 378         } else {
 379                 disk->rotAngle = -180.0;
 380         }
 381
 382         disk->base0 = glhanoi->diskPos[poleSrc->count];
 383         disk->base1 = (glhanoi->state == FINISHED) ?
 384                 disk->base0 : glhanoi->diskPos[poleDst->count];
 385
 386         /* horizontal distance to travel? */
 387         /* was: absx = sqrt(disk->xmax - disk->xmin); */
 388         dh = distance(poleSrc->position, poleDst->position);
 389         /* absx = sqrt(dh); */
 390         ymax = glhanoi->poleHeight + dh;
 391         if(glhanoi->state == FINISHED) {
 392                 ymax += dh * (double)(glhanoi->numberOfDisks - disk->id);
 393         }
 394         h = ymax - disk->ymin;
 395         /* A(a, b, c) = -4 c / (a - b)^2 */
 396         /* theta = atan(4 h / (b - a)) */
 397         theta = atan(4 * h / dh);
 398         if(theta < 0.0)
 399                 theta += M_PI;
 400         costheta = cos(theta);
 401         sintheta = sin(theta);
 402         u = (float)
 403                 sqrt(fabs
 404                          (-g /
 405                           /* (2.0 * A(disk->xmin, disk->xmax, h) * costheta * costheta))); */
 406                           (2.0 * -4 * h / (dh * dh) * costheta * costheta)));
 407         disk->usintheta = u * sintheta;
 408         disk->ucostheta = u * costheta;
 409         /* Not to be confused: disk->dx is the per-time-unit portion of dx */
 410         disk->dx = disk->ucostheta * dx / dh;
 411         disk->dz = disk->ucostheta * dz / dh;
 412         disk->t1 =
 413                 (-u + sqrt(u * u + 2.0 * g * fabs(disk->ymin - disk->base0))) / g;
 414         disk->u1 = u + g * disk->t1;
 415         disk->t2 = 2.0 * disk->usintheta / g;
 416         disk->u2 = disk->usintheta - g * disk->t2;
 417
 418         /* Compute direction of travel, in the XZ plane. */
 419         disk->phi = atan(dz / dx);
 420         disk->phi *= 180.0 / M_PI; /* convert radians to degrees */
 421 }
 422
 423 /* For debugging: show a value as a string of ones and zeroes
 424 static const char *byteToBinary(int x) {
 425     static char b[9];
 426         int i, z;
 427
 428     for (z = 128, i = 0; z > 0; z >>= 1, i++) {
 429                 b[i] = ((x & z) == z) ? '1' : '0';
 430     }
 431         b[i] = '\0';
 432
 433     return b;
 434 }
 435 */
 436
 437 static void pushMove(glhcfg *glhanoi, int n, int src, int dst, int avail) {
 438         SubProblem *sp = &(glhanoi->solveStack[glhanoi->solveStackIdx++]);
 439
 440         if (glhanoi->solveStackIdx > glhanoi->solveStackSize) {
 441                 fprintf(stderr, "solveStack overflow: pushed index %d: %d from %d to %d, using %d\n",
 442                 glhanoi->solveStackIdx, n, src, dst, avail);
 443                 exit(EXIT_FAILURE);
 444         }
 445
 446         sp->nDisks = n;
 447         sp->src = src;
 448         sp->dst = dst;
 449         sp->available = avail & ~((unsigned long)(1 << src))
 450                 & ~((unsigned long)(1 << dst));
 451         /*
 452         fprintf(stderr, "Debug: >  pushed solveStack %d: %d from %d to %d, using %s\n",
 453                 glhanoi->solveStackIdx - 1, n, src, dst, byteToBinary(sp->available));
 454         */
 455 }
 456
 457 static Bool solveStackEmpty(glhcfg *glhanoi) {
 458         return (glhanoi->solveStackIdx < 1);
 459 }
 460
 461 static SubProblem *popMove(glhcfg *glhanoi) {
 462         SubProblem *sp;
 463         if (solveStackEmpty(glhanoi)) return (SubProblem *)NULL;
 464         sp = &(glhanoi->solveStack[--glhanoi->solveStackIdx]);
 465         /* fprintf(stderr, "Debug:  < popped solveStack %d: %d from %d to %d, using %s\n",
 466                         glhanoi->solveStackIdx, sp->nDisks, sp->src, sp->dst, byteToBinary(sp->available)); */
 467         return sp;
 468 }
 469
 470 /* Return number of bits set in b */
 471 static int numBits(unsigned long b) {
 472    int count = 0;
 473    while (b) {
 474       count += b & 0x1u;
 475       b >>= 1;
 476    }
 477    return count;
 478 }
 479
 480 /* Return index (power of 2) of least significant 1 bit. */
 481 static int bitScan(unsigned long b) {
 482         int count;
 483         for (count = 0; b; count++, b >>= 1) {
 484                 if (b & 0x1u) return count;
 485         }
 486         return -1;
 487 }
 488
 489 /* A bit pattern representing all poles */
 490 #define ALL_POLES ((1 << glhanoi->numberOfPoles) - 1)
 491
 492 #define REMOVE_BIT(a, b)  ((a) & ~(1 << (b)))
 493 #define    ADD_BIT(a, b)  ((a) |  (1 << (b)))
 494
 495 static void makeMove(glhcfg *glhanoi)
 496 {
 497         if (glhanoi->numberOfPoles == 3) {
 498                 int fudge = glhanoi->move + 2;
 499                 int magicNumber = magic(fudge);
 500
 501
 502                 glhanoi->currentDisk = pop(glhanoi, glhanoi->src);
 503                 moveSetup(glhanoi, glhanoi->currentDisk);
 504                 push(glhanoi, glhanoi->dst, glhanoi->currentDisk);
 505
 506                 fudge = fudge % 2;
 507
 508                 if(fudge == 1 || magicNumber) {
 509                         swap(&glhanoi->src, &glhanoi->tmp);
 510                 }
 511                 if(fudge == 0 || glhanoi->magicNumber) {
 512                         swap(&glhanoi->dst, &glhanoi->tmp);
 513                 }
 514                 glhanoi->magicNumber = magicNumber;
 515         } else {
 516                 SubProblem sp;
 517                 int tmp = 0;
 518
 519                 if (glhanoi->move == 0) {
 520                         /* Initialize the solution stack. Original problem:
 521                                 move all disks from pole 0 to furthest pole,
 522                                 using all other poles. */
 523                         pushMove(glhanoi, glhanoi->numberOfDisks, 0,
 524                                 glhanoi->numberOfPoles - 1,
 525                                 REMOVE_BIT(REMOVE_BIT(ALL_POLES, 0), glhanoi->numberOfPoles - 1));
 526                 }
 527
 528                 while (!solveStackEmpty(glhanoi)) {
 529                         int k, numAvail;
 530                         sp = *popMove(glhanoi);
 531
 532                         if (sp.nDisks == 1) {
 533                                 /* We have a single, concrete move to do. */
 534                                 /* moveSetup uses glhanoi->src, dst. */
 535                                 glhanoi->src = sp.src;
 536                                 glhanoi->dst = sp.dst;
 537                                 glhanoi->tmp = tmp; /* Probably unnecessary */
 538
 539                                 glhanoi->currentDisk = pop(glhanoi, sp.src);
 540                                 moveSetup(glhanoi, glhanoi->currentDisk);
 541                                 push(glhanoi, sp.dst, glhanoi->currentDisk);
 542
 543                                 return;
 544                         } else {
 545                                 /* Divide and conquer, using Frame-Stewart algorithm, until we get to base case */
 546                                 if (sp.nDisks == 1) break;
 547
 548                                 numAvail = numBits(sp.available);
 549                                 if (numAvail < 2) k = sp.nDisks - 1;
 550                                 else if(numAvail >= sp.nDisks - 2) k = 1;
 551                                 /* heuristic for optimal k: sqrt(2n) (see http://www.cs.wm.edu/~pkstoc/boca.pdf) */
 552                                 else k = (int)(sqrt(2 * sp.nDisks));
 553
 554                                 if (k >= sp.nDisks) k = sp.nDisks - 1;
 555                                 else if (k < 1) k = 1;
 556
 557                                 tmp = bitScan(sp.available);
 558                                 /* fprintf(stderr, "Debug: k is %d, tmp is %d\n", k, tmp); */
 559                                 if (tmp == -1) {
 560                                         fprintf(stderr, "Error: n > 1 (%d) and no poles available\n",
 561                                                 sp.nDisks);
 562                                 }
 563
 564                                 /* Push on moves in reverse order, since this is a stack. */
 565                                 pushMove(glhanoi, k, tmp, sp.dst,
 566                                         REMOVE_BIT(ADD_BIT(sp.available, sp.src), tmp));
 567                                 pushMove(glhanoi, sp.nDisks - k, sp.src, sp.dst,
 568                                         REMOVE_BIT(sp.available, tmp));
 569                                 pushMove(glhanoi, k, sp.src, tmp,
 570                                         REMOVE_BIT(ADD_BIT(sp.available, sp.dst), tmp));
 571
 572                                 /* Repeat until we've found a move we can make. */
 573                         }
 574                 }
 575         }
 576 }
 577
 578 static double lerp(double alpha, double start, double end)
 579 {
 580         return start + alpha * (end - start);
 581 }
 582
 583 static void upfunc(GLdouble t, Disk * d)
 584 {
 585         d->position[0] = d->xmin;
 586         d->position[1] = d->base0 + (d->u1 - 0.5 * g * t) * t;
 587         d->position[2] = d->zmin;
 588
 589         d->rotation[1] = 0.0;
 590 }
 591
 592 static void parafunc(GLdouble t, Disk * d)
 593 {
 594         /* ##was: d->position[0] = d->xmin + d->ucostheta * t; */
 595         d->position[0] = d->xmin + d->dx * t;
 596         d->position[2] = d->zmin + d->dz * t;
 597         d->position[1] = d->ymin + (d->usintheta - 0.5 * g * t) * t;
 598
 599         d->rotation[1] = d->rotAngle * t / d->t2;
 600                 /* d->rotAngle * (d->position[0] - d->xmin) / (d->xmax - d->xmin); */
 601 }
 602
 603 static void downfunc(GLdouble t, Disk * d)
 604 {
 605         d->position[0] = d->xmax;
 606         d->position[1] = d->ymin + (d->u2 - 0.5 * g * t) * t;
 607         d->position[2] = d->zmax;
 608
 609         d->rotation[1] = 0.0;
 610 }
 611
 612 #define normalizeQ(i) ((i) >= glhanoi->trailQSize ? (i) - glhanoi->trailQSize : (i))
 613 #define normalizeQNeg(i) ((i) < 0 ? (i) + glhanoi->trailQSize : (i))
 614
 615 /* Add trail point at position posn at time t onto back of trail queue.
 616         Removes old trails if necessary to make room. */
 617 static void enQTrail(glhcfg *glhanoi, GLfloat *posn)
 618 {
 619         if (glhanoi->trailQSize && glhanoi->state != MONEY_SHOT)  {
 620                 TrailPoint *tp = &(glhanoi->trailQ[glhanoi->trailQBack]);
 621                 double t = getTime();
 622
 623                 tp->position[0] = posn[0];
 624                 tp->position[1] = posn[1] + glhanoi->diskHeight;
 625                 /* Slight jitter to prevent clashing with other trails */
 626                 tp->position[2] = posn[2] + (glhanoi->move % 23) * 0.01;
 627                 tp->startTime = t + TRAIL_START_DELAY;
 628                 tp->endTime = t + TRAIL_START_DELAY + glhanoi->trailDuration;
 629                 tp->isEnd = False;
 630
 631                 /* Update queue back/front indices */
 632                 glhanoi->trailQBack = normalizeQ(glhanoi->trailQBack + 1);
 633                 if (glhanoi->trailQBack == glhanoi->trailQFront)
 634                         glhanoi->trailQFront = normalizeQ(glhanoi->trailQFront + 1);
 635         }
 636 }
 637
 638 /* Mark last trailpoint in queue as the end of a trail. */
 639 /* was: #define endTrail(glh) ((glh)->trailQ[(glh)->trailQBack].isEnd = True) */
 640 static void endTrail(glhcfg *glhanoi) {
 641         if (glhanoi->trailQSize)
 642                 glhanoi->trailQ[normalizeQNeg(glhanoi->trailQBack - 1)].isEnd = True;
 643 }
 644
 645 /* Update disk d's position and rotation based on time t.
 646         Returns true iff move is finished. */
 647 static Bool computePosition(glhcfg *glhanoi, GLfloat t, Disk * d)
 648 {
 649         Bool finished = False;
 650
 651         if(t < d->t1) {
 652                 upfunc(t, d);
 653         } else if(t < d->t1 + d->t2) {
 654                 parafunc(t - d->t1, d);
 655                 enQTrail(glhanoi, d->position);
 656         } else {
 657                 downfunc(t - d->t1 - d->t2, d);
 658                 if(d->position[1] <= d->base1) {
 659                         d->position[1] = d->base1;
 660                         finished = True;
 661                         endTrail(glhanoi);
 662                 }
 663         }
 664         return finished;
 665 }
 666
 667 static void updateView(glhcfg *glhanoi)
 668 {
 669         double longitude, latitude, radius;
 670         double a, b, c, A, B;
 671
 672         get_position(glhanoi->the_rotator, NULL, NULL, &radius,
 673                                  !glhanoi->button_down_p);
 674         get_rotation(glhanoi->the_rotator, &longitude, &latitude, NULL,
 675                                  !glhanoi->button_down_p);
 676         longitude += glhanoi->camera[0];
 677         latitude += glhanoi->camera[1];
 678         radius += glhanoi->camera[2];
 679         /* FUTURE: tweak this to be smooth: */
 680         longitude = longitude - floor(longitude);
 681         latitude = latitude - floor(latitude);
 682         radius = radius - floor(radius);
 683         if(latitude > 0.5) {
 684                 latitude = 1.0 - latitude;
 685         }
 686         if(radius > 0.5) {
 687                 radius = 1.0 - radius;
 688         }
 689
 690         b = glhanoi->centre[1];
 691         c = (MIN_CAMERA_RADIUS +
 692                  radius * (MAX_CAMERA_RADIUS - MIN_CAMERA_RADIUS));
 693         A = M_PI / 4.0 * (1.0 - latitude);
 694         a = sqrt(b * b + c * c - 2.0 * b * c * cos(A));
 695         B = asin(sin(A) * b / a);
 696         glRotatef(-B * 180 / M_PI, 1.0, 0.0, 0.0);
 697
 698         glTranslatef(0.0f, 0.0f,
 699                                  -(MIN_CAMERA_RADIUS +
 700                                    radius * (MAX_CAMERA_RADIUS - MIN_CAMERA_RADIUS)));
 701         glRotatef(longitude * 360.0, 0.0f, 1.0f, 0.0f);
 702         glRotatef(latitude * 180.0, cos(longitude * 2.0 * M_PI), 0.0,
 703                           sin(longitude * 2.0 * M_PI));
 704 }
 705
 706 static void changeState(glhcfg *glhanoi, State state)
 707 {
 708         glhanoi->state = state;
 709         glhanoi->startTime = getTime();
 710 }
 711
 712 static Bool finishedHanoi(glhcfg *glhanoi) {
 713         /* use different criteria depending on algorithm */
 714         return (glhanoi->numberOfPoles == 3 ?
 715                 glhanoi->move >= glhanoi->numberOfMoves :
 716                 solveStackEmpty(glhanoi));
 717 }
 718
 719 static void update_glhanoi(glhcfg *glhanoi)
 720 {
 721         double t = getTime() - glhanoi->startTime;
 722         int i;
 723         Bool done;
 724
 725         switch (glhanoi->state) {
 726         case START:
 727                 if(t < glhanoi->duration) {
 728                         break;
 729                 }
 730                 glhanoi->move = 0;
 731                 if(glhanoi->numberOfDisks % 2 == 0) {
 732                         swap(&glhanoi->tmp, &glhanoi->dst);
 733                 }
 734                 glhanoi->magicNumber = 1;
 735                 makeMove(glhanoi);
 736                 changeState(glhanoi, MOVE_DISK);
 737                 break;
 738
 739         case MOVE_DISK:
 740                 if(computePosition(glhanoi, t * glhanoi->currentDisk->speed, glhanoi->currentDisk)) {
 741                         changeState(glhanoi, MOVE_FINISHED);
 742                 }
 743                 break;
 744
 745         case MOVE_FINISHED:
 746                 ++glhanoi->move;
 747                 if(!finishedHanoi(glhanoi)) {
 748                         makeMove(glhanoi);
 749                         changeState(glhanoi, MOVE_DISK);
 750                 } else {
 751                         glhanoi->duration = FINISH_DURATION;
 752                         changeState(glhanoi, FINISHED);
 753                 }
 754                 break;
 755
 756         case FINISHED:
 757                 if (t < glhanoi->duration)
 758                         break;
 759                 glhanoi->src = glhanoi->olddst;
 760                 glhanoi->dst = glhanoi->oldsrc;
 761                 for(i = 0; i < glhanoi->numberOfDisks; ++i) {
 762                         Disk *disk = pop(glhanoi, glhanoi->src);
 763                         assert(disk != NULL);
 764                         moveSetup(glhanoi, disk);
 765                 }
 766                 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
 767                         push(glhanoi, glhanoi->dst, &glhanoi->disk[i]);
 768                 }
 769                 changeState(glhanoi, MONEY_SHOT);
 770                 break;
 771
 772         case MONEY_SHOT:
 773                 done = True;
 774                 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
 775                         double delay = 0.25 * i;
 776                         int finished;
 777
 778                         if(t - delay < 0) {
 779                                 done = False;
 780                                 continue;
 781                         }
 782
 783                         finished = computePosition(glhanoi, t - delay, &glhanoi->disk[i]);
 784                         glhanoi->disk[i].rotation[1] = 0.0;
 785
 786                         if(!finished) {
 787                                 done = False;
 788                         }
 789                 }
 790                 if(done) {
 791                         glhanoi->src = glhanoi->oldsrc;
 792                         glhanoi->tmp = glhanoi->oldtmp;
 793                         glhanoi->dst = glhanoi->olddst;
 794                         changeState(glhanoi, START);
 795                 }
 796                 break;
 797
 798         case INVALID:
 799         default:
 800                 fprintf(stderr, "Invalid state\n");
 801                 break;
 802         }
 803 }
 804
 805 static void HSVtoRGBf(GLfloat h, GLfloat s, GLfloat v,
 806                            GLfloat * r, GLfloat * g, GLfloat * b)
 807 {
 808         if(s == 0.0) {
 809                 *r = v;
 810                 *g = v;
 811                 *b = v;
 812         } else {
 813                 GLfloat i, f, p, q, t;
 814                 if(h >= 360.0) {
 815                         h = 0.0;
 816                 }
 817                 h /= 60.0;                              /* h now in [0,6). */
 818                 i = floor((double)h);   /* i now largest integer <= h */
 819                 f = h - i;                              /* f is no fractional part of h */
 820                 p = v * (1.0 - s);
 821                 q = v * (1.0 - (s * f));
 822                 t = v * (1.0 - (s * (1.0 - f)));
 823                 switch ((int)i) {
 824                 case 0:
 825                         *r = v;
 826                         *g = t;
 827                         *b = p;
 828                         break;
 829                 case 1:
 830                         *r = q;
 831                         *g = v;
 832                         *b = p;
 833                         break;
 834                 case 2:
 835                         *r = p;
 836                         *g = v;
 837                         *b = t;
 838                         break;
 839                 case 3:
 840                         *r = p;
 841                         *g = q;
 842                         *b = v;
 843                         break;
 844                 case 4:
 845                         *r = t;
 846                         *g = p;
 847                         *b = v;
 848                         break;
 849                 case 5:
 850                         *r = v;
 851                         *g = p;
 852                         *b = q;
 853                         break;
 854                 }
 855         }
 856 }
 857
 858 static void HSVtoRGBv(GLfloat * hsv, GLfloat * rgb)
 859 {
 860         HSVtoRGBf(hsv[0], hsv[1], hsv[2], &rgb[0], &rgb[1], &rgb[2]);
 861 }
 862
 863 static void setMaterial(const GLfloat color[3], const GLfloat hlite[3], int shininess)
 864 {
 865         glColor3fv(color);
 866         glMaterialfv(GL_FRONT, GL_SPECULAR, hlite);
 867         glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color);
 868         glMateriali(GL_FRONT, GL_SHININESS, shininess); /* [0,128] */
 869 }
 870
 871 /*
 872  * drawTube: I know all this stuff is available in gluQuadrics
 873  * but I'd originally intended to texture the poles with a 3D wood
 874  * texture, but I was having difficulty getting wood... what? Why
 875  * are all you Amercians laughing..? Anyway, I don't know if enough
 876  * people's hardware supports 3D textures, so I didn't bother (xorg
 877  * ATI server doesn't :-( )
 878  */
 879 static int drawTube(GLdouble bottomRadius, GLdouble topRadius,
 880                           GLdouble bottomThickness, GLdouble topThickness,
 881                           GLdouble height, GLuint nSlice, GLuint nLoop)
 882 {
 883     int polys = 0;
 884         GLfloat y;
 885         GLfloat *cosCache = malloc(sizeof(GLfloat) * nSlice);
 886         GLfloat *sinCache = malloc(sizeof(GLfloat) * nSlice);
 887         GLint slice;
 888         GLuint loop;
 889         GLint lastSlice = nSlice - 1;
 890         GLfloat radius;
 891         GLfloat innerRadius;
 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         glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1850         glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context));
1851
1852         glViewport(0, 0, (GLint) width, (GLint) height);
1853
1854         glMatrixMode(GL_PROJECTION);
1855         glLoadIdentity();
1856         gluPerspective(30.0, (GLdouble) width / (GLdouble) height, 1.0,
1857                                    2 * MAX_CAMERA_RADIUS);
1858
1859         glMatrixMode(GL_MODELVIEW);
1860         glLoadIdentity();
1861
1862         glClear(GL_COLOR_BUFFER_BIT);
1863 }
1864
1865 static void free_glhanoi(ModeInfo * mi);
1866
1867 ENTRYPOINT void init_glhanoi(ModeInfo * mi)
1868 {
1869         glhcfg *glhanoi;
1870         MI_INIT(mi, glhanoi_cfg, free_glhanoi);
1871
1872         glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1873         glhanoi->glx_context = init_GL(mi);
1874         glhanoi->numberOfDisks = MI_BATCHCOUNT(mi);
1875
1876     if (glhanoi->numberOfDisks <= 1)
1877       glhanoi->numberOfDisks = 3 + (int) BELLRAND(9);
1878
1879         /* magicnumber is a bitfield, so we can't have more than 31 discs
1880            on a system with 4-byte ints. */
1881         if (glhanoi->numberOfDisks >= 8 * sizeof(int))
1882                 glhanoi->numberOfDisks = (8 * sizeof(int)) - 1;
1883
1884         glhanoi->maxDiskIdx = glhanoi->numberOfDisks - 1;
1885
1886         glhanoi->numberOfPoles = get_integer_resource(MI_DISPLAY(mi), "poles", "Integer");
1887         /* Set a number of poles from 3 to numberOfDisks + 1, biased toward lower values,
1888                 with probability decreasing linearly. */
1889     if (glhanoi->numberOfPoles <= 2)
1890       glhanoi->numberOfPoles = 3 +
1891                 (int)((1 - sqrt(frand(1.0))) * (glhanoi->numberOfDisks - 1));
1892
1893         glhanoi->wire = MI_IS_WIREFRAME(mi);
1894
1895 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
1896     glhanoi->wire = 0;
1897 # endif
1898
1899         glhanoi->light = light;
1900         glhanoi->fog = fog;
1901         glhanoi->texture = texture;
1902         glhanoi->speed = speed;
1903         glhanoi->trailDuration = trails;
1904         /* set trailQSize based on 60 fps (a maximum, more or less) */
1905         /* FUTURE: Should clamp framerate to 60 fps? See flurry.c's draw_flurry().
1906                 The only bad effect if we don't is that trail-ends could
1907                 show "unnatural" pauses at high fps. */
1908         glhanoi->trailQSize = (int)(trails * 60.0);
1909
1910         reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
1911
1912         if(glhanoi->wire) {
1913                 glhanoi->light = False;
1914                 glhanoi->fog = False;
1915                 glhanoi->texture = False;
1916         }
1917
1918         initLights(!glhanoi->wire && glhanoi->light);
1919         checkAllocAndExit(!makeTextures(glhanoi), "textures\n");
1920
1921         /* Choose linear or circular layout. Could make this a user option. */
1922         glhanoi->layoutLinear = (glhanoi->numberOfPoles == 3);
1923
1924         initData(glhanoi);
1925         initView(glhanoi);
1926         initFloor(glhanoi);
1927         initBase(glhanoi);
1928         initTowers(glhanoi);
1929         initDisks(glhanoi);
1930
1931         glEnable(GL_DEPTH_TEST);
1932         glEnable(GL_NORMALIZE);
1933         glEnable(GL_CULL_FACE);
1934         glShadeModel(GL_SMOOTH);
1935         if(glhanoi->fog) {
1936                 glClearColor(fogcolor[0], fogcolor[1], fogcolor[2], 1.0);
1937                 glFogi(GL_FOG_MODE, GL_LINEAR);
1938                 glFogfv(GL_FOG_COLOR, fogcolor);
1939                 glFogf(GL_FOG_DENSITY, 0.35f);
1940                 glHint(GL_FOG_HINT, GL_NICEST);
1941                 glFogf(GL_FOG_START, MIN_CAMERA_RADIUS);
1942                 glFogf(GL_FOG_END, MAX_CAMERA_RADIUS / 1.9);
1943                 glEnable(GL_FOG);
1944         }
1945
1946         glhanoi->duration = START_DURATION;
1947         changeState(glhanoi, START);
1948 }
1949
1950 ENTRYPOINT void draw_glhanoi(ModeInfo * mi)
1951 {
1952         glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1953         Display *dpy = MI_DISPLAY(mi);
1954         Window window = MI_WINDOW(mi);
1955
1956         if(!glhanoi->glx_context)
1957                 return;
1958
1959     glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context));
1960
1961         glPolygonMode(GL_FRONT, glhanoi->wire ? GL_LINE : GL_FILL);
1962
1963         glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1964     mi->polygon_count = 0;
1965
1966         glLoadIdentity();
1967     glRotatef(current_device_rotation(), 0, 0, 1);
1968
1969         update_glhanoi(glhanoi);
1970         updateView(glhanoi);
1971
1972 # ifdef HAVE_MOBILE     /* Keep it the same relative size when rotated. */
1973     {
1974       GLfloat h = MI_HEIGHT(mi) / (GLfloat) MI_WIDTH(mi);
1975       int o = (int) current_device_rotation();
1976       if (o != 0 && o != 180 && o != -180)
1977         glScalef (1/h, 1/h, 1/h);
1978     }
1979 # endif
1980
1981         if(!glhanoi->wire && glhanoi->texture) {
1982                 glEnable(GL_TEXTURE_2D);
1983         }
1984     mi->polygon_count += drawFloor(glhanoi);
1985         glDisable(GL_TEXTURE_2D);
1986
1987         mi->polygon_count += drawTowers(glhanoi);
1988         mi->polygon_count += drawDisks(glhanoi);
1989
1990         if (glhanoi->trailQSize) {
1991                 /* No polygons, just lines. So ignore the return count. */
1992                 (void)drawTrails(glhanoi);
1993         }
1994
1995         if(mi->fps_p) {
1996                 do_fps(mi);
1997         }
1998         glFinish();
1999
2000         glXSwapBuffers(dpy, window);
2001 }
2002
2003 ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event)
2004 {
2005         glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
2006
2007     /* #### this is all wrong on iOS -- should be using gltrackball. */
2008
2009         if(event->xany.type == ButtonPress && event->xbutton.button == Button1) {
2010                 glhanoi->button_down_p = True;
2011                 glhanoi->drag_x = event->xbutton.x;
2012                 glhanoi->drag_y = event->xbutton.y;
2013                 return True;
2014         } else if(event->xany.type == ButtonRelease
2015                           && event->xbutton.button == Button1) {
2016                 glhanoi->button_down_p = False;
2017                 return True;
2018         } else if(event->xany.type == ButtonPress &&
2019                           (event->xbutton.button == Button4
2020                            || event->xbutton.button == Button5)) {
2021                 switch (event->xbutton.button) {
2022                 case Button4:
2023                         glhanoi->camera[2] += 0.01;
2024                         break;
2025                 case Button5:
2026                         glhanoi->camera[2] -= 0.01;
2027                         break;
2028                 default:
2029                         fprintf(stderr,
2030                                         "glhanoi: unknown button in mousewheel handler\n");
2031                 }
2032                 return True;
2033         } else if(event->xany.type == MotionNotify
2034                           && glhanoi_cfg->button_down_p) {
2035                 int x_diff, y_diff;
2036
2037                 x_diff = event->xbutton.x - glhanoi->drag_x;
2038                 y_diff = event->xbutton.y - glhanoi->drag_y;
2039
2040                 glhanoi->camera[0] = (float)x_diff / (float)MI_WIDTH(mi);
2041                 glhanoi->camera[1] = (float)y_diff / (float)MI_HEIGHT(mi);
2042
2043                 return True;
2044         }
2045 #if 0 /* #### doesn't work */
2046   else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
2047     {
2048       changeState(glhanoi, START);
2049       return True;
2050     }
2051 #endif
2052         return False;
2053 }
2054
2055 static void free_glhanoi(ModeInfo * mi)
2056 {
2057         int i;
2058         int j;
2059         glhcfg *glh = &glhanoi_cfg[MI_SCREEN(mi)];
2060         if (glh->glx_context) {
2061                 glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glh->glx_context));
2062                 glDeleteLists(glh->floorList, 1);
2063                 glDeleteLists(glh->baseList, 1);
2064                 glDeleteLists(glh->poleList, 1);
2065                 glDeleteLists(glh->textureNames[0], 2);
2066                 for(j = 0; j < glh->numberOfDisks; ++j) {
2067                         glDeleteLists(glh->disk[j].displayList, 1);
2068                 }
2069                 free(glh->disk);
2070                 for(i = 0; i < glh->numberOfPoles; i++) {
2071                         if(glh->pole[i].data != NULL) {
2072                                 free(glh->pole[i].data);
2073                         }
2074                 }
2075         }
2076 }
2077
2078 XSCREENSAVER_MODULE ("GLHanoi", glhanoi)
2079
2080 #endif                                                  /* USE_GL */