123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895 |
- /*
- * Generate Penrose tilings via combinatorial coordinates.
- *
- * For general explanation of the algorithm:
- * https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/
- *
- * I use exactly the same indexing system here that's described in the
- * article. For the P2 tiling, acute isosceles triangles (half-kites)
- * are assigned letters A,B, and obtuse ones (half-darts) U,V; for P3,
- * acute triangles (half of a thin rhomb) are C,D and obtuse ones
- * (half a thick rhomb) are X,Y. Edges of all triangles are indexed
- * anticlockwise around the triangle, with 0 being the base and 1,2
- * being the two equal legs.
- */
- #include <assert.h>
- #include <stddef.h>
- #include <string.h>
- #include "puzzles.h"
- #include "penrose.h"
- #include "penrose-internal.h"
- #include "tree234.h"
- bool penrose_valid_letter(char c, int which)
- {
- switch (c) {
- case 'A': case 'B': case 'U': case 'V':
- return which == PENROSE_P2;
- case 'C': case 'D': case 'X': case 'Y':
- return which == PENROSE_P3;
- default:
- return false;
- }
- }
- /*
- * Result of attempting a transition within the coordinate system.
- * INTERNAL means we've moved to a different child of the same parent,
- * so the 'internal' substructure gives the type of the new triangle
- * and which edge of it we came in through; EXTERNAL means we've moved
- * out of the parent entirely, and the 'external' substructure tells
- * us which edge of the parent triangle we left by, and if it's
- * divided in two, which end of that edge (-1 for the left end or +1
- * for the right end). If the parent edge is undivided, end == 0.
- *
- * The type FAIL _shouldn't_ ever come up! It occurs if you try to
- * compute an incoming transition with an illegal value of 'end' (i.e.
- * having the wrong idea of whether the edge is divided), or if you
- * refer to a child triangle type that doesn't exist in that parent.
- * If it ever happens in the production code then an assertion will
- * fail. But it might be useful to other users of the same code.
- */
- typedef struct TransitionResult {
- enum { INTERNAL, EXTERNAL, FAIL } type;
- union {
- struct {
- char new_child;
- unsigned char new_edge;
- } internal;
- struct {
- unsigned char parent_edge;
- signed char end;
- } external;
- } u;
- } TransitionResult;
- /* Construction function to make an INTERNAL-type TransitionResult */
- static inline TransitionResult internal(char new_child, unsigned new_edge)
- {
- TransitionResult tr;
- tr.type = INTERNAL;
- tr.u.internal.new_child = new_child;
- tr.u.internal.new_edge = new_edge;
- return tr;
- }
- /* Construction function to make an EXTERNAL-type TransitionResult */
- static inline TransitionResult external(unsigned parent_edge, int end)
- {
- TransitionResult tr;
- tr.type = EXTERNAL;
- tr.u.external.parent_edge = parent_edge;
- tr.u.external.end = end;
- return tr;
- }
- /* Construction function to make a FAIL-type TransitionResult */
- static inline TransitionResult fail(void)
- {
- TransitionResult tr;
- tr.type = FAIL;
- return tr;
- }
- /*
- * Compute a transition out of a triangle. Can return either INTERNAL
- * or EXTERNAL types (or FAIL if it gets invalid data).
- */
- static TransitionResult transition(char parent, char child, unsigned edge)
- {
- switch (parent) {
- case 'A':
- switch (child) {
- case 'A':
- switch (edge) {
- case 0: return external(2, -1);
- case 1: return external(0, 0);
- case 2: return internal('B', 1);
- }
- case 'B':
- switch (edge) {
- case 0: return internal('U', 1);
- case 1: return internal('A', 2);
- case 2: return external(1, +1);
- }
- case 'U':
- switch (edge) {
- case 0: return external(2, +1);
- case 1: return internal('B', 0);
- case 2: return external(1, -1);
- }
- default:
- return fail();
- }
- case 'B':
- switch (child) {
- case 'A':
- switch (edge) {
- case 0: return internal('V', 2);
- case 1: return external(2, -1);
- case 2: return internal('B', 1);
- }
- case 'B':
- switch (edge) {
- case 0: return external(1, +1);
- case 1: return internal('A', 2);
- case 2: return external(0, 0);
- }
- case 'V':
- switch (edge) {
- case 0: return external(1, -1);
- case 1: return external(2, +1);
- case 2: return internal('A', 0);
- }
- default:
- return fail();
- }
- case 'U':
- switch (child) {
- case 'B':
- switch (edge) {
- case 0: return internal('U', 1);
- case 1: return external(2, 0);
- case 2: return external(0, +1);
- }
- case 'U':
- switch (edge) {
- case 0: return external(1, 0);
- case 1: return internal('B', 0);
- case 2: return external(0, -1);
- }
- default:
- return fail();
- }
- case 'V':
- switch (child) {
- case 'A':
- switch (edge) {
- case 0: return internal('V', 2);
- case 1: return external(0, -1);
- case 2: return external(1, 0);
- }
- case 'V':
- switch (edge) {
- case 0: return external(2, 0);
- case 1: return external(0, +1);
- case 2: return internal('A', 0);
- }
- default:
- return fail();
- }
- case 'C':
- switch (child) {
- case 'C':
- switch (edge) {
- case 0: return external(1, +1);
- case 1: return internal('Y', 1);
- case 2: return external(0, 0);
- }
- case 'Y':
- switch (edge) {
- case 0: return external(2, 0);
- case 1: return internal('C', 1);
- case 2: return external(1, -1);
- }
- default:
- return fail();
- }
- case 'D':
- switch (child) {
- case 'D':
- switch (edge) {
- case 0: return external(2, -1);
- case 1: return external(0, 0);
- case 2: return internal('X', 2);
- }
- case 'X':
- switch (edge) {
- case 0: return external(1, 0);
- case 1: return external(2, +1);
- case 2: return internal('D', 2);
- }
- default:
- return fail();
- }
- case 'X':
- switch (child) {
- case 'C':
- switch (edge) {
- case 0: return external(2, +1);
- case 1: return internal('Y', 1);
- case 2: return internal('X', 1);
- }
- case 'X':
- switch (edge) {
- case 0: return external(1, 0);
- case 1: return internal('C', 2);
- case 2: return external(0, -1);
- }
- case 'Y':
- switch (edge) {
- case 0: return external(0, +1);
- case 1: return internal('C', 1);
- case 2: return external(2, -1);
- }
- default:
- return fail();
- }
- case 'Y':
- switch (child) {
- case 'D':
- switch (edge) {
- case 0: return external(1, -1);
- case 1: return internal('Y', 2);
- case 2: return internal('X', 2);
- }
- case 'X':
- switch (edge) {
- case 0: return external(0, -1);
- case 1: return external(1, +1);
- case 2: return internal('D', 2);
- }
- case 'Y':
- switch (edge) {
- case 0: return external(2, 0);
- case 1: return external(0, +1);
- case 2: return internal('D', 1);
- }
- default:
- return fail();
- }
- default:
- return fail();
- }
- }
- /*
- * Compute a transition into a parent triangle, after the above
- * function reported an EXTERNAL transition out of a neighbouring
- * parent and we had to recurse. Because we're coming inwards, this
- * should always return an INTERNAL TransitionResult (or FAIL if it
- * gets invalid data).
- */
- static TransitionResult transition_in(char parent, unsigned edge, int end)
- {
- #define EDGEEND(edge, end) (3 * (edge) + 1 + (end))
- switch (parent) {
- case 'A':
- switch (EDGEEND(edge, end)) {
- case EDGEEND(0, 0): return internal('A', 1);
- case EDGEEND(1, -1): return internal('B', 2);
- case EDGEEND(1, +1): return internal('U', 2);
- case EDGEEND(2, -1): return internal('U', 0);
- case EDGEEND(2, +1): return internal('A', 0);
- default:
- return fail();
- }
- case 'B':
- switch (EDGEEND(edge, end)) {
- case EDGEEND(0, 0): return internal('B', 2);
- case EDGEEND(1, -1): return internal('B', 0);
- case EDGEEND(1, +1): return internal('V', 0);
- case EDGEEND(2, -1): return internal('V', 1);
- case EDGEEND(2, +1): return internal('A', 1);
- default:
- return fail();
- }
- case 'U':
- switch (EDGEEND(edge, end)) {
- case EDGEEND(0, -1): return internal('B', 2);
- case EDGEEND(0, +1): return internal('U', 2);
- case EDGEEND(1, 0): return internal('U', 0);
- case EDGEEND(2, 0): return internal('B', 1);
- default:
- return fail();
- }
- case 'V':
- switch (EDGEEND(edge, end)) {
- case EDGEEND(0, -1): return internal('V', 1);
- case EDGEEND(0, +1): return internal('A', 1);
- case EDGEEND(1, 0): return internal('A', 2);
- case EDGEEND(2, 0): return internal('V', 0);
- default:
- return fail();
- }
- case 'C':
- switch (EDGEEND(edge, end)) {
- case EDGEEND(0, 0): return internal('C', 2);
- case EDGEEND(1, -1): return internal('C', 0);
- case EDGEEND(1, +1): return internal('Y', 2);
- case EDGEEND(2, 0): return internal('Y', 0);
- default:
- return fail();
- }
- case 'D':
- switch (EDGEEND(edge, end)) {
- case EDGEEND(0, 0): return internal('D', 1);
- case EDGEEND(1, 0): return internal('X', 0);
- case EDGEEND(2, -1): return internal('X', 1);
- case EDGEEND(2, +1): return internal('D', 0);
- default:
- return fail();
- }
- case 'X':
- switch (EDGEEND(edge, end)) {
- case EDGEEND(0, -1): return internal('Y', 0);
- case EDGEEND(0, +1): return internal('X', 2);
- case EDGEEND(1, 0): return internal('X', 0);
- case EDGEEND(2, -1): return internal('C', 0);
- case EDGEEND(2, +1): return internal('Y', 2);
- default:
- return fail();
- }
- case 'Y':
- switch (EDGEEND(edge, end)) {
- case EDGEEND(0, +1): return internal('X', 0);
- case EDGEEND(0, -1): return internal('Y', 1);
- case EDGEEND(1, -1): return internal('X', 1);
- case EDGEEND(1, +1): return internal('D', 0);
- case EDGEEND(2, 0): return internal('Y', 0);
- default:
- return fail();
- }
- default:
- return fail();
- }
- #undef EDGEEND
- }
- PenroseCoords *penrose_coords_new(void)
- {
- PenroseCoords *pc = snew(PenroseCoords);
- pc->nc = pc->csize = 0;
- pc->c = NULL;
- return pc;
- }
- void penrose_coords_free(PenroseCoords *pc)
- {
- if (pc) {
- sfree(pc->c);
- sfree(pc);
- }
- }
- void penrose_coords_make_space(PenroseCoords *pc, size_t size)
- {
- if (pc->csize < size) {
- pc->csize = pc->csize * 5 / 4 + 16;
- if (pc->csize < size)
- pc->csize = size;
- pc->c = sresize(pc->c, pc->csize, char);
- }
- }
- PenroseCoords *penrose_coords_copy(PenroseCoords *pc_in)
- {
- PenroseCoords *pc_out = penrose_coords_new();
- penrose_coords_make_space(pc_out, pc_in->nc);
- memcpy(pc_out->c, pc_in->c, pc_in->nc * sizeof(*pc_out->c));
- pc_out->nc = pc_in->nc;
- return pc_out;
- }
- /*
- * The main recursive function for computing the next triangle's
- * combinatorial coordinates.
- */
- static void penrosectx_step_recurse(
- PenroseContext *ctx, PenroseCoords *pc, size_t depth,
- unsigned edge, unsigned *outedge)
- {
- TransitionResult tr;
- penrosectx_extend_coords(ctx, pc, depth+2);
- /* Look up the transition out of the starting triangle */
- tr = transition(pc->c[depth+1], pc->c[depth], edge);
- /* If we've left the parent triangle, recurse to find out what new
- * triangle we've landed in at the next size up, and then call
- * transition_in to find out which child of that parent we're
- * going to */
- if (tr.type == EXTERNAL) {
- unsigned parent_outedge;
- penrosectx_step_recurse(
- ctx, pc, depth+1, tr.u.external.parent_edge, &parent_outedge);
- tr = transition_in(pc->c[depth+1], parent_outedge, tr.u.external.end);
- }
- /* Now we should definitely have ended up in a child of the
- * (perhaps rewritten) parent triangle */
- assert(tr.type == INTERNAL);
- pc->c[depth] = tr.u.internal.new_child;
- *outedge = tr.u.internal.new_edge;
- }
- void penrosectx_step(PenroseContext *ctx, PenroseCoords *pc,
- unsigned edge, unsigned *outedge)
- {
- /* Allow outedge to be NULL harmlessly, just in case */
- unsigned dummy_outedge;
- if (!outedge)
- outedge = &dummy_outedge;
- penrosectx_step_recurse(ctx, pc, 0, edge, outedge);
- }
- static Point penrose_triangle_post_edge(char c, unsigned edge)
- {
- static const Point acute_post_edge[3] = {
- {{-1, 1, 0, 1}}, /* phi * t^3 */
- {{-1, 1, -1, 1}}, /* t^4 */
- {{-1, 1, 0, 0}}, /* 1/phi * t^3 */
- };
- static const Point obtuse_post_edge[3] = {
- {{0, -1, 1, 0}}, /* 1/phi * t^4 */
- {{0, 0, 1, 0}}, /* t^2 */
- {{-1, 0, 0, 1}}, /* phi * t^4 */
- };
- switch (c) {
- case 'A': case 'B': case 'C': case 'D':
- return acute_post_edge[edge];
- default: /* case 'U': case 'V': case 'X': case 'Y': */
- return obtuse_post_edge[edge];
- }
- }
- void penrose_place(PenroseTriangle *tri, Point u, Point v, int index_of_u)
- {
- unsigned i;
- Point here = u, delta = point_sub(v, u);
- for (i = 0; i < 3; i++) {
- unsigned edge = (index_of_u + i) % 3;
- tri->vertices[edge] = here;
- here = point_add(here, delta);
- delta = point_mul(delta, penrose_triangle_post_edge(
- tri->pc->c[0], edge));
- }
- }
- void penrose_free(PenroseTriangle *tri)
- {
- penrose_coords_free(tri->pc);
- sfree(tri);
- }
- static bool penrose_relative_probability(char c)
- {
- /* Penrose tile probability ratios are always phi, so we can
- * approximate that very well using two consecutive Fibonacci
- * numbers */
- switch (c) {
- case 'A': case 'B': case 'X': case 'Y':
- return 165580141;
- case 'C': case 'D': case 'U': case 'V':
- return 102334155;
- default:
- return 0;
- }
- }
- static char penrose_choose_random(const char *possibilities, random_state *rs)
- {
- const char *p;
- unsigned long value, limit = 0;
- for (p = possibilities; *p; p++)
- limit += penrose_relative_probability(*p);
- value = random_upto(rs, limit);
- for (p = possibilities; *p; p++) {
- unsigned long curr = penrose_relative_probability(*p);
- if (value < curr)
- return *p;
- value -= curr;
- }
- assert(false && "Probability overflow!");
- return possibilities[0];
- }
- static const char *penrose_starting_tiles(int which)
- {
- return which == PENROSE_P2 ? "ABUV" : "CDXY";
- }
- static const char *penrose_valid_parents(char tile)
- {
- switch (tile) {
- case 'A': return "ABV";
- case 'B': return "ABU";
- case 'U': return "AU";
- case 'V': return "BV";
- case 'C': return "CX";
- case 'D': return "DY";
- case 'X': return "DXY";
- case 'Y': return "CXY";
- default: return NULL;
- }
- }
- void penrosectx_init_random(PenroseContext *ctx, random_state *rs, int which)
- {
- ctx->rs = rs;
- ctx->must_free_rs = false;
- ctx->prototype = penrose_coords_new();
- penrose_coords_make_space(ctx->prototype, 1);
- ctx->prototype->c[0] = penrose_choose_random(
- penrose_starting_tiles(which), rs);
- ctx->prototype->nc = 1;
- ctx->start_vertex = random_upto(rs, 3);
- ctx->orientation = random_upto(rs, 10);
- }
- void penrosectx_init_from_params(
- PenroseContext *ctx, const struct PenrosePatchParams *ps)
- {
- size_t i;
- ctx->rs = NULL;
- ctx->must_free_rs = false;
- ctx->prototype = penrose_coords_new();
- penrose_coords_make_space(ctx->prototype, ps->ncoords);
- for (i = 0; i < ps->ncoords; i++)
- ctx->prototype->c[i] = ps->coords[i];
- ctx->prototype->nc = ps->ncoords;
- ctx->start_vertex = ps->start_vertex;
- ctx->orientation = ps->orientation;
- }
- void penrosectx_cleanup(PenroseContext *ctx)
- {
- if (ctx->must_free_rs)
- random_free(ctx->rs);
- penrose_coords_free(ctx->prototype);
- }
- PenroseCoords *penrosectx_initial_coords(PenroseContext *ctx)
- {
- return penrose_coords_copy(ctx->prototype);
- }
- void penrosectx_extend_coords(PenroseContext *ctx, PenroseCoords *pc,
- size_t n)
- {
- if (ctx->prototype->nc < n) {
- penrose_coords_make_space(ctx->prototype, n);
- while (ctx->prototype->nc < n) {
- if (!ctx->rs) {
- /*
- * For safety, similarly to spectre.c, we respond to a
- * lack of available random_state by making a
- * deterministic one.
- */
- ctx->rs = random_new("dummy", 5);
- ctx->must_free_rs = true;
- }
- ctx->prototype->c[ctx->prototype->nc] = penrose_choose_random(
- penrose_valid_parents(ctx->prototype->c[ctx->prototype->nc-1]),
- ctx->rs);
- ctx->prototype->nc++;
- }
- }
- penrose_coords_make_space(pc, n);
- while (pc->nc < n) {
- pc->c[pc->nc] = ctx->prototype->c[pc->nc];
- pc->nc++;
- }
- }
- static Point penrose_triangle_edge_0_length(char c)
- {
- static const Point one = {{ 1, 0, 0, 0 }};
- static const Point phi = {{ 1, 0, 1, -1 }};
- static const Point invphi = {{ 0, 0, 1, -1 }};
- switch (c) {
- /* P2 tiling: unit-length edges are the long edges, i.e. edges
- * 1,2 of AB and edge 0 of UV. So AB have edge 0 short. */
- case 'A': case 'B':
- return invphi;
- case 'U': case 'V':
- return one;
- /* P3 tiling: unit-length edges are edges 1,2 of everything,
- * so CD have edge 0 short and XY have it long. */
- case 'C': case 'D':
- return invphi;
- default: /* case 'X': case 'Y': */
- return phi;
- }
- }
- PenroseTriangle *penrose_initial(PenroseContext *ctx)
- {
- char type = ctx->prototype->c[0];
- Point origin = {{ 0, 0, 0, 0 }};
- Point edge0 = penrose_triangle_edge_0_length(type);
- Point negoffset;
- size_t i;
- PenroseTriangle *tri = snew(PenroseTriangle);
- /* Orient the triangle by deciding what vector edge #0 should traverse */
- edge0 = point_mul(edge0, point_rot(ctx->orientation));
- /* Place the triangle at an arbitrary position, in that orientation */
- tri->pc = penrose_coords_copy(ctx->prototype);
- penrose_place(tri, origin, edge0, 0);
- /* Now translate so that the appropriate vertex is at the origin */
- negoffset = tri->vertices[ctx->start_vertex];
- for (i = 0; i < 3; i++)
- tri->vertices[i] = point_sub(tri->vertices[i], negoffset);
- return tri;
- }
- PenroseTriangle *penrose_adjacent(PenroseContext *ctx,
- const PenroseTriangle *src_tri,
- unsigned src_edge, unsigned *dst_edge_out)
- {
- unsigned dst_edge;
- PenroseTriangle *dst_tri = snew(PenroseTriangle);
- dst_tri->pc = penrose_coords_copy(src_tri->pc);
- penrosectx_step(ctx, dst_tri->pc, src_edge, &dst_edge);
- penrose_place(dst_tri, src_tri->vertices[(src_edge+1) % 3],
- src_tri->vertices[src_edge], dst_edge);
- if (dst_edge_out)
- *dst_edge_out = dst_edge;
- return dst_tri;
- }
- static int penrose_cmp(void *av, void *bv)
- {
- PenroseTriangle *a = (PenroseTriangle *)av, *b = (PenroseTriangle *)bv;
- size_t i, j;
- /* We should only ever need to compare the first two vertices of
- * any triangle, because those force the rest */
- for (i = 0; i < 2; i++) {
- for (j = 0; j < 4; j++) {
- int ac = a->vertices[i].coeffs[j], bc = b->vertices[i].coeffs[j];
- if (ac < bc)
- return -1;
- if (ac > bc)
- return +1;
- }
- }
- return 0;
- }
- static unsigned penrose_sibling_edge_index(char c)
- {
- switch (c) {
- case 'A': case 'U': return 2;
- case 'B': case 'V': return 1;
- default: return 0;
- }
- }
- void penrosectx_generate(
- PenroseContext *ctx,
- bool (*inbounds)(void *inboundsctx,
- const PenroseTriangle *tri), void *inboundsctx,
- void (*tile)(void *tilectx, const Point *vertices), void *tilectx)
- {
- tree234 *placed = newtree234(penrose_cmp);
- PenroseTriangle *qhead = NULL, *qtail = NULL;
- {
- PenroseTriangle *tri = penrose_initial(ctx);
- add234(placed, tri);
- tri->next = NULL;
- tri->reported = false;
- if (inbounds(inboundsctx, tri))
- qhead = qtail = tri;
- }
- while (qhead) {
- PenroseTriangle *tri = qhead;
- unsigned edge;
- unsigned sibling_edge = penrose_sibling_edge_index(tri->pc->c[0]);
- for (edge = 0; edge < 3; edge++) {
- PenroseTriangle *new_tri, *found_tri;
- new_tri = penrose_adjacent(ctx, tri, edge, NULL);
- if (!inbounds(inboundsctx, new_tri)) {
- penrose_free(new_tri);
- continue;
- }
- found_tri = find234(placed, new_tri, NULL);
- if (found_tri) {
- if (edge == sibling_edge && !tri->reported &&
- !found_tri->reported) {
- /*
- * found_tri and tri are opposite halves of the
- * same tile; both are in the tree, and haven't
- * yet been reported as a completed tile.
- */
- unsigned new_sibling_edge = penrose_sibling_edge_index(
- found_tri->pc->c[0]);
- Point tilevertices[4] = {
- tri->vertices[(sibling_edge + 1) % 3],
- tri->vertices[(sibling_edge + 2) % 3],
- found_tri->vertices[(new_sibling_edge + 1) % 3],
- found_tri->vertices[(new_sibling_edge + 2) % 3],
- };
- tile(tilectx, tilevertices);
- tri->reported = true;
- found_tri->reported = true;
- }
- penrose_free(new_tri);
- continue;
- }
- add234(placed, new_tri);
- qtail->next = new_tri;
- qtail = new_tri;
- new_tri->next = NULL;
- new_tri->reported = false;
- }
- qhead = qhead->next;
- }
- {
- PenroseTriangle *tri;
- while ((tri = delpos234(placed, 0)) != NULL)
- penrose_free(tri);
- freetree234(placed);
- }
- }
- const char *penrose_tiling_params_invalid(
- const struct PenrosePatchParams *params, int which)
- {
- size_t i;
- if (params->ncoords == 0)
- return "expected at least one coordinate";
- for (i = 0; i < params->ncoords; i++) {
- if (!penrose_valid_letter(params->coords[i], which))
- return "invalid coordinate letter";
- if (i > 0 && !strchr(penrose_valid_parents(params->coords[i-1]),
- params->coords[i]))
- return "invalid pair of consecutive coordinates";
- }
- return NULL;
- }
- struct PenroseOutputCtx {
- int xoff, yoff;
- Coord xmin, xmax, ymin, ymax;
- penrose_tile_callback_fn external_cb;
- void *external_cbctx;
- };
- static bool inbounds(void *vctx, const PenroseTriangle *tri)
- {
- struct PenroseOutputCtx *octx = (struct PenroseOutputCtx *)vctx;
- size_t i;
- for (i = 0; i < 3; i++) {
- Coord x = point_x(tri->vertices[i]);
- Coord y = point_y(tri->vertices[i]);
- if (coord_cmp(x, octx->xmin) < 0 || coord_cmp(x, octx->xmax) > 0 ||
- coord_cmp(y, octx->ymin) < 0 || coord_cmp(y, octx->ymax) > 0)
- return false;
- }
- return true;
- }
- static void null_output_tile(void *vctx, const Point *vertices)
- {
- }
- static void really_output_tile(void *vctx, const Point *vertices)
- {
- struct PenroseOutputCtx *octx = (struct PenroseOutputCtx *)vctx;
- size_t i;
- int coords[16];
- for (i = 0; i < 4; i++) {
- Coord x = point_x(vertices[i]);
- Coord y = point_y(vertices[i]);
- coords[4*i + 0] = x.c1 + octx->xoff;
- coords[4*i + 1] = x.cr5;
- coords[4*i + 2] = y.c1 + octx->yoff;
- coords[4*i + 3] = y.cr5;
- }
- octx->external_cb(octx->external_cbctx, coords);
- }
- static void penrose_set_bounds(struct PenroseOutputCtx *octx, int w, int h)
- {
- octx->xoff = w/2;
- octx->yoff = h/2;
- octx->xmin.c1 = -octx->xoff;
- octx->xmax.c1 = -octx->xoff + w;
- octx->ymin.c1 = octx->yoff - h;
- octx->ymax.c1 = octx->yoff;
- octx->xmin.cr5 = 0;
- octx->xmax.cr5 = 0;
- octx->ymin.cr5 = 0;
- octx->ymax.cr5 = 0;
- }
- void penrose_tiling_randomise(struct PenrosePatchParams *params, int which,
- int w, int h, random_state *rs)
- {
- PenroseContext ctx[1];
- struct PenroseOutputCtx octx[1];
- penrose_set_bounds(octx, w, h);
- penrosectx_init_random(ctx, rs, which);
- penrosectx_generate(ctx, inbounds, octx, null_output_tile, NULL);
- params->orientation = ctx->orientation;
- params->start_vertex = ctx->start_vertex;
- params->ncoords = ctx->prototype->nc;
- params->coords = snewn(params->ncoords, char);
- memcpy(params->coords, ctx->prototype->c, params->ncoords);
- penrosectx_cleanup(ctx);
- }
- void penrose_tiling_generate(
- const struct PenrosePatchParams *params, int w, int h,
- penrose_tile_callback_fn cb, void *cbctx)
- {
- PenroseContext ctx[1];
- struct PenroseOutputCtx octx[1];
- penrose_set_bounds(octx, w, h);
- octx->external_cb = cb;
- octx->external_cbctx = cbctx;
- penrosectx_init_from_params(ctx, params);
- penrosectx_generate(ctx, inbounds, octx, really_output_tile, octx);
- penrosectx_cleanup(ctx);
- }
|