1 /* menger, Copyright (c) 2001 Jamie Zawinski <jwz@jwz.org>
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
11 * Generates a 3D Menger Sponge gasket:
14 * __-"" -- __"""----._____
15 * __.--"" -- ___--+---_____. __ .+'|
16 * _.-'"" __ +:"__ | ._..+"" __ .+' F
17 * J"--.____ __ """""+" .+' .J F
18 * J """""---.___ -- .+'" F' F
21 * L -_J L_J F"9 | ;'J .+J .J J
22 * | L_J | F.' .'| J F' J
23 * | |"""--.__ | ' |"" J J
24 * J ._ J ;;; | "L | . |-___J |
25 * J L J J ;-' | L | .'J |_ .' . |
26 * J "" J .---_L F"9 | F.' | .' FJ |
27 * L J .-' __ | L_J | ' :' ' .+
29 * | F"9 """' | . F' .'
31 * +__ -_J F"9 | F.' .'
36 * The straightforward way to generate this object creates way more polygons
37 * than are needed, since there end up being many buried, interior faces.
38 * So first we go through and generate the list of all the squares; then we
39 * sort the list and delete any squares that have a duplicate: if there are
40 * two of them, then they will be interior and facing each other, so we
41 * don't need either. Doing this reduces the polygon count by 20% - 33%.
43 * Another optimization we could do to reduce the polygon count would be to
44 * merge adjascent coplanar squares together into rectangles. This would
45 * result in the outer faces being composed of 1xN strips. It's tricky to
46 * to find these adjascent faces in non-exponential time, though.
48 * We could take advantage of the object's triple symmetry to reduce the
49 * size of the `squares' array, though that wouldn't actually reduce the
50 * number of polygons in the scene.
52 * We could actually simulate large depths with a texture map -- if the
53 * depth is such that the smallest holes are only a few pixels across,
54 * just draw them as spots on the surface! It would look the same.
57 #include <X11/Intrinsic.h>
59 extern XtAppContext app;
61 #define PROGCLASS "Menger"
62 #define HACK_INIT init_sponge
63 #define HACK_DRAW draw_sponge
64 #define HACK_RESHAPE reshape_sponge
65 #define sws_opts xlockmore_opts
67 #define DEF_SPIN "True"
68 #define DEF_WANDER "True"
69 #define DEF_SPEED "150"
70 #define DEF_MAX_DEPTH "3"
71 #define DEF_OPTIMIZE "True"
73 #define DEFAULTS "*delay: 30000 \n" \
74 "*showFPS: False \n" \
75 "*wireframe: False \n" \
76 "*maxDepth: " DEF_MAX_DEPTH "\n" \
77 "*speed:" DEF_SPEED "\n" \
78 "*optimize:" DEF_OPTIMIZE "\n" \
79 "*spin: " DEF_SPIN "\n" \
80 "*wander: " DEF_WANDER "\n" \
84 #define countof(x) (sizeof((x))/sizeof((*x)))
86 #include "xlockmore.h"
90 #ifdef USE_GL /* whole file */
95 unsigned int x0 : 8; /* 8 bottom left */
96 unsigned int y0 : 8; /* 16 */
97 unsigned int z0 : 8; /* 24 */
99 unsigned int x1 : 8; /* 32 top right */
100 unsigned int y1 : 8; /* 40 */
101 unsigned int z1 : 8; /* 48 */
103 int nx : 2; /* 50 normal */
107 /* 2 bits left over; 56 bits / 7 bytes total, */
108 /* which is surely rounded up to 8 bytes. */
113 GLXContext *glx_context;
115 GLfloat rotx, roty, rotz; /* current object rotation */
116 GLfloat dx, dy, dz; /* current rotational velocity */
117 GLfloat ddx, ddy, ddz; /* current rotational acceleration */
118 GLfloat d_max; /* max velocity */
120 GLuint sponge_list0; /* we store X, Y, and Z-facing surfaces */
121 GLuint sponge_list1; /* in their own lists, to make it easy */
122 GLuint sponge_list2; /* to color them differently. */
125 unsigned long squares_size;
126 unsigned long squares_fp;
136 } sponge_configuration;
138 static sponge_configuration *sps = NULL;
140 static char *do_spin;
141 static Bool do_wander;
143 static Bool do_optimize;
144 static int max_depth;
146 static XrmOptionDescRec opts[] = {
147 { "-spin", ".spin", XrmoptionNoArg, "True" },
148 { "+spin", ".spin", XrmoptionNoArg, "False" },
149 { "-wander", ".wander", XrmoptionNoArg, "True" },
150 { "+wander", ".wander", XrmoptionNoArg, "False" },
151 { "-speed", ".speed", XrmoptionSepArg, 0 },
152 { "-optimize", ".optimize", XrmoptionNoArg, "True" },
153 { "+optimize", ".optimize", XrmoptionNoArg, "False" },
154 {"-depth", ".maxDepth", XrmoptionSepArg, (caddr_t) 0 },
157 static argtype vars[] = {
158 {(caddr_t *) &do_spin, "spin", "Spin", DEF_SPIN, t_Bool},
159 {(caddr_t *) &do_wander, "wander", "Wander", DEF_WANDER, t_Bool},
160 {(caddr_t *) &speed, "speed", "Speed", DEF_SPEED, t_Int},
161 {(caddr_t *) &do_optimize, "optimize", "Optimize", DEF_OPTIMIZE, t_Bool},
162 {(caddr_t *) &max_depth, "maxDepth", "MaxDepth", DEF_MAX_DEPTH, t_Int},
165 ModeSpecOpt sws_opts = {countof(opts), opts, countof(vars), vars, NULL};
168 /* Window management, etc
171 reshape_sponge (ModeInfo *mi, int width, int height)
173 GLfloat h = (GLfloat) height / (GLfloat) width;
175 glViewport (0, 0, (GLint) width, (GLint) height);
177 glMatrixMode(GL_PROJECTION);
180 gluPerspective( 30.0, 1/h, 1.0, 100.0 );
181 gluLookAt( 0.0, 0.0, 15.0,
184 glMatrixMode(GL_MODELVIEW);
186 glTranslatef(0.0, 0.0, -15.0);
188 glClear(GL_COLOR_BUFFER_BIT);
193 gl_init (ModeInfo *mi)
195 /* sponge_configuration *sp = &sps[MI_SCREEN(mi)]; */
196 int wire = MI_IS_WIREFRAME(mi);
198 static GLfloat pos[4] = {-4.0, 3.0, 10.0, 1.0};
202 glLightfv(GL_LIGHT0, GL_POSITION, pos);
203 glEnable(GL_CULL_FACE);
204 glEnable(GL_LIGHTING);
206 glEnable(GL_DEPTH_TEST);
211 /* lifted from lament.c */
212 #define RAND(n) ((long) ((random() & 0x7fffffff) % ((long) (n))))
213 #define RANDSIGN() ((random() & 1) ? 1 : -1)
216 rotate(GLfloat *pos, GLfloat *v, GLfloat *dv, GLfloat max_v)
231 if (ppos < 0) abort();
232 if (ppos > 1.0) abort();
233 *pos = (*pos > 0 ? ppos : -ppos);
239 if (*v > max_v || *v < -max_v)
243 /* If it stops, start it going in the other direction. */
250 /* keep going in the same direction */
265 /* Alter direction of rotational acceleration randomly. */
266 if (! (random() % 120))
269 /* Change acceleration very occasionally. */
270 if (! (random() % 200))
274 else if (random() & 1)
282 /* Pushes a 1x1x1 cube at XYZ into the sp->squares list.
285 cube (sponge_configuration *sp, Bool wireframe_p,
286 int x, int y, int z, int s)
290 # define PP(NX, NY, NZ, X0, Y0, Z0, X1, Y1, Z1) \
291 (sq = &sp->squares[sp->squares_fp++], \
295 sq->x0 = x+((X0)*s), \
296 sq->y0 = y+((Y0)*s), \
297 sq->z0 = z+((Z0)*s), \
298 sq->x1 = x+((X1)*s), \
299 sq->y1 = y+((Y1)*s), \
302 PP (0, 0, -1, 0, 1, 0, 1, 0, 0);
303 PP (0, 0, 1, 0, 0, 1, 1, 1, 1);
304 PP (0, -1, 0, 0, 0, 0, 1, 0, 1);
305 PP (0, 1, 0, 0, 1, 1, 1, 1, 0);
307 if (wireframe_p) return; /* don't need the rest */
309 PP (-1, 0, 0, 0, 0, 1, 0, 1, 0);
310 PP ( 1, 0, 0, 1, 0, 0, 1, 1, 1);
313 if (sp->squares_fp >= sp->squares_size) abort();
321 while (n-- > 0) ii *= i;
327 descend_cubes (sponge_configuration *sp, Bool wireframe_p, int countdown,
330 int descend_p = (countdown > 0);
331 int facet_size = iexp (3, countdown);
336 cube (sp, wireframe_p, x+1*s, y+1*s, z, 1);
337 cube (sp, wireframe_p, x+1*s, y+1*s, z+2*s, 1);
338 cube (sp, wireframe_p, x, y+1*s, z+1*s, 1);
339 cube (sp, wireframe_p, x+2*s, y+1*s, z+1*s, 1);
340 cube (sp, wireframe_p, x+1*s, y, z+1*s, 1);
341 cube (sp, wireframe_p, x+1*s, y+2*s, z+1*s, 1);
343 if (!descend_p) return;
346 # define CUBE(xx,yy,zz) \
348 ? descend_cubes (sp, wireframe_p, countdown-1, \
349 x+(xx)*s, y+(yy)*s, z+(zz)*s) \
350 : cube (sp, wireframe_p, x+(xx)*s, y+(yy)*s, z+(zz)*s, 1))
352 CUBE(0, 2, 0); CUBE(1, 2, 0); CUBE(2, 2, 0); /* top front row */
353 CUBE(0, 1, 0); CUBE(2, 1, 0); /* middle front row */
354 CUBE(0, 0, 0); CUBE(1, 0, 0); CUBE(2, 0, 0); /* bottom front row */
355 CUBE(0, 2, 1); CUBE(2, 2, 1); /* top middle row */
356 CUBE(0, 0, 1); CUBE(2, 0, 1); /* bottom middle row */
357 CUBE(0, 2, 2); CUBE(1, 2, 2); CUBE(2, 2, 2); /* top back row */
358 CUBE(0, 1, 2); CUBE(2, 1, 2); /* middle back row */
359 CUBE(0, 0, 2); CUBE(1, 0, 2); CUBE(2, 0, 2); /* bottom back row */
364 static int cmp_squares (const void *a, const void *b);
365 static void delete_redundant_faces (sponge_configuration *);
368 build_sponge (sponge_configuration *sp, Bool wireframe_p, int countdown)
374 cube (sp, wireframe_p, 0, 0, 0, 1);
380 int facet_size = iexp(3, countdown);
381 cube (sp, wireframe_p, 0, 0, 0, facet_size);
383 descend_cubes (sp, wireframe_p, countdown - 1,
387 if (!wireframe_p && do_optimize)
389 qsort (sp->squares, sp->squares_fp, sizeof(*sp->squares),
391 delete_redundant_faces (sp);
397 GLfloat s = 1.0 / iexp (3, countdown);
400 glDeleteLists (sp->sponge_list0, 1);
401 glDeleteLists (sp->sponge_list1, 1);
402 glDeleteLists (sp->sponge_list2, 1);
404 for (j = 0; j < 3; j++)
407 glNewList ((j == 0 ? sp->sponge_list0 :
408 j == 1 ? sp->sponge_list1 :
412 glTranslatef (-1.5, -1.5, -1.5);
415 for (i = 0; i < sp->squares_fp; i++)
417 if ((j == 0 && sq->nx != 0) ||
418 (j == 1 && sq->ny != 0) ||
419 (j == 2 && sq->nz != 0))
421 glBegin (wireframe_p ? GL_LINE_LOOP : GL_QUADS);
422 glNormal3i (sq->nx, sq->ny, sq->nz);
425 glVertex3i (sq->x1, sq->y0, sq->z0);
426 glVertex3i (sq->x1, sq->y1, sq->z0);
427 glVertex3i (sq->x0, sq->y1, sq->z0);
428 glVertex3i (sq->x0, sq->y0, sq->z0);
432 glVertex3i (sq->x1, sq->y0, sq->z0);
433 glVertex3i (sq->x1, sq->y0, sq->z1);
434 glVertex3i (sq->x0, sq->y0, sq->z1);
435 glVertex3i (sq->x0, sq->y0, sq->z0);
439 glVertex3i (sq->x0, sq->y1, sq->z0);
440 glVertex3i (sq->x0, sq->y1, sq->z1);
441 glVertex3i (sq->x0, sq->y0, sq->z1);
442 glVertex3i (sq->x0, sq->y0, sq->z0);
456 cmp_squares (const void *aa, const void *bb)
458 square *a = (square *) aa;
459 square *b = (square *) bb;
462 p0 = (a->x0 < a->x1 ? a->x0 : a->x1);
463 p1 = (b->x0 < b->x1 ? b->x0 : b->x1);
464 if ((i = (p0 - p1))) return i;
466 p0 = (a->y0 < a->y1 ? a->y0 : a->y1);
467 p1 = (b->y0 < b->y1 ? b->y0 : b->y1);
468 if ((i = (p0 - p1))) return i;
470 p0 = (a->z0 < a->z1 ? a->z0 : a->z1);
471 p1 = (b->z0 < b->z1 ? b->z0 : b->z1);
472 if ((i = (p0 - p1))) return i;
475 p0 = (a->x0 > a->x1 ? a->x0 : a->x1);
476 p1 = (b->x0 > b->x1 ? b->x0 : b->x1);
477 if ((i = (p0 - p1))) return i;
479 p0 = (a->y0 > a->y1 ? a->y0 : a->y1);
480 p1 = (b->y0 > b->y1 ? b->y0 : b->y1);
481 if ((i = (p0 - p1))) return i;
483 p0 = (a->z0 > a->z1 ? a->z0 : a->z1);
484 p1 = (b->z0 > b->z1 ? b->z0 : b->z1);
485 if ((i = (p0 - p1))) return i;
493 delete_redundant_faces (sponge_configuration *sp)
495 square *sq = sp->squares;
496 square *end = sq + sp->squares_fp;
502 if (cmp_squares (sq, sq+1)) /* they differ - keep this one */
513 fprintf (stderr, "%s: optimized away %d polygons (%d%%)\n",
516 100 - ((i * 100) / sp->squares_fp));
524 init_sponge (ModeInfo *mi)
526 sponge_configuration *sp;
529 sps = (sponge_configuration *)
530 calloc (MI_NUM_SCREENS(mi), sizeof (sponge_configuration));
532 fprintf(stderr, "%s: out of memory\n", progname);
536 sp = &sps[MI_SCREEN(mi)];
539 sp = &sps[MI_SCREEN(mi)];
541 if ((sp->glx_context = init_GL(mi)) != NULL) {
543 reshape_sponge (mi, MI_WIDTH(mi), MI_HEIGHT(mi));
546 sp->rotx = frand(1.0) * RANDSIGN();
547 sp->roty = frand(1.0) * RANDSIGN();
548 sp->rotz = frand(1.0) * RANDSIGN();
550 /* bell curve from 0-3 degrees, avg 1.5 */
551 sp->dx = (frand(1) + frand(1) + frand(1)) / (360/2);
552 sp->dy = (frand(1) + frand(1) + frand(1)) / (360/2);
553 sp->dz = (frand(1) + frand(1) + frand(1)) / (360/2);
555 sp->d_max = sp->dx * 2;
557 sp->ddx = 0.00006 + frand(0.00003);
558 sp->ddy = 0.00006 + frand(0.00003);
559 sp->ddz = 0.00006 + frand(0.00003);
562 sp->colors = (XColor *) calloc(sp->ncolors, sizeof(XColor));
563 make_smooth_colormap (0, 0, 0,
564 sp->colors, &sp->ncolors,
567 sp->ccolor1 = sp->ncolors / 3;
568 sp->ccolor2 = sp->ccolor1 * 2;
571 int d = max_depth < 1 ? 1 : max_depth;
572 unsigned long facet_size = iexp(3, d);
574 float be_miserly = 0.741;
575 sp->squares_size = iexp(facet_size, 3) * 6 * be_miserly;
576 bytes = sp->squares_size * sizeof (*sp->squares);
579 sp->squares = calloc (1, bytes);
583 fprintf (stderr, "%s: out of memory", progname);
584 if ((sp->squares_size >> 20) > 1)
585 fprintf (stderr, " (%luMB for %luM polygons)\n",
586 bytes >> 20, sp->squares_size >> 20);
588 fprintf (stderr, " (%luKB for %luK polygons)\n",
589 bytes >> 10, sp->squares_size >> 10);
594 sp->sponge_list0 = glGenLists (1);
595 sp->sponge_list1 = glGenLists (1);
596 sp->sponge_list2 = glGenLists (1);
601 draw_sponge (ModeInfo *mi)
603 sponge_configuration *sp = &sps[MI_SCREEN(mi)];
604 Display *dpy = MI_DISPLAY(mi);
605 Window window = MI_WINDOW(mi);
607 static GLfloat color0[4] = {0.0, 0.0, 0.0, 1.0};
608 static GLfloat color1[4] = {0.0, 0.0, 0.0, 1.0};
609 static GLfloat color2[4] = {0.0, 0.0, 0.0, 1.0};
611 static int tick = 99999;
613 if (!sp->glx_context)
616 glShadeModel(GL_SMOOTH);
618 glEnable(GL_DEPTH_TEST);
619 glEnable(GL_NORMALIZE);
620 glEnable(GL_CULL_FACE);
622 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
626 glScalef(1.1, 1.1, 1.1);
633 static int frame = 0;
635 # define SINOID(SCALE,SIZE) \
636 ((((1 + sin((frame * (SCALE)) / 2 * M_PI)) / 2.0) * (SIZE)) - (SIZE)/2)
638 x = SINOID(0.0071, 8.0);
639 y = SINOID(0.0053, 6.0);
640 z = SINOID(0.0037, 15.0);
642 glTranslatef(x, y, z);
650 if (x < 0) x = 1 - (x + 1);
651 if (y < 0) y = 1 - (y + 1);
652 if (z < 0) z = 1 - (z + 1);
654 glRotatef(x * 360, 1.0, 0.0, 0.0);
655 glRotatef(y * 360, 0.0, 1.0, 0.0);
656 glRotatef(z * 360, 0.0, 0.0, 1.0);
658 rotate(&sp->rotx, &sp->dx, &sp->ddx, sp->d_max);
659 rotate(&sp->roty, &sp->dy, &sp->ddy, sp->d_max);
660 rotate(&sp->rotz, &sp->dz, &sp->ddz, sp->d_max);
664 color0[0] = sp->colors[sp->ccolor0].red / 65536.0;
665 color0[1] = sp->colors[sp->ccolor0].green / 65536.0;
666 color0[2] = sp->colors[sp->ccolor0].blue / 65536.0;
668 color1[0] = sp->colors[sp->ccolor1].red / 65536.0;
669 color1[1] = sp->colors[sp->ccolor1].green / 65536.0;
670 color1[2] = sp->colors[sp->ccolor1].blue / 65536.0;
672 color2[0] = sp->colors[sp->ccolor2].red / 65536.0;
673 color2[1] = sp->colors[sp->ccolor2].green / 65536.0;
674 color2[2] = sp->colors[sp->ccolor2].blue / 65536.0;
680 if (sp->ccolor0 >= sp->ncolors) sp->ccolor0 = 0;
681 if (sp->ccolor1 >= sp->ncolors) sp->ccolor1 = 0;
682 if (sp->ccolor2 >= sp->ncolors) sp->ccolor2 = 0;
687 if (sp->current_depth >= max_depth)
688 sp->current_depth = -max_depth;
692 (sp->current_depth < 0
693 ? -sp->current_depth : sp->current_depth));
696 glScalef (2.0, 2.0, 2.0);
698 glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color0);
699 glCallList (sp->sponge_list0);
700 glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color1);
701 glCallList (sp->sponge_list1);
702 glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color2);
703 glCallList (sp->sponge_list2);
707 if (mi->fps_p) do_fps (mi);
710 glXSwapBuffers(dpy, window);