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 #if !defined( __GNUC__ ) && !defined(__cplusplus) && !defined(c_plusplus)
26 #define X_PI (180 * 64)
32 #define ARC_BUFFER_SIZE 256
35 typedef struct _tree {
36 struct _tree *l, *r; /* left and right children */
37 /* extra stuff would go here */
43 typedef struct _circle {
45 double x, y; /* position */
46 double dx, dy; /* velocity */
48 int visible; /* default visibility */
49 struct _fringe *lo, *hi; /* lo and hi fringes */
51 int ni; /* number of intersections */
52 int *i; /* sorted intersection list */
55 typedef struct _fringe {
56 struct _fringe *l, *r; /* left and right children for splay trees */
58 circle *c; /* associated circle */
59 int side; /* 0 for lo, 1 for hi */
61 int mni; /* size of intersection array */
62 int ni; /* number of intersections */
63 int *i; /* sorted intersection list */
67 typedef struct _event {
68 struct _event *l, *r; /* left and right children for splay tree */
70 int kind; /* type of event */
71 double x, y; /* position */
72 fringe *lo, *hi; /* fringes */
82 double fringe_start_cut_x;
83 double fringe_start_cut_y;
85 double fringe_double_cut_x;
86 double fringe_double_cut_y;
87 fringe *fringe_double_cut_lo;
88 fringe *fringe_double_cut_hi;
91 XArc arc_buffer[ARC_BUFFER_SIZE];
97 XWindowAttributes xgwa;
98 Pixmap b, ba, bb; /* double-buffering pixmap */
100 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
101 XdbeBackBuffer backb;
102 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
104 int count, delay, ncolors, colorspeed, color_index, flags, iterations;
105 int color_iterations;
109 typedef int (*cut)(struct state *, tree*); /* cut x is <, =, or > 0 given a <, =, or > x for some a */
113 /******** splaying code */
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 */
120 static tree *splay(struct state *st, cut c, tree *t)
136 /* top-down splaying loop */
140 break; /*** success ***/
144 break; /*** trivial ***/
148 *rl = x; /*** zig ***/
156 *rl = x; /*** zig ***/
162 x->l = y->r; /*** zig-zig ***/
172 *rl = x; /*** zig ***/
177 else { /*** zig-zag ***/
190 break; /*** trivial ***/
194 *lr = x; /*** zig ***/
202 *lr = x; /*** zig ***/
208 x->r = y->l; /*** zig-zig ***/
218 *lr = x; /*** zig ***/
223 else { /*** zig-zag ***/
243 static tree *splay_min(tree *t)
258 break; /*** trivial ***/
262 *rl = x; /*** zig ***/
268 x->l = y->r; /*** zig-zig ***/
283 static tree *splay_max(tree *t)
298 break; /*** trivial ***/
302 *lr = x; /*** zig ***/
308 x->r = y->l; /*** zig-zig ***/
323 /******** circles and fringe */
325 static inline double fringe_x(fringe *f, double y)
329 d = sqrt(f->c->r * f->c->r - dy * dy);
330 return f->side ? f->c->x + d : f->c->x - d;
333 static inline void fringe_add_intersection(fringe *f, double x, double y)
336 if (f->mni < f->ni) {
338 f->i = realloc(f->i, sizeof(int) * f->mni);
340 f->i[f->ni-1] = rint(atan2(y - f->c->y, x - f->c->x) * X_PI / M_PI);
343 static circle *init_circles(struct state *st, int n, int w, int h)
345 int i, r0, dr, speed;
347 double minradius, maxradius;
348 fringe *s = malloc(sizeof(fringe) * n * 2); /* never freed */
349 circle *c = malloc(sizeof(circle) * n);
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;
357 r0 = ceil(minradius * h);
358 dr = floor(maxradius * h) - r0 + 1;
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;
370 v = (1 + frand(0.5)) * speed / 10.0;
371 c[i].dx = v * cos(a);
372 c[i].dy = v * sin(a);
376 c[i].lo->c = c[i].hi->c = c+i;
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;
386 /* this is a hack, but I guess that's what I writing anyways */
387 static void tweak_circle(circle *c)
389 c->x += frand(2) - 1;
390 c->y += frand(1) + 0.1;
393 static void move_circle(circle *c, int w, int h)
400 else if (c->x >= w - c->r) {
409 else if (c->y >= h - c->r) {
415 /******** event queue */
417 static int event_cut(struct state *st, event *e)
419 return st->event_cut_y == e->y ? 0 : st->event_cut_y < e->y ? -1 : 1;
422 static void event_insert(struct state *st, event **eq, event *e)
427 return; /* avoid leak */
430 st->event_cut_y = e->y;
431 *eq = (event*)splay(st, (cut)event_cut, (tree*)*eq);
433 if (e->y == (*eq)->y) {
434 if (!((e->lo == (*eq)->lo && e->hi == (*eq)->hi) || (e->lo == (*eq)->hi && e->hi == (*eq)->lo))) {
436 e->r = 0; /* doing this instead of dying might be dangerous */
440 free(e); /* don't leak! */
442 else if (e->y < (*eq)->y) {
456 static void circle_start_event(struct state *st, event **eq, circle *c)
459 s = malloc(sizeof(event));
465 event_insert(st, eq, s);
468 static void circle_finish_event(struct state *st, event **eq, circle *c)
471 f = malloc(sizeof(event));
477 event_insert(st, eq, f);
480 static event *event_next(event **eq)
486 e = (event*)splay_min((tree*)*eq);
492 static void event_shred(event *e)
501 /******** fringe intersection */
504 static inline int check_fringe_intersection(double ye, fringe *lo, fringe *hi, double x, double y)
506 return ye <= y && ((x < lo->c->x) ^ lo->side) && ((x < hi->c->x) ^ hi->side);
510 static void fringe_intersect(struct state *st, event **eq, double y, fringe *lo, fringe *hi)
513 double dx, dy, sd, rs, rd, d, sx, sy, rp, sqd;
514 double x1, y1, x2, y2;
519 dx = hi->c->x - lo->c->x;
520 dy = hi->c->y - lo->c->y;
521 sd = dx * dx + dy * dy;
526 rs = hi->c->r + lo->c->r;
527 rd = hi->c->r - lo->c->r;
528 d = (rd * rd - sd) * (sd - rs * rs);
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);
543 #define CHECK(xi, yi) (y <= yi && ((xi < lo->c->x) ^ lo->side) && ((xi < hi->c->x) ^ hi->side))
545 #define ADD_CROSS(xi, yi, ilo, ihi) { \
546 e = malloc(sizeof(event)); /* #### LEAK */ \
548 e->x = xi; e->y = yi; \
549 e->lo = ilo; e->hi = ihi; \
550 event_insert(st, eq, e); \
556 ADD_CROSS(x1, y1, lo, hi);
557 ADD_CROSS(x2, y2, hi, lo);
560 ADD_CROSS(x1, y1, hi, lo);
561 ADD_CROSS(x2, y2, lo, hi);
565 ADD_CROSS(x1, y1, lo, hi);
567 else if (CHECK(x2, y2))
568 ADD_CROSS(x2, y2, lo, hi);
573 /******** fringe trees and event handling */
575 #define PANIC ((fringe*)1) /* by alignment, no fringe should every be 1 */
577 static fringe *check_lo(struct state *st, event **eq, double y, fringe *f, fringe *hi)
580 f = (fringe*)splay_max((tree*)f);
581 fringe_intersect(st, eq, y, f, hi);
586 static fringe *check_hi(struct state *st, event **eq, double y, fringe *lo, fringe *f)
589 f = (fringe*)splay_min((tree*)f);
590 fringe_intersect(st, eq, y, lo, f);
595 static int fringe_start_cut(struct state *st, fringe *f)
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;
601 static fringe *fringe_start(struct state *st, event **eq, fringe *f, double x, double y, fringe *lo, fringe *hi)
606 circle_finish_event(st, eq, lo->c);
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);
618 if (x == sx) { /* time to cheat my way out of handling degeneracies */
620 circle_start_event(st, eq, lo->c);
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);
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);
645 static int fringe_double_cut(struct state *st, fringe *f)
648 if (f == st->fringe_double_cut_lo || f == st->fringe_double_cut_hi)
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;
654 static int fringe_double_splay(struct state *st, fringe *f, double x, double y, fringe *lo, fringe *hi)
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);
663 return (f->r = (fringe*)splay_min((tree*)f->r)) == hi;
665 return (f->l = (fringe*)splay_max((tree*)f->l)) == lo;
670 static fringe *fringe_cross(struct state *st, event **eq, fringe *f, double x, double y, fringe *lo, fringe *hi)
673 if (!fringe_double_splay(st, f, x, y, lo, hi))
675 l = check_lo(st, eq, y, lo->l, hi);
676 r = check_hi(st, eq, y, lo, hi->r);
684 static fringe *fringe_finish(struct state *st, event **eq, fringe *f, double x, double y, fringe *lo, fringe *hi)
686 if (!fringe_double_splay(st, f, x, y, lo, hi))
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);
702 /******** plane sweep */
704 static void sweep(struct state *st, int n, circle *c)
711 #define CHECK_PANIC() \
715 for (i=0;i<n;i++) { \
717 c[i].lo->ni = c[i].hi->ni = 0; \
724 circle_start_event(st, &eq, c+i);
727 while ((e = event_next(&eq))) {
730 f = fringe_start(st, &eq, f, e->x, e->y, e->lo, e->hi);
733 f = fringe_cross(st, &eq, f, e->x, e->y, e->lo, e->hi);
735 fringe_add_intersection(e->lo, e->x, e->y);
736 fringe_add_intersection(e->hi, e->x, e->y);
739 f = fringe_finish(st, &eq, f, e->x, e->y, e->lo, e->hi);
747 /******** circle drawing */
749 static void adjust_circle_visibility(circle *c)
753 n = c->lo->ni + c->hi->ni;
754 in = malloc(sizeof(int) * n);
755 for (i=0;i<c->hi->ni;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;
763 while (i < n && j < c->ni) /* whee */
764 a = (in[i] < c->i[j] ? in[i++] : c->i[j++]) - a;
771 c->visible = !c->visible;
777 static void flush_arc_buffer(struct state *st, Drawable w, GC gc)
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;
785 static void draw_circle(struct state *st, Drawable w, GC gc, circle *c)
788 adjust_circle_visibility(c);
790 xi = rint(c->x - c->r);
791 yi = rint(c->y - c->r);
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); \
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])
816 /******** toplevel */
820 check_for_leaks (void)
823 static unsigned long early_brk = 0;
824 unsigned long max = 30 * 1024 * 1024; /* 30 MB */
825 int b = (unsigned long) sbrk(0);
828 else if (b > early_brk + max)
830 fprintf (stderr, "%s: leaked %lu MB -- aborting!\n",
831 progname, ((b - early_brk) >> 20));
834 #endif /* HAVE_SBRK */
839 piecewise_init (Display *dd, Window ww)
841 struct state *st = (struct state *) calloc (1, sizeof(*st));
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");
851 # ifdef HAVE_JWXYZ /* Don't second-guess Quartz's double-buffering */
855 st->color_iterations = st->colorspeed ? 100 / st->colorspeed : 100000;
856 if (!st->color_iterations)
857 st->color_iterations = 1;
859 XGetWindowAttributes(st->dpy, st->window, &st->xgwa);
860 st->colors = calloc(sizeof(XColor), st->ncolors);
862 if (get_boolean_resource(st->dpy, "mono", "Boolean")) {
865 st->colors[0].pixel = get_pixel_resource(st->dpy, st->xgwa.colormap, "foreground", "Foreground");
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);
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 */
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);
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);
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);
899 /* initialize circles */
900 st->circles = init_circles(st, st->count, st->xgwa.width, st->xgwa.height);
908 piecewise_draw (Display *dpy, Window window, void *closure)
910 struct state *st = (struct state *) closure;
913 XFillRectangle (st->dpy, st->b, st->erase_gc, 0, 0, st->xgwa.width, st->xgwa.height);
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);
920 flush_arc_buffer(st, st->b, st->draw_gc);
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);
927 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
929 XdbeSwapInfo info[1];
930 info[0].swap_window = st->window;
931 info[0].swap_action = XdbeUndefined;
932 XdbeSwapBuffers (st->dpy, info, 1);
935 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
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);
941 /* check_for_leaks(); */
946 piecewise_reshape (Display *dpy, Window window, void *closure,
947 unsigned int w, unsigned int h)
949 struct state *st = (struct state *) closure;
950 XGetWindowAttributes(st->dpy, st->window, &st->xgwa);
954 piecewise_event (Display *dpy, Window window, void *closure, XEvent *event)
960 piecewise_free (Display *dpy, Window window, void *closure)
962 struct state *st = (struct state *) closure;
968 static const char *piecewise_defaults [] = {
969 ".background: black",
970 ".foreground: white",
980 "*doubleBuffer: True",
981 #ifdef HAVE_DOUBLE_BUFFER_EXTENSION
983 #endif /* HAVE_DOUBLE_BUFFER_EXTENSION */
985 "*ignoreRotation: True",
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 },
996 { "-count", ".count", XrmoptionSepArg, 0 },
997 { "-minradius", ".minradius", XrmoptionSepArg, 0 },
998 { "-maxradius", ".maxradius", XrmoptionSepArg, 0 },
1000 { "-db", ".doubleBuffer", XrmoptionNoArg, "True" },
1001 { "-no-db", ".doubleBuffer", XrmoptionNoArg, "False" },
1006 XSCREENSAVER_MODULE ("Piecewise", piecewise)