git.hungrycats.org Git - xscreensaver/blob - 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_JWXYZ      /* 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 HAVE_MOBILE
 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)