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" \
90 "*ignoreRotation: True \n" \
92 # define release_penrose 0
93 # define penrose_handle_event 0
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 {"-ammann", ".penrose.ammann", XrmoptionNoArg, "on"},
108 {"+ammann", ".penrose.ammann", XrmoptionNoArg, "off"}
110 static argtype vars[] =
112 {&ammann, "ammann", "Ammann", DEF_AMMANN, t_Bool}
114 static OptionStruct desc[] =
116 {"-/+ammann", "turn on/off Ammann lines"}
119 ENTRYPOINT 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", (char *) NULL,
125 "init_penrose", "init_penrose", "free_penrose", &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 /* The tiles are listed in counterclockwise order. */
261 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
265 static vertex_rule_c vertex_rules[N_VERTEX_RULES] =
268 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2}, 5},
270 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0}, 5},
272 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THIN | 0}, 4},
274 {VT_THICK | 2, VT_THICK | 2, VT_THIN | 1, VT_THIN | 3, VT_THICK | 2,
275 VT_THIN | 1, VT_THIN | 3}, 7},
277 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2,
278 VT_THIN | 1, VT_THIN | 3}, 6},
280 {VT_THICK | 1, VT_THICK | 3, VT_THIN | 2}, 3},
282 {VT_THICK | 0, VT_THIN | 0, VT_THIN | 0}, 3},
284 {VT_THICK | 2, VT_THIN | 1, VT_THICK | 3, VT_THICK | 1, VT_THIN | 3}, 5}
288 /* Match information returned by match_rules. */
295 /* Occasionally floating point coordinates are needed. */
301 /* All angles are measured in multiples of 36 degrees. */
304 static angle_c vtype_angles[] =
305 {4, 1, 4, 1, 2, 3, 2, 3};
307 #define vtype_angle( v) (vtype_angles[ v])
310 /* This is the data related to the tiling of one screen. */
314 int edge_length, line_width;
316 forced_pool_c forced;
318 unsigned long thick_color, thin_color;
322 fcoord_c fived_table[5];
325 static tiling_c *tilings = (tiling_c *) NULL;
329 /* Direction angle of an edge. */
331 vertex_dir(ModeInfo * mi, fringe_node_c * vertex, unsigned side)
333 tiling_c *tp = &tilings[MI_SCREEN(mi)];
335 (side == S_LEFT ? vertex->next : vertex->prev);
338 for (i = 0; i < 5; i++)
339 switch (v2->fived[i] - vertex->fived[i]) {
343 return (2 * i + 5) % 10;
346 if (MI_IS_VERBOSE(mi)) {
347 (void) fprintf(stderr,
348 "Weirdness in vertex_dir (this has been reported)\n");
349 for (i = 0; i < 5; i++)
350 (void) fprintf(stderr, "v2->fived[%d]=%d, vertex->fived[%d]=%d\n",
351 i, v2->fived[i], i, vertex->fived[i]);
353 tp->busyLoop = CELEBRATE;
358 /* Move one step to a given direction. */
360 add_unit_vec(angle_c dir, int *fived)
362 static const int dir2i[] = {0, 3, 1, 4, 2};
366 fived[dir2i[dir % 5]] += (dir % 2 ? -1 : 1);
370 /* For comparing coordinates. */
371 #define fived_equal( f1, f2) (!memcmp( (f1), (f2), 5 * sizeof( int)))
375 * This computes screen coordinates from 5D representation. Note that X
376 * uses left-handed coordinates (y increases downwards).
379 fived_to_loc(int fived[], tiling_c * tp, XPoint *pt)
381 float fifth = 8 * atan(1.) / 5;
384 register fcoord_c offset;
389 if (tp->fived_table[0].x == .0)
390 for (i = 0; i < 5; i++) {
391 tp->fived_table[i].x = cos(fifth * i);
392 tp->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 * tp->fived_table[i].x;
397 offset.y -= r * tp->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(ModeInfo * mi)
408 tiling_c * tp = &tilings[MI_SCREEN(mi)];
409 register fringe_node_c *fp1, *fp2;
410 register forced_node_c *lp1, *lp2;
412 if (tp->fringe.nodes == NULL)
414 fp1 = tp->fringe.nodes;
418 (void) free((void *) fp2);
419 } while (fp1 != tp->fringe.nodes);
420 tp->fringe.nodes = (fringe_node_c *) NULL;
421 for (lp1 = tp->forced.first; lp1 != 0;) {
424 (void) free((void *) lp2);
426 tp->forced.first = 0;
430 /* Called to init the mode. */
432 init_penrose(ModeInfo * mi)
438 MI_INIT (mi, tilings);
439 tp = &tilings[MI_SCREEN(mi)];
441 #if 0 /* if you do this, then the -ammann and -no-ammann options don't work.
443 if (MI_IS_FULLRANDOM(mi))
444 tp->ammann = (Bool) (LRAND() & 1);
452 tp->width = MI_WIDTH(mi);
453 tp->height = MI_HEIGHT(mi);
454 if (MI_NPIXELS(mi) > 2) {
455 tp->thick_color = NRAND(MI_NPIXELS(mi));
456 /* Insure good contrast */
457 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
458 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
463 if (MI_WIDTH(mi) > 2560) { /* Retina displays */
469 tp->edge_length = NRAND(MIN(-size, MAX(MINSIZE,
470 MIN(tp->width, tp->height) / 2)) - MINSIZE + 1) + MINSIZE;
471 else if (size < MINSIZE) {
473 tp->edge_length = MAX(MINSIZE, MIN(tp->width, tp->height) / 2);
475 tp->edge_length = MINSIZE;
477 tp->edge_length = MIN(size, MAX(MINSIZE,
478 MIN(tp->width, tp->height) / 2));
479 tp->origin.x = (tp->width / 2 + NRAND(tp->width)) / 2;
480 tp->origin.y = (tp->height / 2 + NRAND(tp->height)) / 2;
481 tp->fringe.n_nodes = 2;
482 if (tp->fringe.nodes != NULL)
484 if (tp->fringe.nodes != NULL || tp->forced.first != 0) {
485 if (MI_IS_VERBOSE(mi)) {
486 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
487 (void) fprintf(stderr, "tp->fringe.nodes = NULL && tp->forced.first = 0\n");
489 free_penrose(mi); /* Try again */
492 tp->forced.n_nodes = tp->forced.n_visible = 0;
493 if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
498 if (MI_IS_VERBOSE(mi)) {
499 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
500 (void) fprintf(stderr, "fp = 0\n");
502 if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
509 fp->rule_mask = (1 << N_VERTEX_RULES) - 1;
511 if ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
516 if (MI_IS_VERBOSE(mi)) {
517 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
518 (void) fprintf(stderr, "fp->next = 0\n");
520 if ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
527 fp->loc = tp->origin;
528 fp->off_screen = False;
529 for (i = 0; i < 5; i++)
534 fp->next->prev = fp->next->next = fp;
537 fp->fived[i] = 2 * NRAND(2) - 1;
538 fived_to_loc(fp->fived, tp, &(fp->loc));
539 /* That's it! We have created our first edge. */
545 * This attempts to match the configuration of vertex with the vertex
546 * rules. The return value is a total match count. If matches is
547 * non-null, it will be used to store information about the matches
548 * and must be large enough to contain it. To play it absolutely
549 * safe, allocate room for MAX_TILES_PER_VERTEX * N_VERTEX_RULES
550 * entries when searching all matches. The rule mask of vertex will
551 * be applied and rules masked out will not be searched. Only strict
552 * subsequences match. If first_only is true, the search stops when
553 * the first match is found. Otherwise all matches will be found and
554 * the rule_mask of vertex will be updated, which also happens in
555 * single-match mode if no match is found.
558 match_rules(fringe_node_c * vertex, rule_match_c * matches, int first_only)
560 /* I will assume that I can fit all the relevant bits in vertex->tiles
561 into one unsigned long. With 3 bits per element and at most 7
562 elements this means 21 bits, which should leave plenty of room.
563 After packing the bits the rest is just integer comparisons and
564 some bit shuffling. This is essentially Rabin-Karp without
565 congruence arithmetic. */
567 int hits = 0, good_rules[N_VERTEX_RULES], n_good = 0;
569 vertex_hash = 0, lower_bits_mask = ~(VT_TOTAL_MASK << VT_BITS * (vertex->n_tiles - 1));
570 unsigned new_rule_mask = 0;
572 for (i = 0; i < N_VERTEX_RULES; i++)
573 if (vertex->n_tiles >= vertex_rules[i].n_tiles)
574 vertex->rule_mask &= ~(1 << i);
575 else if (vertex->rule_mask & 1 << i)
576 good_rules[n_good++] = i;
577 for (i = 0; i < vertex->n_tiles; i++)
578 vertex_hash |= (unsigned long) vertex->tiles[i] << (VT_BITS * i);
580 for (j = 0; j < n_good; j++) {
581 unsigned long rule_hash = 0;
582 vertex_rule_c *vr = vertex_rules + good_rules[j];
584 for (i = 0; i < vertex->n_tiles; i++)
585 rule_hash |= (unsigned long) vr->tiles[i] << (VT_BITS * i);
586 if (rule_hash == vertex_hash) {
588 matches[hits].rule = good_rules[j];
589 matches[hits].pos = 0;
595 new_rule_mask |= 1 << good_rules[j];
597 for (i = vr->n_tiles - 1; i > 0; i--) {
598 rule_hash = vr->tiles[i] | (rule_hash & lower_bits_mask) << VT_BITS;
599 if (vertex_hash == rule_hash) {
601 matches[hits].rule = good_rules[j];
602 matches[hits].pos = i;
608 new_rule_mask |= 1 << good_rules[j];
612 vertex->rule_mask = new_rule_mask;
618 * find_completions finds the possible ways to add a tile to a vertex.
619 * The return values is the number of such possibilities. You must
620 * first call match_rules to produce matches and n_matches. sides
621 * specifies which side of the vertex to extend and can be S_LEFT or
622 * S_RIGHT. If results is non-null, it should point to an array large
623 * enough to contain the results, which will be stored there.
624 * MAX_COMPL elements will always suffice. If first_only is true we
625 * stop as soon as we find one possibility (NOT USED).
630 find_completions(fringe_node_c * vertex, rule_match_c * matches, int n_matches,
631 unsigned side, vertex_type_c * results /*, int first_only */ )
635 vertex_type_c buf[MAX_COMPL];
641 for (i = 0; i < n_matches; i++) {
642 vertex_rule_c *rule = vertex_rules + matches[i].rule;
643 int pos = (matches[i].pos
644 + (side == S_RIGHT ? vertex->n_tiles : rule->n_tiles - 1))
646 vertex_type_c vtype = rule->tiles[pos];
649 for (j = 0; j < n_res; j++)
650 if (vtype == results[j]) {
655 results[n_res++] = vtype;
662 * Draw a tile on the display. Vertices must be given in a
663 * counterclockwise order. vtype is the vertex type of v1 (and thus
664 * also gives the tile type).
667 draw_tile(fringe_node_c * v1, fringe_node_c * v2,
668 fringe_node_c * v3, fringe_node_c * v4,
669 vertex_type_c vtype, ModeInfo * mi)
671 Display *display = MI_DISPLAY(mi);
672 Window window = MI_WINDOW(mi);
674 tiling_c *tp = &tilings[MI_SCREEN(mi)];
676 vertex_type_c corner = vtype & VT_CORNER_MASK;
678 if (v1->off_screen && v2->off_screen && v3->off_screen && v4->off_screen)
680 pts[corner] = v1->loc;
681 pts[VT_RIGHT(corner)] = v2->loc;
682 pts[VT_FAR(corner)] = v3->loc;
683 pts[VT_LEFT(corner)] = v4->loc;
685 if (MI_NPIXELS(mi) > 2) {
686 if ((vtype & VT_TYPE_MASK) == VT_THICK)
687 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
689 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
691 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
692 XFillPolygon(display, window, gc, pts, 4, Convex, CoordModeOrigin);
693 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
694 XSetLineAttributes(display, gc, tp->line_width,
695 LineSolid, CapNotLast, JoinMiter);
696 XDrawLines(display, window, gc, pts, 5, CoordModeOrigin);
699 /* Draw some Ammann lines for debugging purposes. This will probably
700 fail miserably on a b&w display. */
702 if ((vtype & VT_TYPE_MASK) == VT_THICK) {
704 if (tp->ammann_r == .0) {
705 float pi10 = 2 * atan(1.) / 5;
707 tp->ammann_r = 1 - sin(pi10) / (2 * sin(3 * pi10));
709 if (MI_NPIXELS(mi) > 2)
710 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
712 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
713 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
715 XDrawLine(display, window, gc,
716 (int) (tp->ammann_r * pts[3].x + (1 - tp->ammann_r) * pts[0].x + .5),
717 (int) (tp->ammann_r * pts[3].y + (1 - tp->ammann_r) * pts[0].y + .5),
718 (int) (tp->ammann_r * pts[1].x + (1 - tp->ammann_r) * pts[0].x + .5),
719 (int) (tp->ammann_r * pts[1].y + (1 - tp->ammann_r) * pts[0].y + .5));
720 if (MI_NPIXELS(mi) <= 2)
721 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
723 if (MI_NPIXELS(mi) > 2)
724 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
726 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
727 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
729 XDrawLine(display, window, gc,
730 (int) ((pts[3].x + pts[2].x) / 2 + .5),
731 (int) ((pts[3].y + pts[2].y) / 2 + .5),
732 (int) ((pts[1].x + pts[2].x) / 2 + .5),
733 (int) ((pts[1].y + pts[2].y) / 2 + .5));
734 if (MI_NPIXELS(mi) <= 2)
735 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
741 * Update the status of this vertex on the forced vertex queue. If
742 * the vertex has become untileable set tp->done. This is supposed
743 * to detect dislocations -- never call this routine with a completely
746 * Check for untileable vertices in check_vertex and stop tiling as
747 * soon as one finds one. I don't know if it is possible to run out
748 * of forced vertices while untileable vertices exist (or will
749 * cavities inevitably appear). If this can happen, add_random_tile
750 * might get called with an untileable vertex, causing ( n <= 1).
751 * (This is what the tp->done checks for).
753 * A delayLoop celebrates the dislocation.
756 check_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
758 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
759 int n_hits = match_rules(vertex, hits, False);
760 unsigned forced_sides = 0;
762 if (vertex->rule_mask == 0) {
764 if (MI_IS_VERBOSE(mi)) {
765 (void) fprintf(stderr, "Dislocation occurred!\n");
767 tp->busyLoop = CELEBRATE; /* Should be able to recover */
769 if (1 == find_completions(vertex, hits, n_hits, S_LEFT, 0 /*, False */ ))
770 forced_sides |= S_LEFT;
771 if (1 == find_completions(vertex, hits, n_hits, S_RIGHT, 0 /*, False */ ))
772 forced_sides |= S_RIGHT;
773 if (forced_sides == 0) {
774 if (vertex->list_ptr != 0) {
775 forced_node_c *node = *vertex->list_ptr;
777 *vertex->list_ptr = node->next;
779 node->next->vertex->list_ptr = vertex->list_ptr;
780 (void) free((void *) node);
781 tp->forced.n_nodes--;
782 if (!vertex->off_screen)
783 tp->forced.n_visible--;
784 vertex->list_ptr = 0;
789 if (vertex->list_ptr == 0) {
790 if ((node = ALLOC_NODE(forced_node_c)) == NULL)
792 node->vertex = vertex;
793 node->next = tp->forced.first;
794 if (tp->forced.first != 0)
795 tp->forced.first->vertex->list_ptr = &(node->next);
796 tp->forced.first = node;
797 vertex->list_ptr = &(tp->forced.first);
798 tp->forced.n_nodes++;
799 if (!vertex->off_screen)
800 tp->forced.n_visible++;
802 node = *vertex->list_ptr;
803 node->forced_sides = forced_sides;
809 * Delete this vertex. If the vertex is a member of the forced vertex queue,
810 * also remove that entry. We assume that the vertex is no longer
811 * connected to the fringe. Note that tp->fringe.nodes must not point to
812 * the vertex being deleted.
815 delete_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
817 if (tp->fringe.nodes == vertex) {
819 if (MI_IS_VERBOSE(mi)) {
820 (void) fprintf(stderr, "Weirdness in delete_penrose()\n");
821 (void) fprintf(stderr, "tp->fringe.nodes == vertex\n");
823 tp->busyLoop = CELEBRATE;
825 if (vertex->list_ptr != 0) {
826 forced_node_c *node = *vertex->list_ptr;
828 *vertex->list_ptr = node->next;
830 node->next->vertex->list_ptr = vertex->list_ptr;
831 (void) free((void *) node);
832 tp->forced.n_nodes--;
833 if (!vertex->off_screen)
834 tp->forced.n_visible--;
836 if (!vertex->off_screen)
837 tp->fringe.n_nodes--;
838 (void) free((void *) vertex);
843 * Check whether the addition of a tile of type vtype would completely fill
844 * the space available at vertex.
847 fills_vertex(ModeInfo * mi, vertex_type_c vtype, fringe_node_c * vertex)
850 (vertex_dir(mi, vertex, S_LEFT) - vertex_dir(mi, vertex, S_RIGHT)
851 - vtype_angle(vtype)) % 10 == 0;
856 * If you were to add a tile of type vtype to a specified side of
857 * vertex, fringe_changes tells you which other vertices it would
858 * attach to. The addresses of these vertices will be stored in the
859 * last three arguments. Null is stored if the corresponding vertex
860 * would need to be allocated.
862 * The function also analyzes which vertices would be swallowed by the tiling
863 * and thus cut off from the fringe. The result is returned as a bit pattern.
865 #define FC_BAG 1 /* Total enclosure. Should never occur. */
866 #define FC_NEW_RIGHT 2
868 #define FC_NEW_LEFT 8
869 #define FC_NEW_MASK 0xe
870 #define FC_CUT_THIS 0x10
871 #define FC_CUT_RIGHT 0x20
872 #define FC_CUT_FAR 0x40
873 #define FC_CUT_LEFT 0x80
874 #define FC_CUT_MASK 0xf0
875 #define FC_TOTAL_MASK 0xff
878 fringe_changes(ModeInfo * mi, fringe_node_c * vertex,
879 unsigned side, vertex_type_c vtype,
880 fringe_node_c ** right, fringe_node_c ** far,
881 fringe_node_c ** left)
883 fringe_node_c *v, *f = (fringe_node_c *) NULL;
884 unsigned result = FC_NEW_FAR; /* We clear this later if necessary. */
888 if (fills_vertex(mi, vtype, vertex)) {
889 result |= FC_CUT_THIS;
890 } else if (side == S_LEFT) {
891 result |= FC_NEW_RIGHT;
895 result |= FC_NEW_LEFT;
900 if (!(result & FC_NEW_LEFT)) {
904 if (fills_vertex(mi, VT_LEFT(vtype), v)) {
905 result = (result & ~FC_NEW_FAR) | FC_CUT_LEFT;
911 if (!(result & FC_NEW_RIGHT)) {
915 if (fills_vertex(mi, VT_RIGHT(vtype), v)) {
916 result = (result & ~FC_NEW_FAR) | FC_CUT_RIGHT;
922 if (!(result & FC_NEW_FAR)
923 && fills_vertex(mi, VT_FAR(vtype), f)) {
924 result |= FC_CUT_FAR;
925 result &= (~FC_NEW_LEFT & ~FC_NEW_RIGHT);
926 if (right && (result & FC_CUT_LEFT))
928 if (left && (result & FC_CUT_RIGHT))
931 if (((result & FC_CUT_LEFT) && (result & FC_CUT_RIGHT))
932 || ((result & FC_CUT_THIS) && (result & FC_CUT_FAR)))
938 /* A couple of lesser helper functions for add_tile. */
940 add_vtype(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
943 vertex->tiles[vertex->n_tiles++] = vtype;
947 for (i = vertex->n_tiles; i > 0; i--)
948 vertex->tiles[i] = vertex->tiles[i - 1];
949 vertex->tiles[0] = vtype;
954 static fringe_node_c *
955 alloc_vertex(ModeInfo * mi, angle_c dir, fringe_node_c * from, tiling_c * tp)
959 if ((v = ALLOC_NODE(fringe_node_c)) == NULL) {
961 if (MI_IS_VERBOSE(mi)) {
962 (void) fprintf(stderr, "No memory in alloc_vertex()\n");
964 tp->busyLoop = CELEBRATE;
968 add_unit_vec(dir, v->fived);
969 fived_to_loc(v->fived, tp, &(v->loc));
970 if (v->loc.x < 0 || v->loc.y < 0
971 || v->loc.x >= tp->width || v->loc.y >= tp->height) {
974 if (ww < 200) ww = 200; /* tiny window */
975 if (hh < 200) hh = 200;
976 v->off_screen = True;
977 if (v->loc.x < -ww || v->loc.y < -hh ||
978 v->loc.x >= 2 * ww || v->loc.y >= 2 * hh)
981 v->off_screen = False;
982 tp->fringe.n_nodes++;
985 v->rule_mask = (1 << N_VERTEX_RULES) - 1;
991 * Add a tile described by vtype to the side of vertex. This must be
992 * allowed by the rules -- we do not check it here. New vertices are
993 * allocated as necessary. The fringe and the forced vertex pool are updated.
994 * The new tile is drawn on the display.
996 * One thing we do check here is whether the new tile causes an untiled
997 * area to become enclosed by the tiling. If this would happen, the tile
998 * is not added. The return value is true iff a tile was added.
1001 add_tile(ModeInfo * mi,
1002 fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
1004 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1007 *left = (fringe_node_c *) NULL,
1008 *right = (fringe_node_c *) NULL,
1009 *far = (fringe_node_c *) NULL,
1011 unsigned fc = fringe_changes(mi, vertex, side, vtype, &right, &far, &left);
1014 ltype = VT_LEFT(vtype),
1015 rtype = VT_RIGHT(vtype),
1016 ftype = VT_FAR(vtype);
1018 /* By our conventions vertex->next lies to the left of vertex and
1019 vertex->prev to the right. */
1021 /* This should never occur. */
1024 if (MI_IS_VERBOSE(mi)) {
1025 (void) fprintf(stderr, "Weirdness in add_tile()\n");
1026 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1029 if (side == S_LEFT) {
1031 if ((right = alloc_vertex(mi, vertex_dir(mi, vertex, S_LEFT) -
1032 vtype_angle(vtype), vertex, tp)) == NULL)
1035 if ((far = alloc_vertex(mi, vertex_dir(mi, left, S_RIGHT) +
1036 vtype_angle(ltype), left, tp)) == NULL)
1040 if ((left = alloc_vertex(mi, vertex_dir(mi, vertex, S_RIGHT) +
1041 vtype_angle(vtype), vertex, tp)) == NULL)
1044 if ((far = alloc_vertex(mi, vertex_dir(mi, right, S_LEFT) -
1045 vtype_angle(rtype), right, tp)) == NULL)
1049 /* Having allocated the new vertices, but before joining them with
1050 the rest of the fringe, check if vertices with same coordinates
1051 already exist. If any such are found, give up. */
1052 node = tp->fringe.nodes;
1054 if (((fc & FC_NEW_LEFT) && fived_equal(node->fived, left->fived))
1055 || ((fc & FC_NEW_RIGHT) && fived_equal(node->fived, right->fived))
1056 || ((fc & FC_NEW_FAR) && fived_equal(node->fived, far->fived))) {
1057 /* Better luck next time. */
1058 if (fc & FC_NEW_LEFT)
1059 delete_vertex(mi, left, tp);
1060 if (fc & FC_NEW_RIGHT)
1061 delete_vertex(mi, right, tp);
1062 if (fc & FC_NEW_FAR)
1063 delete_vertex(mi, far, tp);
1067 } while (node != tp->fringe.nodes);
1070 if (!(fc & FC_CUT_THIS)) {
1071 if (side == S_LEFT) {
1072 vertex->next = right;
1073 right->prev = vertex;
1075 vertex->prev = left;
1076 left->next = vertex;
1079 if (!(fc & FC_CUT_FAR)) {
1080 if (!(fc & FC_CUT_LEFT)) {
1084 if (!(fc & FC_CUT_RIGHT)) {
1089 draw_tile(vertex, right, far, left, vtype, mi);
1091 /* Delete vertices that are no longer on the fringe. Check the others. */
1092 if (fc & FC_CUT_THIS) {
1093 tp->fringe.nodes = far;
1094 delete_vertex(mi, vertex, tp);
1096 add_vtype(vertex, side, vtype);
1097 check_vertex(mi, vertex, tp);
1098 tp->fringe.nodes = vertex;
1100 if (fc & FC_CUT_FAR)
1101 delete_vertex(mi, far, tp);
1103 add_vtype(far, fc & FC_CUT_RIGHT ? S_LEFT : S_RIGHT, ftype);
1104 check_vertex(mi, far, tp);
1106 if (fc & FC_CUT_LEFT)
1107 delete_vertex(mi, left, tp);
1109 add_vtype(left, fc & FC_CUT_FAR ? S_LEFT : S_RIGHT, ltype);
1110 check_vertex(mi, left, tp);
1112 if (fc & FC_CUT_RIGHT)
1113 delete_vertex(mi, right, tp);
1115 add_vtype(right, fc & FC_CUT_FAR ? S_RIGHT : S_LEFT, rtype);
1116 check_vertex(mi, right, tp);
1123 * Add a forced tile to a given forced vertex. Basically an easy job,
1124 * since we know what to add. But it might fail if adding the tile
1125 * would cause some untiled area to become enclosed. There is also another
1126 * more exotic culprit: we might have a dislocation. Fortunately, they
1127 * are very rare (the PRL article reported that perfect tilings of over
1128 * 2^50 tiles had been generated). There is a version of the algorithm
1129 * that doesn't produce dislocations, but it's a lot hairier than the
1130 * simpler version I used.
1133 add_forced_tile(ModeInfo * mi, forced_node_c * node)
1135 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1137 vertex_type_c vtype = 0;
1138 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1141 if (node->forced_sides == (S_LEFT | S_RIGHT))
1142 side = NRAND(2) ? S_LEFT : S_RIGHT;
1144 side = node->forced_sides;
1145 n = match_rules(node->vertex, hits, True);
1146 n = find_completions(node->vertex, hits, n, side, &vtype /*, True */ );
1149 if (MI_IS_VERBOSE(mi)) {
1150 (void) fprintf(stderr, "Weirdness in add_forced_tile()\n");
1151 (void) fprintf(stderr, "n = %d\n", n);
1154 return add_tile(mi, node->vertex, side, vtype);
1159 * Whether the addition of a tile of vtype on the given side of vertex
1160 * would conform to the rules. The efficient way to do this would be
1161 * to add the new tile and then use the same type of search as in
1162 * match_rules. However, this function is not a performance
1163 * bottleneck (only needed for random tile additions, which are
1164 * relatively infrequent), so I will settle for a simpler implementation.
1167 legal_move(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
1169 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1170 vertex_type_c legal_vt[MAX_COMPL];
1171 int n_hits, n_legal, i;
1173 n_hits = match_rules(vertex, hits, False);
1174 n_legal = find_completions(vertex, hits, n_hits, side, legal_vt /*, False */ );
1175 for (i = 0; i < n_legal; i++)
1176 if (legal_vt[i] == vtype)
1183 * Add a randomly chosen tile to a given vertex. This requires more checking
1184 * as we must make sure the new tile conforms to the vertex rules at every
1185 * vertex it touches. */
1187 add_random_tile(fringe_node_c * vertex, ModeInfo * mi)
1189 fringe_node_c *right, *left, *far;
1190 int i, j, n, n_hits, n_good;
1191 unsigned side, fc, no_good, s;
1192 vertex_type_c vtypes[MAX_COMPL];
1193 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1194 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1196 if (MI_NPIXELS(mi) > 2) {
1197 tp->thick_color = NRAND(MI_NPIXELS(mi));
1198 /* Insure good contrast */
1199 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
1200 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
1202 tp->thick_color = tp->thin_color = MI_WHITE_PIXEL(mi);
1203 n_hits = match_rules(vertex, hits, False);
1204 side = NRAND(2) ? S_LEFT : S_RIGHT;
1205 n = find_completions(vertex, hits, n_hits, side, vtypes /*, False */ );
1206 /* One answer would mean a forced tile. */
1209 if (MI_IS_VERBOSE(mi)) {
1210 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1211 (void) fprintf(stderr, "n = %d\n", n);
1216 for (i = 0; i < n; i++) {
1217 fc = fringe_changes(mi, vertex, side, vtypes[i], &right, &far, &left);
1220 if (MI_IS_VERBOSE(mi)) {
1221 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1222 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1226 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_LEFT)) ? S_RIGHT : S_LEFT);
1227 if (!legal_move(right, s, VT_RIGHT(vtypes[i]))) {
1228 no_good |= (1 << i);
1234 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_RIGHT)) ? S_LEFT : S_RIGHT);
1235 if (!legal_move(left, s, VT_LEFT(vtypes[i]))) {
1236 no_good |= (1 << i);
1242 s = ((fc & FC_CUT_LEFT) ? S_RIGHT : S_LEFT);
1243 if (!legal_move(far, s, VT_FAR(vtypes[i]))) {
1244 no_good |= (1 << i);
1251 if (MI_IS_VERBOSE(mi)) {
1252 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1253 (void) fprintf(stderr, "n_good = %d\n", n_good);
1257 for (i = j = 0; i <= n; i++, j++)
1258 while (no_good & (1 << j))
1261 if (!add_tile(mi, vertex, side, vtypes[j - 1])) {
1263 if (MI_IS_VERBOSE(mi)) {
1264 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1270 /* One step of the growth algorithm. */
1272 draw_penrose(ModeInfo * mi)
1278 if (tilings == NULL)
1280 tp = &tilings[MI_SCREEN(mi)];
1281 if (tp->fringe.nodes == NULL)
1284 MI_IS_DRAWN(mi) = True;
1285 p = tp->forced.first;
1286 if (tp->busyLoop > 0) {
1290 if (tp->done || tp->failures >= 100) {
1294 /* Check for the initial "2-gon". */
1295 if (tp->fringe.nodes->prev == tp->fringe.nodes->next) {
1296 vertex_type_c vtype = (unsigned char) (VT_TOTAL_MASK & LRAND());
1298 if (!add_tile(mi, tp->fringe.nodes, S_LEFT, vtype))
1302 /* No visible nodes left. */
1303 if (tp->fringe.n_nodes == 0) {
1305 tp->busyLoop = COMPLETION; /* Just finished drawing */
1308 if (tp->forced.n_visible > 0 && tp->failures < 10) {
1309 n = NRAND(tp->forced.n_visible);
1311 while (p->vertex->off_screen)
1318 } else if (tp->forced.n_nodes > 0) {
1319 n = NRAND(tp->forced.n_nodes);
1323 fringe_node_c *fringe_p = tp->fringe.nodes;
1325 n = NRAND(tp->fringe.n_nodes);
1329 fringe_p = fringe_p->next;
1330 } while (fringe_p->off_screen);
1331 add_random_tile(fringe_p, mi);
1335 if (add_forced_tile(mi, p))
1343 reshape_penrose(ModeInfo * mi, int width, int height)
1345 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1347 tp->height = height;
1350 XSCREENSAVER_MODULE ("Penrose", penrose)
1352 #endif /* MODE_penrose */