w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

SplashXPath.cc
Go to the documentation of this file.
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 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 
37 struct SplashXPathPoint
38 {
39  SplashCoord x, y;
40 };
41 
42 struct 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.
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 
67 SplashXPath::SplashXPath(SplashPath *path, SplashCoord *matrix, SplashCoord flatness, bool closeSubpaths, bool adjustLines, int linePosI)
68 {
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(path->length, sizeof(SplashXPathPoint));
78  for (i = 0; i < path->length; ++i) {
79  transform(matrix, path->pts[i].x, path->pts[i].y, &pts[i].x, &pts[i].y);
80  }
81 
82  // set up the stroke adjustment hints
83  if (path->hints) {
84  adjusts = (SplashXPathAdjust *)gmallocn_checkoverflow(path->hintsLength, 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(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(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(adj0);
131  x1 = splashRound(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, &pts[j].x, &pts[j].y);
160  }
161  }
162  gfree(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, (path->flags[i - 1] & splashPathFirst), (path->flags[i + 2] & splashPathLast),
194  !closeSubpaths && (path->flags[i - 1] & splashPathFirst) && !(path->flags[i - 1] & splashPathClosed), !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, xsp, ysp);
212  }
213  }
214  }
215 
216  gfree(pts);
217 }
218 
219 // Apply the stroke adjust hints to point <pt>: (*<xp>, *<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 
246 {
247  length = xPath->length;
248  size = xPath->size;
250  memcpy(segs, xPath->segs, length * sizeof(SplashXPathSeg));
251 }
252 
254 {
255  gfree(segs);
256 }
257 
258 // Add space for <nSegs> more segments
259 void SplashXPath::grow(int nSegs)
260 {
261  if (length + nSegs > size) {
262  if (size == 0) {
263  size = 32;
264  }
265  while (size < length + nSegs) {
266  size *= 2;
267  }
269  if (unlikely(!segs)) {
270  length = 0;
271  size = 0;
272  }
273  }
274 }
275 
277 {
280  int *cNext = new int[splashMaxCurveSplits + 1];
281  SplashCoord xl0, xl1, xl2, xr0, xr1, xr2, xr3, xx1, xx2, xh;
282  SplashCoord yl0, yl1, yl2, yr0, yr1, yr2, yr3, yy1, yy2, yh;
283  SplashCoord dx, dy, mx, my, d1, d2, flatness2;
284  int p1, p2, p3;
285 
286  flatness2 = flatness * flatness;
287 
288  // initial segment
289  p1 = 0;
291 
292  *(cx + p1 * 3 + 0) = x0;
293  *(cx + p1 * 3 + 1) = x1;
294  *(cx + p1 * 3 + 2) = x2;
295  *(cx + p2 * 3 + 0) = x3;
296 
297  *(cy + p1 * 3 + 0) = y0;
298  *(cy + p1 * 3 + 1) = y1;
299  *(cy + p1 * 3 + 2) = y2;
300  *(cy + p2 * 3 + 0) = y3;
301 
302  *(cNext + p1) = p2;
303 
304  while (p1 < splashMaxCurveSplits) {
305 
306  // get the next segment
307  xl0 = *(cx + p1 * 3 + 0);
308  xx1 = *(cx + p1 * 3 + 1);
309  xx2 = *(cx + p1 * 3 + 2);
310 
311  yl0 = *(cy + p1 * 3 + 0);
312  yy1 = *(cy + p1 * 3 + 1);
313  yy2 = *(cy + p1 * 3 + 2);
314 
315  p2 = *(cNext + p1);
316 
317  xr3 = *(cx + p2 * 3 + 0);
318  yr3 = *(cy + p2 * 3 + 0);
319 
320  // compute the distances from the control points to the
321  // midpoint of the straight line (this is a bit of a hack, but
322  // it's much faster than computing the actual distances to the
323  // line)
324  mx = (xl0 + xr3) * 0.5;
325  my = (yl0 + yr3) * 0.5;
326  dx = xx1 - mx;
327  dy = yy1 - my;
328  d1 = dx * dx + dy * dy;
329  dx = xx2 - mx;
330  dy = yy2 - my;
331  d2 = dx * dx + dy * dy;
332 
333  // if the curve is flat enough, or no more subdivisions are
334  // allowed, add the straight line segment
335  if (p2 - p1 == 1 || (d1 <= flatness2 && d2 <= flatness2)) {
336  addSegment(xl0, yl0, xr3, yr3);
337  p1 = p2;
338 
339  // otherwise, subdivide the curve
340  } else {
341  xl1 = (xl0 + xx1) * 0.5;
342  yl1 = (yl0 + yy1) * 0.5;
343  xh = (xx1 + xx2) * 0.5;
344  yh = (yy1 + yy2) * 0.5;
345  xl2 = (xl1 + xh) * 0.5;
346  yl2 = (yl1 + yh) * 0.5;
347  xr2 = (xx2 + xr3) * 0.5;
348  yr2 = (yy2 + yr3) * 0.5;
349  xr1 = (xh + xr2) * 0.5;
350  yr1 = (yh + yr2) * 0.5;
351  xr0 = (xl2 + xr1) * 0.5;
352  yr0 = (yl2 + yr1) * 0.5;
353  // add the new subdivision points
354  p3 = (p1 + p2) / 2;
355 
356  *(cx + p1 * 3 + 1) = xl1;
357  *(cx + p1 * 3 + 2) = xl2;
358 
359  *(cy + p1 * 3 + 1) = yl1;
360  *(cy + p1 * 3 + 2) = yl2;
361 
362  *(cNext + p1) = p3;
363 
364  *(cx + p3 * 3 + 0) = xr0;
365  *(cx + p3 * 3 + 1) = xr1;
366  *(cx + p3 * 3 + 2) = xr2;
367 
368  *(cy + p3 * 3 + 0) = yr0;
369  *(cy + p3 * 3 + 1) = yr1;
370  *(cy + p3 * 3 + 2) = yr2;
371 
372  *(cNext + p3) = p2;
373  }
374  }
375 
376  delete[] cx;
377  delete[] cy;
378  delete[] cNext;
379 }
380 
382 {
383  grow(1);
384  if (unlikely(!segs))
385  return;
386  segs[length].x0 = x0;
387  segs[length].y0 = y0;
388  segs[length].x1 = x1;
389  segs[length].y1 = y1;
390  segs[length].flags = 0;
391  if (y1 == y0) {
392  segs[length].dxdy = segs[length].dydx = 0;
394  if (x1 == x0) {
396  }
397  } else if (x1 == x0) {
398  segs[length].dxdy = segs[length].dydx = 0;
400  } else {
401  segs[length].dxdy = (x1 - x0) / (y1 - y0);
402  segs[length].dydx = (SplashCoord)1 / segs[length].dxdy;
403  }
404  if (y0 > y1) {
406  }
407  ++length;
408 }
409 
411 {
412  bool operator()(const SplashXPathSeg &seg0, const SplashXPathSeg &seg1)
413  {
414  SplashCoord x0, y0, x1, y1;
415 
416  if (seg0.flags & splashXPathFlip) {
417  x0 = seg0.x1;
418  y0 = seg0.y1;
419  } else {
420  x0 = seg0.x0;
421  y0 = seg0.y0;
422  }
423  if (seg1.flags & splashXPathFlip) {
424  x1 = seg1.x1;
425  y1 = seg1.y1;
426  } else {
427  x1 = seg1.x0;
428  y1 = seg1.y0;
429  }
430  return (y0 != y1) ? (y0 < y1) : (x0 < x1);
431  }
432 };
433 
435 {
437  int i;
438 
439  for (i = 0, seg = segs; i < length; ++i, ++seg) {
440  seg->x0 *= splashAASize;
441  seg->y0 *= splashAASize;
442  seg->x1 *= splashAASize;
443  seg->y1 *= splashAASize;
444  }
445 }
446 
448 {
450 }
#define y0
#define x3
#define adjust(a)
#define x0
#define y3
char * p2
Definition: bmpfont.h:62
char * p1
Definition: bmpfont.h:62
static char mx
Definition: bmpfont.h:51
void addSegment(SplashCoord x0, SplashCoord y0, SplashCoord x1, SplashCoord y1)
Definition: SplashXPath.cc:443
SplashXPathSeg * segs
Definition: SplashXPath.h:130
void aaScale()
Definition: SplashXPath.cc:434
GBool strokeAdjust(SplashXPathPoint *pts, SplashPathHint *hints, int nHints, SplashStrokeAdjustMode strokeAdjMode)
Definition: SplashXPath.cc:228
SplashXPath(SplashPath *path, SplashCoord *matrix, SplashCoord flatness, GBool closeSubpaths, GBool simplify, SplashStrokeAdjustMode strokeAdjMode)
Definition: SplashXPath.cc:83
void addCurve(SplashCoord x0, SplashCoord y0, SplashCoord x1, SplashCoord y1, SplashCoord x2, SplashCoord y2, SplashCoord x3, SplashCoord y3, SplashCoord flatness, GBool first, GBool last, GBool end0, GBool end1)
Definition: SplashXPath.cc:354
void grow(int nSegs)
Definition: SplashXPath.cc:342
void transform(SplashCoord *matrix, SplashCoord xi, SplashCoord yi, SplashCoord *xo, SplashCoord *yo)
Definition: SplashXPath.cc:49
#define gfree(p)
Definition: dt2dv.c:326
#define xp
void * gmallocn(int nObjs, int objSize)
Definition: gmem.cc:204
#define memcpy(d, s, n)
Definition: gsftopk.c:64
struct fractpoint hint
Definition: hints.c:78
#define unlikely(x)
Definition: jbig2arith.cc:116
small capitals from c petite p scientific i
Definition: afcover.h:80
kerning y
Definition: ttdriver.c:212
int int cy
Definition: gdfx.h:13
int cx
Definition: gdfx.h:12
static int splashRound(SplashCoord x)
Definition: SplashMath.h:180
#define splashPathLast
Definition: SplashPath.h:36
#define splashPathClosed
Definition: SplashPath.h:40
#define splashPathCurve
Definition: SplashPath.h:43
#define splashPathFirst
Definition: SplashPath.h:33
double SplashCoord
Definition: SplashTypes.h:23
#define splashAASize
Definition: SplashTypes.h:30
#define splashMaxCurveSplits
Definition: SplashXPath.h:26
float x
Definition: cordic.py:15
float ** matrix()
static int32_t last
Definition: ppagelist.c:29
static int32_t first
Definition: ppagelist.c:29
#define x1
#define y1
#define y2
#define x2
#define seg
void * gmallocn_checkoverflow(int count, int size)
Definition: gmem.h:122
void * greallocn_checkoverflow(void *p, int count, int size)
Definition: gmem.h:174
#define splashXPathFlip
Definition: SplashXPath.h:53
#define splashXPathHoriz
Definition: SplashXPath.h:47
#define splashXPathVert
Definition: SplashXPath.h:50
flatness
Definition: splinefont.c:106
static int sort(lua_State *L)
Definition: ltablib.c:411
d1
Definition: sec_div.c:81
SplashCoord xm
Definition: SplashXPath.cc:43
SplashCoord x0b
Definition: SplashXPath.cc:40
SplashCoord x0a
Definition: SplashXPath.cc:40
SplashCoord x0
Definition: SplashXPath.cc:43
SplashCoord xma
Definition: SplashXPath.cc:41
SplashCoord x1b
Definition: SplashXPath.cc:42
SplashCoord x1a
Definition: SplashXPath.cc:42
SplashCoord xmb
Definition: SplashXPath.cc:41
SplashCoord x1
Definition: SplashXPath.cc:43
SplashCoord x
Definition: SplashXPath.cc:34
SplashCoord y
Definition: SplashXPath.cc:34
SplashCoord y1
Definition: SplashXPath.h:34
SplashCoord x0
Definition: SplashXPath.h:33
SplashCoord y0
Definition: SplashXPath.h:33
SplashCoord dxdy
Definition: SplashXPath.h:35
SplashCoord dydx
Definition: SplashXPath.h:36
unsigned int flags
Definition: SplashXPath.h:44
SplashCoord x1
Definition: SplashXPath.h:34
bool operator()(const SplashXPathSeg &seg0, const SplashXPathSeg &seg1)
Definition: SplashXPath.cc:412
Definition: tpic.c:45
double x
Definition: tpic.c:46
double y
Definition: tpic.c:46
Definition: gd.c:2418
int j
Definition: t4ht.c:1589