4eae8c945d288618c45446b92b63d402e1c293ed
[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 static void
229 oom(struct state *st)
230 {
231   fprintf(stderr, "Failed to allocate memory!\n");
232   exit(-1);
233 }
234
235
236 /* Construct a circle or die.
237  */
238 static Circle *
239 new_circle(struct state *st, double scale)
240 {
241   Circle *p = malloc(sizeof(Circle));
242   
243   p->radius = random_radius(st, scale);
244   p->w = p->initial_w = 0.0;
245   p->divisor = random_divisor(st);
246   p->wdot = st->wdot_max / p->divisor;
247   p->pchild = NULL;
248   
249   return p;
250 }
251
252 static void delete_circle(Circle *p)
253 {
254   free(p);
255 }
256
257 static void 
258 delete_circle_chain(Circle *p)
259 {
260   while (p)
261     {
262       Circle *q = p->pchild;
263       delete_circle(p);
264       p = q;
265     }
266 }
267
268 static Circle *
269 new_circle_chain(struct state *st)
270 {
271   Circle *head;
272   double scale = 1.0, factor;
273   int n;
274
275   /* Parent circles are larger than their children by a factor of at
276    * least FACTOR_MIN and at most FACTOR_MAX.
277    */
278   factor = st->sizeFactorMin + frand(st->sizeFactorMax - st->sizeFactorMin);
279   
280   /* There are between minCircles and maxCircles in each figure.
281    */
282   if (st->maxCircles == st->minCircles)
283     n = st->minCircles;            /* Avoid division by zero. */
284   else
285     n = st->minCircles + random() % (st->maxCircles - st->minCircles);
286   
287   head = NULL;
288   while (n--)
289     {
290       Circle *p = new_circle(st, scale);
291       p->pchild = head;
292       head = p;
293
294       scale /= factor;
295     }
296   return head;
297 }
298
299 static void
300 assign_random_common_w(Circle *p)
301 {
302   double w_common = frand(FULLCIRCLE);  /* anywhere on the circle */
303   while (p)
304     {
305       p->initial_w = w_common;
306       p = p->pchild;
307     }
308 }
309
310 static Body *
311 new_body(struct state *st)
312 {
313   Body *p = malloc(sizeof(Body));
314   if (NULL == p)
315     oom(st);
316   p->epicycles = new_circle_chain(st);
317   p->current_color = 0;         /* ?? start them all on different colors? */
318   p->next = NULL;
319   p->x = p->y = 0;
320   p->old_x = p->old_y = 0;
321   p->x_origin = p->y_origin = 0;
322
323   /* Start all the epicycles at the same w value to make it easier to
324    * figure out at what T value the cycle is closed.   We don't just fix
325    * the initial W value because that makes all the patterns tend to 
326    * be symmetrical about the X axis.
327    */
328   assign_random_common_w(p->epicycles);
329   return p;
330 }
331
332 static void
333 delete_body(Body *p)
334 {
335   delete_circle_chain(p->epicycles);
336   free(p);
337 }
338
339
340 static void 
341 draw_body(struct state *st, Body *pb, GC gc)
342 {
343   XDrawLine(st->dpy, st->window, gc, pb->old_x, pb->old_y, pb->x, pb->y);
344 }
345
346 static long
347 compute_divisor_lcm(Circle *p)
348 {
349   long l = 1;
350   
351   while (p)
352     {
353       l = lcm(l, p->divisor);
354       p = p->pchild;
355     }
356   return l;
357 }
358
359               
360 /* move_body()
361  *
362  * Calculate the position for the body at time T.  We work in double 
363  * rather than int to avoid the cumulative errors that would be caused
364  * by the rounding implicit in an assignment to int.
365  */
366 static void
367 move_body(Body *pb, double t)
368 {
369   Circle *p;
370   double x, y;
371
372   pb->old_x = pb->x;
373   pb->old_y = pb->y;
374   
375   x = pb->x_origin;
376   y = pb->y_origin;
377   
378   for (p=pb->epicycles; NULL != p; p=p->pchild)
379     {
380       /* angular pos = initial_pos + time * angular speed */
381       /* but this is an angular position, so modulo FULLCIRCLE. */
382       p->w = fmod(p->initial_w + (t * p->wdot), FULLCIRCLE);
383       
384       x += (p->radius * cos(p->w));
385       y += (p->radius * sin(p->w));
386     }
387   
388   pb->x = (int)x;
389   pb->y = (int)y;
390 }
391
392 static int
393 colour_init(struct state *st, XWindowAttributes *pxgwa)
394 {
395   XGCValues gcv;
396
397 #if 0
398   int H = random() % 360;       /* colour choice from attraction.c. */
399   double S1 = 0.25;
400   double S2 = 1.00;
401   double V = frand(0.25) + 0.75;
402   int line_width = 0;
403 #endif
404
405   int retval = 1;
406   unsigned long valuemask = 0L;
407   unsigned long fg;
408   
409   /* Free any already allocated colors...
410    */
411   if (st->colors)
412     {
413       free_colors(st->dpy, st->cmap, st->colors, st->ncolors);
414       st->colors = 0;
415       st->ncolors = 0;
416     }
417         
418   st->ncolors = get_integer_resource (st->dpy, "colors", "Colors");
419   if (0 == st->ncolors)         /* English spelling? */
420     st->ncolors = get_integer_resource (st->dpy, "colours", "Colors");
421   
422   if (st->ncolors < 2)
423     st->ncolors = 2;
424   if (st->ncolors <= 2)
425     mono_p = True;
426   st->colors = 0;
427
428   if (!mono_p)
429     {
430       st->colors = (XColor *) malloc(sizeof(*st->colors) * (st->ncolors+1));
431       if (!st->colors)
432         oom(st);
433           
434       make_smooth_colormap (st->dpy, pxgwa->visual, st->cmap, st->colors, &st->ncolors,
435                             True, /* allocate */
436                             False, /* not writable */
437                             True); /* verbose (complain about failure) */
438       if (st->ncolors <= 2)
439         {
440           if (st->colors)
441             free (st->colors);
442           st->colors = 0;
443           mono_p = True;
444         }
445     }
446
447   
448   st->bg = get_pixel_resource (st->dpy, st->cmap, "background", "Background");
449
450   /* Set the line width
451    */
452   gcv.line_width = get_integer_resource (st->dpy, "lineWidth", "Integer");
453   if (gcv.line_width)
454     {
455       valuemask |= GCLineWidth;
456
457       gcv.join_style = JoinRound;
458       gcv.cap_style = CapRound;
459           
460       valuemask |= (GCCapStyle | GCJoinStyle);
461     }
462   
463
464   /* Set the drawing function.
465    */
466   gcv.function = GXcopy;
467   valuemask |= GCFunction;
468   
469   /* Set the foreground.
470    */
471 /*  if (mono_p)*/
472     fg = get_pixel_resource (st->dpy, st->cmap, "foreground", "Foreground");
473 /* WTF?
474 else
475     fg = st->bg ^ get_pixel_resource (st->dpy, st->cmap, ("color0"), "Foreground"); 
476 */
477   gcv.foreground = fg;
478   valuemask |= GCForeground;
479
480   /* Actually create the GC.
481    */
482   st->color0 = XCreateGC (st->dpy, st->window, valuemask, &gcv);
483   
484   return retval;
485 }
486
487
488
489
490 static void
491 setup(struct state *st)
492 {
493   XWindowAttributes xgwa;
494   
495   XGetWindowAttributes (st->dpy, st->window, &xgwa);
496   st->cmap = xgwa.colormap;
497
498   st->width = xgwa.width;
499   st->height = xgwa.height;
500   st->x_offset = st->width / 2;
501   st->y_offset = st->height / 2;
502   st->unit_pixels = st->width < st->height ? st->width : st->height;
503
504   {
505     if (!st->done)
506       {
507         colour_init(st, &xgwa);
508         st->done = True;
509       }
510   }
511 }
512
513
514 static void
515 color_step(struct state *st, Body *pb, double frac)
516 {
517   if (!mono_p)
518     {
519       int newshift = st->ncolors * fmod(frac * st->colour_cycle_rate, 1.0);
520       if (newshift != st->color_shift_pos)
521         {
522           pb->current_color = newshift;
523           XSetForeground (st->dpy, st->color0, st->colors[pb->current_color].pixel);
524           st->color_shift_pos = newshift;
525         }
526     }
527 }
528
529
530 #if 0
531 static long
532 distance(long x1, long y1, long x2, long y2)
533 {
534   long dx, dy;
535
536   dx = x2 - x1;
537   dy = y2 - y1;
538   return dx*dx + dy*dy;
539 }
540
541 static int poisson_irand(double p)
542 {
543   int r = 1;
544   while (fabs(frand(1.0)) < p)
545     ++r;
546   return r < 1 ? 1 : r;
547 }
548 #endif
549
550 static void
551 precalculate_figure(Body *pb,
552                     double this_xtime, double step,
553                     int *x_max, int *y_max,
554                     int *x_min, int *y_min)
555 {
556   double t;
557   
558   move_body(pb, 0.0); /* move once to avoid initial line from origin */
559   *x_min = *x_max = pb->x;
560   *y_min = *y_max = pb->y;
561   
562   for (t=0.0; t<this_xtime; t += step)
563     {
564       move_body(pb, t); /* move once to avoid initial line from origin */
565       if (pb->x > *x_max)
566         *x_max = pb->x;
567       if (pb->x < *x_min)
568         *x_min = pb->x;
569       if (pb->y > *y_max)
570         *y_max = pb->y;
571       if (pb->y < *y_min)
572         *y_min = pb->y;
573     }
574 }
575
576 static int i_max(int a, int b)
577 {
578   return (a>b) ? a : b;
579 }
580
581 static void rescale_circles(struct state *st, Body *pb,
582                             int x_max, int y_max,
583                             int x_min, int y_min)
584 {
585   double xscale, yscale, scale;
586   double xm, ym;
587   
588   x_max -= st->x_offset;
589   x_min -= st->x_offset;
590   y_max -= st->y_offset;
591   y_min -= st->y_offset;
592
593   x_max = i_max(x_max, -x_min);
594   y_max = i_max(y_max, -y_min);
595
596
597   xm = st->width / 2.0;
598   ym = st->height / 2.0;
599   if (x_max > xm)
600     xscale = xm / x_max;
601   else
602     xscale = 1.0;
603   if (y_max > ym)
604     yscale = ym / y_max;
605   else
606     yscale = 1.0;
607
608   if (xscale < yscale)          /* wider than tall */
609     scale = xscale;             /* ensure width fits onscreen */
610   else
611     scale = yscale;             /* ensure height fits onscreen */
612
613
614   scale *= FILL_PROPORTION;     /* only fill FILL_PROPORTION of screen */
615   if (scale < 1.0)              /* only reduce, don't enlarge. */
616     {
617       Circle *p;
618       for (p=pb->epicycles; p; p=p->pchild)
619         {
620           p->radius *= scale;
621         }
622     }
623   else
624     {
625       printf("enlarge by x%.2f skipped...\n", scale);
626     }
627 }
628
629
630 /* angular speeds of the circles are harmonics of a fundamental
631  * value.  That should please the Pythagoreans among you... :-)
632  */
633 static double 
634 random_wdot_max(struct state *st)
635 {
636   /* Maximum and minimum values for the choice of wdot_max.  Possible
637    * epicycle speeds vary from wdot_max to (wdot_max * harmonics).
638    */
639   double minspeed, maxspeed;
640   minspeed = get_float_resource(st->dpy, "minSpeed", "Double");
641   maxspeed = get_float_resource(st->dpy, "maxSpeed", "Double");
642   return st->harmonics * (minspeed + FULLCIRCLE * frand(maxspeed-minspeed));
643 }
644
645
646 static void *
647 epicycle_init (Display *disp, Window win)
648 {
649   struct state *st = (struct state *) calloc (1, sizeof(*st));
650   st->dpy = disp;
651   st->window = win;
652
653   st->holdtime = get_integer_resource (st->dpy, "holdtime", "Integer");
654
655   st->circle = FULLCIRCLE;
656   
657   XClearWindow(st->dpy, st->window);
658   st->uncleared = 0;
659   st->restart = 1;
660   
661   st->delay = get_integer_resource (st->dpy, "delay", "Integer");
662   st->harmonics = get_integer_resource(st->dpy, "harmonics", "Integer");
663   st->divisorPoisson = get_float_resource(st->dpy, "divisorPoisson", "Double");
664   
665   st->timestep = get_float_resource(st->dpy, "timestep", "Double");
666   st->timestep_coarse = st->timestep *
667     get_float_resource(st->dpy, "timestepCoarseFactor", "Double");
668   
669   st->sizeFactorMin = get_float_resource(st->dpy, "sizeFactorMin", "Double");
670   st->sizeFactorMax = get_float_resource(st->dpy, "sizeFactorMax", "Double");
671
672   st->minCircles = get_integer_resource (st->dpy, "minCircles", "Integer");
673   st->maxCircles = get_integer_resource (st->dpy, "maxCircles", "Integer");
674
675   st->xtime = 0; /* is this right? */
676
677   return st;
678 }
679
680 static unsigned long
681 epicycle_draw (Display *dpy, Window window, void *closure)
682 {
683   struct state *st = (struct state *) closure;
684   int this_delay = st->delay;
685
686   if (st->eraser) {
687     st->eraser = erase_window (st->dpy, st->window, st->eraser);
688     return 10000;
689   }
690
691   if (st->restart)
692     {
693       setup(st);
694       st->restart = 0;
695
696       /* Flush any outstanding events; this has the side effect of
697        * reducing the number of "false restarts"; resdtarts caused by
698        * one event (e.g. ConfigureNotify) followed by another
699        * (e.g. Expose).
700        */
701           
702       st->wdot_max = random_wdot_max(st);
703           
704       if (st->pb0)
705         {
706           delete_body(st->pb0);
707           st->pb0 = NULL;
708         }
709       st->pb0 = new_body(st);
710       st->pb0->x_origin = st->pb0->x = st->x_offset;
711       st->pb0->y_origin = st->pb0->y = st->y_offset;
712
713       if (st->uncleared)
714         {
715           st->eraser = erase_window (st->dpy, st->window, st->eraser);
716           st->uncleared = 0;
717         }
718
719       precalculate_figure(st->pb0, st->xtime, st->timestep_coarse,
720                           &st->xmax, &st->ymax, &st->xmin, &st->ymin);
721
722       rescale_circles(st, st->pb0, st->xmax, st->ymax, st->xmin, st->ymin);
723       
724       move_body(st->pb0, 0.0); /* move once to avoid initial line from origin */
725       move_body(st->pb0, 0.0); /* move once to avoid initial line from origin */
726
727       
728       st->T = 0.0;                      /* start at time zero. */
729
730       st->L = compute_divisor_lcm(st->pb0->epicycles);
731       
732       st->colour_cycle_rate = fabs(st->L);
733       
734       st->xtime = fabs(st->L * st->circle / st->wdot_max);
735
736       if (st->colors)                           /* (colors==NULL) if mono_p */
737         XSetForeground (st->dpy, st->color0, st->colors[st->pb0->current_color].pixel);
738     }
739
740
741   color_step(st, st->pb0, st->T/st->xtime );
742   draw_body(st, st->pb0, st->color0);
743   st->uncleared = 1;
744
745           
746   /* Check if the figure is complete...*/
747   if (st->T > st->xtime)
748     {
749       this_delay = st->holdtime * 1000000;
750       st->restart = 1;  /* begin new figure. */
751     }
752           
753
754
755   st->T += st->timestep;
756   move_body(st->pb0, st->T);
757
758   return this_delay;
759 }
760
761 static void
762 epicycle_reshape (Display *dpy, Window window, void *closure, 
763                  unsigned int w, unsigned int h)
764 {
765   struct state *st = (struct state *) closure;
766   st->restart = 1;
767 }
768
769 static Bool
770 epicycle_event (Display *dpy, Window window, void *closure, XEvent *e)
771 {
772   struct state *st = (struct state *) closure;
773   if (e->type == ButtonPress)
774     {
775       st->restart = 1;
776       return True;
777     }
778
779   return False;
780 }
781
782 static void
783 epicycle_free (Display *dpy, Window window, void *closure)
784 {
785   struct state *st = (struct state *) closure;
786   free (st);
787 }
788
789 XSCREENSAVER_MODULE ("Epicycle", epicycle)