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   if (!bps) {
 842     bps = (hilbert_configuration *)
 843       calloc (MI_NUM_SCREENS(mi), sizeof (hilbert_configuration));
 844     if (!bps) {
 845       fprintf(stderr, "%s: out of memory\n", progname);
 846       exit(1);
 847     }
 848   }
 849
 850   bp = &bps[MI_SCREEN(mi)];
 851
 852   bp->depth      = 2;
 853   bp->depth_tick = 1;
 854   bp->path_start = 0.0;
 855   bp->path_end   = 0.0;
 856   bp->path_tick  = 1;
 857
 858   if (thickness < 0.01) thickness = 0.01;
 859   if (thickness > 1.0) thickness = 1.0;
 860
 861   if (speed <= 0) speed = 0.0001;
 862   if (max_depth < 2) max_depth = 2;
 863   if (max_depth > 20) max_depth = 20;  /* hard limit due to hilbert_cache */
 864
 865   if (bp->depth > max_depth-1) bp->depth = max_depth-1;
 866
 867   bp->glx_context = init_GL(mi);
 868
 869   reshape_hilbert (mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 870
 871   if (!wire)
 872     {
 873       GLfloat pos[4] = {1.0, 1.0, 1.0, 0.0};
 874       GLfloat amb[4] = {0.0, 0.0, 0.0, 1.0};
 875       GLfloat dif[4] = {1.0, 1.0, 1.0, 1.0};
 876       GLfloat spc[4] = {0.0, 1.0, 1.0, 1.0};
 877
 878       glEnable (GL_LIGHTING);
 879       glEnable (GL_LIGHT0);
 880
 881       glLightfv(GL_LIGHT0, GL_POSITION, pos);
 882       glLightfv(GL_LIGHT0, GL_AMBIENT,  amb);
 883       glLightfv(GL_LIGHT0, GL_DIFFUSE,  dif);
 884       glLightfv(GL_LIGHT0, GL_SPECULAR, spc);
 885     }
 886
 887   {
 888     double spin_speed   = 0.04;
 889     double tilt_speed   = spin_speed / 10;
 890     double wander_speed = 0.008;
 891     double spin_accel   = 0.01;
 892
 893     bp->rot = make_rotator (do_spin ? spin_speed : 0,
 894                             do_spin ? spin_speed : 0,
 895                             do_spin ? spin_speed : 0,
 896                             spin_accel,
 897                             do_wander ? wander_speed : 0,
 898                             do_spin);
 899     bp->rot2 = make_rotator (0, 0, 0, 0, tilt_speed, True);
 900     bp->trackball = gltrackball_init (True);
 901   }
 902
 903   if (mode_str && !strcasecmp(mode_str, "2d"))
 904     bp->twodee_p = True;
 905   else if (mode_str && (!strcasecmp(mode_str, "3d")))
 906     bp->twodee_p = False;
 907   else
 908     {
 909       if (! (mode_str && !strcasecmp(mode_str, "random")))
 910         fprintf (stderr, "%s: 'mode' must be '2d', '3d', or 'random'\n",
 911                  progname);
 912       bp->twodee_p = ((random() % 3) == 0);
 913     }
 914
 915
 916   if (ends_str && (!strcasecmp(ends_str, "closed")))
 917     bp->closed_p = True;
 918   else if (ends_str && (!strcasecmp(ends_str, "open")))
 919     bp->closed_p = False;
 920   else
 921     {
 922       if (! (ends_str && !strcasecmp(ends_str, "random")))
 923         fprintf (stderr, "%s: 'ends' must be 'open', 'closed', or 'random'\n",
 924                  progname);
 925       bp->closed_p = ((random() % 3) != 0);
 926     }
 927
 928
 929   /* More colors results in more polygons (more tube segments) so keeping
 930      this small is worthwhile. */
 931   bp->ncolors = (bp->twodee_p ? 1024 : 128);
 932
 933   if (bp->closed_p)
 934     {
 935       /* Since the path is closed, colors must also be a closed loop */
 936       bp->colors = (XColor *) calloc(bp->ncolors, sizeof(XColor));
 937       make_smooth_colormap (0, 0, 0,
 938                             bp->colors, &bp->ncolors,
 939                             False, 0, False);
 940     }
 941   else
 942     {
 943       /* Since the path is open, first and last colors should differ. */
 944       bp->ncolors *= 2;
 945       bp->colors = (XColor *) calloc(bp->ncolors, sizeof(XColor));
 946       make_uniform_colormap (0, 0, 0,
 947                              bp->colors, &bp->ncolors,
 948                              False, 0, False);
 949       bp->ncolors /= 2;
 950     }
 951
 952   /* Generate display lists for several different resolutions of
 953      a unit tube and a unit sphere.
 954    */
 955   for (i = 0; i < countof(dlist_faces); i++)
 956     {
 957       int faces = dlist_faces[i];
 958       bp->dlists[faces][0] = glGenLists (1);
 959
 960       glNewList (bp->dlists[faces][0], GL_COMPILE);
 961       bp->dlist_polys[faces][0] = unit_sphere (faces, faces, wire);
 962       glEndList ();
 963
 964       bp->dlists[faces][1] = glGenLists (1);
 965
 966       glNewList (bp->dlists[faces][1], GL_COMPILE);
 967       bp->dlist_polys[faces][1] =
 968         tube (0, 0, 0, 1, 0, 0,
 969               1, 0, faces, True, 0, wire);
 970       glEndList ();
 971     }
 972 }
 973
 974
 975 ENTRYPOINT void
 976 draw_hilbert (ModeInfo *mi)
 977 {
 978   hilbert_configuration *bp = &bps[MI_SCREEN(mi)];
 979   Display *dpy = MI_DISPLAY(mi);
 980   Window window = MI_WINDOW(mi);
 981   int wire = MI_IS_WIREFRAME(mi);
 982
 983   static const GLfloat bspec[4]  = {1.0, 1.0, 1.0, 1.0};
 984   static const GLfloat bshiny    = 128.0;
 985   GLfloat bcolor[4] = {1.0, 1.0, 1.0, 1.0};
 986
 987   if (!bp->glx_context)
 988     return;
 989
 990   glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(bp->glx_context));
 991
 992   glShadeModel(GL_SMOOTH);
 993
 994   if (! wire)
 995     {
 996       glEnable (GL_NORMALIZE);
 997       glEnable (GL_DEPTH_TEST);
 998       glEnable (GL_CULL_FACE);
 999       glEnable (GL_LIGHTING);
1000       glEnable (GL_LIGHT0);
1001       glEnable (GL_POLYGON_OFFSET_FILL);
1002     }
1003
1004   glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1005
1006   glPushMatrix ();
1007
1008   glScalef(1.1, 1.1, 1.1);
1009
1010   {
1011     double x, y, z, z2;
1012     get_position (bp->rot, &x, &y, &z, !bp->button_down_p);
1013     glTranslatef((x - 0.5) * 8,
1014                  (y - 0.5) * 8,
1015                  (z - 0.5) * 15);
1016
1017     gltrackball_rotate (bp->trackball);
1018
1019     get_rotation (bp->rot, &x, &y, &z, !bp->button_down_p);
1020
1021     if (bp->twodee_p && do_spin)    /* face front */
1022       {
1023         double max = 70;
1024         get_position (bp->rot2, &x, &y, &z2, !bp->button_down_p);
1025         glRotatef (max/2 - x*max, 1, 0, 0);
1026         glRotatef (max/2 - y*max, 0, 1, 0);
1027         glRotatef (z * 360, 0, 0, 1);  /* but upside down is ok */
1028       }
1029     else
1030       {
1031         glRotatef (x * 360, 1, 0, 0);
1032         glRotatef (y * 360, 0, 1, 0);
1033         glRotatef (z * 360, 0, 0, 1);
1034       }
1035   }
1036
1037   mi->polygon_count = 0;
1038
1039   glMaterialfv (GL_FRONT, GL_SPECULAR,            bspec);
1040   glMateriali  (GL_FRONT, GL_SHININESS,           bshiny);
1041   glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, bcolor);
1042
1043   glScalef (8,8,8);
1044   glTranslatef (0.1, 0.1, 0);
1045
1046   if (!do_spin && !bp->twodee_p)
1047     {
1048       /* tilt the cube a little, and make the start and end visible */
1049       glTranslatef (-0.1, 0, 0);
1050       glRotatef (140, 0, 1, 0);
1051       glRotatef (30, 1, 0, 0);
1052     }
1053
1054   if (wire)
1055     glLineWidth (bp->depth > 4 ? 1.0 :
1056                  bp->depth > 3 ? 2.0 :
1057                  3.0);
1058
1059   if (bp->path_tick > 0)        /* advancing the end point, [0 - N) */
1060     {                           /* drawing 1 partial path, 1st time only. */
1061
1062       if (!bp->button_down_p)
1063         bp->path_end += 0.01 * speed;
1064
1065       if (bp->path_end >= 1.0)
1066         {
1067           bp->path_start = 0.0;
1068           bp->path_end   = 1.0;
1069           bp->path_tick = -1;
1070           bp->pause = PAUSE_TICKS;
1071         }
1072
1073       bp->diam = thickness / pow (2, bp->depth);
1074       hilbert (mi, bp->depth, bp->path_start, bp->path_end);
1075       mi->recursion_depth = bp->depth + bp->path_start;
1076     }
1077
1078   else                          /* advancing the start point, (N - 1] */
1079     {                           /* drawing 2 paths at different rez. */
1080       if (bp->pause)
1081         {
1082           bp->pause--;
1083         }
1084       else
1085         {
1086           if (!bp->button_down_p)
1087             bp->path_start += 0.01 * speed;
1088
1089           if (bp->path_start > 1.0)
1090             {
1091               bp->path_start = 0.0;
1092               bp->depth += bp->depth_tick;
1093               bp->pause = PAUSE_TICKS;
1094               if (bp->depth > max_depth-1)
1095                 {
1096                   bp->depth = max_depth;
1097                   bp->depth_tick = -1;
1098                 }
1099               else if (bp->depth <= 1)
1100                 {
1101                   bp->depth = 1;
1102                   bp->depth_tick = 1;
1103                 }
1104             }
1105         }
1106
1107       {
1108         GLfloat d1 = thickness / pow (2, bp->depth);
1109         GLfloat d2 = thickness / pow (2, bp->depth + bp->depth_tick);
1110         bp->diam = (d1 * (1 - bp->path_start) +
1111                     d2 * bp->path_start);
1112       }
1113
1114       /* First time around, start is 0, and end animates forward.
1115          Then, to display the next higher resolution, we render
1116          depth=N while increasing start and leaving end=1.0;
1117          and simultaneously animationg depth=N+1 with start=0 and
1118          end increasing by the same amount.
1119
1120          The two paths aren't actually connected together at the
1121          resolution-change interface, and sometimes they overlap,
1122          but things go fast enough that it's hard to spot those
1123          glitches, so it looks ok.
1124        */
1125       glPolygonOffset (0, 0);
1126       hilbert (mi, bp->depth,   bp->path_start, bp->path_end);
1127
1128       glPolygonOffset (1.0, 1.0);
1129       hilbert (mi, bp->depth + bp->depth_tick, 0.0, bp->path_start);
1130
1131       mi->recursion_depth = bp->depth + (bp->depth_tick * bp->path_start);
1132     }
1133
1134   glPopMatrix ();
1135
1136   if (mi->fps_p) do_fps (mi);
1137   glFinish();
1138
1139   glXSwapBuffers(dpy, window);
1140 }
1141
1142 XSCREENSAVER_MODULE ("Hilbert", hilbert)
1143
1144 #endif /* USE_GL */