1 /* menger, Copyright (c) 2001, 2002 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);
192 /* lifted from lament.c */
193 #define RAND(n) ((long) ((random() & 0x7fffffff) % ((long) (n))))
194 #define RANDSIGN() ((random() & 1) ? 1 : -1)
197 rotate(GLfloat *pos, GLfloat *v, GLfloat *dv, GLfloat max_v)
212 if (ppos < 0) abort();
213 if (ppos > 1.0) abort();
214 *pos = (*pos > 0 ? ppos : -ppos);
220 if (*v > max_v || *v < -max_v)
224 /* If it stops, start it going in the other direction. */
231 /* keep going in the same direction */
246 /* Alter direction of rotational acceleration randomly. */
247 if (! (random() % 120))
250 /* Change acceleration very occasionally. */
251 if (! (random() % 200))
255 else if (random() & 1)
263 /* Pushes a 1x1x1 cube at XYZ into the sp->squares list.
266 cube (sponge_configuration *sp, Bool wireframe_p,
267 int x, int y, int z, int s)
271 # define PP(NX, NY, NZ, X0, Y0, Z0, X1, Y1, Z1) \
272 (sq = &sp->squares[sp->squares_fp++], \
276 sq->x0 = x+((X0)*s), \
277 sq->y0 = y+((Y0)*s), \
278 sq->z0 = z+((Z0)*s), \
279 sq->x1 = x+((X1)*s), \
280 sq->y1 = y+((Y1)*s), \
283 PP (0, 0, -1, 0, 1, 0, 1, 0, 0);
284 PP (0, 0, 1, 0, 0, 1, 1, 1, 1);
285 PP (0, -1, 0, 0, 0, 0, 1, 0, 1);
286 PP (0, 1, 0, 0, 1, 1, 1, 1, 0);
288 if (wireframe_p) return; /* don't need the rest */
290 PP (-1, 0, 0, 0, 0, 1, 0, 1, 0);
291 PP ( 1, 0, 0, 1, 0, 0, 1, 1, 1);
294 if (sp->squares_fp >= sp->squares_size) abort();
302 while (n-- > 0) ii *= i;
308 descend_cubes (sponge_configuration *sp, Bool wireframe_p, int countdown,
311 int descend_p = (countdown > 0);
312 int facet_size = iexp (3, countdown);
317 cube (sp, wireframe_p, x+1*s, y+1*s, z, 1);
318 cube (sp, wireframe_p, x+1*s, y+1*s, z+2*s, 1);
319 cube (sp, wireframe_p, x, y+1*s, z+1*s, 1);
320 cube (sp, wireframe_p, x+2*s, y+1*s, z+1*s, 1);
321 cube (sp, wireframe_p, x+1*s, y, z+1*s, 1);
322 cube (sp, wireframe_p, x+1*s, y+2*s, z+1*s, 1);
324 if (!descend_p) return;
327 # define CUBE(xx,yy,zz) \
329 ? descend_cubes (sp, wireframe_p, countdown-1, \
330 x+(xx)*s, y+(yy)*s, z+(zz)*s) \
331 : cube (sp, wireframe_p, x+(xx)*s, y+(yy)*s, z+(zz)*s, 1))
333 CUBE(0, 2, 0); CUBE(1, 2, 0); CUBE(2, 2, 0); /* top front row */
334 CUBE(0, 1, 0); CUBE(2, 1, 0); /* middle front row */
335 CUBE(0, 0, 0); CUBE(1, 0, 0); CUBE(2, 0, 0); /* bottom front row */
336 CUBE(0, 2, 1); CUBE(2, 2, 1); /* top middle row */
337 CUBE(0, 0, 1); CUBE(2, 0, 1); /* bottom middle row */
338 CUBE(0, 2, 2); CUBE(1, 2, 2); CUBE(2, 2, 2); /* top back row */
339 CUBE(0, 1, 2); CUBE(2, 1, 2); /* middle back row */
340 CUBE(0, 0, 2); CUBE(1, 0, 2); CUBE(2, 0, 2); /* bottom back row */
345 static int cmp_squares (const void *a, const void *b);
346 static void delete_redundant_faces (sponge_configuration *);
349 build_sponge (sponge_configuration *sp, Bool wireframe_p, int countdown)
355 cube (sp, wireframe_p, 0, 0, 0, 1);
361 int facet_size = iexp(3, countdown);
362 cube (sp, wireframe_p, 0, 0, 0, facet_size);
364 descend_cubes (sp, wireframe_p, countdown - 1,
368 if (!wireframe_p && do_optimize)
370 qsort (sp->squares, sp->squares_fp, sizeof(*sp->squares),
372 delete_redundant_faces (sp);
378 GLfloat s = 1.0 / iexp (3, countdown);
381 glDeleteLists (sp->sponge_list0, 1);
382 glDeleteLists (sp->sponge_list1, 1);
383 glDeleteLists (sp->sponge_list2, 1);
385 for (j = 0; j < 3; j++)
388 glNewList ((j == 0 ? sp->sponge_list0 :
389 j == 1 ? sp->sponge_list1 :
393 glTranslatef (-1.5, -1.5, -1.5);
396 for (i = 0; i < sp->squares_fp; i++)
398 if ((j == 0 && sq->nx != 0) ||
399 (j == 1 && sq->ny != 0) ||
400 (j == 2 && sq->nz != 0))
402 glBegin (wireframe_p ? GL_LINE_LOOP : GL_QUADS);
403 glNormal3i (sq->nx, sq->ny, sq->nz);
406 glVertex3i (sq->x1, sq->y0, sq->z0);
407 glVertex3i (sq->x1, sq->y1, sq->z0);
408 glVertex3i (sq->x0, sq->y1, sq->z0);
409 glVertex3i (sq->x0, sq->y0, sq->z0);
413 glVertex3i (sq->x1, sq->y0, sq->z0);
414 glVertex3i (sq->x1, sq->y0, sq->z1);
415 glVertex3i (sq->x0, sq->y0, sq->z1);
416 glVertex3i (sq->x0, sq->y0, sq->z0);
420 glVertex3i (sq->x0, sq->y1, sq->z0);
421 glVertex3i (sq->x0, sq->y1, sq->z1);
422 glVertex3i (sq->x0, sq->y0, sq->z1);
423 glVertex3i (sq->x0, sq->y0, sq->z0);
437 cmp_squares (const void *aa, const void *bb)
439 square *a = (square *) aa;
440 square *b = (square *) bb;
443 p0 = (a->x0 < a->x1 ? a->x0 : a->x1);
444 p1 = (b->x0 < b->x1 ? b->x0 : b->x1);
445 if ((i = (p0 - p1))) return i;
447 p0 = (a->y0 < a->y1 ? a->y0 : a->y1);
448 p1 = (b->y0 < b->y1 ? b->y0 : b->y1);
449 if ((i = (p0 - p1))) return i;
451 p0 = (a->z0 < a->z1 ? a->z0 : a->z1);
452 p1 = (b->z0 < b->z1 ? b->z0 : b->z1);
453 if ((i = (p0 - p1))) return i;
456 p0 = (a->x0 > a->x1 ? a->x0 : a->x1);
457 p1 = (b->x0 > b->x1 ? b->x0 : b->x1);
458 if ((i = (p0 - p1))) return i;
460 p0 = (a->y0 > a->y1 ? a->y0 : a->y1);
461 p1 = (b->y0 > b->y1 ? b->y0 : b->y1);
462 if ((i = (p0 - p1))) return i;
464 p0 = (a->z0 > a->z1 ? a->z0 : a->z1);
465 p1 = (b->z0 > b->z1 ? b->z0 : b->z1);
466 if ((i = (p0 - p1))) return i;
474 delete_redundant_faces (sponge_configuration *sp)
476 square *sq = sp->squares;
477 square *end = sq + sp->squares_fp;
483 if (cmp_squares (sq, sq+1)) /* they differ - keep this one */
494 fprintf (stderr, "%s: optimized away %d polygons (%d%%)\n",
497 100 - ((i * 100) / sp->squares_fp));
505 init_sponge (ModeInfo *mi)
507 sponge_configuration *sp;
508 int wire = MI_IS_WIREFRAME(mi);
511 sps = (sponge_configuration *)
512 calloc (MI_NUM_SCREENS(mi), sizeof (sponge_configuration));
514 fprintf(stderr, "%s: out of memory\n", progname);
518 sp = &sps[MI_SCREEN(mi)];
521 sp = &sps[MI_SCREEN(mi)];
523 if ((sp->glx_context = init_GL(mi)) != NULL) {
524 reshape_sponge (mi, MI_WIDTH(mi), MI_HEIGHT(mi));
529 static GLfloat pos0[4] = {-1.0, -1.0, 1.0, 0.1};
530 static GLfloat pos1[4] = { 1.0, -0.2, 0.2, 0.1};
531 static GLfloat dif0[4] = {1.0, 1.0, 1.0, 1.0};
532 static GLfloat dif1[4] = {1.0, 1.0, 1.0, 1.0};
534 glLightfv(GL_LIGHT0, GL_POSITION, pos0);
535 glLightfv(GL_LIGHT1, GL_POSITION, pos1);
536 glLightfv(GL_LIGHT0, GL_DIFFUSE, dif0);
537 glLightfv(GL_LIGHT1, GL_DIFFUSE, dif1);
539 glEnable(GL_LIGHTING);
543 glEnable(GL_DEPTH_TEST);
544 glEnable(GL_CULL_FACE);
547 sp->rotx = frand(1.0) * RANDSIGN();
548 sp->roty = frand(1.0) * RANDSIGN();
549 sp->rotz = frand(1.0) * RANDSIGN();
551 /* bell curve from 0-3 degrees, avg 1.5 */
552 sp->dx = (frand(1) + frand(1) + frand(1)) / (360/2);
553 sp->dy = (frand(1) + frand(1) + frand(1)) / (360/2);
554 sp->dz = (frand(1) + frand(1) + frand(1)) / (360/2);
556 sp->d_max = sp->dx * 2;
558 sp->ddx = 0.00006 + frand(0.00003);
559 sp->ddy = 0.00006 + frand(0.00003);
560 sp->ddz = 0.00006 + frand(0.00003);
563 sp->colors = (XColor *) calloc(sp->ncolors, sizeof(XColor));
564 make_smooth_colormap (0, 0, 0,
565 sp->colors, &sp->ncolors,
568 sp->ccolor1 = sp->ncolors / 3;
569 sp->ccolor2 = sp->ccolor1 * 2;
572 int d = max_depth < 1 ? 1 : max_depth;
573 unsigned long facet_size = iexp(3, d);
575 float be_miserly = 0.741;
576 sp->squares_size = iexp(facet_size, 3) * 6 * be_miserly;
577 bytes = sp->squares_size * sizeof (*sp->squares);
580 sp->squares = calloc (1, bytes);
584 fprintf (stderr, "%s: out of memory", progname);
585 if ((sp->squares_size >> 20) > 1)
586 fprintf (stderr, " (%luMB for %luM polygons)\n",
587 bytes >> 20, sp->squares_size >> 20);
589 fprintf (stderr, " (%luKB for %luK polygons)\n",
590 bytes >> 10, sp->squares_size >> 10);
595 sp->sponge_list0 = glGenLists (1);
596 sp->sponge_list1 = glGenLists (1);
597 sp->sponge_list2 = glGenLists (1);
602 draw_sponge (ModeInfo *mi)
604 sponge_configuration *sp = &sps[MI_SCREEN(mi)];
605 Display *dpy = MI_DISPLAY(mi);
606 Window window = MI_WINDOW(mi);
608 static GLfloat color0[4] = {0.0, 0.0, 0.0, 1.0};
609 static GLfloat color1[4] = {0.0, 0.0, 0.0, 1.0};
610 static GLfloat color2[4] = {0.0, 0.0, 0.0, 1.0};
612 static int tick = 99999;
614 if (!sp->glx_context)
617 glShadeModel(GL_SMOOTH);
619 glEnable(GL_DEPTH_TEST);
620 glEnable(GL_NORMALIZE);
621 glEnable(GL_CULL_FACE);
623 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
627 glScalef(1.1, 1.1, 1.1);
634 static int frame = 0;
636 # define SINOID(SCALE,SIZE) \
637 ((((1 + sin((frame * (SCALE)) / 2 * M_PI)) / 2.0) * (SIZE)) - (SIZE)/2)
639 x = SINOID(0.0071, 8.0);
640 y = SINOID(0.0053, 6.0);
641 z = SINOID(0.0037, 15.0);
643 glTranslatef(x, y, z);
651 if (x < 0) x = 1 - (x + 1);
652 if (y < 0) y = 1 - (y + 1);
653 if (z < 0) z = 1 - (z + 1);
655 glRotatef(x * 360, 1.0, 0.0, 0.0);
656 glRotatef(y * 360, 0.0, 1.0, 0.0);
657 glRotatef(z * 360, 0.0, 0.0, 1.0);
659 rotate(&sp->rotx, &sp->dx, &sp->ddx, sp->d_max);
660 rotate(&sp->roty, &sp->dy, &sp->ddy, sp->d_max);
661 rotate(&sp->rotz, &sp->dz, &sp->ddz, sp->d_max);
665 color0[0] = sp->colors[sp->ccolor0].red / 65536.0;
666 color0[1] = sp->colors[sp->ccolor0].green / 65536.0;
667 color0[2] = sp->colors[sp->ccolor0].blue / 65536.0;
669 color1[0] = sp->colors[sp->ccolor1].red / 65536.0;
670 color1[1] = sp->colors[sp->ccolor1].green / 65536.0;
671 color1[2] = sp->colors[sp->ccolor1].blue / 65536.0;
673 color2[0] = sp->colors[sp->ccolor2].red / 65536.0;
674 color2[1] = sp->colors[sp->ccolor2].green / 65536.0;
675 color2[2] = sp->colors[sp->ccolor2].blue / 65536.0;
681 if (sp->ccolor0 >= sp->ncolors) sp->ccolor0 = 0;
682 if (sp->ccolor1 >= sp->ncolors) sp->ccolor1 = 0;
683 if (sp->ccolor2 >= sp->ncolors) sp->ccolor2 = 0;
688 if (sp->current_depth >= max_depth)
689 sp->current_depth = -max_depth;
693 (sp->current_depth < 0
694 ? -sp->current_depth : sp->current_depth));
696 mi->polygon_count = sp->squares_fp; /* for FPS display */
699 glScalef (2.0, 2.0, 2.0);
701 glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color0);
702 glCallList (sp->sponge_list0);
703 glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color1);
704 glCallList (sp->sponge_list1);
705 glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color2);
706 glCallList (sp->sponge_list2);
710 if (mi->fps_p) do_fps (mi);
713 glXSwapBuffers(dpy, window);