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

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