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