1 /* piecewise, 21jan2003
2 * Geoffrey Irving <irving@caltech.edu>
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
15 #include "screenhack.h"
17 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
19 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
21 #define X_PI (180 * 64)
23 /******** splaying code */
25 typedef struct _tree {
26 struct _tree *l, *r; /* left and right children */
27 /* extra stuff would go here */
30 typedef int (*cut)(tree*); /* cut x is <, =, or > 0 given a <, =, or > x for some a */
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 */
37 tree *splay(cut c, tree *t) {
52 /* top-down splaying loop */
56 break; /*** success ***/
60 break; /*** trivial ***/
64 *rl = x; /*** zig ***/
72 *rl = x; /*** zig ***/
78 x->l = y->r; /*** zig-zig ***/
88 *rl = x; /*** zig ***/
93 else { /*** zig-zag ***/
106 break; /*** trivial ***/
110 *lr = x; /*** zig ***/
118 *lr = x; /*** zig ***/
124 x->r = y->l; /*** zig-zig ***/
134 *lr = x; /*** zig ***/
139 else { /*** zig-zag ***/
159 tree *splay_min(tree *t) {
173 break; /*** trivial ***/
177 *rl = x; /*** zig ***/
183 x->l = y->r; /*** zig-zig ***/
198 tree *splay_max(tree *t) {
212 break; /*** trivial ***/
216 *lr = x; /*** zig ***/
222 x->r = y->l; /*** zig-zig ***/
237 /******** circles and fringe */
241 typedef struct _circle {
243 double x, y; /* position */
244 double dx, dy; /* velocity */
246 int visible; /* default visibility */
247 struct _fringe *lo, *hi; /* lo and hi fringes */
249 int ni; /* number of intersections */
250 int *i; /* sorted intersection list */
253 typedef struct _fringe {
254 struct _fringe *l, *r; /* left and right children for splay trees */
256 circle *c; /* associated circle */
257 int side; /* 0 for lo, 1 for hi */
259 int mni; /* size of intersection array */
260 int ni; /* number of intersections */
261 int *i; /* sorted intersection list */
264 inline double fringe_x(fringe *f, double y) {
267 d = sqrt(f->c->r * f->c->r - dy * dy);
268 return f->side ? f->c->x + d : f->c->x - d;
271 inline void fringe_add_intersection(fringe *f, double x, double y) {
273 if (f->mni < f->ni) {
275 f->i = realloc(f->i, sizeof(int) * f->mni);
277 f->i[f->ni-1] = rint(atan2(y - f->c->y, x - f->c->x) * X_PI / M_PI);
280 circle *init_circles(int n, int w, int h) {
281 int i, r0, dr, speed;
283 double minradius, maxradius;
284 fringe *s = malloc(sizeof(fringe) * n * 2); /* never freed */
285 circle *c = malloc(sizeof(circle) * n);
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;
293 r0 = ceil(minradius * h);
294 dr = floor(maxradius * h) - r0 + 1;
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;
306 v = (1 + frand(0.5)) * speed / 10.0;
307 c[i].dx = v * cos(a);
308 c[i].dy = v * sin(a);
312 c[i].lo->c = c[i].hi->c = c+i;
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;
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;
328 void move_circle(circle *c, int w, int h) {
334 else if (c->x >= w - c->r) {
343 else if (c->y >= h - c->r) {
349 /******** event queue */
355 typedef struct _event {
356 struct _event *l, *r; /* left and right children for splay tree */
358 int kind; /* type of event */
359 double x, y; /* position */
360 fringe *lo, *hi; /* fringes */
363 static double event_cut_y;
365 int event_cut(event *e) {
366 return event_cut_y == e->y ? 0 : event_cut_y < e->y ? -1 : 1;
369 void event_insert(event **eq, event *e) {
376 *eq = (event*)splay((cut)event_cut, (tree*)*eq);
378 if (e->y == (*eq)->y) {
379 if (!((e->lo == (*eq)->lo && e->hi == (*eq)->hi) || (e->lo == (*eq)->hi && e->hi == (*eq)->lo))) {
381 e->r = 0; /* doing this instead of dying might be dangerous */
385 else if (e->y < (*eq)->y) {
399 void circle_start_event(event **eq, circle *c) {
401 s = malloc(sizeof(event));
410 void circle_finish_event(event **eq, circle *c) {
412 f = malloc(sizeof(event));
421 event *event_next(event **eq) {
426 e = (event*)splay_min((tree*)*eq);
432 void event_shred(event *e) {
440 /******** fringe intersection */
442 inline int check_fringe_intersection(double ye, fringe *lo, fringe *hi, double x, double y) {
443 return ye <= y && ((x < lo->c->x) ^ lo->side) && ((x < hi->c->x) ^ hi->side);
446 void fringe_intersect(event **eq, double y, fringe *lo, fringe *hi) {
448 double dx, dy, sd, rs, rd, d, sx, sy, rp, sqd;
449 double x1, y1, x2, y2;
454 dx = hi->c->x - lo->c->x;
455 dy = hi->c->y - lo->c->y;
456 sd = dx * dx + dy * dy;
461 rs = hi->c->r + lo->c->r;
462 rd = hi->c->r - lo->c->r;
463 d = (rd * rd - sd) * (sd - rs * rs);
471 sx = (lo->c->x + hi->c->x) / 2;
472 sy = (lo->c->y + hi->c->y) / 2;
473 x1 = sx + sd * (dy * sqd - dx * rp);
474 y1 = sy - sd * (dx * sqd + dy * rp);
475 x2 = sx - sd * (dy * sqd + dx * rp);
476 y2 = sy + sd * (dx * sqd - dy * rp);
478 #define CHECK(xi, yi) (y <= yi && ((xi < lo->c->x) ^ lo->side) && ((xi < hi->c->x) ^ hi->side))
480 #define ADD_CROSS(xi, yi, ilo, ihi) { \
481 e = malloc(sizeof(event)); \
483 e->x = xi; e->y = yi; \
484 e->lo = ilo; e->hi = ihi; \
485 event_insert(eq, e); \
491 ADD_CROSS(x1, y1, lo, hi);
492 ADD_CROSS(x2, y2, hi, lo);
495 ADD_CROSS(x1, y1, hi, lo);
496 ADD_CROSS(x2, y2, lo, hi);
500 ADD_CROSS(x1, y1, lo, hi);
502 else if (CHECK(x2, y2))
503 ADD_CROSS(x2, y2, lo, hi);
508 /******** fringe trees and event handling */
510 #define PANIC ((fringe*)1) /* by alignment, no fringe should every be 1 */
512 fringe *check_lo(event **eq, double y, fringe *f, fringe *hi) {
514 f = (fringe*)splay_max((tree*)f);
515 fringe_intersect(eq, y, f, hi);
520 fringe *check_hi(event **eq, double y, fringe *lo, fringe *f) {
522 f = (fringe*)splay_min((tree*)f);
523 fringe_intersect(eq, y, lo, f);
528 double fringe_start_cut_x;
529 double fringe_start_cut_y;
531 int fringe_start_cut(fringe *f) {
532 double x = fringe_x(f, fringe_start_cut_y);
533 return fringe_start_cut_x == x ? 0 : fringe_start_cut_x < x ? -1 : 1;
536 fringe *fringe_start(event **eq, fringe *f, double x, double y, fringe *lo, fringe *hi) {
540 circle_finish_event(eq, lo->c);
547 fringe_start_cut_x = x;
548 fringe_start_cut_y = y;
549 f = (fringe*)splay((cut)fringe_start_cut, (tree*)f);
552 if (x == sx) { /* time to cheat my way out of handling degeneracies */
554 circle_start_event(eq, lo->c);
558 circle_finish_event(eq, lo->c);
559 f->l = check_lo(eq, y, f->l, lo);
560 fringe_intersect(eq, y, hi, f);
568 circle_finish_event(eq, lo->c);
569 fringe_intersect(eq, y, f, lo);
570 f->r = check_hi(eq, y, hi, f->r);
579 double fringe_double_cut_x;
580 double fringe_double_cut_y;
581 fringe *fringe_double_cut_lo;
582 fringe *fringe_double_cut_hi;
584 int fringe_double_cut(fringe *f) {
586 if (f == fringe_double_cut_lo || f == fringe_double_cut_hi)
588 x = fringe_x(f, fringe_double_cut_y);
589 return fringe_double_cut_x == x ? 0 : fringe_double_cut_x < x ? -1 : 1;
592 int fringe_double_splay(fringe *f, double x, double y, fringe *lo, fringe *hi) {
593 fringe_double_cut_x = x;
594 fringe_double_cut_y = y;
595 fringe_double_cut_lo = lo;
596 fringe_double_cut_hi = hi;
597 f = (fringe*)splay((cut)fringe_double_cut, (tree*)f);
600 return (f->r = (fringe*)splay_min((tree*)f->r)) == hi;
602 return (f->l = (fringe*)splay_max((tree*)f->l)) == lo;
607 fringe *fringe_cross(event **eq, fringe *f, double x, double y, fringe *lo, fringe *hi) {
609 if (!fringe_double_splay(f, x, y, lo, hi))
611 l = check_lo(eq, y, lo->l, hi);
612 r = check_hi(eq, y, lo, hi->r);
620 fringe *fringe_finish(event **eq, fringe *f, double x, double y, fringe *lo, fringe *hi) {
621 if (!fringe_double_splay(f, x, y, lo, hi))
628 lo->l = (fringe*)splay_max((tree*)lo->l);
629 hi->r = (fringe*)splay_min((tree*)hi->r);
630 fringe_intersect(eq, y, lo->l, hi->r);
637 /******** plane sweep */
639 void sweep(int n, circle *c) {
645 #define CHECK_PANIC() \
649 for (i=0;i<n;i++) { \
651 c[i].lo->ni = c[i].hi->ni = 0; \
658 circle_start_event(&eq, c+i);
661 while ((e = event_next(&eq))) {
664 f = fringe_start(&eq, f, e->x, e->y, e->lo, e->hi);
667 f = fringe_cross(&eq, f, e->x, e->y, e->lo, e->hi);
669 fringe_add_intersection(e->lo, e->x, e->y);
670 fringe_add_intersection(e->hi, e->x, e->y);
673 f = fringe_finish(&eq, f, e->x, e->y, e->lo, e->hi);
681 /******** circle drawing */
683 void adjust_circle_visibility(circle *c) {
686 n = c->lo->ni + c->hi->ni;
687 in = malloc(sizeof(int) * n);
688 for (i=0;i<c->hi->ni;i++)
690 for (i=c->lo->ni-1;i>=0;i--)
691 in[n-i-1] = c->lo->i[i] > 0 ? c->lo->i[i] : c->lo->i[i] + 2 * X_PI;
692 c->lo->ni = c->hi->ni = 0;
696 while (i < n && j < c->ni) /* whee */
697 a = (in[i] < c->i[j] ? in[i++] : c->i[j++]) - a;
704 c->visible = !c->visible;
710 #define ARC_BUFFER_SIZE 256
711 int arc_buffer_count = 0;
712 XArc arc_buffer[ARC_BUFFER_SIZE];
714 void flush_arc_buffer(Display *dpy, Drawable w, GC gc) {
715 if (arc_buffer_count) {
716 XDrawArcs(dpy, w, gc, arc_buffer, arc_buffer_count);
717 arc_buffer_count = 0;
721 void draw_circle(Display *dpy, Drawable w, GC gc, circle *c) {
723 adjust_circle_visibility(c);
725 xi = rint(c->x - c->r);
726 yi = rint(c->y - c->r);
729 #define ARC(p, a1, a2) { \
730 if (((p) & 1) ^ c->visible) { \
731 arc_buffer[arc_buffer_count].x = xi; \
732 arc_buffer[arc_buffer_count].y = yi; \
733 arc_buffer[arc_buffer_count].width = di; \
734 arc_buffer[arc_buffer_count].height = di; \
735 arc_buffer[arc_buffer_count].angle1 = -(a1); \
736 arc_buffer[arc_buffer_count].angle2 = (a1) - (a2); \
737 arc_buffer_count++; \
738 if (arc_buffer_count == ARC_BUFFER_SIZE) \
739 flush_arc_buffer(dpy, w, gc); \
746 ARC(0, c->i[c->ni-1], c->i[0] + 2 * X_PI)
747 for (i=1;i<c->ni;i++)
748 ARC(i, c->i[i-1], c->i[i])
751 /******** toplevel */
753 char *progclass = "Piecewise";
755 char *defaults [] = {
756 ".background: black",
757 ".foreground: white",
767 "*doubleBuffer: True",
768 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
770 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
774 XrmOptionDescRec options [] = {
775 { "-delay", ".delay", XrmoptionSepArg, 0 },
776 { "-ncolors", ".ncolors", XrmoptionSepArg, 0 },
777 { "-speed", ".speed", XrmoptionSepArg, 0 },
778 { "-colorspeed", ".colorspeed", XrmoptionSepArg, 0 },
780 { "-count", ".count", XrmoptionSepArg, 0 },
781 { "-minradius", ".minradius", XrmoptionSepArg, 0 },
782 { "-maxradius", ".maxradius", XrmoptionSepArg, 0 },
784 { "-db", ".doubleBuffer", XrmoptionNoArg, "True" },
785 { "-no-db", ".doubleBuffer", XrmoptionNoArg, "False" },
789 void screenhack(Display *dpy, Window window) {
794 GC erase_gc, draw_gc;
795 XWindowAttributes xgwa;
796 Pixmap b = 0, ba = 0, bb = 0; /* double-buffering pixmap */
798 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
799 XdbeBackBuffer backb = 0;
800 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
802 int count, delay, ncolors, colorspeed, color_index, flags, iterations;
803 int color_iterations;
806 count = get_integer_resource("count", "Integer");
807 delay = get_integer_resource("delay", "Integer");
808 ncolors = get_integer_resource("ncolors", "Integer");
809 colorspeed = get_integer_resource("colorspeed", "Integer");
810 dbuf = get_boolean_resource("doubleBuffer", "Boolean");
812 color_iterations = colorspeed ? 100 / colorspeed : 100000;
813 if (!color_iterations)
814 color_iterations = 1;
816 XGetWindowAttributes(dpy, window, &xgwa);
817 colors = calloc(sizeof(XColor), ncolors);
819 if (get_boolean_resource("mono", "Boolean")) {
822 colors[0].pixel = get_pixel_resource("foreground", "Foreground", dpy, xgwa.colormap);
825 make_color_loop(dpy, xgwa.colormap, 0, 1, 1, 120, 1, 1, 240, 1, 1, colors, &ncolors, True, False);
831 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
832 b = backb = xdbe_get_backbuffer(dpy, window, XdbeUndefined);
833 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
836 ba = XCreatePixmap(dpy, window, xgwa.width, xgwa.height,xgwa.depth);
837 bb = XCreatePixmap(dpy, window, xgwa.width, xgwa.height,xgwa.depth);
845 gcv.foreground = get_pixel_resource("background", "Background", dpy, xgwa.colormap);
846 erase_gc = XCreateGC (dpy, b, GCForeground, &gcv);
849 flags = GCForeground;
850 color_index = random() % ncolors;
851 gcv.foreground = colors[color_index].pixel;
852 draw_gc = XCreateGC(dpy, b, flags, &gcv);
854 /* initialize circles */
855 circles = init_circles(count, xgwa.width, xgwa.height);
859 XFillRectangle (dpy, b, erase_gc, 0, 0, xgwa.width, xgwa.height);
861 sweep(count, circles);
862 for (i=0;i<count;i++) {
863 draw_circle(dpy, b, draw_gc, circles+i);
864 move_circle(circles+i, xgwa.width, xgwa.height);
866 flush_arc_buffer(dpy, b, draw_gc);
868 if (++iterations % color_iterations == 0) {
869 color_index = (color_index + 1) % ncolors;
870 XSetForeground(dpy, draw_gc, colors[color_index].pixel);
873 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
875 XdbeSwapInfo info[1];
876 info[0].swap_window = window;
877 info[0].swap_action = XdbeUndefined;
878 XdbeSwapBuffers (dpy, info, 1);
881 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
883 XCopyArea (dpy, b, window, erase_gc, 0, 0, xgwa.width, xgwa.height, 0, 0);
884 b = (b == ba ? bb : ba);
888 screenhack_handle_events(dpy);