tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * Generate Penrose tilings via combinatorial coordinates.
3 *
4 * For general explanation of the algorithm:
5 * https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/
6 *
7 * I use exactly the same indexing system here that's described in the
8 * article. For the P2 tiling, acute isosceles triangles (half-kites)
9 * are assigned letters A,B, and obtuse ones (half-darts) U,V; for P3,
10 * acute triangles (half of a thin rhomb) are C,D and obtuse ones
11 * (half a thick rhomb) are X,Y. Edges of all triangles are indexed
12 * anticlockwise around the triangle, with 0 being the base and 1,2
13 * being the two equal legs.
14 */
15
16#include <assert.h>
17#include <stddef.h>
18#include <string.h>
19
20#include "puzzles.h"
21#include "penrose.h"
22#include "penrose-internal.h"
23#include "tree234.h"
24
25bool penrose_valid_letter(char c, int which)
26{
27 switch (c) {
28 case 'A': case 'B': case 'U': case 'V':
29 return which == PENROSE_P2;
30 case 'C': case 'D': case 'X': case 'Y':
31 return which == PENROSE_P3;
32 default:
33 return false;
34 }
35}
36
37/*
38 * Result of attempting a transition within the coordinate system.
39 * INTERNAL means we've moved to a different child of the same parent,
40 * so the 'internal' substructure gives the type of the new triangle
41 * and which edge of it we came in through; EXTERNAL means we've moved
42 * out of the parent entirely, and the 'external' substructure tells
43 * us which edge of the parent triangle we left by, and if it's
44 * divided in two, which end of that edge (-1 for the left end or +1
45 * for the right end). If the parent edge is undivided, end == 0.
46 *
47 * The type FAIL _shouldn't_ ever come up! It occurs if you try to
48 * compute an incoming transition with an illegal value of 'end' (i.e.
49 * having the wrong idea of whether the edge is divided), or if you
50 * refer to a child triangle type that doesn't exist in that parent.
51 * If it ever happens in the production code then an assertion will
52 * fail. But it might be useful to other users of the same code.
53 */
54typedef struct TransitionResult {
55 enum { INTERNAL, EXTERNAL, FAIL } type;
56 union {
57 struct {
58 char new_child;
59 unsigned char new_edge;
60 } internal;
61 struct {
62 unsigned char parent_edge;
63 signed char end;
64 } external;
65 } u;
66} TransitionResult;
67
68/* Construction function to make an INTERNAL-type TransitionResult */
69static inline TransitionResult internal(char new_child, unsigned new_edge)
70{
71 TransitionResult tr;
72 tr.type = INTERNAL;
73 tr.u.internal.new_child = new_child;
74 tr.u.internal.new_edge = new_edge;
75 return tr;
76}
77
78/* Construction function to make an EXTERNAL-type TransitionResult */
79static inline TransitionResult external(unsigned parent_edge, int end)
80{
81 TransitionResult tr;
82 tr.type = EXTERNAL;
83 tr.u.external.parent_edge = parent_edge;
84 tr.u.external.end = end;
85 return tr;
86}
87
88/* Construction function to make a FAIL-type TransitionResult */
89static inline TransitionResult fail(void)
90{
91 TransitionResult tr;
92 tr.type = FAIL;
93 return tr;
94}
95
96/*
97 * Compute a transition out of a triangle. Can return either INTERNAL
98 * or EXTERNAL types (or FAIL if it gets invalid data).
99 */
100static TransitionResult transition(char parent, char child, unsigned edge)
101{
102 switch (parent) {
103 case 'A':
104 switch (child) {
105 case 'A':
106 switch (edge) {
107 case 0: return external(2, -1);
108 case 1: return external(0, 0);
109 case 2: return internal('B', 1);
110 }
111 case 'B':
112 switch (edge) {
113 case 0: return internal('U', 1);
114 case 1: return internal('A', 2);
115 case 2: return external(1, +1);
116 }
117 case 'U':
118 switch (edge) {
119 case 0: return external(2, +1);
120 case 1: return internal('B', 0);
121 case 2: return external(1, -1);
122 }
123 default:
124 return fail();
125 }
126 case 'B':
127 switch (child) {
128 case 'A':
129 switch (edge) {
130 case 0: return internal('V', 2);
131 case 1: return external(2, -1);
132 case 2: return internal('B', 1);
133 }
134 case 'B':
135 switch (edge) {
136 case 0: return external(1, +1);
137 case 1: return internal('A', 2);
138 case 2: return external(0, 0);
139 }
140 case 'V':
141 switch (edge) {
142 case 0: return external(1, -1);
143 case 1: return external(2, +1);
144 case 2: return internal('A', 0);
145 }
146 default:
147 return fail();
148 }
149 case 'U':
150 switch (child) {
151 case 'B':
152 switch (edge) {
153 case 0: return internal('U', 1);
154 case 1: return external(2, 0);
155 case 2: return external(0, +1);
156 }
157 case 'U':
158 switch (edge) {
159 case 0: return external(1, 0);
160 case 1: return internal('B', 0);
161 case 2: return external(0, -1);
162 }
163 default:
164 return fail();
165 }
166 case 'V':
167 switch (child) {
168 case 'A':
169 switch (edge) {
170 case 0: return internal('V', 2);
171 case 1: return external(0, -1);
172 case 2: return external(1, 0);
173 }
174 case 'V':
175 switch (edge) {
176 case 0: return external(2, 0);
177 case 1: return external(0, +1);
178 case 2: return internal('A', 0);
179 }
180 default:
181 return fail();
182 }
183 case 'C':
184 switch (child) {
185 case 'C':
186 switch (edge) {
187 case 0: return external(1, +1);
188 case 1: return internal('Y', 1);
189 case 2: return external(0, 0);
190 }
191 case 'Y':
192 switch (edge) {
193 case 0: return external(2, 0);
194 case 1: return internal('C', 1);
195 case 2: return external(1, -1);
196 }
197 default:
198 return fail();
199 }
200 case 'D':
201 switch (child) {
202 case 'D':
203 switch (edge) {
204 case 0: return external(2, -1);
205 case 1: return external(0, 0);
206 case 2: return internal('X', 2);
207 }
208 case 'X':
209 switch (edge) {
210 case 0: return external(1, 0);
211 case 1: return external(2, +1);
212 case 2: return internal('D', 2);
213 }
214 default:
215 return fail();
216 }
217 case 'X':
218 switch (child) {
219 case 'C':
220 switch (edge) {
221 case 0: return external(2, +1);
222 case 1: return internal('Y', 1);
223 case 2: return internal('X', 1);
224 }
225 case 'X':
226 switch (edge) {
227 case 0: return external(1, 0);
228 case 1: return internal('C', 2);
229 case 2: return external(0, -1);
230 }
231 case 'Y':
232 switch (edge) {
233 case 0: return external(0, +1);
234 case 1: return internal('C', 1);
235 case 2: return external(2, -1);
236 }
237 default:
238 return fail();
239 }
240 case 'Y':
241 switch (child) {
242 case 'D':
243 switch (edge) {
244 case 0: return external(1, -1);
245 case 1: return internal('Y', 2);
246 case 2: return internal('X', 2);
247 }
248 case 'X':
249 switch (edge) {
250 case 0: return external(0, -1);
251 case 1: return external(1, +1);
252 case 2: return internal('D', 2);
253 }
254 case 'Y':
255 switch (edge) {
256 case 0: return external(2, 0);
257 case 1: return external(0, +1);
258 case 2: return internal('D', 1);
259 }
260 default:
261 return fail();
262 }
263 default:
264 return fail();
265 }
266}
267
268/*
269 * Compute a transition into a parent triangle, after the above
270 * function reported an EXTERNAL transition out of a neighbouring
271 * parent and we had to recurse. Because we're coming inwards, this
272 * should always return an INTERNAL TransitionResult (or FAIL if it
273 * gets invalid data).
274 */
275static TransitionResult transition_in(char parent, unsigned edge, int end)
276{
277 #define EDGEEND(edge, end) (3 * (edge) + 1 + (end))
278
279 switch (parent) {
280 case 'A':
281 switch (EDGEEND(edge, end)) {
282 case EDGEEND(0, 0): return internal('A', 1);
283 case EDGEEND(1, -1): return internal('B', 2);
284 case EDGEEND(1, +1): return internal('U', 2);
285 case EDGEEND(2, -1): return internal('U', 0);
286 case EDGEEND(2, +1): return internal('A', 0);
287 default:
288 return fail();
289 }
290 case 'B':
291 switch (EDGEEND(edge, end)) {
292 case EDGEEND(0, 0): return internal('B', 2);
293 case EDGEEND(1, -1): return internal('B', 0);
294 case EDGEEND(1, +1): return internal('V', 0);
295 case EDGEEND(2, -1): return internal('V', 1);
296 case EDGEEND(2, +1): return internal('A', 1);
297 default:
298 return fail();
299 }
300 case 'U':
301 switch (EDGEEND(edge, end)) {
302 case EDGEEND(0, -1): return internal('B', 2);
303 case EDGEEND(0, +1): return internal('U', 2);
304 case EDGEEND(1, 0): return internal('U', 0);
305 case EDGEEND(2, 0): return internal('B', 1);
306 default:
307 return fail();
308 }
309 case 'V':
310 switch (EDGEEND(edge, end)) {
311 case EDGEEND(0, -1): return internal('V', 1);
312 case EDGEEND(0, +1): return internal('A', 1);
313 case EDGEEND(1, 0): return internal('A', 2);
314 case EDGEEND(2, 0): return internal('V', 0);
315 default:
316 return fail();
317 }
318 case 'C':
319 switch (EDGEEND(edge, end)) {
320 case EDGEEND(0, 0): return internal('C', 2);
321 case EDGEEND(1, -1): return internal('C', 0);
322 case EDGEEND(1, +1): return internal('Y', 2);
323 case EDGEEND(2, 0): return internal('Y', 0);
324 default:
325 return fail();
326 }
327 case 'D':
328 switch (EDGEEND(edge, end)) {
329 case EDGEEND(0, 0): return internal('D', 1);
330 case EDGEEND(1, 0): return internal('X', 0);
331 case EDGEEND(2, -1): return internal('X', 1);
332 case EDGEEND(2, +1): return internal('D', 0);
333 default:
334 return fail();
335 }
336 case 'X':
337 switch (EDGEEND(edge, end)) {
338 case EDGEEND(0, -1): return internal('Y', 0);
339 case EDGEEND(0, +1): return internal('X', 2);
340 case EDGEEND(1, 0): return internal('X', 0);
341 case EDGEEND(2, -1): return internal('C', 0);
342 case EDGEEND(2, +1): return internal('Y', 2);
343 default:
344 return fail();
345 }
346 case 'Y':
347 switch (EDGEEND(edge, end)) {
348 case EDGEEND(0, +1): return internal('X', 0);
349 case EDGEEND(0, -1): return internal('Y', 1);
350 case EDGEEND(1, -1): return internal('X', 1);
351 case EDGEEND(1, +1): return internal('D', 0);
352 case EDGEEND(2, 0): return internal('Y', 0);
353 default:
354 return fail();
355 }
356 default:
357 return fail();
358 }
359
360 #undef EDGEEND
361}
362
363PenroseCoords *penrose_coords_new(void)
364{
365 PenroseCoords *pc = snew(PenroseCoords);
366 pc->nc = pc->csize = 0;
367 pc->c = NULL;
368 return pc;
369}
370
371void penrose_coords_free(PenroseCoords *pc)
372{
373 if (pc) {
374 sfree(pc->c);
375 sfree(pc);
376 }
377}
378
379void penrose_coords_make_space(PenroseCoords *pc, size_t size)
380{
381 if (pc->csize < size) {
382 pc->csize = pc->csize * 5 / 4 + 16;
383 if (pc->csize < size)
384 pc->csize = size;
385 pc->c = sresize(pc->c, pc->csize, char);
386 }
387}
388
389PenroseCoords *penrose_coords_copy(PenroseCoords *pc_in)
390{
391 PenroseCoords *pc_out = penrose_coords_new();
392 penrose_coords_make_space(pc_out, pc_in->nc);
393 memcpy(pc_out->c, pc_in->c, pc_in->nc * sizeof(*pc_out->c));
394 pc_out->nc = pc_in->nc;
395 return pc_out;
396}
397
398/*
399 * The main recursive function for computing the next triangle's
400 * combinatorial coordinates.
401 */
402static void penrosectx_step_recurse(
403 PenroseContext *ctx, PenroseCoords *pc, size_t depth,
404 unsigned edge, unsigned *outedge)
405{
406 TransitionResult tr;
407
408 penrosectx_extend_coords(ctx, pc, depth+2);
409
410 /* Look up the transition out of the starting triangle */
411 tr = transition(pc->c[depth+1], pc->c[depth], edge);
412
413 /* If we've left the parent triangle, recurse to find out what new
414 * triangle we've landed in at the next size up, and then call
415 * transition_in to find out which child of that parent we're
416 * going to */
417 if (tr.type == EXTERNAL) {
418 unsigned parent_outedge;
419 penrosectx_step_recurse(
420 ctx, pc, depth+1, tr.u.external.parent_edge, &parent_outedge);
421 tr = transition_in(pc->c[depth+1], parent_outedge, tr.u.external.end);
422 }
423
424 /* Now we should definitely have ended up in a child of the
425 * (perhaps rewritten) parent triangle */
426 assert(tr.type == INTERNAL);
427 pc->c[depth] = tr.u.internal.new_child;
428 *outedge = tr.u.internal.new_edge;
429}
430
431void penrosectx_step(PenroseContext *ctx, PenroseCoords *pc,
432 unsigned edge, unsigned *outedge)
433{
434 /* Allow outedge to be NULL harmlessly, just in case */
435 unsigned dummy_outedge;
436 if (!outedge)
437 outedge = &dummy_outedge;
438
439 penrosectx_step_recurse(ctx, pc, 0, edge, outedge);
440}
441
442static Point penrose_triangle_post_edge(char c, unsigned edge)
443{
444 static const Point acute_post_edge[3] = {
445 {{-1, 1, 0, 1}}, /* phi * t^3 */
446 {{-1, 1, -1, 1}}, /* t^4 */
447 {{-1, 1, 0, 0}}, /* 1/phi * t^3 */
448 };
449 static const Point obtuse_post_edge[3] = {
450 {{0, -1, 1, 0}}, /* 1/phi * t^4 */
451 {{0, 0, 1, 0}}, /* t^2 */
452 {{-1, 0, 0, 1}}, /* phi * t^4 */
453 };
454
455 switch (c) {
456 case 'A': case 'B': case 'C': case 'D':
457 return acute_post_edge[edge];
458 default: /* case 'U': case 'V': case 'X': case 'Y': */
459 return obtuse_post_edge[edge];
460 }
461}
462
463void penrose_place(PenroseTriangle *tri, Point u, Point v, int index_of_u)
464{
465 unsigned i;
466 Point here = u, delta = point_sub(v, u);
467
468 for (i = 0; i < 3; i++) {
469 unsigned edge = (index_of_u + i) % 3;
470 tri->vertices[edge] = here;
471 here = point_add(here, delta);
472 delta = point_mul(delta, penrose_triangle_post_edge(
473 tri->pc->c[0], edge));
474 }
475}
476
477void penrose_free(PenroseTriangle *tri)
478{
479 penrose_coords_free(tri->pc);
480 sfree(tri);
481}
482
483static unsigned long penrose_relative_probability(char c)
484{
485 /* Penrose tile probability ratios are always phi, so we can
486 * approximate that very well using two consecutive Fibonacci
487 * numbers */
488 switch (c) {
489 case 'A': case 'B': case 'X': case 'Y':
490 return 63245986;
491 case 'C': case 'D': case 'U': case 'V':
492 return 39088169;
493 default:
494 return 0;
495 }
496}
497
498static char penrose_choose_random(const char *possibilities, random_state *rs)
499{
500 const char *p;
501 unsigned long value, limit = 0;
502
503 for (p = possibilities; *p; p++)
504 limit += penrose_relative_probability(*p);
505 value = random_upto(rs, limit);
506 for (p = possibilities; *p; p++) {
507 unsigned long curr = penrose_relative_probability(*p);
508 if (value < curr)
509 return *p;
510 value -= curr;
511 }
512 assert(false && "Probability overflow!");
513 return possibilities[0];
514}
515
516static const char *penrose_starting_tiles(int which)
517{
518 return which == PENROSE_P2 ? "ABUV" : "CDXY";
519}
520
521static const char *penrose_valid_parents(char tile)
522{
523 switch (tile) {
524 case 'A': return "ABV";
525 case 'B': return "ABU";
526 case 'U': return "AU";
527 case 'V': return "BV";
528 case 'C': return "CX";
529 case 'D': return "DY";
530 case 'X': return "DXY";
531 case 'Y': return "CXY";
532 default: return NULL;
533 }
534}
535
536void penrosectx_init_random(PenroseContext *ctx, random_state *rs, int which)
537{
538 ctx->rs = rs;
539 ctx->must_free_rs = false;
540 ctx->prototype = penrose_coords_new();
541 penrose_coords_make_space(ctx->prototype, 1);
542 ctx->prototype->c[0] = penrose_choose_random(
543 penrose_starting_tiles(which), rs);
544 ctx->prototype->nc = 1;
545 ctx->start_vertex = random_upto(rs, 3);
546 ctx->orientation = random_upto(rs, 10);
547}
548
549void penrosectx_init_from_params(
550 PenroseContext *ctx, const struct PenrosePatchParams *ps)
551{
552 size_t i;
553
554 ctx->rs = NULL;
555 ctx->must_free_rs = false;
556 ctx->prototype = penrose_coords_new();
557 penrose_coords_make_space(ctx->prototype, ps->ncoords);
558 for (i = 0; i < ps->ncoords; i++)
559 ctx->prototype->c[i] = ps->coords[i];
560 ctx->prototype->nc = ps->ncoords;
561 ctx->start_vertex = ps->start_vertex;
562 ctx->orientation = ps->orientation;
563}
564
565void penrosectx_cleanup(PenroseContext *ctx)
566{
567 if (ctx->must_free_rs)
568 random_free(ctx->rs);
569 penrose_coords_free(ctx->prototype);
570}
571
572PenroseCoords *penrosectx_initial_coords(PenroseContext *ctx)
573{
574 return penrose_coords_copy(ctx->prototype);
575}
576
577void penrosectx_extend_coords(PenroseContext *ctx, PenroseCoords *pc,
578 size_t n)
579{
580 if (ctx->prototype->nc < n) {
581 penrose_coords_make_space(ctx->prototype, n);
582 while (ctx->prototype->nc < n) {
583 if (!ctx->rs) {
584 /*
585 * For safety, similarly to spectre.c, we respond to a
586 * lack of available random_state by making a
587 * deterministic one.
588 */
589 ctx->rs = random_new("dummy", 5);
590 ctx->must_free_rs = true;
591 }
592
593 ctx->prototype->c[ctx->prototype->nc] = penrose_choose_random(
594 penrose_valid_parents(ctx->prototype->c[ctx->prototype->nc-1]),
595 ctx->rs);
596 ctx->prototype->nc++;
597 }
598 }
599
600 penrose_coords_make_space(pc, n);
601 while (pc->nc < n) {
602 pc->c[pc->nc] = ctx->prototype->c[pc->nc];
603 pc->nc++;
604 }
605}
606
607static Point penrose_triangle_edge_0_length(char c)
608{
609 static const Point one = {{ 1, 0, 0, 0 }};
610 static const Point phi = {{ 1, 0, 1, -1 }};
611 static const Point invphi = {{ 0, 0, 1, -1 }};
612
613 switch (c) {
614 /* P2 tiling: unit-length edges are the long edges, i.e. edges
615 * 1,2 of AB and edge 0 of UV. So AB have edge 0 short. */
616 case 'A': case 'B':
617 return invphi;
618 case 'U': case 'V':
619 return one;
620
621 /* P3 tiling: unit-length edges are edges 1,2 of everything,
622 * so CD have edge 0 short and XY have it long. */
623 case 'C': case 'D':
624 return invphi;
625 default: /* case 'X': case 'Y': */
626 return phi;
627 }
628}
629
630PenroseTriangle *penrose_initial(PenroseContext *ctx)
631{
632 char type = ctx->prototype->c[0];
633 Point origin = {{ 0, 0, 0, 0 }};
634 Point edge0 = penrose_triangle_edge_0_length(type);
635 Point negoffset;
636 size_t i;
637 PenroseTriangle *tri = snew(PenroseTriangle);
638
639 /* Orient the triangle by deciding what vector edge #0 should traverse */
640 edge0 = point_mul(edge0, point_rot(ctx->orientation));
641
642 /* Place the triangle at an arbitrary position, in that orientation */
643 tri->pc = penrose_coords_copy(ctx->prototype);
644 penrose_place(tri, origin, edge0, 0);
645
646 /* Now translate so that the appropriate vertex is at the origin */
647 negoffset = tri->vertices[ctx->start_vertex];
648 for (i = 0; i < 3; i++)
649 tri->vertices[i] = point_sub(tri->vertices[i], negoffset);
650
651 return tri;
652}
653
654PenroseTriangle *penrose_adjacent(PenroseContext *ctx,
655 const PenroseTriangle *src_tri,
656 unsigned src_edge, unsigned *dst_edge_out)
657{
658 unsigned dst_edge;
659 PenroseTriangle *dst_tri = snew(PenroseTriangle);
660 dst_tri->pc = penrose_coords_copy(src_tri->pc);
661 penrosectx_step(ctx, dst_tri->pc, src_edge, &dst_edge);
662 penrose_place(dst_tri, src_tri->vertices[(src_edge+1) % 3],
663 src_tri->vertices[src_edge], dst_edge);
664 if (dst_edge_out)
665 *dst_edge_out = dst_edge;
666 return dst_tri;
667}
668
669static int penrose_cmp(void *av, void *bv)
670{
671 PenroseTriangle *a = (PenroseTriangle *)av, *b = (PenroseTriangle *)bv;
672 size_t i, j;
673
674 /* We should only ever need to compare the first two vertices of
675 * any triangle, because those force the rest */
676 for (i = 0; i < 2; i++) {
677 for (j = 0; j < 4; j++) {
678 int ac = a->vertices[i].coeffs[j], bc = b->vertices[i].coeffs[j];
679 if (ac < bc)
680 return -1;
681 if (ac > bc)
682 return +1;
683 }
684 }
685
686 return 0;
687}
688
689static unsigned penrose_sibling_edge_index(char c)
690{
691 switch (c) {
692 case 'A': case 'U': return 2;
693 case 'B': case 'V': return 1;
694 default: return 0;
695 }
696}
697
698void penrosectx_generate(
699 PenroseContext *ctx,
700 bool (*inbounds)(void *inboundsctx,
701 const PenroseTriangle *tri), void *inboundsctx,
702 void (*tile)(void *tilectx, const Point *vertices), void *tilectx)
703{
704 tree234 *placed = newtree234(penrose_cmp);
705 PenroseTriangle *qhead = NULL, *qtail = NULL;
706
707 {
708 PenroseTriangle *tri = penrose_initial(ctx);
709
710 add234(placed, tri);
711
712 tri->next = NULL;
713 tri->reported = false;
714
715 if (inbounds(inboundsctx, tri))
716 qhead = qtail = tri;
717 }
718
719 while (qhead) {
720 PenroseTriangle *tri = qhead;
721 unsigned edge;
722 unsigned sibling_edge = penrose_sibling_edge_index(tri->pc->c[0]);
723
724 for (edge = 0; edge < 3; edge++) {
725 PenroseTriangle *new_tri, *found_tri;
726
727 new_tri = penrose_adjacent(ctx, tri, edge, NULL);
728
729 if (!inbounds(inboundsctx, new_tri)) {
730 penrose_free(new_tri);
731 continue;
732 }
733
734 found_tri = find234(placed, new_tri, NULL);
735 if (found_tri) {
736 if (edge == sibling_edge && !tri->reported &&
737 !found_tri->reported) {
738 /*
739 * found_tri and tri are opposite halves of the
740 * same tile; both are in the tree, and haven't
741 * yet been reported as a completed tile.
742 */
743 unsigned new_sibling_edge = penrose_sibling_edge_index(
744 found_tri->pc->c[0]);
745 Point tilevertices[4] = {
746 tri->vertices[(sibling_edge + 1) % 3],
747 tri->vertices[(sibling_edge + 2) % 3],
748 found_tri->vertices[(new_sibling_edge + 1) % 3],
749 found_tri->vertices[(new_sibling_edge + 2) % 3],
750 };
751 tile(tilectx, tilevertices);
752
753 tri->reported = true;
754 found_tri->reported = true;
755 }
756
757 penrose_free(new_tri);
758 continue;
759 }
760
761 add234(placed, new_tri);
762 qtail->next = new_tri;
763 qtail = new_tri;
764 new_tri->next = NULL;
765 new_tri->reported = false;
766 }
767
768 qhead = qhead->next;
769 }
770
771 {
772 PenroseTriangle *tri;
773 while ((tri = delpos234(placed, 0)) != NULL)
774 penrose_free(tri);
775 freetree234(placed);
776 }
777}
778
779const char *penrose_tiling_params_invalid(
780 const struct PenrosePatchParams *params, int which)
781{
782 size_t i;
783
784 if (params->ncoords == 0)
785 return "expected at least one coordinate";
786
787 for (i = 0; i < params->ncoords; i++) {
788 if (!penrose_valid_letter(params->coords[i], which))
789 return "invalid coordinate letter";
790 if (i > 0 && !strchr(penrose_valid_parents(params->coords[i-1]),
791 params->coords[i]))
792 return "invalid pair of consecutive coordinates";
793 }
794
795 return NULL;
796}
797
798struct PenroseOutputCtx {
799 int xoff, yoff;
800 Coord xmin, xmax, ymin, ymax;
801
802 penrose_tile_callback_fn external_cb;
803 void *external_cbctx;
804};
805
806static bool inbounds(void *vctx, const PenroseTriangle *tri)
807{
808 struct PenroseOutputCtx *octx = (struct PenroseOutputCtx *)vctx;
809 size_t i;
810
811 for (i = 0; i < 3; i++) {
812 Coord x = point_x(tri->vertices[i]);
813 Coord y = point_y(tri->vertices[i]);
814
815 if (coord_cmp(x, octx->xmin) < 0 || coord_cmp(x, octx->xmax) > 0 ||
816 coord_cmp(y, octx->ymin) < 0 || coord_cmp(y, octx->ymax) > 0)
817 return false;
818 }
819
820 return true;
821}
822
823static void null_output_tile(void *vctx, const Point *vertices)
824{
825}
826
827static void really_output_tile(void *vctx, const Point *vertices)
828{
829 struct PenroseOutputCtx *octx = (struct PenroseOutputCtx *)vctx;
830 size_t i;
831 int coords[16];
832
833 for (i = 0; i < 4; i++) {
834 Coord x = point_x(vertices[i]);
835 Coord y = point_y(vertices[i]);
836
837 coords[4*i + 0] = x.c1 + octx->xoff;
838 coords[4*i + 1] = x.cr5;
839 coords[4*i + 2] = y.c1 + octx->yoff;
840 coords[4*i + 3] = y.cr5;
841 }
842
843 octx->external_cb(octx->external_cbctx, coords);
844}
845
846static void penrose_set_bounds(struct PenroseOutputCtx *octx, int w, int h)
847{
848 octx->xoff = w/2;
849 octx->yoff = h/2;
850 octx->xmin.c1 = -octx->xoff;
851 octx->xmax.c1 = -octx->xoff + w;
852 octx->ymin.c1 = octx->yoff - h;
853 octx->ymax.c1 = octx->yoff;
854 octx->xmin.cr5 = 0;
855 octx->xmax.cr5 = 0;
856 octx->ymin.cr5 = 0;
857 octx->ymax.cr5 = 0;
858}
859
860void penrose_tiling_randomise(struct PenrosePatchParams *params, int which,
861 int w, int h, random_state *rs)
862{
863 PenroseContext ctx[1];
864 struct PenroseOutputCtx octx[1];
865
866 penrose_set_bounds(octx, w, h);
867
868 penrosectx_init_random(ctx, rs, which);
869 penrosectx_generate(ctx, inbounds, octx, null_output_tile, NULL);
870
871 params->orientation = ctx->orientation;
872 params->start_vertex = ctx->start_vertex;
873 params->ncoords = ctx->prototype->nc;
874 params->coords = snewn(params->ncoords, char);
875 memcpy(params->coords, ctx->prototype->c, params->ncoords);
876
877 penrosectx_cleanup(ctx);
878}
879
880void penrose_tiling_generate(
881 const struct PenrosePatchParams *params, int w, int h,
882 penrose_tile_callback_fn cb, void *cbctx)
883{
884 PenroseContext ctx[1];
885 struct PenroseOutputCtx octx[1];
886
887 penrose_set_bounds(octx, w, h);
888 octx->external_cb = cb;
889 octx->external_cbctx = cbctx;
890
891 penrosectx_init_from_params(ctx, params);
892 penrosectx_generate(ctx, inbounds, octx, really_output_tile, octx);
893 penrosectx_cleanup(ctx);
894}