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