?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
beta-0.89.2
[luatex.git] / source / libs / poppler / poppler-src / splash / SplashXPath.cc
blob27106ee3d148a5d93b0f5f3ebb1a037ed7f881a0
1 //========================================================================
2 //
3 // SplashXPath.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) 2010 Paweł Wiejacha <pawel.wiejacha@gmail.com>
15 // Copyright (C) 2010, 2011 Albert Astals Cid <aacid@kde.org>
16 // Copyright (C) 2013 Thomas Freitag <Thomas.Freitag@alfa.de>
17 //
18 // To see a description of the changes please see the Changelog file that
19 // came with your tarball or type make ChangeLog if you are building from git
20 //
21 //========================================================================
22
23 #include <config.h>
24
25 #ifdef USE_GCC_PRAGMAS
26 #pragma implementation
27 #endif
28
29 #include <stdlib.h>
30 #include <string.h>
31 #include <algorithm>
32 #include "goo/gmem.h"
33 #include "SplashMath.h"
34 #include "SplashPath.h"
35 #include "SplashXPath.h"
36
37 //------------------------------------------------------------------------
38
39 struct SplashXPathPoint {
40 SplashCoord x, y;
41 };
42
43 struct SplashXPathAdjust {
44 int firstPt, lastPt; // range of points
45 GBool vert; // vertical or horizontal hint
46 SplashCoord x0a, x0b, // hint boundaries
47 xma, xmb,
48 x1a, x1b;
49 SplashCoord x0, x1, xm; // adjusted coordinates
50 };
51
52 //------------------------------------------------------------------------
53
54 // Transform a point from user space to device space.
55 inline void SplashXPath::transform(SplashCoord *matrix,
56 SplashCoord xi, SplashCoord yi,
57 SplashCoord *xo, SplashCoord *yo) {
58 // [ m[0] m[1] 0 ]
59 // [xo yo 1] = [xi yi 1] * [ m[2] m[3] 0 ]
60 // [ m[4] m[5] 1 ]
61 *xo = xi * matrix[0] + yi * matrix[2] + matrix[4];
62 *yo = xi * matrix[1] + yi * matrix[3] + matrix[5];
63 }
64
65 //------------------------------------------------------------------------
66 // SplashXPath
67 //------------------------------------------------------------------------
68
69 SplashXPath::SplashXPath(SplashPath *path, SplashCoord *matrix,
70 SplashCoord flatness, GBool closeSubpaths,
71 GBool adjustLines, int linePosI) {
72 SplashPathHint *hint;
73 SplashXPathPoint *pts;
74 SplashXPathAdjust *adjusts, *adjust;
75 SplashCoord x0, y0, x1, y1, x2, y2, x3, y3, xsp, ysp;
76 SplashCoord adj0, adj1;
77 int curSubpath, i, j;
78
79 // transform the points
80 pts = (SplashXPathPoint *)gmallocn(path->length, sizeof(SplashXPathPoint));
81 for (i = 0; i < path->length; ++i) {
82 transform(matrix, path->pts[i].x, path->pts[i].y, &pts[i].x, &pts[i].y);
83 }
84
85 // set up the stroke adjustment hints
86 if (path->hints) {
87 adjusts = (SplashXPathAdjust *)gmallocn(path->hintsLength,
88 sizeof(SplashXPathAdjust));
89 for (i = 0; i < path->hintsLength; ++i) {
90 hint = &path->hints[i];
91 if (hint->ctrl0 + 1 >= path->length || hint->ctrl1 + 1 >= path->length) {
92 gfree(adjusts);
93 adjusts = NULL;
94 break;
95 }
96 x0 = pts[hint->ctrl0 ].x; y0 = pts[hint->ctrl0 ].y;
97 x1 = pts[hint->ctrl0 + 1].x; y1 = pts[hint->ctrl0 + 1].y;
98 x2 = pts[hint->ctrl1 ].x; y2 = pts[hint->ctrl1 ].y;
99 x3 = pts[hint->ctrl1 + 1].x; y3 = pts[hint->ctrl1 + 1].y;
100 if (x0 == x1 && x2 == x3) {
101 adjusts[i].vert = gTrue;
102 adj0 = x0;
103 adj1 = x2;
104 } else if (y0 == y1 && y2 == y3) {
105 adjusts[i].vert = gFalse;
106 adj0 = y0;
107 adj1 = y2;
108 } else {
109 gfree(adjusts);
110 adjusts = NULL;
111 break;
112 }
113 if (adj0 > adj1) {
114 x0 = adj0;
115 adj0 = adj1;
116 adj1 = x0;
117 }
118 adjusts[i].x0a = adj0 - 0.01;
119 adjusts[i].x0b = adj0 + 0.01;
120 adjusts[i].xma = (SplashCoord)0.5 * (adj0 + adj1) - 0.01;
121 adjusts[i].xmb = (SplashCoord)0.5 * (adj0 + adj1) + 0.01;
122 adjusts[i].x1a = adj1 - 0.01;
123 adjusts[i].x1b = adj1 + 0.01;
124 // rounding both edge coordinates can result in lines of
125 // different widths (e.g., adj=10.1, adj1=11.3 --> x0=10, x1=11;
126 // adj0=10.4, adj1=11.6 --> x0=10, x1=12), but it has the
127 // benefit of making adjacent strokes/fills line up without any
128 // gaps between them
129 x0 = splashRound(adj0);
130 x1 = splashRound(adj1);
131 if (x1 == x0) {
132 if (adjustLines) {
133 // the adjustment moves thin lines (clip rectangle with
134 // empty width or height) out of clip area, here we need
135 // a special adjustment:
136 x0 = linePosI;
137 x1 = x0 + 1;
138 } else {
139 x1 = x1 + 1;
140 }
141 }
142 adjusts[i].x0 = (SplashCoord)x0;
143 adjusts[i].x1 = (SplashCoord)x1 - 0.01;
144 adjusts[i].xm = (SplashCoord)0.5 * (adjusts[i].x0 + adjusts[i].x1);
145 adjusts[i].firstPt = hint->firstPt;
146 adjusts[i].lastPt = hint->lastPt;
147 }
148
149 } else {
150 adjusts = NULL;
151 }
152
153 // perform stroke adjustment
154 if (adjusts) {
155 for (i = 0, adjust = adjusts; i < path->hintsLength; ++i, ++adjust) {
156 for (j = adjust->firstPt; j <= adjust->lastPt; ++j) {
157 strokeAdjust(adjust, &pts[j].x, &pts[j].y);
158 }
159 }
160 gfree(adjusts);
161 }
162
163 segs = NULL;
164 length = size = 0;
165
166 x0 = y0 = xsp = ysp = 0; // make gcc happy
167 adj0 = adj1 = 0; // make gcc happy
168 curSubpath = 0;
169 i = 0;
170 while (i < path->length) {
171
172 // first point in subpath - skip it
173 if (path->flags[i] & splashPathFirst) {
174 x0 = pts[i].x;
175 y0 = pts[i].y;
176 xsp = x0;
177 ysp = y0;
178 curSubpath = i;
179 ++i;
180
181 } else {
182
183 // curve segment
184 if (path->flags[i] & splashPathCurve) {
185 x1 = pts[i].x;
186 y1 = pts[i].y;
187 x2 = pts[i+1].x;
188 y2 = pts[i+1].y;
189 x3 = pts[i+2].x;
190 y3 = pts[i+2].y;
191 addCurve(x0, y0, x1, y1, x2, y2, x3, y3,
192 flatness,
193 (path->flags[i-1] & splashPathFirst),
194 (path->flags[i+2] & splashPathLast),
195 !closeSubpaths &&
196 (path->flags[i-1] & splashPathFirst) &&
197 !(path->flags[i-1] & splashPathClosed),
198 !closeSubpaths &&
199 (path->flags[i+2] & splashPathLast) &&
200 !(path->flags[i+2] & splashPathClosed));
201 x0 = x3;
202 y0 = y3;
203 i += 3;
204
205 // line segment
206 } else {
207 x1 = pts[i].x;
208 y1 = pts[i].y;
209 addSegment(x0, y0, x1, y1);
210 x0 = x1;
211 y0 = y1;
212 ++i;
213 }
214
215 // close a subpath
216 if (closeSubpaths &&
217 (path->flags[i-1] & splashPathLast) &&
218 (pts[i-1].x != pts[curSubpath].x ||
219 pts[i-1].y != pts[curSubpath].y)) {
220 addSegment(x0, y0, xsp, ysp);
221 }
222 }
223 }
224
225 gfree(pts);
226 }
227
228 // Apply the stroke adjust hints to point <pt>: (*<xp>, *<yp>).
229 void SplashXPath::strokeAdjust(SplashXPathAdjust *adjust,
230 SplashCoord *xp, SplashCoord *yp) {
231 SplashCoord x, y;
232
233 if (adjust->vert) {
234 x = *xp;
235 if (x > adjust->x0a && x < adjust->x0b) {
236 *xp = adjust->x0;
237 } else if (x > adjust->xma && x < adjust->xmb) {
238 *xp = adjust->xm;
239 } else if (x > adjust->x1a && x < adjust->x1b) {
240 *xp = adjust->x1;
241 }
242 } else {
243 y = *yp;
244 if (y > adjust->x0a && y < adjust->x0b) {
245 *yp = adjust->x0;
246 } else if (y > adjust->xma && y < adjust->xmb) {
247 *yp = adjust->xm;
248 } else if (y > adjust->x1a && y < adjust->x1b) {
249 *yp = adjust->x1;
250 }
251 }
252 }
253
254 SplashXPath::SplashXPath(SplashXPath *xPath) {
255 length = xPath->length;
256 size = xPath->size;
257 segs = (SplashXPathSeg *)gmallocn(size, sizeof(SplashXPathSeg));
258 memcpy(segs, xPath->segs, length * sizeof(SplashXPathSeg));
259 }
260
261 SplashXPath::~SplashXPath() {
262 gfree(segs);
263 }
264
265 // Add space for <nSegs> more segments
266 void SplashXPath::grow(int nSegs) {
267 if (length + nSegs > size) {
268 if (size == 0) {
269 size = 32;
270 }
271 while (size < length + nSegs) {
272 size *= 2;
273 }
274 segs = (SplashXPathSeg *)greallocn(segs, size, sizeof(SplashXPathSeg));
275 }
276 }
277
278 void SplashXPath::addCurve(SplashCoord x0, SplashCoord y0,
279 SplashCoord x1, SplashCoord y1,
280 SplashCoord x2, SplashCoord y2,
281 SplashCoord x3, SplashCoord y3,
282 SplashCoord flatness,
283 GBool first, GBool last, GBool end0, GBool end1) {
284 SplashCoord *cx = new SplashCoord[(splashMaxCurveSplits + 1) * 3];
285 SplashCoord *cy = new SplashCoord[(splashMaxCurveSplits + 1) * 3];
286 int *cNext = new int[splashMaxCurveSplits + 1];
287 SplashCoord xl0, xl1, xl2, xr0, xr1, xr2, xr3, xx1, xx2, xh;
288 SplashCoord yl0, yl1, yl2, yr0, yr1, yr2, yr3, yy1, yy2, yh;
289 SplashCoord dx, dy, mx, my, d1, d2, flatness2;
290 int p1, p2, p3;
291
292 #if USE_FIXEDPOINT
293 flatness2 = flatness;
294 #else
295 flatness2 = flatness * flatness;
296 #endif
297
298 // initial segment
299 p1 = 0;
300 p2 = splashMaxCurveSplits;
301
302 *(cx + p1 * 3 + 0) = x0;
303 *(cx + p1 * 3 + 1) = x1;
304 *(cx + p1 * 3 + 2) = x2;
305 *(cx + p2 * 3 + 0) = x3;
306
307 *(cy + p1 * 3 + 0) = y0;
308 *(cy + p1 * 3 + 1) = y1;
309 *(cy + p1 * 3 + 2) = y2;
310 *(cy + p2 * 3 + 0) = y3;
311
312 *(cNext + p1) = p2;
313
314 while (p1 < splashMaxCurveSplits) {
315
316 // get the next segment
317 xl0 = *(cx + p1 * 3 + 0);
318 xx1 = *(cx + p1 * 3 + 1);
319 xx2 = *(cx + p1 * 3 + 2);
320
321 yl0 = *(cy + p1 * 3 + 0);
322 yy1 = *(cy + p1 * 3 + 1);
323 yy2 = *(cy + p1 * 3 + 2);
324
325 p2 = *(cNext + p1);
326
327 xr3 = *(cx + p2 * 3 + 0);
328 yr3 = *(cy + p2 * 3 + 0);
329
330 // compute the distances from the control points to the
331 // midpoint of the straight line (this is a bit of a hack, but
332 // it's much faster than computing the actual distances to the
333 // line)
334 mx = (xl0 + xr3) * 0.5;
335 my = (yl0 + yr3) * 0.5;
336 #if USE_FIXEDPOINT
337 d1 = splashDist(xx1, yy1, mx, my);
338 d2 = splashDist(xx2, yy2, mx, my);
339 #else
340 dx = xx1 - mx;
341 dy = yy1 - my;
342 d1 = dx*dx + dy*dy;
343 dx = xx2 - mx;
344 dy = yy2 - my;
345 d2 = dx*dx + dy*dy;
346 #endif
347
348 // if the curve is flat enough, or no more subdivisions are
349 // allowed, add the straight line segment
350 if (p2 - p1 == 1 || (d1 <= flatness2 && d2 <= flatness2)) {
351 addSegment(xl0, yl0, xr3, yr3);
352 p1 = p2;
353
354 // otherwise, subdivide the curve
355 } else {
356 xl1 = (xl0 + xx1) * 0.5;
357 yl1 = (yl0 + yy1) * 0.5;
358 xh = (xx1 + xx2) * 0.5;
359 yh = (yy1 + yy2) * 0.5;
360 xl2 = (xl1 + xh) * 0.5;
361 yl2 = (yl1 + yh) * 0.5;
362 xr2 = (xx2 + xr3) * 0.5;
363 yr2 = (yy2 + yr3) * 0.5;
364 xr1 = (xh + xr2) * 0.5;
365 yr1 = (yh + yr2) * 0.5;
366 xr0 = (xl2 + xr1) * 0.5;
367 yr0 = (yl2 + yr1) * 0.5;
368 // add the new subdivision points
369 p3 = (p1 + p2) / 2;
370
371 *(cx + p1 * 3 + 1) = xl1;
372 *(cx + p1 * 3 + 2) = xl2;
373
374 *(cy + p1 * 3 + 1) = yl1;
375 *(cy + p1 * 3 + 2) = yl2;
376
377 *(cNext + p1) = p3;
378
379 *(cx + p3 * 3 + 0) = xr0;
380 *(cx + p3 * 3 + 1) = xr1;
381 *(cx + p3 * 3 + 2) = xr2;
382
383 *(cy + p3 * 3 + 0) = yr0;
384 *(cy + p3 * 3 + 1) = yr1;
385 *(cy + p3 * 3 + 2) = yr2;
386
387 *(cNext + p3) = p2;
388 }
389 }
390
391 delete [] cx;
392 delete [] cy;
393 delete [] cNext;
394 }
395
396 void SplashXPath::addSegment(SplashCoord x0, SplashCoord y0,
397 SplashCoord x1, SplashCoord y1) {
398 grow(1);
399 segs[length].x0 = x0;
400 segs[length].y0 = y0;
401 segs[length].x1 = x1;
402 segs[length].y1 = y1;
403 segs[length].flags = 0;
404 if (y1 == y0) {
405 segs[length].dxdy = segs[length].dydx = 0;
406 segs[length].flags |= splashXPathHoriz;
407 if (x1 == x0) {
408 segs[length].flags |= splashXPathVert;
409 }
410 } else if (x1 == x0) {
411 segs[length].dxdy = segs[length].dydx = 0;
412 segs[length].flags |= splashXPathVert;
413 } else {
414 #if USE_FIXEDPOINT
415 if (FixedPoint::divCheck(x1 - x0, y1 - y0, &segs[length].dxdy)) {
416 segs[length].dydx = (SplashCoord)1 / segs[length].dxdy;
417 } else {
418 segs[length].dxdy = segs[length].dydx = 0;
419 if (splashAbs(x1 - x0) > splashAbs(y1 - y0)) {
420 segs[length].flags |= splashXPathHoriz;
421 } else {
422 segs[length].flags |= splashXPathVert;
423 }
424 }
425 #else
426 segs[length].dxdy = (x1 - x0) / (y1 - y0);
427 segs[length].dydx = (SplashCoord)1 / segs[length].dxdy;
428 #endif
429 }
430 if (y0 > y1) {
431 segs[length].flags |= splashXPathFlip;
432 }
433 ++length;
434 }
435
436 struct cmpXPathSegsFunctor {
437 bool operator()(const SplashXPathSeg &seg0, const SplashXPathSeg &seg1) {
438 SplashCoord x0, y0, x1, y1;
439
440 if (seg0.flags & splashXPathFlip) {
441 x0 = seg0.x1;
442 y0 = seg0.y1;
443 } else {
444 x0 = seg0.x0;
445 y0 = seg0.y0;
446 }
447 if (seg1.flags & splashXPathFlip) {
448 x1 = seg1.x1;
449 y1 = seg1.y1;
450 } else {
451 x1 = seg1.x0;
452 y1 = seg1.y0;
453 }
454 return (y0 != y1) ? (y0 < y1) : (x0 < x1);
455 }
456 };
457
458 void SplashXPath::aaScale() {
459 SplashXPathSeg *seg;
460 int i;
461
462 for (i = 0, seg = segs; i < length; ++i, ++seg) {
463 seg->x0 *= splashAASize;
464 seg->y0 *= splashAASize;
465 seg->x1 *= splashAASize;
466 seg->y1 *= splashAASize;
467 }
468 }
469
470 void SplashXPath::sort() {
471 std::sort(segs, segs + length, cmpXPathSegsFunctor());
472 }
LuaTeX git mirror