http://ftp.x.org/contrib/applications/xscreensaver-3.07.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 /* 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   n = minCircles + rand() % (maxCircles - minCircles);
270   
271   head = NULL;
272   while (n--)
273     {
274       Circle *p = new_circle(scale);
275       p->pchild = head;
276       head = p;
277
278       scale /= factor;
279     }
280   return head;
281 }
282
283 static void
284 assign_random_common_w(Circle *p)
285 {
286   double w_common = frand(FULLCIRCLE);  /* anywhere on the circle */
287   while (p)
288     {
289       p->initial_w = w_common;
290       p = p->pchild;
291     }
292 }
293
294 static Body *
295 new_body(void)
296 {
297   Body *p = malloc(sizeof(Body));
298   if (NULL == p)
299     oom();
300   p->epicycles = new_circle_chain();
301   p->current_color = 0;         /* ?? start them all on different colors? */
302   p->next = NULL;
303   p->x = p->y = 0;
304   p->old_x = p->old_y = 0;
305   p->x_origin = p->y_origin = 0;
306
307   /* Start all the epicycles at the same w value to make it easier to
308    * figure out at what T value the cycle is closed.   We don't just fix
309    * the initial W value because that makes all the patterns tend to 
310    * be symmetrical about the X axis.
311    */
312   assign_random_common_w(p->epicycles);
313   return p;
314 }
315
316 static void
317 delete_body(Body *p)
318 {
319   delete_circle_chain(p->epicycles);
320   free(p);
321 }
322
323
324 static void 
325 draw_body(Body *pb, GC gc)
326 {
327   XDrawLine(dpy, window, gc, pb->old_x, pb->old_y, pb->x, pb->y);
328 }
329
330 static long
331 compute_divisor_lcm(Circle *p)
332 {
333   long l = 1;
334   
335   while (p)
336     {
337       l = lcm(l, p->divisor);
338       p = p->pchild;
339     }
340   return l;
341 }
342
343               
344 /* move_body()
345  *
346  * Calculate the position for the body at time T.  We work in double 
347  * rather than int to avoid the cumulative errors that would be caused
348  * by the rounding implicit in an assignment to int.
349  */
350 static void
351 move_body(Body *pb, double t)
352 {
353   Circle *p;
354   double x, y;
355
356   pb->old_x = pb->x;
357   pb->old_y = pb->y;
358   
359   x = pb->x_origin;
360   y = pb->y_origin;
361   
362   for (p=pb->epicycles; NULL != p; p=p->pchild)
363     {
364       /* angular pos = initial_pos + time * angular speed */
365       /* but this is an angular position, so modulo FULLCIRCLE. */
366       p->w = fmod(p->initial_w + (t * p->wdot), FULLCIRCLE);
367       
368       x += (p->radius * cos(p->w));
369       y += (p->radius * sin(p->w));
370     }
371   
372   pb->x = (int)x;
373   pb->y = (int)y;
374 }
375
376 static int
377 colour_init(XWindowAttributes *pxgwa)
378 {
379   XGCValues gcv;
380
381 #if 0
382   int H = random() % 360;       /* colour choice from attraction.c. */
383   double S1 = 0.25;
384   double S2 = 1.00;
385   double V = frand(0.25) + 0.75;
386   int line_width = 0;
387 #endif
388
389   int retval = 1;
390   unsigned long valuemask = 0L;
391   unsigned long fg;
392   
393   /* Free any already allocated colors...
394    */
395   if (colors)
396     {
397       free_colors(dpy, cmap, colors, ncolors);
398       colors = 0;
399       ncolors = 0;
400     }
401         
402   ncolors = get_integer_resource ("colors", "Colors");
403   if (0 == ncolors)             /* English spelling? */
404     ncolors = get_integer_resource ("colours", "Colors");
405   
406   if (ncolors < 2)
407     ncolors = 2;
408   if (ncolors <= 2)
409     mono_p = True;
410   colors = 0;
411
412   if (!mono_p)
413     {
414       colors = (XColor *) malloc(sizeof(*colors) * (ncolors+1));
415       if (!colors)
416         oom();
417           
418       make_smooth_colormap (dpy, pxgwa->visual, cmap, colors, &ncolors,
419                             True, /* allocate */
420                             False, /* not writable */
421                             True); /* verbose (complain about failure) */
422       if (ncolors <= 2)
423         {
424           if (colors)
425             free (colors);
426           colors = 0;
427           mono_p = True;
428         }
429     }
430
431   
432   bg = get_pixel_resource ("background", "Background", dpy, cmap);
433
434   /* Set the line width
435    */
436   gcv.line_width = get_integer_resource ("lineWidth", "Integer");
437   if (gcv.line_width)
438     {
439       valuemask |= GCLineWidth;
440
441       gcv.join_style = JoinRound;
442       gcv.cap_style = CapRound;
443           
444       valuemask |= (GCCapStyle | GCJoinStyle);
445     }
446   
447
448   /* Set the drawing function.
449    */
450   gcv.function = GXcopy;
451   valuemask |= GCFunction;
452   
453   /* Set the foreground.
454    */
455   if (mono_p)
456     fg = get_pixel_resource ("foreground", "Foreground", dpy, cmap);
457   else
458     fg = bg ^ get_pixel_resource (("color0"), "Foreground", dpy, cmap); 
459   gcv.foreground = fg;
460   valuemask |= GCForeground;
461
462   /* Actually create the GC.
463    */
464   color0 = XCreateGC (dpy, window, valuemask, &gcv);
465   
466   return retval;
467 }
468
469
470 /* check_events(); originally from XScreensaver: hacks/maze.c,
471  * but now quite heavily modified.
472  *
473  * Reaction to events:-
474  *
475  * Mouse 1 -- new figure }
476  *       2 -- new figure }-- ignored when running on root window.
477  *       3 -- exit       }
478  *
479  * Window resized or exposed -- new figure.
480  * Window iconised -- wait until it's re-mapped, then start a new figure.
481  */
482 static int
483 check_events (void)                        /* X event handler [ rhess ] */
484 {
485   XEvent e;
486   int unmapped = 0;
487         
488   while (unmapped || XPending(dpy))
489     {
490       XNextEvent(dpy, &e);
491                 
492       switch (e.type)
493         {
494         case ButtonPress:
495           switch (e.xbutton.button)
496             {
497             case 3:
498               exit (0);
499               break;
500                                 
501             case 2:
502             case 1:
503             default:
504               restart = 1 ;
505               stop = 0 ;
506               break;
507             }
508           break;
509                         
510         case ConfigureNotify:
511           restart = 1;
512           break;
513                         
514         case UnmapNotify:
515           printf("unmapped!\n");
516           unmapped = 1;
517           restart = 1;                  /* restart with new fig. when re-mapped. */
518           break;
519                         
520         case Expose:            
521           if (0 == e.xexpose.count)
522             {
523                                 /* We can get several expose events in the queue.
524                                  * Only the last one has a zero count.  We eat
525                                  * events in this function so as to avoid restarting
526                                  * the screensaver many times in quick succession.
527                                  */
528               restart = 1;
529             }
530           /* If we had been unmapped and are now waiting to be re-mapped,
531            * indicate that we condition we are waiting for is now met.
532            */
533           if (unmapped)
534             printf("re-mapped!\n");
535           unmapped = 0;
536           break;
537
538         default:
539           screenhack_handle_event(dpy, &e);
540           break;
541         }
542                 
543       /* If we're unmapped, don't return to the caller.  This
544        * prevents us wasting CPU, calculating new positions for
545        * things that will never be plotted.   This is a real CPU
546        * saver.
547        */
548       if (!unmapped)
549         return 1;
550     }
551   return 0;
552 }
553
554
555 static void
556 setup(void)
557 {
558   XWindowAttributes xgwa;
559   int root;
560   
561   XGetWindowAttributes (dpy, window, &xgwa);
562   cmap = xgwa.colormap;
563
564   width = xgwa.width;
565   height = xgwa.height;
566   x_offset = width / 2;
567   y_offset = height / 2;
568   unit_pixels = width < height ? width : height;
569
570   {
571     static Bool done = False;
572     if (!done)
573       {
574         colour_init(&xgwa);
575         done = True;
576       }
577   }
578   
579   root = get_boolean_resource("root", "Boolean");
580   
581   if (root)
582     {
583       XSelectInput(dpy, window, ExposureMask);
584     }
585   else
586     {
587       XWindowAttributes xgwa;
588       XGetWindowAttributes (dpy, window, &xgwa);
589       XSelectInput (dpy, window,
590                     xgwa.your_event_mask | ExposureMask |
591                     ButtonPressMask |StructureNotifyMask);
592     }
593   
594 }
595 static void
596 color_step(Body *pb, double frac)
597 {
598   if (!mono_p)
599     {
600       int newshift = ncolors * fmod(frac * colour_cycle_rate, 1.0);
601       if (newshift != color_shift_pos)
602         {
603           pb->current_color = newshift;
604           XSetForeground (dpy, color0, colors[pb->current_color].pixel);
605           color_shift_pos = newshift;
606         }
607     }
608 }
609
610
611 long
612 distance(long x1, long y1, long x2, long y2)
613 {
614   long dx, dy;
615
616   dx = x2 - x1;
617   dy = y2 - y1;
618   return dx*dx + dy*dy;
619 }
620
621 #if 0
622 static int poisson_irand(double p)
623 {
624   int r = 1;
625   while (fabs(frand(1.0)) < p)
626     ++r;
627   return r < 1 ? 1 : r;
628 }
629 #endif
630
631 static void
632 precalculate_figure(Body *pb,
633                     double xtime, double step,
634                     int *x_max, int *y_max,
635                     int *x_min, int *y_min)
636 {
637   double t;
638   
639   move_body(pb, 0.0); /* move once to avoid initial line from origin */
640   *x_min = *x_max = pb->x;
641   *y_min = *y_max = pb->y;
642   
643   for (t=0.0; t<xtime; t += step)
644     {
645       move_body(pb, t); /* move once to avoid initial line from origin */
646       if (pb->x > *x_max)
647         *x_max = pb->x;
648       if (pb->x < *x_min)
649         *x_min = pb->x;
650       if (pb->y > *y_max)
651         *y_max = pb->y;
652       if (pb->y < *y_min)
653         *y_min = pb->y;
654     }
655 }
656
657 static int i_max(int a, int b)
658 {
659   return (a>b) ? a : b;
660 }
661
662 static void rescale_circles(Body *pb,
663                             int x_max, int y_max,
664                             int x_min, int y_min)
665 {
666   double xscale, yscale, scale;
667   double xm, ym;
668   
669   x_max -= x_offset;
670   x_min -= x_offset;
671   y_max -= y_offset;
672   y_min -= y_offset;
673
674   x_max = i_max(x_max, -x_min);
675   y_max = i_max(y_max, -y_min);
676
677
678   xm = width / 2.0;
679   ym = height / 2.0;
680   if (x_max > xm)
681     xscale = xm / x_max;
682   else
683     xscale = 1.0;
684   if (y_max > ym)
685     yscale = ym / y_max;
686   else
687     yscale = 1.0;
688
689   if (xscale < yscale)          /* wider than tall */
690     scale = xscale;             /* ensure width fits onscreen */
691   else
692     scale = yscale;             /* ensure height fits onscreen */
693
694
695   scale *= FILL_PROPORTION;     /* only fill FILL_PROPORTION of screen */
696   if (scale < 1.0)              /* only reduce, don't enlarge. */
697     {
698       Circle *p;
699       for (p=pb->epicycles; p; p=p->pchild)
700         {
701           p->radius *= scale;
702         }
703     }
704   else
705     {
706       printf("enlarge by x%.2f skipped...\n", scale);
707     }
708 }
709
710
711 /* angular speeds of the circles are harmonics of a fundamental
712  * value.  That should please the Pythagoreans among you... :-)
713  */
714 static double 
715 random_wdot_max(void)
716 {
717   /* Maximum and minimum values for the choice of wdot_max.  Possible
718    * epicycle speeds vary from wdot_max to (wdot_max * harmonics).
719    */
720   double minspeed, maxspeed;
721   minspeed = get_float_resource("minSpeed", "Double");
722   maxspeed = get_float_resource("maxSpeed", "Double");
723   return harmonics * (minspeed + FULLCIRCLE * frand(maxspeed-minspeed));
724 }
725
726 /* this is the function called for your screensaver */
727 /*GLOBAL*/ void
728 screenhack(Display *disp, Window win)
729 {
730   Body *pb = NULL;
731   long l;
732   double t, timestep, circle, xtime, timestep_coarse;
733   int delay;
734   int uncleared = 1;
735   int xmax, xmin, ymax, ymin;
736   int holdtime = get_integer_resource ("holdtime", "Integer");
737
738   dpy = disp;
739   window = win;
740
741   circle = FULLCIRCLE;
742   
743   XClearWindow(dpy, window);
744   uncleared = 0;
745   
746   delay = get_integer_resource ("delay", "Integer");
747   harmonics = get_integer_resource("harmonics", "Integer");
748   divisorPoisson = get_float_resource("divisorPoisson", "Double");
749   
750   timestep = get_float_resource("timestep", "Double");
751   timestep_coarse = timestep *
752     get_float_resource("timestepCoarseFactor", "Double");
753   
754   sizeFactorMin = get_float_resource("sizeFactorMin", "Double");
755   sizeFactorMax = get_float_resource("sizeFactorMax", "Double");
756
757   minCircles = get_integer_resource ("minCircles", "Integer");
758   maxCircles = get_integer_resource ("maxCircles", "Integer");
759
760   xtime = 0; /* is this right? */
761   while (0 == stop)
762     {
763       setup(); /* do this inside the loop to cope with any window resizing */
764       restart = 0;
765
766       /* Flush any outstanding events; this has the side effect of
767        * reducing the number of "false restarts"; resdtarts caused by
768        * one event (e.g. ConfigureNotify) followed by another
769        * (e.g. Expose).
770        */
771       XSync(dpy, True);
772           
773       wdot_max = random_wdot_max();
774           
775       if (pb)
776         {
777           delete_body(pb);
778           pb = NULL;
779         }
780       pb = new_body();
781       pb->x_origin = pb->x = x_offset;
782       pb->y_origin = pb->y = y_offset;
783           
784       
785       if (uncleared)
786         {
787           erase_full_window(dpy, window);
788           uncleared = 0;
789         }
790
791       fflush(stdout);
792       precalculate_figure(pb, xtime, timestep_coarse,
793                           &xmax, &ymax, &xmin, &ymin);
794
795       rescale_circles(pb, xmax, ymax, xmin, ymin);
796       
797       move_body(pb, 0.0); /* move once to avoid initial line from origin */
798       move_body(pb, 0.0); /* move once to avoid initial line from origin */
799
800       
801       t = 0.0;                  /* start at time zero. */
802
803       l = compute_divisor_lcm(pb->epicycles);
804       
805       colour_cycle_rate = fabs(l);
806       
807       xtime = fabs(l * circle / wdot_max);
808
809       if (colors)                               /* (colors==NULL) if mono_p */
810         XSetForeground (dpy, color0, colors[pb->current_color].pixel);
811
812       while (0 == restart)
813         {
814           color_step(pb, t/xtime );
815           draw_body(pb, color0);
816           uncleared = 1;
817
818           
819           /* Check if the figure is complete...*/
820           if (t > xtime)
821             {
822               XSync (dpy, False);
823
824               check_events();
825               if (holdtime)
826                 sleep(holdtime); /* show complete figure for a bit. */
827
828               restart = 1;      /* begin new figure. */
829             }
830           
831           
832           check_events();
833           if (delay)
834             usleep (delay);
835           
836           t += timestep;
837           move_body(pb, t);
838           check_events();
839         }
840     }
841 }
842