1 /* -*- Mode: C; tab-width: 4 -*- */
2 /* turtle --- fractal curves */
3
4 #if 0
5 static const char sccsid[] = "@(#)turtle.c 5.00 2000/11/01 xlockmore";
6
7 #endif
8
9 /*-
10 * Copyright (c) 1996 by David Bagley.
11 *
12 * Permission to use, copy, modify, and distribute this software and its
13 * documentation for any purpose and without fee is hereby granted,
14 * provided that the above copyright notice appear in all copies and that
15 * both that copyright notice and this permission notice appear in
16 * supporting documentation.
17 *
18 * This file is provided AS IS with no warranties of any kind. The author
19 * shall have no liability with respect to the infringement of copyrights,
20 * trade secrets or any patents by this file or any part thereof. In no
21 * event will the author be liable for any lost revenue or profits or
22 * other special, indirect and consequential damages.
23 *
24 * Revision History:
25 * 01-Nov-2000: Allocation checks
26 * 10-May-1997: Compatible with xscreensaver
27 * 01-Dec-1996: Not too proud how I hacked in 2 more curves
28 * 30-Sep-1996: started with Hilbert curve, David Bagley
29 * From Fractal Programming in C by Roger T. Stevens
30 */
31
32 #ifdef STANDALONE
33 #define MODE_turtle
34 #define DEFAULTS "*delay: 1000000 \n" \
35 "*cycles: 20 \n" \
36 "*ncolors: 64 \n" \
37
38 # define free_turtle 0
39 # define reshape_turtle 0
40 # define turtle_handle_event 0
41 #include "xlockmore.h" /* in xscreensaver distribution */
42 #else /* STANDALONE */
43 #include "xlock.h" /* in xlockmore distribution */
44 #endif /* STANDALONE */
45
46 #ifdef MODE_turtle
47
48 ENTRYPOINT ModeSpecOpt turtle_opts =
49 {0, (XrmOptionDescRec *) NULL, 0, (argtype *) NULL, (OptionStruct *) NULL};
50
51 #ifdef USE_MODULES
52 ModStruct turtle_description =
53 {"turtle", "init_turtle", "draw_turtle", "release_turtle",
54 "init_turtle", "init_turtle", (char *) NULL, &turtle_opts,
55 1000000, 1, 20, 1, 64, 1.0, "",
56 "Shows turtle fractals", 0, NULL};
57
58 #endif
59
60 #define HILBERT 0 /* Not exactly a turtle algorithm... p199 */
61 #define CESARO_VAR 1 /* Telephone curve p168 */
62 #define HARTER_HEIGHTWAY 2 /* Dragon curve p292 */
63 #define TURTLE_CURVES 3
64
65 #define POINT(x_1,y_1,x_2,y_2) (((x_2)==(x_1))?(((y_2)>(y_1))?90.0:270.0):\
66 ((x_2)>(x_1))?(atan(((y_2)-(y_1))/((x_2)-(x_1)))*(180.0/M_PI)):\
67 (atan(((y_2)-(y_1))/((x_2)-(x_1)))*(180.0/M_PI)+180.0))
68 #define TURN(theta, angle) ((theta)+=(angle))
69 #define STEP(x, y, r, theta) ((x)+=(r)*cos((theta)*M_PI/180.0)),\
70 ((y)+=(r)*sin((theta)*M_PI/180.0))
71
72 typedef struct {
73 double r, theta, x, y;
74 } turtletype;
75
76 typedef struct {
77 double x, y;
78 } complextype;
79
80 typedef struct {
81 int width, height;
82 int time;
83 int level;
84 int curve;
85 int r, maxlevel, min, dir;
86 XPoint pt1, pt2;
87 XPoint start;
88 turtletype turtle;
89 int sign;
90 } turtlestruct;
91
92 static turtlestruct *turtles = (turtlestruct *) NULL;
93
94 static void
generate_hilbert(ModeInfo * mi,int r1,int r2)95 generate_hilbert(ModeInfo * mi, int r1, int r2)
96 {
97 Display *display = MI_DISPLAY(mi);
98 Window window = MI_WINDOW(mi);
99 GC gc = MI_GC(mi);
100 turtlestruct *tp = &turtles[MI_SCREEN(mi)];
101
102 tp->level--;
103
104 if (tp->level > 0)
105 generate_hilbert(mi, r2, r1);
106
107 tp->pt2.x += r1;
108 tp->pt2.y += r2;
109 XDrawLine(display, window, gc,
110 tp->pt1.x, tp->pt1.y, tp->pt2.x, tp->pt2.y);
111 tp->pt1.x = tp->pt2.x;
112 tp->pt1.y = tp->pt2.y;
113
114 if (tp->level > 0)
115 generate_hilbert(mi, r1, r2);
116
117 tp->pt2.x += r2;
118 tp->pt2.y += r1;
119 XDrawLine(display, window, gc,
120 tp->pt1.x, tp->pt1.y, tp->pt2.x, tp->pt2.y);
121 tp->pt1.x = tp->pt2.x;
122 tp->pt1.y = tp->pt2.y;
123
124 if (tp->level > 0)
125 generate_hilbert(mi, r1, r2);
126
127 tp->pt2.x -= r1;
128 tp->pt2.y -= r2;
129 XDrawLine(display, window, gc,
130 tp->pt1.x, tp->pt1.y, tp->pt2.x, tp->pt2.y);
131 tp->pt1.x = tp->pt2.x;
132 tp->pt1.y = tp->pt2.y;
133
134 if (tp->level > 0)
135 generate_hilbert(mi, -r2, -r1);
136
137 tp->level++;
138 }
139
140 static void
generate_cesarovar(ModeInfo * mi,double pt1x,double pt1y,double pt2x,double pt2y,int level,int sign)141 generate_cesarovar(ModeInfo * mi, double pt1x, double pt1y,
142 double pt2x, double pt2y, int level, int sign)
143 {
144 Display *display = MI_DISPLAY(mi);
145 Window window = MI_WINDOW(mi);
146 GC gc = MI_GC(mi);
147 turtlestruct *tp = &turtles[MI_SCREEN(mi)];
148 complextype points[4];
149
150 level--;
151
152 tp->turtle.r = sqrt((double) ((pt2x - pt1x) * (pt2x - pt1x) +
153 (pt2y - pt1y) * (pt2y - pt1y))) / 2.0;
154 points[0].x = pt1x;
155 points[0].y = pt1y;
156 points[2].x = pt2x;
157 points[2].y = pt2y;
158 tp->turtle.theta = POINT(pt1x, pt1y, pt2x, pt2y);
159 tp->turtle.x = pt1x;
160 tp->turtle.y = pt1y;
161 STEP(tp->turtle.x, tp->turtle.y, tp->turtle.r, tp->turtle.theta);
162 points[3].x = tp->turtle.x;
163 points[3].y = tp->turtle.y;
164 TURN(tp->turtle.theta, 90.0 * (double) sign);
165 STEP(tp->turtle.x, tp->turtle.y, tp->turtle.r, tp->turtle.theta);
166 points[1].x = tp->turtle.x;
167 points[1].y = tp->turtle.y;
168 sign = -1;
169 if (level > 0) {
170 int j;
171
172 for (j = 0; j < 2; j++) {
173 pt1x = points[j].x;
174 pt2x = points[j + 1].x;
175 pt1y = points[j].y;
176 pt2y = points[j + 1].y;
177 generate_cesarovar(mi, pt1x, pt1y, pt2x, pt2y, level, sign);
178 }
179 } else {
180 XDrawLine(display, window, gc,
181 (int) points[0].x + tp->start.x, (int) points[0].y + tp->start.y,
182 (int) points[2].x + tp->start.x, (int) points[2].y + tp->start.y);
183 XDrawLine(display, window, gc,
184 (int) points[1].x + tp->start.x, (int) points[1].y + tp->start.y,
185 (int) points[3].x + tp->start.x, (int) points[3].y + tp->start.y);
186 }
187 }
188
189 static void
generate_harter_heightway(ModeInfo * mi,double pt1x,double pt1y,double pt2x,double pt2y,int level,int sign)190 generate_harter_heightway(ModeInfo * mi, double pt1x, double pt1y,
191 double pt2x, double pt2y, int level, int sign)
192 {
193 Display *display = MI_DISPLAY(mi);
194 Window window = MI_WINDOW(mi);
195 GC gc = MI_GC(mi);
196 turtlestruct *tp = &turtles[MI_SCREEN(mi)];
197 complextype points[4];
198 int sign2 = -1;
199
200 level--;
201
202 tp->turtle.r = sqrt((double) ((pt2x - pt1x) * (pt2x - pt1x) +
203 (pt2y - pt1y) * (pt2y - pt1y)) / 2.0);
204 points[0].x = pt1x;
205 points[0].y = pt1y;
206 points[2].x = pt2x;
207 points[2].y = pt2y;
208 tp->turtle.theta = POINT(pt1x, pt1y, pt2x, pt2y);
209 tp->turtle.x = pt1x;
210 tp->turtle.y = pt1y;
211 TURN(tp->turtle.theta, 45.0 * (double) sign);
212 STEP(tp->turtle.x, tp->turtle.y, tp->turtle.r, tp->turtle.theta);
213 points[1].x = tp->turtle.x;
214 points[1].y = tp->turtle.y;
215 if (level > 0) {
216 int j;
217
218 for (j = 0; j < 2; j++) {
219 pt1x = points[j].x;
220 pt2x = points[j + 1].x;
221 pt1y = points[j].y;
222 pt2y = points[j + 1].y;
223 generate_harter_heightway(mi, pt1x, pt1y, pt2x, pt2y, level, sign2);
224 sign2 *= -1;
225 }
226 } else {
227 XDrawLine(display, window, gc,
228 (int) points[0].x + tp->start.x, (int) points[0].y + tp->start.y,
229 (int) points[1].x + tp->start.x, (int) points[1].y + tp->start.y);
230 XDrawLine(display, window, gc,
231 (int) points[1].x + tp->start.x, (int) points[1].y + tp->start.y,
232 (int) points[2].x + tp->start.x, (int) points[2].y + tp->start.y);
233 }
234 }
235
236 ENTRYPOINT void
init_turtle(ModeInfo * mi)237 init_turtle(ModeInfo * mi)
238 {
239 int i;
240 turtlestruct *tp;
241
242 MI_INIT(mi, turtles);
243 tp = &turtles[MI_SCREEN(mi)];
244
245 tp->width = MI_WIDTH(mi);
246 tp->height = MI_HEIGHT(mi);
247 tp->min = MIN(tp->width, tp->height);
248 tp->maxlevel = 0;
249 i = tp->min;
250 do {
251 tp->r = i;
252 tp->maxlevel++;
253 i = (tp->min - 1) / (1 << tp->maxlevel);
254 } while (i > 1);
255 tp->maxlevel--;
256 tp->r = tp->min = (tp->r << tp->maxlevel);
257 tp->width = MAX(tp->width, tp->min + 1);
258 tp->height = MAX(tp->height, tp->min + 1);
259
260 tp->curve = NRAND(TURTLE_CURVES);
261 switch (tp->curve) {
262 case HILBERT:
263 tp->start.x = NRAND(tp->width - tp->min);
264 tp->start.y = NRAND(tp->height - tp->min);
265 break;
266 case CESARO_VAR:
267 tp->r <<= 6;
268 tp->min = 3 * tp->min / 4;
269 tp->start.x = tp->width / 2;
270 tp->start.y = tp->height / 2;
271 switch (NRAND(4)) {
272 case 0:
273 tp->pt1.x = -tp->min / 2;
274 tp->pt1.y = 0;
275 tp->pt2.x = tp->min / 2;
276 tp->pt2.y = 0;
277 tp->start.y -= tp->min / 6;
278 break;
279 case 1:
280 tp->pt1.x = 0;
281 tp->pt1.y = -tp->min / 2;
282 tp->pt2.x = 0;
283 tp->pt2.y = tp->min / 2;
284 tp->start.x += tp->min / 6;
285 break;
286 case 2:
287 tp->pt1.x = tp->min / 2;
288 tp->pt1.y = 0;
289 tp->pt2.x = -tp->min / 2;
290 tp->pt2.y = 0;
291 tp->start.y += tp->min / 6;
292 break;
293 case 3:
294 tp->pt1.x = 0;
295 tp->pt1.y = tp->min / 2;
296 tp->pt2.x = 0;
297 tp->pt2.y = -tp->min / 2;
298 tp->start.x -= tp->min / 6;
299 break;
300 }
301 break;
302 case HARTER_HEIGHTWAY:
303 tp->r <<= 6;
304 tp->min = 3 * tp->min / 4;
305 tp->start.x = tp->width / 2;
306 tp->start.y = tp->height / 2;
307 switch (NRAND(4)) {
308 case 0:
309 tp->pt1.x = -tp->min / 2;
310 tp->pt1.y = -tp->min / 12;
311 tp->pt2.x = tp->min / 2;
312 tp->pt2.y = -tp->min / 12;
313 break;
314 case 1:
315 tp->pt1.x = tp->min / 12;
316 tp->pt1.y = -tp->min / 2;
317 tp->pt2.x = tp->min / 12;
318 tp->pt2.y = tp->min / 2;
319 break;
320 case 2:
321 tp->pt1.x = tp->min / 2;
322 tp->pt1.y = tp->min / 12;
323 tp->pt2.x = -tp->min / 2;
324 tp->pt2.y = tp->min / 12;
325 break;
326 case 3:
327 tp->pt1.x = -tp->min / 12;
328 tp->pt1.y = tp->min / 2;
329 tp->pt2.x = -tp->min / 12;
330 tp->pt2.y = -tp->min / 2;
331 break;
332 }
333 }
334 tp->level = 0;
335 tp->sign = 1;
336 tp->dir = NRAND(4);
337 tp->time = 0;
338
339 MI_CLEARWINDOW(mi);
340
341 if (MI_NPIXELS(mi) <= 2)
342 XSetForeground(MI_DISPLAY(mi), MI_GC(mi), MI_WHITE_PIXEL(mi));
343 }
344
345 ENTRYPOINT void
draw_turtle(ModeInfo * mi)346 draw_turtle(ModeInfo * mi)
347 {
348 turtlestruct *tp;
349
350 if (turtles == NULL)
351 return;
352 tp = &turtles[MI_SCREEN(mi)];
353
354 if (++tp->time > MI_CYCLES(mi))
355 init_turtle(mi);
356
357 MI_IS_DRAWN(mi) = True;
358
359 if (MI_NPIXELS(mi) > 2)
360 XSetForeground(MI_DISPLAY(mi), MI_GC(mi),
361 MI_PIXEL(mi, NRAND(MI_NPIXELS(mi))));
362
363 tp->r = tp->r >> 1;
364 tp->level++;
365 if (tp->r > 1)
366 switch (tp->curve) {
367 case HILBERT:
368 switch (tp->dir) {
369 case 0:
370 tp->pt1.x = tp->pt2.x = tp->start.x + tp->r / 2;
371 tp->pt1.y = tp->pt2.y = tp->start.y + tp->r / 2;
372 generate_hilbert(mi, 0, tp->r);
373 break;
374 case 1:
375 tp->pt1.x = tp->pt2.x = tp->start.x + tp->min - tp->r / 2;
376 tp->pt1.y = tp->pt2.y = tp->start.y + tp->min - tp->r / 2;
377 generate_hilbert(mi, 0, -tp->r);
378 break;
379 case 2:
380 tp->pt1.x = tp->pt2.x = tp->start.x + tp->min - tp->r / 2;
381 tp->pt1.y = tp->pt2.y = tp->start.y + tp->min - tp->r / 2;
382 generate_hilbert(mi, -tp->r, 0);
383 break;
384 case 3:
385 tp->pt1.x = tp->pt2.x = tp->start.x + tp->r / 2;
386 tp->pt1.y = tp->pt2.y = tp->start.y + tp->r / 2;
387 generate_hilbert(mi, tp->r, 0);
388 }
389 break;
390 case CESARO_VAR:
391 generate_cesarovar(mi,
392 (double) tp->pt1.x, (double) tp->pt1.y,
393 (double) tp->pt2.x, (double) tp->pt2.y,
394 tp->level, tp->sign);
395 break;
396 case HARTER_HEIGHTWAY:
397 generate_harter_heightway(mi,
398 (double) tp->pt1.x, (double) tp->pt1.y,
399 (double) tp->pt2.x, (double) tp->pt2.y,
400 tp->level, tp->sign);
401 break;
402 }
403 }
404
405 ENTRYPOINT void
release_turtle(ModeInfo * mi)406 release_turtle(ModeInfo * mi)
407 {
408 if (turtles != NULL) {
409 free(turtles);
410 turtles = (turtlestruct *) NULL;
411 }
412 }
413
414 XSCREENSAVER_MODULE ("Turtle", turtle)
415
416 #endif /* MODE_turtle */
417