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