← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to tests/poppler/splash/SplashScreen.cc

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

Lines of Context:
tests/poppler/splash/SplashScreen.cc
 
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
 
 
33
static 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
 
 
44
struct SplashScreenPoint {
 
45
  int x, y;
 
46
  int dist;
 
47
};
 
48
 
 
49
static 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.
 
62
SplashScreen::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
 
 
75
void 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
 
 
143
void 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
 
 
160
void 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.
 
233
int 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.
 
249
void 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
 
 
377
SplashScreen::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
 
 
386
SplashScreen::~SplashScreen() {
 
387
  gfree(mat);
 
388
}
 
389
 
 
390
int 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
 
 
410
GBool SplashScreen::isStatic(Guchar value) {
 
411
  if (mat == NULL) createMatrix();
 
412
  
 
413
  return value < minVal || value >= maxVal;
 
414
}