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
22 static const char sccsid[] = "@(#)penrose.c 5.00 2000/11/01 xlockmore";
26 * Copyright (c) 1996 by Timo Korvola <tkorvola@dopey.hut.fi>
28 * Permission to use, copy, modify, and distribute this software and its
29 * documentation for any purpose and without fee is hereby granted,
30 * provided that the above copyright notice appear in all copies and that
31 * both that copyright notice and this permission notice appear in
32 * supporting documentation.
34 * This file is provided AS IS with no warranties of any kind. The author
35 * shall have no liability with respect to the infringement of copyrights,
36 * trade secrets or any patents by this file or any part thereof. In no
37 * event will the author be liable for any lost revenue or profits or
38 * other special, indirect and consequential damages.
41 * 01-Nov-2000: Allocation checks
42 * 10-May-1997: Jamie Zawinski <jwz@jwz.org> compatible with xscreensaver
43 * 09-Sep-1996: Written.
47 Be careful, this probably still has a few bugs (many of which may only
48 appear with a very low probability). These are seen with -verbose .
49 If one of these are hit penrose will reinitialize.
53 * See Onoda, Steinhardt, DiVincenzo and Socolar in
54 * Phys. Rev. Lett. 60, #25, 1988 or
55 * Strandburg in Computers in Physics, Sep/Oct 1991.
57 * This implementation uses the simpler version of the growth
58 * algorithm, i.e., if there are no forced vertices, a randomly chosen
59 * tile is added to a randomly chosen vertex (no preference for those
62 * There are two essential differences to the algorithm presented in
63 * the literature: First, we do not allow the tiling to enclose an
64 * untiled area. Whenever this is in danger of happening, we just
65 * do not add the tile, hoping for a better random choice the next
66 * time. Second, when choosing a vertex randomly, we will take
67 * one that lies within the viewport if available. If this seems to
68 * cause enclosures in the forced rule case, we will allow invisible
69 * vertices to be chosen.
71 * Tiling is restarted whenever one of the following happens: there
72 * are no incomplete vertices within the viewport or the tiling has
73 * extended a window's length beyond the edge of the window
74 * horizontally or vertically or forced rule choice has failed 100
75 * times due to areas about to become enclosed.
78 * Science News March 23 1985 Vol 127, No. 12
79 * Science News July 16 1988 Vol 134, No. 3
80 * The Economist Sept 17 1988 pg. 100
86 #define DEFAULTS "*delay: 10000 \n" \
89 "*fpsSolid: true \n" \
91 # define refresh_penrose 0
92 # define penrose_handle_event 0
93 # include "xlockmore.h" /* from the xscreensaver distribution */
94 #else /* !STANDALONE */
95 # include "xlock.h" /* from the xlockmore distribution */
96 #endif /* !STANDALONE */
100 #define DEF_AMMANN "False"
104 static XrmOptionDescRec opts[] =
106 {"-ammann", ".penrose.ammann", XrmoptionNoArg, "on"},
107 {"+ammann", ".penrose.ammann", XrmoptionNoArg, "off"}
109 static argtype vars[] =
111 {&ammann, "ammann", "Ammann", DEF_AMMANN, t_Bool}
113 static OptionStruct desc[] =
115 {"-/+ammann", "turn on/off Ammann lines"}
118 ENTRYPOINT ModeSpecOpt penrose_opts =
119 {sizeof opts / sizeof opts[0], opts, sizeof vars / sizeof vars[0], vars, desc};
122 ModStruct penrose_description =
123 {"penrose", "init_penrose", "draw_penrose", "release_penrose",
124 "init_penrose", "init_penrose", (char *) NULL, &penrose_opts,
125 10000, 1, 1, -40, 64, 1.0, "",
126 "Shows Penrose's quasiperiodic tilings", 0, NULL};
131 * Annoyingly the ANSI C library people have reserved all identifiers
132 * ending with _t for future use. Hence we use _c as a suffix for
133 * typedefs (c for class, although this is not C++).
139 * In theory one could fit 10 tiles to a single vertex. However, the
140 * vertex rules only allow at most seven tiles to meet at a vertex.
143 #define CELEBRATE 31415 /* This causes a pause, an error occurred. */
144 #define COMPLETION 3141 /* This causes a pause, tiles filled up screen. */
146 #define MAX_TILES_PER_VERTEX 7
147 #define N_VERTEX_RULES 8
148 #define ALLOC_NODE(type) (type *)malloc(sizeof (type))
151 * These are used to specify directions. They can also be used in bit
152 * masks to specify a combination of directions.
159 * We do not actually maintain objects corresponding to the tiles since
160 * we do not really need them and they would only consume memory and
161 * cause additional bookkeeping. Instead we only have vertices, and
162 * each vertex lists the type of each adjacent tile as well as the
163 * position of the vertex on the tile (hereafter refered to as
164 * "corner"). These positions are numbered in counterclockwise order
165 * so that 0 is where two double arrows meet (see one of the
166 * articles). The tile type and vertex number are stored in a single
167 * integer (we use char, and even most of it remains unused).
169 * The primary use of tile objects would be draw traversal, but we do
170 * not currently do redraws at all (we just start over).
172 #define VT_CORNER_MASK 0x3
173 #define VT_TYPE_MASK 0x4
177 #define VT_TOTAL_MASK 0x7
179 typedef unsigned char vertex_type_c;
182 * These allow one to compute the types of the other corners of the tile. If
183 * you are standing at a vertex of type vt looking towards the middle of the
184 * tile, VT_LEFT( vt) is the vertex on your left etc.
186 #define VT_LEFT( vt) ((((vt) - 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
187 #define VT_RIGHT( vt) ((((vt) + 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
188 #define VT_FAR( vt) ((vt) ^ 2)
192 * Since we do not do redraws, we only store the vertices we need. These are
193 * the ones with still some empty space around them for the growth algorithm
196 * Here we use a doubly chained ring-like structure as vertices often need
197 * to be removed or inserted (they are kept in geometrical order
198 * circling the tiled area counterclockwise). The ring is refered to by
199 * a pointer to one more or less random node. When deleting nodes one
200 * must make sure that this pointer continues to refer to a valid
201 * node. A vertex count is maintained to make it easier to pick
204 typedef struct forced_node forced_node_c;
206 typedef struct fringe_node {
207 struct fringe_node *prev;
208 struct fringe_node *next;
209 /* These are numbered counterclockwise. The gap, if any, lies
210 between the last and first tiles. */
211 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
213 /* A bit mask used to indicate vertex rules that are still applicable for
214 completing this vertex. Initialize this to (1 << N_VERTEX_RULES) - 1,
215 i.e., all ones, and the rule matching functions will automatically mask
216 out rules that no longer match. */
217 unsigned char rule_mask;
218 /* If the vertex is on the forced vertex list, this points to the
219 pointer to the appropriate node in the list. To remove the
220 vertex from the list just set *list_ptr to the next node,
221 deallocate and decrement node count. */
222 struct forced_node **list_ptr;
223 /* Screen coordinates. */
225 /* We also keep track of 5D coordinates to avoid rounding errors.
226 These are in units of edge length. */
228 /* This is used to quickly check if a vertex is visible. */
229 unsigned char off_screen;
233 fringe_node_c *nodes;
234 /* This does not count off-screen nodes. */
240 * The forced vertex pool contains vertices where at least one
241 * side of the tiled region can only be extended in one way. Note
242 * that this does not necessarily mean that there would only be one
243 * applicable rule. forced_sides are specified using S_LEFT and
244 * S_RIGHT as if looking at the untiled region from the vertex.
247 fringe_node_c *vertex;
248 unsigned forced_sides;
249 struct forced_node *next;
253 forced_node_c *first;
254 int n_nodes, n_visible;
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 /* This is the data related to the tiling of one screen. */
315 forced_pool_c forced;
317 unsigned long thick_color, thin_color;
321 fcoord_c fived_table[5];
324 static tiling_c *tilings = (tiling_c *) NULL;
328 /* Direction angle of an edge. */
330 vertex_dir(ModeInfo * mi, fringe_node_c * vertex, unsigned side)
332 tiling_c *tp = &tilings[MI_SCREEN(mi)];
334 (side == S_LEFT ? vertex->next : vertex->prev);
337 for (i = 0; i < 5; i++)
338 switch (v2->fived[i] - vertex->fived[i]) {
342 return (2 * i + 5) % 10;
345 if (MI_IS_VERBOSE(mi)) {
346 (void) fprintf(stderr,
347 "Weirdness in vertex_dir (this has been reported)\n");
348 for (i = 0; i < 5; i++)
349 (void) fprintf(stderr, "v2->fived[%d]=%d, vertex->fived[%d]=%d\n",
350 i, v2->fived[i], i, vertex->fived[i]);
352 tp->busyLoop = CELEBRATE;
357 /* Move one step to a given direction. */
359 add_unit_vec(angle_c dir, int *fived)
361 static const int dir2i[] = {0, 3, 1, 4, 2};
365 fived[dir2i[dir % 5]] += (dir % 2 ? -1 : 1);
369 /* For comparing coordinates. */
370 #define fived_equal( f1, f2) (!memcmp( (f1), (f2), 5 * sizeof( int)))
374 * This computes screen coordinates from 5D representation. Note that X
375 * uses left-handed coordinates (y increases downwards).
378 fived_to_loc(int fived[], tiling_c * tp, XPoint *pt)
380 float fifth = 8 * atan(1.) / 5;
383 register fcoord_c offset;
388 if (tp->fived_table[0].x == .0)
389 for (i = 0; i < 5; i++) {
390 tp->fived_table[i].x = cos(fifth * i);
391 tp->fived_table[i].y = sin(fifth * i);
393 for (i = 0; i < 5; i++) {
394 r = fived[i] * tp->edge_length;
395 offset.x += r * tp->fived_table[i].x;
396 offset.y -= r * tp->fived_table[i].y;
398 (*pt).x += (int) (offset.x + .5);
399 (*pt).y += (int) (offset.y + .5);
403 /* Mop up dynamic data for one screen. */
405 free_penrose(tiling_c * tp)
407 register fringe_node_c *fp1, *fp2;
408 register forced_node_c *lp1, *lp2;
410 if (tp->fringe.nodes == NULL)
412 fp1 = tp->fringe.nodes;
416 (void) free((void *) fp2);
417 } while (fp1 != tp->fringe.nodes);
418 tp->fringe.nodes = (fringe_node_c *) NULL;
419 for (lp1 = tp->forced.first; lp1 != 0;) {
422 (void) free((void *) lp2);
424 tp->forced.first = 0;
428 /* Called to init the mode. */
430 init_penrose(ModeInfo * mi)
436 if (tilings == NULL) {
437 if ((tilings = (tiling_c *) calloc(MI_NUM_SCREENS(mi),
438 sizeof (tiling_c))) == NULL)
441 tp = &tilings[MI_SCREEN(mi)];
443 #if 0 /* if you do this, then the -ammann and -no-ammann options don't work.
445 if (MI_IS_FULLRANDOM(mi))
446 tp->ammann = (Bool) (LRAND() & 1);
454 tp->width = MI_WIDTH(mi);
455 tp->height = MI_HEIGHT(mi);
456 if (MI_NPIXELS(mi) > 2) {
457 tp->thick_color = NRAND(MI_NPIXELS(mi));
458 /* Insure good contrast */
459 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
460 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
464 tp->edge_length = NRAND(MIN(-size, MAX(MINSIZE,
465 MIN(tp->width, tp->height) / 2)) - MINSIZE + 1) + MINSIZE;
466 else if (size < MINSIZE) {
468 tp->edge_length = MAX(MINSIZE, MIN(tp->width, tp->height) / 2);
470 tp->edge_length = MINSIZE;
472 tp->edge_length = MIN(size, MAX(MINSIZE,
473 MIN(tp->width, tp->height) / 2));
474 tp->origin.x = (tp->width / 2 + NRAND(tp->width)) / 2;
475 tp->origin.y = (tp->height / 2 + NRAND(tp->height)) / 2;
476 tp->fringe.n_nodes = 2;
477 if (tp->fringe.nodes != NULL)
479 if (tp->fringe.nodes != NULL || tp->forced.first != 0) {
480 if (MI_IS_VERBOSE(mi)) {
481 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
482 (void) fprintf(stderr, "tp->fringe.nodes = NULL && tp->forced.first = 0\n");
484 free_penrose(tp); /* Try again */
487 tp->forced.n_nodes = tp->forced.n_visible = 0;
488 if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
493 if (MI_IS_VERBOSE(mi)) {
494 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
495 (void) fprintf(stderr, "fp = 0\n");
497 if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
504 fp->rule_mask = (1 << N_VERTEX_RULES) - 1;
506 if ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
511 if (MI_IS_VERBOSE(mi)) {
512 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
513 (void) fprintf(stderr, "fp->next = 0\n");
515 if ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
522 fp->loc = tp->origin;
523 fp->off_screen = False;
524 for (i = 0; i < 5; i++)
529 fp->next->prev = fp->next->next = fp;
532 fp->fived[i] = 2 * NRAND(2) - 1;
533 fived_to_loc(fp->fived, tp, &(fp->loc));
534 /* That's it! We have created our first edge. */
538 * This attempts to match the configuration of vertex with the vertex
539 * rules. The return value is a total match count. If matches is
540 * non-null, it will be used to store information about the matches
541 * and must be large enough to contain it. To play it absolutely
542 * safe, allocate room for MAX_TILES_PER_VERTEX * N_VERTEX_RULES
543 * entries when searching all matches. The rule mask of vertex will
544 * be applied and rules masked out will not be searched. Only strict
545 * subsequences match. If first_only is true, the search stops when
546 * the first match is found. Otherwise all matches will be found and
547 * the rule_mask of vertex will be updated, which also happens in
548 * single-match mode if no match is found.
551 match_rules(fringe_node_c * vertex, rule_match_c * matches, int first_only)
553 /* I will assume that I can fit all the relevant bits in vertex->tiles
554 into one unsigned long. With 3 bits per element and at most 7
555 elements this means 21 bits, which should leave plenty of room.
556 After packing the bits the rest is just integer comparisons and
557 some bit shuffling. This is essentially Rabin-Karp without
558 congruence arithmetic. */
560 int hits = 0, good_rules[N_VERTEX_RULES], n_good = 0;
562 vertex_hash = 0, lower_bits_mask = ~(VT_TOTAL_MASK << VT_BITS * (vertex->n_tiles - 1));
563 unsigned new_rule_mask = 0;
565 for (i = 0; i < N_VERTEX_RULES; i++)
566 if (vertex->n_tiles >= vertex_rules[i].n_tiles)
567 vertex->rule_mask &= ~(1 << i);
568 else if (vertex->rule_mask & 1 << i)
569 good_rules[n_good++] = i;
570 for (i = 0; i < vertex->n_tiles; i++)
571 vertex_hash |= (unsigned long) vertex->tiles[i] << (VT_BITS * i);
573 for (j = 0; j < n_good; j++) {
574 unsigned long rule_hash = 0;
575 vertex_rule_c *vr = vertex_rules + good_rules[j];
577 for (i = 0; i < vertex->n_tiles; i++)
578 rule_hash |= (unsigned long) vr->tiles[i] << (VT_BITS * i);
579 if (rule_hash == vertex_hash) {
581 matches[hits].rule = good_rules[j];
582 matches[hits].pos = 0;
588 new_rule_mask |= 1 << good_rules[j];
590 for (i = vr->n_tiles - 1; i > 0; i--) {
591 rule_hash = vr->tiles[i] | (rule_hash & lower_bits_mask) << VT_BITS;
592 if (vertex_hash == rule_hash) {
594 matches[hits].rule = good_rules[j];
595 matches[hits].pos = i;
601 new_rule_mask |= 1 << good_rules[j];
605 vertex->rule_mask = new_rule_mask;
611 * find_completions finds the possible ways to add a tile to a vertex.
612 * The return values is the number of such possibilities. You must
613 * first call match_rules to produce matches and n_matches. sides
614 * specifies which side of the vertex to extend and can be S_LEFT or
615 * S_RIGHT. If results is non-null, it should point to an array large
616 * enough to contain the results, which will be stored there.
617 * MAX_COMPL elements will always suffice. If first_only is true we
618 * stop as soon as we find one possibility (NOT USED).
623 find_completions(fringe_node_c * vertex, rule_match_c * matches, int n_matches,
624 unsigned side, vertex_type_c * results /*, int first_only */ )
628 vertex_type_c buf[MAX_COMPL];
634 for (i = 0; i < n_matches; i++) {
635 vertex_rule_c *rule = vertex_rules + matches[i].rule;
636 int pos = (matches[i].pos
637 + (side == S_RIGHT ? vertex->n_tiles : rule->n_tiles - 1))
639 vertex_type_c vtype = rule->tiles[pos];
642 for (j = 0; j < n_res; j++)
643 if (vtype == results[j]) {
648 results[n_res++] = vtype;
655 * Draw a tile on the display. Vertices must be given in a
656 * counterclockwise order. vtype is the vertex type of v1 (and thus
657 * also gives the tile type).
660 draw_tile(fringe_node_c * v1, fringe_node_c * v2,
661 fringe_node_c * v3, fringe_node_c * v4,
662 vertex_type_c vtype, ModeInfo * mi)
664 Display *display = MI_DISPLAY(mi);
665 Window window = MI_WINDOW(mi);
667 tiling_c *tp = &tilings[MI_SCREEN(mi)];
669 vertex_type_c corner = vtype & VT_CORNER_MASK;
671 if (v1->off_screen && v2->off_screen && v3->off_screen && v4->off_screen)
673 pts[corner] = v1->loc;
674 pts[VT_RIGHT(corner)] = v2->loc;
675 pts[VT_FAR(corner)] = v3->loc;
676 pts[VT_LEFT(corner)] = v4->loc;
678 if (MI_NPIXELS(mi) > 2) {
679 if ((vtype & VT_TYPE_MASK) == VT_THICK)
680 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
682 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
684 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
685 XFillPolygon(display, window, gc, pts, 4, Convex, CoordModeOrigin);
686 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
687 XDrawLines(display, window, gc, pts, 5, CoordModeOrigin);
690 /* Draw some Ammann lines for debugging purposes. This will probably
691 fail miserably on a b&w display. */
693 if ((vtype & VT_TYPE_MASK) == VT_THICK) {
695 if (tp->ammann_r == .0) {
696 float pi10 = 2 * atan(1.) / 5;
698 tp->ammann_r = 1 - sin(pi10) / (2 * sin(3 * pi10));
700 if (MI_NPIXELS(mi) > 2)
701 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
703 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
704 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
706 XDrawLine(display, window, gc,
707 (int) (tp->ammann_r * pts[3].x + (1 - tp->ammann_r) * pts[0].x + .5),
708 (int) (tp->ammann_r * pts[3].y + (1 - tp->ammann_r) * pts[0].y + .5),
709 (int) (tp->ammann_r * pts[1].x + (1 - tp->ammann_r) * pts[0].x + .5),
710 (int) (tp->ammann_r * pts[1].y + (1 - tp->ammann_r) * pts[0].y + .5));
711 if (MI_NPIXELS(mi) <= 2)
712 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
714 if (MI_NPIXELS(mi) > 2)
715 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
717 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
718 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
720 XDrawLine(display, window, gc,
721 (int) ((pts[3].x + pts[2].x) / 2 + .5),
722 (int) ((pts[3].y + pts[2].y) / 2 + .5),
723 (int) ((pts[1].x + pts[2].x) / 2 + .5),
724 (int) ((pts[1].y + pts[2].y) / 2 + .5));
725 if (MI_NPIXELS(mi) <= 2)
726 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
732 * Update the status of this vertex on the forced vertex queue. If
733 * the vertex has become untileable set tp->done. This is supposed
734 * to detect dislocations -- never call this routine with a completely
737 * Check for untileable vertices in check_vertex and stop tiling as
738 * soon as one finds one. I don't know if it is possible to run out
739 * of forced vertices while untileable vertices exist (or will
740 * cavities inevitably appear). If this can happen, add_random_tile
741 * might get called with an untileable vertex, causing ( n <= 1).
742 * (This is what the tp->done checks for).
744 * A delayLoop celebrates the dislocation.
747 check_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
749 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
750 int n_hits = match_rules(vertex, hits, False);
751 unsigned forced_sides = 0;
753 if (vertex->rule_mask == 0) {
755 if (MI_IS_VERBOSE(mi)) {
756 (void) fprintf(stderr, "Dislocation occurred!\n");
758 tp->busyLoop = CELEBRATE; /* Should be able to recover */
760 if (1 == find_completions(vertex, hits, n_hits, S_LEFT, 0 /*, False */ ))
761 forced_sides |= S_LEFT;
762 if (1 == find_completions(vertex, hits, n_hits, S_RIGHT, 0 /*, False */ ))
763 forced_sides |= S_RIGHT;
764 if (forced_sides == 0) {
765 if (vertex->list_ptr != 0) {
766 forced_node_c *node = *vertex->list_ptr;
768 *vertex->list_ptr = node->next;
770 node->next->vertex->list_ptr = vertex->list_ptr;
771 (void) free((void *) node);
772 tp->forced.n_nodes--;
773 if (!vertex->off_screen)
774 tp->forced.n_visible--;
775 vertex->list_ptr = 0;
780 if (vertex->list_ptr == 0) {
781 if ((node = ALLOC_NODE(forced_node_c)) == NULL)
783 node->vertex = vertex;
784 node->next = tp->forced.first;
785 if (tp->forced.first != 0)
786 tp->forced.first->vertex->list_ptr = &(node->next);
787 tp->forced.first = node;
788 vertex->list_ptr = &(tp->forced.first);
789 tp->forced.n_nodes++;
790 if (!vertex->off_screen)
791 tp->forced.n_visible++;
793 node = *vertex->list_ptr;
794 node->forced_sides = forced_sides;
800 * Delete this vertex. If the vertex is a member of the forced vertex queue,
801 * also remove that entry. We assume that the vertex is no longer
802 * connected to the fringe. Note that tp->fringe.nodes must not point to
803 * the vertex being deleted.
806 delete_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
808 if (tp->fringe.nodes == vertex) {
810 if (MI_IS_VERBOSE(mi)) {
811 (void) fprintf(stderr, "Weirdness in delete_penrose()\n");
812 (void) fprintf(stderr, "tp->fringe.nodes == vertex\n");
814 tp->busyLoop = CELEBRATE;
816 if (vertex->list_ptr != 0) {
817 forced_node_c *node = *vertex->list_ptr;
819 *vertex->list_ptr = node->next;
821 node->next->vertex->list_ptr = vertex->list_ptr;
822 (void) free((void *) node);
823 tp->forced.n_nodes--;
824 if (!vertex->off_screen)
825 tp->forced.n_visible--;
827 if (!vertex->off_screen)
828 tp->fringe.n_nodes--;
829 (void) free((void *) vertex);
834 * Check whether the addition of a tile of type vtype would completely fill
835 * the space available at vertex.
838 fills_vertex(ModeInfo * mi, vertex_type_c vtype, fringe_node_c * vertex)
841 (vertex_dir(mi, vertex, S_LEFT) - vertex_dir(mi, vertex, S_RIGHT)
842 - vtype_angle(vtype)) % 10 == 0;
847 * If you were to add a tile of type vtype to a specified side of
848 * vertex, fringe_changes tells you which other vertices it would
849 * attach to. The addresses of these vertices will be stored in the
850 * last three arguments. Null is stored if the corresponding vertex
851 * would need to be allocated.
853 * The function also analyzes which vertices would be swallowed by the tiling
854 * and thus cut off from the fringe. The result is returned as a bit pattern.
856 #define FC_BAG 1 /* Total enclosure. Should never occur. */
857 #define FC_NEW_RIGHT 2
859 #define FC_NEW_LEFT 8
860 #define FC_NEW_MASK 0xe
861 #define FC_CUT_THIS 0x10
862 #define FC_CUT_RIGHT 0x20
863 #define FC_CUT_FAR 0x40
864 #define FC_CUT_LEFT 0x80
865 #define FC_CUT_MASK 0xf0
866 #define FC_TOTAL_MASK 0xff
869 fringe_changes(ModeInfo * mi, fringe_node_c * vertex,
870 unsigned side, vertex_type_c vtype,
871 fringe_node_c ** right, fringe_node_c ** far,
872 fringe_node_c ** left)
874 fringe_node_c *v, *f = (fringe_node_c *) NULL;
875 unsigned result = FC_NEW_FAR; /* We clear this later if necessary. */
879 if (fills_vertex(mi, vtype, vertex)) {
880 result |= FC_CUT_THIS;
881 } else if (side == S_LEFT) {
882 result |= FC_NEW_RIGHT;
886 result |= FC_NEW_LEFT;
891 if (!(result & FC_NEW_LEFT)) {
895 if (fills_vertex(mi, VT_LEFT(vtype), v)) {
896 result = (result & ~FC_NEW_FAR) | FC_CUT_LEFT;
902 if (!(result & FC_NEW_RIGHT)) {
906 if (fills_vertex(mi, VT_RIGHT(vtype), v)) {
907 result = (result & ~FC_NEW_FAR) | FC_CUT_RIGHT;
913 if (!(result & FC_NEW_FAR)
914 && fills_vertex(mi, VT_FAR(vtype), f)) {
915 result |= FC_CUT_FAR;
916 result &= (~FC_NEW_LEFT & ~FC_NEW_RIGHT);
917 if (right && (result & FC_CUT_LEFT))
919 if (left && (result & FC_CUT_RIGHT))
922 if (((result & FC_CUT_LEFT) && (result & FC_CUT_RIGHT))
923 || ((result & FC_CUT_THIS) && (result & FC_CUT_FAR)))
929 /* A couple of lesser helper functions for add_tile. */
931 add_vtype(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
934 vertex->tiles[vertex->n_tiles++] = vtype;
938 for (i = vertex->n_tiles; i > 0; i--)
939 vertex->tiles[i] = vertex->tiles[i - 1];
940 vertex->tiles[0] = vtype;
945 static fringe_node_c *
946 alloc_vertex(ModeInfo * mi, angle_c dir, fringe_node_c * from, tiling_c * tp)
950 if ((v = ALLOC_NODE(fringe_node_c)) == NULL) {
952 if (MI_IS_VERBOSE(mi)) {
953 (void) fprintf(stderr, "No memory in alloc_vertex()\n");
955 tp->busyLoop = CELEBRATE;
959 add_unit_vec(dir, v->fived);
960 fived_to_loc(v->fived, tp, &(v->loc));
961 if (v->loc.x < 0 || v->loc.y < 0
962 || v->loc.x >= tp->width || v->loc.y >= tp->height) {
963 v->off_screen = True;
964 if (v->loc.x < -tp->width || v->loc.y < -tp->height
965 || v->loc.x >= 2 * tp->width || v->loc.y >= 2 * tp->height)
968 v->off_screen = False;
969 tp->fringe.n_nodes++;
972 v->rule_mask = (1 << N_VERTEX_RULES) - 1;
978 * Add a tile described by vtype to the side of vertex. This must be
979 * allowed by the rules -- we do not check it here. New vertices are
980 * allocated as necessary. The fringe and the forced vertex pool are updated.
981 * The new tile is drawn on the display.
983 * One thing we do check here is whether the new tile causes an untiled
984 * area to become enclosed by the tiling. If this would happen, the tile
985 * is not added. The return value is true iff a tile was added.
988 add_tile(ModeInfo * mi,
989 fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
991 tiling_c *tp = &tilings[MI_SCREEN(mi)];
994 *left = (fringe_node_c *) NULL,
995 *right = (fringe_node_c *) NULL,
996 *far = (fringe_node_c *) NULL,
998 unsigned fc = fringe_changes(mi, vertex, side, vtype, &right, &far, &left);
1001 ltype = VT_LEFT(vtype),
1002 rtype = VT_RIGHT(vtype),
1003 ftype = VT_FAR(vtype);
1005 /* By our conventions vertex->next lies to the left of vertex and
1006 vertex->prev to the right. */
1008 /* This should never occur. */
1011 if (MI_IS_VERBOSE(mi)) {
1012 (void) fprintf(stderr, "Weirdness in add_tile()\n");
1013 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1016 if (side == S_LEFT) {
1018 if ((right = alloc_vertex(mi, vertex_dir(mi, vertex, S_LEFT) -
1019 vtype_angle(vtype), vertex, tp)) == NULL)
1022 if ((far = alloc_vertex(mi, vertex_dir(mi, left, S_RIGHT) +
1023 vtype_angle(ltype), left, tp)) == NULL)
1027 if ((left = alloc_vertex(mi, vertex_dir(mi, vertex, S_RIGHT) +
1028 vtype_angle(vtype), vertex, tp)) == NULL)
1031 if ((far = alloc_vertex(mi, vertex_dir(mi, right, S_LEFT) -
1032 vtype_angle(rtype), right, tp)) == NULL)
1036 /* Having allocated the new vertices, but before joining them with
1037 the rest of the fringe, check if vertices with same coordinates
1038 already exist. If any such are found, give up. */
1039 node = tp->fringe.nodes;
1041 if (((fc & FC_NEW_LEFT) && fived_equal(node->fived, left->fived))
1042 || ((fc & FC_NEW_RIGHT) && fived_equal(node->fived, right->fived))
1043 || ((fc & FC_NEW_FAR) && fived_equal(node->fived, far->fived))) {
1044 /* Better luck next time. */
1045 if (fc & FC_NEW_LEFT)
1046 delete_vertex(mi, left, tp);
1047 if (fc & FC_NEW_RIGHT)
1048 delete_vertex(mi, right, tp);
1049 if (fc & FC_NEW_FAR)
1050 delete_vertex(mi, far, tp);
1054 } while (node != tp->fringe.nodes);
1057 if (!(fc & FC_CUT_THIS)) {
1058 if (side == S_LEFT) {
1059 vertex->next = right;
1060 right->prev = vertex;
1062 vertex->prev = left;
1063 left->next = vertex;
1066 if (!(fc & FC_CUT_FAR)) {
1067 if (!(fc & FC_CUT_LEFT)) {
1071 if (!(fc & FC_CUT_RIGHT)) {
1076 draw_tile(vertex, right, far, left, vtype, mi);
1078 /* Delete vertices that are no longer on the fringe. Check the others. */
1079 if (fc & FC_CUT_THIS) {
1080 tp->fringe.nodes = far;
1081 delete_vertex(mi, vertex, tp);
1083 add_vtype(vertex, side, vtype);
1084 check_vertex(mi, vertex, tp);
1085 tp->fringe.nodes = vertex;
1087 if (fc & FC_CUT_FAR)
1088 delete_vertex(mi, far, tp);
1090 add_vtype(far, fc & FC_CUT_RIGHT ? S_LEFT : S_RIGHT, ftype);
1091 check_vertex(mi, far, tp);
1093 if (fc & FC_CUT_LEFT)
1094 delete_vertex(mi, left, tp);
1096 add_vtype(left, fc & FC_CUT_FAR ? S_LEFT : S_RIGHT, ltype);
1097 check_vertex(mi, left, tp);
1099 if (fc & FC_CUT_RIGHT)
1100 delete_vertex(mi, right, tp);
1102 add_vtype(right, fc & FC_CUT_FAR ? S_RIGHT : S_LEFT, rtype);
1103 check_vertex(mi, right, tp);
1110 * Add a forced tile to a given forced vertex. Basically an easy job,
1111 * since we know what to add. But it might fail if adding the tile
1112 * would cause some untiled area to become enclosed. There is also another
1113 * more exotic culprit: we might have a dislocation. Fortunately, they
1114 * are very rare (the PRL article reported that perfect tilings of over
1115 * 2^50 tiles had been generated). There is a version of the algorithm
1116 * that doesn't produce dislocations, but it's a lot hairier than the
1117 * simpler version I used.
1120 add_forced_tile(ModeInfo * mi, forced_node_c * node)
1122 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1124 vertex_type_c vtype;
1125 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1128 if (node->forced_sides == (S_LEFT | S_RIGHT))
1129 side = NRAND(2) ? S_LEFT : S_RIGHT;
1131 side = node->forced_sides;
1132 n = match_rules(node->vertex, hits, True);
1133 n = find_completions(node->vertex, hits, n, side, &vtype /*, True */ );
1136 if (MI_IS_VERBOSE(mi)) {
1137 (void) fprintf(stderr, "Weirdness in add_forced_tile()\n");
1138 (void) fprintf(stderr, "n = %d\n", n);
1141 return add_tile(mi, node->vertex, side, vtype);
1146 * Whether the addition of a tile of vtype on the given side of vertex
1147 * would conform to the rules. The efficient way to do this would be
1148 * to add the new tile and then use the same type of search as in
1149 * match_rules. However, this function is not a performance
1150 * bottleneck (only needed for random tile additions, which are
1151 * relatively infrequent), so I will settle for a simpler implementation.
1154 legal_move(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
1156 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1157 vertex_type_c legal_vt[MAX_COMPL];
1158 int n_hits, n_legal, i;
1160 n_hits = match_rules(vertex, hits, False);
1161 n_legal = find_completions(vertex, hits, n_hits, side, legal_vt /*, False */ );
1162 for (i = 0; i < n_legal; i++)
1163 if (legal_vt[i] == vtype)
1170 * Add a randomly chosen tile to a given vertex. This requires more checking
1171 * as we must make sure the new tile conforms to the vertex rules at every
1172 * vertex it touches. */
1174 add_random_tile(fringe_node_c * vertex, ModeInfo * mi)
1176 fringe_node_c *right, *left, *far;
1177 int i, j, n, n_hits, n_good;
1178 unsigned side, fc, no_good, s;
1179 vertex_type_c vtypes[MAX_COMPL];
1180 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1181 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1183 if (MI_NPIXELS(mi) > 2) {
1184 tp->thick_color = NRAND(MI_NPIXELS(mi));
1185 /* Insure good contrast */
1186 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
1187 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
1189 tp->thick_color = tp->thin_color = MI_WHITE_PIXEL(mi);
1190 n_hits = match_rules(vertex, hits, False);
1191 side = NRAND(2) ? S_LEFT : S_RIGHT;
1192 n = find_completions(vertex, hits, n_hits, side, vtypes /*, False */ );
1193 /* One answer would mean a forced tile. */
1196 if (MI_IS_VERBOSE(mi)) {
1197 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1198 (void) fprintf(stderr, "n = %d\n", n);
1203 for (i = 0; i < n; i++) {
1204 fc = fringe_changes(mi, vertex, side, vtypes[i], &right, &far, &left);
1207 if (MI_IS_VERBOSE(mi)) {
1208 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1209 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1213 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_LEFT)) ? S_RIGHT : S_LEFT);
1214 if (!legal_move(right, s, VT_RIGHT(vtypes[i]))) {
1215 no_good |= (1 << i);
1221 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_RIGHT)) ? S_LEFT : S_RIGHT);
1222 if (!legal_move(left, s, VT_LEFT(vtypes[i]))) {
1223 no_good |= (1 << i);
1229 s = ((fc & FC_CUT_LEFT) ? S_RIGHT : S_LEFT);
1230 if (!legal_move(far, s, VT_FAR(vtypes[i]))) {
1231 no_good |= (1 << i);
1238 if (MI_IS_VERBOSE(mi)) {
1239 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1240 (void) fprintf(stderr, "n_good = %d\n", n_good);
1244 for (i = j = 0; i <= n; i++, j++)
1245 while (no_good & (1 << j))
1248 if (!add_tile(mi, vertex, side, vtypes[j - 1])) {
1250 if (MI_IS_VERBOSE(mi)) {
1251 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1257 /* One step of the growth algorithm. */
1259 draw_penrose(ModeInfo * mi)
1265 if (tilings == NULL)
1267 tp = &tilings[MI_SCREEN(mi)];
1268 if (tp->fringe.nodes == NULL)
1271 MI_IS_DRAWN(mi) = True;
1272 p = tp->forced.first;
1273 if (tp->busyLoop > 0) {
1277 if (tp->done || tp->failures >= 100) {
1281 /* Check for the initial "2-gon". */
1282 if (tp->fringe.nodes->prev == tp->fringe.nodes->next) {
1283 vertex_type_c vtype = (unsigned char) (VT_TOTAL_MASK & LRAND());
1287 if (!add_tile(mi, tp->fringe.nodes, S_LEFT, vtype))
1291 /* No visible nodes left. */
1292 if (tp->fringe.n_nodes == 0) {
1294 tp->busyLoop = COMPLETION; /* Just finished drawing */
1297 if (tp->forced.n_visible > 0 && tp->failures < 10) {
1298 n = NRAND(tp->forced.n_visible);
1300 while (p->vertex->off_screen)
1307 } else if (tp->forced.n_nodes > 0) {
1308 n = NRAND(tp->forced.n_nodes);
1312 fringe_node_c *fringe_p = tp->fringe.nodes;
1314 n = NRAND(tp->fringe.n_nodes);
1318 fringe_p = fringe_p->next;
1319 } while (fringe_p->off_screen);
1320 add_random_tile(fringe_p, mi);
1324 if (add_forced_tile(mi, p))
1332 reshape_penrose(ModeInfo * mi, int width, int height)
1334 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1336 tp->height = height;
1339 /* Total clean-up. */
1341 release_penrose(ModeInfo * mi)
1343 if (tilings != NULL) {
1346 for (screen = 0; screen < MI_NUM_SCREENS(mi); screen++)
1347 free_penrose(&tilings[screen]);
1348 (void) free((void *) tilings);
1349 tilings = (tiling_c *) NULL;
1353 XSCREENSAVER_MODULE ("Penrose", penrose)
1355 #endif /* MODE_penrose */