From http://www.jwz.org/xscreensaver/xscreensaver-5.27.tar.gz
[xscreensaver] / hacks / piecewise.c
1 /* piecewise, 21jan2003
2  * Geoffrey Irving <irving@caltech.edu>
3  *
4  * Permission to use, copy, modify, distribute, and sell this software and its
5  * documentation for any purpose is hereby granted without fee, provided that
6  * the above copyright notice appear in all copies and that both that
7  * copyright notice and this permission notice appear in supporting
8  * documentation.  No representations are made about the suitability of this
9  * software for any purpose.  It is provided "as is" without express or 
10  * implied warranty.
11  */
12
13 #include <stdarg.h>
14 #include <math.h>
15 #include "screenhack.h"
16
17 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
18 # include "xdbe.h"
19 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
20
21 #if !defined( __GNUC__ ) && !defined(__cplusplus) && !defined(c_plusplus)
22 #undef inline
23 #define inline                  /* */
24 #endif
25
26 #define X_PI (180 * 64)
27
28 #define START 0
29 #define CROSS 1
30 #define FINISH 2
31
32 #define ARC_BUFFER_SIZE 256
33
34
35 typedef struct _tree {
36   struct _tree *l, *r;   /* left and right children */
37                          /* extra stuff would go here */
38   } tree;
39
40
41 struct _fringe;
42
43 typedef struct _circle {
44   int r;                    /* radius */
45   double x, y;              /* position */
46   double dx, dy;            /* velocity */
47
48   int visible;              /* default visibility */
49   struct _fringe *lo, *hi;  /* lo and hi fringes */
50
51   int ni;                   /* number of intersections */
52   int *i;                   /* sorted intersection list */
53   } circle;             
54
55 typedef struct _fringe {
56   struct _fringe *l, *r;  /* left and right children for splay trees */
57
58   circle *c;              /* associated circle */
59   int side;               /* 0 for lo, 1 for hi */
60
61   int mni;                /* size of intersection array */
62   int ni;                 /* number of intersections */
63   int *i;                 /* sorted intersection list */
64   } fringe;
65
66
67 typedef struct _event {
68   struct _event *l, *r;    /* left and right children for splay tree */
69
70   int kind;                /* type of event */
71   double x, y;             /* position */
72   fringe *lo, *hi;         /* fringes */
73   } event;
74
75
76 struct state {
77   Display *dpy;
78   Window window;
79
80   double event_cut_y;
81
82   double fringe_start_cut_x;
83   double fringe_start_cut_y;
84
85   double fringe_double_cut_x;
86   double fringe_double_cut_y;
87   fringe *fringe_double_cut_lo;
88   fringe *fringe_double_cut_hi;
89
90   int arc_buffer_count;
91   XArc arc_buffer[ARC_BUFFER_SIZE];
92
93   Bool dbuf;
94   XColor *colors;
95   XGCValues gcv;
96   GC erase_gc, draw_gc;
97   XWindowAttributes xgwa;
98   Pixmap b, ba, bb;    /* double-buffering pixmap */
99
100 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
101   XdbeBackBuffer backb;
102 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
103
104   int count, delay, ncolors, colorspeed, color_index, flags, iterations;
105   int color_iterations;
106   circle *circles;
107 };
108
109 typedef int (*cut)(struct state *, tree*);    /* cut x is <, =, or > 0 given a <, =, or > x for some a */
110
111
112
113 /******** splaying code */
114
115 /* Top-down splay routine.  Reference:
116  *   "Self-adjusting Binary Search Trees", Sleator and Tarjan,
117  *   JACM Volume 32, No 3, July 1985, pp 652-686.
118  * See page 668 for specific splay transformations */
119
120 static tree *splay(struct state *st, cut c, tree *t)
121 {
122   int v, vv;
123   tree *l, *r;
124   tree **lr, **rl;
125   tree *x, *y, *z;
126
127   if (!t)
128     return 0;
129
130   /* initialization */
131   x = t;
132   l = r = 0;
133   lr = &l;
134   rl = &r;
135
136   /* top-down splaying loop */
137   for (;;) {
138     v = c(st, x);
139     if (v == 0)
140       break;               /*** success ***/
141     else if (v < 0) {
142       y = x->l;
143       if (!y)
144         break;             /*** trivial ***/
145       else {
146         vv = c(st, y);
147         if (vv == 0) {
148           *rl = x;         /*** zig ***/
149           rl = &x->l;
150           x = y;
151           break;
152           }
153         else if (vv < 0) {
154           z = y->l;
155           if (!z) {
156             *rl = x;       /*** zig ***/
157             rl = &x->l;
158             x = y;
159             break;
160             }
161           else {
162             x->l = y->r;   /*** zig-zig ***/
163             y->r = x;
164             *rl = y;
165             rl = &y->l;
166             x = z;
167             }
168           }
169         else { /* vv > 0 */
170           z = y->r;
171           if (!z) {
172             *rl = x;       /*** zig ***/
173             rl = &x->l;
174             x = y;
175             break;
176             }
177           else {           /*** zig-zag ***/
178             *lr = y;
179             lr = &y->r;
180             *rl = x;
181             rl = &x->l;
182             x = z;
183             }
184           }
185         }
186       }
187     else { /* v > 0 */
188       y = x->r;
189       if (!y)
190         break;             /*** trivial ***/
191       else {
192         vv = c(st, y);
193         if (vv == 0) {
194           *lr = x;         /*** zig ***/
195           lr = &x->r;
196           x = y;
197           break;
198           }
199         else if (vv > 0) {
200           z = y->r;
201           if (!z) {
202             *lr = x;       /*** zig ***/
203             lr = &x->r;
204             x = y;
205             break;
206             }
207           else {
208             x->r = y->l;   /*** zig-zig ***/
209             y->l = x;
210             *lr = y;
211             lr = &y->r;
212             x = z;
213             }
214           }
215         else { /* vv < 0 */
216           z = y->l;
217           if (!z) {
218             *lr = x;       /*** zig ***/
219             lr = &x->r;
220             x = y;
221             break;
222             }
223           else {           /*** zig-zag ***/
224             *rl = y;
225             rl = &y->l;
226             *lr = x;
227             lr = &x->r;
228             x = z;
229             }
230           }
231         }
232       }
233     }
234
235   /* completion */
236   *lr = x->l;
237   x->l = l;
238   *rl = x->r;
239   x->r = r;
240   return x;
241   }
242
243 static tree *splay_min(tree *t)
244 {
245   tree *r, **rl;
246   tree *x, *y, *z;
247
248   if (!t)
249     return 0;
250
251   x = t;
252   r = 0;
253   rl = &r;
254
255   for (;;) {
256     y = x->l;
257     if (!y)
258       break;           /*** trivial ***/
259     else {
260       z = y->l;
261       if (!z) {
262         *rl = x;       /*** zig ***/
263         rl = &x->l;
264         x = y;
265         break;
266         }
267       else {
268         x->l = y->r;   /*** zig-zig ***/
269         y->r = x;
270         *rl = y;
271         rl = &y->l;
272         x = z;
273         }
274       }
275     }
276
277   x->l = 0;
278   *rl = x->r;
279   x->r = r;
280   return x;
281   }
282
283 static tree *splay_max(tree *t)
284 {
285   tree *l, **lr;
286   tree *x, *y, *z;
287
288   if (!t)
289     return 0;
290
291   x = t;
292   l = 0;
293   lr = &l;
294
295   for (;;) {
296     y = x->r;
297     if (!y)
298       break;           /*** trivial ***/
299     else {
300       z = y->r;
301       if (!z) {
302         *lr = x;       /*** zig ***/
303         lr = &x->r;
304         x = y;
305         break;
306         }
307       else {
308         x->r = y->l;   /*** zig-zig ***/
309         y->l = x;
310         *lr = y;
311         lr = &y->r;
312         x = z;
313         }
314       }
315     }
316
317   *lr = x->l;
318   x->l = l;
319   x->r = 0;
320   return x;
321   }
322
323 /******** circles and fringe */
324
325 static inline double fringe_x(fringe *f, double y)
326 {
327   double dy, d;
328   dy = f->c->y - y;
329   d = sqrt(f->c->r * f->c->r - dy * dy);
330   return f->side ? f->c->x + d : f->c->x - d;
331   }
332
333 static inline void fringe_add_intersection(fringe *f, double x, double y)
334 {
335   f->ni++;
336   if (f->mni < f->ni) {
337     f->mni += 2;
338     f->i = realloc(f->i, sizeof(int) * f->mni);
339     }
340   f->i[f->ni-1] = rint(atan2(y - f->c->y, x - f->c->x) * X_PI / M_PI);
341   }
342
343 static circle *init_circles(struct state *st, int n, int w, int h)
344 {
345   int i, r0, dr, speed;
346   double v, a;
347   double minradius, maxradius;
348   fringe *s = malloc(sizeof(fringe) * n * 2);    /* never freed */
349   circle *c = malloc(sizeof(circle) * n);
350
351   speed = get_integer_resource(st->dpy, "speed", "Speed");
352   minradius = get_float_resource(st->dpy, "minradius", "Float");
353   maxradius = get_float_resource(st->dpy, "maxradius", "Float");
354   if (maxradius < minradius)
355     maxradius = minradius;
356
357   r0 = ceil(minradius * h); 
358   dr = floor(maxradius * h) - r0 + 1;
359
360   for (i=0;i<n;i++) {
361     c[i].r = r0 + ((dr > 0) ? random() % dr : 0);
362     c[i].x = c[i].r + frand(w - 1 - 2 * c[i].r);
363     c[i].y = c[i].r + frand(h - 1 - 2 * c[i].r);
364     c[i].visible = random() & 1;
365
366     c[i].ni = 0;
367     c[i].i = 0;
368
369     a = frand(2 * M_PI);
370     v = (1 + frand(0.5)) * speed / 10.0;
371     c[i].dx = v * cos(a);
372     c[i].dy = v * sin(a);
373
374     c[i].lo = s+i+i;
375     c[i].hi = s+i+i+1;
376     c[i].lo->c = c[i].hi->c = c+i;
377     c[i].lo->side = 0;
378     c[i].hi->side = 1;
379     c[i].lo->mni = c[i].lo->ni = c[i].hi->mni = c[i].hi->ni = 0;
380     c[i].lo->i = c[i].hi->i = 0;
381     }
382
383   return c;
384   }
385
386 /* this is a hack, but I guess that's what I writing anyways */
387 static void tweak_circle(circle *c)
388 {
389   c->x += frand(2) - 1;
390   c->y += frand(1) + 0.1;
391   }
392
393 static void move_circle(circle *c, int w, int h)
394 {
395   c->x += c->dx;
396   if (c->x < c->r) {
397     c->x = c->r;
398     c->dx = -c->dx;
399     }
400   else if (c->x >= w - c->r) {
401     c->x = w - 1 - c->r;
402     c->dx = -c->dx;
403     }
404   c->y += c->dy;
405   if (c->y < c->r) {
406     c->y = c->r;
407     c->dy = -c->dy;
408     }
409   else if (c->y >= h - c->r) {
410     c->y = h - 1 - c->r;
411     c->dy = -c->dy;
412     }
413   }
414
415 /******** event queue */
416
417 static int event_cut(struct state *st, event *e)
418 {
419   return st->event_cut_y == e->y ? 0 : st->event_cut_y < e->y ? -1 : 1;
420   }
421
422 static void event_insert(struct state *st, event **eq, event *e)
423 {
424   if (!*eq) {
425     e->l = e->r = 0;
426     *eq = e;
427     return; /* avoid leak */
428     }
429
430   st->event_cut_y = e->y;
431   *eq = (event*)splay(st, (cut)event_cut, (tree*)*eq);
432
433   if (e->y == (*eq)->y) {
434     if (!((e->lo == (*eq)->lo && e->hi == (*eq)->hi) || (e->lo == (*eq)->hi && e->hi == (*eq)->lo))) {
435       e->l = (*eq)->l;
436       e->r = 0;             /* doing this instead of dying might be dangerous */
437       (*eq)->l = e;           
438       }
439     else
440       free(e); /* don't leak! */
441     }
442   else if (e->y < (*eq)->y) {
443     e->l = (*eq)->l;
444     e->r = *eq;
445     (*eq)->l = 0;
446     *eq = e;
447     }
448   else {
449     e->l = *eq;
450     e->r = (*eq)->r; 
451     (*eq)->r = 0;
452     *eq = e;
453     }
454   }
455
456 static void circle_start_event(struct state *st, event **eq, circle *c)
457 {
458   event *s;
459   s = malloc(sizeof(event));
460   s->kind = START;
461   s->x = c->x;
462   s->y = c->y - c->r;
463   s->lo = c->lo;
464   s->hi = c->hi;
465   event_insert(st, eq, s);
466   }
467
468 static void circle_finish_event(struct state *st, event **eq, circle *c)
469 {
470   event *f;
471   f = malloc(sizeof(event));
472   f->kind = FINISH;
473   f->x = c->x;
474   f->y = c->y + c->r;
475   f->lo = c->lo;
476   f->hi = c->hi;
477   event_insert(st, eq, f);
478   }
479
480 static event *event_next(event **eq)
481 {
482   event *e;
483   if (!*eq)
484     return 0;
485   else {
486     e = (event*)splay_min((tree*)*eq);
487     *eq = e->r; 
488     return e;
489     }
490   }
491
492 static void event_shred(event *e)
493 {
494   if (e) {
495     event_shred(e->l);
496     event_shred(e->r);
497     free(e);
498     }
499   }
500
501 /******** fringe intersection */
502
503 #if 0
504 static inline int check_fringe_intersection(double ye, fringe *lo, fringe *hi, double x, double y)
505 {
506   return ye <= y && ((x < lo->c->x) ^ lo->side) && ((x < hi->c->x) ^ hi->side);
507   }
508 #endif /* 0 */
509
510 static void fringe_intersect(struct state *st, event **eq, double y, fringe *lo, fringe *hi)
511 {
512   event *e;
513   double dx, dy, sd, rs, rd, d, sx, sy, rp, sqd;
514   double x1, y1, x2, y2;
515
516   if (lo->c == hi->c)
517     return;
518
519   dx = hi->c->x - lo->c->x; 
520   dy = hi->c->y - lo->c->y; 
521   sd = dx * dx + dy * dy; 
522
523   if (sd == 0)
524     return;
525
526   rs = hi->c->r + lo->c->r; 
527   rd = hi->c->r - lo->c->r; 
528   d = (rd * rd - sd) * (sd - rs * rs);
529
530   if (d <= 0)
531     return;
532  
533   sd = 0.5 / sd;
534   rp = rs * rd; 
535   sqd = sqrt(d); 
536   sx = (lo->c->x + hi->c->x) / 2;
537   sy = (lo->c->y + hi->c->y) / 2;
538   x1 = sx + sd * (dy * sqd - dx * rp); 
539   y1 = sy - sd * (dx * sqd + dy * rp);
540   x2 = sx - sd * (dy * sqd + dx * rp);
541   y2 = sy + sd * (dx * sqd - dy * rp);
542
543   #define CHECK(xi, yi) (y <= yi && ((xi < lo->c->x) ^ lo->side) && ((xi < hi->c->x) ^ hi->side))
544
545   #define ADD_CROSS(xi, yi, ilo, ihi) {  \
546     e = malloc(sizeof(event));   /* #### LEAK */        \
547     e->kind = CROSS;                     \
548     e->x = xi; e->y = yi;                \
549     e->lo = ilo; e->hi = ihi;            \
550     event_insert(st, eq, e);                 \
551     }
552
553   if (CHECK(x1, y1)) {
554     if (CHECK(x2, y2)) {
555       if (y1 < y2) {
556         ADD_CROSS(x1, y1, lo, hi);
557         ADD_CROSS(x2, y2, hi, lo);
558         }
559       else {
560         ADD_CROSS(x1, y1, hi, lo);
561         ADD_CROSS(x2, y2, lo, hi);
562         }
563       }
564     else
565       ADD_CROSS(x1, y1, lo, hi);
566     }
567   else if (CHECK(x2, y2))
568     ADD_CROSS(x2, y2, lo, hi); 
569
570   return;
571   }
572
573 /******** fringe trees and event handling */
574
575 #define PANIC ((fringe*)1)     /* by alignment, no fringe should every be 1 */
576
577 static fringe *check_lo(struct state *st, event **eq, double y, fringe *f, fringe *hi)
578 {
579   if (f) {
580     f = (fringe*)splay_max((tree*)f);
581     fringe_intersect(st, eq, y, f, hi);
582     }
583   return f;
584   }
585
586 static fringe *check_hi(struct state *st, event **eq, double y, fringe *lo, fringe *f)
587 {
588   if (f) {
589     f = (fringe*)splay_min((tree*)f);
590     fringe_intersect(st, eq, y, lo, f);
591     }
592   return f;
593   }
594
595 static int fringe_start_cut(struct state *st, fringe *f)
596 {
597   double x = fringe_x(f, st->fringe_start_cut_y);
598   return st->fringe_start_cut_x == x ? 0 : st->fringe_start_cut_x < x ? -1 : 1;
599   }
600
601 static fringe *fringe_start(struct state *st, event **eq, fringe *f, double x, double y, fringe *lo, fringe *hi)
602 {
603   double sx;
604
605   if (!f) {
606     circle_finish_event(st, eq, lo->c);
607     lo->l = 0;
608     lo->r = hi;
609     hi->l = hi->r = 0;
610     return lo;
611     }
612
613   st->fringe_start_cut_x = x;
614   st->fringe_start_cut_y = y;
615   f = (fringe*)splay(st, (cut)fringe_start_cut, (tree*)f);
616
617   sx = fringe_x(f, y);
618   if (x == sx) {       /* time to cheat my way out of handling degeneracies */
619     tweak_circle(lo->c);
620     circle_start_event(st, eq, lo->c);
621     return f;
622     }
623   else if (x < sx) {
624     circle_finish_event(st, eq, lo->c);
625     f->l = check_lo(st, eq, y, f->l, lo);    
626     fringe_intersect(st, eq, y, hi, f);
627     lo->l = f->l;
628     lo->r = f;
629     f->l = hi;
630     hi->l = hi->r = 0;
631     return lo;
632     }
633   else {
634     circle_finish_event(st, eq, lo->c);
635     fringe_intersect(st, eq, y, f, lo);
636     f->r = check_hi(st, eq, y, hi, f->r);
637     hi->r = f->r;
638     hi->l = f;
639     f->r = lo;
640     lo->l = lo->r = 0;
641     return hi;
642     }
643   }
644
645 static int fringe_double_cut(struct state *st, fringe *f)
646 {
647   double x;
648   if (f == st->fringe_double_cut_lo || f == st->fringe_double_cut_hi)
649     return 0;
650   x = fringe_x(f, st->fringe_double_cut_y);
651   return st->fringe_double_cut_x == x ? 0 : st->fringe_double_cut_x < x ? -1 : 1;
652   }
653
654 static int fringe_double_splay(struct state *st, fringe *f, double x, double y, fringe *lo, fringe *hi)
655 {
656   st->fringe_double_cut_x = x;
657   st->fringe_double_cut_y = y;
658   st->fringe_double_cut_lo = lo;
659   st->fringe_double_cut_hi = hi;
660   f = (fringe*)splay(st, (cut)fringe_double_cut, (tree*)f);
661
662   if (f == lo)
663     return (f->r = (fringe*)splay_min((tree*)f->r)) == hi;
664   else if (f == hi)
665     return (f->l = (fringe*)splay_max((tree*)f->l)) == lo;
666   else
667     return 0;
668   }
669
670 static fringe *fringe_cross(struct state *st, event **eq, fringe *f, double x, double y, fringe *lo, fringe *hi)
671 {
672   fringe *l, *r;
673   if (!fringe_double_splay(st, f, x, y, lo, hi))
674     return PANIC;
675   l = check_lo(st, eq, y, lo->l, hi);
676   r = check_hi(st, eq, y, lo, hi->r);
677   lo->l = hi;
678   lo->r = r;
679   hi->l = l;
680   hi->r = 0;
681   return lo;
682   }
683
684 static fringe *fringe_finish(struct state *st, event **eq, fringe *f, double x, double y, fringe *lo, fringe *hi)
685 {
686   if (!fringe_double_splay(st, f, x, y, lo, hi))
687     return PANIC;
688   else if (!lo->l)
689     return hi->r;
690   else if (!hi->r)
691     return lo->l;
692   else {
693     lo->l = (fringe*)splay_max((tree*)lo->l);
694     hi->r = (fringe*)splay_min((tree*)hi->r);
695     fringe_intersect(st, eq, y, lo->l, hi->r);
696     lo->l->r = hi->r;
697     hi->r->l = 0;
698     return lo->l;
699     }
700   }
701
702 /******** plane sweep */
703
704 static void sweep(struct state *st, int n, circle *c)
705 {
706   int i;
707   event *eq, *e;
708   fringe *f;
709
710   RESTART:
711   #define CHECK_PANIC()                 \
712     if (f == PANIC) {                   \
713       free(e);                          \
714       event_shred(eq);                  \
715       for (i=0;i<n;i++) {               \
716         tweak_circle(c+i);              \
717         c[i].lo->ni = c[i].hi->ni = 0;  \
718         }                               \
719       goto RESTART;                     \
720       }
721
722   eq = 0;
723   for (i=0;i<n;i++)
724     circle_start_event(st, &eq, c+i); 
725   f = 0;
726
727   while ((e = event_next(&eq))) {
728     switch (e->kind) {
729       case START:
730         f = fringe_start(st, &eq, f, e->x, e->y, e->lo, e->hi);
731         break;
732       case CROSS:
733         f = fringe_cross(st, &eq, f, e->x, e->y, e->lo, e->hi);
734         CHECK_PANIC();
735         fringe_add_intersection(e->lo, e->x, e->y);
736         fringe_add_intersection(e->hi, e->x, e->y);
737         break;
738       case FINISH:
739         f = fringe_finish(st, &eq, f, e->x, e->y, e->lo, e->hi);
740         CHECK_PANIC();
741         break;
742       }
743     free(e);
744     }
745   }
746
747 /******** circle drawing */
748
749 static void adjust_circle_visibility(circle *c)
750 {
751   int i, j, n, a;
752   int *in;
753   n = c->lo->ni + c->hi->ni;
754   in = malloc(sizeof(int) * n);
755   for (i=0;i<c->hi->ni;i++)
756     in[i] = c->hi->i[i]; 
757   for (i=c->lo->ni-1;i>=0;i--)
758     in[n-i-1] = c->lo->i[i] > 0 ? c->lo->i[i] : c->lo->i[i] + 2 * X_PI;
759   c->lo->ni = c->hi->ni = 0;
760
761   i = j = 0;
762   a = 0;
763   while (i < n && j < c->ni)           /* whee */
764     a = (in[i] < c->i[j] ? in[i++] : c->i[j++]) - a;
765   while (i < n)
766     a = in[i++] - a;
767   while (j < c->ni)
768     a = c->i[j++] - a;
769
770   if (a > X_PI) 
771     c->visible = !c->visible;
772   free(c->i);  
773   c->ni = n;
774   c->i = in;
775   }
776
777 static void flush_arc_buffer(struct state *st, Drawable w, GC gc)
778 {
779   if (st->arc_buffer_count) {
780     XDrawArcs(st->dpy, w, gc, st->arc_buffer, st->arc_buffer_count);
781     st->arc_buffer_count = 0;
782     }
783   }
784
785 static void draw_circle(struct state *st, Drawable w, GC gc, circle *c)
786 {
787   int i, xi, yi, di;
788   adjust_circle_visibility(c); 
789
790   xi = rint(c->x - c->r);
791   yi = rint(c->y - c->r);
792   di = c->r << 1;
793
794   #define ARC(p, a1, a2) {                                \
795     if (((p) & 1) ^ c->visible) {                         \
796       st->arc_buffer[st->arc_buffer_count].x      = xi;           \
797       st->arc_buffer[st->arc_buffer_count].y      = yi;           \
798       st->arc_buffer[st->arc_buffer_count].width  = di;           \
799       st->arc_buffer[st->arc_buffer_count].height = di;           \
800       st->arc_buffer[st->arc_buffer_count].angle1 = -(a1);        \
801       st->arc_buffer[st->arc_buffer_count].angle2 = (a1) - (a2);  \
802       st->arc_buffer_count++;                                 \
803       if (st->arc_buffer_count == ARC_BUFFER_SIZE)            \
804         flush_arc_buffer(st, w, gc);                     \
805       }                                                   \
806     }
807
808   if (!c->ni)
809     ARC(0, 0, 2 * X_PI)
810   else
811     ARC(0, c->i[c->ni-1], c->i[0] + 2 * X_PI)
812   for (i=1;i<c->ni;i++)
813     ARC(i, c->i[i-1], c->i[i])
814   }
815
816 /******** toplevel */
817
818 #if 0
819 static void
820 check_for_leaks (void)
821 {
822 #ifdef HAVE_SBRK
823   static unsigned long early_brk = 0;
824   unsigned long max = 30 * 1024 * 1024;  /* 30 MB */
825   int b = (unsigned long) sbrk(0);
826   if (early_brk == 0)
827     early_brk = b;
828   else if (b > early_brk + max)
829     {
830       fprintf (stderr, "%s: leaked %lu MB -- aborting!\n",
831                progname, ((b - early_brk) >> 20));
832       exit (1);
833     }
834 #endif /* HAVE_SBRK */
835 }
836 #endif
837
838 static void *
839 piecewise_init (Display *dd, Window ww)
840 {
841   struct state *st = (struct state *) calloc (1, sizeof(*st));
842   st->dpy = dd;
843   st->window = ww;
844
845   st->count = get_integer_resource(st->dpy, "count", "Integer");
846   st->delay = get_integer_resource(st->dpy, "delay", "Integer");
847   st->ncolors = get_integer_resource(st->dpy, "ncolors", "Integer");
848   st->colorspeed = get_integer_resource(st->dpy, "colorspeed", "Integer");
849   st->dbuf = get_boolean_resource(st->dpy, "doubleBuffer", "Boolean");
850
851 # ifdef HAVE_COCOA      /* Don't second-guess Quartz's double-buffering */
852   st->dbuf = False;
853 # endif
854
855   st->color_iterations = st->colorspeed ? 100 / st->colorspeed : 100000;
856   if (!st->color_iterations)
857     st->color_iterations = 1;
858
859   XGetWindowAttributes(st->dpy, st->window, &st->xgwa);
860   st->colors = calloc(sizeof(XColor), st->ncolors);
861
862   if (get_boolean_resource(st->dpy, "mono", "Boolean")) {  
863     MONO:
864       st->ncolors = 1;
865       st->colors[0].pixel = get_pixel_resource(st->dpy, st->xgwa.colormap, "foreground", "Foreground");
866     }
867   else {
868     make_color_loop(st->xgwa.screen, st->xgwa.visual, st->xgwa.colormap,
869                     0, 1, 1, 120, 1, 1, 240, 1, 1,
870                     st->colors, &st->ncolors, True, False);
871     if (st->ncolors < 2)
872       goto MONO; 
873     }
874
875   if (st->dbuf) {
876 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
877     st->b = st->backb = xdbe_get_backbuffer(st->dpy, st->window, XdbeUndefined);
878 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
879     
880     if (!st->b) {
881       st->ba = XCreatePixmap(st->dpy, st->window, st->xgwa.width, st->xgwa.height,st->xgwa.depth);
882       st->bb = XCreatePixmap(st->dpy, st->window, st->xgwa.width, st->xgwa.height,st->xgwa.depth);
883       st->b = st->ba;
884       }
885     }
886   else
887     st->b = st->window;
888
889   /* erasure gc */
890   st->gcv.foreground = get_pixel_resource(st->dpy, st->xgwa.colormap, "background", "Background");
891   st->erase_gc = XCreateGC (st->dpy, st->b, GCForeground, &st->gcv);
892
893   /* drawing gc */
894   st->flags = GCForeground;
895   st->color_index = random() % st->ncolors;
896   st->gcv.foreground = st->colors[st->color_index].pixel;
897   st->draw_gc = XCreateGC(st->dpy, st->b, st->flags, &st->gcv);
898
899   /* initialize circles */
900   st->circles = init_circles(st, st->count, st->xgwa.width, st->xgwa.height);
901   
902   st->iterations = 0;
903
904   return st;
905 }
906
907 static unsigned long
908 piecewise_draw (Display *dpy, Window window, void *closure)
909 {
910   struct state *st = (struct state *) closure;
911   int i;
912
913   XFillRectangle (st->dpy, st->b, st->erase_gc, 0, 0, st->xgwa.width, st->xgwa.height);
914
915   sweep(st, st->count, st->circles);
916   for (i=0;i<st->count;i++) {
917     draw_circle(st, st->b, st->draw_gc, st->circles+i);
918     move_circle(st->circles+i, st->xgwa.width, st->xgwa.height);
919   }
920   flush_arc_buffer(st, st->b, st->draw_gc);
921
922   if (++st->iterations % st->color_iterations == 0) {
923     st->color_index = (st->color_index + 1) % st->ncolors;
924     XSetForeground(st->dpy, st->draw_gc, st->colors[st->color_index].pixel);
925   }
926
927 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
928   if (st->backb) {
929     XdbeSwapInfo info[1];
930     info[0].swap_window = st->window;
931     info[0].swap_action = XdbeUndefined;
932     XdbeSwapBuffers (st->dpy, info, 1);
933   }
934   else
935 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
936     if (st->dbuf) {
937       XCopyArea (st->dpy, st->b, st->window, st->erase_gc, 0, 0, st->xgwa.width, st->xgwa.height, 0, 0);
938       st->b = (st->b == st->ba ? st->bb : st->ba);
939     }
940
941 /*  check_for_leaks(); */
942   return st->delay;
943 }
944
945 static void
946 piecewise_reshape (Display *dpy, Window window, void *closure, 
947                  unsigned int w, unsigned int h)
948 {
949   struct state *st = (struct state *) closure;
950   XGetWindowAttributes(st->dpy, st->window, &st->xgwa);
951 }
952
953 static Bool
954 piecewise_event (Display *dpy, Window window, void *closure, XEvent *event)
955 {
956   return False;
957 }
958
959 static void
960 piecewise_free (Display *dpy, Window window, void *closure)
961 {
962   struct state *st = (struct state *) closure;
963   free (st);
964 }
965
966
967
968 static const char *piecewise_defaults [] = {
969   ".background:         black",
970   ".foreground:         white",
971   "*delay:              10000",
972   "*speed:              15",
973   "*ncolors:            256",
974   ".colorspeed:         10",
975
976   ".count:              32",
977   ".minradius:          0.05",
978   ".maxradius:          0.2",   
979
980   "*doubleBuffer:       True",
981 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
982   "*useDBE:             True",
983 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
984 #ifdef USE_IPHONE
985   "*ignoreRotation:     True",
986 #endif
987   0
988   };
989
990 static XrmOptionDescRec piecewise_options [] = {
991   { "-delay",           ".delay",       XrmoptionSepArg, 0 },
992   { "-ncolors",         ".ncolors",     XrmoptionSepArg, 0 },
993   { "-speed",           ".speed",       XrmoptionSepArg, 0 },
994   { "-colorspeed",      ".colorspeed",  XrmoptionSepArg, 0 },
995
996   { "-count",           ".count",       XrmoptionSepArg, 0 },
997   { "-minradius",       ".minradius",   XrmoptionSepArg, 0 },
998   { "-maxradius",       ".maxradius",   XrmoptionSepArg, 0 },
999
1000   { "-db",              ".doubleBuffer", XrmoptionNoArg,  "True" },
1001   { "-no-db",           ".doubleBuffer", XrmoptionNoArg,  "False" },
1002   { 0, 0, 0, 0 }
1003   };
1004
1005
1006 XSCREENSAVER_MODULE ("Piecewise", piecewise)