arospdf/splash/SplashScreen.cc

   1 //========================================================================
   2 //
   3 // SplashScreen.cc
   4 //
   5 //========================================================================
   6
   7 #include <aconf.h>
   8
   9 #ifdef USE_GCC_PRAGMAS
  10 #pragma implementation
  11 #endif
  12
  13 #include <stdlib.h>
  14 #include <string.h>
  15 #include "gmem.h"
  16 #include "SplashMath.h"
  17 #include "SplashScreen.h"
  18
  19 //------------------------------------------------------------------------
  20
  21 static SplashScreenParams defaultParams = {
  22   splashScreenDispersed,        // type
  23   2,                            // size
  24   2,                            // dotRadius
  25   1.0,                          // gamma
  26   0.0,                          // blackThreshold
  27   1.0                           // whiteThreshold
  28 };
  29
  30 //------------------------------------------------------------------------
  31
  32 struct SplashScreenPoint {
  33   int x, y;
  34   int dist;
  35 };
  36
  37 static int cmpDistances(const void *p0, const void *p1) {
  38   return ((SplashScreenPoint *)p0)->dist - ((SplashScreenPoint *)p1)->dist;
  39 }
  40
  41 //------------------------------------------------------------------------
  42 // SplashScreen
  43 //------------------------------------------------------------------------
  44
  45 // If <clustered> is true, this generates a 45 degree screen using a
  46 // circular dot spot function.  DPI = resolution / ((size / 2) *
  47 // sqrt(2)).  If <clustered> is false, this generates an optimal
  48 // threshold matrix using recursive tesselation.  Gamma correction
  49 // (gamma = 1 / 1.33) is also computed here.
  50 SplashScreen::SplashScreen(SplashScreenParams *params) {
  51   Guchar u, black, white;
  52   int i;
  53
  54   if (!params) {
  55     params = &defaultParams;
  56   }
  57
  58   switch (params->type) {
  59
  60   case splashScreenDispersed:
  61     // size must be a power of 2
  62     for (size = 1; size < params->size; size <<= 1) ;
  63     mat = (Guchar *)gmallocn(size * size, sizeof(Guchar));
  64     buildDispersedMatrix(size/2, size/2, 1, size/2, 1);
  65     break;
  66
  67   case splashScreenClustered:
  68     // size must be even
  69     size = (params->size >> 1) << 1;
  70     if (size < 2) {
  71       size = 2;
  72     }
  73     mat = (Guchar *)gmallocn(size * size, sizeof(Guchar));
  74     buildClusteredMatrix();
  75     break;
  76
  77   case splashScreenStochasticClustered:
  78     // size must be at least 2*r
  79     if (params->size < 2 * params->dotRadius) {
  80       size = 2 * params->dotRadius;
  81     } else {
  82       size = params->size;
  83     }
  84     mat = (Guchar *)gmallocn(size * size, sizeof(Guchar));
  85     buildSCDMatrix(params->dotRadius);
  86     break;
  87   }
  88
  89   // do gamma correction and compute minVal/maxVal
  90   minVal = 255;
  91   maxVal = 0;
  92   black = splashRound((SplashCoord)255.0 * params->blackThreshold);
  93   if (black < 1) {
  94     black = 1;
  95   }
  96   white = splashRound((SplashCoord)255.0 * params->whiteThreshold);
  97   //if (white > 255) { -- this never happens
  98   //  white = 255;
  99   //}
 100   for (i = 0; i < size * size; ++i) {
 101     u = splashRound((SplashCoord)255.0 *
 102                     splashPow((SplashCoord)mat[i] / 255.0, params->gamma));
 103     if (u < black) {
 104       u = black;
 105     } else if (u >= white) {
 106       u = white;
 107     }
 108     mat[i] = u;
 109     if (u < minVal) {
 110       minVal = u;
 111     } else if (u > maxVal) {
 112       maxVal = u;
 113     }
 114   }
 115 }
 116
 117 void SplashScreen::buildDispersedMatrix(int i, int j, int val,
 118                                         int delta, int offset) {
 119   if (delta == 0) {
 120     // map values in [1, size^2] --> [1, 255]
 121     mat[i * size + j] = 1 + (254 * (val - 1)) / (size * size - 1);
 122   } else {
 123     buildDispersedMatrix(i, j,
 124                          val, delta / 2, 4*offset);
 125     buildDispersedMatrix((i + delta) % size, (j + delta) % size,
 126                          val + offset, delta / 2, 4*offset);
 127     buildDispersedMatrix((i + delta) % size, j,
 128                          val + 2*offset, delta / 2, 4*offset);
 129     buildDispersedMatrix((i + 2*delta) % size, (j + delta) % size,
 130                          val + 3*offset, delta / 2, 4*offset);
 131   }
 132 }
 133
 134 void SplashScreen::buildClusteredMatrix() {
 135   SplashCoord *dist;
 136   SplashCoord u, v, d;
 137   Guchar val;
 138   int size2, x, y, x1, y1, i;
 139
 140   size2 = size >> 1;
 141
 142   // initialize the threshold matrix
 143   for (y = 0; y < size; ++y) {
 144     for (x = 0; x < size; ++x) {
 145       mat[y * size + x] = 0;
 146     }
 147   }
 148
 149   // build the distance matrix
 150   dist = (SplashCoord *)gmallocn(size * size2, sizeof(SplashCoord));
 151   for (y = 0; y < size2; ++y) {
 152     for (x = 0; x < size2; ++x) {
 153       if (x + y < size2 - 1) {
 154         u = (SplashCoord)x + 0.5 - 0;
 155         v = (SplashCoord)y + 0.5 - 0;
 156       } else {
 157         u = (SplashCoord)x + 0.5 - (SplashCoord)size2;
 158         v = (SplashCoord)y + 0.5 - (SplashCoord)size2;
 159       }
 160       dist[y * size2 + x] = u*u + v*v;
 161     }
 162   }
 163   for (y = 0; y < size2; ++y) {
 164     for (x = 0; x < size2; ++x) {
 165       if (x < y) {
 166         u = (SplashCoord)x + 0.5 - 0;
 167         v = (SplashCoord)y + 0.5 - (SplashCoord)size2;
 168       } else {
 169         u = (SplashCoord)x + 0.5 - (SplashCoord)size2;
 170         v = (SplashCoord)y + 0.5 - 0;
 171       }
 172       dist[(size2 + y) * size2 + x] = u*u + v*v;
 173     }
 174   }
 175
 176   // build the threshold matrix
 177   minVal = 1;
 178   maxVal = 0;
 179   x1 = y1 = 0; // make gcc happy
 180   for (i = 0; i < size * size2; ++i) {
 181     d = -1;
 182     for (y = 0; y < size; ++y) {
 183       for (x = 0; x < size2; ++x) {
 184         if (mat[y * size + x] == 0 &&
 185             dist[y * size2 + x] > d) {
 186           x1 = x;
 187           y1 = y;
 188           d = dist[y1 * size2 + x1];
 189         }
 190       }
 191     }
 192     // map values in [0, 2*size*size2-1] --> [1, 255]
 193     val = 1 + (254 * (2*i)) / (2*size*size2 - 1);
 194     mat[y1 * size + x1] = val;
 195     val = 1 + (254 * (2*i+1)) / (2*size*size2 - 1);
 196     if (y1 < size2) {
 197       mat[(y1 + size2) * size + x1 + size2] = val;
 198     } else {
 199       mat[(y1 - size2) * size + x1 + size2] = val;
 200     }
 201   }
 202
 203   gfree(dist);
 204 }
 205
 206 // Compute the distance between two points on a toroid.
 207 int SplashScreen::distance(int x0, int y0, int x1, int y1) {
 208   int dx0, dx1, dx, dy0, dy1, dy;
 209
 210   dx0 = abs(x0 - x1);
 211   dx1 = size - dx0;
 212   dx = dx0 < dx1 ? dx0 : dx1;
 213   dy0 = abs(y0 - y1);
 214   dy1 = size - dy0;
 215   dy = dy0 < dy1 ? dy0 : dy1;
 216   return dx * dx + dy * dy;
 217 }
 218
 219 // Algorithm taken from:
 220 // Victor Ostromoukhov and Roger D. Hersch, "Stochastic Clustered-Dot
 221 // Dithering" in Color Imaging: Device-Independent Color, Color
 222 // Hardcopy, and Graphic Arts IV, SPIE Vol. 3648, pp. 496-505, 1999.
 223 void SplashScreen::buildSCDMatrix(int r) {
 224   SplashScreenPoint *dots, *pts;
 225   int dotsLen, dotsSize;
 226   char *tmpl;
 227   char *grid;
 228   int *region, *dist;
 229   int x, y, xx, yy, x0, x1, y0, y1, i, j, d, iMin, dMin, n;
 230
 231   //~ this should probably happen somewhere else
 232   srand(123);
 233
 234   // generate the random space-filling curve
 235   pts = (SplashScreenPoint *)gmallocn(size * size, sizeof(SplashScreenPoint));
 236   i = 0;
 237   for (y = 0; y < size; ++y) {
 238     for (x = 0; x < size; ++x) {
 239       pts[i].x = x;
 240       pts[i].y = y;
 241       ++i;
 242     }
 243   }
 244   for (i = 0; i < size * size; ++i) {
 245     j = i + (int)((double)(size * size - i) *
 246                   (double)rand() / ((double)RAND_MAX + 1.0));
 247     x = pts[i].x;
 248     y = pts[i].y;
 249     pts[i].x = pts[j].x;
 250     pts[i].y = pts[j].y;
 251     pts[j].x = x;
 252     pts[j].y = y;
 253   }
 254
 255   // construct the circle template
 256   tmpl = (char *)gmallocn((r+1)*(r+1), sizeof(char));
 257   for (y = 0; y <= r; ++y) {
 258     for (x = 0; x <= r; ++x) {
 259       tmpl[y*(r+1) + x] = (x * y <= r * r) ? 1 : 0;
 260     }
 261   }
 262
 263   // mark all grid cells as free
 264   grid = (char *)gmallocn(size * size, sizeof(char));
 265   for (y = 0; y < size; ++y) {
 266     for (x = 0; x < size; ++x) {
 267       grid[y*size + x] = 0;
 268     }
 269   }
 270
 271   // walk the space-filling curve, adding dots
 272   dotsLen = 0;
 273   dotsSize = 32;
 274   dots = (SplashScreenPoint *)gmallocn(dotsSize, sizeof(SplashScreenPoint));
 275   for (i = 0; i < size * size; ++i) {
 276     x = pts[i].x;
 277     y = pts[i].y;
 278     if (!grid[y*size + x]) {
 279       if (dotsLen == dotsSize) {
 280         dotsSize *= 2;
 281         dots = (SplashScreenPoint *)greallocn(dots, dotsSize,
 282                                               sizeof(SplashScreenPoint));
 283       }
 284       dots[dotsLen++] = pts[i];
 285       for (yy = 0; yy <= r; ++yy) {
 286         y0 = (y + yy) % size;
 287         y1 = (y - yy + size) % size;
 288         for (xx = 0; xx <= r; ++xx) {
 289           if (tmpl[yy*(r+1) + xx]) {
 290             x0 = (x + xx) % size;
 291             x1 = (x - xx + size) % size;
 292             grid[y0*size + x0] = 1;
 293             grid[y0*size + x1] = 1;
 294             grid[y1*size + x0] = 1;
 295             grid[y1*size + x1] = 1;
 296           }
 297         }
 298       }
 299     }
 300   }
 301
 302   gfree(tmpl);
 303   gfree(grid);
 304
 305   // assign each cell to a dot, compute distance to center of dot
 306   region = (int *)gmallocn(size * size, sizeof(int));
 307   dist = (int *)gmallocn(size * size, sizeof(int));
 308   for (y = 0; y < size; ++y) {
 309     for (x = 0; x < size; ++x) {
 310       iMin = 0;
 311       dMin = distance(dots[0].x, dots[0].y, x, y);
 312       for (i = 1; i < dotsLen; ++i) {
 313         d = distance(dots[i].x, dots[i].y, x, y);
 314         if (d < dMin) {
 315           iMin = i;
 316           dMin = d;
 317         }
 318       }
 319       region[y*size + x] = iMin;
 320       dist[y*size + x] = dMin;
 321     }
 322   }
 323
 324   // compute threshold values
 325   for (i = 0; i < dotsLen; ++i) {
 326     n = 0;
 327     for (y = 0; y < size; ++y) {
 328       for (x = 0; x < size; ++x) {
 329         if (region[y*size + x] == i) {
 330           pts[n].x = x;
 331           pts[n].y = y;
 332           pts[n].dist = distance(dots[i].x, dots[i].y, x, y);
 333           ++n;
 334         }
 335       }
 336     }
 337     qsort(pts, n, sizeof(SplashScreenPoint), &cmpDistances);
 338     for (j = 0; j < n; ++j) {
 339       // map values in [0 .. n-1] --> [255 .. 1]
 340       mat[pts[j].y * size + pts[j].x] = 255 - (254 * j) / (n - 1);
 341     }
 342   }
 343
 344   gfree(pts);
 345   gfree(region);
 346   gfree(dist);
 347
 348   gfree(dots);
 349 }
 350
 351 SplashScreen::SplashScreen(SplashScreen *screen) {
 352   size = screen->size;
 353   mat = (Guchar *)gmallocn(size * size, sizeof(Guchar));
 354   memcpy(mat, screen->mat, size * size * sizeof(Guchar));
 355   minVal = screen->minVal;
 356   maxVal = screen->maxVal;
 357 }
 358
 359 SplashScreen::~SplashScreen() {
 360   gfree(mat);
 361 }
 362
 363 int SplashScreen::test(int x, int y, Guchar value) {
 364   int xx, yy;
 365
 366   if (value < minVal) {
 367     return 0;
 368   }
 369   if (value >= maxVal) {
 370     return 1;
 371   }
 372   if ((xx = x % size) < 0) {
 373     xx = -xx;
 374   }
 375   if ((yy = y % size) < 0) {
 376     yy = -yy;
 377   }
 378   return value < mat[yy * size + xx] ? 0 : 1;
 379 }
 380
 381 GBool SplashScreen::isStatic(Guchar value) {
 382   return value < minVal || value >= maxVal;
 383 }