1 /* -*- Mode: C; tab-width: 4 -*- */
2 /* penrose --- quasiperiodic tilings */
4 /* As reported in News of the Weird:
6 In April, Sir Roger Penrose, a British math professor who has worked
7 with Stephen Hawking on such topics as relativity, black holes, and
8 whether time has a beginning, filed a copyright-infringement lawsuit
9 against the Kimberly-Clark Corporation, which Penrose said copied a
10 pattern he created (a pattern demonstrating that "a nonrepeating
11 pattern could exist in nature") for its Kleenex quilted toilet paper.
12 Penrose said he doesn't like litigation but, "When it comes to the
13 population of Great Britain being invited by a multinational to wipe
14 their bottoms on what appears to be the work of a Knight of the
15 Realm, then a last stand must be taken."
17 NOTW #491, 4-jul-1997, by Chuck Shepherd.
18 http://www.nine.org/notw/notw.html
21 #if !defined( lint ) && !defined( SABER )
22 static const char sccsid[] = "@(#)penrose.c 5.00 2000/11/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 * 01-Nov-2000: Allocation checks
43 * 10-May-1997: Jamie Zawinski <jwz@jwz.org> compatible with xscreensaver
44 * 09-Sep-1996: Written.
48 Be careful, this probably still has a few bugs (many of which may only
49 appear with a very low probability). These are seen with -verbose .
50 If one of these are hit penrose will reinitialize.
54 * See Onoda, Steinhardt, DiVincenzo and Socolar in
55 * Phys. Rev. Lett. 60, #25, 1988 or
56 * Strandburg in Computers in Physics, Sep/Oct 1991.
58 * This implementation uses the simpler version of the growth
59 * algorithm, i.e., if there are no forced vertices, a randomly chosen
60 * tile is added to a randomly chosen vertex (no preference for those
63 * There are two essential differences to the algorithm presented in
64 * the literature: First, we do not allow the tiling to enclose an
65 * untiled area. Whenever this is in danger of happening, we just
66 * do not add the tile, hoping for a better random choice the next
67 * time. Second, when choosing a vertex randomly, we will take
68 * one that lies within the viewport if available. If this seems to
69 * cause enclosures in the forced rule case, we will allow invisible
70 * vertices to be chosen.
72 * Tiling is restarted whenever one of the following happens: there
73 * are no incomplete vertices within the viewport or the tiling has
74 * extended a window's length beyond the edge of the window
75 * horizontally or vertically or forced rule choice has failed 100
76 * times due to areas about to become enclosed.
79 * Science News March 23 1985 Vol 127, No. 12
80 * Science News July 16 1988 Vol 134, No. 3
81 * The Economist Sept 17 1988 pg. 100
87 #define PROGCLASS "Penrose"
88 #define HACK_INIT init_penrose
89 #define HACK_DRAW draw_penrose
90 #define penrose_opts xlockmore_opts
91 #define DEFAULTS "*delay: 10000 \n" \
94 #include "xlockmore.h" /* from the xscreensaver distribution */
95 #else /* !STANDALONE */
96 #include "xlock.h" /* from the xlockmore distribution */
97 #endif /* !STANDALONE */
101 #define DEF_AMMANN "False"
105 static XrmOptionDescRec opts[] =
107 {(char *) "-ammann", (char *) ".penrose.ammann", XrmoptionNoArg, (caddr_t) "on"},
108 {(char *) "+ammann", (char *) ".penrose.ammann", XrmoptionNoArg, (caddr_t) "off"}
110 static argtype vars[] =
112 {(caddr_t *) & ammann, (char *) "ammann", (char *) "Ammann", (char *) DEF_AMMANN, t_Bool}
114 static OptionStruct desc[] =
116 {(char *) "-/+ammann", (char *) "turn on/off Ammann lines"}
119 ModeSpecOpt penrose_opts =
120 {sizeof opts / sizeof opts[0], opts, sizeof vars / sizeof vars[0], vars, desc};
123 ModStruct penrose_description =
124 {"penrose", "init_penrose", "draw_penrose", "release_penrose",
125 "init_penrose", "init_penrose", (char *) NULL, &penrose_opts,
126 10000, 1, 1, -40, 64, 1.0, "",
127 "Shows Penrose's quasiperiodic tilings", 0, NULL};
132 * Annoyingly the ANSI C library people have reserved all identifiers
133 * ending with _t for future use. Hence we use _c as a suffix for
134 * typedefs (c for class, although this is not C++).
140 * In theory one could fit 10 tiles to a single vertex. However, the
141 * vertex rules only allow at most seven tiles to meet at a vertex.
144 #define CELEBRATE 31415 /* This causes a pause, an error occurred. */
145 #define COMPLETION 3141 /* This causes a pause, tiles filled up screen. */
147 #define MAX_TILES_PER_VERTEX 7
148 #define N_VERTEX_RULES 8
149 #define ALLOC_NODE(type) (type *)malloc(sizeof (type))
152 * These are used to specify directions. They can also be used in bit
153 * masks to specify a combination of directions.
160 * We do not actually maintain objects corresponding to the tiles since
161 * we do not really need them and they would only consume memory and
162 * cause additional bookkeeping. Instead we only have vertices, and
163 * each vertex lists the type of each adjacent tile as well as the
164 * position of the vertex on the tile (hereafter refered to as
165 * "corner"). These positions are numbered in counterclockwise order
166 * so that 0 is where two double arrows meet (see one of the
167 * articles). The tile type and vertex number are stored in a single
168 * integer (we use char, and even most of it remains unused).
170 * The primary use of tile objects would be draw traversal, but we do
171 * not currently do redraws at all (we just start over).
173 #define VT_CORNER_MASK 0x3
174 #define VT_TYPE_MASK 0x4
178 #define VT_TOTAL_MASK 0x7
180 typedef unsigned char vertex_type_c;
183 * These allow one to compute the types of the other corners of the tile. If
184 * you are standing at a vertex of type vt looking towards the middle of the
185 * tile, VT_LEFT( vt) is the vertex on your left etc.
187 #define VT_LEFT( vt) ((((vt) - 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
188 #define VT_RIGHT( vt) ((((vt) + 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
189 #define VT_FAR( vt) ((vt) ^ 2)
193 * Since we do not do redraws, we only store the vertices we need. These are
194 * the ones with still some empty space around them for the growth algorithm
197 * Here we use a doubly chained ring-like structure as vertices often need
198 * to be removed or inserted (they are kept in geometrical order
199 * circling the tiled area counterclockwise). The ring is refered to by
200 * a pointer to one more or less random node. When deleting nodes one
201 * must make sure that this pointer continues to refer to a valid
202 * node. A vertex count is maintained to make it easier to pick
205 typedef struct forced_node forced_node_c;
207 typedef struct fringe_node {
208 struct fringe_node *prev;
209 struct fringe_node *next;
210 /* These are numbered counterclockwise. The gap, if any, lies
211 between the last and first tiles. */
212 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
214 /* A bit mask used to indicate vertex rules that are still applicable for
215 completing this vertex. Initialize this to (1 << N_VERTEX_RULES) - 1,
216 i.e., all ones, and the rule matching functions will automatically mask
217 out rules that no longer match. */
218 unsigned char rule_mask;
219 /* If the vertex is on the forced vertex list, this points to the
220 pointer to the appropriate node in the list. To remove the
221 vertex from the list just set *list_ptr to the next node,
222 deallocate and decrement node count. */
223 struct forced_node **list_ptr;
224 /* Screen coordinates. */
226 /* We also keep track of 5D coordinates to avoid rounding errors.
227 These are in units of edge length. */
229 /* This is used to quickly check if a vertex is visible. */
230 unsigned char off_screen;
234 fringe_node_c *nodes;
235 /* This does not count off-screen nodes. */
241 * The forced vertex pool contains vertices where at least one
242 * side of the tiled region can only be extended in one way. Note
243 * that this does not necessarily mean that there would only be one
244 * applicable rule. forced_sides are specified using S_LEFT and
245 * S_RIGHT as if looking at the untiled region from the vertex.
248 fringe_node_c *vertex;
249 unsigned forced_sides;
250 struct forced_node *next;
254 forced_node_c *first;
255 int n_nodes, n_visible;
259 /* This is the data related to the tiling of one screen. */
265 forced_pool_c forced;
267 unsigned long thick_color, thin_color;
272 static tiling_c *tilings = (tiling_c *) NULL;
274 /* The tiles are listed in counterclockwise order. */
276 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
280 static vertex_rule_c vertex_rules[N_VERTEX_RULES] =
283 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2}, 5},
285 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0}, 5},
287 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THIN | 0}, 4},
289 {VT_THICK | 2, VT_THICK | 2, VT_THIN | 1, VT_THIN | 3, VT_THICK | 2,
290 VT_THIN | 1, VT_THIN | 3}, 7},
292 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2,
293 VT_THIN | 1, VT_THIN | 3}, 6},
295 {VT_THICK | 1, VT_THICK | 3, VT_THIN | 2}, 3},
297 {VT_THICK | 0, VT_THIN | 0, VT_THIN | 0}, 3},
299 {VT_THICK | 2, VT_THIN | 1, VT_THICK | 3, VT_THICK | 1, VT_THIN | 3}, 5}
303 /* Match information returned by match_rules. */
310 /* Occasionally floating point coordinates are needed. */
316 /* All angles are measured in multiples of 36 degrees. */
319 static angle_c vtype_angles[] =
320 {4, 1, 4, 1, 2, 3, 2, 3};
322 #define vtype_angle( v) (vtype_angles[ v])
325 /* Direction angle of an edge. */
327 vertex_dir(ModeInfo * mi, fringe_node_c * vertex, unsigned side)
329 tiling_c *tp = &tilings[MI_SCREEN(mi)];
331 (side == S_LEFT ? vertex->next : vertex->prev);
334 for (i = 0; i < 5; i++)
335 switch (v2->fived[i] - vertex->fived[i]) {
339 return (2 * i + 5) % 10;
342 if (MI_IS_VERBOSE(mi)) {
343 (void) fprintf(stderr,
344 "Weirdness in vertex_dir (this has been reported)\n");
345 for (i = 0; i < 5; i++)
346 (void) fprintf(stderr, "v2->fived[%d]=%d, vertex->fived[%d]=%d\n",
347 i, v2->fived[i], i, vertex->fived[i]);
349 tp->busyLoop = CELEBRATE;
354 /* Move one step to a given direction. */
356 add_unit_vec(angle_c dir, int *fived)
363 fived[dir2i[dir % 5]] += (dir % 2 ? -1 : 1);
367 /* For comparing coordinates. */
368 #define fived_equal( f1, f2) (!memcmp( (f1), (f2), 5 * sizeof( int)))
372 * This computes screen coordinates from 5D representation. Note that X
373 * uses left-handed coordinates (y increases downwards).
376 fived_to_loc(int fived[], tiling_c * tp, XPoint *pt)
378 static fcoord_c fived_table[5] =
381 float fifth = 8 * atan(1.) / 5;
384 register fcoord_c offset;
389 if (fived_table[0].x == .0)
390 for (i = 0; i < 5; i++) {
391 fived_table[i].x = cos(fifth * i);
392 fived_table[i].y = sin(fifth * i);
394 for (i = 0; i < 5; i++) {
395 r = fived[i] * tp->edge_length;
396 offset.x += r * fived_table[i].x;
397 offset.y -= r * fived_table[i].y;
399 (*pt).x += (int) (offset.x + .5);
400 (*pt).y += (int) (offset.y + .5);
404 /* Mop up dynamic data for one screen. */
406 free_penrose(tiling_c * tp)
408 register fringe_node_c *fp1, *fp2;
409 register forced_node_c *lp1, *lp2;
411 if (tp->fringe.nodes == NULL)
413 fp1 = tp->fringe.nodes;
417 (void) free((void *) fp2);
418 } while (fp1 != tp->fringe.nodes);
419 tp->fringe.nodes = (fringe_node_c *) NULL;
420 for (lp1 = tp->forced.first; lp1 != 0;) {
423 (void) free((void *) lp2);
425 tp->forced.first = 0;
429 /* Called to init the mode. */
431 init_penrose(ModeInfo * mi)
437 if (tilings == NULL) {
438 if ((tilings = (tiling_c *) calloc(MI_NUM_SCREENS(mi),
439 sizeof (tiling_c))) == NULL)
442 tp = &tilings[MI_SCREEN(mi)];
444 #if 0 /* if you do this, then the -ammann and -no-ammann options don't work.
446 if (MI_IS_FULLRANDOM(mi))
447 tp->ammann = (Bool) (LRAND() & 1);
455 tp->width = MI_WIDTH(mi);
456 tp->height = MI_HEIGHT(mi);
457 if (MI_NPIXELS(mi) > 2) {
458 tp->thick_color = NRAND(MI_NPIXELS(mi));
459 /* Insure good contrast */
460 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
461 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
465 tp->edge_length = NRAND(MIN(-size, MAX(MINSIZE,
466 MIN(tp->width, tp->height) / 2)) - MINSIZE + 1) + MINSIZE;
467 else if (size < MINSIZE) {
469 tp->edge_length = MAX(MINSIZE, MIN(tp->width, tp->height) / 2);
471 tp->edge_length = MINSIZE;
473 tp->edge_length = MIN(size, MAX(MINSIZE,
474 MIN(tp->width, tp->height) / 2));
475 tp->origin.x = (tp->width / 2 + NRAND(tp->width)) / 2;
476 tp->origin.y = (tp->height / 2 + NRAND(tp->height)) / 2;
477 tp->fringe.n_nodes = 2;
478 if (tp->fringe.nodes != NULL)
480 if (tp->fringe.nodes != NULL || tp->forced.first != 0) {
481 if (MI_IS_VERBOSE(mi)) {
482 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
483 (void) fprintf(stderr, "tp->fringe.nodes = NULL && tp->forced.first = 0\n");
485 free_penrose(tp); /* Try again */
488 tp->forced.n_nodes = tp->forced.n_visible = 0;
489 if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
494 if (MI_IS_VERBOSE(mi)) {
495 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
496 (void) fprintf(stderr, "fp = 0\n");
498 if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
505 fp->rule_mask = (1 << N_VERTEX_RULES) - 1;
507 if ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
512 if (MI_IS_VERBOSE(mi)) {
513 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
514 (void) fprintf(stderr, "fp->next = 0\n");
516 if ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
523 fp->loc = tp->origin;
524 fp->off_screen = False;
525 for (i = 0; i < 5; i++)
530 fp->next->prev = fp->next->next = fp;
533 fp->fived[i] = 2 * NRAND(2) - 1;
534 fived_to_loc(fp->fived, tp, &(fp->loc));
535 /* That's it! We have created our first edge. */
539 * This attempts to match the configuration of vertex with the vertex
540 * rules. The return value is a total match count. If matches is
541 * non-null, it will be used to store information about the matches
542 * and must be large enough to contain it. To play it absolutely
543 * safe, allocate room for MAX_TILES_PER_VERTEX * N_VERTEX_RULES
544 * entries when searching all matches. The rule mask of vertex will
545 * be applied and rules masked out will not be searched. Only strict
546 * subsequences match. If first_only is true, the search stops when
547 * the first match is found. Otherwise all matches will be found and
548 * the rule_mask of vertex will be updated, which also happens in
549 * single-match mode if no match is found.
552 match_rules(fringe_node_c * vertex, rule_match_c * matches, int first_only)
554 /* I will assume that I can fit all the relevant bits in vertex->tiles
555 into one unsigned long. With 3 bits per element and at most 7
556 elements this means 21 bits, which should leave plenty of room.
557 After packing the bits the rest is just integer comparisons and
558 some bit shuffling. This is essentially Rabin-Karp without
559 congruence arithmetic. */
561 int hits = 0, good_rules[N_VERTEX_RULES], n_good = 0;
563 vertex_hash = 0, lower_bits_mask = ~(VT_TOTAL_MASK << VT_BITS * (vertex->n_tiles - 1));
564 unsigned new_rule_mask = 0;
566 for (i = 0; i < N_VERTEX_RULES; i++)
567 if (vertex->n_tiles >= vertex_rules[i].n_tiles)
568 vertex->rule_mask &= ~(1 << i);
569 else if (vertex->rule_mask & 1 << i)
570 good_rules[n_good++] = i;
571 for (i = 0; i < vertex->n_tiles; i++)
572 vertex_hash |= (unsigned long) vertex->tiles[i] << (VT_BITS * i);
574 for (j = 0; j < n_good; j++) {
575 unsigned long rule_hash = 0;
576 vertex_rule_c *vr = vertex_rules + good_rules[j];
578 for (i = 0; i < vertex->n_tiles; i++)
579 rule_hash |= (unsigned long) vr->tiles[i] << (VT_BITS * i);
580 if (rule_hash == vertex_hash) {
582 matches[hits].rule = good_rules[j];
583 matches[hits].pos = 0;
589 new_rule_mask |= 1 << good_rules[j];
591 for (i = vr->n_tiles - 1; i > 0; i--) {
592 rule_hash = vr->tiles[i] | (rule_hash & lower_bits_mask) << VT_BITS;
593 if (vertex_hash == rule_hash) {
595 matches[hits].rule = good_rules[j];
596 matches[hits].pos = i;
602 new_rule_mask |= 1 << good_rules[j];
606 vertex->rule_mask = new_rule_mask;
612 * find_completions finds the possible ways to add a tile to a vertex.
613 * The return values is the number of such possibilities. You must
614 * first call match_rules to produce matches and n_matches. sides
615 * specifies which side of the vertex to extend and can be S_LEFT or
616 * S_RIGHT. If results is non-null, it should point to an array large
617 * enough to contain the results, which will be stored there.
618 * MAX_COMPL elements will always suffice. If first_only is true we
619 * stop as soon as we find one possibility (NOT USED).
624 find_completions(fringe_node_c * vertex, rule_match_c * matches, int n_matches,
625 unsigned side, vertex_type_c * results /*, int first_only */ )
629 vertex_type_c buf[MAX_COMPL];
635 for (i = 0; i < n_matches; i++) {
636 vertex_rule_c *rule = vertex_rules + matches[i].rule;
637 int pos = (matches[i].pos
638 + (side == S_RIGHT ? vertex->n_tiles : rule->n_tiles - 1))
640 vertex_type_c vtype = rule->tiles[pos];
643 for (j = 0; j < n_res; j++)
644 if (vtype == results[j]) {
649 results[n_res++] = vtype;
656 * Draw a tile on the display. Vertices must be given in a
657 * counterclockwise order. vtype is the vertex type of v1 (and thus
658 * also gives the tile type).
661 draw_tile(fringe_node_c * v1, fringe_node_c * v2,
662 fringe_node_c * v3, fringe_node_c * v4,
663 vertex_type_c vtype, ModeInfo * mi)
665 Display *display = MI_DISPLAY(mi);
666 Window window = MI_WINDOW(mi);
668 tiling_c *tp = &tilings[MI_SCREEN(mi)];
670 vertex_type_c corner = vtype & VT_CORNER_MASK;
672 if (v1->off_screen && v2->off_screen && v3->off_screen && v4->off_screen)
674 pts[corner] = v1->loc;
675 pts[VT_RIGHT(corner)] = v2->loc;
676 pts[VT_FAR(corner)] = v3->loc;
677 pts[VT_LEFT(corner)] = v4->loc;
679 if (MI_NPIXELS(mi) > 2) {
680 if ((vtype & VT_TYPE_MASK) == VT_THICK)
681 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
683 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
685 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
686 XFillPolygon(display, window, gc, pts, 4, Convex, CoordModeOrigin);
687 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
688 XDrawLines(display, window, gc, pts, 5, CoordModeOrigin);
691 /* Draw some Ammann lines for debugging purposes. This will probably
692 fail miserably on a b&w display. */
694 if ((vtype & VT_TYPE_MASK) == VT_THICK) {
698 float pi10 = 2 * atan(1.) / 5;
700 r = 1 - sin(pi10) / (2 * sin(3 * pi10));
702 if (MI_NPIXELS(mi) > 2)
703 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
705 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
706 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
708 XDrawLine(display, window, gc,
709 (int) (r * pts[3].x + (1 - r) * pts[0].x + .5),
710 (int) (r * pts[3].y + (1 - r) * pts[0].y + .5),
711 (int) (r * pts[1].x + (1 - r) * pts[0].x + .5),
712 (int) (r * pts[1].y + (1 - r) * pts[0].y + .5));
713 if (MI_NPIXELS(mi) <= 2)
714 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
716 if (MI_NPIXELS(mi) > 2)
717 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
719 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
720 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
722 XDrawLine(display, window, gc,
723 (int) ((pts[3].x + pts[2].x) / 2 + .5),
724 (int) ((pts[3].y + pts[2].y) / 2 + .5),
725 (int) ((pts[1].x + pts[2].x) / 2 + .5),
726 (int) ((pts[1].y + pts[2].y) / 2 + .5));
727 if (MI_NPIXELS(mi) <= 2)
728 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
734 * Update the status of this vertex on the forced vertex queue. If
735 * the vertex has become untileable set tp->done. This is supposed
736 * to detect dislocations -- never call this routine with a completely
739 * Check for untileable vertices in check_vertex and stop tiling as
740 * soon as one finds one. I don't know if it is possible to run out
741 * of forced vertices while untileable vertices exist (or will
742 * cavities inevitably appear). If this can happen, add_random_tile
743 * might get called with an untileable vertex, causing ( n <= 1).
744 * (This is what the tp->done checks for).
746 * A delayLoop celebrates the dislocation.
749 check_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
751 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
752 int n_hits = match_rules(vertex, hits, False);
753 unsigned forced_sides = 0;
755 if (vertex->rule_mask == 0) {
757 if (MI_IS_VERBOSE(mi)) {
758 (void) fprintf(stderr, "Dislocation occurred!\n");
760 tp->busyLoop = CELEBRATE; /* Should be able to recover */
762 if (1 == find_completions(vertex, hits, n_hits, S_LEFT, 0 /*, False */ ))
763 forced_sides |= S_LEFT;
764 if (1 == find_completions(vertex, hits, n_hits, S_RIGHT, 0 /*, False */ ))
765 forced_sides |= S_RIGHT;
766 if (forced_sides == 0) {
767 if (vertex->list_ptr != 0) {
768 forced_node_c *node = *vertex->list_ptr;
770 *vertex->list_ptr = node->next;
772 node->next->vertex->list_ptr = vertex->list_ptr;
773 (void) free((void *) node);
774 tp->forced.n_nodes--;
775 if (!vertex->off_screen)
776 tp->forced.n_visible--;
777 vertex->list_ptr = 0;
782 if (vertex->list_ptr == 0) {
783 if ((node = ALLOC_NODE(forced_node_c)) == NULL)
785 node->vertex = vertex;
786 node->next = tp->forced.first;
787 if (tp->forced.first != 0)
788 tp->forced.first->vertex->list_ptr = &(node->next);
789 tp->forced.first = node;
790 vertex->list_ptr = &(tp->forced.first);
791 tp->forced.n_nodes++;
792 if (!vertex->off_screen)
793 tp->forced.n_visible++;
795 node = *vertex->list_ptr;
796 node->forced_sides = forced_sides;
802 * Delete this vertex. If the vertex is a member of the forced vertex queue,
803 * also remove that entry. We assume that the vertex is no longer
804 * connected to the fringe. Note that tp->fringe.nodes must not point to
805 * the vertex being deleted.
808 delete_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
810 if (tp->fringe.nodes == vertex) {
812 if (MI_IS_VERBOSE(mi)) {
813 (void) fprintf(stderr, "Weirdness in delete_penrose()\n");
814 (void) fprintf(stderr, "tp->fringe.nodes == vertex\n");
816 tp->busyLoop = CELEBRATE;
818 if (vertex->list_ptr != 0) {
819 forced_node_c *node = *vertex->list_ptr;
821 *vertex->list_ptr = node->next;
823 node->next->vertex->list_ptr = vertex->list_ptr;
824 (void) free((void *) node);
825 tp->forced.n_nodes--;
826 if (!vertex->off_screen)
827 tp->forced.n_visible--;
829 if (!vertex->off_screen)
830 tp->fringe.n_nodes--;
831 (void) free((void *) vertex);
836 * Check whether the addition of a tile of type vtype would completely fill
837 * the space available at vertex.
840 fills_vertex(ModeInfo * mi, vertex_type_c vtype, fringe_node_c * vertex)
843 (vertex_dir(mi, vertex, S_LEFT) - vertex_dir(mi, vertex, S_RIGHT)
844 - vtype_angle(vtype)) % 10 == 0;
849 * If you were to add a tile of type vtype to a specified side of
850 * vertex, fringe_changes tells you which other vertices it would
851 * attach to. The addresses of these vertices will be stored in the
852 * last three arguments. Null is stored if the corresponding vertex
853 * would need to be allocated.
855 * The function also analyzes which vertices would be swallowed by the tiling
856 * and thus cut off from the fringe. The result is returned as a bit pattern.
858 #define FC_BAG 1 /* Total enclosure. Should never occur. */
859 #define FC_NEW_RIGHT 2
861 #define FC_NEW_LEFT 8
862 #define FC_NEW_MASK 0xe
863 #define FC_CUT_THIS 0x10
864 #define FC_CUT_RIGHT 0x20
865 #define FC_CUT_FAR 0x40
866 #define FC_CUT_LEFT 0x80
867 #define FC_CUT_MASK 0xf0
868 #define FC_TOTAL_MASK 0xff
871 fringe_changes(ModeInfo * mi, fringe_node_c * vertex,
872 unsigned side, vertex_type_c vtype,
873 fringe_node_c ** right, fringe_node_c ** far,
874 fringe_node_c ** left)
876 fringe_node_c *v, *f = (fringe_node_c *) NULL;
877 unsigned result = FC_NEW_FAR; /* We clear this later if necessary. */
881 if (fills_vertex(mi, vtype, vertex)) {
882 result |= FC_CUT_THIS;
883 } else if (side == S_LEFT) {
884 result |= FC_NEW_RIGHT;
888 result |= FC_NEW_LEFT;
893 if (!(result & FC_NEW_LEFT)) {
897 if (fills_vertex(mi, VT_LEFT(vtype), v)) {
898 result = (result & ~FC_NEW_FAR) | FC_CUT_LEFT;
904 if (!(result & FC_NEW_RIGHT)) {
908 if (fills_vertex(mi, VT_RIGHT(vtype), v)) {
909 result = (result & ~FC_NEW_FAR) | FC_CUT_RIGHT;
915 if (!(result & FC_NEW_FAR)
916 && fills_vertex(mi, VT_FAR(vtype), f)) {
917 result |= FC_CUT_FAR;
918 result &= (~FC_NEW_LEFT & ~FC_NEW_RIGHT);
919 if (right && (result & FC_CUT_LEFT))
921 if (left && (result & FC_CUT_RIGHT))
924 if (((result & FC_CUT_LEFT) && (result & FC_CUT_RIGHT))
925 || ((result & FC_CUT_THIS) && (result & FC_CUT_FAR)))
931 /* A couple of lesser helper functions for add_tile. */
933 add_vtype(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
936 vertex->tiles[vertex->n_tiles++] = vtype;
940 for (i = vertex->n_tiles; i > 0; i--)
941 vertex->tiles[i] = vertex->tiles[i - 1];
942 vertex->tiles[0] = vtype;
947 static fringe_node_c *
948 alloc_vertex(ModeInfo * mi, angle_c dir, fringe_node_c * from, tiling_c * tp)
952 if ((v = ALLOC_NODE(fringe_node_c)) == NULL) {
954 if (MI_IS_VERBOSE(mi)) {
955 (void) fprintf(stderr, "No memory in alloc_vertex()\n");
957 tp->busyLoop = CELEBRATE;
961 add_unit_vec(dir, v->fived);
962 fived_to_loc(v->fived, tp, &(v->loc));
963 if (v->loc.x < 0 || v->loc.y < 0
964 || v->loc.x >= tp->width || v->loc.y >= tp->height) {
965 v->off_screen = True;
966 if (v->loc.x < -tp->width || v->loc.y < -tp->height
967 || v->loc.x >= 2 * tp->width || v->loc.y >= 2 * tp->height)
970 v->off_screen = False;
971 tp->fringe.n_nodes++;
974 v->rule_mask = (1 << N_VERTEX_RULES) - 1;
980 * Add a tile described by vtype to the side of vertex. This must be
981 * allowed by the rules -- we do not check it here. New vertices are
982 * allocated as necessary. The fringe and the forced vertex pool are updated.
983 * The new tile is drawn on the display.
985 * One thing we do check here is whether the new tile causes an untiled
986 * area to become enclosed by the tiling. If this would happen, the tile
987 * is not added. The return value is true iff a tile was added.
990 add_tile(ModeInfo * mi,
991 fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
993 tiling_c *tp = &tilings[MI_SCREEN(mi)];
996 *left = (fringe_node_c *) NULL,
997 *right = (fringe_node_c *) NULL,
998 *far = (fringe_node_c *) NULL,
1000 unsigned fc = fringe_changes(mi, vertex, side, vtype, &right, &far, &left);
1003 ltype = VT_LEFT(vtype),
1004 rtype = VT_RIGHT(vtype),
1005 ftype = VT_FAR(vtype);
1007 /* By our conventions vertex->next lies to the left of vertex and
1008 vertex->prev to the right. */
1010 /* This should never occur. */
1013 if (MI_IS_VERBOSE(mi)) {
1014 (void) fprintf(stderr, "Weirdness in add_tile()\n");
1015 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1018 if (side == S_LEFT) {
1020 if ((right = alloc_vertex(mi, vertex_dir(mi, vertex, S_LEFT) -
1021 vtype_angle(vtype), vertex, tp)) == NULL)
1024 if ((far = alloc_vertex(mi, vertex_dir(mi, left, S_RIGHT) +
1025 vtype_angle(ltype), left, tp)) == NULL)
1029 if ((left = alloc_vertex(mi, vertex_dir(mi, vertex, S_RIGHT) +
1030 vtype_angle(vtype), vertex, tp)) == NULL)
1033 if ((far = alloc_vertex(mi, vertex_dir(mi, right, S_LEFT) -
1034 vtype_angle(rtype), right, tp)) == NULL)
1038 /* Having allocated the new vertices, but before joining them with
1039 the rest of the fringe, check if vertices with same coordinates
1040 already exist. If any such are found, give up. */
1041 node = tp->fringe.nodes;
1043 if (((fc & FC_NEW_LEFT) && fived_equal(node->fived, left->fived))
1044 || ((fc & FC_NEW_RIGHT) && fived_equal(node->fived, right->fived))
1045 || ((fc & FC_NEW_FAR) && fived_equal(node->fived, far->fived))) {
1046 /* Better luck next time. */
1047 if (fc & FC_NEW_LEFT)
1048 delete_vertex(mi, left, tp);
1049 if (fc & FC_NEW_RIGHT)
1050 delete_vertex(mi, right, tp);
1051 if (fc & FC_NEW_FAR)
1052 delete_vertex(mi, far, tp);
1056 } while (node != tp->fringe.nodes);
1059 if (!(fc & FC_CUT_THIS)) {
1060 if (side == S_LEFT) {
1061 vertex->next = right;
1062 right->prev = vertex;
1064 vertex->prev = left;
1065 left->next = vertex;
1068 if (!(fc & FC_CUT_FAR)) {
1069 if (!(fc & FC_CUT_LEFT)) {
1073 if (!(fc & FC_CUT_RIGHT)) {
1078 draw_tile(vertex, right, far, left, vtype, mi);
1080 /* Delete vertices that are no longer on the fringe. Check the others. */
1081 if (fc & FC_CUT_THIS) {
1082 tp->fringe.nodes = far;
1083 delete_vertex(mi, vertex, tp);
1085 add_vtype(vertex, side, vtype);
1086 check_vertex(mi, vertex, tp);
1087 tp->fringe.nodes = vertex;
1089 if (fc & FC_CUT_FAR)
1090 delete_vertex(mi, far, tp);
1092 add_vtype(far, fc & FC_CUT_RIGHT ? S_LEFT : S_RIGHT, ftype);
1093 check_vertex(mi, far, tp);
1095 if (fc & FC_CUT_LEFT)
1096 delete_vertex(mi, left, tp);
1098 add_vtype(left, fc & FC_CUT_FAR ? S_LEFT : S_RIGHT, ltype);
1099 check_vertex(mi, left, tp);
1101 if (fc & FC_CUT_RIGHT)
1102 delete_vertex(mi, right, tp);
1104 add_vtype(right, fc & FC_CUT_FAR ? S_RIGHT : S_LEFT, rtype);
1105 check_vertex(mi, right, tp);
1112 * Add a forced tile to a given forced vertex. Basically an easy job,
1113 * since we know what to add. But it might fail if adding the tile
1114 * would cause some untiled area to become enclosed. There is also another
1115 * more exotic culprit: we might have a dislocation. Fortunately, they
1116 * are very rare (the PRL article reported that perfect tilings of over
1117 * 2^50 tiles had been generated). There is a version of the algorithm
1118 * that doesn't produce dislocations, but it's a lot hairier than the
1119 * simpler version I used.
1122 add_forced_tile(ModeInfo * mi, forced_node_c * node)
1124 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1126 vertex_type_c vtype;
1127 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1130 if (node->forced_sides == (S_LEFT | S_RIGHT))
1131 side = NRAND(2) ? S_LEFT : S_RIGHT;
1133 side = node->forced_sides;
1134 n = match_rules(node->vertex, hits, True);
1135 n = find_completions(node->vertex, hits, n, side, &vtype /*, True */ );
1138 if (MI_IS_VERBOSE(mi)) {
1139 (void) fprintf(stderr, "Weirdness in add_forced_tile()\n");
1140 (void) fprintf(stderr, "n = %d\n", n);
1143 return add_tile(mi, node->vertex, side, vtype);
1148 * Whether the addition of a tile of vtype on the given side of vertex
1149 * would conform to the rules. The efficient way to do this would be
1150 * to add the new tile and then use the same type of search as in
1151 * match_rules. However, this function is not a performance
1152 * bottleneck (only needed for random tile additions, which are
1153 * relatively infrequent), so I will settle for a simpler implementation.
1156 legal_move(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
1158 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1159 vertex_type_c legal_vt[MAX_COMPL];
1160 int n_hits, n_legal, i;
1162 n_hits = match_rules(vertex, hits, False);
1163 n_legal = find_completions(vertex, hits, n_hits, side, legal_vt /*, False */ );
1164 for (i = 0; i < n_legal; i++)
1165 if (legal_vt[i] == vtype)
1172 * Add a randomly chosen tile to a given vertex. This requires more checking
1173 * as we must make sure the new tile conforms to the vertex rules at every
1174 * vertex it touches. */
1176 add_random_tile(fringe_node_c * vertex, ModeInfo * mi)
1178 fringe_node_c *right, *left, *far;
1179 int i, j, n, n_hits, n_good;
1180 unsigned side, fc, no_good, s;
1181 vertex_type_c vtypes[MAX_COMPL];
1182 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1183 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1185 if (MI_NPIXELS(mi) > 2) {
1186 tp->thick_color = NRAND(MI_NPIXELS(mi));
1187 /* Insure good contrast */
1188 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
1189 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
1191 tp->thick_color = tp->thin_color = MI_WHITE_PIXEL(mi);
1192 n_hits = match_rules(vertex, hits, False);
1193 side = NRAND(2) ? S_LEFT : S_RIGHT;
1194 n = find_completions(vertex, hits, n_hits, side, vtypes /*, False */ );
1195 /* One answer would mean a forced tile. */
1198 if (MI_IS_VERBOSE(mi)) {
1199 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1200 (void) fprintf(stderr, "n = %d\n", n);
1205 for (i = 0; i < n; i++) {
1206 fc = fringe_changes(mi, vertex, side, vtypes[i], &right, &far, &left);
1209 if (MI_IS_VERBOSE(mi)) {
1210 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1211 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1215 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_LEFT)) ? S_RIGHT : S_LEFT);
1216 if (!legal_move(right, s, VT_RIGHT(vtypes[i]))) {
1217 no_good |= (1 << i);
1223 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_RIGHT)) ? S_LEFT : S_RIGHT);
1224 if (!legal_move(left, s, VT_LEFT(vtypes[i]))) {
1225 no_good |= (1 << i);
1231 s = ((fc & FC_CUT_LEFT) ? S_RIGHT : S_LEFT);
1232 if (!legal_move(far, s, VT_FAR(vtypes[i]))) {
1233 no_good |= (1 << i);
1240 if (MI_IS_VERBOSE(mi)) {
1241 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1242 (void) fprintf(stderr, "n_good = %d\n", n_good);
1246 for (i = j = 0; i <= n; i++, j++)
1247 while (no_good & (1 << j))
1250 if (!add_tile(mi, vertex, side, vtypes[j - 1])) {
1252 if (MI_IS_VERBOSE(mi)) {
1253 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1259 /* One step of the growth algorithm. */
1261 draw_penrose(ModeInfo * mi)
1267 if (tilings == NULL)
1269 tp = &tilings[MI_SCREEN(mi)];
1270 if (tp->fringe.nodes == NULL)
1273 MI_IS_DRAWN(mi) = True;
1274 p = tp->forced.first;
1275 if (tp->busyLoop > 0) {
1279 if (tp->done || tp->failures >= 100) {
1283 /* Check for the initial "2-gon". */
1284 if (tp->fringe.nodes->prev == tp->fringe.nodes->next) {
1285 vertex_type_c vtype = (unsigned char) (VT_TOTAL_MASK & LRAND());
1289 if (!add_tile(mi, tp->fringe.nodes, S_LEFT, vtype))
1293 /* No visible nodes left. */
1294 if (tp->fringe.n_nodes == 0) {
1296 tp->busyLoop = COMPLETION; /* Just finished drawing */
1299 if (tp->forced.n_visible > 0 && tp->failures < 10) {
1300 n = NRAND(tp->forced.n_visible);
1302 while (p->vertex->off_screen)
1309 } else if (tp->forced.n_nodes > 0) {
1310 n = NRAND(tp->forced.n_nodes);
1314 fringe_node_c *fringe_p = tp->fringe.nodes;
1316 n = NRAND(tp->fringe.n_nodes);
1320 fringe_p = fringe_p->next;
1321 } while (fringe_p->off_screen);
1322 add_random_tile(fringe_p, mi);
1326 if (add_forced_tile(mi, p))
1333 /* Total clean-up. */
1335 release_penrose(ModeInfo * mi)
1337 if (tilings != NULL) {
1340 for (screen = 0; screen < MI_NUM_SCREENS(mi); screen++)
1341 free_penrose(&tilings[screen]);
1342 (void) free((void *) tilings);
1343 tilings = (tiling_c *) NULL;
1347 #endif /* MODE_penrose */