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

source code of poppler/splash/SplashScreen.cc