git.hungrycats.org Git - xscreensaver/blob - hacks/tessellimage.c

   1 /* tessellimage, Copyright (c) 2014-2018 Jamie Zawinski <jwz@jwz.org>
   2  *
   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
   9  * implied warranty.
  10  */
  11
  12 #include "screenhack.h"
  13 #include "delaunay.h"
  14
  15 #ifndef HAVE_JWXYZ
  16 # define XK_MISCELLANY
  17 # include <X11/keysymdef.h>
  18 #endif
  19
  20 #undef countof
  21 #define countof(x) (sizeof((x))/sizeof((*x)))
  22
  23 struct state {
  24   Display *dpy;
  25   Window window;
  26   XWindowAttributes xgwa;
  27   GC wgc, pgc;
  28   int delay;
  29   Bool outline_p, cache_p, fill_p;
  30   double duration, duration2;
  31   int max_depth, max_resolution;
  32   double start_time, start_time2;
  33
  34   XImage *img, *delta;
  35   Pixmap image, output, deltap;
  36   int nthreshes, threshes[256], vsizes[256];
  37   int thresh, dthresh;
  38   Pixmap cache[256];
  39
  40   async_load_state *img_loader;
  41   XRectangle geom;
  42   Bool button_down_p;
  43   enum { DELAUNAY, VORONOI } mode;
  44 };
  45
  46 typedef struct {
  47   int npoints;
  48   XPoint ctr;
  49   XPoint *p;
  50 } voronoi_polygon;
  51
  52 typedef struct {
  53   XPoint p;
  54   double slope;
  55 } voronoi_pa;
  56
  57
  58 /* Returns the current time in seconds as a double.
  59  */
  60 static double
  61 double_time (void)
  62 {
  63   struct timeval now;
  64 # ifdef GETTIMEOFDAY_TWO_ARGS
  65   struct timezone tzp;
  66   gettimeofday(&now, &tzp);
  67 # else
  68   gettimeofday(&now);
  69 # endif
  70
  71   return (now.tv_sec + ((double) now.tv_usec * 0.000001));
  72 }
  73
  74
  75 static void *
  76 tessellimage_init (Display *dpy, Window window)
  77 {
  78   struct state *st = (struct state *) calloc (1, sizeof(*st));
  79
  80   st->dpy = dpy;
  81   st->window = window;
  82
  83   XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
  84
  85   st->delay = get_integer_resource (st->dpy, "delay", "Integer");
  86   if (st->delay < 1) st->delay = 1;
  87
  88   st->outline_p = get_boolean_resource (st->dpy, "outline", "Boolean");
  89   st->cache_p   = get_boolean_resource (st->dpy, "cache", "Boolean");
  90   st->fill_p    = get_boolean_resource (st->dpy, "fillScreen", "Boolean");
  91
  92   st->max_depth = get_integer_resource (st->dpy, "maxDepth", "MaxDepth");
  93   if (st->max_depth < 100) st->max_depth = 100;
  94
  95   st->max_resolution = get_integer_resource (st->dpy,
  96                                              "maxResolution", "MaxResolution");
  97   if (st->max_resolution < 0) st->max_resolution = 0;
  98
  99   st->duration = get_float_resource (st->dpy, "duration", "Seconds");
 100   if (st->duration < 1) st->duration = 1;
 101
 102   st->duration2 = get_float_resource (st->dpy, "duration2", "Seconds");
 103   if (st->duration2 < 0.001) st->duration = 0.001;
 104
 105   XClearWindow(st->dpy, st->window);
 106
 107   return st;
 108 }
 109
 110
 111 /* Given a bitmask, returns the position and width of the field.
 112  */
 113 static void
 114 decode_mask (unsigned int mask, unsigned int *pos_ret, unsigned int *size_ret)
 115 {
 116   int i;
 117   for (i = 0; i < 32; i++)
 118     if (mask & (1L << i))
 119       {
 120         int j = 0;
 121         *pos_ret = i;
 122         for (; i < 32; i++, j++)
 123           if (! (mask & (1L << i)))
 124             break;
 125         *size_ret = j;
 126         return;
 127       }
 128 }
 129
 130
 131 static unsigned long
 132 pixel_distance (Screen *s, Visual *v, unsigned long p1, unsigned long p2)
 133 {
 134   static int initted_p = 0;
 135   static unsigned long rmsk=0, gmsk=0, bmsk=0;
 136   static unsigned int rpos=0, gpos=0, bpos=0;
 137   static unsigned int rsiz=0, gsiz=0, bsiz=0;
 138
 139   unsigned char r1, g1, b1;
 140   unsigned char r2, g2, b2;
 141   long distance;
 142
 143   if (!p1 && !p2) return 0;
 144
 145   if (! initted_p) {
 146     visual_rgb_masks (s, v, &rmsk, &gmsk, &bmsk);
 147     decode_mask (rmsk, &rpos, &rsiz);
 148     decode_mask (gmsk, &gpos, &gsiz);
 149     decode_mask (bmsk, &bpos, &bsiz);
 150     initted_p = 1;
 151   }
 152
 153   r1 = (p1 & rmsk) >> rpos;
 154   g1 = (p1 & gmsk) >> gpos;
 155   b1 = (p1 & bmsk) >> bpos;
 156
 157   r2 = (p2 & rmsk) >> rpos;
 158   g2 = (p2 & gmsk) >> gpos;
 159   b2 = (p2 & bmsk) >> bpos;
 160
 161 #if 0
 162   /* Compute the distance in linear RGB space.
 163    */
 164   distance = cbrt (((r2 - r1) * (r2 - r1)) +
 165                    ((g2 - g1) * (g2 - g1)) +
 166                    ((b2 - b1) * (b2 - b1)));
 167
 168 # elif 1
 169   /* Compute the distance in luminance-weighted RGB space.
 170    */
 171   {
 172     int rd = (r2 - r1) * 0.2989 * (1 / 0.5870);
 173     int gd = (g2 - g1) * 0.5870 * (1 / 0.5870);
 174     int bd = (b2 - b1) * 0.1140 * (1 / 0.5870);
 175     distance = cbrt ((rd * rd) + (gd * gd) + (bd * bd));
 176   }
 177 # else
 178   /* Compute the distance in brightness-weighted HSV space.
 179      (Slower, and doesn't seem to look better than luminance RGB.)
 180    */
 181   {
 182     int h1, h2;
 183     double s1, s2;
 184     double v1, v2;
 185     double hd, sd, vd, dd;
 186     rgb_to_hsv (r1, g1, b1, &h1, &s1, &v1);
 187     rgb_to_hsv (r2, g2, b2, &h2, &s2, &v2);
 188
 189     hd = abs (h2 - h1);
 190     if (hd >= 180) hd -= 180;
 191     hd /= 180.0;
 192     sd = fabs (s2 - s1);
 193     vd = fabs (v2 - v1);
 194
 195     /* [hsv]d are now the distance as 0.0 - 1.0. */
 196     /* Compute the overall distance, giving more weight to V. */
 197     dd = (hd * 0.25 + sd * 0.25 + vd * 0.5);
 198
 199     if (dd < 0 || dd > 1.0) abort();
 200     distance = dd * 255;
 201   }
 202 # endif
 203
 204   if (distance < 0) distance = -distance;
 205   return distance;
 206 }
 207
 208
 209 static void
 210 flush_cache (struct state *st)
 211 {
 212   int i;
 213   for (i = 0; i < countof(st->cache); i++)
 214     if (st->cache[i])
 215       {
 216         XFreePixmap (st->dpy, st->cache[i]);
 217         st->cache[i] = 0;
 218       }
 219   if (st->deltap)
 220     {
 221       XFreePixmap (st->dpy, st->deltap);
 222       st->deltap = 0;
 223     }
 224 }
 225
 226
 227 /* Scale up the bits in st->img so that it fills the screen, centered.
 228  */
 229 static void
 230 scale_image (struct state *st)
 231 {
 232   double scale, s1, s2;
 233   XImage *img2;
 234   int x, y, cx, cy;
 235
 236   if (st->geom.width <= 0 || st->geom.height <= 0)
 237     return;
 238
 239   s1 = st->geom.width  / (double) st->img->width;
 240   s2 = st->geom.height / (double) st->img->height;
 241   scale = (s1 < s2 ? s1 : s2);
 242
 243   img2 = XCreateImage (st->dpy, st->xgwa.visual, st->img->depth,
 244                        ZPixmap, 0, NULL,
 245                        st->img->width, st->img->height, 8, 0);
 246   if (! img2) abort();
 247   img2->data = (char *) calloc (img2->height, img2->bytes_per_line);
 248   if (! img2->data) abort();
 249
 250   cx = st->img->width  / 2;
 251   cy = st->img->height / 2;
 252
 253   if (st->geom.width < st->geom.height)  /* portrait: aim toward the top */
 254     cy = st->img->height / (2 / scale);
 255
 256   for (y = 0; y < img2->height; y++)
 257     for (x = 0; x < img2->width; x++)
 258       {
 259         int x2 = cx + ((x - cx) * scale);
 260         int y2 = cy + ((y - cy) * scale);
 261         unsigned long p = 0;
 262         if (x2 >= 0 && y2 >= 0 &&
 263             x2 < st->img->width && y2 < st->img->height)
 264           p = XGetPixel (st->img, x2, y2);
 265         XPutPixel (img2, x, y, p);
 266       }
 267   free (st->img->data);
 268   st->img->data = 0;
 269   XDestroyImage (st->img);
 270   st->img = img2;
 271
 272   st->geom.x = 0;
 273   st->geom.y = 0;
 274   st->geom.width = st->img->width;
 275   st->geom.height = st->img->height;
 276 }
 277
 278
 279
 280 static void
 281 analyze (struct state *st)
 282 {
 283   Window root;
 284   int x, y, i;
 285   unsigned int w, h, bw, d;
 286   unsigned long histo[256];
 287
 288   {
 289     char *s = get_string_resource (st->dpy, "mode", "Mode");
 290     if (!s || !*s || !strcasecmp(s, "random"))
 291       st->mode = (random() & 1) ? DELAUNAY : VORONOI;
 292     else if (!strcasecmp(s, "delaunay"))
 293       st->mode = DELAUNAY;
 294     else if (!strcasecmp(s, "voronoi"))
 295       st->mode = VORONOI;
 296     else
 297       {
 298         fprintf (stderr,
 299                  "%s: mode must be delaunay, voronoi or random, not \"%s\"\n",
 300                  progname, s);
 301         exit (1);
 302       }
 303   }
 304
 305   flush_cache (st);
 306
 307   /* Convert the loaded pixmap to an XImage.
 308    */
 309   XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
 310   XGetGeometry (st->dpy, st->image, &root, &x, &y, &w, &h, &bw, &d);
 311
 312   if (st->img)
 313     {
 314       free (st->img->data);
 315       st->img->data = 0;
 316       XDestroyImage (st->img);
 317     }
 318   st->img = XGetImage (st->dpy, st->image, 0, 0, w, h, ~0L, ZPixmap);
 319
 320   if (st->fill_p) scale_image (st);
 321
 322   /* Create the delta map: color space distance between each pixel.
 323      Maybe doing running a Sobel Filter matrix on this would be a
 324      better idea.  That might be a bit faster, but I think it would
 325      make no visual difference.
 326    */
 327   if (st->delta)
 328     {
 329       free (st->delta->data);
 330       st->delta->data = 0;
 331       XDestroyImage (st->delta);
 332     }
 333   st->delta = XCreateImage (st->dpy, st->xgwa.visual, d, ZPixmap, 0, NULL,
 334                             w, h, 32, 0);
 335   st->delta->data = (char *)
 336     calloc (st->delta->height, st->delta->bytes_per_line);
 337
 338   for (y = 0; y < st->delta->height; y++)
 339     {
 340       for (x = 0; x < st->delta->width; x++)
 341         {
 342           unsigned long pixels[5];
 343           int i = 0;
 344           int distance = 0;
 345           pixels[i++] =                     XGetPixel (st->img, x,   y);
 346           pixels[i++] = (x > 0 && y > 0   ? XGetPixel (st->img, x-1, y-1) : 0);
 347           pixels[i++] = (         y > 0   ? XGetPixel (st->img, x,   y-1) : 0);
 348           pixels[i++] = (x > 0            ? XGetPixel (st->img, x-1, y)   : 0);
 349           pixels[i++] = (x > 0 && y < h-1 ? XGetPixel (st->img, x-1, y+1) : 0);
 350
 351           for (i = 1; i < countof(pixels); i++)
 352             distance += pixel_distance (st->xgwa.screen, st->xgwa.visual,
 353                                         pixels[0], pixels[i]);
 354           distance /= countof(pixels)-1;
 355           XPutPixel (st->delta, x, y, distance);
 356         }
 357     }
 358
 359   /* Collect a histogram of every distance value.
 360    */
 361   memset (histo, 0, sizeof(histo));
 362   for (y = 0; y < st->delta->height; y++)
 363     for (x = 0; x < st->delta->width; x++)
 364       {
 365         unsigned long p = XGetPixel (st->delta, x, y);
 366         if (p > sizeof(histo)) abort();
 367         histo[p]++;
 368       }
 369
 370   /* Convert that from "occurrences of N" to ">= N".
 371    */
 372   for (i = countof(histo) - 1; i > 0; i--)
 373     histo[i-1] += histo[i];
 374
 375 # if 0
 376   fprintf (stderr, "%s: histo: ", progname);
 377   for (i = 0; i < countof(histo); i++)
 378     fprintf(stderr, "%d:%lu ", i, histo[i]);
 379   fprintf(stderr, "\n");
 380 # endif
 381
 382   /* Collect a useful set of threshold values, ignoring thresholds that
 383      result in a very similar number of control points (since those images
 384      probably won't look very different).
 385    */
 386
 387   {
 388     int max_vsize = st->max_depth;
 389     int min_vsize = 20;
 390     int min_delta = 100;
 391
 392     if (min_vsize > max_vsize/100)
 393       min_vsize = max_vsize/100;
 394
 395     if (min_delta > max_vsize/1000)
 396       min_delta = max_vsize/1000;
 397
 398     st->nthreshes = 0;
 399     for (i = countof(histo)-1; i >= 0; i--)
 400       {
 401         unsigned long vsize = histo[i];
 402
 403         /* If this is a different vsize, push it. */
 404         if (vsize >= min_vsize &&
 405             vsize <= max_vsize &&
 406             (st->nthreshes == 0 ||
 407              vsize >= st->vsizes[st->nthreshes-1] + min_delta))
 408           {
 409             st->threshes[st->nthreshes] = i;
 410             st->vsizes[st->nthreshes] = vsize;
 411             st->nthreshes++;
 412           }
 413       }
 414   }
 415
 416   st->thresh = 0;   /* startup */
 417   st->dthresh = 1;  /* forward */
 418
 419   if (st->output)
 420     {
 421       XFreePixmap (st->dpy, st->output);
 422       st->output = 0;
 423     }
 424
 425
 426 # if 0
 427   fprintf (stderr, "%s: threshes:", progname);
 428   for (i = 0; i < st->nthreshes; i++)
 429     fprintf (stderr, " %d=%d", st->threshes[i], st->vsizes[i]);
 430   fprintf (stderr, "\n");
 431 # endif
 432 }
 433
 434
 435 /* True if the distance between any two corners is too small for it to
 436    make sense to draw an outline around this triangle.
 437  */
 438 static Bool
 439 small_triangle_p (const XPoint *p)
 440 {
 441   int min = 4;
 442   if (abs (p[0].x - p[1].x) < min) return True;
 443   if (abs (p[0].y - p[1].y) < min) return True;
 444   if (abs (p[1].x - p[2].x) < min) return True;
 445   if (abs (p[1].y - p[2].y) < min) return True;
 446   if (abs (p[2].x - p[0].x) < min) return True;
 447   if (abs (p[2].y - p[0].y) < min) return True;
 448   return False;
 449 }
 450
 451 static Bool
 452 small_cell_p (const voronoi_polygon *p)
 453 {
 454   int min = 4;
 455   if (abs (p->p[0].x - p->ctr.x) < min) return True;
 456   if (abs (p->p[0].y - p->ctr.y) < min) return True;
 457   return False;
 458 }
 459
 460
 461 static int
 462 cmp_ccw (const void *v1, const void *v2)
 463 {
 464   const voronoi_pa *p1,*p2;
 465   p1 = v1;
 466   p2 = v2;
 467   if      (p1->slope < p2->slope) return -1;
 468   else if (p1->slope > p2->slope) return  1;
 469   return 0;
 470 }
 471
 472 static void
 473 sort_ccw (XPoint *ctr, XPoint *p, int npoints)
 474 {
 475   voronoi_pa *pa = (void *) malloc (npoints * sizeof(*pa));
 476   int i;
 477   for (i = 0; i < npoints; i++)
 478     {
 479       pa[i].p = p[i];
 480       pa[i].slope = atan2 (p[i].x - ctr->x, p[i].y - ctr->y);
 481     }
 482   qsort (pa, npoints, sizeof(*pa), cmp_ccw);
 483   for (i = 0; i < npoints; i++)
 484     p[i] = pa[i].p;
 485   free (pa);
 486 }
 487
 488
 489 static voronoi_polygon *
 490 delaunay_to_voronoi (int np, XYZ *p, int nv, ITRIANGLE *v, double scale)
 491 {
 492   struct tri_list {
 493     int count, size;
 494     int *tri;
 495   };
 496
 497   int i, j;
 498   struct tri_list *vert_to_tri = (struct tri_list *)
 499     calloc (np + 1, sizeof(*vert_to_tri));
 500   voronoi_polygon *out = (voronoi_polygon *) calloc (np + 1, sizeof(*out));
 501
 502   /* Iterate the triangles to construct a map of vertices to the
 503      triangles that contain them.
 504    */
 505   for (i = 0; i < nv; i++)
 506     {
 507       for (j = 0; j < 3; j++)   /* iterate points in each triangle */
 508         {
 509           int p = *((&v[i].p1) + j);
 510           struct tri_list *t = &vert_to_tri[p];
 511           if (p < 0 || p >= np) abort();
 512           if (t->size <= t->count + 1)
 513             {
 514               t->size += 3;
 515               t->size *= 1.3;
 516               t->tri = realloc (t->tri, t->size * sizeof(*t->tri));
 517               if (! t->tri) abort();
 518             }
 519           t->tri[t->count++] = i;
 520         }
 521     }
 522
 523   /* For every vertex, compose a polygon whose corners are the centers
 524      of each triangle using that vertex.  Skip any with less than 3 points.
 525
 526      This is currently omitting the voronoi cells that should touch the edges
 527      of the outer rectangle. Not sure exactly how to include those.
 528    */
 529   for (i = 0; i < np; i++)
 530     {
 531       long ctr_x = 0, ctr_y = 0;
 532       struct tri_list *t = &vert_to_tri[i];
 533       int n = t->count;
 534       if (n < 3) n = 0;
 535       out[i].npoints = n;
 536       if (n == 0) continue;
 537       out[i].ctr.x = out[i].ctr.y = 0;
 538       out[i].p = (n > 0
 539                   ? (XPoint *) calloc (out[i].npoints + 1, sizeof (*out[i].p))
 540                   : 0);
 541       for (j = 0; j < out[i].npoints; j++)
 542         {
 543           ITRIANGLE *tt = &v[t->tri[j]];
 544           out[i].p[j].x = scale * (p[tt->p1].x + p[tt->p2].x + p[tt->p3].x) / 3;
 545           out[i].p[j].y = scale * (p[tt->p1].y + p[tt->p2].y + p[tt->p3].y) / 3;
 546           ctr_x += out[i].p[j].x;
 547           ctr_y += out[i].p[j].y;
 548         }
 549       out[i].ctr.x = ctr_x / out[i].npoints;  /* long -> short */
 550       out[i].ctr.y = ctr_y / out[i].npoints;
 551       if (out[i].ctr.x < 0) abort();
 552       if (out[i].ctr.y < 0) abort();
 553       sort_ccw (&out[i].ctr, out[i].p, out[i].npoints);
 554     }
 555
 556   for (i = 0; i < np+1; i++)
 557     if (vert_to_tri[i].tri)
 558       free (vert_to_tri[i].tri);
 559   free (vert_to_tri);
 560
 561   return out;
 562 }
 563
 564
 565 static void
 566 tessellate (struct state *st)
 567 {
 568   Bool ticked_p = False;
 569
 570   if (! st->image) return;
 571
 572   if (! st->wgc)
 573     {
 574       XGCValues gcv;
 575       gcv.function = GXcopy;
 576       gcv.subwindow_mode = IncludeInferiors;
 577       st->wgc = XCreateGC(st->dpy, st->window, GCFunction, &gcv);
 578       st->pgc = XCreateGC(st->dpy, st->image, GCFunction, &gcv);
 579     }
 580
 581   if (! st->nthreshes) return;
 582
 583
 584   /* If duration2 has expired, switch to the next threshold. */
 585
 586   if (! st->button_down_p)
 587     {
 588       double t2 = double_time();
 589       if (st->start_time2 + st->duration2 < t2)
 590         {
 591           st->start_time2 = t2;
 592           st->thresh += st->dthresh;
 593           ticked_p = True;
 594           if (st->thresh >= st->nthreshes)
 595             {
 596               st->thresh = st->nthreshes - 1;
 597               st->dthresh = -1;
 598             }
 599           else if (st->thresh < 0)
 600             {
 601               st->thresh = 0;
 602               st->dthresh = 1;
 603             }
 604         }
 605     }
 606
 607   if (! st->output)
 608     ticked_p = True;
 609
 610   /* If we've picked a new threshold, regenerate the output image. */
 611
 612   if (ticked_p && st->cache[st->thresh])
 613     {
 614       if (st->output)
 615         XCopyArea (st->dpy,
 616                    st->cache[st->thresh],
 617                    st->output, st->pgc,
 618                    0, 0, st->xgwa.width, st->xgwa.height,
 619                    0, 0);
 620     }
 621   else if (ticked_p)
 622     {
 623       int threshold = st->threshes[st->thresh];
 624       int vsize = st->vsizes[st->thresh];
 625       ITRIANGLE *v;
 626       XYZ *p = 0;
 627       int nv = 0;
 628       int ntri = 0;
 629       int x, y, i;
 630       double wscale = st->xgwa.width / (double) st->delta->width;
 631
 632 #if 0
 633       fprintf(stderr, "%s: thresh %d/%d = %d=%d\n",
 634               progname, st->thresh, st->nthreshes, threshold, vsize);
 635 #endif
 636
 637       /* Create a control point at every pixel where the delta is above
 638          the current threshold.  Triangulate from those. */
 639
 640       vsize += 8;  /* corners of screen + corners of image */
 641
 642       p = (XYZ *) calloc (vsize+4, sizeof(*p));
 643       v = (ITRIANGLE *) calloc (3*(vsize+4), sizeof(*v));
 644       if (!p || !v)
 645         {
 646           fprintf (stderr, "%s: out of memory (%d)\n", progname, vsize);
 647           abort();
 648         }
 649
 650       /* Add control points for the corners of the screen, and for the
 651          corners of the image.
 652        */
 653       if (st->geom.width  <= 0) st->geom.width  = st->delta->width;
 654       if (st->geom.height <= 0) st->geom.height = st->delta->height;
 655
 656       for (y = 0; y <= 1; y++)
 657         for (x = 0; x <= 1; x++)
 658           {
 659             p[nv].x = x ? st->delta->width-1  : 0;
 660             p[nv].y = y ? st->delta->height-1 : 0;
 661             p[nv].z = XGetPixel (st->delta, (int) p[nv].x, (int) p[nv].y);
 662             nv++;
 663             p[nv].x = st->geom.x + (x ? st->geom.width-1  : 0);
 664             p[nv].y = st->geom.y + (y ? st->geom.height-1 : 0);
 665             p[nv].z = XGetPixel (st->delta, (int) p[nv].x, (int) p[nv].y);
 666             nv++;
 667           }
 668
 669       /* Add control points for every pixel that exceeds the threshold.
 670        */
 671       for (y = 0; y < st->delta->height; y++)
 672         for (x = 0; x < st->delta->width; x++)
 673           {
 674             unsigned long px = XGetPixel (st->delta, x, y);
 675             if (px >= threshold)
 676               {
 677                 if (nv >= vsize) abort();
 678                 p[nv].x = x;
 679                 p[nv].y = y;
 680                 p[nv].z = px;
 681                 nv++;
 682               }
 683           }
 684
 685       if (nv != vsize) abort();
 686
 687       qsort (p, nv, sizeof(*p), delaunay_xyzcompare);
 688       if (delaunay (nv, p, v, &ntri))
 689         {
 690           fprintf (stderr, "%s: out of memory\n", progname);
 691           abort();
 692         }
 693
 694       /* Create the output pixmap based on that triangulation. */
 695
 696       if (st->output)
 697         XFreePixmap (st->dpy, st->output);
 698       st->output = XCreatePixmap (st->dpy, st->window,
 699                                   st->xgwa.width, st->xgwa.height,
 700                                   st->xgwa.depth);
 701       XFillRectangle (st->dpy, st->output, st->pgc,
 702                       0, 0, st->xgwa.width, st->xgwa.height);
 703
 704       switch (st->mode) {
 705       case VORONOI:
 706         {
 707           voronoi_polygon *polys =
 708             delaunay_to_voronoi (nv, p, ntri, v, wscale);
 709           for (i = 0; i < nv; i++)
 710             {
 711               if (polys[i].npoints >= 3)
 712                 {
 713                   unsigned long color = XGetPixel (st->img,
 714                                                    polys[i].ctr.x / wscale,
 715                                                    polys[i].ctr.y / wscale);
 716                   XSetForeground (st->dpy, st->pgc, color);
 717                   XFillPolygon (st->dpy, st->output, st->pgc,
 718                                 polys[i].p, polys[i].npoints,
 719                                 Convex, CoordModeOrigin);
 720
 721                   if (st->outline_p && !small_cell_p(&polys[i]))
 722                     {
 723                       XColor bd;
 724                       double scale = 0.8;
 725                       bd.pixel = color;
 726                       XQueryColor (st->dpy, st->xgwa.colormap, &bd);
 727                       bd.red   *= scale;
 728                       bd.green *= scale;
 729                       bd.blue  *= scale;
 730
 731                       /* bd.red = 0xFFFF; bd.green = 0; bd.blue = 0; */
 732
 733                       XAllocColor (st->dpy, st->xgwa.colormap, &bd);
 734                       XSetForeground (st->dpy, st->pgc, bd.pixel);
 735                       XDrawLines (st->dpy, st->output, st->pgc,
 736                                   polys[i].p, polys[i].npoints,
 737                                   CoordModeOrigin);
 738                       XFreeColors (st->dpy, st->xgwa.colormap, &bd.pixel,
 739                                    1, 0);
 740                     }
 741                 }
 742               if (polys[i].p) free (polys[i].p);
 743               polys[i].p = 0;
 744             }
 745           free (polys);
 746         }
 747         break;
 748
 749       case DELAUNAY:
 750         for (i = 0; i < ntri; i++)
 751           {
 752             XPoint xp[3];
 753             unsigned long color;
 754             xp[0].x = p[v[i].p1].x * wscale; xp[0].y = p[v[i].p1].y * wscale;
 755             xp[1].x = p[v[i].p2].x * wscale; xp[1].y = p[v[i].p2].y * wscale;
 756             xp[2].x = p[v[i].p3].x * wscale; xp[2].y = p[v[i].p3].y * wscale;
 757
 758             /* Set the color of this triangle to the pixel at its midpoint. */
 759             color = XGetPixel (st->img,
 760                                (xp[0].x + xp[1].x + xp[2].x) / (3 * wscale),
 761                                (xp[0].y + xp[1].y + xp[2].y) / (3 * wscale));
 762
 763             XSetForeground (st->dpy, st->pgc, color);
 764             XFillPolygon (st->dpy, st->output, st->pgc, xp, countof(xp),
 765                           Convex, CoordModeOrigin);
 766
 767             if (st->outline_p && !small_triangle_p(xp))
 768               { /* Border the triangle with a color that is darker */
 769                 XColor bd;
 770                 double scale = 0.8;
 771                 bd.pixel = color;
 772                 XQueryColor (st->dpy, st->xgwa.colormap, &bd);
 773                 bd.red   *= scale;
 774                 bd.green *= scale;
 775                 bd.blue  *= scale;
 776
 777                 /* bd.red = 0xFFFF; bd.green = 0; bd.blue = 0; */
 778
 779                 XAllocColor (st->dpy, st->xgwa.colormap, &bd);
 780                 XSetForeground (st->dpy, st->pgc, bd.pixel);
 781                 XDrawLines (st->dpy, st->output, st->pgc,
 782                             xp, countof(xp), CoordModeOrigin);
 783                 XFreeColors (st->dpy, st->xgwa.colormap, &bd.pixel, 1, 0);
 784               }
 785           }
 786         break;
 787       default:
 788         abort();
 789       }
 790
 791       free (p);
 792       free (v);
 793
 794       if (st->cache_p && !st->cache[st->thresh])
 795         {
 796           st->cache[st->thresh] =
 797             XCreatePixmap (st->dpy, st->window,
 798                            st->xgwa.width, st->xgwa.height,
 799                            st->xgwa.depth);
 800           if (! st->cache[st->thresh])
 801             {
 802               fprintf (stderr, "%s: out of memory\n", progname);
 803               abort();
 804             }
 805           if (st->output)
 806             XCopyArea (st->dpy,
 807                        st->output,
 808                        st->cache[st->thresh],
 809                        st->pgc,
 810                        0, 0, st->xgwa.width, st->xgwa.height,
 811                        0, 0);
 812         }
 813     }
 814
 815   if (! st->output) abort();
 816 }
 817
 818
 819 /* Convert the delta map into a displayable pixmap.
 820  */
 821 static Pixmap
 822 get_deltap (struct state *st)
 823 {
 824   int x, y;
 825   int w = st->xgwa.width;
 826   int h = st->xgwa.height;
 827   double wscale = st->xgwa.width / (double) st->delta->width;
 828   XImage *dimg;
 829
 830   Visual *v = st->xgwa.visual;
 831   unsigned long rmsk=0, gmsk=0, bmsk=0;
 832   unsigned int rpos=0, gpos=0, bpos=0;
 833   unsigned int rsiz=0, gsiz=0, bsiz=0;
 834
 835   if (st->deltap) return st->deltap;
 836
 837   visual_rgb_masks (st->xgwa.screen, v, &rmsk, &gmsk, &bmsk);
 838   decode_mask (rmsk, &rpos, &rsiz);
 839   decode_mask (gmsk, &gpos, &gsiz);
 840   decode_mask (bmsk, &bpos, &bsiz);
 841
 842   dimg = XCreateImage (st->dpy, st->xgwa.visual, st->xgwa.depth,
 843                        ZPixmap, 0, NULL, w, h, 8, 0);
 844   if (! dimg) abort();
 845   dimg->data = (char *) calloc (dimg->height, dimg->bytes_per_line);
 846   if (! dimg->data) abort();
 847
 848   for (y = 0; y < h; y++)
 849     for (x = 0; x < w; x++)
 850       {
 851         unsigned long v = XGetPixel (st->delta, x / wscale, y / wscale) << 5;
 852         unsigned long p = (((v << rpos) & rmsk) |
 853                            ((v << gpos) & gmsk) |
 854                            ((v << bpos) & bmsk));
 855         XPutPixel (dimg, x, y, p);
 856       }
 857
 858   st->deltap = XCreatePixmap (st->dpy, st->window, w, h, st->xgwa.depth);
 859   XPutImage (st->dpy, st->deltap, st->pgc, dimg, 0, 0, 0, 0, w, h);
 860   XDestroyImage (dimg);
 861   return st->deltap;
 862 }
 863
 864
 865 static unsigned long
 866 tessellimage_draw (Display *dpy, Window window, void *closure)
 867 {
 868   struct state *st = (struct state *) closure;
 869
 870   if (st->img_loader)   /* still loading */
 871     {
 872       st->img_loader = load_image_async_simple (st->img_loader, 0, 0, 0, 0,
 873                                                 &st->geom);
 874       if (! st->img_loader) {  /* just finished */
 875         analyze (st);
 876         st->start_time = double_time();
 877         st->start_time2 = st->start_time;
 878       }
 879       goto DONE;
 880     }
 881
 882   if (!st->img_loader &&
 883       st->start_time + st->duration < double_time()) {
 884     int w = st->xgwa.width;
 885     int h = st->xgwa.height;
 886
 887     /* Analysing a full-resolution image on a Retina display is too slow,
 888        so scale down the source at image-load time. */
 889     if (st->max_resolution > 10)
 890       {
 891         if (w > h && w > st->max_resolution)
 892           h = st->max_resolution * h / w, w = st->max_resolution;
 893         else if (h > st->max_resolution)
 894           w = st->max_resolution * w / h, h = st->max_resolution;
 895       }
 896     /* fprintf(stderr,"%s: loading %d x %d\n", progname, w, h); */
 897
 898     XClearWindow (st->dpy, st->window);
 899     if (st->image) XFreePixmap (dpy, st->image);
 900     st->image = XCreatePixmap (st->dpy, st->window, w, h, st->xgwa.depth);
 901     st->img_loader = load_image_async_simple (0, st->xgwa.screen, st->window,
 902                                               st->image, 0, &st->geom);
 903     goto DONE;
 904   }
 905
 906   tessellate (st);
 907
 908   XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
 909   XClearWindow (st->dpy, st->window);
 910
 911   if (st->output)
 912     XCopyArea (st->dpy,
 913                (st->button_down_p ? get_deltap (st) : st->output),
 914                st->window, st->wgc,
 915                0, 0, st->xgwa.width, st->xgwa.height, 0, 0);
 916   else if (!st->nthreshes)
 917     XCopyArea (st->dpy,
 918                st->image,
 919                st->window, st->wgc,
 920                0, 0, st->xgwa.width, st->xgwa.height, 0, 0);
 921
 922
 923  DONE:
 924   return st->delay;
 925 }
 926
 927 static void
 928 tessellimage_reshape (Display *dpy, Window window, void *closure,
 929                  unsigned int w, unsigned int h)
 930 {
 931   struct state *st = (struct state *) closure;
 932   XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
 933 }
 934
 935 static Bool
 936 tessellimage_event (Display *dpy, Window window, void *closure, XEvent *event)
 937 {
 938   struct state *st = (struct state *) closure;
 939   if (event->xany.type == ButtonPress)
 940     {
 941       st->button_down_p = True;
 942       return True;
 943     }
 944   else if (event->xany.type == ButtonRelease)
 945     {
 946       st->button_down_p = False;
 947       return True;
 948     }
 949   else if (screenhack_event_helper (dpy, window, event))
 950     {
 951       st->start_time = 0;   /* load next image */
 952       return True;
 953     }
 954
 955   return False;
 956 }
 957
 958
 959 static void
 960 tessellimage_free (Display *dpy, Window window, void *closure)
 961 {
 962   struct state *st = (struct state *) closure;
 963   flush_cache (st);
 964   if (st->wgc) XFreeGC (dpy, st->wgc);
 965   if (st->pgc) XFreeGC (dpy, st->pgc);
 966   if (st->image)  XFreePixmap (dpy, st->image);
 967   if (st->output) XFreePixmap (dpy, st->output);
 968   if (st->delta)  XDestroyImage (st->delta);
 969   free (st);
 970 }
 971
 972
 973 \f
 974
 975 static const char *tessellimage_defaults [] = {
 976   ".background:                 black",
 977   ".foreground:                 white",
 978   ".lowrez:                     True",
 979   "*dontClearRoot:              True",
 980   "*fpsSolid:                   true",
 981   "*mode:                       random",
 982   "*delay:                      30000",
 983   "*duration:                   120",
 984   "*duration2:                  0.4",
 985   "*maxDepth:                   30000",
 986   "*maxResolution:              1024",
 987   "*outline:                    True",
 988   "*fillScreen:                 True",
 989   "*cache:                      True",
 990 #ifdef HAVE_MOBILE
 991   "*ignoreRotation:             True",
 992   "*rotateImages:               True",
 993 #endif
 994   0
 995 };
 996
 997 static XrmOptionDescRec tessellimage_options [] = {
 998   { "-delay",           ".delay",               XrmoptionSepArg, 0 },
 999   { "-duration",        ".duration",            XrmoptionSepArg, 0 },
1000   { "-duration2",       ".duration2",           XrmoptionSepArg, 0 },
1001   { "-max-depth",       ".maxDepth",            XrmoptionSepArg, 0 },
1002   { "-max-resolution",  ".maxResolution",       XrmoptionSepArg, 0 },
1003   { "-mode",            ".mode",                XrmoptionSepArg, 0 },
1004   { "-outline",         ".outline",             XrmoptionNoArg, "True"  },
1005   { "-no-outline",      ".outline",             XrmoptionNoArg, "False" },
1006   { "-fill-screen",     ".fillScreen",          XrmoptionNoArg, "True"  },
1007   { "-no-fill-screen",  ".fillScreen",          XrmoptionNoArg, "False" },
1008   { "-cache",           ".cache",               XrmoptionNoArg, "True"  },
1009   { "-no-cache",        ".cache",               XrmoptionNoArg, "False" },
1010   { 0, 0, 0, 0 }
1011 };
1012
1013 XSCREENSAVER_MODULE ("Tessellimage", tessellimage)