source: trunk/poppler/mypoppler/splash/SplashScreen.cc @ 250

Last change on this file since 250 was 250, checked in by Eugene Romanenko, 13 years ago

PDF plugin: poppler library updated to version 0.8.3

File size: 9.4 KB
Line 
1//========================================================================
2//
3// SplashScreen.cc
4//
5//========================================================================
6
7#include <config.h>
8
9#ifdef USE_GCC_PRAGMAS
10#pragma implementation
11#endif
12
13#include <stdlib.h>
14#include <string.h>
15#include "goo/gmem.h"
16#include "SplashMath.h"
17#include "SplashScreen.h"
18
19static SplashScreenParams defaultParams = {
20  splashScreenDispersed,        // type
21  2,                            // size
22  2,                            // dotRadius
23  1.0,                          // gamma
24  0.0,                          // blackThreshold
25  1.0                           // whiteThreshold
26};
27
28//------------------------------------------------------------------------
29
30struct SplashScreenPoint {
31  int x, y;
32  int dist;
33};
34
35static int cmpDistances(const void *p0, const void *p1) {
36  return ((SplashScreenPoint *)p0)->dist - ((SplashScreenPoint *)p1)->dist;
37}
38
39//------------------------------------------------------------------------
40// SplashScreen
41//------------------------------------------------------------------------
42
43// If <clustered> is true, this generates a 45 degree screen using a
44// circular dot spot function.  DPI = resolution / ((size / 2) *
45// sqrt(2)).  If <clustered> is false, this generates an optimal
46// threshold matrix using recursive tesselation.  Gamma correction
47// (gamma = 1 / 1.33) is also computed here.
48SplashScreen::SplashScreen(SplashScreenParams *params) {
49  Guchar u, black, white;
50  int i;
51
52  if (!params) {
53    params = &defaultParams;
54  }
55
56  switch (params->type) {
57
58  case splashScreenDispersed:
59    // size must be a power of 2
60    for (size = 1; size < params->size; size <<= 1) ;
61    mat = (Guchar *)gmallocn(size * size, sizeof(Guchar));
62    buildDispersedMatrix(size/2, size/2, 1, size/2, 1);
63    break;
64
65  case splashScreenClustered:
66    // size must be even
67    size = (params->size >> 1) << 1;
68    if (size < 2) {
69      size = 2;
70    }
71    mat = (Guchar *)gmallocn(size * size, sizeof(Guchar));
72    buildClusteredMatrix();
73    break;
74
75  case splashScreenStochasticClustered:
76    // size must be at least 2*r
77    if (params->size < 2 * params->dotRadius) {
78      size = 2 * params->dotRadius;
79    } else {
80      size = params->size;
81    }
82    mat = (Guchar *)gmallocn(size * size, sizeof(Guchar));
83    buildSCDMatrix(params->dotRadius);
84    break;
85  }
86
87  // do gamma correction and compute minVal/maxVal
88  minVal = 255;
89  maxVal = 0;
90  black = splashRound((SplashCoord)255.0 * params->blackThreshold);
91  if (black < 1) {
92    black = 1;
93  }
94  int whiteAux = splashRound((SplashCoord)255.0 * params->whiteThreshold);
95  if (whiteAux > 255) {
96    white = 255;
97  } else {
98    white = whiteAux;
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
117void 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
134void 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.
207int 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.
223void 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
351SplashScreen::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
359SplashScreen::~SplashScreen() {
360  gfree(mat);
361}
362
363int 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
381GBool SplashScreen::isStatic(Guchar value) {
382  return value < minVal || value >= maxVal;
383}
Note: See TracBrowser for help on using the repository browser.