1 /* tessellimage, Copyright (c) 2014 Jamie Zawinski <jwz@jwz.org>
3 * Permission to use, copy, modify, distribute, and sell this software and its
4 * documentation for any purpose is hereby granted without fee, provided that
5 * the above copyright notice appear in all copies and that both that
6 * copyright notice and this permission notice appear in supporting
7 * documentation. No representations are made about the suitability of this
8 * software for any purpose. It is provided "as is" without express or
12 #include "screenhack.h"
19 # define XK_MISCELLANY
20 # include <X11/keysymdef.h>
24 #define countof(x) (sizeof((x))/sizeof((*x)))
29 XWindowAttributes xgwa;
32 Bool outline_p, cache_p, fill_p;
33 double duration, duration2;
35 double start_time, start_time2;
38 Pixmap image, output, deltap;
39 int nthreshes, threshes[256], vsizes[256];
43 async_load_state *img_loader;
49 /* Returns the current time in seconds as a double.
55 # ifdef GETTIMEOFDAY_TWO_ARGS
57 gettimeofday(&now, &tzp);
62 return (now.tv_sec + ((double) now.tv_usec * 0.000001));
67 tessellimage_init (Display *dpy, Window window)
69 struct state *st = (struct state *) calloc (1, sizeof(*st));
74 XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
76 st->delay = get_integer_resource (st->dpy, "delay", "Integer");
77 if (st->delay < 1) st->delay = 1;
79 st->outline_p = get_boolean_resource (st->dpy, "outline", "Boolean");
80 st->cache_p = get_boolean_resource (st->dpy, "cache", "Boolean");
81 st->fill_p = get_boolean_resource (st->dpy, "fillScreen", "Boolean");
83 st->max_depth = get_integer_resource (st->dpy, "maxDepth", "MaxDepth");
84 if (st->max_depth < 100) st->max_depth = 100;
86 st->duration = get_float_resource (st->dpy, "duration", "Seconds");
87 if (st->duration < 1) st->duration = 1;
89 st->duration2 = get_float_resource (st->dpy, "duration2", "Seconds");
90 if (st->duration2 < 0.001) st->duration = 0.001;
92 XClearWindow(st->dpy, st->window);
98 /* Given a bitmask, returns the position and width of the field.
101 decode_mask (unsigned int mask, unsigned int *pos_ret, unsigned int *size_ret)
104 for (i = 0; i < 32; i++)
105 if (mask & (1L << i))
109 for (; i < 32; i++, j++)
110 if (! (mask & (1L << i)))
119 pixel_distance (Screen *s, Visual *v, unsigned long p1, unsigned long p2)
121 static int initted_p = 0;
122 static unsigned long rmsk=0, gmsk=0, bmsk=0;
123 static unsigned int rpos=0, gpos=0, bpos=0;
124 static unsigned int rsiz=0, gsiz=0, bsiz=0;
126 unsigned char r1, g1, b1;
127 unsigned char r2, g2, b2;
130 if (!p1 && !p2) return 0;
133 visual_rgb_masks (s, v, &rmsk, &gmsk, &bmsk);
134 decode_mask (rmsk, &rpos, &rsiz);
135 decode_mask (gmsk, &gpos, &gsiz);
136 decode_mask (bmsk, &bpos, &bsiz);
140 r1 = (p1 & rmsk) >> rpos;
141 g1 = (p1 & gmsk) >> gpos;
142 b1 = (p1 & bmsk) >> bpos;
144 r2 = (p2 & rmsk) >> rpos;
145 g2 = (p2 & gmsk) >> gpos;
146 b2 = (p2 & bmsk) >> bpos;
149 /* Compute the distance in linear RGB space.
151 distance = cbrt (((r2 - r1) * (r2 - r1)) +
152 ((g2 - g1) * (g2 - g1)) +
153 ((b2 - b1) * (b2 - b1)));
156 /* Compute the distance in luminance-weighted RGB space.
159 int rd = (r2 - r1) * 0.2989 * (1 / 0.5870);
160 int gd = (g2 - g1) * 0.5870 * (1 / 0.5870);
161 int bd = (b2 - b1) * 0.1140 * (1 / 0.5870);
162 distance = cbrt ((rd * rd) + (gd * gd) + (bd * bd));
165 /* Compute the distance in brightness-weighted HSV space.
166 (Slower, and doesn't seem to look better than luminance RGB.)
172 double hd, sd, vd, dd;
173 rgb_to_hsv (r1, g1, b1, &h1, &s1, &v1);
174 rgb_to_hsv (r2, g2, b2, &h2, &s2, &v2);
177 if (hd >= 180) hd -= 180;
182 /* [hsv]d are now the distance as 0.0 - 1.0. */
183 /* Compute the overall distance, giving more weight to V. */
184 dd = (hd * 0.25 + sd * 0.25 + vd * 0.5);
186 if (dd < 0 || dd > 1.0) abort();
191 if (distance < 0) distance = -distance;
197 flush_cache (struct state *st)
200 for (i = 0; i < countof(st->cache); i++)
203 XFreePixmap (st->dpy, st->cache[i]);
208 XFreePixmap (st->dpy, st->deltap);
214 /* Scale up the bits in st->img so that it fills the screen, centered.
217 scale_image (struct state *st)
219 double scale, s1, s2;
223 if (st->geom.width <= 0 || st->geom.height <= 0)
226 s1 = st->geom.width / (double) st->img->width;
227 s2 = st->geom.height / (double) st->img->height;
228 scale = (s1 < s2 ? s1 : s2);
230 img2 = XCreateImage (st->dpy, st->xgwa.visual, st->img->depth,
232 st->img->width, st->img->height, 8, 0);
234 img2->data = (char *) calloc (img2->height, img2->bytes_per_line);
235 if (! img2->data) abort();
237 cx = st->img->width / 2;
238 cy = st->img->height / 2;
240 if (st->geom.width < st->geom.height) /* portrait: aim toward the top */
241 cy = st->img->height / (2 / scale);
243 for (y = 0; y < img2->height; y++)
244 for (x = 0; x < img2->width; x++)
246 int x2 = cx + ((x - cx) * scale);
247 int y2 = cy + ((y - cy) * scale);
249 if (x2 >= 0 && y2 >= 0 &&
250 x2 < st->img->width && y2 < st->img->height)
251 p = XGetPixel (st->img, x2, y2);
252 XPutPixel (img2, x, y, p);
254 free (st->img->data);
256 XDestroyImage (st->img);
261 st->geom.width = st->img->width;
262 st->geom.height = st->img->height;
268 analyze (struct state *st)
272 unsigned int w, h, bw, d;
273 unsigned long histo[256];
277 /* Convert the loaded pixmap to an XImage.
279 XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
280 XGetGeometry (st->dpy, st->image, &root, &x, &y, &w, &h, &bw, &d);
284 free (st->img->data);
286 XDestroyImage (st->img);
288 st->img = XGetImage (st->dpy, st->image, 0, 0, w, h, ~0L, ZPixmap);
290 if (st->fill_p) scale_image (st);
292 /* Create the delta map: color space distance between each pixel.
293 Maybe doing running a Sobel Filter matrix on this would be a
294 better idea. That might be a bit faster, but I think it would
295 make no visual difference.
299 free (st->delta->data);
301 XDestroyImage (st->delta);
303 st->delta = XCreateImage (st->dpy, st->xgwa.visual, d, ZPixmap, 0, NULL,
305 st->delta->data = (char *)
306 calloc (st->delta->height, st->delta->bytes_per_line);
308 for (y = 0; y < st->delta->height; y++)
310 for (x = 0; x < st->delta->width; x++)
312 unsigned long pixels[5];
315 pixels[i++] = XGetPixel (st->img, x, y);
316 pixels[i++] = (x > 0 && y > 0 ? XGetPixel (st->img, x-1, y-1) : 0);
317 pixels[i++] = ( y > 0 ? XGetPixel (st->img, x, y-1) : 0);
318 pixels[i++] = (x > 0 ? XGetPixel (st->img, x-1, y) : 0);
319 pixels[i++] = (x > 0 && y < h-1 ? XGetPixel (st->img, x-1, y+1) : 0);
321 for (i = 1; i < countof(pixels); i++)
322 distance += pixel_distance (st->xgwa.screen, st->xgwa.visual,
323 pixels[0], pixels[i]);
324 distance /= countof(pixels)-1;
325 XPutPixel (st->delta, x, y, distance);
329 /* Collect a histogram of every distance value.
331 memset (histo, 0, sizeof(histo));
332 for (y = 0; y < st->delta->height; y++)
333 for (x = 0; x < st->delta->width; x++)
335 unsigned long p = XGetPixel (st->delta, x, y);
336 if (p > sizeof(histo)) abort();
340 /* Convert that from "occurrences of N" to ">= N".
342 for (i = countof(histo) - 1; i > 0; i--)
343 histo[i-1] += histo[i];
346 fprintf (stderr, "%s: histo: ", progname);
347 for (i = 0; i < countof(histo); i++)
348 fprintf(stderr, "%d:%lu ", i, histo[i]);
349 fprintf(stderr, "\n");
352 /* Collect a useful set of threshold values, ignoring thresholds that
353 result in a very similar number of control points (since those images
354 probably won't look very different).
358 int max_vsize = st->max_depth;
362 if (min_vsize > max_vsize/100)
363 min_vsize = max_vsize/100;
365 if (min_delta > max_vsize/1000)
366 min_delta = max_vsize/1000;
369 for (i = countof(histo)-1; i >= 0; i--)
371 unsigned long vsize = histo[i];
373 /* If this is a different vsize, push it. */
374 if (vsize >= min_vsize &&
375 vsize <= max_vsize &&
376 (st->nthreshes == 0 ||
377 vsize >= st->vsizes[st->nthreshes-1] + min_delta))
379 st->threshes[st->nthreshes] = i;
380 st->vsizes[st->nthreshes] = vsize;
386 st->thresh = 0; /* startup */
387 st->dthresh = 1; /* forward */
391 XFreePixmap (st->dpy, st->output);
397 fprintf (stderr, "%s: threshes:", progname);
398 for (i = 0; i < st->nthreshes; i++)
399 fprintf (stderr, " %d=%d", st->threshes[i], st->vsizes[i]);
400 fprintf (stderr, "\n");
406 /* True if the distance between any two corners is too small for it to
407 make sense to draw an outline around this triangle.
410 small_triangle_p (const XPoint *p)
413 if (abs (p[0].x - p[1].x) < min) return True;
414 if (abs (p[0].y - p[1].y) < min) return True;
415 if (abs (p[1].x - p[2].x) < min) return True;
416 if (abs (p[1].y - p[2].y) < min) return True;
417 if (abs (p[2].x - p[0].x) < min) return True;
418 if (abs (p[2].y - p[0].y) < min) return True;
421 #endif /* DO_VORONOI */
430 static voronoi_polygon *
431 delaunay_to_voronoi (int np, XYZ *p, int nv, ITRIANGLE *v)
439 struct tri_list *vert_to_tri = (struct tri_list *)
440 calloc (np + 1, sizeof(*vert_to_tri));
441 voronoi_polygon *out = (voronoi_polygon *) calloc (np + 1, sizeof(*out));
444 for (i = 0; i < np; i++)
445 printf("# p %d = %d %d\n", i, (int)p[i].x, (int)p[i].y);
447 for (i = 0; i < nv; i++)
448 printf("@ t %d = %d %d %d\n", i, (int)v[i].p1, (int)v[i].p2, (int)v[i].p3);
452 /* Iterate the triangles to construct a map of vertices to the
453 triangles that contain them.
455 for (i = 0; i < nv; i++)
457 for (j = 0; j < 3; j++) /* iterate points in each triangle */
459 int p = *((&v[i].p1) + j);
460 struct tri_list *t = &vert_to_tri[p];
461 if (p < 0 || p >= np) abort();
462 if (t->size <= t->count + 1)
466 t->tri = realloc (t->tri, t->size * sizeof(*t->tri));
467 if (! t->tri) abort();
469 t->tri[t->count++] = i;
474 for (i = 0; i < nv; i++)
476 struct tri_list *t = &vert_to_tri[i];
477 printf("p %d [%d %d]:", i, (int)p[i].x, (int)p[i].y);
478 for (j = 0; j < t->count; j++) {
480 printf(" t %d [%d(%d %d) %d(%d %d) %d(%d %d)]",
483 (int)p[v[tt].p1].x, (int)p[v[tt].p1].y,
485 (int)p[v[tt].p2].x, (int)p[v[tt].p2].y,
487 (int)p[v[tt].p3].x, (int)p[v[tt].p3].y
489 if (tt < 0 || tt >= nv) abort();
495 /* For every vertex, compose a polygon whose corners are the centers
496 of each triangle using that vertex. Skip any with less than 3 points.
498 for (i = 0; i < np; i++)
500 struct tri_list *t = &vert_to_tri[i];
505 ? (XPoint *) calloc (out[i].npoints + 1, sizeof (*out[i].p))
508 for (j = 0; j < out[i].npoints; j++)
510 ITRIANGLE *tt = &v[t->tri[j]];
511 out[i].p[j].x = (p[tt->p1].x + p[tt->p2].x + p[tt->p3].x) / 3;
512 out[i].p[j].y = (p[tt->p1].y + p[tt->p2].y + p[tt->p3].y) / 3;
513 //printf(" [%d: %d %d]", j, out[i].p[j].x, out[i].p[j].y);
522 #endif /* DO_VORONOI */
528 tessellate (struct state *st)
530 Bool ticked_p = False;
532 if (! st->image) return;
537 gcv.function = GXcopy;
538 gcv.subwindow_mode = IncludeInferiors;
539 st->wgc = XCreateGC(st->dpy, st->window, GCFunction, &gcv);
540 st->pgc = XCreateGC(st->dpy, st->image, GCFunction, &gcv);
543 if (! st->nthreshes) return;
546 /* If duration2 has expired, switch to the next threshold. */
548 if (! st->button_down_p)
550 double t2 = double_time();
551 if (st->start_time2 + st->duration2 < t2)
553 st->start_time2 = t2;
554 st->thresh += st->dthresh;
556 if (st->thresh >= st->nthreshes)
558 st->thresh = st->nthreshes - 1;
561 else if (st->thresh < 0)
572 /* If we've picked a new threshold, regenerate the output image. */
574 if (ticked_p && st->cache[st->thresh])
578 st->cache[st->thresh],
580 0, 0, st->delta->width, st->delta->height,
585 int threshold = st->threshes[st->thresh];
586 int vsize = st->vsizes[st->thresh];
594 fprintf(stderr, "%s: thresh %d/%d = %d=%d\n",
595 progname, st->thresh, st->nthreshes, threshold, vsize);
598 /* Create a control point at every pixel where the delta is above
599 the current threshold. Triangulate from those. */
601 vsize += 8; /* corners of screen + corners of image */
603 p = (XYZ *) calloc (vsize+4, sizeof(*p));
604 v = (ITRIANGLE *) calloc (3*(vsize+4), sizeof(*v));
607 fprintf (stderr, "%s: out of memory (%d)\n", progname, vsize);
611 /* Add control points for the corners of the screen, and for the
612 corners of the image.
614 if (st->geom.width <= 0) st->geom.width = st->delta->width;
615 if (st->geom.height <= 0) st->geom.height = st->delta->height;
617 for (y = 0; y <= 1; y++)
618 for (x = 0; x <= 1; x++)
620 p[nv].x = x ? st->delta->width-1 : 0;
621 p[nv].y = y ? st->delta->height-1 : 0;
622 p[nv].z = XGetPixel (st->delta, (int) p[nv].x, (int) p[nv].y);
624 p[nv].x = st->geom.x + (x ? st->geom.width-1 : 0);
625 p[nv].y = st->geom.y + (y ? st->geom.height-1 : 0);
626 p[nv].z = XGetPixel (st->delta, (int) p[nv].x, (int) p[nv].y);
630 /* Add control points for every pixel that exceeds the threshold.
632 for (y = 0; y < st->delta->height; y++)
633 for (x = 0; x < st->delta->width; x++)
635 unsigned long px = XGetPixel (st->delta, x, y);
638 if (nv >= vsize) abort();
646 if (nv != vsize) abort();
648 qsort (p, nv, sizeof(*p), delaunay_xyzcompare);
649 if (delaunay (nv, p, v, &ntri))
651 fprintf (stderr, "%s: out of memory\n", progname);
655 /* Create the output pixmap based on that triangulation. */
658 XFreePixmap (st->dpy, st->output);
659 st->output = XCreatePixmap (st->dpy, st->window,
660 st->delta->width, st->delta->height,
662 XFillRectangle (st->dpy, st->output, st->pgc,
663 0, 0, st->delta->width, st->delta->height);
667 voronoi_polygon *polys = delaunay_to_voronoi (nv, p, ntri, v);
668 for (i = 0; i < nv; i++)
670 if (polys[i].npoints >= 3)
672 unsigned long color = XGetPixel (st->img, p[i].x, p[i].y);
673 XSetForeground (st->dpy, st->pgc, color);
674 XFillPolygon (st->dpy, st->output, st->pgc,
675 polys[i].p, polys[i].npoints,
676 Convex, CoordModeOrigin);
683 XQueryColor (st->dpy, st->xgwa.colormap, &bd);
688 /* bd.red = 0xFFFF; bd.green = 0; bd.blue = 0; */
690 XAllocColor (st->dpy, st->xgwa.colormap, &bd);
691 XSetForeground (st->dpy, st->pgc, bd.pixel);
692 XDrawLines (st->dpy, st->output, st->pgc,
693 polys[i].p, polys[i].npoints,
695 XFreeColors (st->dpy, st->xgwa.colormap, &bd.pixel, 1, 0);
698 if (polys[i].p) free (polys[i].p);
703 #else /* !DO_VORONOI */
705 for (i = 0; i < ntri; i++)
709 xp[0].x = p[v[i].p1].x; xp[0].y = p[v[i].p1].y;
710 xp[1].x = p[v[i].p2].x; xp[1].y = p[v[i].p2].y;
711 xp[2].x = p[v[i].p3].x; xp[2].y = p[v[i].p3].y;
713 /* Set the color of this triangle to the pixel at its midpoint. */
714 color = XGetPixel (st->img,
715 (xp[0].x + xp[1].x + xp[2].x) / 3,
716 (xp[0].y + xp[1].y + xp[2].y) / 3);
718 XSetForeground (st->dpy, st->pgc, color);
719 XFillPolygon (st->dpy, st->output, st->pgc, xp, countof(xp),
720 Convex, CoordModeOrigin);
722 if (st->outline_p && !small_triangle_p(xp))
723 { /* Border the triangle with a color that is darker */
727 XQueryColor (st->dpy, st->xgwa.colormap, &bd);
732 /* bd.red = 0xFFFF; bd.green = 0; bd.blue = 0; */
734 XAllocColor (st->dpy, st->xgwa.colormap, &bd);
735 XSetForeground (st->dpy, st->pgc, bd.pixel);
736 XDrawLines (st->dpy, st->output, st->pgc,
737 xp, countof(xp), CoordModeOrigin);
738 XFreeColors (st->dpy, st->xgwa.colormap, &bd.pixel, 1, 0);
741 #endif /* !DO_VORONOI */
746 if (st->cache_p && !st->cache[st->thresh])
748 st->cache[st->thresh] =
749 XCreatePixmap (st->dpy, st->window,
750 st->delta->width, st->delta->height,
752 if (! st->cache[st->thresh])
754 fprintf (stderr, "%s: out of memory\n", progname);
760 st->cache[st->thresh],
762 0, 0, st->delta->width, st->delta->height,
767 if (! st->output) abort();
771 /* Convert the delta map into a displayable pixmap.
774 get_deltap (struct state *st)
777 int w = st->delta->width;
778 int h = st->delta->height;
781 Visual *v = st->xgwa.visual;
782 unsigned long rmsk=0, gmsk=0, bmsk=0;
783 unsigned int rpos=0, gpos=0, bpos=0;
784 unsigned int rsiz=0, gsiz=0, bsiz=0;
786 if (st->deltap) return st->deltap;
788 visual_rgb_masks (st->xgwa.screen, v, &rmsk, &gmsk, &bmsk);
789 decode_mask (rmsk, &rpos, &rsiz);
790 decode_mask (gmsk, &gpos, &gsiz);
791 decode_mask (bmsk, &bpos, &bsiz);
793 dimg = XCreateImage (st->dpy, st->xgwa.visual, st->xgwa.depth,
794 ZPixmap, 0, NULL, w, h, 8, 0);
796 dimg->data = (char *) calloc (dimg->height, dimg->bytes_per_line);
797 if (! dimg->data) abort();
799 for (y = 0; y < h; y++)
800 for (x = 0; x < w; x++)
802 unsigned long v = XGetPixel (st->delta, x, y) << 5;
803 unsigned long p = (((v << rpos) & rmsk) |
804 ((v << gpos) & gmsk) |
805 ((v << bpos) & bmsk));
806 XPutPixel (dimg, x, y, p);
809 st->deltap = XCreatePixmap (st->dpy, st->window, w, h, st->xgwa.depth);
810 XPutImage (st->dpy, st->deltap, st->pgc, dimg, 0, 0, 0, 0, w, h);
811 XDestroyImage (dimg);
817 tessellimage_draw (Display *dpy, Window window, void *closure)
819 struct state *st = (struct state *) closure;
821 if (st->img_loader) /* still loading */
823 st->img_loader = load_image_async_simple (st->img_loader, 0, 0, 0, 0,
825 if (! st->img_loader) { /* just finished */
827 st->start_time = double_time();
828 st->start_time2 = st->start_time;
833 if (!st->img_loader &&
834 st->start_time + st->duration < double_time()) {
835 XClearWindow (st->dpy, st->window);
836 if (st->image) XFreePixmap (dpy, st->image);
837 st->image = XCreatePixmap (st->dpy, st->window,
838 st->xgwa.width, st->xgwa.height,
840 st->img_loader = load_image_async_simple (0, st->xgwa.screen, st->window,
841 st->image, 0, &st->geom);
847 XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
848 XClearWindow (st->dpy, st->window);
852 (st->button_down_p ? get_deltap (st) : st->output),
854 0, 0, st->delta->width, st->delta->height,
855 (st->xgwa.width - st->delta->width) / 2,
856 (st->xgwa.height - st->delta->height) / 2);
857 else if (!st->nthreshes)
861 0, 0, st->xgwa.width, st->xgwa.height,
871 tessellimage_reshape (Display *dpy, Window window, void *closure,
872 unsigned int w, unsigned int h)
874 struct state *st = (struct state *) closure;
875 XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
879 tessellimage_event (Display *dpy, Window window, void *closure, XEvent *event)
881 struct state *st = (struct state *) closure;
882 if (event->xany.type == ButtonPress)
884 st->button_down_p = True;
887 else if (event->xany.type == ButtonRelease)
889 st->button_down_p = False;
892 else if (screenhack_event_helper (dpy, window, event))
894 st->start_time = 0; /* load next image */
903 tessellimage_free (Display *dpy, Window window, void *closure)
905 struct state *st = (struct state *) closure;
907 if (st->wgc) XFreeGC (dpy, st->wgc);
908 if (st->pgc) XFreeGC (dpy, st->pgc);
909 if (st->image) XFreePixmap (dpy, st->image);
910 if (st->output) XFreePixmap (dpy, st->output);
911 if (st->delta) XDestroyImage (st->delta);
918 static const char *tessellimage_defaults [] = {
919 ".background: black",
920 ".foreground: white",
921 "*dontClearRoot: True",
931 "*ignoreRotation: True",
932 "*rotateImages: True",
937 static XrmOptionDescRec tessellimage_options [] = {
938 { "-delay", ".delay", XrmoptionSepArg, 0 },
939 { "-duration", ".duration", XrmoptionSepArg, 0 },
940 { "-duration2", ".duration2", XrmoptionSepArg, 0 },
941 { "-max-depth", ".maxDepth", XrmoptionSepArg, 0 },
942 { "-outline", ".outline", XrmoptionNoArg, "True" },
943 { "-no-outline", ".outline", XrmoptionNoArg, "False" },
944 { "-fill-screen", ".fillScreen", XrmoptionNoArg, "True" },
945 { "-no-fill-screen", ".fillScreen", XrmoptionNoArg, "False" },
946 { "-cache", ".cache", XrmoptionNoArg, "True" },
947 { "-no-cache", ".cache", XrmoptionNoArg, "False" },
951 XSCREENSAVER_MODULE ("Tessellimage", tessellimage)