diff options
author | Franklin Wei <franklin@rockbox.org> | 2024-07-22 21:43:25 -0400 |
---|---|---|
committer | Franklin Wei <franklin@rockbox.org> | 2024-07-22 21:44:08 -0400 |
commit | 09aa8de52cb962f1ceebfb1fd44f2c54a924fc5c (patch) | |
tree | 182bd4efb2dc8ca4fcb369d8cccab0c0f290d054 /apps/plugins/puzzles/src/penrose.c | |
parent | c72030f98c953a82ed6f5c7132ad000c3d5f4a16 (diff) | |
download | rockbox-09aa8de52cb962f1ceebfb1fd44f2c54a924fc5c.tar.gz rockbox-09aa8de52cb962f1ceebfb1fd44f2c54a924fc5c.zip |
puzzles: resync with upstream
This brings the puzzles source in sync with Simon's branch, commit fd304c5
(from March 2024), with some added Rockbox-specific compatibility changes:
https://www.franklinwei.com/git/puzzles/commit/?h=rockbox-devel&id=516830d9d76bdfe64fe5ccf2a9b59c33f5c7c078
There are quite a lot of backend changes, including a new "Mosaic" puzzle.
In addition, some new frontend changes were necessary:
- New "Preferences" menu to access the user preferences system.
- Enabled spacebar input for several games.
Change-Id: I94c7df674089c92f32d5f07025f6a1059068af1e
Diffstat (limited to 'apps/plugins/puzzles/src/penrose.c')
-rw-r--r-- | apps/plugins/puzzles/src/penrose.c | 1271 |
1 files changed, 768 insertions, 503 deletions
diff --git a/apps/plugins/puzzles/src/penrose.c b/apps/plugins/puzzles/src/penrose.c index ccde30d8b4..4d7dcc4347 100644 --- a/apps/plugins/puzzles/src/penrose.c +++ b/apps/plugins/puzzles/src/penrose.c | |||
@@ -1,629 +1,894 @@ | |||
1 | /* penrose.c | 1 | /* |
2 | * | 2 | * Generate Penrose tilings via combinatorial coordinates. |
3 | * Penrose tile generator. | ||
4 | * | 3 | * |
5 | * Uses half-tile technique outlined on: | 4 | * For general explanation of the algorithm: |
5 | * https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/ | ||
6 | * | 6 | * |
7 | * http://tartarus.org/simon/20110412-penrose/penrose.xhtml | 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. | ||
8 | */ | 14 | */ |
9 | 15 | ||
10 | #include <assert.h> | 16 | #include <assert.h> |
17 | #include <stddef.h> | ||
11 | #include <string.h> | 18 | #include <string.h> |
12 | #include <math.h> | ||
13 | #include <stdio.h> | ||
14 | 19 | ||
15 | #include "puzzles.h" /* for malloc routines, and PI */ | 20 | #include "puzzles.h" |
16 | #include "penrose.h" | 21 | #include "penrose.h" |
22 | #include "penrose-internal.h" | ||
23 | #include "tree234.h" | ||
17 | 24 | ||
18 | /* ------------------------------------------------------- | 25 | bool penrose_valid_letter(char c, int which) |
19 | * 36-degree basis vector arithmetic routines. | 26 | { |
20 | */ | 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 | } | ||
21 | 36 | ||
22 | /* Imagine drawing a | 37 | /* |
23 | * ten-point 'clock face' like this: | 38 | * Result of attempting a transition within the coordinate system. |
24 | * | 39 | * INTERNAL means we've moved to a different child of the same parent, |
25 | * -E | 40 | * so the 'internal' substructure gives the type of the new triangle |
26 | * -D | A | 41 | * and which edge of it we came in through; EXTERNAL means we've moved |
27 | * \ | / | 42 | * out of the parent entirely, and the 'external' substructure tells |
28 | * -C. \ | / ,B | 43 | * us which edge of the parent triangle we left by, and if it's |
29 | * `-._\|/_,-' | 44 | * divided in two, which end of that edge (-1 for the left end or +1 |
30 | * ,-' /|\ `-. | 45 | * for the right end). If the parent edge is undivided, end == 0. |
31 | * -B' / | \ `C | ||
32 | * / | \ | ||
33 | * -A | D | ||
34 | * E | ||
35 | * | ||
36 | * In case the ASCII art isn't clear, those are supposed to be ten | ||
37 | * vectors of length 1, all sticking out from the origin at equal | ||
38 | * angular spacing (hence 36 degrees). Our basis vectors are A,B,C,D (I | ||
39 | * choose them to be symmetric about the x-axis so that the final | ||
40 | * translation into 2d coordinates will also be symmetric, which I | ||
41 | * think will avoid minor rounding uglinesses), so our vector | ||
42 | * representation sets | ||
43 | * | ||
44 | * A = (1,0,0,0) | ||
45 | * B = (0,1,0,0) | ||
46 | * C = (0,0,1,0) | ||
47 | * D = (0,0,0,1) | ||
48 | * | ||
49 | * The fifth vector E looks at first glance as if it needs to be | ||
50 | * another basis vector, but in fact it doesn't, because it can be | ||
51 | * represented in terms of the other four. Imagine starting from the | ||
52 | * origin and following the path -A, +B, -C, +D: you'll find you've | ||
53 | * traced four sides of a pentagram, and ended up one E-vector away | ||
54 | * from the origin. So we have | ||
55 | * | ||
56 | * E = (-1,1,-1,1) | ||
57 | * | ||
58 | * This tells us that we can rotate any vector in this system by 36 | ||
59 | * degrees: if we start with a*A + b*B + c*C + d*D, we want to end up | ||
60 | * with a*B + b*C + c*D + d*E, and we substitute our identity for E to | ||
61 | * turn that into a*B + b*C + c*D + d*(-A+B-C+D). In other words, | ||
62 | * | ||
63 | * rotate_one_notch_clockwise(a,b,c,d) = (-d, d+a, -d+b, d+c) | ||
64 | * | ||
65 | * and you can verify for yourself that applying that operation | ||
66 | * repeatedly starting with (1,0,0,0) cycles round ten vectors and | ||
67 | * comes back to where it started. | ||
68 | * | ||
69 | * The other operation that may be required is to construct vectors | ||
70 | * with lengths that are multiples of phi. That can be done by | ||
71 | * observing that the vector C-B is parallel to E and has length 1/phi, | ||
72 | * and the vector D-A is parallel to E and has length phi. So this | ||
73 | * tells us that given any vector, we can construct one which points in | ||
74 | * the same direction and is 1/phi or phi times its length, like this: | ||
75 | * | ||
76 | * divide_by_phi(vector) = rotate(vector, 2) - rotate(vector, 3) | ||
77 | * multiply_by_phi(vector) = rotate(vector, 1) - rotate(vector, 4) | ||
78 | * | ||
79 | * where rotate(vector, n) means applying the above | ||
80 | * rotate_one_notch_clockwise primitive n times. Expanding out the | ||
81 | * applications of rotate gives the following direct representation in | ||
82 | * terms of the vector coordinates: | ||
83 | * | ||
84 | * divide_by_phi(a,b,c,d) = (b-d, c+d-b, a+b-c, c-a) | ||
85 | * multiply_by_phi(a,b,c,d) = (a+b-d, c+d, a+b, c+d-a) | ||
86 | * | ||
87 | * and you can verify for yourself that those two operations are | ||
88 | * inverses of each other (as you'd hope!). | ||
89 | * | 46 | * |
90 | * Having done all of this, testing for equality between two vectors is | 47 | * The type FAIL _shouldn't_ ever come up! It occurs if you try to |
91 | * a trivial matter of comparing the four integer coordinates. (Which | 48 | * compute an incoming transition with an illegal value of 'end' (i.e. |
92 | * it _wouldn't_ have been if we'd kept E as a fifth basis vector, | 49 | * having the wrong idea of whether the edge is divided), or if you |
93 | * because then (-1,1,-1,1,0) and (0,0,0,0,1) would have had to be | 50 | * refer to a child triangle type that doesn't exist in that parent. |
94 | * considered identical. So leaving E out is vital.) | 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. | ||
95 | */ | 53 | */ |
96 | 54 | typedef struct TransitionResult { | |
97 | struct vector { int a, b, c, d; }; | 55 | enum { INTERNAL, EXTERNAL, FAIL } type; |
98 | 56 | union { | |
99 | static vector v_origin(void) | 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 */ | ||
69 | static inline TransitionResult internal(char new_child, unsigned new_edge) | ||
100 | { | 70 | { |
101 | vector v; | 71 | TransitionResult tr; |
102 | v.a = v.b = v.c = v.d = 0; | 72 | tr.type = INTERNAL; |
103 | return v; | 73 | tr.u.internal.new_child = new_child; |
74 | tr.u.internal.new_edge = new_edge; | ||
75 | return tr; | ||
104 | } | 76 | } |
105 | 77 | ||
106 | /* We start with a unit vector of B: this means we can easily | 78 | /* Construction function to make an EXTERNAL-type TransitionResult */ |
107 | * draw an isoceles triangle centred on the X axis. */ | 79 | static inline TransitionResult external(unsigned parent_edge, int end) |
108 | #ifdef TEST_VECTORS | 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 | } | ||
109 | 87 | ||
110 | static vector v_unit(void) | 88 | /* Construction function to make a FAIL-type TransitionResult */ |
89 | static inline TransitionResult fail(void) | ||
111 | { | 90 | { |
112 | vector v; | 91 | TransitionResult tr; |
92 | tr.type = FAIL; | ||
93 | return tr; | ||
94 | } | ||
113 | 95 | ||
114 | v.b = 1; | 96 | /* |
115 | v.a = v.c = v.d = 0; | 97 | * Compute a transition out of a triangle. Can return either INTERNAL |
116 | return v; | 98 | * or EXTERNAL types (or FAIL if it gets invalid data). |
99 | */ | ||
100 | static 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 | } | ||
117 | } | 266 | } |
118 | 267 | ||
119 | #endif | 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 | */ | ||
275 | static 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 | } | ||
120 | 359 | ||
121 | #define COS54 0.5877852 | 360 | #undef EDGEEND |
122 | #define SIN54 0.8090169 | 361 | } |
123 | #define COS18 0.9510565 | ||
124 | #define SIN18 0.3090169 | ||
125 | 362 | ||
126 | /* These two are a bit rough-and-ready for now. Note that B/C are | 363 | PenroseCoords *penrose_coords_new(void) |
127 | * 18 degrees from the x-axis, and A/D are 54 degrees. */ | ||
128 | double v_x(vector *vs, int i) | ||
129 | { | 364 | { |
130 | return (vs[i].a + vs[i].d) * COS54 + | 365 | PenroseCoords *pc = snew(PenroseCoords); |
131 | (vs[i].b + vs[i].c) * COS18; | 366 | pc->nc = pc->csize = 0; |
367 | pc->c = NULL; | ||
368 | return pc; | ||
132 | } | 369 | } |
133 | 370 | ||
134 | double v_y(vector *vs, int i) | 371 | void penrose_coords_free(PenroseCoords *pc) |
135 | { | 372 | { |
136 | return (vs[i].a - vs[i].d) * SIN54 + | 373 | if (pc) { |
137 | (vs[i].b - vs[i].c) * SIN18; | 374 | sfree(pc->c); |
138 | 375 | sfree(pc); | |
376 | } | ||
139 | } | 377 | } |
140 | 378 | ||
141 | static vector v_trans(vector v, vector trans) | 379 | void penrose_coords_make_space(PenroseCoords *pc, size_t size) |
142 | { | 380 | { |
143 | v.a += trans.a; | 381 | if (pc->csize < size) { |
144 | v.b += trans.b; | 382 | pc->csize = pc->csize * 5 / 4 + 16; |
145 | v.c += trans.c; | 383 | if (pc->csize < size) |
146 | v.d += trans.d; | 384 | pc->csize = size; |
147 | return v; | 385 | pc->c = sresize(pc->c, pc->csize, char); |
386 | } | ||
148 | } | 387 | } |
149 | 388 | ||
150 | static vector v_rotate_36(vector v) | 389 | PenroseCoords *penrose_coords_copy(PenroseCoords *pc_in) |
151 | { | 390 | { |
152 | vector vv; | 391 | PenroseCoords *pc_out = penrose_coords_new(); |
153 | vv.a = -v.d; | 392 | penrose_coords_make_space(pc_out, pc_in->nc); |
154 | vv.b = v.d + v.a; | 393 | memcpy(pc_out->c, pc_in->c, pc_in->nc * sizeof(*pc_out->c)); |
155 | vv.c = -v.d + v.b; | 394 | pc_out->nc = pc_in->nc; |
156 | vv.d = v.d + v.c; | 395 | return pc_out; |
157 | return vv; | ||
158 | } | 396 | } |
159 | 397 | ||
160 | static vector v_rotate(vector v, int ang) | 398 | /* |
399 | * The main recursive function for computing the next triangle's | ||
400 | * combinatorial coordinates. | ||
401 | */ | ||
402 | static void penrosectx_step_recurse( | ||
403 | PenroseContext *ctx, PenroseCoords *pc, size_t depth, | ||
404 | unsigned edge, unsigned *outedge) | ||
161 | { | 405 | { |
162 | int i; | 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 | } | ||
163 | 423 | ||
164 | assert((ang % 36) == 0); | 424 | /* Now we should definitely have ended up in a child of the |
165 | while (ang < 0) ang += 360; | 425 | * (perhaps rewritten) parent triangle */ |
166 | ang = 360-ang; | 426 | assert(tr.type == INTERNAL); |
167 | for (i = 0; i < (ang/36); i++) | 427 | pc->c[depth] = tr.u.internal.new_child; |
168 | v = v_rotate_36(v); | 428 | *outedge = tr.u.internal.new_edge; |
169 | return v; | ||
170 | } | 429 | } |
171 | 430 | ||
172 | #ifdef TEST_VECTORS | 431 | void penrosectx_step(PenroseContext *ctx, PenroseCoords *pc, |
173 | 432 | unsigned edge, unsigned *outedge) | |
174 | static vector v_scale(vector v, int sc) | ||
175 | { | 433 | { |
176 | v.a *= sc; | 434 | /* Allow outedge to be NULL harmlessly, just in case */ |
177 | v.b *= sc; | 435 | unsigned dummy_outedge; |
178 | v.c *= sc; | 436 | if (!outedge) |
179 | v.d *= sc; | 437 | outedge = &dummy_outedge; |
180 | return v; | ||
181 | } | ||
182 | 438 | ||
183 | #endif | 439 | penrosectx_step_recurse(ctx, pc, 0, edge, outedge); |
440 | } | ||
184 | 441 | ||
185 | static vector v_growphi(vector v) | 442 | static Point penrose_triangle_post_edge(char c, unsigned edge) |
186 | { | 443 | { |
187 | vector vv; | 444 | static const Point acute_post_edge[3] = { |
188 | vv.a = v.a + v.b - v.d; | 445 | {{-1, 1, 0, 1}}, /* phi * t^3 */ |
189 | vv.b = v.c + v.d; | 446 | {{-1, 1, -1, 1}}, /* t^4 */ |
190 | vv.c = v.a + v.b; | 447 | {{-1, 1, 0, 0}}, /* 1/phi * t^3 */ |
191 | vv.d = v.c + v.d - v.a; | 448 | }; |
192 | return vv; | 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 | } | ||
193 | } | 461 | } |
194 | 462 | ||
195 | static vector v_shrinkphi(vector v) | 463 | void penrose_place(PenroseTriangle *tri, Point u, Point v, int index_of_u) |
196 | { | 464 | { |
197 | vector vv; | 465 | unsigned i; |
198 | vv.a = v.b - v.d; | 466 | Point here = u, delta = point_sub(v, u); |
199 | vv.b = v.c + v.d - v.b; | 467 | |
200 | vv.c = v.a + v.b - v.c; | 468 | for (i = 0; i < 3; i++) { |
201 | vv.d = v.c - v.a; | 469 | unsigned edge = (index_of_u + i) % 3; |
202 | return vv; | 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 | } | ||
203 | } | 475 | } |
204 | 476 | ||
205 | #ifdef TEST_VECTORS | 477 | void penrose_free(PenroseTriangle *tri) |
206 | |||
207 | static const char *v_debug(vector v) | ||
208 | { | 478 | { |
209 | static char buf[255]; | 479 | penrose_coords_free(tri->pc); |
210 | sprintf(buf, | 480 | sfree(tri); |
211 | "(%d,%d,%d,%d)[%2.2f,%2.2f]", | ||
212 | v.a, v.b, v.c, v.d, v_x(&v,0), v_y(&v,0)); | ||
213 | return buf; | ||
214 | } | 481 | } |
215 | 482 | ||
216 | #endif | 483 | static bool penrose_relative_probability(char c) |
217 | |||
218 | /* ------------------------------------------------------- | ||
219 | * Tiling routines. | ||
220 | */ | ||
221 | |||
222 | static vector xform_coord(vector vo, int shrink, vector vtrans, int ang) | ||
223 | { | 484 | { |
224 | if (shrink < 0) | 485 | /* Penrose tile probability ratios are always phi, so we can |
225 | vo = v_shrinkphi(vo); | 486 | * approximate that very well using two consecutive Fibonacci |
226 | else if (shrink > 0) | 487 | * numbers */ |
227 | vo = v_growphi(vo); | 488 | switch (c) { |
228 | 489 | case 'A': case 'B': case 'X': case 'Y': | |
229 | vo = v_rotate(vo, ang); | 490 | return 165580141; |
230 | vo = v_trans(vo, vtrans); | 491 | case 'C': case 'D': case 'U': case 'V': |
231 | 492 | return 102334155; | |
232 | return vo; | 493 | default: |
494 | return 0; | ||
495 | } | ||
233 | } | 496 | } |
234 | 497 | ||
235 | 498 | static char penrose_choose_random(const char *possibilities, random_state *rs) | |
236 | #define XFORM(n,o,s,a) vs[(n)] = xform_coord(v_edge, (s), vs[(o)], (a)) | ||
237 | |||
238 | static int penrose_p2_small(penrose_state *state, int depth, int flip, | ||
239 | vector v_orig, vector v_edge); | ||
240 | |||
241 | static int penrose_p2_large(penrose_state *state, int depth, int flip, | ||
242 | vector v_orig, vector v_edge) | ||
243 | { | 499 | { |
244 | vector vv_orig, vv_edge; | 500 | const char *p; |
245 | 501 | unsigned long value, limit = 0; | |
246 | #ifdef DEBUG_PENROSE | 502 | |
247 | { | 503 | for (p = possibilities; *p; p++) |
248 | vector vs[3]; | 504 | limit += penrose_relative_probability(*p); |
249 | vs[0] = v_orig; | 505 | value = random_upto(rs, limit); |
250 | XFORM(1, 0, 0, 0); | 506 | for (p = possibilities; *p; p++) { |
251 | XFORM(2, 0, 0, -36*flip); | 507 | unsigned long curr = penrose_relative_probability(*p); |
252 | 508 | if (value < curr) | |
253 | state->new_tile(state, vs, 3, depth); | 509 | return *p; |
510 | value -= curr; | ||
254 | } | 511 | } |
255 | #endif | 512 | assert(false && "Probability overflow!"); |
256 | 513 | return possibilities[0]; | |
257 | if (flip > 0) { | 514 | } |
258 | vector vs[4]; | ||
259 | 515 | ||
260 | vs[0] = v_orig; | 516 | static const char *penrose_starting_tiles(int which) |
261 | XFORM(1, 0, 0, -36); | 517 | { |
262 | XFORM(2, 0, 0, 0); | 518 | return which == PENROSE_P2 ? "ABUV" : "CDXY"; |
263 | XFORM(3, 0, 0, 36); | 519 | } |
264 | 520 | ||
265 | state->new_tile(state, vs, 4, depth); | 521 | static 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; | ||
266 | } | 533 | } |
267 | if (depth >= state->max_depth) return 0; | 534 | } |
268 | |||
269 | vv_orig = v_trans(v_orig, v_rotate(v_edge, -36*flip)); | ||
270 | vv_edge = v_rotate(v_edge, 108*flip); | ||
271 | |||
272 | penrose_p2_small(state, depth+1, flip, | ||
273 | v_orig, v_shrinkphi(v_edge)); | ||
274 | 535 | ||
275 | penrose_p2_large(state, depth+1, flip, | 536 | void penrosectx_init_random(PenroseContext *ctx, random_state *rs, int which) |
276 | vv_orig, v_shrinkphi(vv_edge)); | 537 | { |
277 | penrose_p2_large(state, depth+1, -flip, | 538 | ctx->rs = rs; |
278 | vv_orig, v_shrinkphi(vv_edge)); | 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 | } | ||
279 | 548 | ||
280 | return 0; | 549 | void 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; | ||
281 | } | 563 | } |
282 | 564 | ||
283 | static int penrose_p2_small(penrose_state *state, int depth, int flip, | 565 | void penrosectx_cleanup(PenroseContext *ctx) |
284 | vector v_orig, vector v_edge) | ||
285 | { | 566 | { |
286 | vector vv_orig; | 567 | if (ctx->must_free_rs) |
568 | random_free(ctx->rs); | ||
569 | penrose_coords_free(ctx->prototype); | ||
570 | } | ||
287 | 571 | ||
288 | #ifdef DEBUG_PENROSE | 572 | PenroseCoords *penrosectx_initial_coords(PenroseContext *ctx) |
289 | { | 573 | { |
290 | vector vs[3]; | 574 | return penrose_coords_copy(ctx->prototype); |
291 | vs[0] = v_orig; | 575 | } |
292 | XFORM(1, 0, 0, 0); | ||
293 | XFORM(2, 0, -1, -36*flip); | ||
294 | 576 | ||
295 | state->new_tile(state, vs, 3, depth); | 577 | void 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 | } | ||
296 | } | 598 | } |
297 | #endif | ||
298 | |||
299 | if (flip > 0) { | ||
300 | vector vs[4]; | ||
301 | |||
302 | vs[0] = v_orig; | ||
303 | XFORM(1, 0, 0, -72); | ||
304 | XFORM(2, 0, -1, -36); | ||
305 | XFORM(3, 0, 0, 0); | ||
306 | 599 | ||
307 | state->new_tile(state, vs, 4, depth); | 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++; | ||
308 | } | 604 | } |
309 | |||
310 | if (depth >= state->max_depth) return 0; | ||
311 | |||
312 | vv_orig = v_trans(v_orig, v_edge); | ||
313 | |||
314 | penrose_p2_large(state, depth+1, -flip, | ||
315 | v_orig, v_shrinkphi(v_rotate(v_edge, -36*flip))); | ||
316 | |||
317 | penrose_p2_small(state, depth+1, flip, | ||
318 | vv_orig, v_shrinkphi(v_rotate(v_edge, -144*flip))); | ||
319 | |||
320 | return 0; | ||
321 | } | 605 | } |
322 | 606 | ||
323 | static int penrose_p3_small(penrose_state *state, int depth, int flip, | 607 | static Point penrose_triangle_edge_0_length(char c) |
324 | vector v_orig, vector v_edge); | ||
325 | |||
326 | static int penrose_p3_large(penrose_state *state, int depth, int flip, | ||
327 | vector v_orig, vector v_edge) | ||
328 | { | 608 | { |
329 | vector vv_orig; | 609 | static const Point one = {{ 1, 0, 0, 0 }}; |
330 | 610 | static const Point phi = {{ 1, 0, 1, -1 }}; | |
331 | #ifdef DEBUG_PENROSE | 611 | static const Point invphi = {{ 0, 0, 1, -1 }}; |
332 | { | 612 | |
333 | vector vs[3]; | 613 | switch (c) { |
334 | vs[0] = v_orig; | 614 | /* P2 tiling: unit-length edges are the long edges, i.e. edges |
335 | XFORM(1, 0, 1, 0); | 615 | * 1,2 of AB and edge 0 of UV. So AB have edge 0 short. */ |
336 | XFORM(2, 0, 0, -36*flip); | 616 | case 'A': case 'B': |
337 | 617 | return invphi; | |
338 | state->new_tile(state, vs, 3, depth); | 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; | ||
339 | } | 627 | } |
340 | #endif | 628 | } |
341 | 629 | ||
342 | if (flip > 0) { | 630 | PenroseTriangle *penrose_initial(PenroseContext *ctx) |
343 | vector vs[4]; | 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 | } | ||
344 | 653 | ||
345 | vs[0] = v_orig; | 654 | PenroseTriangle *penrose_adjacent(PenroseContext *ctx, |
346 | XFORM(1, 0, 0, -36); | 655 | const PenroseTriangle *src_tri, |
347 | XFORM(2, 0, 1, 0); | 656 | unsigned src_edge, unsigned *dst_edge_out) |
348 | XFORM(3, 0, 0, 36); | 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 | } | ||
349 | 668 | ||
350 | state->new_tile(state, vs, 4, depth); | 669 | static 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 | } | ||
351 | } | 684 | } |
352 | if (depth >= state->max_depth) return 0; | ||
353 | |||
354 | vv_orig = v_trans(v_orig, v_edge); | ||
355 | |||
356 | penrose_p3_large(state, depth+1, -flip, | ||
357 | vv_orig, v_shrinkphi(v_rotate(v_edge, 180))); | ||
358 | |||
359 | penrose_p3_small(state, depth+1, flip, | ||
360 | vv_orig, v_shrinkphi(v_rotate(v_edge, -108*flip))); | ||
361 | |||
362 | vv_orig = v_trans(v_orig, v_growphi(v_edge)); | ||
363 | |||
364 | penrose_p3_large(state, depth+1, flip, | ||
365 | vv_orig, v_shrinkphi(v_rotate(v_edge, -144*flip))); | ||
366 | |||
367 | 685 | ||
368 | return 0; | 686 | return 0; |
369 | } | 687 | } |
370 | 688 | ||
371 | static int penrose_p3_small(penrose_state *state, int depth, int flip, | 689 | static unsigned penrose_sibling_edge_index(char c) |
372 | vector v_orig, vector v_edge) | ||
373 | { | 690 | { |
374 | vector vv_orig; | 691 | switch (c) { |
375 | 692 | case 'A': case 'U': return 2; | |
376 | #ifdef DEBUG_PENROSE | 693 | case 'B': case 'V': return 1; |
377 | { | 694 | default: return 0; |
378 | vector vs[3]; | ||
379 | vs[0] = v_orig; | ||
380 | XFORM(1, 0, 0, 0); | ||
381 | XFORM(2, 0, 0, -36*flip); | ||
382 | |||
383 | state->new_tile(state, vs, 3, depth); | ||
384 | } | 695 | } |
385 | #endif | 696 | } |
386 | |||
387 | if (flip > 0) { | ||
388 | vector vs[4]; | ||
389 | |||
390 | vs[0] = v_orig; | ||
391 | XFORM(1, 0, 0, -36); | ||
392 | XFORM(3, 0, 0, 0); | ||
393 | XFORM(2, 3, 0, -36); | ||
394 | 697 | ||
395 | state->new_tile(state, vs, 4, depth); | 698 | void penrosectx_generate( |
396 | } | 699 | PenroseContext *ctx, |
397 | if (depth >= state->max_depth) return 0; | 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; | ||
398 | 706 | ||
399 | /* NB these two are identical to the first two of p3_large. */ | 707 | { |
400 | vv_orig = v_trans(v_orig, v_edge); | 708 | PenroseTriangle *tri = penrose_initial(ctx); |
401 | 709 | ||
402 | penrose_p3_large(state, depth+1, -flip, | 710 | add234(placed, tri); |
403 | vv_orig, v_shrinkphi(v_rotate(v_edge, 180))); | ||
404 | 711 | ||
405 | penrose_p3_small(state, depth+1, flip, | 712 | tri->next = NULL; |
406 | vv_orig, v_shrinkphi(v_rotate(v_edge, -108*flip))); | 713 | tri->reported = false; |
407 | 714 | ||
408 | return 0; | 715 | if (inbounds(inboundsctx, tri)) |
409 | } | 716 | qhead = qtail = tri; |
717 | } | ||
410 | 718 | ||
411 | /* ------------------------------------------------------- | 719 | while (qhead) { |
412 | * Utility routines. | 720 | PenroseTriangle *tri = qhead; |
413 | */ | 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 | } | ||
414 | 767 | ||
415 | double penrose_side_length(double start_size, int depth) | 768 | qhead = qhead->next; |
416 | { | 769 | } |
417 | return start_size / pow(PHI, depth); | ||
418 | } | ||
419 | 770 | ||
420 | void penrose_count_tiles(int depth, int *nlarge, int *nsmall) | 771 | { |
421 | { | 772 | PenroseTriangle *tri; |
422 | /* Steal sgt's fibonacci thingummy. */ | 773 | while ((tri = delpos234(placed, 0)) != NULL) |
774 | penrose_free(tri); | ||
775 | freetree234(placed); | ||
776 | } | ||
423 | } | 777 | } |
424 | 778 | ||
425 | /* | 779 | const char *penrose_tiling_params_invalid( |
426 | * It turns out that an acute isosceles triangle with sides in ratio 1:phi:phi | 780 | const struct PenrosePatchParams *params, int which) |
427 | * has an incentre which is conveniently 2*phi^-2 of the way from the apex to | ||
428 | * the base. Why's that convenient? Because: if we situate the incentre of the | ||
429 | * triangle at the origin, then we can place the apex at phi^-2 * (B+C), and | ||
430 | * the other two vertices at apex-B and apex-C respectively. So that's an acute | ||
431 | * triangle with its long sides of unit length, covering a circle about the | ||
432 | * origin of radius 1-(2*phi^-2), which is conveniently enough phi^-3. | ||
433 | * | ||
434 | * (later mail: this is an overestimate by about 5%) | ||
435 | */ | ||
436 | |||
437 | int penrose(penrose_state *state, int which, int angle) | ||
438 | { | 781 | { |
439 | vector vo = v_origin(); | 782 | size_t i; |
440 | vector vb = v_origin(); | ||
441 | |||
442 | vo.b = vo.c = -state->start_size; | ||
443 | vo = v_shrinkphi(v_shrinkphi(vo)); | ||
444 | |||
445 | vb.b = state->start_size; | ||
446 | 783 | ||
447 | vo = v_rotate(vo, angle); | 784 | if (params->ncoords == 0) |
448 | vb = v_rotate(vb, angle); | 785 | return "expected at least one coordinate"; |
449 | 786 | ||
450 | if (which == PENROSE_P2) | 787 | for (i = 0; i < params->ncoords; i++) { |
451 | return penrose_p2_large(state, 0, 1, vo, vb); | 788 | if (!penrose_valid_letter(params->coords[i], which)) |
452 | else | 789 | return "invalid coordinate letter"; |
453 | return penrose_p3_small(state, 0, 1, vo, vb); | 790 | if (i > 0 && !strchr(penrose_valid_parents(params->coords[i-1]), |
454 | } | 791 | params->coords[i])) |
455 | 792 | return "invalid pair of consecutive coordinates"; | |
456 | /* | ||
457 | * We're asked for a MxN grid, which just means a tiling fitting into roughly | ||
458 | * an MxN space in some kind of reasonable unit - say, the side length of the | ||
459 | * two-arrow edges of the tiles. By some reasoning in a previous email, that | ||
460 | * means we want to pick some subarea of a circle of radius 3.11*sqrt(M^2+N^2). | ||
461 | * To cover that circle, we need to subdivide a triangle large enough that it | ||
462 | * contains a circle of that radius. | ||
463 | * | ||
464 | * Hence: start with those three vectors marking triangle vertices, scale them | ||
465 | * all up by phi repeatedly until the radius of the inscribed circle gets | ||
466 | * bigger than the target, and then recurse into that triangle with the same | ||
467 | * recursion depth as the number of times you scaled up. That will give you | ||
468 | * tiles of unit side length, covering a circle big enough that if you randomly | ||
469 | * choose an orientation and coordinates within the circle, you'll be able to | ||
470 | * get any valid piece of Penrose tiling of size MxN. | ||
471 | */ | ||
472 | #define INCIRCLE_RADIUS 0.22426 /* phi^-3 less 5%: see above */ | ||
473 | |||
474 | void penrose_calculate_size(int which, int tilesize, int w, int h, | ||
475 | double *required_radius, int *start_size, int *depth) | ||
476 | { | ||
477 | double rradius, size; | ||
478 | int n = 0; | ||
479 | |||
480 | /* | ||
481 | * Fudge factor to scale P2 and P3 tilings differently. This | ||
482 | * doesn't seem to have much relevance to questions like the | ||
483 | * average number of tiles per unit area; it's just aesthetic. | ||
484 | */ | ||
485 | if (which == PENROSE_P2) | ||
486 | tilesize = tilesize * 3 / 2; | ||
487 | else | ||
488 | tilesize = tilesize * 5 / 4; | ||
489 | |||
490 | rradius = tilesize * 3.11 * sqrt((double)(w*w + h*h)); | ||
491 | size = tilesize; | ||
492 | |||
493 | while ((size * INCIRCLE_RADIUS) < rradius) { | ||
494 | n++; | ||
495 | size = size * PHI; | ||
496 | } | 793 | } |
497 | 794 | ||
498 | *start_size = (int)size; | 795 | return NULL; |
499 | *depth = n; | ||
500 | *required_radius = rradius; | ||
501 | } | 796 | } |
502 | 797 | ||
503 | /* ------------------------------------------------------- | 798 | struct PenroseOutputCtx { |
504 | * Test code. | 799 | int xoff, yoff; |
505 | */ | 800 | Coord xmin, xmax, ymin, ymax; |
506 | |||
507 | #ifdef TEST_PENROSE | ||
508 | |||
509 | #include <stdio.h> | ||
510 | #include <string.h> | ||
511 | 801 | ||
512 | int show_recursion = 0; | 802 | penrose_tile_callback_fn external_cb; |
513 | int ntiles, nfinal; | 803 | void *external_cbctx; |
804 | }; | ||
514 | 805 | ||
515 | int test_cb(penrose_state *state, vector *vs, int n, int depth) | 806 | static bool inbounds(void *vctx, const PenroseTriangle *tri) |
516 | { | 807 | { |
517 | int i, xoff = 0, yoff = 0; | 808 | struct PenroseOutputCtx *octx = (struct PenroseOutputCtx *)vctx; |
518 | double l = penrose_side_length(state->start_size, depth); | 809 | size_t i; |
519 | double rball = l / 10.0; | ||
520 | const char *col; | ||
521 | 810 | ||
522 | ntiles++; | 811 | for (i = 0; i < 3; i++) { |
523 | if (state->max_depth == depth) { | 812 | Coord x = point_x(tri->vertices[i]); |
524 | col = n == 4 ? "black" : "green"; | 813 | Coord y = point_y(tri->vertices[i]); |
525 | nfinal++; | ||
526 | } else { | ||
527 | if (!show_recursion) | ||
528 | return 0; | ||
529 | col = n == 4 ? "red" : "blue"; | ||
530 | } | ||
531 | if (n != 4) yoff = state->start_size; | ||
532 | 814 | ||
533 | printf("<polygon points=\""); | 815 | if (coord_cmp(x, octx->xmin) < 0 || coord_cmp(x, octx->xmax) > 0 || |
534 | for (i = 0; i < n; i++) { | 816 | coord_cmp(y, octx->ymin) < 0 || coord_cmp(y, octx->ymax) > 0) |
535 | printf("%s%f,%f", (i == 0) ? "" : " ", | 817 | return false; |
536 | v_x(vs, i) + xoff, v_y(vs, i) + yoff); | ||
537 | } | 818 | } |
538 | printf("\" style=\"fill: %s; fill-opacity: 0.2; stroke: %s\" />\n", col, col); | ||
539 | printf("<ellipse cx=\"%f\" cy=\"%f\" rx=\"%f\" ry=\"%f\" fill=\"%s\" />", | ||
540 | v_x(vs, 0) + xoff, v_y(vs, 0) + yoff, rball, rball, col); | ||
541 | 819 | ||
542 | return 0; | 820 | return true; |
543 | } | 821 | } |
544 | 822 | ||
545 | void usage_exit(void) | 823 | static void null_output_tile(void *vctx, const Point *vertices) |
546 | { | 824 | { |
547 | fprintf(stderr, "Usage: penrose-test [--recursion] P2|P3 SIZE DEPTH\n"); | ||
548 | exit(1); | ||
549 | } | 825 | } |
550 | 826 | ||
551 | int main(int argc, char *argv[]) | 827 | static void really_output_tile(void *vctx, const Point *vertices) |
552 | { | 828 | { |
553 | penrose_state ps; | 829 | struct PenroseOutputCtx *octx = (struct PenroseOutputCtx *)vctx; |
554 | int which = 0; | 830 | size_t i; |
555 | 831 | int coords[16]; | |
556 | while (--argc > 0) { | 832 | |
557 | char *p = *++argv; | 833 | for (i = 0; i < 4; i++) { |
558 | if (!strcmp(p, "-h") || !strcmp(p, "--help")) { | 834 | Coord x = point_x(vertices[i]); |
559 | usage_exit(); | 835 | Coord y = point_y(vertices[i]); |
560 | } else if (!strcmp(p, "--recursion")) { | 836 | |
561 | show_recursion = 1; | 837 | coords[4*i + 0] = x.c1 + octx->xoff; |
562 | } else if (*p == '-') { | 838 | coords[4*i + 1] = x.cr5; |
563 | fprintf(stderr, "Unrecognised option '%s'\n", p); | 839 | coords[4*i + 2] = y.c1 + octx->yoff; |
564 | exit(1); | 840 | coords[4*i + 3] = y.cr5; |
565 | } else { | ||
566 | break; | ||
567 | } | ||
568 | } | 841 | } |
569 | 842 | ||
570 | if (argc < 3) usage_exit(); | 843 | octx->external_cb(octx->external_cbctx, coords); |
571 | 844 | } | |
572 | if (strcmp(argv[0], "P2") == 0) which = PENROSE_P2; | ||
573 | else if (strcmp(argv[0], "P3") == 0) which = PENROSE_P3; | ||
574 | else usage_exit(); | ||
575 | |||
576 | ps.start_size = atoi(argv[1]); | ||
577 | ps.max_depth = atoi(argv[2]); | ||
578 | ps.new_tile = test_cb; | ||
579 | |||
580 | ntiles = nfinal = 0; | ||
581 | |||
582 | printf("\ | ||
583 | <?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n\ | ||
584 | <!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 20010904//EN\"\n\ | ||
585 | \"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">\n\ | ||
586 | \n\ | ||
587 | <svg xmlns=\"http://www.w3.org/2000/svg\"\n\ | ||
588 | xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n"); | ||
589 | |||
590 | printf("<g>\n"); | ||
591 | penrose(&ps, which); | ||
592 | printf("</g>\n"); | ||
593 | 845 | ||
594 | printf("<!-- %d tiles and %d leaf tiles total -->\n", | 846 | static void penrose_set_bounds(struct PenroseOutputCtx *octx, int w, int h) |
595 | ntiles, nfinal); | 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 | } | ||
596 | 859 | ||
597 | printf("</svg>"); | 860 | void 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]; | ||
598 | 865 | ||
599 | return 0; | 866 | penrose_set_bounds(octx, w, h); |
600 | } | ||
601 | 867 | ||
602 | #endif | 868 | penrosectx_init_random(ctx, rs, which); |
869 | penrosectx_generate(ctx, inbounds, octx, null_output_tile, NULL); | ||
603 | 870 | ||
604 | #ifdef TEST_VECTORS | 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); | ||
605 | 876 | ||
606 | static void dbgv(const char *msg, vector v) | 877 | penrosectx_cleanup(ctx); |
607 | { | ||
608 | printf("%s: %s\n", msg, v_debug(v)); | ||
609 | } | 878 | } |
610 | 879 | ||
611 | int main(int argc, const char *argv[]) | 880 | void penrose_tiling_generate( |
881 | const struct PenrosePatchParams *params, int w, int h, | ||
882 | penrose_tile_callback_fn cb, void *cbctx) | ||
612 | { | 883 | { |
613 | vector v = v_unit(); | 884 | PenroseContext ctx[1]; |
885 | struct PenroseOutputCtx octx[1]; | ||
614 | 886 | ||
615 | dbgv("unit vector", v); | 887 | penrose_set_bounds(octx, w, h); |
616 | v = v_rotate(v, 36); | 888 | octx->external_cb = cb; |
617 | dbgv("rotated 36", v); | 889 | octx->external_cbctx = cbctx; |
618 | v = v_scale(v, 2); | ||
619 | dbgv("scaled x2", v); | ||
620 | v = v_shrinkphi(v); | ||
621 | dbgv("shrunk phi", v); | ||
622 | v = v_rotate(v, -36); | ||
623 | dbgv("rotated -36", v); | ||
624 | 890 | ||
625 | return 0; | 891 | penrosectx_init_from_params(ctx, params); |
892 | penrosectx_generate(ctx, inbounds, octx, really_output_tile, octx); | ||
893 | penrosectx_cleanup(ctx); | ||
626 | } | 894 | } |
627 | |||
628 | #endif | ||
629 | /* vim: set shiftwidth=4 tabstop=8: */ | ||