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