← Back to branch summary

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

« back to all changes in this revision

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