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 # define refresh_penrose 0
90 # define reshape_penrose 0
91 # define penrose_handle_event 0
92 # include "xlockmore.h" /* from the xscreensaver distribution */
93 #else /* !STANDALONE */
94 # include "xlock.h" /* from the xlockmore distribution */
95 #endif /* !STANDALONE */
99 #define DEF_AMMANN "False"
103 static XrmOptionDescRec opts[] =
105 {"-ammann", ".penrose.ammann", XrmoptionNoArg, "on"},
106 {"+ammann", ".penrose.ammann", XrmoptionNoArg, "off"}
108 static argtype vars[] =
110 {&ammann, "ammann", "Ammann", DEF_AMMANN, t_Bool}
112 static OptionStruct desc[] =
114 {"-/+ammann", "turn on/off Ammann lines"}
117 ENTRYPOINT ModeSpecOpt penrose_opts =
118 {sizeof opts / sizeof opts[0], opts, sizeof vars / sizeof vars[0], vars, desc};
121 ModStruct penrose_description =
122 {"penrose", "init_penrose", "draw_penrose", "release_penrose",
123 "init_penrose", "init_penrose", (char *) NULL, &penrose_opts,
124 10000, 1, 1, -40, 64, 1.0, "",
125 "Shows Penrose's quasiperiodic tilings", 0, NULL};
130 * Annoyingly the ANSI C library people have reserved all identifiers
131 * ending with _t for future use. Hence we use _c as a suffix for
132 * typedefs (c for class, although this is not C++).
138 * In theory one could fit 10 tiles to a single vertex. However, the
139 * vertex rules only allow at most seven tiles to meet at a vertex.
142 #define CELEBRATE 31415 /* This causes a pause, an error occurred. */
143 #define COMPLETION 3141 /* This causes a pause, tiles filled up screen. */
145 #define MAX_TILES_PER_VERTEX 7
146 #define N_VERTEX_RULES 8
147 #define ALLOC_NODE(type) (type *)malloc(sizeof (type))
150 * These are used to specify directions. They can also be used in bit
151 * masks to specify a combination of directions.
158 * We do not actually maintain objects corresponding to the tiles since
159 * we do not really need them and they would only consume memory and
160 * cause additional bookkeeping. Instead we only have vertices, and
161 * each vertex lists the type of each adjacent tile as well as the
162 * position of the vertex on the tile (hereafter refered to as
163 * "corner"). These positions are numbered in counterclockwise order
164 * so that 0 is where two double arrows meet (see one of the
165 * articles). The tile type and vertex number are stored in a single
166 * integer (we use char, and even most of it remains unused).
168 * The primary use of tile objects would be draw traversal, but we do
169 * not currently do redraws at all (we just start over).
171 #define VT_CORNER_MASK 0x3
172 #define VT_TYPE_MASK 0x4
176 #define VT_TOTAL_MASK 0x7
178 typedef unsigned char vertex_type_c;
181 * These allow one to compute the types of the other corners of the tile. If
182 * you are standing at a vertex of type vt looking towards the middle of the
183 * tile, VT_LEFT( vt) is the vertex on your left etc.
185 #define VT_LEFT( vt) ((((vt) - 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
186 #define VT_RIGHT( vt) ((((vt) + 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
187 #define VT_FAR( vt) ((vt) ^ 2)
191 * Since we do not do redraws, we only store the vertices we need. These are
192 * the ones with still some empty space around them for the growth algorithm
195 * Here we use a doubly chained ring-like structure as vertices often need
196 * to be removed or inserted (they are kept in geometrical order
197 * circling the tiled area counterclockwise). The ring is refered to by
198 * a pointer to one more or less random node. When deleting nodes one
199 * must make sure that this pointer continues to refer to a valid
200 * node. A vertex count is maintained to make it easier to pick
203 typedef struct forced_node forced_node_c;
205 typedef struct fringe_node {
206 struct fringe_node *prev;
207 struct fringe_node *next;
208 /* These are numbered counterclockwise. The gap, if any, lies
209 between the last and first tiles. */
210 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
212 /* A bit mask used to indicate vertex rules that are still applicable for
213 completing this vertex. Initialize this to (1 << N_VERTEX_RULES) - 1,
214 i.e., all ones, and the rule matching functions will automatically mask
215 out rules that no longer match. */
216 unsigned char rule_mask;
217 /* If the vertex is on the forced vertex list, this points to the
218 pointer to the appropriate node in the list. To remove the
219 vertex from the list just set *list_ptr to the next node,
220 deallocate and decrement node count. */
221 struct forced_node **list_ptr;
222 /* Screen coordinates. */
224 /* We also keep track of 5D coordinates to avoid rounding errors.
225 These are in units of edge length. */
227 /* This is used to quickly check if a vertex is visible. */
228 unsigned char off_screen;
232 fringe_node_c *nodes;
233 /* This does not count off-screen nodes. */
239 * The forced vertex pool contains vertices where at least one
240 * side of the tiled region can only be extended in one way. Note
241 * that this does not necessarily mean that there would only be one
242 * applicable rule. forced_sides are specified using S_LEFT and
243 * S_RIGHT as if looking at the untiled region from the vertex.
246 fringe_node_c *vertex;
247 unsigned forced_sides;
248 struct forced_node *next;
252 forced_node_c *first;
253 int n_nodes, n_visible;
257 /* The tiles are listed in counterclockwise order. */
259 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
263 static vertex_rule_c vertex_rules[N_VERTEX_RULES] =
266 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2}, 5},
268 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0}, 5},
270 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THIN | 0}, 4},
272 {VT_THICK | 2, VT_THICK | 2, VT_THIN | 1, VT_THIN | 3, VT_THICK | 2,
273 VT_THIN | 1, VT_THIN | 3}, 7},
275 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2,
276 VT_THIN | 1, VT_THIN | 3}, 6},
278 {VT_THICK | 1, VT_THICK | 3, VT_THIN | 2}, 3},
280 {VT_THICK | 0, VT_THIN | 0, VT_THIN | 0}, 3},
282 {VT_THICK | 2, VT_THIN | 1, VT_THICK | 3, VT_THICK | 1, VT_THIN | 3}, 5}
286 /* Match information returned by match_rules. */
293 /* Occasionally floating point coordinates are needed. */
299 /* All angles are measured in multiples of 36 degrees. */
302 static angle_c vtype_angles[] =
303 {4, 1, 4, 1, 2, 3, 2, 3};
305 #define vtype_angle( v) (vtype_angles[ v])
308 /* This is the data related to the tiling of one screen. */
314 forced_pool_c forced;
316 unsigned long thick_color, thin_color;
320 fcoord_c fived_table[5];
323 static tiling_c *tilings = (tiling_c *) NULL;
327 /* Direction angle of an edge. */
329 vertex_dir(ModeInfo * mi, fringe_node_c * vertex, unsigned side)
331 tiling_c *tp = &tilings[MI_SCREEN(mi)];
333 (side == S_LEFT ? vertex->next : vertex->prev);
336 for (i = 0; i < 5; i++)
337 switch (v2->fived[i] - vertex->fived[i]) {
341 return (2 * i + 5) % 10;
344 if (MI_IS_VERBOSE(mi)) {
345 (void) fprintf(stderr,
346 "Weirdness in vertex_dir (this has been reported)\n");
347 for (i = 0; i < 5; i++)
348 (void) fprintf(stderr, "v2->fived[%d]=%d, vertex->fived[%d]=%d\n",
349 i, v2->fived[i], i, vertex->fived[i]);
351 tp->busyLoop = CELEBRATE;
356 /* Move one step to a given direction. */
358 add_unit_vec(angle_c dir, int *fived)
360 static const int dir2i[] = {0, 3, 1, 4, 2};
364 fived[dir2i[dir % 5]] += (dir % 2 ? -1 : 1);
368 /* For comparing coordinates. */
369 #define fived_equal( f1, f2) (!memcmp( (f1), (f2), 5 * sizeof( int)))
373 * This computes screen coordinates from 5D representation. Note that X
374 * uses left-handed coordinates (y increases downwards).
377 fived_to_loc(int fived[], tiling_c * tp, XPoint *pt)
379 float fifth = 8 * atan(1.) / 5;
382 register fcoord_c offset;
387 if (tp->fived_table[0].x == .0)
388 for (i = 0; i < 5; i++) {
389 tp->fived_table[i].x = cos(fifth * i);
390 tp->fived_table[i].y = sin(fifth * i);
392 for (i = 0; i < 5; i++) {
393 r = fived[i] * tp->edge_length;
394 offset.x += r * tp->fived_table[i].x;
395 offset.y -= r * tp->fived_table[i].y;
397 (*pt).x += (int) (offset.x + .5);
398 (*pt).y += (int) (offset.y + .5);
402 /* Mop up dynamic data for one screen. */
404 free_penrose(tiling_c * tp)
406 register fringe_node_c *fp1, *fp2;
407 register forced_node_c *lp1, *lp2;
409 if (tp->fringe.nodes == NULL)
411 fp1 = tp->fringe.nodes;
415 (void) free((void *) fp2);
416 } while (fp1 != tp->fringe.nodes);
417 tp->fringe.nodes = (fringe_node_c *) NULL;
418 for (lp1 = tp->forced.first; lp1 != 0;) {
421 (void) free((void *) lp2);
423 tp->forced.first = 0;
427 /* Called to init the mode. */
429 init_penrose(ModeInfo * mi)
435 if (tilings == NULL) {
436 if ((tilings = (tiling_c *) calloc(MI_NUM_SCREENS(mi),
437 sizeof (tiling_c))) == NULL)
440 tp = &tilings[MI_SCREEN(mi)];
442 #if 0 /* if you do this, then the -ammann and -no-ammann options don't work.
444 if (MI_IS_FULLRANDOM(mi))
445 tp->ammann = (Bool) (LRAND() & 1);
453 tp->width = MI_WIDTH(mi);
454 tp->height = MI_HEIGHT(mi);
455 if (MI_NPIXELS(mi) > 2) {
456 tp->thick_color = NRAND(MI_NPIXELS(mi));
457 /* Insure good contrast */
458 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
459 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
463 tp->edge_length = NRAND(MIN(-size, MAX(MINSIZE,
464 MIN(tp->width, tp->height) / 2)) - MINSIZE + 1) + MINSIZE;
465 else if (size < MINSIZE) {
467 tp->edge_length = MAX(MINSIZE, MIN(tp->width, tp->height) / 2);
469 tp->edge_length = MINSIZE;
471 tp->edge_length = MIN(size, MAX(MINSIZE,
472 MIN(tp->width, tp->height) / 2));
473 tp->origin.x = (tp->width / 2 + NRAND(tp->width)) / 2;
474 tp->origin.y = (tp->height / 2 + NRAND(tp->height)) / 2;
475 tp->fringe.n_nodes = 2;
476 if (tp->fringe.nodes != NULL)
478 if (tp->fringe.nodes != NULL || tp->forced.first != 0) {
479 if (MI_IS_VERBOSE(mi)) {
480 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
481 (void) fprintf(stderr, "tp->fringe.nodes = NULL && tp->forced.first = 0\n");
483 free_penrose(tp); /* Try again */
486 tp->forced.n_nodes = tp->forced.n_visible = 0;
487 if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
492 if (MI_IS_VERBOSE(mi)) {
493 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
494 (void) fprintf(stderr, "fp = 0\n");
496 if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
503 fp->rule_mask = (1 << N_VERTEX_RULES) - 1;
505 if ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
510 if (MI_IS_VERBOSE(mi)) {
511 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
512 (void) fprintf(stderr, "fp->next = 0\n");
514 if ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
521 fp->loc = tp->origin;
522 fp->off_screen = False;
523 for (i = 0; i < 5; i++)
528 fp->next->prev = fp->next->next = fp;
531 fp->fived[i] = 2 * NRAND(2) - 1;
532 fived_to_loc(fp->fived, tp, &(fp->loc));
533 /* That's it! We have created our first edge. */
537 * This attempts to match the configuration of vertex with the vertex
538 * rules. The return value is a total match count. If matches is
539 * non-null, it will be used to store information about the matches
540 * and must be large enough to contain it. To play it absolutely
541 * safe, allocate room for MAX_TILES_PER_VERTEX * N_VERTEX_RULES
542 * entries when searching all matches. The rule mask of vertex will
543 * be applied and rules masked out will not be searched. Only strict
544 * subsequences match. If first_only is true, the search stops when
545 * the first match is found. Otherwise all matches will be found and
546 * the rule_mask of vertex will be updated, which also happens in
547 * single-match mode if no match is found.
550 match_rules(fringe_node_c * vertex, rule_match_c * matches, int first_only)
552 /* I will assume that I can fit all the relevant bits in vertex->tiles
553 into one unsigned long. With 3 bits per element and at most 7
554 elements this means 21 bits, which should leave plenty of room.
555 After packing the bits the rest is just integer comparisons and
556 some bit shuffling. This is essentially Rabin-Karp without
557 congruence arithmetic. */
559 int hits = 0, good_rules[N_VERTEX_RULES], n_good = 0;
561 vertex_hash = 0, lower_bits_mask = ~(VT_TOTAL_MASK << VT_BITS * (vertex->n_tiles - 1));
562 unsigned new_rule_mask = 0;
564 for (i = 0; i < N_VERTEX_RULES; i++)
565 if (vertex->n_tiles >= vertex_rules[i].n_tiles)
566 vertex->rule_mask &= ~(1 << i);
567 else if (vertex->rule_mask & 1 << i)
568 good_rules[n_good++] = i;
569 for (i = 0; i < vertex->n_tiles; i++)
570 vertex_hash |= (unsigned long) vertex->tiles[i] << (VT_BITS * i);
572 for (j = 0; j < n_good; j++) {
573 unsigned long rule_hash = 0;
574 vertex_rule_c *vr = vertex_rules + good_rules[j];
576 for (i = 0; i < vertex->n_tiles; i++)
577 rule_hash |= (unsigned long) vr->tiles[i] << (VT_BITS * i);
578 if (rule_hash == vertex_hash) {
580 matches[hits].rule = good_rules[j];
581 matches[hits].pos = 0;
587 new_rule_mask |= 1 << good_rules[j];
589 for (i = vr->n_tiles - 1; i > 0; i--) {
590 rule_hash = vr->tiles[i] | (rule_hash & lower_bits_mask) << VT_BITS;
591 if (vertex_hash == rule_hash) {
593 matches[hits].rule = good_rules[j];
594 matches[hits].pos = i;
600 new_rule_mask |= 1 << good_rules[j];
604 vertex->rule_mask = new_rule_mask;
610 * find_completions finds the possible ways to add a tile to a vertex.
611 * The return values is the number of such possibilities. You must
612 * first call match_rules to produce matches and n_matches. sides
613 * specifies which side of the vertex to extend and can be S_LEFT or
614 * S_RIGHT. If results is non-null, it should point to an array large
615 * enough to contain the results, which will be stored there.
616 * MAX_COMPL elements will always suffice. If first_only is true we
617 * stop as soon as we find one possibility (NOT USED).
622 find_completions(fringe_node_c * vertex, rule_match_c * matches, int n_matches,
623 unsigned side, vertex_type_c * results /*, int first_only */ )
627 vertex_type_c buf[MAX_COMPL];
633 for (i = 0; i < n_matches; i++) {
634 vertex_rule_c *rule = vertex_rules + matches[i].rule;
635 int pos = (matches[i].pos
636 + (side == S_RIGHT ? vertex->n_tiles : rule->n_tiles - 1))
638 vertex_type_c vtype = rule->tiles[pos];
641 for (j = 0; j < n_res; j++)
642 if (vtype == results[j]) {
647 results[n_res++] = vtype;
654 * Draw a tile on the display. Vertices must be given in a
655 * counterclockwise order. vtype is the vertex type of v1 (and thus
656 * also gives the tile type).
659 draw_tile(fringe_node_c * v1, fringe_node_c * v2,
660 fringe_node_c * v3, fringe_node_c * v4,
661 vertex_type_c vtype, ModeInfo * mi)
663 Display *display = MI_DISPLAY(mi);
664 Window window = MI_WINDOW(mi);
666 tiling_c *tp = &tilings[MI_SCREEN(mi)];
668 vertex_type_c corner = vtype & VT_CORNER_MASK;
670 if (v1->off_screen && v2->off_screen && v3->off_screen && v4->off_screen)
672 pts[corner] = v1->loc;
673 pts[VT_RIGHT(corner)] = v2->loc;
674 pts[VT_FAR(corner)] = v3->loc;
675 pts[VT_LEFT(corner)] = v4->loc;
677 if (MI_NPIXELS(mi) > 2) {
678 if ((vtype & VT_TYPE_MASK) == VT_THICK)
679 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
681 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
683 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
684 XFillPolygon(display, window, gc, pts, 4, Convex, CoordModeOrigin);
685 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
686 XDrawLines(display, window, gc, pts, 5, CoordModeOrigin);
689 /* Draw some Ammann lines for debugging purposes. This will probably
690 fail miserably on a b&w display. */
692 if ((vtype & VT_TYPE_MASK) == VT_THICK) {
694 if (tp->ammann_r == .0) {
695 float pi10 = 2 * atan(1.) / 5;
697 tp->ammann_r = 1 - sin(pi10) / (2 * sin(3 * pi10));
699 if (MI_NPIXELS(mi) > 2)
700 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
702 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
703 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
705 XDrawLine(display, window, gc,
706 (int) (tp->ammann_r * pts[3].x + (1 - tp->ammann_r) * pts[0].x + .5),
707 (int) (tp->ammann_r * pts[3].y + (1 - tp->ammann_r) * pts[0].y + .5),
708 (int) (tp->ammann_r * pts[1].x + (1 - tp->ammann_r) * pts[0].x + .5),
709 (int) (tp->ammann_r * pts[1].y + (1 - tp->ammann_r) * pts[0].y + .5));
710 if (MI_NPIXELS(mi) <= 2)
711 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
713 if (MI_NPIXELS(mi) > 2)
714 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
716 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
717 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
719 XDrawLine(display, window, gc,
720 (int) ((pts[3].x + pts[2].x) / 2 + .5),
721 (int) ((pts[3].y + pts[2].y) / 2 + .5),
722 (int) ((pts[1].x + pts[2].x) / 2 + .5),
723 (int) ((pts[1].y + pts[2].y) / 2 + .5));
724 if (MI_NPIXELS(mi) <= 2)
725 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
731 * Update the status of this vertex on the forced vertex queue. If
732 * the vertex has become untileable set tp->done. This is supposed
733 * to detect dislocations -- never call this routine with a completely
736 * Check for untileable vertices in check_vertex and stop tiling as
737 * soon as one finds one. I don't know if it is possible to run out
738 * of forced vertices while untileable vertices exist (or will
739 * cavities inevitably appear). If this can happen, add_random_tile
740 * might get called with an untileable vertex, causing ( n <= 1).
741 * (This is what the tp->done checks for).
743 * A delayLoop celebrates the dislocation.
746 check_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
748 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
749 int n_hits = match_rules(vertex, hits, False);
750 unsigned forced_sides = 0;
752 if (vertex->rule_mask == 0) {
754 if (MI_IS_VERBOSE(mi)) {
755 (void) fprintf(stderr, "Dislocation occurred!\n");
757 tp->busyLoop = CELEBRATE; /* Should be able to recover */
759 if (1 == find_completions(vertex, hits, n_hits, S_LEFT, 0 /*, False */ ))
760 forced_sides |= S_LEFT;
761 if (1 == find_completions(vertex, hits, n_hits, S_RIGHT, 0 /*, False */ ))
762 forced_sides |= S_RIGHT;
763 if (forced_sides == 0) {
764 if (vertex->list_ptr != 0) {
765 forced_node_c *node = *vertex->list_ptr;
767 *vertex->list_ptr = node->next;
769 node->next->vertex->list_ptr = vertex->list_ptr;
770 (void) free((void *) node);
771 tp->forced.n_nodes--;
772 if (!vertex->off_screen)
773 tp->forced.n_visible--;
774 vertex->list_ptr = 0;
779 if (vertex->list_ptr == 0) {
780 if ((node = ALLOC_NODE(forced_node_c)) == NULL)
782 node->vertex = vertex;
783 node->next = tp->forced.first;
784 if (tp->forced.first != 0)
785 tp->forced.first->vertex->list_ptr = &(node->next);
786 tp->forced.first = node;
787 vertex->list_ptr = &(tp->forced.first);
788 tp->forced.n_nodes++;
789 if (!vertex->off_screen)
790 tp->forced.n_visible++;
792 node = *vertex->list_ptr;
793 node->forced_sides = forced_sides;
799 * Delete this vertex. If the vertex is a member of the forced vertex queue,
800 * also remove that entry. We assume that the vertex is no longer
801 * connected to the fringe. Note that tp->fringe.nodes must not point to
802 * the vertex being deleted.
805 delete_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
807 if (tp->fringe.nodes == vertex) {
809 if (MI_IS_VERBOSE(mi)) {
810 (void) fprintf(stderr, "Weirdness in delete_penrose()\n");
811 (void) fprintf(stderr, "tp->fringe.nodes == vertex\n");
813 tp->busyLoop = CELEBRATE;
815 if (vertex->list_ptr != 0) {
816 forced_node_c *node = *vertex->list_ptr;
818 *vertex->list_ptr = node->next;
820 node->next->vertex->list_ptr = vertex->list_ptr;
821 (void) free((void *) node);
822 tp->forced.n_nodes--;
823 if (!vertex->off_screen)
824 tp->forced.n_visible--;
826 if (!vertex->off_screen)
827 tp->fringe.n_nodes--;
828 (void) free((void *) vertex);
833 * Check whether the addition of a tile of type vtype would completely fill
834 * the space available at vertex.
837 fills_vertex(ModeInfo * mi, vertex_type_c vtype, fringe_node_c * vertex)
840 (vertex_dir(mi, vertex, S_LEFT) - vertex_dir(mi, vertex, S_RIGHT)
841 - vtype_angle(vtype)) % 10 == 0;
846 * If you were to add a tile of type vtype to a specified side of
847 * vertex, fringe_changes tells you which other vertices it would
848 * attach to. The addresses of these vertices will be stored in the
849 * last three arguments. Null is stored if the corresponding vertex
850 * would need to be allocated.
852 * The function also analyzes which vertices would be swallowed by the tiling
853 * and thus cut off from the fringe. The result is returned as a bit pattern.
855 #define FC_BAG 1 /* Total enclosure. Should never occur. */
856 #define FC_NEW_RIGHT 2
858 #define FC_NEW_LEFT 8
859 #define FC_NEW_MASK 0xe
860 #define FC_CUT_THIS 0x10
861 #define FC_CUT_RIGHT 0x20
862 #define FC_CUT_FAR 0x40
863 #define FC_CUT_LEFT 0x80
864 #define FC_CUT_MASK 0xf0
865 #define FC_TOTAL_MASK 0xff
868 fringe_changes(ModeInfo * mi, fringe_node_c * vertex,
869 unsigned side, vertex_type_c vtype,
870 fringe_node_c ** right, fringe_node_c ** far,
871 fringe_node_c ** left)
873 fringe_node_c *v, *f = (fringe_node_c *) NULL;
874 unsigned result = FC_NEW_FAR; /* We clear this later if necessary. */
878 if (fills_vertex(mi, vtype, vertex)) {
879 result |= FC_CUT_THIS;
880 } else if (side == S_LEFT) {
881 result |= FC_NEW_RIGHT;
885 result |= FC_NEW_LEFT;
890 if (!(result & FC_NEW_LEFT)) {
894 if (fills_vertex(mi, VT_LEFT(vtype), v)) {
895 result = (result & ~FC_NEW_FAR) | FC_CUT_LEFT;
901 if (!(result & FC_NEW_RIGHT)) {
905 if (fills_vertex(mi, VT_RIGHT(vtype), v)) {
906 result = (result & ~FC_NEW_FAR) | FC_CUT_RIGHT;
912 if (!(result & FC_NEW_FAR)
913 && fills_vertex(mi, VT_FAR(vtype), f)) {
914 result |= FC_CUT_FAR;
915 result &= (~FC_NEW_LEFT & ~FC_NEW_RIGHT);
916 if (right && (result & FC_CUT_LEFT))
918 if (left && (result & FC_CUT_RIGHT))
921 if (((result & FC_CUT_LEFT) && (result & FC_CUT_RIGHT))
922 || ((result & FC_CUT_THIS) && (result & FC_CUT_FAR)))
928 /* A couple of lesser helper functions for add_tile. */
930 add_vtype(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
933 vertex->tiles[vertex->n_tiles++] = vtype;
937 for (i = vertex->n_tiles; i > 0; i--)
938 vertex->tiles[i] = vertex->tiles[i - 1];
939 vertex->tiles[0] = vtype;
944 static fringe_node_c *
945 alloc_vertex(ModeInfo * mi, angle_c dir, fringe_node_c * from, tiling_c * tp)
949 if ((v = ALLOC_NODE(fringe_node_c)) == NULL) {
951 if (MI_IS_VERBOSE(mi)) {
952 (void) fprintf(stderr, "No memory in alloc_vertex()\n");
954 tp->busyLoop = CELEBRATE;
958 add_unit_vec(dir, v->fived);
959 fived_to_loc(v->fived, tp, &(v->loc));
960 if (v->loc.x < 0 || v->loc.y < 0
961 || v->loc.x >= tp->width || v->loc.y >= tp->height) {
962 v->off_screen = True;
963 if (v->loc.x < -tp->width || v->loc.y < -tp->height
964 || v->loc.x >= 2 * tp->width || v->loc.y >= 2 * tp->height)
967 v->off_screen = False;
968 tp->fringe.n_nodes++;
971 v->rule_mask = (1 << N_VERTEX_RULES) - 1;
977 * Add a tile described by vtype to the side of vertex. This must be
978 * allowed by the rules -- we do not check it here. New vertices are
979 * allocated as necessary. The fringe and the forced vertex pool are updated.
980 * The new tile is drawn on the display.
982 * One thing we do check here is whether the new tile causes an untiled
983 * area to become enclosed by the tiling. If this would happen, the tile
984 * is not added. The return value is true iff a tile was added.
987 add_tile(ModeInfo * mi,
988 fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
990 tiling_c *tp = &tilings[MI_SCREEN(mi)];
993 *left = (fringe_node_c *) NULL,
994 *right = (fringe_node_c *) NULL,
995 *far = (fringe_node_c *) NULL,
997 unsigned fc = fringe_changes(mi, vertex, side, vtype, &right, &far, &left);
1000 ltype = VT_LEFT(vtype),
1001 rtype = VT_RIGHT(vtype),
1002 ftype = VT_FAR(vtype);
1004 /* By our conventions vertex->next lies to the left of vertex and
1005 vertex->prev to the right. */
1007 /* This should never occur. */
1010 if (MI_IS_VERBOSE(mi)) {
1011 (void) fprintf(stderr, "Weirdness in add_tile()\n");
1012 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1015 if (side == S_LEFT) {
1017 if ((right = alloc_vertex(mi, vertex_dir(mi, vertex, S_LEFT) -
1018 vtype_angle(vtype), vertex, tp)) == NULL)
1021 if ((far = alloc_vertex(mi, vertex_dir(mi, left, S_RIGHT) +
1022 vtype_angle(ltype), left, tp)) == NULL)
1026 if ((left = alloc_vertex(mi, vertex_dir(mi, vertex, S_RIGHT) +
1027 vtype_angle(vtype), vertex, tp)) == NULL)
1030 if ((far = alloc_vertex(mi, vertex_dir(mi, right, S_LEFT) -
1031 vtype_angle(rtype), right, tp)) == NULL)
1035 /* Having allocated the new vertices, but before joining them with
1036 the rest of the fringe, check if vertices with same coordinates
1037 already exist. If any such are found, give up. */
1038 node = tp->fringe.nodes;
1040 if (((fc & FC_NEW_LEFT) && fived_equal(node->fived, left->fived))
1041 || ((fc & FC_NEW_RIGHT) && fived_equal(node->fived, right->fived))
1042 || ((fc & FC_NEW_FAR) && fived_equal(node->fived, far->fived))) {
1043 /* Better luck next time. */
1044 if (fc & FC_NEW_LEFT)
1045 delete_vertex(mi, left, tp);
1046 if (fc & FC_NEW_RIGHT)
1047 delete_vertex(mi, right, tp);
1048 if (fc & FC_NEW_FAR)
1049 delete_vertex(mi, far, tp);
1053 } while (node != tp->fringe.nodes);
1056 if (!(fc & FC_CUT_THIS)) {
1057 if (side == S_LEFT) {
1058 vertex->next = right;
1059 right->prev = vertex;
1061 vertex->prev = left;
1062 left->next = vertex;
1065 if (!(fc & FC_CUT_FAR)) {
1066 if (!(fc & FC_CUT_LEFT)) {
1070 if (!(fc & FC_CUT_RIGHT)) {
1075 draw_tile(vertex, right, far, left, vtype, mi);
1077 /* Delete vertices that are no longer on the fringe. Check the others. */
1078 if (fc & FC_CUT_THIS) {
1079 tp->fringe.nodes = far;
1080 delete_vertex(mi, vertex, tp);
1082 add_vtype(vertex, side, vtype);
1083 check_vertex(mi, vertex, tp);
1084 tp->fringe.nodes = vertex;
1086 if (fc & FC_CUT_FAR)
1087 delete_vertex(mi, far, tp);
1089 add_vtype(far, fc & FC_CUT_RIGHT ? S_LEFT : S_RIGHT, ftype);
1090 check_vertex(mi, far, tp);
1092 if (fc & FC_CUT_LEFT)
1093 delete_vertex(mi, left, tp);
1095 add_vtype(left, fc & FC_CUT_FAR ? S_LEFT : S_RIGHT, ltype);
1096 check_vertex(mi, left, tp);
1098 if (fc & FC_CUT_RIGHT)
1099 delete_vertex(mi, right, tp);
1101 add_vtype(right, fc & FC_CUT_FAR ? S_RIGHT : S_LEFT, rtype);
1102 check_vertex(mi, right, tp);
1109 * Add a forced tile to a given forced vertex. Basically an easy job,
1110 * since we know what to add. But it might fail if adding the tile
1111 * would cause some untiled area to become enclosed. There is also another
1112 * more exotic culprit: we might have a dislocation. Fortunately, they
1113 * are very rare (the PRL article reported that perfect tilings of over
1114 * 2^50 tiles had been generated). There is a version of the algorithm
1115 * that doesn't produce dislocations, but it's a lot hairier than the
1116 * simpler version I used.
1119 add_forced_tile(ModeInfo * mi, forced_node_c * node)
1121 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1123 vertex_type_c vtype;
1124 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1127 if (node->forced_sides == (S_LEFT | S_RIGHT))
1128 side = NRAND(2) ? S_LEFT : S_RIGHT;
1130 side = node->forced_sides;
1131 n = match_rules(node->vertex, hits, True);
1132 n = find_completions(node->vertex, hits, n, side, &vtype /*, True */ );
1135 if (MI_IS_VERBOSE(mi)) {
1136 (void) fprintf(stderr, "Weirdness in add_forced_tile()\n");
1137 (void) fprintf(stderr, "n = %d\n", n);
1140 return add_tile(mi, node->vertex, side, vtype);
1145 * Whether the addition of a tile of vtype on the given side of vertex
1146 * would conform to the rules. The efficient way to do this would be
1147 * to add the new tile and then use the same type of search as in
1148 * match_rules. However, this function is not a performance
1149 * bottleneck (only needed for random tile additions, which are
1150 * relatively infrequent), so I will settle for a simpler implementation.
1153 legal_move(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
1155 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1156 vertex_type_c legal_vt[MAX_COMPL];
1157 int n_hits, n_legal, i;
1159 n_hits = match_rules(vertex, hits, False);
1160 n_legal = find_completions(vertex, hits, n_hits, side, legal_vt /*, False */ );
1161 for (i = 0; i < n_legal; i++)
1162 if (legal_vt[i] == vtype)
1169 * Add a randomly chosen tile to a given vertex. This requires more checking
1170 * as we must make sure the new tile conforms to the vertex rules at every
1171 * vertex it touches. */
1173 add_random_tile(fringe_node_c * vertex, ModeInfo * mi)
1175 fringe_node_c *right, *left, *far;
1176 int i, j, n, n_hits, n_good;
1177 unsigned side, fc, no_good, s;
1178 vertex_type_c vtypes[MAX_COMPL];
1179 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1180 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1182 if (MI_NPIXELS(mi) > 2) {
1183 tp->thick_color = NRAND(MI_NPIXELS(mi));
1184 /* Insure good contrast */
1185 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
1186 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
1188 tp->thick_color = tp->thin_color = MI_WHITE_PIXEL(mi);
1189 n_hits = match_rules(vertex, hits, False);
1190 side = NRAND(2) ? S_LEFT : S_RIGHT;
1191 n = find_completions(vertex, hits, n_hits, side, vtypes /*, False */ );
1192 /* One answer would mean a forced tile. */
1195 if (MI_IS_VERBOSE(mi)) {
1196 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1197 (void) fprintf(stderr, "n = %d\n", n);
1202 for (i = 0; i < n; i++) {
1203 fc = fringe_changes(mi, vertex, side, vtypes[i], &right, &far, &left);
1206 if (MI_IS_VERBOSE(mi)) {
1207 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1208 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1212 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_LEFT)) ? S_RIGHT : S_LEFT);
1213 if (!legal_move(right, s, VT_RIGHT(vtypes[i]))) {
1214 no_good |= (1 << i);
1220 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_RIGHT)) ? S_LEFT : S_RIGHT);
1221 if (!legal_move(left, s, VT_LEFT(vtypes[i]))) {
1222 no_good |= (1 << i);
1228 s = ((fc & FC_CUT_LEFT) ? S_RIGHT : S_LEFT);
1229 if (!legal_move(far, s, VT_FAR(vtypes[i]))) {
1230 no_good |= (1 << i);
1237 if (MI_IS_VERBOSE(mi)) {
1238 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1239 (void) fprintf(stderr, "n_good = %d\n", n_good);
1243 for (i = j = 0; i <= n; i++, j++)
1244 while (no_good & (1 << j))
1247 if (!add_tile(mi, vertex, side, vtypes[j - 1])) {
1249 if (MI_IS_VERBOSE(mi)) {
1250 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1256 /* One step of the growth algorithm. */
1258 draw_penrose(ModeInfo * mi)
1264 if (tilings == NULL)
1266 tp = &tilings[MI_SCREEN(mi)];
1267 if (tp->fringe.nodes == NULL)
1270 MI_IS_DRAWN(mi) = True;
1271 p = tp->forced.first;
1272 if (tp->busyLoop > 0) {
1276 if (tp->done || tp->failures >= 100) {
1280 /* Check for the initial "2-gon". */
1281 if (tp->fringe.nodes->prev == tp->fringe.nodes->next) {
1282 vertex_type_c vtype = (unsigned char) (VT_TOTAL_MASK & LRAND());
1286 if (!add_tile(mi, tp->fringe.nodes, S_LEFT, vtype))
1290 /* No visible nodes left. */
1291 if (tp->fringe.n_nodes == 0) {
1293 tp->busyLoop = COMPLETION; /* Just finished drawing */
1296 if (tp->forced.n_visible > 0 && tp->failures < 10) {
1297 n = NRAND(tp->forced.n_visible);
1299 while (p->vertex->off_screen)
1306 } else if (tp->forced.n_nodes > 0) {
1307 n = NRAND(tp->forced.n_nodes);
1311 fringe_node_c *fringe_p = tp->fringe.nodes;
1313 n = NRAND(tp->fringe.n_nodes);
1317 fringe_p = fringe_p->next;
1318 } while (fringe_p->off_screen);
1319 add_random_tile(fringe_p, mi);
1323 if (add_forced_tile(mi, p))
1330 /* Total clean-up. */
1332 release_penrose(ModeInfo * mi)
1334 if (tilings != NULL) {
1337 for (screen = 0; screen < MI_NUM_SCREENS(mi); screen++)
1338 free_penrose(&tilings[screen]);
1339 (void) free((void *) tilings);
1340 tilings = (tiling_c *) NULL;
1344 XSCREENSAVER_MODULE ("Penrose", penrose)
1346 #endif /* MODE_penrose */