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