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

Last change on this file since 461 was 461, checked in by Silvan Scherrer, 11 years ago

poppler update to 0.14.2

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