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