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

   1 /* hilbert, Copyright (c) 2011-2014 Jamie Zawinski <jwz@jwz.org>
   2  *
   3  * Permission to use, copy, modify, distribute, and sell this software and its
   4  * documentation for any purpose is hereby granted without fee, provided that
   5  * the above copyright notice appear in all copies and that both that
   6  * copyright notice and this permission notice appear in supporting
   7  * documentation.  No representations are made about the suitability of this
   8  * software for any purpose.  It is provided "as is" without express or
   9  * implied warranty.
  10  *
  11  * 2D and 3D Hilbert space-filling curves.
  12  *
  13  * Inspired by "Visualizing Hilbert Curves" by Nelson Max, 1998:
  14  * https://e-reports-ext.llnl.gov/pdf/234149.pdf
  15  */
  16
  17 #define DEFAULTS        "*delay:        30000       \n" \
  18                         "*count:        30          \n" \
  19                         "*showFPS:      False       \n" \
  20                         "*wireframe:    False       \n" \
  21                         "*geometry:     800x800\n" \
  22                         "*suppressRotationAnimation: True\n" \
  23
  24 # define refresh_hilbert 0
  25 # define release_hilbert 0
  26 #undef countof
  27 #define countof(x) (sizeof((x))/sizeof((*x)))
  28
  29 #include "xlockmore.h"
  30 #include "colors.h"
  31 #include "sphere.h"
  32 #include "tube.h"
  33 #include "rotator.h"
  34 #include "gltrackball.h"
  35 #include <ctype.h>
  36
  37 #ifdef USE_GL /* whole file */
  38
  39
  40 #define DEF_SPIN        "True"
  41 #define DEF_WANDER      "False"
  42 #define DEF_SPEED       "1.0"
  43 #define DEF_MODE        "random"
  44 #define DEF_ENDS        "random"
  45 #define DEF_MAX_DEPTH   "5"
  46 #define DEF_THICKNESS   "0.25"
  47
  48 #define PAUSE_TICKS 180
  49
  50 typedef struct {
  51   double x,y,z;
  52 } XYZ;
  53
  54 typedef struct {
  55   unsigned short x,y,z;
  56 } XYZb;
  57
  58 typedef struct {
  59   int size;
  60   XYZb *values;         /* assume max depth of 20 (2^16 on each side) */
  61 } hilbert_cache;
  62
  63
  64 static int dlist_faces[] = { 20, 10, 8, 4, 3 };
  65
  66
  67 typedef struct {
  68   GLXContext *glx_context;
  69   rotator *rot, *rot2;
  70   trackball_state *trackball;
  71   Bool button_down_p;
  72   Bool twodee_p;
  73   Bool closed_p;
  74   int ncolors;
  75   XColor *colors;
  76
  77   int depth;
  78   int depth_tick;
  79
  80   GLfloat path_start, path_end;
  81   int path_tick;
  82   int pause;
  83   GLfloat diam;
  84
  85   hilbert_cache **caches;       /* filled lazily */
  86
  87   GLuint dlists   [40][2];      /* we don't actually alloc all of these */
  88   int dlist_polys [40][2];
  89
  90 } hilbert_configuration;
  91
  92 static hilbert_configuration *bps = NULL;
  93
  94 static Bool do_spin;
  95 static GLfloat speed;
  96 static Bool do_wander;
  97 static char *mode_str;
  98 static char *ends_str;
  99 static int max_depth;
 100 static GLfloat thickness;
 101
 102 static XrmOptionDescRec opts[] = {
 103   { "-spin",      ".spin",     XrmoptionNoArg, "True"   },
 104   { "+spin",      ".spin",     XrmoptionNoArg, "False"  },
 105   { "-speed",     ".speed",    XrmoptionSepArg, 0       },
 106   { "-wander",    ".wander",   XrmoptionNoArg, "True"   },
 107   { "+wander",    ".wander",   XrmoptionNoArg, "False"  },
 108   { "-mode",      ".mode",     XrmoptionSepArg, 0       },
 109   { "-2d",        ".mode",     XrmoptionNoArg, "2D"     },
 110   { "-3d",        ".mode",     XrmoptionNoArg, "3D"     },
 111   { "-ends",      ".ends",     XrmoptionSepArg, 0       },
 112   { "-closed",    ".ends",     XrmoptionNoArg, "closed" },
 113   { "-open",      ".ends",     XrmoptionNoArg, "open"   },
 114   { "-max-depth", ".maxDepth", XrmoptionSepArg, 0       },
 115   { "-thickness", ".thickness",XrmoptionSepArg, 0       },
 116 };
 117
 118 static argtype vars[] = {
 119   {&do_spin,   "spin",     "Spin",     DEF_SPIN,      t_Bool},
 120   {&do_wander, "wander",   "Wander",   DEF_WANDER,    t_Bool},
 121   {&speed,     "speed",    "Speed",    DEF_SPEED,     t_Float},
 122   {&mode_str,  "mode",     "Mode",     DEF_MODE,      t_String},
 123   {&ends_str,  "ends",     "Ends",     DEF_ENDS,      t_String},
 124   {&max_depth, "maxDepth", "MaxDepth", DEF_MAX_DEPTH, t_Int},
 125   {&thickness, "thickness","Thickness",DEF_THICKNESS, t_Float},
 126 };
 127
 128 ENTRYPOINT ModeSpecOpt hilbert_opts = {countof(opts), opts, countof(vars), vars, NULL};
 129
 130
 131 /* 2D Hilbert, and closed-loop variant.
 132  */
 133
 134 /* These arrays specify which bits of the T index contribute to the
 135    X, Y and Z values.  Higher order bits are defined recursively.
 136  */
 137 static const int xbit2d[4] = { 0, 0, 1, 1 };
 138 static const int ybit2d[4] = { 0, 1, 1, 0 };
 139
 140 static const int xbit3d[8] = { 0,0,0,0,1,1,1,1 };
 141 static const int ybit3d[8] = { 0,1,1,0,0,1,1,0 };
 142 static const int zbit3d[8] = { 0,0,1,1,1,1,0,0 };
 143
 144 /* These matrixes encapsulate the necessary reflection and translation
 145    of each 4 sub-squares or 8 sub-cubes.  The r2d and r3d arrays are
 146    the normal Hilbert descent, and the s2d and s3d arrays are the
 147    modified curve used for only level 0 of a closed-form path.
 148  */
 149
 150 static int r2d[4][2][2] = {
 151   /*      _    _
 152          | |..| |
 153          :_    _:
 154           _|  |_
 155
 156   */
 157   {{ 0, 1},
 158    { 1, 0}},
 159   {{ 1, 0},
 160    { 0, 1}},
 161   {{ 1, 0},
 162    { 0, 1}},
 163   {{ 0,-1},
 164    {-1, 0}},
 165 };
 166
 167 static int s2d[4][2][2] = {
 168   /*      __    __
 169          |  |..|  |     Used for outermost iteration only, in "closed" mode
 170          :   ..   :
 171          |__|  |__|
 172
 173   */
 174   {{-1, 0},
 175    { 0,-1}},
 176   {{ 1, 0},
 177    { 0, 1}},
 178   {{ 1, 0},
 179    { 0, 1}},
 180   {{-1, 0},
 181    { 0,-1}},
 182 };
 183
 184
 185 static int r3d[8][3][3] = {
 186   /*
 187           /|      /|
 188          / |     / |
 189         /__|____/  |
 190            |       |
 191           /       /
 192          /       /
 193   */
 194  {{ 0, 1, 0},
 195   { 1, 0, 0},
 196   { 0, 0, 1}},
 197  {{ 0, 0, 1},
 198   { 0, 1, 0},
 199   { 1, 0, 0}},
 200  {{ 1, 0, 0},
 201   { 0, 1, 0},
 202   { 0, 0, 1}},
 203  {{ 0, 0,-1},
 204   {-1, 0, 0},
 205   { 0, 1, 0}},
 206  {{ 0, 0, 1},
 207   { 1, 0, 0},
 208   { 0, 1, 0}},
 209  {{ 1, 0, 0},
 210   { 0, 1, 0},
 211   { 0, 0, 1}},
 212  {{ 0, 0,-1},
 213   { 0, 1, 0},
 214   {-1, 0, 0}},
 215  {{ 0,-1, 0},
 216   {-1, 0, 0},
 217   { 0, 0, 1}},
 218 };
 219
 220
 221 static int s3d[8][3][3] = {
 222   /*
 223           /|      /|    Used for outermost iteration only, in "closed" mode
 224          / |     / |
 225         /__|____/  |
 226            |       |
 227           /       /
 228          /_______/
 229   */
 230  {{-1, 0, 0},
 231   { 0, 0,-1},
 232   { 0, 1, 0}},
 233  {{ 0, 0, 1},
 234   { 0, 1, 0},
 235   { 1, 0, 0}},
 236  {{ 1, 0, 0},
 237   { 0, 1, 0},
 238   { 0, 0, 1}},
 239  {{ 0, 0,-1},
 240   {-1, 0, 0},
 241   { 0, 1, 0}},
 242  {{ 0, 0, 1},
 243   { 1, 0, 0},
 244   { 0, 1, 0}},
 245  {{ 1, 0, 0},
 246   { 0, 1, 0},
 247   { 0, 0, 1}},
 248  {{ 0, 0,-1},
 249   { 0, 1, 0},
 250   {-1, 0, 0}},
 251
 252  {{-1, 0, 0},
 253   { 0, 0,-1},
 254   { 0, 1, 0}},
 255 };
 256
 257
 258
 259 /* Matrix utilities
 260  */
 261
 262 static void
 263 matrix_times_vector2d (int m[2][2], int v[2], int dest[2])
 264 {
 265   dest[0] = m[0][0]*v[0] + m[0][1]*v[1];
 266   dest[1] = m[1][0]*v[0] + m[1][1]*v[1];
 267 }
 268
 269 static void
 270 matrix_times_vector3d (int m[3][3], int v[3], int dest[3])
 271 {
 272   dest[0] = m[0][0]*v[0] + m[0][1]*v[1] + m[0][2]*v[2];
 273   dest[1] = m[1][0]*v[0] + m[1][1]*v[1] + m[1][2]*v[2];
 274   dest[2] = m[2][0]*v[0] + m[2][1]*v[1] + m[2][2]*v[2];
 275 }
 276
 277
 278 static void
 279 matrix_multiply2d (int m1[2][2], int m2[2][2], int dest[2][2])
 280 {
 281   dest[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
 282   dest[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
 283   dest[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
 284   dest[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
 285 }
 286
 287 static void
 288 matrix_multiply3d (int m1[3][3], int m2[3][3], int dest[3][3])
 289 {
 290   int i, j, k;
 291   for (i = 0; i < 3; i++)
 292     for (j = 0; j < 3; j++)
 293       {
 294         dest[i][j] = 0;
 295         for (k = 0; k < 3; k++)
 296           dest[i][j] += m1[i][k] * m2[k][j];
 297       }
 298 }
 299
 300 static void
 301 identity_matrix2d (int m[2][2])
 302 {
 303   m[0][0] = m[1][1] = 1;
 304   m[0][1] = m[1][0] = 0;
 305 }
 306
 307 static void
 308 identity_matrix3d (int m[3][3])
 309 {
 310   m[0][0] = m[1][1] = m[2][2] = 1;
 311   m[0][1] = m[0][2] = m[1][0] = m[1][2] = m[2][0] = m[2][1] = 0;
 312 }
 313
 314
 315 static void
 316 matrix_copy2d (int src[2][2], int dest[2][2])
 317 {
 318   int i, j;
 319   for (i = 0; i < 2; i++)
 320     for (j = 0; j < 2; j++)
 321       dest[i][j] = src[i][j];
 322 }
 323
 324
 325 static void
 326 matrix_copy3d (int src[3][3], int dest[3][3])
 327 {
 328   int i, j;
 329   for (i = 0; i < 3; i++)
 330     for (j = 0; j < 3; j++)
 331       dest[i][j] = src[i][j];
 332 }
 333
 334
 335 /* 2D and 3D Hilbert:
 336    Given an index T along the curve, return the XY or XYZ coordinates.
 337    N is depth of the curve.
 338  */
 339
 340 static void
 341 t_to_xy (int n, int t, int *x, int *y, Bool closed_p)
 342 {
 343   int k, rt[2][2], rq[2][2], va[2], vb[2];
 344   identity_matrix2d(rt);
 345   *x = *y = 0;
 346
 347   for (k = n-1; k >= 0; k--)
 348     {
 349       int j = 3 & (t >> (2*k));
 350       va[0] = 2 * xbit2d[j] - 1;
 351       va[1] = 2 * ybit2d[j] - 1;
 352       matrix_times_vector2d (rt, va, vb);
 353       *x += ((vb[0] + 1) / 2) << k;
 354       *y += ((vb[1] + 1) / 2) << k;
 355       if (k > 0)
 356         {
 357           matrix_copy2d (rt, rq);
 358           if (k == n-1 && closed_p)
 359             matrix_multiply2d (rq, s2d[j], rt);
 360           else
 361             matrix_multiply2d (rq, r2d[j], rt);
 362         }
 363     }
 364 }
 365
 366
 367 static void
 368 t_to_xyz (int n, int t, int *x, int *y, int *z, Bool closed_p)
 369 {
 370   int k, rt[3][3], rq[3][3], va[3], vb[3];
 371   identity_matrix3d(rt);
 372   *x = *y = *z = 0;
 373
 374   for (k = n-1; k >= 0; k--)
 375     {
 376       int j = 7 & (t >> (3*k));
 377       va[0] = 2 * xbit3d[j] - 1;
 378       va[1] = 2 * ybit3d[j] - 1;
 379       va[2] = 2 * zbit3d[j] - 1;
 380       matrix_times_vector3d (rt, va, vb);
 381       *x += ((vb[0] + 1) / 2) << k;
 382       *y += ((vb[1] + 1) / 2) << k;
 383       *z += ((vb[2] + 1) / 2) << k;
 384       if (k > 0)
 385         {
 386           matrix_copy3d (rt, rq);
 387           if (k == n-1 && closed_p)
 388             matrix_multiply3d (rq, s3d[j], rt);
 389           else
 390             matrix_multiply3d (rq, r3d[j], rt);
 391         }
 392     }
 393 }
 394
 395
 396 /* Rendering the curve
 397  */
 398
 399
 400 /* Draw a sphere at the intersection of two tubes, to round off
 401    the connection between them.  Use one of our cache display lists
 402    of unit spheres in various sizes.
 403  */
 404 static int
 405 draw_joint (ModeInfo *mi, XYZ p, GLfloat diam, int faces, int wire)
 406 {
 407   hilbert_configuration *bp = &bps[MI_SCREEN(mi)];
 408   int i;
 409   diam *= 0.99;  /* try to clean up the edges a bit */
 410
 411   if (faces <= 4) return 0;  /* too small to see */
 412
 413   glPushMatrix();
 414   glTranslatef (p.x, p.y, p.z);
 415   glScalef (diam, diam, diam);
 416
 417   /*  i = unit_sphere (faces, faces, wire);*/
 418
 419   /* if (!bp->dlists[faces][0]) abort(); */
 420   /* if (!bp->dlist_polys[faces][0]) abort(); */
 421
 422   glCallList (bp->dlists[faces][0]);
 423   i = bp->dlist_polys[faces][0];
 424   glPopMatrix();
 425   return i;
 426 }
 427
 428
 429 /* Draw a tube, and associated end caps.  Use one of our cache display lists
 430    of unit tubes in various sizes.  Pick the resolution of the tube based
 431    on how large it's being drawn.  It's ok to get chunkier if the thing is
 432    only a few pixels wide on the screen.
 433  */
 434 static Bool
 435 draw_segment (ModeInfo *mi,
 436               XYZ p0, XYZ p1,           /* from, to */
 437               int t, int end_t,         /* value and range */
 438               GLfloat path_start, GLfloat path_end,     /* clipping */
 439               Bool head_cap_p,
 440               int *last_colorP)
 441 {
 442   hilbert_configuration *bp = &bps[MI_SCREEN(mi)];
 443
 444   double t0 = (double) (t-1) / end_t;   /* ratio of p[01] along curve */
 445   double t1 = (double) t / end_t;
 446
 447   int wire = MI_IS_WIREFRAME(mi);
 448   int owire = wire;
 449   GLfloat dd = bp->diam;
 450   int faces;
 451
 452   if (path_start >= t1)  /* whole segment is before clipping region */
 453     return False;
 454   if (path_end < t0)     /* whole segment is after clipping region */
 455     return False;
 456
 457
 458   if (bp->twodee_p) dd *= 2;   /* more polys in 2D mode */
 459
 460   faces = (dd > 0.040 ? dlist_faces[0] :
 461            dd > 0.020 ? dlist_faces[1] :
 462            dd > 0.010 ? dlist_faces[2] :
 463            dd > 0.005 ? dlist_faces[3] :
 464            dd > 0.002 ? dlist_faces[4] :
 465            1);
 466
 467   /* In 2d mode, we can drop into wireframe mode and it still looks ok... */
 468   if (faces == 1)
 469     {
 470       if (bp->twodee_p)
 471         wire = True;
 472       else
 473         faces = 3;
 474     }
 475
 476   if (wire && !owire)
 477     {
 478       glDisable (GL_DEPTH_TEST);
 479       glDisable (GL_CULL_FACE);
 480       glDisable (GL_LIGHTING);
 481     }
 482
 483   if (t0 < path_start)
 484     {
 485       XYZ p;
 486       GLfloat seg_range = t1 - t0;
 487       GLfloat clip_range = path_start - t0;
 488       GLfloat ratio = clip_range / seg_range;
 489       p.x = p0.x + ((p1.x - p0.x) * ratio);
 490       p.y = p0.y + ((p1.y - p0.y) * ratio);
 491       p.z = p0.z + ((p1.z - p0.z) * ratio);
 492       p0 = p;
 493     }
 494
 495   if (t1 > path_end)
 496     {
 497       XYZ p;
 498       GLfloat seg_range = t1 - t0;
 499       GLfloat clip_range = path_end - t0;
 500       GLfloat ratio = clip_range / seg_range;
 501       p.x = p0.x + ((p1.x - p0.x) * ratio);
 502       p.y = p0.y + ((p1.y - p0.y) * ratio);
 503       p.z = p0.z + ((p1.z - p0.z) * ratio);
 504       p1 = p;
 505     }
 506
 507   if (p0.x == p1.x &&
 508       p0.y == p1.y &&
 509       p0.z == p1.z)
 510     return False;
 511
 512   {
 513     int segs = bp->ncolors * (t1 - t0);
 514     int i;
 515     XYZ p0b, p1b;
 516
 517     if (segs < 1) segs = 1;
 518
 519     for (i = 0; i < segs; i++)
 520       {
 521         int j = i + 1;
 522         GLfloat color[4] = {0.0, 0.0, 0.0, 1.0};
 523         GLfloat t0b;
 524         int c;
 525
 526         p0b.x = p0.x + i * ((p1.x - p0.x) / segs);
 527         p0b.y = p0.y + i * ((p1.y - p0.y) / segs);
 528         p0b.z = p0.z + i * ((p1.z - p0.z) / segs);
 529
 530         p1b.x = p0.x + j * ((p1.x - p0.x) / segs);
 531         p1b.y = p0.y + j * ((p1.y - p0.y) / segs);
 532         p1b.z = p0.z + j * ((p1.z - p0.z) / segs);
 533
 534
 535
 536         /* #### this isn't quite right */
 537         t0b = t0 + i * (t1 - t0) / segs;
 538
 539         c = bp->ncolors * t0b;
 540         if (c >= bp->ncolors) c = bp->ncolors-1;
 541
 542         /* Above depth 6, was spending 5% of the time in glMateralfv,
 543            so only set the color if it's different. */
 544
 545         if (c != *last_colorP)
 546           {
 547             color[0] = bp->colors[c].red   / 65536.0;
 548             color[1] = bp->colors[c].green / 65536.0;
 549             color[2] = bp->colors[c].blue  / 65536.0;
 550             if (wire)
 551               glColor3fv (color);
 552             else
 553               glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color);
 554             *last_colorP = c;
 555           }
 556
 557
 558         if (wire)
 559           {
 560             glBegin (GL_LINES);
 561             glVertex3f (p0b.x, p0b.y, p0b.z);
 562             glVertex3f (p1b.x, p1b.y, p1b.z);
 563             glEnd ();
 564             mi->polygon_count++;
 565           }
 566         else
 567           {
 568             /* mi->polygon_count += tube (p0b.x, p0b.y, p0b.z,
 569                                           p1b.x, p1b.y, p1b.z,
 570                                           bp->diam, 0, faces, True,
 571                                           0, wire);
 572              */
 573
 574             /* Render a rotated and scaled prefab unit tube.
 575
 576                There's probably a slightly more concise way to do this,
 577                but since they're all at right angles at least we don't
 578                have to use atan().
 579              */
 580             GLfloat s;
 581             glPushMatrix();
 582             glTranslatef (p0b.x, p0b.y, p0b.z);
 583
 584             if (p1b.x > p0b.x)
 585               {
 586                 s = p1b.x - p0b.x;
 587               }
 588             else if (p1b.x < p0b.x)
 589               {
 590                 glRotatef (180, 0, 0, 1);
 591                 s = p0b.x - p1b.x;
 592               }
 593             else if (p1b.y > p0b.y) {
 594                 glRotatef (90, 0, 0, 1);
 595                 s = p1b.y - p0b.y;
 596               }
 597             else if (p1b.y < p0b.y)
 598               {
 599                 glRotatef (-90, 0, 0, 1);
 600                 s = p0b.y - p1b.y;
 601               }
 602             else if (p1b.z > p0b.z)
 603               {
 604                 glRotatef (-90, 0, 1, 0);
 605                 s = p1b.z - p0b.z;
 606               }
 607             else /* (p1b.z < p0b.z) */
 608               {
 609                 glRotatef (90, 0, 1, 0);
 610                 s = p0b.z - p1b.z;
 611               }
 612
 613             glScalef (s, bp->diam, bp->diam);
 614             glCallList (bp->dlists[faces][1]);
 615             mi->polygon_count += bp->dlist_polys[faces][1];
 616             glPopMatrix();
 617
 618
 619             /* If this is the bleeding edge, cap it too. */
 620             if (head_cap_p) {
 621               mi->polygon_count += draw_joint (mi, p0b, bp->diam, faces, wire);
 622               head_cap_p = False;
 623             }
 624           }
 625       }
 626
 627     /* If the path is closed, close it.  This segment doesn't animate
 628        like the others, but, oh well.
 629      */
 630     if (! wire)
 631       mi->polygon_count += draw_joint (mi, p1b, bp->diam, faces, wire);
 632   }
 633
 634   return True;
 635 }
 636
 637
 638 static void
 639 mem(void)
 640 {
 641   fprintf (stderr, "%s: out of memory\n", progname);
 642   exit (1);
 643 }
 644
 645
 646 /* Render the whole thing, but omit segments that lie outside of
 647    the path_start and path_end ratios.
 648  */
 649 static void
 650 hilbert (ModeInfo *mi, int size, GLfloat path_start, GLfloat path_end)
 651 {
 652   hilbert_configuration *bp = &bps[MI_SCREEN(mi)];
 653   int wire = MI_IS_WIREFRAME(mi);
 654
 655   GLfloat w = pow(2, size);
 656   int end_t = (bp->twodee_p ? w * w : w * w * w);
 657
 658   XYZ prev = { 0, };
 659   XYZ first = { 0, };
 660   Bool first_p = False;
 661   Bool any_p = False;
 662   int t;
 663   Bool fill_cache_p = False;
 664   hilbert_cache *cc;
 665   int last_color = -1;
 666
 667   /* Do this here since at higher resolutions, we turn wireframe on
 668      and off. */
 669
 670   if (! wire)
 671     {
 672       glEnable (GL_NORMALIZE);
 673       glEnable (GL_DEPTH_TEST);
 674       glEnable (GL_CULL_FACE);
 675       glEnable (GL_LIGHTING);
 676       glEnable (GL_POLYGON_OFFSET_FILL);
 677     }
 678
 679
 680   if (!bp->caches)
 681     {
 682       bp->caches = (hilbert_cache **)
 683         calloc (max_depth + 2, sizeof (*bp->caches));
 684       if (!bp->caches) mem();
 685       fill_cache_p = True;
 686     }
 687
 688   cc = bp->caches[size];
 689   if (! cc)
 690     {
 691       cc = (hilbert_cache *) calloc (1, sizeof (*cc));
 692       cc->values = (XYZb *) calloc (end_t + 1, sizeof (*cc->values));
 693       if (!cc->values) mem();
 694       cc->size = end_t;
 695       bp->caches[size] = cc;
 696       fill_cache_p = True;
 697     }
 698
 699   for (t = 0; t < end_t; t++)
 700     {
 701       int x, y, z;
 702       XYZ c;
 703       XYZb *cb;
 704
 705       if (!fill_cache_p)
 706         {
 707           cb = &cc->values[t];
 708           x = cb->x;
 709           y = cb->y;
 710           z = cb->z;
 711         }
 712       else
 713         {
 714           if (!bp->twodee_p)
 715             t_to_xyz (size, t, &x, &y, &z, bp->closed_p);
 716           else
 717             {
 718               t_to_xy (size, t, &x, &y, bp->closed_p);
 719               z = w/2;
 720             }
 721           cb = &cc->values[t];
 722           cb->x = x;
 723           cb->y = y;
 724           cb->z = z;
 725         }
 726
 727       c.x = (GLfloat) x / w - 0.5;
 728       c.y = (GLfloat) y / w - 0.5;
 729       c.z = (GLfloat) z / w - 0.5;
 730
 731       /* #### We could save some polygons by not drawing the spheres
 732          between colinear segments. */
 733
 734       if (t > 0) {
 735         if (draw_segment (mi, prev, c, t, end_t, path_start, path_end, !any_p,
 736                           &last_color))
 737           any_p = True;
 738       }
 739       prev = c;
 740       if (! first_p) {
 741         first = c;
 742         first_p = True;
 743       }
 744     }
 745
 746   if (bp->closed_p && path_end >= 1.0) {
 747     draw_segment (mi, prev, first, t, end_t, path_start, path_end, !any_p,
 748                   &last_color);
 749   }
 750 }
 751
 752
 753
 754 /* Window management, etc
 755  */
 756 ENTRYPOINT void
 757 reshape_hilbert (ModeInfo *mi, int width, int height)
 758 {
 759   GLfloat h = (GLfloat) height / (GLfloat) width;
 760
 761   glViewport (0, 0, (GLint) width, (GLint) height);
 762
 763   glMatrixMode(GL_PROJECTION);
 764   glLoadIdentity();
 765   gluPerspective (30.0, 1/h, 1.0, 100.0);
 766
 767   glMatrixMode(GL_MODELVIEW);
 768   glLoadIdentity();
 769   gluLookAt( 0.0, 0.0, 30.0,
 770              0.0, 0.0, 0.0,
 771              0.0, 1.0, 0.0);
 772
 773 # ifdef HAVE_MOBILE     /* Keep it the same relative size when rotated. */
 774   {
 775     int o = (int) current_device_rotation();
 776     if (o != 0 && o != 180 && o != -180)
 777       glScalef (1/h, 1/h, 1/h);
 778   }
 779 # endif
 780
 781   glClear(GL_COLOR_BUFFER_BIT);
 782 }
 783
 784
 785 ENTRYPOINT Bool
 786 hilbert_handle_event (ModeInfo *mi, XEvent *event)
 787 {
 788   hilbert_configuration *bp = &bps[MI_SCREEN(mi)];
 789
 790   if (gltrackball_event_handler (event, bp->trackball,
 791                                  MI_WIDTH (mi), MI_HEIGHT (mi),
 792                                  &bp->button_down_p))
 793     return True;
 794   else if (event->xany.type == KeyPress)
 795     {
 796       KeySym keysym;
 797       char c = 0;
 798       XLookupString (&event->xkey, &c, 1, &keysym, 0);
 799       if (c == '+' || c == '=' ||
 800           keysym == XK_Up || keysym == XK_Right || keysym == XK_Next)
 801         {
 802           bp->depth++;
 803           if (bp->depth > max_depth) bp->depth = max_depth;
 804           return True;
 805         }
 806       else if (c == '-' || c == '_' ||
 807                keysym == XK_Down || keysym == XK_Left || keysym == XK_Prior)
 808         {
 809           bp->depth--;
 810           if (bp->depth < 1) bp->depth = 1;
 811           return True;
 812         }
 813       else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
 814         {
 815           bp->depth += bp->depth_tick;
 816           if (bp->depth > max_depth-1)
 817             {
 818               bp->depth = max_depth;
 819               bp->depth_tick = -1;
 820             }
 821           else if (bp->depth <= 1)
 822             {
 823               bp->depth = 1;
 824               bp->depth_tick = 1;
 825             }
 826           return True;
 827         }
 828     }
 829
 830   return False;
 831 }
 832
 833
 834 ENTRYPOINT void
 835 init_hilbert (ModeInfo *mi)
 836 {
 837   hilbert_configuration *bp;
 838   int wire = MI_IS_WIREFRAME(mi);
 839   int i;
 840
 841   MI_INIT (mi, bps, NULL);
 842
 843   bp = &bps[MI_SCREEN(mi)];
 844
 845   bp->depth      = 2;
 846   bp->depth_tick = 1;
 847   bp->path_start = 0.0;
 848   bp->path_end   = 0.0;
 849   bp->path_tick  = 1;
 850
 851   if (thickness < 0.01) thickness = 0.01;
 852   if (thickness > 1.0) thickness = 1.0;
 853
 854   if (speed <= 0) speed = 0.0001;
 855   if (max_depth < 2) max_depth = 2;
 856   if (max_depth > 20) max_depth = 20;  /* hard limit due to hilbert_cache */
 857
 858   if (bp->depth > max_depth-1) bp->depth = max_depth-1;
 859
 860   bp->glx_context = init_GL(mi);
 861
 862   reshape_hilbert (mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 863
 864   if (!wire)
 865     {
 866       GLfloat pos[4] = {1.0, 1.0, 1.0, 0.0};
 867       GLfloat amb[4] = {0.0, 0.0, 0.0, 1.0};
 868       GLfloat dif[4] = {1.0, 1.0, 1.0, 1.0};
 869       GLfloat spc[4] = {0.0, 1.0, 1.0, 1.0};
 870
 871       glEnable (GL_LIGHTING);
 872       glEnable (GL_LIGHT0);
 873
 874       glLightfv(GL_LIGHT0, GL_POSITION, pos);
 875       glLightfv(GL_LIGHT0, GL_AMBIENT,  amb);
 876       glLightfv(GL_LIGHT0, GL_DIFFUSE,  dif);
 877       glLightfv(GL_LIGHT0, GL_SPECULAR, spc);
 878     }
 879
 880   {
 881     double spin_speed   = 0.04;
 882     double tilt_speed   = spin_speed / 10;
 883     double wander_speed = 0.008;
 884     double spin_accel   = 0.01;
 885
 886     bp->rot = make_rotator (do_spin ? spin_speed : 0,
 887                             do_spin ? spin_speed : 0,
 888                             do_spin ? spin_speed : 0,
 889                             spin_accel,
 890                             do_wander ? wander_speed : 0,
 891                             do_spin);
 892     bp->rot2 = make_rotator (0, 0, 0, 0, tilt_speed, True);
 893     bp->trackball = gltrackball_init (True);
 894   }
 895
 896   if (mode_str && !strcasecmp(mode_str, "2d"))
 897     bp->twodee_p = True;
 898   else if (mode_str && (!strcasecmp(mode_str, "3d")))
 899     bp->twodee_p = False;
 900   else
 901     {
 902       if (! (mode_str && !strcasecmp(mode_str, "random")))
 903         fprintf (stderr, "%s: 'mode' must be '2d', '3d', or 'random'\n",
 904                  progname);
 905       bp->twodee_p = ((random() % 3) == 0);
 906     }
 907
 908
 909   if (ends_str && (!strcasecmp(ends_str, "closed")))
 910     bp->closed_p = True;
 911   else if (ends_str && (!strcasecmp(ends_str, "open")))
 912     bp->closed_p = False;
 913   else
 914     {
 915       if (! (ends_str && !strcasecmp(ends_str, "random")))
 916         fprintf (stderr, "%s: 'ends' must be 'open', 'closed', or 'random'\n",
 917                  progname);
 918       bp->closed_p = ((random() % 3) != 0);
 919     }
 920
 921
 922   /* More colors results in more polygons (more tube segments) so keeping
 923      this small is worthwhile. */
 924   bp->ncolors = (bp->twodee_p ? 1024 : 128);
 925
 926   if (bp->closed_p)
 927     {
 928       /* Since the path is closed, colors must also be a closed loop */
 929       bp->colors = (XColor *) calloc(bp->ncolors, sizeof(XColor));
 930       make_smooth_colormap (0, 0, 0,
 931                             bp->colors, &bp->ncolors,
 932                             False, 0, False);
 933     }
 934   else
 935     {
 936       /* Since the path is open, first and last colors should differ. */
 937       bp->ncolors *= 2;
 938       bp->colors = (XColor *) calloc(bp->ncolors, sizeof(XColor));
 939       make_uniform_colormap (0, 0, 0,
 940                              bp->colors, &bp->ncolors,
 941                              False, 0, False);
 942       bp->ncolors /= 2;
 943     }
 944
 945   /* Generate display lists for several different resolutions of
 946      a unit tube and a unit sphere.
 947    */
 948   for (i = 0; i < countof(dlist_faces); i++)
 949     {
 950       int faces = dlist_faces[i];
 951       bp->dlists[faces][0] = glGenLists (1);
 952
 953       glNewList (bp->dlists[faces][0], GL_COMPILE);
 954       bp->dlist_polys[faces][0] = unit_sphere (faces, faces, wire);
 955       glEndList ();
 956
 957       bp->dlists[faces][1] = glGenLists (1);
 958
 959       glNewList (bp->dlists[faces][1], GL_COMPILE);
 960       bp->dlist_polys[faces][1] =
 961         tube (0, 0, 0, 1, 0, 0,
 962               1, 0, faces, True, 0, wire);
 963       glEndList ();
 964     }
 965 }
 966
 967
 968 ENTRYPOINT void
 969 draw_hilbert (ModeInfo *mi)
 970 {
 971   hilbert_configuration *bp = &bps[MI_SCREEN(mi)];
 972   Display *dpy = MI_DISPLAY(mi);
 973   Window window = MI_WINDOW(mi);
 974   int wire = MI_IS_WIREFRAME(mi);
 975
 976   static const GLfloat bspec[4]  = {1.0, 1.0, 1.0, 1.0};
 977   static const GLfloat bshiny    = 128.0;
 978   GLfloat bcolor[4] = {1.0, 1.0, 1.0, 1.0};
 979
 980   if (!bp->glx_context)
 981     return;
 982
 983   glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(bp->glx_context));
 984
 985   glShadeModel(GL_SMOOTH);
 986
 987   if (! wire)
 988     {
 989       glEnable (GL_NORMALIZE);
 990       glEnable (GL_DEPTH_TEST);
 991       glEnable (GL_CULL_FACE);
 992       glEnable (GL_LIGHTING);
 993       glEnable (GL_LIGHT0);
 994       glEnable (GL_POLYGON_OFFSET_FILL);
 995     }
 996
 997   glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
 998
 999   glPushMatrix ();
1000
1001   glScalef(1.1, 1.1, 1.1);
1002
1003   {
1004     double x, y, z, z2;
1005     get_position (bp->rot, &x, &y, &z, !bp->button_down_p);
1006     glTranslatef((x - 0.5) * 8,
1007                  (y - 0.5) * 8,
1008                  (z - 0.5) * 15);
1009
1010     gltrackball_rotate (bp->trackball);
1011
1012     get_rotation (bp->rot, &x, &y, &z, !bp->button_down_p);
1013
1014     if (bp->twodee_p && do_spin)    /* face front */
1015       {
1016         double max = 70;
1017         get_position (bp->rot2, &x, &y, &z2, !bp->button_down_p);
1018         glRotatef (max/2 - x*max, 1, 0, 0);
1019         glRotatef (max/2 - y*max, 0, 1, 0);
1020         glRotatef (z * 360, 0, 0, 1);  /* but upside down is ok */
1021       }
1022     else
1023       {
1024         glRotatef (x * 360, 1, 0, 0);
1025         glRotatef (y * 360, 0, 1, 0);
1026         glRotatef (z * 360, 0, 0, 1);
1027       }
1028   }
1029
1030   mi->polygon_count = 0;
1031
1032   glMaterialfv (GL_FRONT, GL_SPECULAR,            bspec);
1033   glMateriali  (GL_FRONT, GL_SHININESS,           bshiny);
1034   glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, bcolor);
1035
1036   glScalef (8,8,8);
1037   glTranslatef (0.1, 0.1, 0);
1038
1039   if (!do_spin && !bp->twodee_p)
1040     {
1041       /* tilt the cube a little, and make the start and end visible */
1042       glTranslatef (-0.1, 0, 0);
1043       glRotatef (140, 0, 1, 0);
1044       glRotatef (30, 1, 0, 0);
1045     }
1046
1047   if (wire)
1048     glLineWidth (bp->depth > 4 ? 1.0 :
1049                  bp->depth > 3 ? 2.0 :
1050                  3.0);
1051
1052   if (bp->path_tick > 0)        /* advancing the end point, [0 - N) */
1053     {                           /* drawing 1 partial path, 1st time only. */
1054
1055       if (!bp->button_down_p)
1056         bp->path_end += 0.01 * speed;
1057
1058       if (bp->path_end >= 1.0)
1059         {
1060           bp->path_start = 0.0;
1061           bp->path_end   = 1.0;
1062           bp->path_tick = -1;
1063           bp->pause = PAUSE_TICKS;
1064         }
1065
1066       bp->diam = thickness / pow (2, bp->depth);
1067       hilbert (mi, bp->depth, bp->path_start, bp->path_end);
1068       mi->recursion_depth = bp->depth + bp->path_start;
1069     }
1070
1071   else                          /* advancing the start point, (N - 1] */
1072     {                           /* drawing 2 paths at different rez. */
1073       if (bp->pause)
1074         {
1075           bp->pause--;
1076         }
1077       else
1078         {
1079           if (!bp->button_down_p)
1080             bp->path_start += 0.01 * speed;
1081
1082           if (bp->path_start > 1.0)
1083             {
1084               bp->path_start = 0.0;
1085               bp->depth += bp->depth_tick;
1086               bp->pause = PAUSE_TICKS;
1087               if (bp->depth > max_depth-1)
1088                 {
1089                   bp->depth = max_depth;
1090                   bp->depth_tick = -1;
1091                 }
1092               else if (bp->depth <= 1)
1093                 {
1094                   bp->depth = 1;
1095                   bp->depth_tick = 1;
1096                 }
1097             }
1098         }
1099
1100       {
1101         GLfloat d1 = thickness / pow (2, bp->depth);
1102         GLfloat d2 = thickness / pow (2, bp->depth + bp->depth_tick);
1103         bp->diam = (d1 * (1 - bp->path_start) +
1104                     d2 * bp->path_start);
1105       }
1106
1107       /* First time around, start is 0, and end animates forward.
1108          Then, to display the next higher resolution, we render
1109          depth=N while increasing start and leaving end=1.0;
1110          and simultaneously animationg depth=N+1 with start=0 and
1111          end increasing by the same amount.
1112
1113          The two paths aren't actually connected together at the
1114          resolution-change interface, and sometimes they overlap,
1115          but things go fast enough that it's hard to spot those
1116          glitches, so it looks ok.
1117        */
1118       glPolygonOffset (0, 0);
1119       hilbert (mi, bp->depth,   bp->path_start, bp->path_end);
1120
1121       glPolygonOffset (1.0, 1.0);
1122       hilbert (mi, bp->depth + bp->depth_tick, 0.0, bp->path_start);
1123
1124       mi->recursion_depth = bp->depth + (bp->depth_tick * bp->path_start);
1125     }
1126
1127   glPopMatrix ();
1128
1129   if (mi->fps_p) do_fps (mi);
1130   glFinish();
1131
1132   glXSwapBuffers(dpy, window);
1133 }
1134
1135 XSCREENSAVER_MODULE ("Hilbert", hilbert)
1136
1137 #endif /* USE_GL */