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

source code of poppler/splash/SplashXPath.cc