http://www.jwz.org/xscreensaver/xscreensaver-5.12.tar.gz
[xscreensaver] / hacks / epicycle.c
1 /* epicycle --- The motion of a body with epicycles, as in the pre-Copernican
2  * cosmologies.
3  *
4  * Copyright (c) 1998  James Youngman <jay@gnu.org>
5  * 
6  * Permission to use, copy, modify, distribute, and sell this software and its
7  * documentation for any purpose is hereby granted without fee, provided that
8  * the above copyright notice appear in all copies and that both that
9  * copyright notice and this permission notice appear in supporting
10  * documentation.  No representations are made about the suitability of this
11  * software for any purpose.  It is provided "as is" without express or 
12  * implied warranty.
13  */
14
15 /* Standard C headers; screenhack.h assumes that these have already
16  * been included if required -- for example, it defines M_PI if not
17  * already defined.
18  */
19 #include <float.h>
20 #include <math.h>
21
22
23 #include "screenhack.h"
24 #include "erase.h"
25
26 /* MIT-SHM headers omitted; this screenhack doesn't use it */
27
28
29
30 /*********************************************************/
31 /******************** MAGIC CONSTANTS ********************/
32 /*********************************************************/
33 #define MIN_RADIUS (5)          /* smallest allowable circle radius */
34 #define FILL_PROPORTION (0.9)   /* proportion of screen to fill by scaling. */
35 /*********************************************************/
36 /***************** END OF MAGIC CONSTANTS ****************/
37 /*********************************************************/
38
39
40
41 #define FULLCIRCLE (2.0 * M_PI) /* radians in a circle. */
42
43
44 /* Some of these resource values here are hand-tuned to give a
45  * pleasing variety of interesting shapes.  These are not the only
46  * good settings, but you may find you need to change some as a group
47  * to get pleasing figures.
48  */
49 static const char *epicycle_defaults [] = {
50   ".background: black",
51   ".foreground: white",
52   "*fpsSolid:   true",
53   "*colors:     100",
54   "*color0:     red",
55   "*delay:      20000",
56   "*holdtime:   2",
57   "*lineWidth:  4",
58   "*minCircles:  2",
59   "*maxCircles:  10",
60   "*minSpeed:   0.003",
61   "*maxSpeed:   0.005",
62   "*harmonics:  8",
63   "*timestep:   1.0",
64   "*timestepCoarseFactor: 1.0", /* no option for this resource. */
65   "*divisorPoisson: 0.4",
66   "*sizeFactorMin: 1.05",
67   "*sizeFactorMax: 2.05",
68   0
69 };
70
71 /* options passed to this program */
72 static XrmOptionDescRec epicycle_options [] = {
73   { "-color0",          ".color0",        XrmoptionSepArg, 0 },
74   { "-colors",          ".colors",        XrmoptionSepArg, 0 },
75   { "-colours",         ".colors",        XrmoptionSepArg, 0 },
76   { "-foreground",      ".foreground",    XrmoptionSepArg, 0 },
77   { "-delay",           ".delay",         XrmoptionSepArg, 0 },
78   { "-holdtime",        ".holdtime",      XrmoptionSepArg, 0 },
79   { "-linewidth",       ".lineWidth",     XrmoptionSepArg, 0 },
80   { "-min_circles",     ".minCircles",    XrmoptionSepArg, 0 },
81   { "-max_circles",     ".maxCircles",    XrmoptionSepArg, 0 },
82   { "-min_speed",       ".minSpeed",      XrmoptionSepArg, 0 },
83   { "-max_speed",       ".maxSpeed",      XrmoptionSepArg, 0 },
84   { "-harmonics",       ".harmonics",     XrmoptionSepArg, 0 },
85   { "-timestep",        ".timestep",      XrmoptionSepArg, 0 },
86   { "-divisor_poisson",".divisorPoisson",XrmoptionSepArg, 0 },
87   { "-size_factor_min", ".sizeFactorMin", XrmoptionSepArg, 0 },
88   { "-size_factor_max", ".sizeFactorMax", XrmoptionSepArg, 0 },
89   { 0, 0, 0, 0 }
90 };
91
92
93 /* Each circle is centred on a point on the rim of another circle.
94  */
95 struct tagCircle
96 {
97   long radius;                  /* in pixels */
98   double w;                     /* position (radians ccw from x-axis) */
99   double initial_w;             /* starting position */
100   double wdot;                  /* rotation rate (change in w per iteration) */
101   int    divisor;
102
103   struct tagCircle *pchild;
104 };
105 typedef struct tagCircle Circle;
106
107
108 struct tagBody                  /* a body that moves on a system of circles. */
109 {
110   int x_origin, y_origin;
111   int x, y;
112   int old_x, old_y;
113   int current_color;            /* pixel index into colors[] */
114   Circle *epicycles;            /* system of circles on which it moves. */
115   struct tagBody *next;         /* next in list. */
116 };
117 typedef struct tagBody Body;
118
119
120 struct state {
121    Display *dpy;
122    Window window;
123    GC color0;
124    int width, height;
125    int x_offset, y_offset;
126    int unit_pixels;
127    unsigned long bg;
128    Colormap cmap;
129    int restart;
130    double wdot_max;
131    XColor *colors;
132    int ncolors;
133    int color_shift_pos; /* how far we are towards that. */
134    double colour_cycle_rate;
135    int harmonics;
136    double divisorPoisson;
137    double sizeFactorMin;
138    double sizeFactorMax;
139    int minCircles;
140    int maxCircles;
141
142    Bool done;
143
144    long L;
145    double T, timestep, circle, timestep_coarse;
146    int delay;
147    int uncleared;
148    int holdtime;
149    int xmax, xmin, ymax, ymin;
150    Body *pb0;
151    double xtime;
152    eraser_state *eraser;
153 };
154
155
156
157 /* Determine the GCD of two numbers using Euclid's method.  The other
158  * possible algorighm is Stein's method, but it's probably only going
159  * to be much faster on machines with no divide instruction, like the
160  * ARM and the Z80.  The former is very fast anyway and the latter
161  * probably won't run X clients; in any case, this calculation is not
162  * the bulk of the computational expense of the program.  I originally
163  * tried using Stein's method, but I wanted to remove the gotos.  Not
164  * wanting to introduce possible bugs, I plumped for Euclid's method
165  * instead.  Lastly, Euclid's algorithm is preferred to the
166  * generalisation for N inputs.
167  *
168  * See Knuth, section 4.5.2.
169  */
170 static int
171 gcd(int u, int v)               /* Euclid's Method */
172 {
173   /* If either operand of % is negative, the sign of the result is
174    * implementation-defined.  See section 6.3.5 "Multiplicative
175    * Operators" of the ANSI C Standard (page 46 [LEFT HAND PAGE!] of
176    * "Annotated C Standard", Osborne, ISBN 0-07-881952-0).
177    */
178   if (u < 0) u = -u;
179   if (v < 0) v = -v;
180   
181   while (0 != v)
182     {
183       int r;
184       r = u % v;
185       u = v;
186       v = r;
187     }
188   return u;
189 }
190
191 /* Determine the Lowest Common Multiple of two integers, using
192  * Euclid's Proposition 34, as explained in Knuth's The Art of
193  * Computer Programming, Vol 2, section 4.5.2.
194  */
195 static int
196 lcm(int u, int v)
197 {
198   return u / gcd(u,v) * v;
199 }
200
201 static long 
202 random_radius(struct state *st, double scale)   
203 {
204   long r;
205
206   r = frand(scale) * st->unit_pixels/2; /* for frand() see utils/yarandom.h */
207   if (r < MIN_RADIUS)
208     r = MIN_RADIUS;
209   return r;
210 }
211
212
213 static long
214 random_divisor(struct state *st)
215 {
216   int divisor = 1;
217   int sign;
218
219   while (frand(1.0) < st->divisorPoisson && divisor <= st->harmonics)
220     {
221       ++divisor;
222     }
223   sign = (frand(1.0) < 0.5) ? +1 : -1;
224   return sign * divisor;
225 }
226
227
228 /* Construct a circle or die.
229  */
230 static Circle *
231 new_circle(struct state *st, double scale)
232 {
233   Circle *p = malloc(sizeof(Circle));
234   
235   p->radius = random_radius(st, scale);
236   p->w = p->initial_w = 0.0;
237   p->divisor = random_divisor(st);
238   p->wdot = st->wdot_max / p->divisor;
239   p->pchild = NULL;
240   
241   return p;
242 }
243
244 static void delete_circle(Circle *p)
245 {
246   free(p);
247 }
248
249 static void 
250 delete_circle_chain(Circle *p)
251 {
252   while (p)
253     {
254       Circle *q = p->pchild;
255       delete_circle(p);
256       p = q;
257     }
258 }
259
260 static Circle *
261 new_circle_chain(struct state *st)
262 {
263   Circle *head;
264   double scale = 1.0, factor;
265   int n;
266
267   /* Parent circles are larger than their children by a factor of at
268    * least FACTOR_MIN and at most FACTOR_MAX.
269    */
270   factor = st->sizeFactorMin + frand(st->sizeFactorMax - st->sizeFactorMin);
271   
272   /* There are between minCircles and maxCircles in each figure.
273    */
274   if (st->maxCircles == st->minCircles)
275     n = st->minCircles;            /* Avoid division by zero. */
276   else
277     n = st->minCircles + random() % (st->maxCircles - st->minCircles);
278   
279   head = NULL;
280   while (n--)
281     {
282       Circle *p = new_circle(st, scale);
283       p->pchild = head;
284       head = p;
285
286       scale /= factor;
287     }
288   return head;
289 }
290
291 static void
292 assign_random_common_w(Circle *p)
293 {
294   double w_common = frand(FULLCIRCLE);  /* anywhere on the circle */
295   while (p)
296     {
297       p->initial_w = w_common;
298       p = p->pchild;
299     }
300 }
301
302 static Body *
303 new_body(struct state *st)
304 {
305   Body *p = malloc(sizeof(Body));
306   if (!p) abort();
307   p->epicycles = new_circle_chain(st);
308   p->current_color = 0;         /* ?? start them all on different colors? */
309   p->next = NULL;
310   p->x = p->y = 0;
311   p->old_x = p->old_y = 0;
312   p->x_origin = p->y_origin = 0;
313
314   /* Start all the epicycles at the same w value to make it easier to
315    * figure out at what T value the cycle is closed.   We don't just fix
316    * the initial W value because that makes all the patterns tend to 
317    * be symmetrical about the X axis.
318    */
319   assign_random_common_w(p->epicycles);
320   return p;
321 }
322
323 static void
324 delete_body(Body *p)
325 {
326   delete_circle_chain(p->epicycles);
327   free(p);
328 }
329
330
331 static void 
332 draw_body(struct state *st, Body *pb, GC gc)
333 {
334   XDrawLine(st->dpy, st->window, gc, pb->old_x, pb->old_y, pb->x, pb->y);
335 }
336
337 static long
338 compute_divisor_lcm(Circle *p)
339 {
340   long l = 1;
341   
342   while (p)
343     {
344       l = lcm(l, p->divisor);
345       p = p->pchild;
346     }
347   return l;
348 }
349
350               
351 /* move_body()
352  *
353  * Calculate the position for the body at time T.  We work in double 
354  * rather than int to avoid the cumulative errors that would be caused
355  * by the rounding implicit in an assignment to int.
356  */
357 static void
358 move_body(Body *pb, double t)
359 {
360   Circle *p;
361   double x, y;
362
363   pb->old_x = pb->x;
364   pb->old_y = pb->y;
365   
366   x = pb->x_origin;
367   y = pb->y_origin;
368   
369   for (p=pb->epicycles; NULL != p; p=p->pchild)
370     {
371       /* angular pos = initial_pos + time * angular speed */
372       /* but this is an angular position, so modulo FULLCIRCLE. */
373       p->w = fmod(p->initial_w + (t * p->wdot), FULLCIRCLE);
374       
375       x += (p->radius * cos(p->w));
376       y += (p->radius * sin(p->w));
377     }
378   
379   pb->x = (int)x;
380   pb->y = (int)y;
381 }
382
383 static int
384 colour_init(struct state *st, XWindowAttributes *pxgwa)
385 {
386   XGCValues gcv;
387
388 #if 0
389   int H = random() % 360;       /* colour choice from attraction.c. */
390   double S1 = 0.25;
391   double S2 = 1.00;
392   double V = frand(0.25) + 0.75;
393   int line_width = 0;
394 #endif
395
396   int retval = 1;
397   unsigned long valuemask = 0L;
398   unsigned long fg;
399   
400   /* Free any already allocated colors...
401    */
402   if (st->colors)
403     {
404       free_colors(st->dpy, st->cmap, st->colors, st->ncolors);
405       st->colors = 0;
406       st->ncolors = 0;
407     }
408         
409   st->ncolors = get_integer_resource (st->dpy, "colors", "Colors");
410   if (0 == st->ncolors)         /* English spelling? */
411     st->ncolors = get_integer_resource (st->dpy, "colours", "Colors");
412   
413   if (st->ncolors < 2)
414     st->ncolors = 2;
415   if (st->ncolors <= 2)
416     mono_p = True;
417   st->colors = 0;
418
419   if (!mono_p)
420     {
421       st->colors = (XColor *) malloc(sizeof(*st->colors) * (st->ncolors+1));
422       if (!st->colors) abort();
423           
424       make_smooth_colormap (st->dpy, pxgwa->visual, st->cmap, st->colors, &st->ncolors,
425                             True, /* allocate */
426                             False, /* not writable */
427                             True); /* verbose (complain about failure) */
428       if (st->ncolors <= 2)
429         {
430           if (st->colors)
431             free (st->colors);
432           st->colors = 0;
433           mono_p = True;
434         }
435     }
436
437   
438   st->bg = get_pixel_resource (st->dpy, st->cmap, "background", "Background");
439
440   /* Set the line width
441    */
442   gcv.line_width = get_integer_resource (st->dpy, "lineWidth", "Integer");
443   if (gcv.line_width)
444     {
445       valuemask |= GCLineWidth;
446
447       gcv.join_style = JoinRound;
448       gcv.cap_style = CapRound;
449           
450       valuemask |= (GCCapStyle | GCJoinStyle);
451     }
452   
453
454   /* Set the drawing function.
455    */
456   gcv.function = GXcopy;
457   valuemask |= GCFunction;
458   
459   /* Set the foreground.
460    */
461 /*  if (mono_p)*/
462     fg = get_pixel_resource (st->dpy, st->cmap, "foreground", "Foreground");
463 /* WTF?
464 else
465     fg = st->bg ^ get_pixel_resource (st->dpy, st->cmap, ("color0"), "Foreground"); 
466 */
467   gcv.foreground = fg;
468   valuemask |= GCForeground;
469
470   /* Actually create the GC.
471    */
472   st->color0 = XCreateGC (st->dpy, st->window, valuemask, &gcv);
473   
474   return retval;
475 }
476
477
478
479
480 static void
481 setup(struct state *st)
482 {
483   XWindowAttributes xgwa;
484   
485   XGetWindowAttributes (st->dpy, st->window, &xgwa);
486   st->cmap = xgwa.colormap;
487
488   st->width = xgwa.width;
489   st->height = xgwa.height;
490   st->x_offset = st->width / 2;
491   st->y_offset = st->height / 2;
492   st->unit_pixels = st->width < st->height ? st->width : st->height;
493
494   {
495     if (!st->done)
496       {
497         colour_init(st, &xgwa);
498         st->done = True;
499       }
500   }
501 }
502
503
504 static void
505 color_step(struct state *st, Body *pb, double frac)
506 {
507   if (!mono_p)
508     {
509       int newshift = st->ncolors * fmod(frac * st->colour_cycle_rate, 1.0);
510       if (newshift != st->color_shift_pos)
511         {
512           pb->current_color = newshift;
513           XSetForeground (st->dpy, st->color0, st->colors[pb->current_color].pixel);
514           st->color_shift_pos = newshift;
515         }
516     }
517 }
518
519
520 #if 0
521 static long
522 distance(long x1, long y1, long x2, long y2)
523 {
524   long dx, dy;
525
526   dx = x2 - x1;
527   dy = y2 - y1;
528   return dx*dx + dy*dy;
529 }
530
531 static int poisson_irand(double p)
532 {
533   int r = 1;
534   while (fabs(frand(1.0)) < p)
535     ++r;
536   return r < 1 ? 1 : r;
537 }
538 #endif
539
540 static void
541 precalculate_figure(Body *pb,
542                     double this_xtime, double step,
543                     int *x_max, int *y_max,
544                     int *x_min, int *y_min)
545 {
546   double t;
547   
548   move_body(pb, 0.0); /* move once to avoid initial line from origin */
549   *x_min = *x_max = pb->x;
550   *y_min = *y_max = pb->y;
551   
552   for (t=0.0; t<this_xtime; t += step)
553     {
554       move_body(pb, t); /* move once to avoid initial line from origin */
555       if (pb->x > *x_max)
556         *x_max = pb->x;
557       if (pb->x < *x_min)
558         *x_min = pb->x;
559       if (pb->y > *y_max)
560         *y_max = pb->y;
561       if (pb->y < *y_min)
562         *y_min = pb->y;
563     }
564 }
565
566 static int i_max(int a, int b)
567 {
568   return (a>b) ? a : b;
569 }
570
571 static void rescale_circles(struct state *st, Body *pb,
572                             int x_max, int y_max,
573                             int x_min, int y_min)
574 {
575   double xscale, yscale, scale;
576   double xm, ym;
577   
578   x_max -= st->x_offset;
579   x_min -= st->x_offset;
580   y_max -= st->y_offset;
581   y_min -= st->y_offset;
582
583   x_max = i_max(x_max, -x_min);
584   y_max = i_max(y_max, -y_min);
585
586
587   xm = st->width / 2.0;
588   ym = st->height / 2.0;
589   if (x_max > xm)
590     xscale = xm / x_max;
591   else
592     xscale = 1.0;
593   if (y_max > ym)
594     yscale = ym / y_max;
595   else
596     yscale = 1.0;
597
598   if (xscale < yscale)          /* wider than tall */
599     scale = xscale;             /* ensure width fits onscreen */
600   else
601     scale = yscale;             /* ensure height fits onscreen */
602
603
604   scale *= FILL_PROPORTION;     /* only fill FILL_PROPORTION of screen */
605   if (scale < 1.0)              /* only reduce, don't enlarge. */
606     {
607       Circle *p;
608       for (p=pb->epicycles; p; p=p->pchild)
609         {
610           p->radius *= scale;
611         }
612     }
613   else
614     {
615       printf("enlarge by x%.2f skipped...\n", scale);
616     }
617 }
618
619
620 /* angular speeds of the circles are harmonics of a fundamental
621  * value.  That should please the Pythagoreans among you... :-)
622  */
623 static double 
624 random_wdot_max(struct state *st)
625 {
626   /* Maximum and minimum values for the choice of wdot_max.  Possible
627    * epicycle speeds vary from wdot_max to (wdot_max * harmonics).
628    */
629   double minspeed, maxspeed;
630   minspeed = get_float_resource(st->dpy, "minSpeed", "Double");
631   maxspeed = get_float_resource(st->dpy, "maxSpeed", "Double");
632   return st->harmonics * (minspeed + FULLCIRCLE * frand(maxspeed-minspeed));
633 }
634
635
636 static void *
637 epicycle_init (Display *disp, Window win)
638 {
639   struct state *st = (struct state *) calloc (1, sizeof(*st));
640   st->dpy = disp;
641   st->window = win;
642
643   st->holdtime = get_integer_resource (st->dpy, "holdtime", "Integer");
644
645   st->circle = FULLCIRCLE;
646   
647   XClearWindow(st->dpy, st->window);
648   st->uncleared = 0;
649   st->restart = 1;
650   
651   st->delay = get_integer_resource (st->dpy, "delay", "Integer");
652   st->harmonics = get_integer_resource(st->dpy, "harmonics", "Integer");
653   st->divisorPoisson = get_float_resource(st->dpy, "divisorPoisson", "Double");
654   
655   st->timestep = get_float_resource(st->dpy, "timestep", "Double");
656   st->timestep_coarse = st->timestep *
657     get_float_resource(st->dpy, "timestepCoarseFactor", "Double");
658   
659   st->sizeFactorMin = get_float_resource(st->dpy, "sizeFactorMin", "Double");
660   st->sizeFactorMax = get_float_resource(st->dpy, "sizeFactorMax", "Double");
661
662   st->minCircles = get_integer_resource (st->dpy, "minCircles", "Integer");
663   st->maxCircles = get_integer_resource (st->dpy, "maxCircles", "Integer");
664
665   st->xtime = 0; /* is this right? */
666
667   return st;
668 }
669
670 static unsigned long
671 epicycle_draw (Display *dpy, Window window, void *closure)
672 {
673   struct state *st = (struct state *) closure;
674   int this_delay = st->delay;
675
676   if (st->eraser) {
677     st->eraser = erase_window (st->dpy, st->window, st->eraser);
678     return 10000;
679   }
680
681   if (st->restart)
682     {
683       setup(st);
684       st->restart = 0;
685
686       /* Flush any outstanding events; this has the side effect of
687        * reducing the number of "false restarts"; resdtarts caused by
688        * one event (e.g. ConfigureNotify) followed by another
689        * (e.g. Expose).
690        */
691           
692       st->wdot_max = random_wdot_max(st);
693           
694       if (st->pb0)
695         {
696           delete_body(st->pb0);
697           st->pb0 = NULL;
698         }
699       st->pb0 = new_body(st);
700       st->pb0->x_origin = st->pb0->x = st->x_offset;
701       st->pb0->y_origin = st->pb0->y = st->y_offset;
702
703       if (st->uncleared)
704         {
705           st->eraser = erase_window (st->dpy, st->window, st->eraser);
706           st->uncleared = 0;
707         }
708
709       precalculate_figure(st->pb0, st->xtime, st->timestep_coarse,
710                           &st->xmax, &st->ymax, &st->xmin, &st->ymin);
711
712       rescale_circles(st, st->pb0, st->xmax, st->ymax, st->xmin, st->ymin);
713       
714       move_body(st->pb0, 0.0); /* move once to avoid initial line from origin */
715       move_body(st->pb0, 0.0); /* move once to avoid initial line from origin */
716
717       
718       st->T = 0.0;                      /* start at time zero. */
719
720       st->L = compute_divisor_lcm(st->pb0->epicycles);
721       
722       st->colour_cycle_rate = fabs(st->L);
723       
724       st->xtime = fabs(st->L * st->circle / st->wdot_max);
725
726       if (st->colors)                           /* (colors==NULL) if mono_p */
727         XSetForeground (st->dpy, st->color0, st->colors[st->pb0->current_color].pixel);
728     }
729
730
731   color_step(st, st->pb0, st->T/st->xtime );
732   draw_body(st, st->pb0, st->color0);
733   st->uncleared = 1;
734
735           
736   /* Check if the figure is complete...*/
737   if (st->T > st->xtime)
738     {
739       this_delay = st->holdtime * 1000000;
740       st->restart = 1;  /* begin new figure. */
741     }
742           
743
744
745   st->T += st->timestep;
746   move_body(st->pb0, st->T);
747
748   return this_delay;
749 }
750
751 static void
752 epicycle_reshape (Display *dpy, Window window, void *closure, 
753                  unsigned int w, unsigned int h)
754 {
755   struct state *st = (struct state *) closure;
756   st->restart = 1;
757 }
758
759 static Bool
760 epicycle_event (Display *dpy, Window window, void *closure, XEvent *e)
761 {
762   struct state *st = (struct state *) closure;
763   if (e->type == ButtonPress)
764     {
765       st->restart = 1;
766       return True;
767     }
768
769   return False;
770 }
771
772 static void
773 epicycle_free (Display *dpy, Window window, void *closure)
774 {
775   struct state *st = (struct state *) closure;
776   free (st);
777 }
778
779 XSCREENSAVER_MODULE ("Epicycle", epicycle)