/* hilbert, Copyright (c) 2011-2014 Jamie Zawinski * * Permission to use, copy, modify, distribute, and sell this software and its * documentation for any purpose is hereby granted without fee, provided that * the above copyright notice appear in all copies and that both that * copyright notice and this permission notice appear in supporting * documentation. No representations are made about the suitability of this * software for any purpose. It is provided "as is" without express or * implied warranty. * * 2D and 3D Hilbert space-filling curves. * * Inspired by "Visualizing Hilbert Curves" by Nelson Max, 1998: * https://e-reports-ext.llnl.gov/pdf/234149.pdf */ #define DEFAULTS "*delay: 30000 \n" \ "*count: 30 \n" \ "*showFPS: False \n" \ "*wireframe: False \n" \ "*geometry: 800x800\n" \ "*suppressRotationAnimation: True\n" \ # define release_hilbert 0 #undef countof #define countof(x) (sizeof((x))/sizeof((*x))) #include "xlockmore.h" #include "colors.h" #include "sphere.h" #include "tube.h" #include "rotator.h" #include "gltrackball.h" #include #ifdef USE_GL /* whole file */ #define DEF_SPIN "True" #define DEF_WANDER "False" #define DEF_SPEED "1.0" #define DEF_MODE "random" #define DEF_ENDS "random" #define DEF_MAX_DEPTH "5" #define DEF_THICKNESS "0.25" #define PAUSE_TICKS 180 typedef struct { double x,y,z; } XYZ; typedef struct { unsigned short x,y,z; } XYZb; typedef struct { int size; XYZb *values; /* assume max depth of 20 (2^16 on each side) */ } hilbert_cache; static int dlist_faces[] = { 20, 10, 8, 4, 3 }; typedef struct { GLXContext *glx_context; rotator *rot, *rot2; trackball_state *trackball; Bool button_down_p; Bool twodee_p; Bool closed_p; int ncolors; XColor *colors; int depth; int depth_tick; GLfloat path_start, path_end; int path_tick; int pause; GLfloat diam; hilbert_cache **caches; /* filled lazily */ GLuint dlists [40][2]; /* we don't actually alloc all of these */ int dlist_polys [40][2]; } hilbert_configuration; static hilbert_configuration *bps = NULL; static Bool do_spin; static GLfloat speed; static Bool do_wander; static char *mode_str; static char *ends_str; static int max_depth; static GLfloat thickness; static XrmOptionDescRec opts[] = { { "-spin", ".spin", XrmoptionNoArg, "True" }, { "+spin", ".spin", XrmoptionNoArg, "False" }, { "-speed", ".speed", XrmoptionSepArg, 0 }, { "-wander", ".wander", XrmoptionNoArg, "True" }, { "+wander", ".wander", XrmoptionNoArg, "False" }, { "-mode", ".mode", XrmoptionSepArg, 0 }, { "-2d", ".mode", XrmoptionNoArg, "2D" }, { "-3d", ".mode", XrmoptionNoArg, "3D" }, { "-ends", ".ends", XrmoptionSepArg, 0 }, { "-closed", ".ends", XrmoptionNoArg, "closed" }, { "-open", ".ends", XrmoptionNoArg, "open" }, { "-max-depth", ".maxDepth", XrmoptionSepArg, 0 }, { "-thickness", ".thickness",XrmoptionSepArg, 0 }, }; static argtype vars[] = { {&do_spin, "spin", "Spin", DEF_SPIN, t_Bool}, {&do_wander, "wander", "Wander", DEF_WANDER, t_Bool}, {&speed, "speed", "Speed", DEF_SPEED, t_Float}, {&mode_str, "mode", "Mode", DEF_MODE, t_String}, {&ends_str, "ends", "Ends", DEF_ENDS, t_String}, {&max_depth, "maxDepth", "MaxDepth", DEF_MAX_DEPTH, t_Int}, {&thickness, "thickness","Thickness",DEF_THICKNESS, t_Float}, }; ENTRYPOINT ModeSpecOpt hilbert_opts = {countof(opts), opts, countof(vars), vars, NULL}; /* 2D Hilbert, and closed-loop variant. */ /* These arrays specify which bits of the T index contribute to the X, Y and Z values. Higher order bits are defined recursively. */ static const int xbit2d[4] = { 0, 0, 1, 1 }; static const int ybit2d[4] = { 0, 1, 1, 0 }; static const int xbit3d[8] = { 0,0,0,0,1,1,1,1 }; static const int ybit3d[8] = { 0,1,1,0,0,1,1,0 }; static const int zbit3d[8] = { 0,0,1,1,1,1,0,0 }; /* These matrixes encapsulate the necessary reflection and translation of each 4 sub-squares or 8 sub-cubes. The r2d and r3d arrays are the normal Hilbert descent, and the s2d and s3d arrays are the modified curve used for only level 0 of a closed-form path. */ static int r2d[4][2][2] = { /* _ _ | |..| | :_ _: _| |_ */ {{ 0, 1}, { 1, 0}}, {{ 1, 0}, { 0, 1}}, {{ 1, 0}, { 0, 1}}, {{ 0,-1}, {-1, 0}}, }; static int s2d[4][2][2] = { /* __ __ | |..| | Used for outermost iteration only, in "closed" mode : .. : |__| |__| */ {{-1, 0}, { 0,-1}}, {{ 1, 0}, { 0, 1}}, {{ 1, 0}, { 0, 1}}, {{-1, 0}, { 0,-1}}, }; static int r3d[8][3][3] = { /* /| /| / | / | /__|____/ | | | / / / / */ {{ 0, 1, 0}, { 1, 0, 0}, { 0, 0, 1}}, {{ 0, 0, 1}, { 0, 1, 0}, { 1, 0, 0}}, {{ 1, 0, 0}, { 0, 1, 0}, { 0, 0, 1}}, {{ 0, 0,-1}, {-1, 0, 0}, { 0, 1, 0}}, {{ 0, 0, 1}, { 1, 0, 0}, { 0, 1, 0}}, {{ 1, 0, 0}, { 0, 1, 0}, { 0, 0, 1}}, {{ 0, 0,-1}, { 0, 1, 0}, {-1, 0, 0}}, {{ 0,-1, 0}, {-1, 0, 0}, { 0, 0, 1}}, }; static int s3d[8][3][3] = { /* /| /| Used for outermost iteration only, in "closed" mode / | / | /__|____/ | | | / / /_______/ */ {{-1, 0, 0}, { 0, 0,-1}, { 0, 1, 0}}, {{ 0, 0, 1}, { 0, 1, 0}, { 1, 0, 0}}, {{ 1, 0, 0}, { 0, 1, 0}, { 0, 0, 1}}, {{ 0, 0,-1}, {-1, 0, 0}, { 0, 1, 0}}, {{ 0, 0, 1}, { 1, 0, 0}, { 0, 1, 0}}, {{ 1, 0, 0}, { 0, 1, 0}, { 0, 0, 1}}, {{ 0, 0,-1}, { 0, 1, 0}, {-1, 0, 0}}, {{-1, 0, 0}, { 0, 0,-1}, { 0, 1, 0}}, }; /* Matrix utilities */ static void matrix_times_vector2d (int m[2][2], int v[2], int dest[2]) { dest[0] = m[0][0]*v[0] + m[0][1]*v[1]; dest[1] = m[1][0]*v[0] + m[1][1]*v[1]; } static void matrix_times_vector3d (int m[3][3], int v[3], int dest[3]) { dest[0] = m[0][0]*v[0] + m[0][1]*v[1] + m[0][2]*v[2]; dest[1] = m[1][0]*v[0] + m[1][1]*v[1] + m[1][2]*v[2]; dest[2] = m[2][0]*v[0] + m[2][1]*v[1] + m[2][2]*v[2]; } static void matrix_multiply2d (int m1[2][2], int m2[2][2], int dest[2][2]) { dest[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]; dest[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]; dest[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]; dest[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]; } static void matrix_multiply3d (int m1[3][3], int m2[3][3], int dest[3][3]) { int i, j, k; for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) { dest[i][j] = 0; for (k = 0; k < 3; k++) dest[i][j] += m1[i][k] * m2[k][j]; } } static void identity_matrix2d (int m[2][2]) { m[0][0] = m[1][1] = 1; m[0][1] = m[1][0] = 0; } static void identity_matrix3d (int m[3][3]) { m[0][0] = m[1][1] = m[2][2] = 1; m[0][1] = m[0][2] = m[1][0] = m[1][2] = m[2][0] = m[2][1] = 0; } static void matrix_copy2d (int src[2][2], int dest[2][2]) { int i, j; for (i = 0; i < 2; i++) for (j = 0; j < 2; j++) dest[i][j] = src[i][j]; } static void matrix_copy3d (int src[3][3], int dest[3][3]) { int i, j; for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) dest[i][j] = src[i][j]; } /* 2D and 3D Hilbert: Given an index T along the curve, return the XY or XYZ coordinates. N is depth of the curve. */ static void t_to_xy (int n, int t, int *x, int *y, Bool closed_p) { int k, rt[2][2], rq[2][2], va[2], vb[2]; identity_matrix2d(rt); *x = *y = 0; for (k = n-1; k >= 0; k--) { int j = 3 & (t >> (2*k)); va[0] = 2 * xbit2d[j] - 1; va[1] = 2 * ybit2d[j] - 1; matrix_times_vector2d (rt, va, vb); *x += ((vb[0] + 1) / 2) << k; *y += ((vb[1] + 1) / 2) << k; if (k > 0) { matrix_copy2d (rt, rq); if (k == n-1 && closed_p) matrix_multiply2d (rq, s2d[j], rt); else matrix_multiply2d (rq, r2d[j], rt); } } } static void t_to_xyz (int n, int t, int *x, int *y, int *z, Bool closed_p) { int k, rt[3][3], rq[3][3], va[3], vb[3]; identity_matrix3d(rt); *x = *y = *z = 0; for (k = n-1; k >= 0; k--) { int j = 7 & (t >> (3*k)); va[0] = 2 * xbit3d[j] - 1; va[1] = 2 * ybit3d[j] - 1; va[2] = 2 * zbit3d[j] - 1; matrix_times_vector3d (rt, va, vb); *x += ((vb[0] + 1) / 2) << k; *y += ((vb[1] + 1) / 2) << k; *z += ((vb[2] + 1) / 2) << k; if (k > 0) { matrix_copy3d (rt, rq); if (k == n-1 && closed_p) matrix_multiply3d (rq, s3d[j], rt); else matrix_multiply3d (rq, r3d[j], rt); } } } /* Rendering the curve */ /* Draw a sphere at the intersection of two tubes, to round off the connection between them. Use one of our cache display lists of unit spheres in various sizes. */ static int draw_joint (ModeInfo *mi, XYZ p, GLfloat diam, int faces, int wire) { hilbert_configuration *bp = &bps[MI_SCREEN(mi)]; int i; diam *= 0.99; /* try to clean up the edges a bit */ if (faces <= 4) return 0; /* too small to see */ glPushMatrix(); glTranslatef (p.x, p.y, p.z); glScalef (diam, diam, diam); /* i = unit_sphere (faces, faces, wire);*/ /* if (!bp->dlists[faces][0]) abort(); */ /* if (!bp->dlist_polys[faces][0]) abort(); */ glCallList (bp->dlists[faces][0]); i = bp->dlist_polys[faces][0]; glPopMatrix(); return i; } /* Draw a tube, and associated end caps. Use one of our cache display lists of unit tubes in various sizes. Pick the resolution of the tube based on how large it's being drawn. It's ok to get chunkier if the thing is only a few pixels wide on the screen. */ static Bool draw_segment (ModeInfo *mi, XYZ p0, XYZ p1, /* from, to */ int t, int end_t, /* value and range */ GLfloat path_start, GLfloat path_end, /* clipping */ Bool head_cap_p, int *last_colorP) { hilbert_configuration *bp = &bps[MI_SCREEN(mi)]; double t0 = (double) (t-1) / end_t; /* ratio of p[01] along curve */ double t1 = (double) t / end_t; int wire = MI_IS_WIREFRAME(mi); int owire = wire; GLfloat dd = bp->diam; int faces; if (path_start >= t1) /* whole segment is before clipping region */ return False; if (path_end < t0) /* whole segment is after clipping region */ return False; if (bp->twodee_p) dd *= 2; /* more polys in 2D mode */ faces = (dd > 0.040 ? dlist_faces[0] : dd > 0.020 ? dlist_faces[1] : dd > 0.010 ? dlist_faces[2] : dd > 0.005 ? dlist_faces[3] : dd > 0.002 ? dlist_faces[4] : 1); /* In 2d mode, we can drop into wireframe mode and it still looks ok... */ if (faces == 1) { if (bp->twodee_p) wire = True; else faces = 3; } if (wire && !owire) { glDisable (GL_DEPTH_TEST); glDisable (GL_CULL_FACE); glDisable (GL_LIGHTING); } if (t0 < path_start) { XYZ p; GLfloat seg_range = t1 - t0; GLfloat clip_range = path_start - t0; GLfloat ratio = clip_range / seg_range; p.x = p0.x + ((p1.x - p0.x) * ratio); p.y = p0.y + ((p1.y - p0.y) * ratio); p.z = p0.z + ((p1.z - p0.z) * ratio); p0 = p; } if (t1 > path_end) { XYZ p; GLfloat seg_range = t1 - t0; GLfloat clip_range = path_end - t0; GLfloat ratio = clip_range / seg_range; p.x = p0.x + ((p1.x - p0.x) * ratio); p.y = p0.y + ((p1.y - p0.y) * ratio); p.z = p0.z + ((p1.z - p0.z) * ratio); p1 = p; } if (p0.x == p1.x && p0.y == p1.y && p0.z == p1.z) return False; { int segs = bp->ncolors * (t1 - t0); int i; XYZ p0b, p1b; if (segs < 1) segs = 1; for (i = 0; i < segs; i++) { int j = i + 1; GLfloat color[4] = {0.0, 0.0, 0.0, 1.0}; GLfloat t0b; int c; p0b.x = p0.x + i * ((p1.x - p0.x) / segs); p0b.y = p0.y + i * ((p1.y - p0.y) / segs); p0b.z = p0.z + i * ((p1.z - p0.z) / segs); p1b.x = p0.x + j * ((p1.x - p0.x) / segs); p1b.y = p0.y + j * ((p1.y - p0.y) / segs); p1b.z = p0.z + j * ((p1.z - p0.z) / segs); /* #### this isn't quite right */ t0b = t0 + i * (t1 - t0) / segs; c = bp->ncolors * t0b; if (c >= bp->ncolors) c = bp->ncolors-1; /* Above depth 6, was spending 5% of the time in glMateralfv, so only set the color if it's different. */ if (c != *last_colorP) { color[0] = bp->colors[c].red / 65536.0; color[1] = bp->colors[c].green / 65536.0; color[2] = bp->colors[c].blue / 65536.0; if (wire) glColor3fv (color); else glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color); *last_colorP = c; } if (wire) { glBegin (GL_LINES); glVertex3f (p0b.x, p0b.y, p0b.z); glVertex3f (p1b.x, p1b.y, p1b.z); glEnd (); mi->polygon_count++; } else { /* mi->polygon_count += tube (p0b.x, p0b.y, p0b.z, p1b.x, p1b.y, p1b.z, bp->diam, 0, faces, True, 0, wire); */ /* Render a rotated and scaled prefab unit tube. There's probably a slightly more concise way to do this, but since they're all at right angles at least we don't have to use atan(). */ GLfloat s; glPushMatrix(); glTranslatef (p0b.x, p0b.y, p0b.z); if (p1b.x > p0b.x) { s = p1b.x - p0b.x; } else if (p1b.x < p0b.x) { glRotatef (180, 0, 0, 1); s = p0b.x - p1b.x; } else if (p1b.y > p0b.y) { glRotatef (90, 0, 0, 1); s = p1b.y - p0b.y; } else if (p1b.y < p0b.y) { glRotatef (-90, 0, 0, 1); s = p0b.y - p1b.y; } else if (p1b.z > p0b.z) { glRotatef (-90, 0, 1, 0); s = p1b.z - p0b.z; } else /* (p1b.z < p0b.z) */ { glRotatef (90, 0, 1, 0); s = p0b.z - p1b.z; } glScalef (s, bp->diam, bp->diam); glCallList (bp->dlists[faces][1]); mi->polygon_count += bp->dlist_polys[faces][1]; glPopMatrix(); /* If this is the bleeding edge, cap it too. */ if (head_cap_p) { mi->polygon_count += draw_joint (mi, p0b, bp->diam, faces, wire); head_cap_p = False; } } } /* If the path is closed, close it. This segment doesn't animate like the others, but, oh well. */ if (! wire) mi->polygon_count += draw_joint (mi, p1b, bp->diam, faces, wire); } return True; } static void mem(void) { fprintf (stderr, "%s: out of memory\n", progname); exit (1); } /* Render the whole thing, but omit segments that lie outside of the path_start and path_end ratios. */ static void hilbert (ModeInfo *mi, int size, GLfloat path_start, GLfloat path_end) { hilbert_configuration *bp = &bps[MI_SCREEN(mi)]; int wire = MI_IS_WIREFRAME(mi); GLfloat w = pow(2, size); int end_t = (bp->twodee_p ? w * w : w * w * w); XYZ prev = { 0, }; XYZ first = { 0, }; Bool first_p = False; Bool any_p = False; int t; Bool fill_cache_p = False; hilbert_cache *cc; int last_color = -1; /* Do this here since at higher resolutions, we turn wireframe on and off. */ if (! wire) { glEnable (GL_NORMALIZE); glEnable (GL_DEPTH_TEST); glEnable (GL_CULL_FACE); glEnable (GL_LIGHTING); glEnable (GL_POLYGON_OFFSET_FILL); } if (!bp->caches) { bp->caches = (hilbert_cache **) calloc (max_depth + 2, sizeof (*bp->caches)); if (!bp->caches) mem(); fill_cache_p = True; } cc = bp->caches[size]; if (! cc) { cc = (hilbert_cache *) calloc (1, sizeof (*cc)); cc->values = (XYZb *) calloc (end_t + 1, sizeof (*cc->values)); if (!cc->values) mem(); cc->size = end_t; bp->caches[size] = cc; fill_cache_p = True; } for (t = 0; t < end_t; t++) { int x, y, z; XYZ c; XYZb *cb; if (!fill_cache_p) { cb = &cc->values[t]; x = cb->x; y = cb->y; z = cb->z; } else { if (!bp->twodee_p) t_to_xyz (size, t, &x, &y, &z, bp->closed_p); else { t_to_xy (size, t, &x, &y, bp->closed_p); z = w/2; } cb = &cc->values[t]; cb->x = x; cb->y = y; cb->z = z; } c.x = (GLfloat) x / w - 0.5; c.y = (GLfloat) y / w - 0.5; c.z = (GLfloat) z / w - 0.5; /* #### We could save some polygons by not drawing the spheres between colinear segments. */ if (t > 0) { if (draw_segment (mi, prev, c, t, end_t, path_start, path_end, !any_p, &last_color)) any_p = True; } prev = c; if (! first_p) { first = c; first_p = True; } } if (bp->closed_p && path_end >= 1.0) { draw_segment (mi, prev, first, t, end_t, path_start, path_end, !any_p, &last_color); } } /* Window management, etc */ ENTRYPOINT void reshape_hilbert (ModeInfo *mi, int width, int height) { GLfloat h = (GLfloat) height / (GLfloat) width; int y = 0; if (width > height * 5) { /* tiny window: show middle */ height = width * 9/16; y = -height/2; h = height / (GLfloat) width; } glViewport (0, y, (GLint) width, (GLint) height); glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluPerspective (30.0, 1/h, 1.0, 100.0); glMatrixMode(GL_MODELVIEW); glLoadIdentity(); gluLookAt( 0.0, 0.0, 30.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0); # ifdef HAVE_MOBILE /* Keep it the same relative size when rotated. */ { int o = (int) current_device_rotation(); if (o != 0 && o != 180 && o != -180) glScalef (1/h, 1/h, 1/h); } # endif glClear(GL_COLOR_BUFFER_BIT); } ENTRYPOINT Bool hilbert_handle_event (ModeInfo *mi, XEvent *event) { hilbert_configuration *bp = &bps[MI_SCREEN(mi)]; if (gltrackball_event_handler (event, bp->trackball, MI_WIDTH (mi), MI_HEIGHT (mi), &bp->button_down_p)) return True; else if (event->xany.type == KeyPress) { KeySym keysym; char c = 0; XLookupString (&event->xkey, &c, 1, &keysym, 0); if (c == '+' || c == '=' || keysym == XK_Up || keysym == XK_Right || keysym == XK_Next) { bp->depth++; if (bp->depth > max_depth) bp->depth = max_depth; return True; } else if (c == '-' || c == '_' || keysym == XK_Down || keysym == XK_Left || keysym == XK_Prior) { bp->depth--; if (bp->depth < 1) bp->depth = 1; return True; } else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event)) { bp->depth += bp->depth_tick; if (bp->depth > max_depth-1) { bp->depth = max_depth; bp->depth_tick = -1; } else if (bp->depth <= 1) { bp->depth = 1; bp->depth_tick = 1; } return True; } } return False; } ENTRYPOINT void init_hilbert (ModeInfo *mi) { hilbert_configuration *bp; int wire = MI_IS_WIREFRAME(mi); int i; MI_INIT (mi, bps); bp = &bps[MI_SCREEN(mi)]; bp->depth = 2; bp->depth_tick = 1; bp->path_start = 0.0; bp->path_end = 0.0; bp->path_tick = 1; if (thickness < 0.01) thickness = 0.01; if (thickness > 1.0) thickness = 1.0; if (speed <= 0) speed = 0.0001; if (max_depth < 2) max_depth = 2; if (max_depth > 20) max_depth = 20; /* hard limit due to hilbert_cache */ if (bp->depth > max_depth-1) bp->depth = max_depth-1; bp->glx_context = init_GL(mi); reshape_hilbert (mi, MI_WIDTH(mi), MI_HEIGHT(mi)); if (!wire) { GLfloat pos[4] = {1.0, 1.0, 1.0, 0.0}; GLfloat amb[4] = {0.0, 0.0, 0.0, 1.0}; GLfloat dif[4] = {1.0, 1.0, 1.0, 1.0}; GLfloat spc[4] = {0.0, 1.0, 1.0, 1.0}; glEnable (GL_LIGHTING); glEnable (GL_LIGHT0); glLightfv(GL_LIGHT0, GL_POSITION, pos); glLightfv(GL_LIGHT0, GL_AMBIENT, amb); glLightfv(GL_LIGHT0, GL_DIFFUSE, dif); glLightfv(GL_LIGHT0, GL_SPECULAR, spc); } { double spin_speed = 0.04; double tilt_speed = spin_speed / 10; double wander_speed = 0.008; double spin_accel = 0.01; bp->rot = make_rotator (do_spin ? spin_speed : 0, do_spin ? spin_speed : 0, do_spin ? spin_speed : 0, spin_accel, do_wander ? wander_speed : 0, do_spin); bp->rot2 = make_rotator (0, 0, 0, 0, tilt_speed, True); bp->trackball = gltrackball_init (True); } if (mode_str && !strcasecmp(mode_str, "2d")) bp->twodee_p = True; else if (mode_str && (!strcasecmp(mode_str, "3d"))) bp->twodee_p = False; else { if (! (mode_str && !strcasecmp(mode_str, "random"))) fprintf (stderr, "%s: 'mode' must be '2d', '3d', or 'random'\n", progname); bp->twodee_p = ((random() % 3) == 0); } if (ends_str && (!strcasecmp(ends_str, "closed"))) bp->closed_p = True; else if (ends_str && (!strcasecmp(ends_str, "open"))) bp->closed_p = False; else { if (! (ends_str && !strcasecmp(ends_str, "random"))) fprintf (stderr, "%s: 'ends' must be 'open', 'closed', or 'random'\n", progname); bp->closed_p = ((random() % 3) != 0); } /* More colors results in more polygons (more tube segments) so keeping this small is worthwhile. */ bp->ncolors = (bp->twodee_p ? 1024 : 128); if (bp->closed_p) { /* Since the path is closed, colors must also be a closed loop */ bp->colors = (XColor *) calloc(bp->ncolors, sizeof(XColor)); make_smooth_colormap (0, 0, 0, bp->colors, &bp->ncolors, False, 0, False); } else { /* Since the path is open, first and last colors should differ. */ bp->ncolors *= 2; bp->colors = (XColor *) calloc(bp->ncolors, sizeof(XColor)); make_uniform_colormap (0, 0, 0, bp->colors, &bp->ncolors, False, 0, False); bp->ncolors /= 2; } /* Generate display lists for several different resolutions of a unit tube and a unit sphere. */ for (i = 0; i < countof(dlist_faces); i++) { int faces = dlist_faces[i]; bp->dlists[faces][0] = glGenLists (1); glNewList (bp->dlists[faces][0], GL_COMPILE); bp->dlist_polys[faces][0] = unit_sphere (faces, faces, wire); glEndList (); bp->dlists[faces][1] = glGenLists (1); glNewList (bp->dlists[faces][1], GL_COMPILE); bp->dlist_polys[faces][1] = tube (0, 0, 0, 1, 0, 0, 1, 0, faces, True, 0, wire); glEndList (); } } ENTRYPOINT void draw_hilbert (ModeInfo *mi) { hilbert_configuration *bp = &bps[MI_SCREEN(mi)]; Display *dpy = MI_DISPLAY(mi); Window window = MI_WINDOW(mi); int wire = MI_IS_WIREFRAME(mi); static const GLfloat bspec[4] = {1.0, 1.0, 1.0, 1.0}; static const GLfloat bshiny = 128.0; GLfloat bcolor[4] = {1.0, 1.0, 1.0, 1.0}; if (!bp->glx_context) return; glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *bp->glx_context); glShadeModel(GL_SMOOTH); if (! wire) { glEnable (GL_NORMALIZE); glEnable (GL_DEPTH_TEST); glEnable (GL_CULL_FACE); glEnable (GL_LIGHTING); glEnable (GL_LIGHT0); glEnable (GL_POLYGON_OFFSET_FILL); } glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); glPushMatrix (); glScalef(1.1, 1.1, 1.1); { double x, y, z, z2; get_position (bp->rot, &x, &y, &z, !bp->button_down_p); glTranslatef((x - 0.5) * 8, (y - 0.5) * 8, (z - 0.5) * 15); gltrackball_rotate (bp->trackball); get_rotation (bp->rot, &x, &y, &z, !bp->button_down_p); if (bp->twodee_p && do_spin) /* face front */ { double max = 70; get_position (bp->rot2, &x, &y, &z2, !bp->button_down_p); glRotatef (max/2 - x*max, 1, 0, 0); glRotatef (max/2 - y*max, 0, 1, 0); glRotatef (z * 360, 0, 0, 1); /* but upside down is ok */ } else { glRotatef (x * 360, 1, 0, 0); glRotatef (y * 360, 0, 1, 0); glRotatef (z * 360, 0, 0, 1); } } mi->polygon_count = 0; glMaterialfv (GL_FRONT, GL_SPECULAR, bspec); glMateriali (GL_FRONT, GL_SHININESS, bshiny); glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, bcolor); glScalef (8,8,8); glTranslatef (0.1, 0.1, 0); if (!do_spin && !bp->twodee_p) { /* tilt the cube a little, and make the start and end visible */ glTranslatef (-0.1, 0, 0); glRotatef (140, 0, 1, 0); glRotatef (30, 1, 0, 0); } if (wire) glLineWidth (bp->depth > 4 ? 1.0 : bp->depth > 3 ? 2.0 : 3.0); if (bp->path_tick > 0) /* advancing the end point, [0 - N) */ { /* drawing 1 partial path, 1st time only. */ if (!bp->button_down_p) bp->path_end += 0.01 * speed; if (bp->path_end >= 1.0) { bp->path_start = 0.0; bp->path_end = 1.0; bp->path_tick = -1; bp->pause = PAUSE_TICKS; } bp->diam = thickness / pow (2, bp->depth); hilbert (mi, bp->depth, bp->path_start, bp->path_end); mi->recursion_depth = bp->depth + bp->path_start; } else /* advancing the start point, (N - 1] */ { /* drawing 2 paths at different rez. */ if (bp->pause) { bp->pause--; } else { if (!bp->button_down_p) bp->path_start += 0.01 * speed; if (bp->path_start > 1.0) { bp->path_start = 0.0; bp->depth += bp->depth_tick; bp->pause = PAUSE_TICKS; if (bp->depth > max_depth-1) { bp->depth = max_depth; bp->depth_tick = -1; } else if (bp->depth <= 1) { bp->depth = 1; bp->depth_tick = 1; } } } { GLfloat d1 = thickness / pow (2, bp->depth); GLfloat d2 = thickness / pow (2, bp->depth + bp->depth_tick); bp->diam = (d1 * (1 - bp->path_start) + d2 * bp->path_start); } /* First time around, start is 0, and end animates forward. Then, to display the next higher resolution, we render depth=N while increasing start and leaving end=1.0; and simultaneously animationg depth=N+1 with start=0 and end increasing by the same amount. The two paths aren't actually connected together at the resolution-change interface, and sometimes they overlap, but things go fast enough that it's hard to spot those glitches, so it looks ok. */ glPolygonOffset (0, 0); hilbert (mi, bp->depth, bp->path_start, bp->path_end); glPolygonOffset (1.0, 1.0); hilbert (mi, bp->depth + bp->depth_tick, 0.0, bp->path_start); mi->recursion_depth = bp->depth + (bp->depth_tick * bp->path_start); } glPopMatrix (); if (mi->fps_p) do_fps (mi); glFinish(); glXSwapBuffers(dpy, window); } ENTRYPOINT void free_hilbert (ModeInfo *mi) { hilbert_configuration *bp = &bps[MI_SCREEN(mi)]; int i; if (!bp->glx_context) return; glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *bp->glx_context); if (bp->trackball) gltrackball_free (bp->trackball); if (bp->rot) free_rotator (bp->rot); if (bp->rot2) free_rotator (bp->rot2); if (bp->colors) free (bp->colors); if (bp->caches) for (i = 0; i < max_depth + 2; i++) if (bp->caches[i]) { free (bp->caches[i]->values); free (bp->caches[i]); } /* #### free dlists */ } XSCREENSAVER_MODULE ("Hilbert", hilbert) #endif /* USE_GL */