1 /* -*- Mode: C; tab-width: 4 -*-
2 * penrose --- quasiperiodic tilings.
5 /* As reported in News of the Weird:
7 In April, Sir Roger Penrose, a British math professor who has worked
8 with Stephen Hawking on such topics as relativity, black holes, and
9 whether time has a beginning, filed a copyright-infringement lawsuit
10 against the Kimberly-Clark Corporation, which Penrose said copied a
11 pattern he created (a pattern demonstrating that "a nonrepeating
12 pattern could exist in nature") for its Kleenex quilted toilet paper.
13 Penrose said he doesn't like litigation but, "When it comes to the
14 population of Great Britain being invited by a multinational to wipe
15 their bottoms on what appears to be the work of a Knight of the
16 Realm, then a last stand must be taken."
18 NOTW #491, 4-jul-1997, by Chuck Shepherd.
19 http://www.nine.org/notw/notw.html
23 #if !defined( lint ) && !defined( SABER )
24 static const char sccsid[] = "@(#)penrose.c 4.00 97/01/01 xlockmore";
27 /* Copyright (c) 1996 by Timo Korvola <tkorvola@dopey.hut.fi>
29 * Permission to use, copy, modify, and distribute this software and its
30 * documentation for any purpose and without fee is hereby granted,
31 * provided that the above copyright notice appear in all copies and that
32 * both that copyright notice and this permission notice appear in
33 * supporting documentation.
35 * This file is provided AS IS with no warranties of any kind. The author
36 * shall have no liability with respect to the infringement of copyrights,
37 * trade secrets or any patents by this file or any part thereof. In no
38 * event will the author be liable for any lost revenue or profits or
39 * other special, indirect and consequential damages.
42 * 10-May-97: jwz@jwz.org: turned into a standalone program.
43 * 09-Sep-96: Written. */
46 Be careful, this probably still has a few bugs (many of which may only
47 appear with a very low probability). These are seen with -verbose .
48 If one of these are hit penrose will reinitialize.
52 * See Onoda, Steinhardt, DiVincenzo and Socolar in
53 * Phys. Rev. Lett. 60, #25, 1988 or
54 * Strandburg in Computers in Physics, Sep/Oct 1991.
56 * This implementation uses the simpler version of the growth
57 * algorithm, i.e., if there are no forced vertices, a randomly chosen
58 * tile is added to a randomly chosen vertex (no preference for those
61 * There are two essential differences to the algorithm presented in
62 * the literature: First, we do not allow the tiling to enclose an
63 * untiled area. Whenever this is in danger of happening, we just
64 * do not add the tile, hoping for a better random choice the next
65 * time. Second, when choosing a vertex randomly, we will take
66 * one that lies withing the viewport if available. If this seems to
67 * cause enclosures in the forced rule case, we will allow invisible
68 * vertices to be chosen.
70 * Tiling is restarted whenever one of the following happens: there
71 * are no incomplete vertices within the viewport or the tiling has
72 * extended a window's length beyond the edge of the window
73 * horizontally or vertically or forced rule choice has failed 100
74 * times due to areas about to become enclosed.
79 # define PROGCLASS "Penrose"
80 # define HACK_INIT init_penrose
81 # define HACK_DRAW draw_penrose
82 # define penrose_opts xlockmore_opts
83 # define DEFAULTS "*delay: 10000 \n" \
86 # include "xlockmore.h" /* from the xscreensaver distribution */
87 #else /* !STANDALONE */
88 # include "xlock.h" /* from the xlockmore distribution */
89 #endif /* !STANDALONE */
93 * Annoyingly the ANSI C library people have reserved all identifiers
94 * ending with _t for future use. Hence we use _c as a suffix for
95 * typedefs (c for class, although this is not C++).
101 * In theory one could fit 10 tiles to a single vertex. However, the
102 * vertex rules only allow at most seven tiles to meet at a vertex.
105 #define MAX_TILES_PER_VERTEX 7
106 #define N_VERTEX_RULES 8
107 #define ALLOC_NODE( type) ((type *)malloc( sizeof( type)))
108 #define DEF_AMMANN "False"
112 /* How long in seconds should we wait before starting a new tiling? */
113 static long redo_delay = 3;
114 static long redo_delay_usec;
116 static XrmOptionDescRec opts[] =
118 {"-ammann", ".penrose.ammann", XrmoptionNoArg, (caddr_t) "on"},
119 {"+ammann", ".penrose.ammann", XrmoptionNoArg, (caddr_t) "off"},
120 {"-redoDelay", ".penrose.redoDelay", XrmoptionSepArg, NULL}
122 static argtype vars[] =
124 {(caddr_t *) & ammann, "ammann", "Ammann", DEF_AMMANN, t_Bool},
125 {(caddr_t *) & redo_delay, "redoDelay", "RedoDelay", "3", t_Int}
127 static OptionStruct desc[] =
129 {"-/+ammann", "turn on/off Ammann lines"},
130 {"-redoDelay", "delay between new tilings"}
133 ModeSpecOpt penrose_opts = { 3, opts, 2, vars, desc };
137 * These are used to specify directions. They can also be used in bit
138 * masks to specify a combination of directions.
145 * We do not actually maintain objects corresponding to the tiles since
146 * we do not really need them and they would only consume memory and
147 * cause additional bookkeeping. Instead we only have vertices, and
148 * each vertex lists the type of each adjacent tile as well as the
149 * position of the vertex on the tile (hereafter refered to as
150 * "corner"). These positions are numbered in counterclockwise order
151 * so that 0 is where two double arrows meet (see one of the
152 * articles). The tile type and vertex number are stored in a single
153 * integer (we use char, and even most of it remains unused).
155 * The primary use of tile objects would be draw traversal, but we do
156 * not currently do redraws at all (we just start over).
158 #define VT_CORNER_MASK 0x3
159 #define VT_TYPE_MASK 0x4
163 #define VT_TOTAL_MASK 0x7
165 typedef unsigned char vertex_type_c;
168 * These allow one to compute the types of the other corners of the tile. If
169 * you are standing at a vertex of type vt looking towards the middle of the
170 * tile, VT_LEFT( vt) is the vertex on your left etc.
172 #define VT_LEFT( vt) ((((vt) - 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
173 #define VT_RIGHT( vt) ((((vt) + 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
174 #define VT_FAR( vt) ((vt) ^ 2)
178 * Since we do not do redraws, we only store the vertices we need. These are
179 * the ones with still some empty space around them for the growth algorithm
182 * Here we use a doubly chained ring-like structure as vertices often need
183 * to be removed or inserted (they are kept in geometrical order
184 * circling the tiled area counterclockwise). The ring is refered to by
185 * a pointer to one more or less random node. When deleting nodes one
186 * must make sure that this pointer continues to refer to a valid
187 * node. A vertex count is maintained to make it easier to pick
190 typedef struct forced_node forced_node_c;
192 typedef struct fringe_node {
193 struct fringe_node *prev;
194 struct fringe_node *next;
195 /* These are numbered counterclockwise. The gap, if any, lies
196 between the last and first tiles. */
197 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
199 /* A bit mask used to indicate vertex rules that are still applicable for
200 completing this vertex. Initialize this to (1 << N_VERTEX_RULES) - 1,
201 i.e., all ones, and the rule matching functions will automatically mask
202 out rules that no longer match. */
203 unsigned char rule_mask;
204 /* If the vertex is on the forced vertex list, this points to the
205 pointer to the appropriate node in the list. To remove the
206 vertex from the list just set *list_ptr to the next node,
207 deallocate and decrement node count. */
208 struct forced_node **list_ptr;
209 /* Screen coordinates. */
211 /* We also keep track of 5D coordinates to avoid rounding errors.
212 These are in units of edge length. */
214 /* This is used to quickly check if a vertex is visible. */
215 unsigned char off_screen;
219 fringe_node_c *nodes;
220 /* This does not count off-screen nodes. */
226 * The forced vertex pool contains vertices where at least one
227 * side of the tiled region can only be extended in one way. Note
228 * that this does not necessarily mean that there would only be one
229 * applicable rule. forced_sides are specified using S_LEFT and
230 * S_RIGHT as if looking at the untiled region from the vertex.
233 fringe_node_c *vertex;
234 unsigned forced_sides;
235 struct forced_node *next;
239 forced_node_c *first;
240 int n_nodes, n_visible;
244 /* This is the data related to the tiling of one screen. */
250 forced_pool_c forced;
252 int thick_color, thin_color;
255 static tiling_c *tilings; /* = {0} */
258 /* The tiles are listed in counterclockwise order. */
260 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
264 static vertex_rule_c vertex_rules[N_VERTEX_RULES] =
267 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2}, 5},
269 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0}, 5},
271 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THIN | 0}, 4},
273 {VT_THICK | 2, VT_THICK | 2, VT_THIN | 1, VT_THIN | 3, VT_THICK | 2,
274 VT_THIN | 1, VT_THIN | 3}, 7},
276 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2,
277 VT_THIN | 1, VT_THIN | 3}, 6},
279 {VT_THICK | 1, VT_THICK | 3, VT_THIN | 2}, 3},
281 {VT_THICK | 0, VT_THIN | 0, VT_THIN | 0}, 3},
283 {VT_THICK | 2, VT_THIN | 1, VT_THICK | 3, VT_THICK | 1, VT_THIN | 3}, 5}
287 /* Match information returned by match_rules. */
294 /* Occasionally floating point coordinates are needed. */
300 /* All angles are measured in multiples of 36 degrees. */
303 static angle_c vtype_angles[] =
304 {4, 1, 4, 1, 2, 3, 2, 3};
306 #define vtype_angle( v) (vtype_angles[ v])
309 /* Direction angle of an edge. */
311 vertex_dir(ModeInfo * mi, fringe_node_c * vertex, unsigned side)
313 tiling_c *tp = &tilings[MI_SCREEN(mi)];
315 (side == S_LEFT ? vertex->next : vertex->prev);
318 for (i = 0; i < 5; i++)
319 switch (v2->fived[i] - vertex->fived[i]) {
323 return (2 * i + 5) % 10;
326 if (MI_WIN_IS_VERBOSE(mi)) {
327 (void) fprintf(stderr,
328 "Weirdness in vertex_dir (this has been reported)\n");
329 for (i = 0; i < 5; i++)
330 (void) fprintf(stderr, "v2->fived[%d]=%d, vertex->fived[%d]=%d\n",
331 i, v2->fived[i], i, vertex->fived[i]);
333 MI_PAUSE(mi) = redo_delay_usec;
338 /* Move one step to a given direction. */
340 add_unit_vec(angle_c dir, int *fived)
347 fived[dir2i[dir % 5]] += (dir % 2 ? -1 : 1);
351 /* For comparing coordinates. */
352 #define fived_equal( f1, f2) (!memcmp( (f1), (f2), 5 * sizeof( int)))
356 * This computes screen coordinates from 5D representation. Note that X
357 * uses left-handed coordinates (y increases downwards).
360 fived_to_loc(int fived[], tiling_c * tp)
362 static fcoord_c fived_table[5] =
365 float fifth = 8 * atan(1.) / 5;
368 register fcoord_c offset =
370 XPoint pt = tp->origin;
372 if (fived_table[0].x == .0)
373 for (i = 0; i < 5; i++) {
374 fived_table[i].x = cos(fifth * i);
375 fived_table[i].y = sin(fifth * i);
377 for (i = 0; i < 5; i++) {
378 r = fived[i] * tp->edge_length;
379 offset.x += r * fived_table[i].x;
380 offset.y -= r * fived_table[i].y;
382 pt.x += (int) (offset.x + .5);
383 pt.y += (int) (offset.y + .5);
388 /* Mop up dynamic data for one screen. */
390 release_screen(tiling_c * tp)
392 register fringe_node_c *fp1, *fp2;
393 register forced_node_c *lp1, *lp2;
395 if (tp->fringe.nodes == 0)
397 fp1 = tp->fringe.nodes;
401 (void) free((char *) fp2);
402 } while (fp1 != tp->fringe.nodes);
403 tp->fringe.nodes = 0;
404 for (lp1 = tp->forced.first; lp1 != 0;) {
407 (void) free((char *) lp2);
409 tp->forced.first = 0;
413 /* Called to init the mode. */
415 init_penrose(ModeInfo * mi)
421 redo_delay_usec = redo_delay * 1000000;
423 if (tilings == NULL) {
424 if ((tilings = (tiling_c *) calloc(MI_NUM_SCREENS(mi),
425 sizeof (tiling_c))) == NULL)
428 tp = &tilings[MI_SCREEN(mi)];
431 tp->width = MI_WIN_WIDTH(mi);
432 tp->height = MI_WIN_HEIGHT(mi);
433 if (MI_NPIXELS(mi) > 2) {
434 tp->thick_color = NRAND(MI_NPIXELS(mi));
435 /* Insure good contrast */
436 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
437 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
441 tp->edge_length = NRAND(MIN(-size, MAX(MINSIZE,
442 MIN(tp->width, tp->height) / 2)) - MINSIZE + 1) + MINSIZE;
443 else if (size < MINSIZE) {
445 tp->edge_length = MAX(MINSIZE, MIN(tp->width, tp->height) / 2);
447 tp->edge_length = MINSIZE;
449 tp->edge_length = MIN(size, MAX(MINSIZE,
450 MIN(tp->width, tp->height) / 2));
451 tp->origin.x = (tp->width / 2 + NRAND(tp->width)) / 2;
452 tp->origin.y = (tp->height / 2 + NRAND(tp->height)) / 2;
453 tp->fringe.n_nodes = 2;
454 if (tp->fringe.nodes != 0)
456 if (tp->fringe.nodes != 0 || tp->forced.first != 0) {
457 if (MI_WIN_IS_VERBOSE(mi)) {
458 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
459 (void) fprintf(stderr, "tp->fringe.nodes = 0 && tp->forced.first = 0\n");
461 release_screen(tp); /* Try again */
464 tp->forced.n_nodes = tp->forced.n_visible = 0;
465 fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c);
467 if (MI_WIN_IS_VERBOSE(mi)) {
468 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
469 (void) fprintf(stderr, "fp = 0\n");
471 fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c);
475 fp->rule_mask = (1 << N_VERTEX_RULES) - 1;
477 fp->prev = fp->next = ALLOC_NODE(fringe_node_c);
479 if (MI_WIN_IS_VERBOSE(mi)) {
480 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
481 (void) fprintf(stderr, "fp->next = 0\n");
483 fp->prev = fp->next = ALLOC_NODE(fringe_node_c);
487 fp->loc = tp->origin;
488 fp->off_screen = False;
489 for (i = 0; i < 5; i++)
494 fp->next->prev = fp->next->next = fp;
497 fp->fived[i] = 2 * NRAND(2) - 1;
498 fp->loc = fived_to_loc(fp->fived, tp);
499 /* That's it! We have created our first edge. */
503 * This attempts to match the configuration of vertex with the vertex
504 * rules. The return value is a total match count. If matches is
505 * non-null, it will be used to store information about the matches
506 * and must be large enough to contain it. To play it absolutely
507 * safe, allocate room for MAX_TILES_PER_VERTEX * N_VERTEX_RULES
508 * entries when searching all matches. The rule mask of vertex will
509 * be applied and rules masked out will not be searched. Only strict
510 * subsequences match. If first_only is true, the search stops when
511 * the first match is found. Otherwise all matches will be found and
512 * the rule_mask of vertex will be updated, which also happens in
513 * single-match mode if no match is found.
516 match_rules(fringe_node_c * vertex, rule_match_c * matches, int first_only)
518 /* I will assume that I can fit all the relevant bits in vertex->tiles
519 into one unsigned long. With 3 bits per element and at most 7
520 elements this means 21 bits, which should leave plenty of room.
521 After packing the bits the rest is just integer comparisons and
522 some bit shuffling. This is essentially Rabin-Karp without
523 congruence arithmetic. */
525 int hits = 0, good_rules[N_VERTEX_RULES], n_good = 0;
527 vertex_hash = 0, lower_bits_mask = ~(VT_TOTAL_MASK << VT_BITS * (vertex->n_tiles - 1));
528 unsigned new_rule_mask = 0;
530 for (i = 0; i < N_VERTEX_RULES; i++)
531 if (vertex->n_tiles >= vertex_rules[i].n_tiles)
532 vertex->rule_mask &= ~(1 << i);
533 else if (vertex->rule_mask & 1 << i)
534 good_rules[n_good++] = i;
535 for (i = 0; i < vertex->n_tiles; i++)
536 vertex_hash |= (unsigned long) vertex->tiles[i] << (VT_BITS * i);
538 for (j = 0; j < n_good; j++) {
539 unsigned long rule_hash = 0;
540 vertex_rule_c *vr = vertex_rules + good_rules[j];
542 for (i = 0; i < vertex->n_tiles; i++)
543 rule_hash |= (unsigned long) vr->tiles[i] << (VT_BITS * i);
544 if (rule_hash == vertex_hash) {
546 matches[hits].rule = good_rules[j];
547 matches[hits].pos = 0;
553 new_rule_mask |= 1 << good_rules[j];
555 for (i = vr->n_tiles - 1; i > 0; i--) {
556 rule_hash = vr->tiles[i] | (rule_hash & lower_bits_mask) << VT_BITS;
557 if (vertex_hash == rule_hash) {
559 matches[hits].rule = good_rules[j];
560 matches[hits].pos = i;
566 new_rule_mask |= 1 << good_rules[j];
570 vertex->rule_mask = new_rule_mask;
576 * find_completions finds the possible ways to add a tile to a vertex.
577 * The return values is the number of such possibilities. You must
578 * first call match_rules to produce matches and n_matches. sides
579 * specifies which side of the vertex to extend and can be S_LEFT or
580 * S_RIGHT. If results is non-null, it should point to an array large
581 * enough to contain the results, which will be stored there.
582 * MAX_COMPL elements will always suffice. If first_only is true we
583 * stop as soon as we find one possibility (NOT USED).
588 find_completions(fringe_node_c * vertex, rule_match_c * matches, int n_matches,
589 unsigned side, vertex_type_c * results /*, int first_only */ )
593 vertex_type_c buf[MAX_COMPL];
599 for (i = 0; i < n_matches; i++) {
600 vertex_rule_c *rule = vertex_rules + matches[i].rule;
601 int pos = (matches[i].pos
602 + (side == S_RIGHT ? vertex->n_tiles : rule->n_tiles - 1))
604 vertex_type_c vtype = rule->tiles[pos];
607 for (j = 0; j < n_res; j++)
608 if (vtype == results[j]) {
613 results[n_res++] = vtype;
620 * Draw a tile on the display. Vertices must be given in a
621 * counterclockwise order. vtype is the vertex type of v1 (and thus
622 * also gives the tile type).
625 draw_tile(fringe_node_c * v1, fringe_node_c * v2,
626 fringe_node_c * v3, fringe_node_c * v4,
627 vertex_type_c vtype, ModeInfo * mi)
629 Display *display = MI_DISPLAY(mi);
630 Window window = MI_WINDOW(mi);
632 tiling_c *tp = &tilings[MI_SCREEN(mi)];
634 vertex_type_c corner = vtype & VT_CORNER_MASK;
636 if (v1->off_screen && v2->off_screen && v3->off_screen && v4->off_screen)
638 pts[corner] = v1->loc;
639 pts[VT_RIGHT(corner)] = v2->loc;
640 pts[VT_FAR(corner)] = v3->loc;
641 pts[VT_LEFT(corner)] = v4->loc;
643 if (MI_NPIXELS(mi) > 2) {
644 if ((vtype & VT_TYPE_MASK) == VT_THICK)
645 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
647 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
649 XSetForeground(display, gc, MI_WIN_WHITE_PIXEL(mi));
650 XFillPolygon(display, window, gc, pts, 4, Convex, CoordModeOrigin);
651 XSetForeground(display, gc, MI_WIN_BLACK_PIXEL(mi));
652 XDrawLines(display, window, gc, pts, 5, CoordModeOrigin);
655 /* Draw some Ammann lines for debugging purposes. This will probably
656 fail miserably on a b&w display. */
658 if ((vtype & VT_TYPE_MASK) == VT_THICK) {
662 float pi10 = 2 * atan(1.) / 5;
664 r = 1 - sin(pi10) / (2 * sin(3 * pi10));
666 if (MI_NPIXELS(mi) > 2)
667 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
669 XSetForeground(display, gc, MI_WIN_WHITE_PIXEL(mi));
670 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
672 XDrawLine(display, window, gc,
673 (int) (r * pts[3].x + (1 - r) * pts[0].x + .5),
674 (int) (r * pts[3].y + (1 - r) * pts[0].y + .5),
675 (int) (r * pts[1].x + (1 - r) * pts[0].x + .5),
676 (int) (r * pts[1].y + (1 - r) * pts[0].y + .5));
677 if (MI_NPIXELS(mi) <= 2)
678 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
680 if (MI_NPIXELS(mi) > 2)
681 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
683 XSetForeground(display, gc, MI_WIN_WHITE_PIXEL(mi));
684 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
686 XDrawLine(display, window, gc,
687 (int) ((pts[3].x + pts[2].x) / 2 + .5),
688 (int) ((pts[3].y + pts[2].y) / 2 + .5),
689 (int) ((pts[1].x + pts[2].x) / 2 + .5),
690 (int) ((pts[1].y + pts[2].y) / 2 + .5));
691 if (MI_NPIXELS(mi) <= 2)
692 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
698 * Update the status of this vertex on the forced vertex queue. If
699 * the vertex has become untileable set tp->done. This is supposed
700 * to detect dislocations -- never call this routine with a completely
703 * Check for untileable vertices in check_vertex and stop tiling as
704 * soon as one finds one. I don't know if it is possible to run out
705 * of forced vertices while untileable vertices exist (or will
706 * cavities inevitably appear). If this can happen, add_random_tile
707 * might get called with an untileable vertex, causing ( n <= 1).
708 * (This is what the tp->done checks for).
710 * A MI_PAUSE celebrates the dislocation.
713 check_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
715 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
716 int n_hits = match_rules(vertex, hits, False);
717 unsigned forced_sides = 0;
719 if (vertex->rule_mask == 0) {
721 if (MI_WIN_IS_VERBOSE(mi)) {
722 (void) fprintf(stderr, "Dislocation occured!\n");
724 MI_PAUSE(mi) = redo_delay_usec; /* Should be able to recover */
726 if (1 == find_completions(vertex, hits, n_hits, S_LEFT, 0 /*, False */ ))
727 forced_sides |= S_LEFT;
728 if (1 == find_completions(vertex, hits, n_hits, S_RIGHT, 0 /*, False */ ))
729 forced_sides |= S_RIGHT;
730 if (forced_sides == 0) {
731 if (vertex->list_ptr != 0) {
732 forced_node_c *node = *vertex->list_ptr;
734 *vertex->list_ptr = node->next;
736 node->next->vertex->list_ptr = vertex->list_ptr;
738 tp->forced.n_nodes--;
739 if (!vertex->off_screen)
740 tp->forced.n_visible--;
741 vertex->list_ptr = 0;
746 if (vertex->list_ptr == 0) {
747 node = ALLOC_NODE(forced_node_c);
748 node->vertex = vertex;
749 node->next = tp->forced.first;
750 if (tp->forced.first != 0)
751 tp->forced.first->vertex->list_ptr = &(node->next);
752 tp->forced.first = node;
753 vertex->list_ptr = &(tp->forced.first);
754 tp->forced.n_nodes++;
755 if (!vertex->off_screen)
756 tp->forced.n_visible++;
758 node = *vertex->list_ptr;
759 node->forced_sides = forced_sides;
765 * Delete this vertex. If the vertex is a member of the forced vertex queue,
766 * also remove that entry. We assume that the vertex is no longer
767 * connected to the fringe. Note that tp->fringe.nodes must not point to
768 * the vertex being deleted.
771 delete_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
773 if (tp->fringe.nodes == vertex) {
775 if (MI_WIN_IS_VERBOSE(mi)) {
776 (void) fprintf(stderr, "Weirdness in delete_penrose()\n");
777 (void) fprintf(stderr, "tp->fringe.nodes == vertex\n");
779 MI_PAUSE(mi) = redo_delay_usec;
781 if (vertex->list_ptr != 0) {
782 forced_node_c *node = *vertex->list_ptr;
784 *vertex->list_ptr = node->next;
786 node->next->vertex->list_ptr = vertex->list_ptr;
788 tp->forced.n_nodes--;
789 if (!vertex->off_screen)
790 tp->forced.n_visible--;
792 if (!vertex->off_screen)
793 tp->fringe.n_nodes--;
798 /* Check whether the addition of a tile of type vtype would completely fill *
799 the space available at vertex. */
801 fills_vertex(ModeInfo * mi, vertex_type_c vtype, fringe_node_c * vertex)
804 (vertex_dir(mi, vertex, S_LEFT) - vertex_dir(mi, vertex, S_RIGHT)
805 - vtype_angle(vtype)) % 10 == 0;
810 * If you were to add a tile of type vtype to a specified side of
811 * vertex, fringe_changes tells you which other vertices it would
812 * attach to. The addresses of these vertices will be stored in the
813 * last three arguments. Null is stored if the corresponding vertex
814 * would need to be allocated.
816 * The function also analyzes which vertices would be swallowed by the tiling
817 * and thus cut off from the fringe. The result is returned as a bit pattern.
819 #define FC_BAG 1 /* Total enclosure. Should never occur. */
820 #define FC_NEW_RIGHT 2
822 #define FC_NEW_LEFT 8
823 #define FC_NEW_MASK 0xe
824 #define FC_CUT_THIS 0x10
825 #define FC_CUT_RIGHT 0x20
826 #define FC_CUT_FAR 0x40
827 #define FC_CUT_LEFT 0x80
828 #define FC_CUT_MASK 0xf0
829 #define FC_TOTAL_MASK 0xff
832 fringe_changes(ModeInfo * mi, fringe_node_c * vertex,
833 unsigned side, vertex_type_c vtype,
834 fringe_node_c ** right, fringe_node_c ** far,
835 fringe_node_c ** left)
837 fringe_node_c *v, *f = NULL;
838 unsigned result = FC_NEW_FAR; /* We clear this later if necessary. */
842 if (fills_vertex(mi, vtype, vertex)) {
843 result |= FC_CUT_THIS;
844 } else if (side == S_LEFT) {
845 result |= FC_NEW_RIGHT;
849 result |= FC_NEW_LEFT;
854 if (!(result & FC_NEW_LEFT)) {
858 if (fills_vertex(mi, VT_LEFT(vtype), v)) {
859 result = (result & ~FC_NEW_FAR) | FC_CUT_LEFT;
865 if (!(result & FC_NEW_RIGHT)) {
869 if (fills_vertex(mi, VT_RIGHT(vtype), v)) {
870 result = (result & ~FC_NEW_FAR) | FC_CUT_RIGHT;
876 if (!(result & FC_NEW_FAR)
877 && fills_vertex(mi, VT_FAR(vtype), f)) {
878 result |= FC_CUT_FAR;
879 result &= (~FC_NEW_LEFT & ~FC_NEW_RIGHT);
880 if (right && (result & FC_CUT_LEFT))
882 if (left && (result & FC_CUT_RIGHT))
885 if (((result & FC_CUT_LEFT) && (result & FC_CUT_RIGHT))
886 || ((result & FC_CUT_THIS) && (result & FC_CUT_FAR)))
892 /* A couple of lesser helper functions for add_tile. */
894 add_vtype(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
897 vertex->tiles[vertex->n_tiles++] = vtype;
901 for (i = vertex->n_tiles; i > 0; i--)
902 vertex->tiles[i] = vertex->tiles[i - 1];
903 vertex->tiles[0] = vtype;
908 static fringe_node_c *
909 alloc_vertex(ModeInfo * mi, angle_c dir, fringe_node_c * from, tiling_c * tp)
911 fringe_node_c *v = ALLOC_NODE(fringe_node_c);
915 if (MI_WIN_IS_VERBOSE(mi)) {
916 (void) fprintf(stderr, "Weirdness in alloc_vertex()\n");
917 (void) fprintf(stderr, "v = 0\n");
919 MI_PAUSE(mi) = redo_delay_usec;
922 add_unit_vec(dir, v->fived);
923 v->loc = fived_to_loc(v->fived, tp);
924 if (v->loc.x < 0 || v->loc.y < 0
925 || v->loc.x >= tp->width || v->loc.y >= tp->height) {
926 v->off_screen = True;
927 if (v->loc.x < -tp->width || v->loc.y < -tp->height
928 || v->loc.x >= 2 * tp->width || v->loc.y >= 2 * tp->height)
931 v->off_screen = False;
932 tp->fringe.n_nodes++;
935 v->rule_mask = (1 << N_VERTEX_RULES) - 1;
941 * Add a tile described by vtype to the side of vertex. This must be
942 * allowed by the rules -- we do not check it here. New vertices are
943 * allocated as necessary. The fringe and the forced vertex pool are updated.
944 * The new tile is drawn on the display.
946 * One thing we do check here is whether the new tile causes an untiled
947 * area to become enclosed by the tiling. If this would happen, the tile
948 * is not added. The return value is true iff a tile was added.
951 add_tile(ModeInfo * mi,
952 fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
954 tiling_c *tp = &tilings[MI_SCREEN(mi)];
961 unsigned fc = fringe_changes(mi, vertex, side, vtype, &right, &far, &left);
964 ltype = VT_LEFT(vtype),
965 rtype = VT_RIGHT(vtype),
966 ftype = VT_FAR(vtype);
968 /* By our conventions vertex->next lies to the left of vertex and
969 vertex->prev to the right. */
971 /* This should never occur. */
974 if (MI_WIN_IS_VERBOSE(mi)) {
975 (void) fprintf(stderr, "Weirdness in add_tile()\n");
976 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
979 if (side == S_LEFT) {
981 right = alloc_vertex(mi,
982 vertex_dir(mi, vertex, S_LEFT) - vtype_angle(vtype), vertex, tp);
984 far = alloc_vertex(mi,
985 vertex_dir(mi, left, S_RIGHT) + vtype_angle(ltype), left, tp);
988 left = alloc_vertex(mi,
989 vertex_dir(mi, vertex, S_RIGHT) + vtype_angle(vtype), vertex, tp);
991 far = alloc_vertex(mi,
992 vertex_dir(mi, right, S_LEFT) - vtype_angle(rtype), right, tp);
995 /* Having allocated the new vertices, but before joining them with
996 the rest of the fringe, check if vertices with same coordinates
997 already exist. If any such are found, give up. */
998 node = tp->fringe.nodes;
1000 if (((fc & FC_NEW_LEFT) && fived_equal(node->fived, left->fived))
1001 || ((fc & FC_NEW_RIGHT) && fived_equal(node->fived, right->fived))
1002 || ((fc & FC_NEW_FAR) && fived_equal(node->fived, far->fived))) {
1003 /* Better luck next time. */
1004 if (fc & FC_NEW_LEFT)
1005 delete_vertex(mi, left, tp);
1006 if (fc & FC_NEW_RIGHT)
1007 delete_vertex(mi, right, tp);
1008 if (fc & FC_NEW_FAR)
1009 delete_vertex(mi, far, tp);
1013 } while (node != tp->fringe.nodes);
1016 if (!(fc & FC_CUT_THIS)) {
1017 if (side == S_LEFT) {
1018 vertex->next = right;
1019 right->prev = vertex;
1021 vertex->prev = left;
1022 left->next = vertex;
1025 if (!(fc & FC_CUT_FAR)) {
1026 if (!(fc & FC_CUT_LEFT)) {
1030 if (!(fc & FC_CUT_RIGHT)) {
1035 draw_tile(vertex, right, far, left, vtype, mi);
1037 /* Delete vertices that are no longer on the fringe. Check the others. */
1038 if (fc & FC_CUT_THIS) {
1039 tp->fringe.nodes = far;
1040 delete_vertex(mi, vertex, tp);
1042 add_vtype(vertex, side, vtype);
1043 check_vertex(mi, vertex, tp);
1044 tp->fringe.nodes = vertex;
1046 if (fc & FC_CUT_FAR)
1047 delete_vertex(mi, far, tp);
1049 add_vtype(far, fc & FC_CUT_RIGHT ? S_LEFT : S_RIGHT, ftype);
1050 check_vertex(mi, far, tp);
1052 if (fc & FC_CUT_LEFT)
1053 delete_vertex(mi, left, tp);
1055 add_vtype(left, fc & FC_CUT_FAR ? S_LEFT : S_RIGHT, ltype);
1056 check_vertex(mi, left, tp);
1058 if (fc & FC_CUT_RIGHT)
1059 delete_vertex(mi, right, tp);
1061 add_vtype(right, fc & FC_CUT_FAR ? S_RIGHT : S_LEFT, rtype);
1062 check_vertex(mi, right, tp);
1069 * Add a forced tile to a given forced vertex. Basically an easy job,
1070 * since we know what to add. But it might fail if adding the tile
1071 * would cause some untiled area to become enclosed. There is also another
1072 * more exotic culprit: we might have a dislocation. Fortunately, they
1073 * are very rare (the PRL article reported that perfect tilings of over
1074 * 2^50 tiles had been generated). There is a version of the algorithm
1075 * that doesn't produce dislocations, but it's a lot hairier than the
1076 * simpler version I used.
1079 add_forced_tile(ModeInfo * mi, forced_node_c * node)
1081 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1083 vertex_type_c vtype;
1084 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1087 if (node->forced_sides == (S_LEFT | S_RIGHT))
1088 side = NRAND(2) ? S_LEFT : S_RIGHT;
1090 side = node->forced_sides;
1091 n = match_rules(node->vertex, hits, True);
1092 n = find_completions(node->vertex, hits, n, side, &vtype /*, True */ );
1095 if (MI_WIN_IS_VERBOSE(mi)) {
1096 (void) fprintf(stderr, "Weirdness in add_forced_tile()\n");
1097 (void) fprintf(stderr, "n = %d\n", n);
1100 return add_tile(mi, node->vertex, side, vtype);
1105 * Whether the addition of a tile of vtype on the given side of vertex
1106 * would conform to the rules. The efficient way to do this would be
1107 * to add the new tile and then use the same type of search as in
1108 * match_rules. However, this function is not a performance
1109 * bottleneck (only needed for random tile additions, which are
1110 * relatively infrequent), so I will settle for a simpler implementation.
1113 legal_move(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
1115 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1116 vertex_type_c legal_vt[MAX_COMPL];
1117 int n_hits, n_legal, i;
1119 n_hits = match_rules(vertex, hits, False);
1120 n_legal = find_completions(vertex, hits, n_hits, side, legal_vt /*, False */ );
1121 for (i = 0; i < n_legal; i++)
1122 if (legal_vt[i] == vtype)
1129 * Add a randomly chosen tile to a given vertex. This requires more checking
1130 * as we must make sure the new tile conforms to the vertex rules at every
1131 * vertex it touches. */
1133 add_random_tile(fringe_node_c * vertex, ModeInfo * mi)
1135 fringe_node_c *right, *left, *far;
1136 int i, j, n, n_hits, n_good;
1137 unsigned side, fc, no_good, s;
1138 vertex_type_c vtypes[MAX_COMPL];
1139 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1140 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1142 if (MI_NPIXELS(mi) > 2) {
1143 tp->thick_color = NRAND(MI_NPIXELS(mi));
1144 /* Insure good contrast */
1145 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
1146 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
1148 tp->thick_color = tp->thin_color = MI_WIN_WHITE_PIXEL(mi);
1149 n_hits = match_rules(vertex, hits, False);
1150 side = NRAND(2) ? S_LEFT : S_RIGHT;
1151 n = find_completions(vertex, hits, n_hits, side, vtypes /*, False */ );
1152 /* One answer would mean a forced tile. */
1155 if (MI_WIN_IS_VERBOSE(mi)) {
1156 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1157 (void) fprintf(stderr, "n = %d\n", n);
1162 for (i = 0; i < n; i++) {
1163 fc = fringe_changes(mi, vertex, side, vtypes[i], &right, &far, &left);
1166 if (MI_WIN_IS_VERBOSE(mi)) {
1167 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1168 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1172 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_LEFT)) ? S_RIGHT : S_LEFT);
1173 if (!legal_move(right, s, VT_RIGHT(vtypes[i]))) {
1174 no_good |= (1 << i);
1180 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_RIGHT)) ? S_LEFT : S_RIGHT);
1181 if (!legal_move(left, s, VT_LEFT(vtypes[i]))) {
1182 no_good |= (1 << i);
1188 s = ((fc & FC_CUT_LEFT) ? S_RIGHT : S_LEFT);
1189 if (!legal_move(far, s, VT_FAR(vtypes[i]))) {
1190 no_good |= (1 << i);
1197 if (MI_WIN_IS_VERBOSE(mi)) {
1198 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1199 (void) fprintf(stderr, "n_good = %d\n", n_good);
1203 for (i = j = 0; i <= n; i++, j++)
1204 while (no_good & (1 << j))
1207 i = add_tile(mi, vertex, side, vtypes[j - 1]);
1210 if (MI_WIN_IS_VERBOSE(mi)) {
1211 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1212 (void) fprintf(stderr, "i = %d\n", i);
1217 /* One step of the growth algorithm. */
1219 draw_penrose(ModeInfo * mi)
1221 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1223 forced_node_c *p = tp->forced.first;
1225 if (tp->done || tp->failures >= 100) {
1229 /* Check for the initial "2-gon". */
1230 if (tp->fringe.nodes->prev == tp->fringe.nodes->next) {
1231 vertex_type_c vtype = VT_TOTAL_MASK & LRAND();
1233 XClearWindow(MI_DISPLAY(mi), MI_WINDOW(mi));
1234 (void) add_tile(mi, tp->fringe.nodes, S_LEFT, vtype);
1237 /* No visible nodes left. */
1238 if (tp->fringe.n_nodes == 0) {
1240 MI_PAUSE(mi) = redo_delay_usec; /* Just finished drawing */
1243 if (tp->forced.n_visible > 0 && tp->failures < 10) {
1244 n = NRAND(tp->forced.n_visible);
1246 while (p->vertex->off_screen)
1253 } else if (tp->forced.n_nodes > 0) {
1254 n = NRAND(tp->forced.n_nodes);
1258 fringe_node_c *p = tp->fringe.nodes;
1260 n = NRAND(tp->fringe.n_nodes);
1265 } while (p->off_screen);
1266 add_random_tile(p, mi);
1270 if (add_forced_tile(mi, p))
1277 /* Total clean-up. */
1279 release_penrose(ModeInfo * mi)
1281 if (tilings != NULL) {
1284 for (screen = 0; screen < MI_NUM_SCREENS(mi); screen++) {
1285 tiling_c *tp = &tilings[screen];
1289 (void) free((void *) tilings);