1 /* -*- Mode: C; tab-width: 4 -*-
2 * penrose --- quasiperiodic tilings.
5 /* As reported in News of the Weird:
7 In April, Sir Roger Penrose, a British math professor who has worked
8 with Stephen Hawking on such topics as relativity, black holes, and
9 whether time has a beginning, filed a copyright-infringement lawsuit
10 against the Kimberly-Clark Corporation, which Penrose said copied a
11 pattern he created (a pattern demonstrating that "a nonrepeating
12 pattern could exist in nature") for its Kleenex quilted toilet paper.
13 Penrose said he doesn't like litigation but, "When it comes to the
14 population of Great Britain being invited by a multinational to wipe
15 their bottoms on what appears to be the work of a Knight of the
16 Realm, then a last stand must be taken."
18 NOTW #491, 4-jul-1997, by Chuck Shepherd.
19 http://www.nine.org/notw/notw.html
23 #if !defined( lint ) && !defined( SABER )
24 static const char sccsid[] = "@(#)penrose.c 4.00 97/01/01 xlockmore";
27 /* Copyright (c) 1996 by Timo Korvola <tkorvola@dopey.hut.fi>
29 * Permission to use, copy, modify, and distribute this software and its
30 * documentation for any purpose and without fee is hereby granted,
31 * provided that the above copyright notice appear in all copies and that
32 * both that copyright notice and this permission notice appear in
33 * supporting documentation.
35 * This file is provided AS IS with no warranties of any kind. The author
36 * shall have no liability with respect to the infringement of copyrights,
37 * trade secrets or any patents by this file or any part thereof. In no
38 * event will the author be liable for any lost revenue or profits or
39 * other special, indirect and consequential damages.
42 * 10-May-97: jwz@jwz.org: turned into a standalone program.
43 * 09-Sep-96: Written. */
46 Be careful, this probably still has a few bugs (many of which may only
47 appear with a very low probability). These are seen with -verbose .
48 If one of these are hit penrose will reinitialize.
52 * See Onoda, Steinhardt, DiVincenzo and Socolar in
53 * Phys. Rev. Lett. 60, #25, 1988 or
54 * Strandburg in Computers in Physics, Sep/Oct 1991.
56 * This implementation uses the simpler version of the growth
57 * algorithm, i.e., if there are no forced vertices, a randomly chosen
58 * tile is added to a randomly chosen vertex (no preference for those
61 * There are two essential differences to the algorithm presented in
62 * the literature: First, we do not allow the tiling to enclose an
63 * untiled area. Whenever this is in danger of happening, we just
64 * do not add the tile, hoping for a better random choice the next
65 * time. Second, when choosing a vertex randomly, we will take
66 * one that lies withing the viewport if available. If this seems to
67 * cause enclosures in the forced rule case, we will allow invisible
68 * vertices to be chosen.
70 * Tiling is restarted whenever one of the following happens: there
71 * are no incomplete vertices within the viewport or the tiling has
72 * extended a window's length beyond the edge of the window
73 * horizontally or vertically or forced rule choice has failed 100
74 * times due to areas about to become enclosed.
79 # define PROGCLASS "Penrose"
80 # define HACK_INIT init_penrose
81 # define HACK_DRAW draw_penrose
82 # define penrose_opts xlockmore_opts
83 # define DEFAULTS "*delay: 10000 \n" \
86 # include "xlockmore.h" /* from the xscreensaver distribution */
87 #else /* !STANDALONE */
88 # include "xlock.h" /* from the xlockmore distribution */
89 #endif /* !STANDALONE */
93 * Annoyingly the ANSI C library people have reserved all identifiers
94 * ending with _t for future use. Hence we use _c as a suffix for
95 * typedefs (c for class, although this is not C++).
101 * In theory one could fit 10 tiles to a single vertex. However, the
102 * vertex rules only allow at most seven tiles to meet at a vertex.
105 #define CELEBRATE 31415927 /* This causes a pause, an error occurred. */
106 #define COMPLETION 3141593 /* This causes a pause, an error occurred. */
108 #define MAX_TILES_PER_VERTEX 7
109 #define N_VERTEX_RULES 8
110 #define ALLOC_NODE( type) ((type *)malloc( sizeof( type)))
111 #define DEF_AMMANN "False"
115 static XrmOptionDescRec opts[] =
117 {"-ammann", ".penrose.ammann", XrmoptionNoArg, (caddr_t) "on"},
118 {"+ammann", ".penrose.ammann", XrmoptionNoArg, (caddr_t) "off"}
120 static argtype vars[] =
122 {(caddr_t *) & ammann, "ammann", "Ammann", DEF_AMMANN, t_Bool}
124 static OptionStruct desc[] =
126 {"-/+ammann", "turn on/off Ammann lines"}
129 ModeSpecOpt penrose_opts = { 2, opts, 1, vars, desc };
133 * These are used to specify directions. They can also be used in bit
134 * masks to specify a combination of directions.
141 * We do not actually maintain objects corresponding to the tiles since
142 * we do not really need them and they would only consume memory and
143 * cause additional bookkeeping. Instead we only have vertices, and
144 * each vertex lists the type of each adjacent tile as well as the
145 * position of the vertex on the tile (hereafter refered to as
146 * "corner"). These positions are numbered in counterclockwise order
147 * so that 0 is where two double arrows meet (see one of the
148 * articles). The tile type and vertex number are stored in a single
149 * integer (we use char, and even most of it remains unused).
151 * The primary use of tile objects would be draw traversal, but we do
152 * not currently do redraws at all (we just start over).
154 #define VT_CORNER_MASK 0x3
155 #define VT_TYPE_MASK 0x4
159 #define VT_TOTAL_MASK 0x7
161 typedef unsigned char vertex_type_c;
164 * These allow one to compute the types of the other corners of the tile. If
165 * you are standing at a vertex of type vt looking towards the middle of the
166 * tile, VT_LEFT( vt) is the vertex on your left etc.
168 #define VT_LEFT( vt) ((((vt) - 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
169 #define VT_RIGHT( vt) ((((vt) + 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
170 #define VT_FAR( vt) ((vt) ^ 2)
174 * Since we do not do redraws, we only store the vertices we need. These are
175 * the ones with still some empty space around them for the growth algorithm
178 * Here we use a doubly chained ring-like structure as vertices often need
179 * to be removed or inserted (they are kept in geometrical order
180 * circling the tiled area counterclockwise). The ring is refered to by
181 * a pointer to one more or less random node. When deleting nodes one
182 * must make sure that this pointer continues to refer to a valid
183 * node. A vertex count is maintained to make it easier to pick
186 typedef struct forced_node forced_node_c;
188 typedef struct fringe_node {
189 struct fringe_node *prev;
190 struct fringe_node *next;
191 /* These are numbered counterclockwise. The gap, if any, lies
192 between the last and first tiles. */
193 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
195 /* A bit mask used to indicate vertex rules that are still applicable for
196 completing this vertex. Initialize this to (1 << N_VERTEX_RULES) - 1,
197 i.e., all ones, and the rule matching functions will automatically mask
198 out rules that no longer match. */
199 unsigned char rule_mask;
200 /* If the vertex is on the forced vertex list, this points to the
201 pointer to the appropriate node in the list. To remove the
202 vertex from the list just set *list_ptr to the next node,
203 deallocate and decrement node count. */
204 struct forced_node **list_ptr;
205 /* Screen coordinates. */
207 /* We also keep track of 5D coordinates to avoid rounding errors.
208 These are in units of edge length. */
210 /* This is used to quickly check if a vertex is visible. */
211 unsigned char off_screen;
215 fringe_node_c *nodes;
216 /* This does not count off-screen nodes. */
222 * The forced vertex pool contains vertices where at least one
223 * side of the tiled region can only be extended in one way. Note
224 * that this does not necessarily mean that there would only be one
225 * applicable rule. forced_sides are specified using S_LEFT and
226 * S_RIGHT as if looking at the untiled region from the vertex.
229 fringe_node_c *vertex;
230 unsigned forced_sides;
231 struct forced_node *next;
235 forced_node_c *first;
236 int n_nodes, n_visible;
240 /* This is the data related to the tiling of one screen. */
246 forced_pool_c forced;
248 int thick_color, thin_color;
251 static tiling_c *tilings; /* = {0} */
254 /* The tiles are listed in counterclockwise order. */
256 vertex_type_c tiles[MAX_TILES_PER_VERTEX];
260 static vertex_rule_c vertex_rules[N_VERTEX_RULES] =
263 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2}, 5},
265 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0}, 5},
267 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THIN | 0}, 4},
269 {VT_THICK | 2, VT_THICK | 2, VT_THIN | 1, VT_THIN | 3, VT_THICK | 2,
270 VT_THIN | 1, VT_THIN | 3}, 7},
272 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2,
273 VT_THIN | 1, VT_THIN | 3}, 6},
275 {VT_THICK | 1, VT_THICK | 3, VT_THIN | 2}, 3},
277 {VT_THICK | 0, VT_THIN | 0, VT_THIN | 0}, 3},
279 {VT_THICK | 2, VT_THIN | 1, VT_THICK | 3, VT_THICK | 1, VT_THIN | 3}, 5}
283 /* Match information returned by match_rules. */
290 /* Occasionally floating point coordinates are needed. */
296 /* All angles are measured in multiples of 36 degrees. */
299 static angle_c vtype_angles[] =
300 {4, 1, 4, 1, 2, 3, 2, 3};
302 #define vtype_angle( v) (vtype_angles[ v])
305 /* Direction angle of an edge. */
307 vertex_dir(ModeInfo * mi, fringe_node_c * vertex, unsigned side)
309 tiling_c *tp = &tilings[MI_SCREEN(mi)];
311 (side == S_LEFT ? vertex->next : vertex->prev);
314 for (i = 0; i < 5; i++)
315 switch (v2->fived[i] - vertex->fived[i]) {
319 return (2 * i + 5) % 10;
322 if (MI_WIN_IS_VERBOSE(mi)) {
323 (void) fprintf(stderr,
324 "Weirdness in vertex_dir (this has been reported)\n");
325 for (i = 0; i < 5; i++)
326 (void) fprintf(stderr, "v2->fived[%d]=%d, vertex->fived[%d]=%d\n",
327 i, v2->fived[i], i, vertex->fived[i]);
329 MI_PAUSE(mi) = CELEBRATE;
334 /* Move one step to a given direction. */
336 add_unit_vec(angle_c dir, int *fived)
343 fived[dir2i[dir % 5]] += (dir % 2 ? -1 : 1);
347 /* For comparing coordinates. */
348 #define fived_equal( f1, f2) (!memcmp( (f1), (f2), 5 * sizeof( int)))
352 * This computes screen coordinates from 5D representation. Note that X
353 * uses left-handed coordinates (y increases downwards).
356 fived_to_loc(int fived[], tiling_c * tp)
358 static fcoord_c fived_table[5] =
361 float fifth = 8 * atan(1.) / 5;
364 register fcoord_c offset =
366 XPoint pt = tp->origin;
368 if (fived_table[0].x == .0)
369 for (i = 0; i < 5; i++) {
370 fived_table[i].x = cos(fifth * i);
371 fived_table[i].y = sin(fifth * i);
373 for (i = 0; i < 5; i++) {
374 r = fived[i] * tp->edge_length;
375 offset.x += r * fived_table[i].x;
376 offset.y -= r * fived_table[i].y;
378 pt.x += (int) (offset.x + .5);
379 pt.y += (int) (offset.y + .5);
384 /* Mop up dynamic data for one screen. */
386 release_screen(tiling_c * tp)
388 register fringe_node_c *fp1, *fp2;
389 register forced_node_c *lp1, *lp2;
391 if (tp->fringe.nodes == 0)
393 fp1 = tp->fringe.nodes;
397 (void) free((char *) fp2);
398 } while (fp1 != tp->fringe.nodes);
399 tp->fringe.nodes = 0;
400 for (lp1 = tp->forced.first; lp1 != 0;) {
403 (void) free((char *) lp2);
405 tp->forced.first = 0;
409 /* Called to init the mode. */
411 init_penrose(ModeInfo * mi)
417 if (tilings == NULL) {
418 if ((tilings = (tiling_c *) calloc(MI_NUM_SCREENS(mi),
419 sizeof (tiling_c))) == NULL)
422 tp = &tilings[MI_SCREEN(mi)];
425 tp->width = MI_WIN_WIDTH(mi);
426 tp->height = MI_WIN_HEIGHT(mi);
427 if (MI_NPIXELS(mi) > 2) {
428 tp->thick_color = NRAND(MI_NPIXELS(mi));
429 /* Insure good contrast */
430 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
431 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
435 tp->edge_length = NRAND(MIN(-size, MAX(MINSIZE,
436 MIN(tp->width, tp->height) / 2)) - MINSIZE + 1) + MINSIZE;
437 else if (size < MINSIZE) {
439 tp->edge_length = MAX(MINSIZE, MIN(tp->width, tp->height) / 2);
441 tp->edge_length = MINSIZE;
443 tp->edge_length = MIN(size, MAX(MINSIZE,
444 MIN(tp->width, tp->height) / 2));
445 tp->origin.x = (tp->width / 2 + NRAND(tp->width)) / 2;
446 tp->origin.y = (tp->height / 2 + NRAND(tp->height)) / 2;
447 tp->fringe.n_nodes = 2;
448 if (tp->fringe.nodes != 0)
450 if (tp->fringe.nodes != 0 || tp->forced.first != 0) {
451 if (MI_WIN_IS_VERBOSE(mi)) {
452 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
453 (void) fprintf(stderr, "tp->fringe.nodes = 0 && tp->forced.first = 0\n");
455 release_screen(tp); /* Try again */
458 tp->forced.n_nodes = tp->forced.n_visible = 0;
459 fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c);
461 if (MI_WIN_IS_VERBOSE(mi)) {
462 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
463 (void) fprintf(stderr, "fp = 0\n");
465 fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c);
469 fp->rule_mask = (1 << N_VERTEX_RULES) - 1;
471 fp->prev = fp->next = ALLOC_NODE(fringe_node_c);
473 if (MI_WIN_IS_VERBOSE(mi)) {
474 (void) fprintf(stderr, "Weirdness in init_penrose()\n");
475 (void) fprintf(stderr, "fp->next = 0\n");
477 fp->prev = fp->next = ALLOC_NODE(fringe_node_c);
481 fp->loc = tp->origin;
482 fp->off_screen = False;
483 for (i = 0; i < 5; i++)
488 fp->next->prev = fp->next->next = fp;
491 fp->fived[i] = 2 * NRAND(2) - 1;
492 fp->loc = fived_to_loc(fp->fived, tp);
493 /* That's it! We have created our first edge. */
497 * This attempts to match the configuration of vertex with the vertex
498 * rules. The return value is a total match count. If matches is
499 * non-null, it will be used to store information about the matches
500 * and must be large enough to contain it. To play it absolutely
501 * safe, allocate room for MAX_TILES_PER_VERTEX * N_VERTEX_RULES
502 * entries when searching all matches. The rule mask of vertex will
503 * be applied and rules masked out will not be searched. Only strict
504 * subsequences match. If first_only is true, the search stops when
505 * the first match is found. Otherwise all matches will be found and
506 * the rule_mask of vertex will be updated, which also happens in
507 * single-match mode if no match is found.
510 match_rules(fringe_node_c * vertex, rule_match_c * matches, int first_only)
512 /* I will assume that I can fit all the relevant bits in vertex->tiles
513 into one unsigned long. With 3 bits per element and at most 7
514 elements this means 21 bits, which should leave plenty of room.
515 After packing the bits the rest is just integer comparisons and
516 some bit shuffling. This is essentially Rabin-Karp without
517 congruence arithmetic. */
519 int hits = 0, good_rules[N_VERTEX_RULES], n_good = 0;
521 vertex_hash = 0, lower_bits_mask = ~(VT_TOTAL_MASK << VT_BITS * (vertex->n_tiles - 1));
522 unsigned new_rule_mask = 0;
524 for (i = 0; i < N_VERTEX_RULES; i++)
525 if (vertex->n_tiles >= vertex_rules[i].n_tiles)
526 vertex->rule_mask &= ~(1 << i);
527 else if (vertex->rule_mask & 1 << i)
528 good_rules[n_good++] = i;
529 for (i = 0; i < vertex->n_tiles; i++)
530 vertex_hash |= (unsigned long) vertex->tiles[i] << (VT_BITS * i);
532 for (j = 0; j < n_good; j++) {
533 unsigned long rule_hash = 0;
534 vertex_rule_c *vr = vertex_rules + good_rules[j];
536 for (i = 0; i < vertex->n_tiles; i++)
537 rule_hash |= (unsigned long) vr->tiles[i] << (VT_BITS * i);
538 if (rule_hash == vertex_hash) {
540 matches[hits].rule = good_rules[j];
541 matches[hits].pos = 0;
547 new_rule_mask |= 1 << good_rules[j];
549 for (i = vr->n_tiles - 1; i > 0; i--) {
550 rule_hash = vr->tiles[i] | (rule_hash & lower_bits_mask) << VT_BITS;
551 if (vertex_hash == rule_hash) {
553 matches[hits].rule = good_rules[j];
554 matches[hits].pos = i;
560 new_rule_mask |= 1 << good_rules[j];
564 vertex->rule_mask = new_rule_mask;
570 * find_completions finds the possible ways to add a tile to a vertex.
571 * The return values is the number of such possibilities. You must
572 * first call match_rules to produce matches and n_matches. sides
573 * specifies which side of the vertex to extend and can be S_LEFT or
574 * S_RIGHT. If results is non-null, it should point to an array large
575 * enough to contain the results, which will be stored there.
576 * MAX_COMPL elements will always suffice. If first_only is true we
577 * stop as soon as we find one possibility (NOT USED).
582 find_completions(fringe_node_c * vertex, rule_match_c * matches, int n_matches,
583 unsigned side, vertex_type_c * results /*, int first_only */ )
587 vertex_type_c buf[MAX_COMPL];
593 for (i = 0; i < n_matches; i++) {
594 vertex_rule_c *rule = vertex_rules + matches[i].rule;
595 int pos = (matches[i].pos
596 + (side == S_RIGHT ? vertex->n_tiles : rule->n_tiles - 1))
598 vertex_type_c vtype = rule->tiles[pos];
601 for (j = 0; j < n_res; j++)
602 if (vtype == results[j]) {
607 results[n_res++] = vtype;
614 * Draw a tile on the display. Vertices must be given in a
615 * counterclockwise order. vtype is the vertex type of v1 (and thus
616 * also gives the tile type).
619 draw_tile(fringe_node_c * v1, fringe_node_c * v2,
620 fringe_node_c * v3, fringe_node_c * v4,
621 vertex_type_c vtype, ModeInfo * mi)
623 Display *display = MI_DISPLAY(mi);
624 Window window = MI_WINDOW(mi);
626 tiling_c *tp = &tilings[MI_SCREEN(mi)];
628 vertex_type_c corner = vtype & VT_CORNER_MASK;
630 if (v1->off_screen && v2->off_screen && v3->off_screen && v4->off_screen)
632 pts[corner] = v1->loc;
633 pts[VT_RIGHT(corner)] = v2->loc;
634 pts[VT_FAR(corner)] = v3->loc;
635 pts[VT_LEFT(corner)] = v4->loc;
637 if (MI_NPIXELS(mi) > 2) {
638 if ((vtype & VT_TYPE_MASK) == VT_THICK)
639 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
641 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
643 XSetForeground(display, gc, MI_WIN_WHITE_PIXEL(mi));
644 XFillPolygon(display, window, gc, pts, 4, Convex, CoordModeOrigin);
645 XSetForeground(display, gc, MI_WIN_BLACK_PIXEL(mi));
646 XDrawLines(display, window, gc, pts, 5, CoordModeOrigin);
649 /* Draw some Ammann lines for debugging purposes. This will probably
650 fail miserably on a b&w display. */
652 if ((vtype & VT_TYPE_MASK) == VT_THICK) {
656 float pi10 = 2 * atan(1.) / 5;
658 r = 1 - sin(pi10) / (2 * sin(3 * pi10));
660 if (MI_NPIXELS(mi) > 2)
661 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
663 XSetForeground(display, gc, MI_WIN_WHITE_PIXEL(mi));
664 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
666 XDrawLine(display, window, gc,
667 (int) (r * pts[3].x + (1 - r) * pts[0].x + .5),
668 (int) (r * pts[3].y + (1 - r) * pts[0].y + .5),
669 (int) (r * pts[1].x + (1 - r) * pts[0].x + .5),
670 (int) (r * pts[1].y + (1 - r) * pts[0].y + .5));
671 if (MI_NPIXELS(mi) <= 2)
672 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
674 if (MI_NPIXELS(mi) > 2)
675 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
677 XSetForeground(display, gc, MI_WIN_WHITE_PIXEL(mi));
678 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
680 XDrawLine(display, window, gc,
681 (int) ((pts[3].x + pts[2].x) / 2 + .5),
682 (int) ((pts[3].y + pts[2].y) / 2 + .5),
683 (int) ((pts[1].x + pts[2].x) / 2 + .5),
684 (int) ((pts[1].y + pts[2].y) / 2 + .5));
685 if (MI_NPIXELS(mi) <= 2)
686 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
692 * Update the status of this vertex on the forced vertex queue. If
693 * the vertex has become untileable set tp->done. This is supposed
694 * to detect dislocations -- never call this routine with a completely
697 * Check for untileable vertices in check_vertex and stop tiling as
698 * soon as one finds one. I don't know if it is possible to run out
699 * of forced vertices while untileable vertices exist (or will
700 * cavities inevitably appear). If this can happen, add_random_tile
701 * might get called with an untileable vertex, causing ( n <= 1).
702 * (This is what the tp->done checks for).
704 * A MI_PAUSE celebrates the dislocation.
707 check_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
709 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
710 int n_hits = match_rules(vertex, hits, False);
711 unsigned forced_sides = 0;
713 if (vertex->rule_mask == 0) {
715 if (MI_WIN_IS_VERBOSE(mi)) {
716 (void) fprintf(stderr, "Dislocation occured!\n");
718 MI_PAUSE(mi) = CELEBRATE; /* Should be able to recover */
720 if (1 == find_completions(vertex, hits, n_hits, S_LEFT, 0 /*, False */ ))
721 forced_sides |= S_LEFT;
722 if (1 == find_completions(vertex, hits, n_hits, S_RIGHT, 0 /*, False */ ))
723 forced_sides |= S_RIGHT;
724 if (forced_sides == 0) {
725 if (vertex->list_ptr != 0) {
726 forced_node_c *node = *vertex->list_ptr;
728 *vertex->list_ptr = node->next;
730 node->next->vertex->list_ptr = vertex->list_ptr;
732 tp->forced.n_nodes--;
733 if (!vertex->off_screen)
734 tp->forced.n_visible--;
735 vertex->list_ptr = 0;
740 if (vertex->list_ptr == 0) {
741 node = ALLOC_NODE(forced_node_c);
742 node->vertex = vertex;
743 node->next = tp->forced.first;
744 if (tp->forced.first != 0)
745 tp->forced.first->vertex->list_ptr = &(node->next);
746 tp->forced.first = node;
747 vertex->list_ptr = &(tp->forced.first);
748 tp->forced.n_nodes++;
749 if (!vertex->off_screen)
750 tp->forced.n_visible++;
752 node = *vertex->list_ptr;
753 node->forced_sides = forced_sides;
759 * Delete this vertex. If the vertex is a member of the forced vertex queue,
760 * also remove that entry. We assume that the vertex is no longer
761 * connected to the fringe. Note that tp->fringe.nodes must not point to
762 * the vertex being deleted.
765 delete_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
767 if (tp->fringe.nodes == vertex) {
769 if (MI_WIN_IS_VERBOSE(mi)) {
770 (void) fprintf(stderr, "Weirdness in delete_penrose()\n");
771 (void) fprintf(stderr, "tp->fringe.nodes == vertex\n");
773 MI_PAUSE(mi) = CELEBRATE;
775 if (vertex->list_ptr != 0) {
776 forced_node_c *node = *vertex->list_ptr;
778 *vertex->list_ptr = node->next;
780 node->next->vertex->list_ptr = vertex->list_ptr;
782 tp->forced.n_nodes--;
783 if (!vertex->off_screen)
784 tp->forced.n_visible--;
786 if (!vertex->off_screen)
787 tp->fringe.n_nodes--;
792 /* Check whether the addition of a tile of type vtype would completely fill *
793 the space available at vertex. */
795 fills_vertex(ModeInfo * mi, vertex_type_c vtype, fringe_node_c * vertex)
798 (vertex_dir(mi, vertex, S_LEFT) - vertex_dir(mi, vertex, S_RIGHT)
799 - vtype_angle(vtype)) % 10 == 0;
804 * If you were to add a tile of type vtype to a specified side of
805 * vertex, fringe_changes tells you which other vertices it would
806 * attach to. The addresses of these vertices will be stored in the
807 * last three arguments. Null is stored if the corresponding vertex
808 * would need to be allocated.
810 * The function also analyzes which vertices would be swallowed by the tiling
811 * and thus cut off from the fringe. The result is returned as a bit pattern.
813 #define FC_BAG 1 /* Total enclosure. Should never occur. */
814 #define FC_NEW_RIGHT 2
816 #define FC_NEW_LEFT 8
817 #define FC_NEW_MASK 0xe
818 #define FC_CUT_THIS 0x10
819 #define FC_CUT_RIGHT 0x20
820 #define FC_CUT_FAR 0x40
821 #define FC_CUT_LEFT 0x80
822 #define FC_CUT_MASK 0xf0
823 #define FC_TOTAL_MASK 0xff
826 fringe_changes(ModeInfo * mi, fringe_node_c * vertex,
827 unsigned side, vertex_type_c vtype,
828 fringe_node_c ** right, fringe_node_c ** far,
829 fringe_node_c ** left)
831 fringe_node_c *v, *f = NULL;
832 unsigned result = FC_NEW_FAR; /* We clear this later if necessary. */
836 if (fills_vertex(mi, vtype, vertex)) {
837 result |= FC_CUT_THIS;
838 } else if (side == S_LEFT) {
839 result |= FC_NEW_RIGHT;
843 result |= FC_NEW_LEFT;
848 if (!(result & FC_NEW_LEFT)) {
852 if (fills_vertex(mi, VT_LEFT(vtype), v)) {
853 result = (result & ~FC_NEW_FAR) | FC_CUT_LEFT;
859 if (!(result & FC_NEW_RIGHT)) {
863 if (fills_vertex(mi, VT_RIGHT(vtype), v)) {
864 result = (result & ~FC_NEW_FAR) | FC_CUT_RIGHT;
870 if (!(result & FC_NEW_FAR)
871 && fills_vertex(mi, VT_FAR(vtype), f)) {
872 result |= FC_CUT_FAR;
873 result &= (~FC_NEW_LEFT & ~FC_NEW_RIGHT);
874 if (right && (result & FC_CUT_LEFT))
876 if (left && (result & FC_CUT_RIGHT))
879 if (((result & FC_CUT_LEFT) && (result & FC_CUT_RIGHT))
880 || ((result & FC_CUT_THIS) && (result & FC_CUT_FAR)))
886 /* A couple of lesser helper functions for add_tile. */
888 add_vtype(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
891 vertex->tiles[vertex->n_tiles++] = vtype;
895 for (i = vertex->n_tiles; i > 0; i--)
896 vertex->tiles[i] = vertex->tiles[i - 1];
897 vertex->tiles[0] = vtype;
902 static fringe_node_c *
903 alloc_vertex(ModeInfo * mi, angle_c dir, fringe_node_c * from, tiling_c * tp)
905 fringe_node_c *v = ALLOC_NODE(fringe_node_c);
909 if (MI_WIN_IS_VERBOSE(mi)) {
910 (void) fprintf(stderr, "Weirdness in alloc_vertex()\n");
911 (void) fprintf(stderr, "v = 0\n");
913 MI_PAUSE(mi) = CELEBRATE;
916 add_unit_vec(dir, v->fived);
917 v->loc = fived_to_loc(v->fived, tp);
918 if (v->loc.x < 0 || v->loc.y < 0
919 || v->loc.x >= tp->width || v->loc.y >= tp->height) {
920 v->off_screen = True;
921 if (v->loc.x < -tp->width || v->loc.y < -tp->height
922 || v->loc.x >= 2 * tp->width || v->loc.y >= 2 * tp->height)
925 v->off_screen = False;
926 tp->fringe.n_nodes++;
929 v->rule_mask = (1 << N_VERTEX_RULES) - 1;
935 * Add a tile described by vtype to the side of vertex. This must be
936 * allowed by the rules -- we do not check it here. New vertices are
937 * allocated as necessary. The fringe and the forced vertex pool are updated.
938 * The new tile is drawn on the display.
940 * One thing we do check here is whether the new tile causes an untiled
941 * area to become enclosed by the tiling. If this would happen, the tile
942 * is not added. The return value is true iff a tile was added.
945 add_tile(ModeInfo * mi,
946 fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
948 tiling_c *tp = &tilings[MI_SCREEN(mi)];
955 unsigned fc = fringe_changes(mi, vertex, side, vtype, &right, &far, &left);
958 ltype = VT_LEFT(vtype),
959 rtype = VT_RIGHT(vtype),
960 ftype = VT_FAR(vtype);
962 /* By our conventions vertex->next lies to the left of vertex and
963 vertex->prev to the right. */
965 /* This should never occur. */
968 if (MI_WIN_IS_VERBOSE(mi)) {
969 (void) fprintf(stderr, "Weirdness in add_tile()\n");
970 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
973 if (side == S_LEFT) {
975 right = alloc_vertex(mi,
976 vertex_dir(mi, vertex, S_LEFT) - vtype_angle(vtype), vertex, tp);
978 far = alloc_vertex(mi,
979 vertex_dir(mi, left, S_RIGHT) + vtype_angle(ltype), left, tp);
982 left = alloc_vertex(mi,
983 vertex_dir(mi, vertex, S_RIGHT) + vtype_angle(vtype), vertex, tp);
985 far = alloc_vertex(mi,
986 vertex_dir(mi, right, S_LEFT) - vtype_angle(rtype), right, tp);
989 /* Having allocated the new vertices, but before joining them with
990 the rest of the fringe, check if vertices with same coordinates
991 already exist. If any such are found, give up. */
992 node = tp->fringe.nodes;
994 if (((fc & FC_NEW_LEFT) && fived_equal(node->fived, left->fived))
995 || ((fc & FC_NEW_RIGHT) && fived_equal(node->fived, right->fived))
996 || ((fc & FC_NEW_FAR) && fived_equal(node->fived, far->fived))) {
997 /* Better luck next time. */
998 if (fc & FC_NEW_LEFT)
999 delete_vertex(mi, left, tp);
1000 if (fc & FC_NEW_RIGHT)
1001 delete_vertex(mi, right, tp);
1002 if (fc & FC_NEW_FAR)
1003 delete_vertex(mi, far, tp);
1007 } while (node != tp->fringe.nodes);
1010 if (!(fc & FC_CUT_THIS))
1011 if (side == S_LEFT) {
1012 vertex->next = right;
1013 right->prev = vertex;
1015 vertex->prev = left;
1016 left->next = vertex;
1018 if (!(fc & FC_CUT_FAR)) {
1019 if (!(fc & FC_CUT_LEFT)) {
1023 if (!(fc & FC_CUT_RIGHT)) {
1028 draw_tile(vertex, right, far, left, vtype, mi);
1030 /* Delete vertices that are no longer on the fringe. Check the others. */
1031 if (fc & FC_CUT_THIS) {
1032 tp->fringe.nodes = far;
1033 delete_vertex(mi, vertex, tp);
1035 add_vtype(vertex, side, vtype);
1036 check_vertex(mi, vertex, tp);
1037 tp->fringe.nodes = vertex;
1039 if (fc & FC_CUT_FAR)
1040 delete_vertex(mi, far, tp);
1042 add_vtype(far, fc & FC_CUT_RIGHT ? S_LEFT : S_RIGHT, ftype);
1043 check_vertex(mi, far, tp);
1045 if (fc & FC_CUT_LEFT)
1046 delete_vertex(mi, left, tp);
1048 add_vtype(left, fc & FC_CUT_FAR ? S_LEFT : S_RIGHT, ltype);
1049 check_vertex(mi, left, tp);
1051 if (fc & FC_CUT_RIGHT)
1052 delete_vertex(mi, right, tp);
1054 add_vtype(right, fc & FC_CUT_FAR ? S_RIGHT : S_LEFT, rtype);
1055 check_vertex(mi, right, tp);
1062 * Add a forced tile to a given forced vertex. Basically an easy job,
1063 * since we know what to add. But it might fail if adding the tile
1064 * would cause some untiled area to become enclosed. There is also another
1065 * more exotic culprit: we might have a dislocation. Fortunately, they
1066 * are very rare (the PRL article reported that perfect tilings of over
1067 * 2^50 tiles had been generated). There is a version of the algorithm
1068 * that doesn't produce dislocations, but it's a lot hairier than the
1069 * simpler version I used.
1072 add_forced_tile(ModeInfo * mi, forced_node_c * node)
1074 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1076 vertex_type_c vtype;
1077 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1080 if (node->forced_sides == (S_LEFT | S_RIGHT))
1081 side = NRAND(2) ? S_LEFT : S_RIGHT;
1083 side = node->forced_sides;
1084 n = match_rules(node->vertex, hits, True);
1085 n = find_completions(node->vertex, hits, n, side, &vtype /*, True */ );
1088 if (MI_WIN_IS_VERBOSE(mi)) {
1089 (void) fprintf(stderr, "Weirdness in add_forced_tile()\n");
1090 (void) fprintf(stderr, "n = %d\n", n);
1093 return add_tile(mi, node->vertex, side, vtype);
1098 * Whether the addition of a tile of vtype on the given side of vertex
1099 * would conform to the rules. The efficient way to do this would be
1100 * to add the new tile and then use the same type of search as in
1101 * match_rules. However, this function is not a performance
1102 * bottleneck (only needed for random tile additions, which are
1103 * relatively infrequent), so I will settle for a simpler implementation.
1106 legal_move(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
1108 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1109 vertex_type_c legal_vt[MAX_COMPL];
1110 int n_hits, n_legal, i;
1112 n_hits = match_rules(vertex, hits, False);
1113 n_legal = find_completions(vertex, hits, n_hits, side, legal_vt /*, False */ );
1114 for (i = 0; i < n_legal; i++)
1115 if (legal_vt[i] == vtype)
1122 * Add a randomly chosen tile to a given vertex. This requires more checking
1123 * as we must make sure the new tile conforms to the vertex rules at every
1124 * vertex it touches. */
1126 add_random_tile(fringe_node_c * vertex, ModeInfo * mi)
1128 fringe_node_c *right, *left, *far;
1129 int i, j, n, n_hits, n_good;
1130 unsigned side, fc, no_good, s;
1131 vertex_type_c vtypes[MAX_COMPL];
1132 rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1133 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1135 if (MI_NPIXELS(mi) > 2) {
1136 tp->thick_color = NRAND(MI_NPIXELS(mi));
1137 /* Insure good contrast */
1138 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
1139 MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
1141 tp->thick_color = tp->thin_color = MI_WIN_WHITE_PIXEL(mi);
1142 n_hits = match_rules(vertex, hits, False);
1143 side = NRAND(2) ? S_LEFT : S_RIGHT;
1144 n = find_completions(vertex, hits, n_hits, side, vtypes /*, False */ );
1145 /* One answer would mean a forced tile. */
1148 if (MI_WIN_IS_VERBOSE(mi)) {
1149 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1150 (void) fprintf(stderr, "n = %d\n", n);
1155 for (i = 0; i < n; i++) {
1156 fc = fringe_changes(mi, vertex, side, vtypes[i], &right, &far, &left);
1159 if (MI_WIN_IS_VERBOSE(mi)) {
1160 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1161 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1165 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_LEFT)) ? S_RIGHT : S_LEFT);
1166 if (!legal_move(right, s, VT_RIGHT(vtypes[i]))) {
1167 no_good |= (1 << i);
1173 s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_RIGHT)) ? S_LEFT : S_RIGHT);
1174 if (!legal_move(left, s, VT_LEFT(vtypes[i]))) {
1175 no_good |= (1 << i);
1181 s = ((fc & FC_CUT_LEFT) ? S_RIGHT : S_LEFT);
1182 if (!legal_move(far, s, VT_FAR(vtypes[i]))) {
1183 no_good |= (1 << i);
1190 if (MI_WIN_IS_VERBOSE(mi)) {
1191 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1192 (void) fprintf(stderr, "n_good = %d\n", n_good);
1196 for (i = j = 0; i <= n; i++, j++)
1197 while (no_good & (1 << j))
1200 i = add_tile(mi, vertex, side, vtypes[j - 1]);
1203 if (MI_WIN_IS_VERBOSE(mi)) {
1204 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1205 (void) fprintf(stderr, "i = %d\n", i);
1210 /* One step of the growth algorithm. */
1212 draw_penrose(ModeInfo * mi)
1214 tiling_c *tp = &tilings[MI_SCREEN(mi)];
1216 forced_node_c *p = tp->forced.first;
1218 if (tp->done || tp->failures >= 100) {
1222 /* Check for the initial "2-gon". */
1223 if (tp->fringe.nodes->prev == tp->fringe.nodes->next) {
1224 vertex_type_c vtype = VT_TOTAL_MASK & LRAND();
1226 XClearWindow(MI_DISPLAY(mi), MI_WINDOW(mi));
1227 (void) add_tile(mi, tp->fringe.nodes, S_LEFT, vtype);
1230 /* No visible nodes left. */
1231 if (tp->fringe.n_nodes == 0) {
1233 MI_PAUSE(mi) = COMPLETION; /* Just finished drawing */
1236 if (tp->forced.n_visible > 0 && tp->failures < 10) {
1237 n = NRAND(tp->forced.n_visible);
1239 while (p->vertex->off_screen)
1246 } else if (tp->forced.n_nodes > 0) {
1247 n = NRAND(tp->forced.n_nodes);
1251 fringe_node_c *p = tp->fringe.nodes;
1253 n = NRAND(tp->fringe.n_nodes);
1258 } while (p->off_screen);
1259 add_random_tile(p, mi);
1263 if (add_forced_tile(mi, p))
1270 /* Total clean-up. */
1272 release_penrose(ModeInfo * mi)
1274 if (tilings != NULL) {
1277 for (screen = 0; screen < MI_NUM_SCREENS(mi); screen++) {
1278 tiling_c *tp = &tilings[screen];
1282 (void) free((void *) tilings);