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 HACK_HANDLE_EVENT sponge_handle_event
66 #define EVENT_MASK PointerMotionMask
67 #define sws_opts xlockmore_opts
69 #define DEF_SPIN "True"
70 #define DEF_WANDER "True"
71 #define DEF_SPEED "150"
72 #define DEF_MAX_DEPTH "3"
73 #define DEF_OPTIMIZE "True"
75 #define DEFAULTS "*delay: 30000 \n" \
76 "*showFPS: False \n" \
77 "*wireframe: False \n" \
78 "*maxDepth: " DEF_MAX_DEPTH "\n" \
79 "*speed:" DEF_SPEED "\n" \
80 "*optimize:" DEF_OPTIMIZE "\n" \
81 "*spin: " DEF_SPIN "\n" \
82 "*wander: " DEF_WANDER "\n" \
86 #define countof(x) (sizeof((x))/sizeof((*x)))
88 #include "xlockmore.h"
91 #include "gltrackball.h"
94 #ifdef USE_GL /* whole file */
99 unsigned int x0 : 8; /* 8 bottom left */
100 unsigned int y0 : 8; /* 16 */
101 unsigned int z0 : 8; /* 24 */
103 unsigned int x1 : 8; /* 32 top right */
104 unsigned int y1 : 8; /* 40 */
105 unsigned int z1 : 8; /* 48 */
107 int nx : 2; /* 50 normal */
111 /* 2 bits left over; 56 bits / 7 bytes total, */
112 /* which is surely rounded up to 8 bytes. */
117 GLXContext *glx_context;
119 trackball_state *trackball;
121 GLuint sponge_list0; /* we store X, Y, and Z-facing surfaces */
122 GLuint sponge_list1; /* in their own lists, to make it easy */
123 GLuint sponge_list2; /* to color them differently. */
126 unsigned long squares_size;
127 unsigned long squares_fp;
137 } sponge_configuration;
139 static sponge_configuration *sps = NULL;
142 static Bool do_wander;
144 static Bool do_optimize;
145 static int max_depth;
147 static XrmOptionDescRec opts[] = {
148 { "-spin", ".spin", XrmoptionNoArg, "True" },
149 { "+spin", ".spin", XrmoptionNoArg, "False" },
150 { "-wander", ".wander", XrmoptionNoArg, "True" },
151 { "+wander", ".wander", XrmoptionNoArg, "False" },
152 { "-speed", ".speed", XrmoptionSepArg, 0 },
153 { "-optimize", ".optimize", XrmoptionNoArg, "True" },
154 { "+optimize", ".optimize", XrmoptionNoArg, "False" },
155 {"-depth", ".maxDepth", XrmoptionSepArg, (caddr_t) 0 },
158 static argtype vars[] = {
159 {(caddr_t *) &do_spin, "spin", "Spin", DEF_SPIN, t_Bool},
160 {(caddr_t *) &do_wander, "wander", "Wander", DEF_WANDER, t_Bool},
161 {(caddr_t *) &speed, "speed", "Speed", DEF_SPEED, t_Int},
162 {(caddr_t *) &do_optimize, "optimize", "Optimize", DEF_OPTIMIZE, t_Bool},
163 {(caddr_t *) &max_depth, "maxDepth", "MaxDepth", DEF_MAX_DEPTH, t_Int},
166 ModeSpecOpt sws_opts = {countof(opts), opts, countof(vars), vars, NULL};
169 /* Window management, etc
172 reshape_sponge (ModeInfo *mi, int width, int height)
174 GLfloat h = (GLfloat) height / (GLfloat) width;
176 glViewport (0, 0, (GLint) width, (GLint) height);
178 glMatrixMode(GL_PROJECTION);
180 gluPerspective (30.0, 1/h, 1.0, 100.0);
182 glMatrixMode(GL_MODELVIEW);
184 gluLookAt( 0.0, 0.0, 30.0,
188 glClear(GL_COLOR_BUFFER_BIT);
192 /* Pushes a 1x1x1 cube at XYZ into the sp->squares list.
195 cube (sponge_configuration *sp, Bool wireframe_p,
196 int x, int y, int z, int s)
200 # define PP(NX, NY, NZ, X0, Y0, Z0, X1, Y1, Z1) \
201 (sq = &sp->squares[sp->squares_fp++], \
205 sq->x0 = x+((X0)*s), \
206 sq->y0 = y+((Y0)*s), \
207 sq->z0 = z+((Z0)*s), \
208 sq->x1 = x+((X1)*s), \
209 sq->y1 = y+((Y1)*s), \
212 PP (0, 0, -1, 0, 1, 0, 1, 0, 0);
213 PP (0, 0, 1, 0, 0, 1, 1, 1, 1);
214 PP (0, -1, 0, 0, 0, 0, 1, 0, 1);
215 PP (0, 1, 0, 0, 1, 1, 1, 1, 0);
217 if (wireframe_p) return; /* don't need the rest */
219 PP (-1, 0, 0, 0, 0, 1, 0, 1, 0);
220 PP ( 1, 0, 0, 1, 0, 0, 1, 1, 1);
223 if (sp->squares_fp >= sp->squares_size) abort();
231 while (n-- > 0) ii *= i;
237 descend_cubes (sponge_configuration *sp, Bool wireframe_p, int countdown,
240 int descend_p = (countdown > 0);
241 int facet_size = iexp (3, countdown);
246 cube (sp, wireframe_p, x+1*s, y+1*s, z, 1);
247 cube (sp, wireframe_p, x+1*s, y+1*s, z+2*s, 1);
248 cube (sp, wireframe_p, x, y+1*s, z+1*s, 1);
249 cube (sp, wireframe_p, x+2*s, y+1*s, z+1*s, 1);
250 cube (sp, wireframe_p, x+1*s, y, z+1*s, 1);
251 cube (sp, wireframe_p, x+1*s, y+2*s, z+1*s, 1);
253 if (!descend_p) return;
256 # define CUBE(xx,yy,zz) \
258 ? descend_cubes (sp, wireframe_p, countdown-1, \
259 x+(xx)*s, y+(yy)*s, z+(zz)*s) \
260 : cube (sp, wireframe_p, x+(xx)*s, y+(yy)*s, z+(zz)*s, 1))
262 CUBE(0, 2, 0); CUBE(1, 2, 0); CUBE(2, 2, 0); /* top front row */
263 CUBE(0, 1, 0); CUBE(2, 1, 0); /* middle front row */
264 CUBE(0, 0, 0); CUBE(1, 0, 0); CUBE(2, 0, 0); /* bottom front row */
265 CUBE(0, 2, 1); CUBE(2, 2, 1); /* top middle row */
266 CUBE(0, 0, 1); CUBE(2, 0, 1); /* bottom middle row */
267 CUBE(0, 2, 2); CUBE(1, 2, 2); CUBE(2, 2, 2); /* top back row */
268 CUBE(0, 1, 2); CUBE(2, 1, 2); /* middle back row */
269 CUBE(0, 0, 2); CUBE(1, 0, 2); CUBE(2, 0, 2); /* bottom back row */
274 static int cmp_squares (const void *a, const void *b);
275 static void delete_redundant_faces (sponge_configuration *);
278 build_sponge (sponge_configuration *sp, Bool wireframe_p, int countdown)
284 cube (sp, wireframe_p, 0, 0, 0, 1);
290 int facet_size = iexp(3, countdown);
291 cube (sp, wireframe_p, 0, 0, 0, facet_size);
293 descend_cubes (sp, wireframe_p, countdown - 1,
297 if (!wireframe_p && do_optimize)
299 qsort (sp->squares, sp->squares_fp, sizeof(*sp->squares),
301 delete_redundant_faces (sp);
307 GLfloat s = 1.0 / iexp (3, countdown);
310 glDeleteLists (sp->sponge_list0, 1);
311 glDeleteLists (sp->sponge_list1, 1);
312 glDeleteLists (sp->sponge_list2, 1);
314 for (j = 0; j < 3; j++)
317 glNewList ((j == 0 ? sp->sponge_list0 :
318 j == 1 ? sp->sponge_list1 :
322 glTranslatef (-1.5, -1.5, -1.5);
325 for (i = 0; i < sp->squares_fp; i++)
327 if ((j == 0 && sq->nx != 0) ||
328 (j == 1 && sq->ny != 0) ||
329 (j == 2 && sq->nz != 0))
331 glBegin (wireframe_p ? GL_LINE_LOOP : GL_QUADS);
332 glNormal3i (sq->nx, sq->ny, sq->nz);
335 glVertex3i (sq->x1, sq->y0, sq->z0);
336 glVertex3i (sq->x1, sq->y1, sq->z0);
337 glVertex3i (sq->x0, sq->y1, sq->z0);
338 glVertex3i (sq->x0, sq->y0, sq->z0);
342 glVertex3i (sq->x1, sq->y0, sq->z0);
343 glVertex3i (sq->x1, sq->y0, sq->z1);
344 glVertex3i (sq->x0, sq->y0, sq->z1);
345 glVertex3i (sq->x0, sq->y0, sq->z0);
349 glVertex3i (sq->x0, sq->y1, sq->z0);
350 glVertex3i (sq->x0, sq->y1, sq->z1);
351 glVertex3i (sq->x0, sq->y0, sq->z1);
352 glVertex3i (sq->x0, sq->y0, sq->z0);
366 cmp_squares (const void *aa, const void *bb)
368 square *a = (square *) aa;
369 square *b = (square *) bb;
372 p0 = (a->x0 < a->x1 ? a->x0 : a->x1);
373 p1 = (b->x0 < b->x1 ? b->x0 : b->x1);
374 if ((i = (p0 - p1))) return i;
376 p0 = (a->y0 < a->y1 ? a->y0 : a->y1);
377 p1 = (b->y0 < b->y1 ? b->y0 : b->y1);
378 if ((i = (p0 - p1))) return i;
380 p0 = (a->z0 < a->z1 ? a->z0 : a->z1);
381 p1 = (b->z0 < b->z1 ? b->z0 : b->z1);
382 if ((i = (p0 - p1))) return i;
385 p0 = (a->x0 > a->x1 ? a->x0 : a->x1);
386 p1 = (b->x0 > b->x1 ? b->x0 : b->x1);
387 if ((i = (p0 - p1))) return i;
389 p0 = (a->y0 > a->y1 ? a->y0 : a->y1);
390 p1 = (b->y0 > b->y1 ? b->y0 : b->y1);
391 if ((i = (p0 - p1))) return i;
393 p0 = (a->z0 > a->z1 ? a->z0 : a->z1);
394 p1 = (b->z0 > b->z1 ? b->z0 : b->z1);
395 if ((i = (p0 - p1))) return i;
403 delete_redundant_faces (sponge_configuration *sp)
405 square *sq = sp->squares;
406 square *end = sq + sp->squares_fp;
412 if (cmp_squares (sq, sq+1)) /* they differ - keep this one */
423 fprintf (stderr, "%s: optimized away %d polygons (%d%%)\n",
426 100 - ((i * 100) / sp->squares_fp));
434 sponge_handle_event (ModeInfo *mi, XEvent *event)
436 sponge_configuration *sp = &sps[MI_SCREEN(mi)];
438 if (event->xany.type == ButtonPress &&
439 event->xbutton.button & Button1)
441 sp->button_down_p = True;
442 gltrackball_start (sp->trackball,
443 event->xbutton.x, event->xbutton.y,
444 MI_WIDTH (mi), MI_HEIGHT (mi));
447 else if (event->xany.type == ButtonRelease &&
448 event->xbutton.button & Button1)
450 sp->button_down_p = False;
453 else if (event->xany.type == MotionNotify &&
456 gltrackball_track (sp->trackball,
457 event->xmotion.x, event->xmotion.y,
458 MI_WIDTH (mi), MI_HEIGHT (mi));
468 init_sponge (ModeInfo *mi)
470 sponge_configuration *sp;
471 int wire = MI_IS_WIREFRAME(mi);
474 sps = (sponge_configuration *)
475 calloc (MI_NUM_SCREENS(mi), sizeof (sponge_configuration));
477 fprintf(stderr, "%s: out of memory\n", progname);
481 sp = &sps[MI_SCREEN(mi)];
484 sp = &sps[MI_SCREEN(mi)];
486 if ((sp->glx_context = init_GL(mi)) != NULL) {
487 reshape_sponge (mi, MI_WIDTH(mi), MI_HEIGHT(mi));
492 static GLfloat pos0[4] = {-1.0, -1.0, 1.0, 0.1};
493 static GLfloat pos1[4] = { 1.0, -0.2, 0.2, 0.1};
494 static GLfloat dif0[4] = {1.0, 1.0, 1.0, 1.0};
495 static GLfloat dif1[4] = {1.0, 1.0, 1.0, 1.0};
497 glLightfv(GL_LIGHT0, GL_POSITION, pos0);
498 glLightfv(GL_LIGHT1, GL_POSITION, pos1);
499 glLightfv(GL_LIGHT0, GL_DIFFUSE, dif0);
500 glLightfv(GL_LIGHT1, GL_DIFFUSE, dif1);
502 glEnable(GL_LIGHTING);
506 glEnable(GL_DEPTH_TEST);
507 glEnable(GL_CULL_FACE);
511 double spin_speed = 1.0;
512 double wander_speed = 0.03;
513 sp->rot = make_rotator (do_spin ? spin_speed : 0,
514 do_spin ? spin_speed : 0,
515 do_spin ? spin_speed : 0,
517 do_wander ? wander_speed : 0,
519 sp->trackball = gltrackball_init ();
523 sp->colors = (XColor *) calloc(sp->ncolors, sizeof(XColor));
524 make_smooth_colormap (0, 0, 0,
525 sp->colors, &sp->ncolors,
528 sp->ccolor1 = sp->ncolors / 3;
529 sp->ccolor2 = sp->ccolor1 * 2;
532 int d = max_depth < 1 ? 1 : max_depth;
533 unsigned long facet_size = iexp(3, d);
535 float be_miserly = 0.741;
536 sp->squares_size = iexp(facet_size, 3) * 6 * be_miserly;
537 bytes = sp->squares_size * sizeof (*sp->squares);
540 sp->squares = calloc (1, bytes);
544 fprintf (stderr, "%s: out of memory", progname);
545 if ((sp->squares_size >> 20) > 1)
546 fprintf (stderr, " (%luMB for %luM polygons)\n",
547 bytes >> 20, sp->squares_size >> 20);
549 fprintf (stderr, " (%luKB for %luK polygons)\n",
550 bytes >> 10, sp->squares_size >> 10);
555 sp->sponge_list0 = glGenLists (1);
556 sp->sponge_list1 = glGenLists (1);
557 sp->sponge_list2 = glGenLists (1);
562 draw_sponge (ModeInfo *mi)
564 sponge_configuration *sp = &sps[MI_SCREEN(mi)];
565 Display *dpy = MI_DISPLAY(mi);
566 Window window = MI_WINDOW(mi);
568 static GLfloat color0[4] = {0.0, 0.0, 0.0, 1.0};
569 static GLfloat color1[4] = {0.0, 0.0, 0.0, 1.0};
570 static GLfloat color2[4] = {0.0, 0.0, 0.0, 1.0};
572 static int tick = 99999;
574 if (!sp->glx_context)
577 glShadeModel(GL_SMOOTH);
579 glEnable(GL_DEPTH_TEST);
580 glEnable(GL_NORMALIZE);
581 glEnable(GL_CULL_FACE);
583 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
587 glScalef(1.1, 1.1, 1.1);
591 get_position (sp->rot, &x, &y, &z, !sp->button_down_p);
592 glTranslatef((x - 0.5) * 8,
596 gltrackball_rotate (sp->trackball);
598 get_rotation (sp->rot, &x, &y, &z, !sp->button_down_p);
599 glRotatef (x * 360, 1.0, 0.0, 0.0);
600 glRotatef (y * 360, 0.0, 1.0, 0.0);
601 glRotatef (z * 360, 0.0, 0.0, 1.0);
604 color0[0] = sp->colors[sp->ccolor0].red / 65536.0;
605 color0[1] = sp->colors[sp->ccolor0].green / 65536.0;
606 color0[2] = sp->colors[sp->ccolor0].blue / 65536.0;
608 color1[0] = sp->colors[sp->ccolor1].red / 65536.0;
609 color1[1] = sp->colors[sp->ccolor1].green / 65536.0;
610 color1[2] = sp->colors[sp->ccolor1].blue / 65536.0;
612 color2[0] = sp->colors[sp->ccolor2].red / 65536.0;
613 color2[1] = sp->colors[sp->ccolor2].green / 65536.0;
614 color2[2] = sp->colors[sp->ccolor2].blue / 65536.0;
620 if (sp->ccolor0 >= sp->ncolors) sp->ccolor0 = 0;
621 if (sp->ccolor1 >= sp->ncolors) sp->ccolor1 = 0;
622 if (sp->ccolor2 >= sp->ncolors) sp->ccolor2 = 0;
627 if (sp->current_depth >= max_depth)
628 sp->current_depth = -max_depth;
632 (sp->current_depth < 0
633 ? -sp->current_depth : sp->current_depth));
635 mi->polygon_count = sp->squares_fp; /* for FPS display */
638 glScalef (2.0, 2.0, 2.0);
640 glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color0);
641 glCallList (sp->sponge_list0);
642 glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color1);
643 glCallList (sp->sponge_list1);
644 glMaterialfv (GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color2);
645 glCallList (sp->sponge_list2);
649 if (mi->fps_p) do_fps (mi);
652 glXSwapBuffers(dpy, window);