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
  25 #define DEFAULTS "*delay:     15000\n" \
  26                                  "*count:     0\n" \
  27                                  "*showFPS:   False\n" \
  28                                  "*wireframe: False\n"
  29
  30 # define refresh_glhanoi 0
  31
  32 /* polygon resolution of poles and disks */
  33 #define NSLICE 32
  34 #define NLOOPS 1
  35
  36 /* How long to wait at start and finish. */
  37 #define START_DURATION 1.0
  38 #define FINISH_DURATION 1.0
  39 #define BASE_LENGTH 30.0
  40 #define BOARD_SQUARES 8
  41
  42 #define MAX_CAMERA_RADIUS 250.0
  43 #define MIN_CAMERA_RADIUS 75.0
  44
  45 #define MARBLE_SCALE 1.01
  46
  47 #undef BELLRAND
  48 /* Return a double precision number in [0...n], with bell curve distribution. */
  49 #define BELLRAND(n) ((frand((n)) + frand((n)) + frand((n))) / 3)
  50
  51 enum {
  52         MARBLE_TEXURE,
  53         N_TEXTURES
  54 };
  55
  56 #define MARBLE_TEXTURE_SIZE 256
  57
  58 #undef countof
  59 #define countof(x) (sizeof((x))/sizeof((*x)))
  60
  61 #include <math.h>
  62 #include "xlockmore.h"
  63
  64 #ifdef USE_GL                                   /* whole file */
  65
  66 typedef struct timeval glhtime;
  67
  68 static double getTime(void)
  69 {
  70         struct timeval t;
  71 #ifdef GETTIMEOFDAY_TWO_ARGS
  72         gettimeofday(&t, NULL);
  73 #else                                                   /* !GETTIMEOFDAY_TWO_ARGS */
  74         gettimeofday(&t);
  75 #endif                                                  /* !GETTIMEOFDAY_TWO_ARGS */
  76         return t.tv_sec + t.tv_usec / 1000000.0;
  77 }
  78
  79 typedef enum {
  80         START,
  81         MOVE_DISK,
  82         MOVE_FINISHED,
  83         FINISHED,
  84         MONEY_SHOT,
  85         INVALID = -1
  86 } State;
  87
  88 typedef struct {
  89         int id;
  90         GLuint displayList;
  91         GLfloat position[3];
  92         GLfloat rotation[3];
  93         GLfloat color[4];
  94         GLfloat base0;
  95         GLfloat base1;
  96         GLfloat height;
  97         GLfloat xmin, xmax, ymin;
  98         GLfloat u1, u2;
  99         GLfloat t1, t2;
 100         GLfloat ucostheta, usintheta;
 101         GLdouble rotAngle;
 102         GLfloat speed;
 103     int polys;
 104 } Disk;
 105
 106 typedef struct {
 107         Disk **data;
 108         int count;
 109         int size;
 110 } Pole;
 111
 112 /* A SubProblem is a recursive subdivision of the problem, and means
 113   "Move nDisks disks from src pole to dst pole, using the poles indicated in 'available'." */
 114 typedef struct {
 115         int nDisks;
 116         int src, dst;
 117         unsigned long available; /* a bitmask of poles that have no smaller disks on them */
 118 } SubProblem;
 119
 120 typedef struct {
 121         GLXContext *glx_context;
 122         State state;
 123         Bool wire;
 124         Bool fog;
 125         Bool light;
 126         double startTime;
 127         double lastTime;
 128         double duration;
 129         int numberOfDisks;
 130         int numberOfPoles;
 131         int numberOfMoves;
 132         int maxDiskIdx;
 133         int magicNumber;
 134         Disk *currentDisk;
 135         int move;
 136         /* src, tmp, dst: index of pole that is source / storage / destination for
 137                 current move */
 138         int src;
 139         int tmp;
 140         int dst;
 141         int oldsrc;
 142         int oldtmp;
 143         int olddst;
 144         SubProblem *solveStack;
 145         int solveStackSize, solveStackIdx;
 146         Pole *pole;
 147         float boardSize;
 148         float baseLength;
 149         float baseWidth;
 150         float baseHeight;
 151         float poleRadius;
 152         float poleHeight;
 153         float poleOffset;
 154         float diskHeight;
 155         float *diskPos;                         /* pre-computed disk positions on rods */
 156         Disk *disk;
 157         GLint floorList;
 158         GLint baseList;
 159         GLint poleList;
 160     int floorpolys, basepolys, polepolys;
 161         GLfloat camera[3];
 162         GLfloat centre[3];
 163         rotator *the_rotator;
 164         Bool button_down_p;
 165         Bool texture;
 166         GLuint textureNames[N_TEXTURES];
 167         int drag_x;
 168         int drag_y;
 169         int noise_initted;
 170         int p[512];
 171 } glhcfg;
 172
 173 static glhcfg *glhanoi_cfg = NULL;
 174 static Bool fog;
 175 static Bool light;
 176 static Bool texture;
 177 static int poles;
 178 static double speed; /* coefficient for how fast the disks move */
 179
 180 static XrmOptionDescRec opts[] = {
 181         {"-light", ".glhanoi.light", XrmoptionNoArg, "true"},
 182         {"+light", ".glhanoi.light", XrmoptionNoArg, "false"},
 183         {"-fog", ".glhanoi.fog", XrmoptionNoArg, "true"},
 184         {"+fog", ".glhanoi.fog", XrmoptionNoArg, "false"},
 185         {"-texture", ".glhanoi.texture", XrmoptionNoArg, "true"},
 186         {"+texture", ".glhanoi.texture", XrmoptionNoArg, "false"},
 187         {"-poles", ".glhanoi.poles", XrmoptionSepArg, 0 },
 188         {"-speed", ".glhanoi.speed", XrmoptionSepArg, 0 }
 189 };
 190
 191 static argtype vars[] = {
 192         {&light, "light", "Light", DEF_LIGHT, t_Bool},
 193         {&fog, "fog", "Fog", DEF_FOG, t_Bool},
 194         {&texture, "texture", "Texture", DEF_TEXTURE, t_Bool},
 195         {&poles, "poles", "Poles", DEF_POLES, t_Int},
 196         {&speed, "speed", "Speed", DEF_SPEED, t_Float}
 197 };
 198
 199 static OptionStruct desc[] = {
 200         {"+/-light", "whether to light the scene"},
 201         {"+/-fog", "whether to apply fog to the scene"},
 202         {"+/-texture", "whether to apply texture to the scene"},
 203         {"-poles r", "number of poles to move disks between"},
 204         {"-speed s", "speed multiplier"}
 205 };
 206
 207 ENTRYPOINT ModeSpecOpt glhanoi_opts = { countof(opts), opts, countof(vars), vars, desc };
 208
 209 #ifdef USE_MODULES
 210
 211 ModStruct glhanoi_description = {
 212         "glhanoi", "init_glhanoi", "draw_glhanoi", "release_glhanoi",
 213         "draw_glhanoi", "init_glhanoi", NULL, &glhanoi_opts,
 214         1000, 1, 2, 1, 4, 1.0, "",
 215         "Towers of Hanoi", 0, NULL
 216 };
 217
 218 #endif
 219
 220 static const GLfloat cBlack[] = { 0.0, 0.0, 0.0, 1.0 };
 221 static const GLfloat cWhite[] = { 1.0, 1.0, 1.0, 1.0 };
 222 static const GLfloat poleColor[] = { 0.545, 0.137, 0.137 };
 223 static const GLfloat baseColor[] = { 0.34, 0.34, 0.48 };
 224 static const GLfloat fogcolor[] = { 0.5, 0.5, 0.5 };
 225
 226 static const float left[] = { 1.0, 0.0, 0.0 };
 227 static const float up[] = { 0.0, 1.0, 0.0 };
 228 static const float front[] = { 0.0, 0.0, 1.0 };
 229 static const float right[] = { -1.0, 0.0, 0.0 };
 230 static const float down[] = { 0.0, -1.0, 0.0 };
 231 static const float back[] = { 0.0, 0.0, -1.0 };
 232
 233 static const GLfloat pos0[4] = { 50.0, 50.0, 50.0, 0.0 };
 234 static const GLfloat amb0[4] = { 0.0, 0.0, 0.0, 1.0 };
 235 static const GLfloat dif0[4] = { 1.0, 1.0, 1.0, 1.0 };
 236 static const GLfloat spc0[4] = { 0.0, 1.0, 1.0, 1.0 };
 237
 238 static const GLfloat pos1[4] = { -50.0, 50.0, -50.0, 0.0 };
 239 static const GLfloat amb1[4] = { 0.0, 0.0, 0.0, 1.0 };
 240 static const GLfloat dif1[4] = { 1.0, 1.0, 1.0, 1.0 };
 241 static const GLfloat spc1[4] = { 1.0, 1.0, 1.0, 1.0 };
 242
 243 static float g = 3.0 * 9.80665;         /* hmm, looks like we need more gravity, Scotty... */
 244
 245 static void checkAllocAndExit(Bool item, char *descr) {
 246         if (!item) {
 247                 fprintf(stderr, "%s: unable to allocate memory for %s\n",
 248                                 progname, descr);
 249                 exit(EXIT_FAILURE);
 250         }
 251 }
 252
 253 #define DOPUSH(X, Y)    (((X)->count) >= ((X)->size)) ? NULL : ((X)->data[(X)->count++] = (Y))
 254 #define DOPOP(X)        (X)->count <= 0 ? NULL : ((X)->data[--((X)->count)])
 255
 256 /* push disk d onto pole idx */
 257 static Disk *push(glhcfg *glhanoi, int idx, Disk * d)
 258 {
 259         return DOPUSH(&glhanoi->pole[idx], d);
 260 }
 261
 262 /* pop the top disk from pole idx */
 263 static Disk *pop(glhcfg *glhanoi, int idx)
 264 {
 265         return DOPOP(&glhanoi->pole[idx]);
 266 }
 267
 268 static inline void swap(int *x, int *y)
 269 {
 270         *x = *x ^ *y;
 271         *y = *x ^ *y;
 272         *x = *x ^ *y;
 273 }
 274
 275 /*
 276  * magic - it's magic...
 277  *  Return 1 if the number of trailing zeroes on i is even, unless i is 1 or 0.
 278  */
 279 static int magic(int i)
 280 {
 281         int count = 0;
 282         if(i <= 1)
 283                 return 0;
 284         while((i & 0x01) == 0) {
 285                 i >>= 1;
 286                 count++;
 287         }
 288         return count % 2 == 0;
 289 }
 290
 291 #if 0
 292 static float distance(float *p0, float *p1)
 293 {
 294         float x, y, z;
 295         x = p1[0] - p0[0];
 296         y = p1[1] - p0[1];
 297         z = p1[2] - p0[2];
 298         return (float)sqrt(x * x + y * y + z * z);
 299 }
 300 #endif
 301
 302 static GLfloat A(GLfloat a, GLfloat b, GLfloat c)
 303 {
 304         GLfloat sum = a + b;
 305         return c / (a * b - 0.25 * sum * sum);
 306 }
 307
 308 static void moveSetup(glhcfg *glhanoi, Disk * disk)
 309 {
 310         float h, ymax;
 311         float u;
 312         int src = glhanoi->src;
 313         int dst = glhanoi->dst;
 314         GLfloat theta;
 315         GLfloat sintheta, costheta;
 316         double absx;
 317
 318         if(glhanoi->state != FINISHED) {
 319                 double xxx = -180.0 * (dst - src >= 0 ? 1.0 : -1.0);
 320                 if(random() % 6 == 0) {
 321                         disk->rotAngle = xxx * (2 - 2 * random() % 2) * (random() % 3 + 1);
 322                 } else {
 323                         disk->rotAngle = xxx;
 324                 }
 325                 if(random() % 4 == 0) {
 326                         disk->rotAngle = -disk->rotAngle;
 327                 }
 328
 329         } else {
 330                 disk->rotAngle = -180.0;
 331         }
 332
 333         disk->base0 = glhanoi->diskPos[glhanoi->pole[src].count];
 334         disk->base1 =
 335                 glhanoi->state ==
 336                 FINISHED ? disk->base0 : glhanoi->diskPos[glhanoi->pole[dst].
 337                                                                                                   count];
 338
 339         disk->xmin = glhanoi->poleOffset * (src - (glhanoi->numberOfPoles - 1.0f) * 0.5);
 340         disk->xmax = glhanoi->poleOffset * (dst - (glhanoi->numberOfPoles - 1.0f) * 0.5);
 341         disk->ymin = glhanoi->poleHeight;
 342
 343         absx = fabs(disk->xmax - disk->xmin);
 344         ymax = glhanoi->poleHeight + absx;
 345         if(glhanoi->state == FINISHED) {
 346                 ymax += absx * (double)(glhanoi->numberOfDisks - disk->id);
 347         }
 348         h = ymax - disk->ymin;
 349         theta = atan((disk->xmin - disk->xmax) * A(disk->xmin, disk->xmax, h));
 350         if(theta < 0.0)
 351                 theta += M_PI;
 352         costheta = cos(theta);
 353         sintheta = sin(theta);
 354         u = (float)
 355                 sqrt(fabs
 356                          (-g /
 357                           (2.0 * A(disk->xmin, disk->xmax, h) * costheta * costheta)));
 358         disk->usintheta = u * sintheta;
 359         disk->ucostheta = u * costheta;
 360         disk->t1 =
 361                 (-u + sqrt(u * u + 2.0 * g * fabs(disk->ymin - disk->base0))) / g;
 362         disk->u1 = u + g * disk->t1;
 363         disk->t2 = 2.0 * disk->usintheta / g;
 364         disk->u2 = disk->usintheta - g * disk->t2;
 365 }
 366
 367 /* For debugging: show a value as a string of ones and zeroes
 368 static const char *byteToBinary(int x) {
 369     static char b[9];
 370         int i, z;
 371
 372     for (z = 128, i = 0; z > 0; z >>= 1, i++) {
 373                 b[i] = ((x & z) == z) ? '1' : '0';
 374     }
 375         b[i] = '\0';
 376
 377     return b;
 378 }
 379 */
 380
 381 static void pushMove(glhcfg *glhanoi, int n, int src, int dst, int avail) {
 382         SubProblem *sp = &(glhanoi->solveStack[glhanoi->solveStackIdx++]);
 383
 384         if (glhanoi->solveStackIdx > glhanoi->solveStackSize) {
 385                 fprintf(stderr, "solveStack overflow: pushed index %d: %d from %d to %d, using %d\n",
 386                 glhanoi->solveStackIdx, n, src, dst, avail);
 387                 exit(EXIT_FAILURE);
 388         }
 389
 390         sp->nDisks = n;
 391         sp->src = src;
 392         sp->dst = dst;
 393         sp->available = avail & ~((unsigned long)(1 << src))
 394                 & ~((unsigned long)(1 << dst));
 395         /*
 396         fprintf(stderr, "Debug: >  pushed solveStack %d: %d from %d to %d, using %s\n",
 397                 glhanoi->solveStackIdx - 1, n, src, dst, byteToBinary(sp->available));
 398         */
 399 }
 400
 401
 402 static Bool solveStackEmpty(glhcfg *glhanoi) {
 403         return (glhanoi->solveStackIdx < 1);
 404 }
 405
 406 static SubProblem *popMove(glhcfg *glhanoi) {
 407         SubProblem *sp;
 408         if (solveStackEmpty(glhanoi)) return (SubProblem *)NULL;
 409         sp = &(glhanoi->solveStack[--glhanoi->solveStackIdx]);
 410         /* fprintf(stderr, "Debug:  < popped solveStack %d: %d from %d to %d, using %s\n",
 411                         glhanoi->solveStackIdx, sp->nDisks, sp->src, sp->dst, byteToBinary(sp->available)); */
 412         return sp;
 413 }
 414
 415 /* Return number of bits set in b */
 416 static int numBits(unsigned long b) {
 417    int count = 0;
 418    while (b) {
 419       count += b & 0x1u;
 420       b >>= 1;
 421    }
 422    return count;
 423 }
 424
 425 /* Return index (power of 2) of least significant 1 bit. */
 426 static int bitScan(unsigned long b) {
 427         int count;
 428         for (count = 0; b; count++, b >>= 1) {
 429                 if (b & 0x1u) return count;
 430         }
 431         return -1;
 432 }
 433
 434 /* A bit pattern representing all poles */
 435 #define ALL_POLES ((1 << glhanoi->numberOfPoles) - 1)
 436
 437 #define REMOVE_BIT(a, b)  ((a) & ~(1 << (b)))
 438 #define    ADD_BIT(a, b)  ((a) |  (1 << (b)))
 439
 440 static void makeMove(glhcfg *glhanoi)
 441 {
 442         if (glhanoi->numberOfPoles == 3) {
 443                 int fudge = glhanoi->move + 2;
 444                 int magicNumber = magic(fudge);
 445
 446
 447                 glhanoi->currentDisk = pop(glhanoi, glhanoi->src);
 448                 moveSetup(glhanoi, glhanoi->currentDisk);
 449                 push(glhanoi, glhanoi->dst, glhanoi->currentDisk);
 450
 451                 fudge = fudge % 2;
 452
 453                 if(fudge == 1 || magicNumber) {
 454                         swap(&glhanoi->src, &glhanoi->tmp);
 455                 }
 456                 if(fudge == 0 || glhanoi->magicNumber) {
 457                         swap(&glhanoi->dst, &glhanoi->tmp);
 458                 }
 459                 glhanoi->magicNumber = magicNumber;
 460         } else {
 461                 SubProblem sp;
 462                 int tmp = 0;
 463
 464                 if (glhanoi->move == 0) {
 465                         /* Initialize the solution stack. Original problem:
 466                                 move all disks from pole 0 to furthest pole,
 467                                 using all other poles. */
 468                         pushMove(glhanoi, glhanoi->numberOfDisks, 0,
 469                                 glhanoi->numberOfPoles - 1,
 470                                 REMOVE_BIT(REMOVE_BIT(ALL_POLES, 0), glhanoi->numberOfPoles - 1));
 471                 }
 472
 473                 while (!solveStackEmpty(glhanoi)) {
 474                         int k, numAvail;
 475                         sp = *popMove(glhanoi);
 476
 477                         if (sp.nDisks == 1) {
 478                                 /* We have a single, concrete move to do. */
 479                                 /* moveSetup uses glhanoi->src, dst. */
 480                                 glhanoi->src = sp.src;
 481                                 glhanoi->dst = sp.dst;
 482                                 glhanoi->tmp = tmp; /* Probably unnecessary */
 483
 484                                 glhanoi->currentDisk = pop(glhanoi, sp.src);
 485                                 moveSetup(glhanoi, glhanoi->currentDisk);
 486                                 push(glhanoi, sp.dst, glhanoi->currentDisk);
 487
 488                                 return;
 489                         } else {
 490                                 /* Divide and conquer, using Frame-Stewart algorithm, until we get to base case */
 491                                 if (sp.nDisks == 1) break;
 492
 493                                 numAvail = numBits(sp.available);
 494                                 if (numAvail < 2) k = sp.nDisks - 1;
 495                                 else if(numAvail >= sp.nDisks - 2) k = 1;
 496                                 /* heuristic for optimal k: sqrt(2n) (see http://www.cs.wm.edu/~pkstoc/boca.pdf) */
 497                                 else k = (int)(sqrt(2 * sp.nDisks));
 498
 499                                 if (k >= sp.nDisks) k = sp.nDisks - 1;
 500                                 else if (k < 1) k = 1;
 501
 502                                 tmp = bitScan(sp.available);
 503                                 /* fprintf(stderr, "Debug: k is %d, tmp is %d\n", k, tmp); */
 504                                 if (tmp == -1) {
 505                                         fprintf(stderr, "Error: n > 1 (%d) and no poles available\n",
 506                                                 sp.nDisks);
 507                                 }
 508
 509                                 /* Push on moves in reverse order, since this is a stack. */
 510                                 pushMove(glhanoi, k, tmp, sp.dst,
 511                                         REMOVE_BIT(ADD_BIT(sp.available, sp.src), tmp));
 512                                 pushMove(glhanoi, sp.nDisks - k, sp.src, sp.dst,
 513                                         REMOVE_BIT(sp.available, tmp));
 514                                 pushMove(glhanoi, k, sp.src, tmp,
 515                                         REMOVE_BIT(ADD_BIT(sp.available, sp.dst), tmp));
 516
 517                                 /* Repeat until we've found a move we can make. */
 518                         }
 519                 }
 520         }
 521 }
 522
 523 static double lerp(double alpha, double start, double end)
 524 {
 525         return start + alpha * (end - start);
 526 }
 527
 528 static void upfunc(GLdouble t, Disk * d)
 529 {
 530         d->position[0] = d->xmin;
 531         d->position[1] = d->base0 + (d->u1 - 0.5 * g * t) * t;
 532
 533         d->rotation[1] = 0.0;
 534 }
 535
 536 static void parafunc(GLdouble t, Disk * d)
 537 {
 538         d->position[0] = d->xmin + d->ucostheta * t;
 539         d->position[1] = d->ymin + (d->usintheta - 0.5 * g * t) * t;
 540
 541         d->rotation[1] =
 542         d->rotAngle * (d->position[0] - d->xmin) / (d->xmax - d->xmin);
 543 }
 544
 545 static void downfunc(GLdouble t, Disk * d)
 546 {
 547         d->position[0] = d->xmax;
 548         d->position[1] = d->ymin + (d->u2 - 0.5 * g * t) * t;
 549
 550         d->rotation[1] = 0.0;
 551 }
 552
 553 /* Return true iff move is finished. */
 554 static Bool computePosition(GLfloat t, Disk * d)
 555 {
 556         Bool finished = False;
 557
 558         if(t < d->t1) {
 559                 upfunc(t, d);
 560         } else if(t < d->t1 + d->t2) {
 561                 parafunc(t - d->t1, d);
 562         } else {
 563                 downfunc(t - d->t1 - d->t2, d);
 564                 if(d->position[1] <= d->base1) {
 565                         d->position[1] = d->base1;
 566                         finished = True;
 567                 }
 568         }
 569         return finished;
 570 }
 571
 572 static void updateView(glhcfg *glhanoi)
 573 {
 574         double longitude, latitude, radius;
 575         double a, b, c, A, B;
 576
 577         get_position(glhanoi->the_rotator, NULL, NULL, &radius,
 578                                  !glhanoi->button_down_p);
 579         get_rotation(glhanoi->the_rotator, &longitude, &latitude, NULL,
 580                                  !glhanoi->button_down_p);
 581         longitude += glhanoi->camera[0];
 582         latitude += glhanoi->camera[1];
 583         radius += glhanoi->camera[2];
 584         longitude = longitude - floor(longitude);
 585         latitude = latitude - floor(latitude);
 586         radius = radius - floor(radius);
 587         if(latitude > 0.5) {
 588                 latitude = 1.0 - latitude;
 589         }
 590         if(radius > 0.5) {
 591                 radius = 1.0 - radius;
 592         }
 593
 594         b = glhanoi->centre[1];
 595         c = (MIN_CAMERA_RADIUS +
 596                  radius * (MAX_CAMERA_RADIUS - MIN_CAMERA_RADIUS));
 597         A = M_PI / 4.0 * (1.0 - latitude);
 598         a = sqrt(b * b + c * c - 2.0 * b * c * cos(A));
 599         B = asin(sin(A) * b / a);
 600         glRotatef(-B * 180 / M_PI, 1.0, 0.0, 0.0);
 601
 602         glTranslatef(0.0f, 0.0f,
 603                                  -(MIN_CAMERA_RADIUS +
 604                                    radius * (MAX_CAMERA_RADIUS - MIN_CAMERA_RADIUS)));
 605         glRotatef(longitude * 360.0, 0.0f, 1.0f, 0.0f);
 606         glRotatef(latitude * 180.0, cos(longitude * 2.0 * M_PI), 0.0,
 607                           sin(longitude * 2.0 * M_PI));
 608 }
 609
 610 static void changeState(glhcfg *glhanoi, State state)
 611 {
 612         glhanoi->state = state;
 613         glhanoi->startTime = getTime();
 614 }
 615
 616 static Bool finishedHanoi(glhcfg *glhanoi) {
 617         /* use different criteria depending on algorithm */
 618         return (glhanoi->numberOfPoles == 3 ?
 619                 glhanoi->move >= glhanoi->numberOfMoves :
 620                 solveStackEmpty(glhanoi));
 621 }
 622
 623 static void update_glhanoi(glhcfg *glhanoi)
 624 {
 625         double t = getTime() - glhanoi->startTime;
 626         int i;
 627         Bool done;
 628
 629         switch (glhanoi->state) {
 630         case START:
 631                 if(t < glhanoi->duration) {
 632                         break;
 633                 }
 634                 glhanoi->move = 0;
 635                 if(glhanoi->numberOfDisks % 2 == 0) {
 636                         swap(&glhanoi->tmp, &glhanoi->dst);
 637                 }
 638                 glhanoi->magicNumber = 1;
 639                 makeMove(glhanoi);
 640                 changeState(glhanoi, MOVE_DISK);
 641                 break;
 642
 643         case MOVE_DISK:
 644                 if(computePosition(t * glhanoi->currentDisk->speed, glhanoi->currentDisk)) {
 645                         changeState(glhanoi, MOVE_FINISHED);
 646                 }
 647                 break;
 648
 649         case MOVE_FINISHED:
 650                 ++glhanoi->move;
 651                 if(!finishedHanoi(glhanoi)) {
 652                         makeMove(glhanoi);
 653                         changeState(glhanoi, MOVE_DISK);
 654                 } else {
 655                         glhanoi->duration = FINISH_DURATION;
 656                         changeState(glhanoi, FINISHED);
 657                 }
 658                 break;
 659
 660         case FINISHED:
 661                 while(t < glhanoi->duration) {
 662                         break;
 663                 }
 664                 glhanoi->src = glhanoi->olddst;
 665                 glhanoi->dst = glhanoi->oldsrc;
 666                 for(i = 0; i < glhanoi->numberOfDisks; ++i) {
 667                         Disk *disk = pop(glhanoi, glhanoi->src);
 668                         assert(disk != NULL);
 669                         moveSetup(glhanoi, disk);
 670                 }
 671                 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
 672                         push(glhanoi, glhanoi->dst, &glhanoi->disk[i]);
 673                 }
 674                 changeState(glhanoi, MONEY_SHOT);
 675                 break;
 676
 677         case MONEY_SHOT:
 678                 done = True;
 679                 for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
 680                         double delay = 0.25 * i;
 681                         int finished;
 682
 683                         if(t - delay < 0) {
 684                                 done = False;
 685                                 continue;
 686                         }
 687
 688                         finished = computePosition(t - delay, &glhanoi->disk[i]);
 689                         glhanoi->disk[i].rotation[1] = 0.0;
 690
 691                         if(!finished) {
 692                                 done = False;
 693                         }
 694                 }
 695                 if(done) {
 696                         glhanoi->src = glhanoi->oldsrc;
 697                         glhanoi->tmp = glhanoi->oldtmp;
 698                         glhanoi->dst = glhanoi->olddst;
 699                         changeState(glhanoi, START);
 700                 }
 701                 break;
 702
 703         case INVALID:
 704         default:
 705                 fprintf(stderr, "Invalid state\n");
 706                 break;
 707         }
 708 }
 709
 710 static void HSVtoRGBf(GLfloat h, GLfloat s, GLfloat v,
 711                            GLfloat * r, GLfloat * g, GLfloat * b)
 712 {
 713         if(s == 0.0) {
 714                 *r = v;
 715                 *g = v;
 716                 *b = v;
 717         } else {
 718                 GLfloat i, f, p, q, t;
 719                 if(h >= 360.0) {
 720                         h = 0.0;
 721                 }
 722                 h /= 60.0;                              /* h now in [0,6). */
 723                 i = floor((double)h);   /* i now largest integer <= h */
 724                 f = h - i;                              /* f is no fractional part of h */
 725                 p = v * (1.0 - s);
 726                 q = v * (1.0 - (s * f));
 727                 t = v * (1.0 - (s * (1.0 - f)));
 728                 switch ((int)i) {
 729                 case 0:
 730                         *r = v;
 731                         *g = t;
 732                         *b = p;
 733                         break;
 734                 case 1:
 735                         *r = q;
 736                         *g = v;
 737                         *b = p;
 738                         break;
 739                 case 2:
 740                         *r = p;
 741                         *g = v;
 742                         *b = t;
 743                         break;
 744                 case 3:
 745                         *r = p;
 746                         *g = q;
 747                         *b = v;
 748                         break;
 749                 case 4:
 750                         *r = t;
 751                         *g = p;
 752                         *b = v;
 753                         break;
 754                 case 5:
 755                         *r = v;
 756                         *g = p;
 757                         *b = q;
 758                         break;
 759                 }
 760         }
 761 }
 762
 763 static void HSVtoRGBv(GLfloat * hsv, GLfloat * rgb)
 764 {
 765         HSVtoRGBf(hsv[0], hsv[1], hsv[2], &rgb[0], &rgb[1], &rgb[2]);
 766 }
 767
 768 static void setMaterial(const GLfloat color[3], const GLfloat hlite[3], int shininess)
 769 {
 770         glColor3fv(color);
 771         glMaterialfv(GL_FRONT, GL_SPECULAR, hlite);
 772         glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color);
 773         glMateriali(GL_FRONT, GL_SHININESS, shininess); /* [0,128] */
 774 }
 775
 776 /*
 777  * drawTube: I know all this stuff is available in gluQuadrics
 778  * but I'd originally intended to texture the poles with a 3D wood
 779  * texture, but I was having difficulty getting wood... what? Why
 780  * are all you Amercians laughing..? Anyway, I don't know if enough
 781  * people's hardware supports 3D textures, so I didn't bother (xorg
 782  * ATI server doesn't :-( )
 783  */
 784 static int drawTube(GLdouble bottomRadius, GLdouble topRadius,
 785                           GLdouble bottomThickness, GLdouble topThickness,
 786                           GLdouble height, GLuint nSlice, GLuint nLoop)
 787 {
 788     int polys = 0;
 789         GLfloat y;
 790         GLfloat *cosCache = malloc(sizeof(GLfloat) * nSlice);
 791         GLfloat *sinCache = malloc(sizeof(GLfloat) * nSlice);
 792         GLint slice;
 793         GLuint loop;
 794         GLint lastSlice = nSlice - 1;
 795         GLfloat radius;
 796         GLfloat innerRadius;
 797         /*GLfloat maxRadius;*/
 798
 799         if(bottomThickness > bottomRadius) {
 800                 bottomThickness = bottomRadius;
 801         }
 802         if(topThickness > topRadius) {
 803                 topThickness = topRadius;
 804         }
 805         if(bottomThickness < 0.0) {
 806                 bottomThickness = 0.0;
 807         }
 808         if(topThickness < 0.0) {
 809                 topThickness = 0.0;
 810         }
 811 /*      if(topRadius >= bottomRadius) {
 812                 maxRadius = topRadius;
 813         } else {
 814                 maxRadius = bottomRadius;
 815         }*/
 816
 817         /* bottom */
 818         y = 0.0;
 819         radius = bottomRadius;
 820         innerRadius = bottomRadius - bottomThickness;
 821         /* innerTexCoordSize = texCoordSize * innerRadius / maxRadius; */
 822         /* outerTexCoordSize = texCoordSize * radius / maxRadius; */
 823         /* yTexCoord = minTexCoord; */
 824
 825         glBegin(GL_QUAD_STRIP);
 826
 827         glNormal3f(0.0, -1.0, 0.0);
 828
 829         /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + innerTexCoordSize); */
 830         glVertex3f(0.0, y, innerRadius);
 831
 832         /* glTexCoord3f(midTexCoord, yTexCoord, midTexCoord + outerTexCoordSize); */
 833         glVertex3f(0.0, y, radius);
 834
 835         for(slice = lastSlice; slice >= 0; --slice) {
 836                 GLfloat theta = 2.0 * M_PI * (double)slice / nSlice;
 837
 838                 cosCache[slice] = cos(theta);
 839                 sinCache[slice] = sin(theta);
 840
 841                 /* glTexCoord3f(midTexCoord + sinCache[slice] * innerTexCoordSize, */
 842                 /* yTexCoord, */
 843                 /* midTexCoord + cosCache[slice] * innerTexCoordSize); */
 844                 glVertex3f(innerRadius * sinCache[slice], y,
 845                                    innerRadius * cosCache[slice]);
 846                 /* glTexCoord3f(midTexCoord + sinCache[slice] * outerTexCoordSize, */
 847                 /* yTexCoord, */
 848                 /* midTexCoord + cosCache[slice] * outerTexCoordSize); */
 849                 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
 850         polys++;
 851         }
 852         glEnd();
 853
 854         /* middle */
 855         for(loop = 0; loop < nLoop; ++loop) {
 856                 GLfloat lowerRadius =
 857                         bottomRadius + (topRadius -
 858                                                         bottomRadius) * (float)loop / (nLoop);
 859                 GLfloat upperRadius =
 860                         bottomRadius + (topRadius - bottomRadius) * (float)(loop +
 861                                                                                                                                 1) /
 862                         (nLoop);
 863                 GLfloat lowerY = height * (float)loop / (nLoop);
 864                 GLfloat upperY = height * (float)(loop + 1) / (nLoop);
 865                 GLfloat factor = (topRadius - topThickness) -
 866                         (bottomRadius - bottomThickness);
 867
 868                 /* outside */
 869                 glBegin(GL_QUAD_STRIP);
 870                 for(slice = 0; slice < nSlice; ++slice) {
 871                         glNormal3f(sinCache[slice], 0.0, cosCache[slice]);
 872                         glVertex3f(upperRadius * sinCache[slice], upperY,
 873                                            upperRadius * cosCache[slice]);
 874                         glVertex3f(lowerRadius * sinCache[slice], lowerY,
 875                                            lowerRadius * cosCache[slice]);
 876             polys++;
 877                 }
 878                 glNormal3f(0.0, 0.0, 1.0);
 879                 glVertex3f(0.0, upperY, upperRadius);
 880                 glVertex3f(0.0, lowerY, lowerRadius);
 881         polys++;
 882                 glEnd();
 883
 884                 /* inside */
 885                 lowerRadius = bottomRadius - bottomThickness +
 886                         factor * (float)loop / (nLoop);
 887                 upperRadius = bottomRadius - bottomThickness +
 888                         factor * (float)(loop + 1) / (nLoop);
 889
 890                 glBegin(GL_QUAD_STRIP);
 891                 glNormal3f(0.0, 0.0, -1.0);
 892                 glVertex3f(0.0, upperY, upperRadius);
 893                 glVertex3f(0.0, lowerY, lowerRadius);
 894                 for(slice = lastSlice; slice >= 0; --slice) {
 895                         glNormal3f(-sinCache[slice], 0.0, -cosCache[slice]);
 896                         glVertex3f(upperRadius * sinCache[slice], upperY,
 897                                            upperRadius * cosCache[slice]);
 898                         glVertex3f(lowerRadius * sinCache[slice], lowerY,
 899                                            lowerRadius * cosCache[slice]);
 900             polys++;
 901                 }
 902                 glEnd();
 903         }
 904
 905         /* top */
 906         y = height;
 907         radius = topRadius;
 908         innerRadius = topRadius - topThickness;
 909
 910         glBegin(GL_QUAD_STRIP);
 911         glNormal3f(0.0, 1.0, 0.0);
 912         for(slice = 0; slice < nSlice; ++slice) {
 913                 glVertex3f(innerRadius * sinCache[slice], y,
 914                                    innerRadius * cosCache[slice]);
 915
 916                 glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]);
 917         polys++;
 918         }
 919         glVertex3f(0.0, y, innerRadius);
 920         glVertex3f(0.0, y, radius);
 921         glEnd();
 922     return polys;
 923 }
 924
 925 static int drawPole(GLfloat radius, GLfloat length)
 926 {
 927   return drawTube(radius, radius, radius, radius, length, NSLICE, NLOOPS);
 928 }
 929
 930 static int drawDisk3D(GLdouble inner_radius, GLdouble outer_radius,
 931                       GLdouble height)
 932 {
 933   return drawTube(outer_radius, outer_radius, outer_radius - inner_radius,
 934                   outer_radius - inner_radius, height, NSLICE, NLOOPS);
 935 }
 936
 937 static int drawCuboid(GLfloat length, GLfloat width, GLfloat height)
 938 {
 939         GLfloat xmin = -length / 2.0f;
 940         GLfloat xmax = length / 2.0f;
 941         GLfloat zmin = -width / 2.0f;
 942         GLfloat zmax = width / 2.0f;
 943         GLfloat ymin = 0.0f;
 944         GLfloat ymax = height;
 945     int polys = 0;
 946
 947         glBegin(GL_QUADS);
 948         /* front */
 949         glNormal3fv(front);
 950         glVertex3f(xmin, ymin, zmax);   /* 0 */
 951         glVertex3f(xmax, ymin, zmax);   /* 1 */
 952         glVertex3f(xmax, ymax, zmax);   /* 2 */
 953         glVertex3f(xmin, ymax, zmax);   /* 3 */
 954     polys++;
 955         /* right */
 956         glNormal3fv(right);
 957         glVertex3f(xmax, ymin, zmax);   /* 1 */
 958         glVertex3f(xmax, ymin, zmin);   /* 5 */
 959         glVertex3f(xmax, ymax, zmin);   /* 6 */
 960         glVertex3f(xmax, ymax, zmax);   /* 2 */
 961     polys++;
 962         /* back */
 963         glNormal3fv(back);
 964         glVertex3f(xmax, ymin, zmin);   /* 5 */
 965         glVertex3f(xmin, ymin, zmin);   /* 4 */
 966         glVertex3f(xmin, ymax, zmin);   /* 7 */
 967         glVertex3f(xmax, ymax, zmin);   /* 6 */
 968     polys++;
 969         /* left */
 970         glNormal3fv(left);
 971         glVertex3f(xmin, ymin, zmin);   /* 4 */
 972         glVertex3f(xmin, ymin, zmax);   /* 0 */
 973         glVertex3f(xmin, ymax, zmax);   /* 3 */
 974         glVertex3f(xmin, ymax, zmin);   /* 7 */
 975     polys++;
 976         /* top */
 977         glNormal3fv(up);
 978         glVertex3f(xmin, ymax, zmax);   /* 3 */
 979         glVertex3f(xmax, ymax, zmax);   /* 2 */
 980         glVertex3f(xmax, ymax, zmin);   /* 6 */
 981         glVertex3f(xmin, ymax, zmin);   /* 7 */
 982     polys++;
 983         /* bottom */
 984         glNormal3fv(down);
 985         glVertex3f(xmin, ymin, zmin);   /* 4 */
 986         glVertex3f(xmax, ymin, zmin);   /* 5 */
 987         glVertex3f(xmax, ymin, zmax);   /* 1 */
 988         glVertex3f(xmin, ymin, zmax);   /* 0 */
 989     polys++;
 990         glEnd();
 991     return polys;
 992 }
 993
 994 static int drawDisks(glhcfg *glhanoi)
 995 {
 996         int i;
 997     int polys = 0;
 998
 999         glPushMatrix();
1000         glTranslatef(0.0f, glhanoi->baseHeight, 0.0f);
1001         for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1002                 Disk *disk = &glhanoi->disk[i];
1003                 GLfloat *pos = disk->position;
1004                 GLfloat *rot = disk->rotation;
1005
1006                 glPushMatrix();
1007                 glTranslatef(pos[0], pos[1], pos[2]);
1008                 if(rot[1] != 0.0) {
1009                         glTranslatef(0.0, glhanoi->diskHeight / 2.0, 0.0);
1010                         glRotatef(rot[1], 0.0, 0.0, 1.0);
1011                         glTranslatef(0.0, -glhanoi->diskHeight / 2.0, 0.0);
1012                 }
1013                 glCallList(disk->displayList);
1014         polys += disk->polys;
1015                 glPopMatrix();
1016         }
1017         glPopMatrix();
1018     return polys;
1019 }
1020
1021 static GLfloat getDiskRadius(glhcfg *glhanoi, int i)
1022 {
1023         return ((GLfloat) i + 3.0) * glhanoi->baseLength /
1024                 (2 * 0.95 * glhanoi->numberOfPoles * (glhanoi->numberOfDisks + 3.0));
1025 }
1026
1027 static void initData(glhcfg *glhanoi)
1028 {
1029         GLfloat maxDiskRadius;
1030         int i;
1031
1032         glhanoi->baseLength = BASE_LENGTH;
1033         maxDiskRadius = getDiskRadius(glhanoi, glhanoi->numberOfDisks);
1034         glhanoi->poleRadius = maxDiskRadius / (glhanoi->numberOfDisks + 3.0);
1035         /* fprintf(stderr, "Debug: baseL = %f, maxDiskR = %f, poleR = %f\n",
1036                 glhanoi->baseLength, maxDiskRadius, glhanoi->poleRadius); */
1037         glhanoi->baseWidth = 2.0 * maxDiskRadius;
1038         glhanoi->poleOffset = 2.0 * getDiskRadius(glhanoi, glhanoi->maxDiskIdx);
1039         glhanoi->diskHeight = 2.0 * glhanoi->poleRadius;
1040         glhanoi->baseHeight = 2.0 * glhanoi->poleRadius;
1041         glhanoi->poleHeight = glhanoi->numberOfDisks *
1042                 glhanoi->diskHeight + glhanoi->poleRadius;
1043         /* numberOfMoves only applies if numberOfPoles = 3 */
1044         glhanoi->numberOfMoves = (1 << glhanoi->numberOfDisks) - 1;
1045         glhanoi->boardSize = glhanoi->baseLength * 0.5 * (1.0 + sqrt(5.0));
1046
1047         glhanoi->pole = (Pole *)calloc(glhanoi->numberOfPoles, sizeof(Pole));
1048         checkAllocAndExit(!!glhanoi->pole, "poles");
1049
1050         for(i = 0; i < glhanoi->numberOfPoles; i++) {
1051                 checkAllocAndExit(
1052                         !!(glhanoi->pole[i].data = calloc(glhanoi->numberOfDisks, sizeof(Disk *))),
1053                         "disk stack");
1054                 glhanoi->pole[i].size = glhanoi->numberOfDisks;
1055         }
1056         checkAllocAndExit(
1057                         !!(glhanoi->diskPos = calloc(glhanoi->numberOfDisks, sizeof(double))),
1058                         "diskPos");
1059
1060         glhanoi->the_rotator = make_rotator(0.1, 0.025, 0, 1, 0.005, False);
1061         glhanoi->button_down_p = False;
1062
1063         glhanoi->src = glhanoi->oldsrc = 0;
1064         glhanoi->tmp = glhanoi->oldtmp = 1;
1065         glhanoi->dst = glhanoi->olddst = glhanoi->numberOfPoles - 1;
1066
1067         if (glhanoi->numberOfPoles > 3) {
1068                 glhanoi->solveStackSize = glhanoi->numberOfDisks + 2;
1069                 glhanoi->solveStack = (SubProblem *)calloc(glhanoi->solveStackSize, sizeof(SubProblem));
1070                 checkAllocAndExit(!!glhanoi->solveStack, "solving stack");
1071                 glhanoi->solveStackIdx = 0;
1072         }
1073 }
1074
1075 static void initView(glhcfg *glhanoi)
1076 {
1077         glhanoi->camera[0] = 0.0;
1078         glhanoi->camera[1] = 0.0;
1079         glhanoi->camera[2] = 0.0;
1080         glhanoi->centre[0] = 0.0;
1081         glhanoi->centre[1] = glhanoi->poleHeight * 3.0;
1082         glhanoi->centre[2] = 0.0;
1083 }
1084
1085 /*
1086  * noise_improved.c - based on ImprovedNoise.java
1087  * JAVA REFERENCE IMPLEMENTATION OF IMPROVED NOISE - COPYRIGHT 2002 KEN PERLIN.
1088  */
1089 static double fade(double t)
1090 {
1091         return t * t * t * (t * (t * 6 - 15) + 10);
1092 }
1093
1094 static double grad(int hash, double x, double y, double z)
1095 {
1096         int h = hash & 15;                      /* CONVERT LO 4 BITS OF HASH CODE */
1097         double u = h < 8 ? x : y,       /* INTO 12 GRADIENT DIRECTIONS. */
1098                 v = h < 4 ? y : h == 12 || h == 14 ? x : z;
1099         return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
1100 }
1101
1102 static const int permutation[] = { 151, 160, 137, 91, 90, 15,
1103         131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142,
1104         8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 26,
1105         197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237,
1106         149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71,
1107         134, 139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60,
1108         211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 102, 143,
1109         54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89,
1110         18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 198,
1111         173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118,
1112         126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189,
1113         28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70,
1114         221, 153, 101, 155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108,
1115         110, 79, 113, 224, 232, 178, 185, 112, 104, 218, 246, 97, 228, 251,
1116         34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241, 81, 51, 145,
1117         235, 249, 14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 157, 184,
1118         84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205,
1119         93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61,
1120         156, 180
1121 };
1122
1123 static void initNoise(glhcfg *glhanoi)
1124 {
1125         int i;
1126         for(i = 0; i < 256; i++)
1127                 glhanoi->p[256 + i] = glhanoi->p[i] = permutation[i];
1128 }
1129
1130 static double improved_noise(glhcfg *glhanoi, double x, double y, double z)
1131 {
1132         double u, v, w;
1133         int A, AA, AB, B, BA, BB;
1134         int X = (int)floor(x) & 255,    /* FIND UNIT CUBE THAT */
1135                 Y = (int)floor(y) & 255,        /* CONTAINS POINT. */
1136                 Z = (int)floor(z) & 255;
1137         if(!glhanoi->noise_initted) {
1138                 initNoise(glhanoi);
1139                 glhanoi->noise_initted = 1;
1140         }
1141         x -= floor(x);                          /* FIND RELATIVE X,Y,Z */
1142         y -= floor(y);                          /* OF POINT IN CUBE. */
1143         z -= floor(z);
1144         u  = fade(x),                           /* COMPUTE FADE CURVES */
1145         v  = fade(y),                           /* FOR EACH OF X,Y,Z. */
1146         w  = fade(z);
1147         A  = glhanoi->p[X] + Y;
1148         AA = glhanoi->p[A] + Z;
1149         AB = glhanoi->p[A + 1] + Z,     /* HASH COORDINATES OF */
1150         B  = glhanoi->p[X + 1] + Y;
1151         BA = glhanoi->p[B] + Z;
1152         BB = glhanoi->p[B + 1] + Z;     /* THE 8 CUBE CORNERS, */
1153         return lerp(w, lerp(v, lerp(u, grad(glhanoi->p[AA], x, y, z),/* AND ADD */
1154                                                                 grad(glhanoi->p[BA], x - 1, y, z)),/* BLENDED */
1155                                                 lerp(u, grad(glhanoi->p[AB], x, y - 1, z),/* RESULTS */
1156                                                          grad(glhanoi->p[BB], x - 1, y - 1, z))),/* FROM 8 CORNERS */
1157                                 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 */
1158                                          lerp(u, grad(glhanoi->p[AB + 1], x, y - 1, z - 1),
1159                                                   grad(glhanoi->p[BB + 1], x - 1, y - 1, z - 1))));
1160 }
1161
1162 /*
1163  * end noise_improved.c - based on ImprovedNoise.java
1164  */
1165
1166 struct tex_col_t {
1167         GLuint *colours;
1168         /* GLfloat *points; */
1169         unsigned int ncols;
1170 };
1171 typedef struct tex_col_t tex_col_t;
1172
1173 static GLubyte *makeTexture(glhcfg *glhanoi, int x_size, int y_size, int z_size,
1174                                          GLuint(*texFunc) (glhcfg *, double, double, double,
1175                                                                            tex_col_t *), tex_col_t * colours)
1176 {
1177         int i, j, k;
1178         GLubyte *textureData;
1179         GLuint *texturePtr;
1180         double x, y, z;
1181         double xi, yi, zi;
1182
1183         if((textureData =
1184                 calloc(x_size * y_size * z_size, sizeof(GLuint))) == NULL) {
1185                 return NULL;
1186         }
1187
1188         xi = 1.0 / x_size;
1189         yi = 1.0 / y_size;
1190         zi = 1.0 / z_size;
1191
1192         z = 0.0;
1193         texturePtr = (void *)textureData;
1194         for(k = 0; k < z_size; k++, z += zi) {
1195                 y = 0.0;
1196                 for(j = 0; j < y_size; j++, y += yi) {
1197                         x = 0.0;
1198                         for(i = 0; i < x_size; i++, x += xi) {
1199                                 *texturePtr = texFunc(glhanoi, x, y, z, colours);
1200                                 ++texturePtr;
1201                         }
1202                 }
1203         }
1204         return textureData;
1205 }
1206
1207 static void freeTexCols(tex_col_t*p)
1208 {
1209         free(p->colours);
1210         free(p);
1211 }
1212
1213 static tex_col_t *makeMarbleColours(void)
1214 {
1215         tex_col_t *marbleColours;
1216         int ncols = 2;
1217
1218         marbleColours = malloc(sizeof(tex_col_t));
1219         if(marbleColours == NULL) return NULL;
1220         marbleColours->colours = calloc(sizeof(GLuint), ncols);
1221         if(marbleColours->colours == NULL) return NULL;
1222         marbleColours->ncols = ncols;
1223
1224         marbleColours->colours[0] = 0x3f3f3f3f;
1225         marbleColours->colours[1] = 0xffffffff;
1226
1227         return marbleColours;
1228 }
1229
1230 static double turb(glhcfg *glhanoi, double x, double y, double z, int octaves)
1231 {
1232         int oct, freq = 1;
1233         double r = 0.0;
1234
1235         for(oct = 0; oct < octaves; ++oct) {
1236                 r += fabs(improved_noise(glhanoi, freq * x, freq * y, freq * z)) / freq;
1237                 freq <<= 1;
1238         }
1239         return r / 2.0;
1240 }
1241
1242 static void perturb(glhcfg *glhanoi, double *x, double *y, double *z, double scale)
1243 {
1244         double t = scale * turb(glhanoi, *x, *y, *z, 4);
1245         *x += t;
1246         *y += t;
1247         *z += t;
1248 }
1249
1250 static double f_m(double x, double y, double z)
1251 {
1252         return sin(3.0 * M_PI * x);
1253 }
1254
1255 static GLuint C_m(double x, const tex_col_t * tex_cols)
1256 {
1257         int r = tex_cols->colours[0] & 0xff;
1258         int g = tex_cols->colours[0] >> 8 & 0xff;
1259         int b = tex_cols->colours[0] >> 16 & 0xff;
1260         double factor;
1261         int r1, g1, b1;
1262         x = x - floor(x);
1263
1264         factor = (1.0 + sin(2.0 * M_PI * x)) / 2.0;
1265
1266         r1 = (tex_cols->colours[1] & 0xff);
1267         g1 = (tex_cols->colours[1] >> 8 & 0xff);
1268         b1 = (tex_cols->colours[1] >> 16 & 0xff);
1269
1270         r += (int)(factor * (r1 - r));
1271         g += (int)(factor * (g1 - g));
1272         b += (int)(factor * (b1 - b));
1273
1274         return 0xff000000 | (b << 16) | (g << 8) | r;
1275 }
1276
1277
1278 static GLuint makeMarbleTexture(glhcfg *glhanoi, double x, double y, double z, tex_col_t * colours)
1279 {
1280         perturb(glhanoi, &x, &y, &z, MARBLE_SCALE);
1281         return C_m(f_m(x, y, z), colours);
1282 }
1283
1284 static void setTexture(glhcfg *glhanoi, int n)
1285 {
1286         glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[n]);
1287 }
1288
1289 /* returns 1 on failure, 0 on success */
1290 static int makeTextures(glhcfg *glhanoi)
1291 {
1292         GLubyte *marbleTexture;
1293         tex_col_t *marbleColours;
1294
1295         glGenTextures(N_TEXTURES, glhanoi->textureNames);
1296
1297         if((marbleColours = makeMarbleColours()) == NULL) {
1298                 return 1;
1299         }
1300         if((marbleTexture =
1301                 makeTexture(glhanoi, MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 1,
1302                                         makeMarbleTexture, marbleColours)) == NULL) {
1303                 return 1;
1304         }
1305
1306         glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[0]);
1307         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
1308         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
1309         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
1310         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
1311         glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA,
1312                                  MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 0,
1313                                  GL_RGBA, GL_UNSIGNED_BYTE, marbleTexture);
1314         free(marbleTexture);
1315         freeTexCols(marbleColours);
1316
1317         return 0;
1318 }
1319
1320 static void initFloor(glhcfg *glhanoi)
1321 {
1322         int i, j;
1323         float tileSize = glhanoi->boardSize / BOARD_SQUARES;
1324         float x0, x1, z0, z1;
1325         float tx0, tx1, tz0, tz1;
1326         const float *col = cWhite;
1327         float texIncr = 1.0 / BOARD_SQUARES;
1328
1329     glhanoi->floorpolys = 0;
1330         checkAllocAndExit(!!(glhanoi->floorList = glGenLists(1)), "floor display list");
1331         glNewList(glhanoi->floorList, GL_COMPILE);
1332         x0 = -glhanoi->boardSize / 2.0;
1333         tx0 = 0.0f;
1334         setMaterial(col, cWhite, 128);
1335         setTexture(glhanoi, 0);
1336         glNormal3fv(up);
1337         for(i = 0; i < BOARD_SQUARES; i++, x0 += tileSize, tx0 += texIncr) {
1338                 x1 = x0 + tileSize;
1339                 tx1 = tx0 + texIncr;
1340                 z0 = -glhanoi->boardSize / 2.0;
1341                 tz0 = 0.0f;
1342                 for(j = 0; j < BOARD_SQUARES; j++, z0 += tileSize, tz0 += texIncr) {
1343                         int colIndex = (i + j) & 0x1;
1344
1345                         z1 = z0 + tileSize;
1346                         tz1 = tz0 + texIncr;
1347
1348                         if(colIndex)
1349                                 col = cWhite;
1350                         else
1351                                 col = cBlack;
1352
1353                         setMaterial(col, cWhite, 100);
1354
1355                         glBegin(GL_QUADS);
1356
1357                         glTexCoord2d(tx0, tz0);
1358                         glVertex3f(x0, 0.0, z0);
1359
1360                         glTexCoord2d(tx0, tz1);
1361                         glVertex3f(x0, 0.0, z1);
1362
1363                         glTexCoord2d(tx1, tz1);
1364                         glVertex3f(x1, 0.0, z1);
1365
1366                         glTexCoord2d(tx1, tz0);
1367                         glVertex3f(x1, 0.0, z0);
1368             glhanoi->floorpolys++;
1369                         glEnd();
1370                 }
1371         }
1372         glEndList();
1373 }
1374
1375 static void initTowers(glhcfg *glhanoi)
1376 {
1377         int i;
1378
1379         checkAllocAndExit(!!(glhanoi->baseList = glGenLists(1)), "tower bases display list");
1380
1381         glNewList(glhanoi->baseList, GL_COMPILE);
1382         setMaterial(baseColor, cWhite, 50);
1383     glhanoi->basepolys = drawCuboid(glhanoi->baseLength, glhanoi->baseWidth,
1384                                     glhanoi->baseHeight);
1385         glEndList();
1386
1387         checkAllocAndExit(!!(glhanoi->poleList = glGenLists(1)), "poles display list\n");
1388
1389         glNewList(glhanoi->poleList, GL_COMPILE);
1390         glPushMatrix();
1391         glTranslatef(-glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5f, glhanoi->baseHeight, 0.0f);
1392         setMaterial(poleColor, cWhite, 50);
1393         for (i = 0; i < glhanoi->numberOfPoles; i++) {
1394                 glhanoi->polepolys = drawPole(glhanoi->poleRadius, glhanoi->poleHeight);
1395                 /* poleOffset is based on disk radius. */
1396                 glTranslatef(glhanoi->poleOffset, 0.0, 0.0);
1397         }
1398         glPopMatrix();
1399         glEndList();
1400 }
1401
1402 /* Parameterized hue based on input 0.0 - 1.0. */
1403 static double cfunc(double x)
1404 {
1405 #define COMP <
1406         if(x < 2.0 / 7.0) {
1407                 return (1.0 / 12.0) / (1.0 / 7.0) * x;
1408         }
1409         if(x < 3.0 / 7.0) {
1410                 /* (7x - 1) / 6 */
1411                 return (1.0 + 1.0 / 6.0) * x - 1.0 / 6.0;
1412         }
1413         if(x < 4.0 / 7.0) {
1414                 return (2.0 + 1.0 / 3.0) * x - 2.0 / 3.0;
1415         }
1416         if(x < 5.0 / 7.0) {
1417                 return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1418         }
1419         return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0;
1420 }
1421
1422 static void initDisks(glhcfg *glhanoi)
1423 {
1424         int i;
1425         glhanoi->disk = (Disk *) calloc(glhanoi->numberOfDisks, sizeof(Disk));
1426         checkAllocAndExit(!!glhanoi->disk, "disks");
1427
1428         for(i = glhanoi->maxDiskIdx; i >= 0; i--) {
1429                 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1430                 double f = cfunc((GLfloat) i / (GLfloat) glhanoi->numberOfDisks);
1431                 GLfloat diskColor = f * 360.0;
1432                 GLfloat color[3];
1433                 Disk *disk = &glhanoi->disk[i];
1434
1435                 disk->id = i;
1436                 disk->position[0] = -glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5;
1437                 disk->position[1] = glhanoi->diskHeight * height;
1438                 disk->position[2] = 0.0;
1439                 disk->rotation[0] = 0.0;
1440                 disk->rotation[1] = 0.0;
1441                 disk->rotation[2] = 0.0;
1442                 disk->polys = 0;
1443
1444                 /* make smaller disks move faster */
1445                 disk->speed = lerp(((double)glhanoi->numberOfDisks - i) / glhanoi->numberOfDisks, 1.0, speed);
1446                 /* fprintf(stderr, "disk id: %d, alpha: %0.2f, speed: %0.2f\n", disk->id,
1447                         ((double)(glhanoi->maxDiskIdx - i)) / glhanoi->numberOfDisks, disk->speed); */
1448
1449                 color[0] = diskColor;
1450                 color[1] = 1.0f;
1451                 color[2] = 1.0f;
1452                 HSVtoRGBv(color, color);
1453
1454                 checkAllocAndExit(!!(disk->displayList = glGenLists(1)), "disk display list");
1455                 glNewList(disk->displayList, GL_COMPILE);
1456                 setMaterial(color, cWhite, 100.0);
1457                 disk->polys += drawDisk3D(glhanoi->poleRadius,
1458                                   getDiskRadius(glhanoi, i),
1459                                   glhanoi->diskHeight);
1460                 /*fprintf(stderr, "Debug: disk %d has radius %f\n", i,
1461                         getDiskRadius(glhanoi, i)); */
1462                 glEndList();
1463         }
1464         for(i = glhanoi->maxDiskIdx; i >= 0; --i) {
1465                 GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i);
1466                 int h = glhanoi->maxDiskIdx - i;
1467                 glhanoi->diskPos[h] = glhanoi->diskHeight * height;
1468                 push(glhanoi, glhanoi->src, &glhanoi->disk[i]);
1469         }
1470 }
1471
1472 static void initLights(Bool state)
1473 {
1474         if(state) {
1475                 glLightfv(GL_LIGHT0, GL_POSITION, pos0);
1476                 glLightfv(GL_LIGHT0, GL_AMBIENT, amb0);
1477                 glLightfv(GL_LIGHT0, GL_DIFFUSE, dif0);
1478                 glLightfv(GL_LIGHT0, GL_SPECULAR, spc0);
1479
1480                 glLightfv(GL_LIGHT1, GL_POSITION, pos1);
1481                 glLightfv(GL_LIGHT1, GL_AMBIENT, amb1);
1482                 glLightfv(GL_LIGHT1, GL_DIFFUSE, dif1);
1483                 glLightfv(GL_LIGHT1, GL_SPECULAR, spc1);
1484
1485                 glEnable(GL_LIGHTING);
1486                 glEnable(GL_LIGHT0);
1487                 glEnable(GL_LIGHT1);
1488         } else {
1489                 glDisable(GL_LIGHTING);
1490         }
1491 }
1492
1493 static int drawFloor(glhcfg *glhanoi)
1494 {
1495         glCallList(glhanoi->floorList);
1496     return glhanoi->floorpolys;
1497 }
1498
1499 static int drawTowers(glhcfg *glhanoi)
1500 {
1501         glCallList(glhanoi->baseList);
1502         glCallList(glhanoi->poleList);
1503     return glhanoi->basepolys + glhanoi->polepolys;
1504 }
1505
1506 /* Window management, etc
1507  */
1508 ENTRYPOINT void reshape_glhanoi(ModeInfo * mi, int width, int height)
1509 {
1510         glViewport(0, 0, (GLint) width, (GLint) height);
1511
1512         glMatrixMode(GL_PROJECTION);
1513         glLoadIdentity();
1514         gluPerspective(30.0, (GLdouble) width / (GLdouble) height, 1.0,
1515                                    2 * MAX_CAMERA_RADIUS);
1516
1517         glMatrixMode(GL_MODELVIEW);
1518         glLoadIdentity();
1519
1520         glClear(GL_COLOR_BUFFER_BIT);
1521 }
1522
1523 ENTRYPOINT void init_glhanoi(ModeInfo * mi)
1524 {
1525         glhcfg *glhanoi;
1526         if(!glhanoi_cfg) {
1527                 glhanoi_cfg =
1528                         (glhcfg *) calloc(MI_NUM_SCREENS(mi), sizeof(glhcfg));
1529                 checkAllocAndExit(!!glhanoi_cfg, "configuration");
1530         }
1531
1532         glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1533         glhanoi->glx_context = init_GL(mi);
1534         glhanoi->numberOfDisks = MI_BATCHCOUNT(mi);
1535
1536     if (glhanoi->numberOfDisks <= 1)
1537       glhanoi->numberOfDisks = 3 + (int) BELLRAND(9);
1538
1539         /* magicnumber is a bitfield, so we can't have more than 31 discs
1540            on a system with 4-byte ints. */
1541         if (glhanoi->numberOfDisks >= 8 * sizeof(int))
1542                 glhanoi->numberOfDisks = (8 * sizeof(int)) - 1;
1543
1544         glhanoi->maxDiskIdx = glhanoi->numberOfDisks - 1;
1545
1546         speed = get_float_resource(MI_DISPLAY(mi), "speed", "float");
1547         /* fprintf(stderr, "speed: %0.2f\n", speed); */
1548
1549         glhanoi->numberOfPoles = get_integer_resource(MI_DISPLAY(mi), "poles", "Integer");
1550         /* Set a number of poles from 3 to numberOfDisks + 1, biased toward lower values,
1551                 with probability decreasing linearly. */
1552     if (glhanoi->numberOfPoles <= 2)
1553       glhanoi->numberOfPoles = 3 +
1554                 (int)((1 - sqrt(frand(1.0))) * (glhanoi->numberOfDisks - 1));
1555         /* fprintf(stderr, "Debug: Num disks: %d; num poles: %d\n", glhanoi->numberOfDisks, glhanoi->numberOfPoles); */
1556
1557         glhanoi->wire = MI_IS_WIREFRAME(mi);
1558         glhanoi->light = light;
1559         glhanoi->fog = fog;
1560         glhanoi->texture = texture;
1561
1562         reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
1563
1564         if(glhanoi->wire) {
1565                 glhanoi->light = False;
1566                 glhanoi->fog = False;
1567                 glhanoi->texture = False;
1568         }
1569
1570         initLights(!glhanoi->wire && glhanoi->light);
1571         checkAllocAndExit(!makeTextures(glhanoi), "textures\n");
1572
1573         initData(glhanoi);
1574         initView(glhanoi);
1575         initFloor(glhanoi);
1576         initTowers(glhanoi);
1577         initDisks(glhanoi);
1578
1579         glEnable(GL_DEPTH_TEST);
1580         glEnable(GL_NORMALIZE);
1581         glEnable(GL_CULL_FACE);
1582         glShadeModel(GL_SMOOTH);
1583         if(glhanoi->fog) {
1584                 glClearColor(fogcolor[0], fogcolor[1], fogcolor[2], 1.0);
1585                 glFogi(GL_FOG_MODE, GL_LINEAR);
1586                 glFogfv(GL_FOG_COLOR, fogcolor);
1587                 glFogf(GL_FOG_DENSITY, 0.35f);
1588                 glHint(GL_FOG_HINT, GL_NICEST);
1589                 glFogf(GL_FOG_START, MIN_CAMERA_RADIUS);
1590                 glFogf(GL_FOG_END, MAX_CAMERA_RADIUS / 1.9);
1591                 glEnable(GL_FOG);
1592         }
1593
1594         glhanoi->duration = START_DURATION;
1595         changeState(glhanoi, START);
1596 }
1597
1598 ENTRYPOINT void draw_glhanoi(ModeInfo * mi)
1599 {
1600         glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1601         Display *dpy = MI_DISPLAY(mi);
1602         Window window = MI_WINDOW(mi);
1603
1604         if(!glhanoi->glx_context)
1605                 return;
1606
1607     glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context));
1608
1609         glPolygonMode(GL_FRONT, glhanoi->wire ? GL_LINE : GL_FILL);
1610
1611         glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1612     mi->polygon_count = 0;
1613
1614         glLoadIdentity();
1615
1616         update_glhanoi(glhanoi);
1617         updateView(glhanoi);
1618
1619         if(!glhanoi->wire && glhanoi->texture) {
1620                 glEnable(GL_TEXTURE_2D);
1621         }
1622     mi->polygon_count += drawFloor(glhanoi);
1623         glDisable(GL_TEXTURE_2D);
1624
1625         mi->polygon_count += drawTowers(glhanoi);
1626         mi->polygon_count += drawDisks(glhanoi);
1627
1628         if(mi->fps_p) {
1629                 do_fps(mi);
1630         }
1631         glFinish();
1632
1633         glXSwapBuffers(dpy, window);
1634 }
1635
1636 ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event)
1637 {
1638         glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)];
1639
1640         if(event->xany.type == ButtonPress && event->xbutton.button == Button1) {
1641                 glhanoi->button_down_p = True;
1642                 glhanoi->drag_x = event->xbutton.x;
1643                 glhanoi->drag_y = event->xbutton.y;
1644                 return True;
1645         } else if(event->xany.type == ButtonRelease
1646                           && event->xbutton.button == Button1) {
1647                 glhanoi->button_down_p = False;
1648                 return True;
1649         } else if(event->xany.type == ButtonPress &&
1650                           (event->xbutton.button == Button4
1651                            || event->xbutton.button == Button5)) {
1652                 switch (event->xbutton.button) {
1653                 case Button4:
1654                         glhanoi->camera[2] += 0.01;
1655                         break;
1656                 case Button5:
1657                         glhanoi->camera[2] -= 0.01;
1658                         break;
1659                 default:
1660                         fprintf(stderr,
1661                                         "glhanoi: unknown button in mousewheel handler\n");
1662                 }
1663                 return True;
1664         } else if(event->xany.type == MotionNotify
1665                           && glhanoi_cfg->button_down_p) {
1666                 int x_diff, y_diff;
1667
1668                 x_diff = event->xbutton.x - glhanoi->drag_x;
1669                 y_diff = event->xbutton.y - glhanoi->drag_y;
1670
1671                 glhanoi->camera[0] = (float)x_diff / (float)MI_WIDTH(mi);
1672                 glhanoi->camera[1] = (float)y_diff / (float)MI_HEIGHT(mi);
1673
1674                 return True;
1675         }
1676         return False;
1677 }
1678
1679 ENTRYPOINT void release_glhanoi(ModeInfo * mi)
1680 {
1681         if(glhanoi_cfg != NULL) {
1682                 int screen;
1683                 for(screen = 0; screen < MI_NUM_SCREENS(mi); screen++) {
1684                         int i;
1685                         int j;
1686                         glhcfg *glh = &glhanoi_cfg[screen];
1687                         glDeleteLists(glh->floorList, 1);
1688                         glDeleteLists(glh->baseList, 1);
1689                         glDeleteLists(glh->poleList, 1);
1690                         glDeleteLists(glh->textureNames[0], 2);
1691                         for(j = 0; j < glh->numberOfDisks; ++j) {
1692                                 glDeleteLists(glh->disk[j].displayList, 1);
1693                         }
1694                         free(glh->disk);
1695                         for(i = 0; i < glh->numberOfPoles; i++) {
1696                                 if(glh->pole[i].data != NULL) {
1697                                         free(glh->pole[i].data);
1698                                 }
1699                         }
1700                 }
1701         }
1702         free(glhanoi_cfg);
1703         glhanoi_cfg = NULL;
1704 }
1705
1706 XSCREENSAVER_MODULE ("GLHanoi", glhanoi)
1707
1708 #endif                                                  /* USE_GL */