← Back to branch summary

~ubuntu-branches/ubuntu/lucid/xpdf/lucid-updates

« back to all changes in this revision

Viewing changes to splash/SplashXPath.cc

  • Committer: Bazaar Package Importer
  • Author(s): Andy Price
  • Date: 2007-05-17 22:04:33 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20070517220433-gzcx2lrvllkbl7mr
Tags: 3.02-1ubuntu1
https://launchpad.net/bugs/113365
* Merge from Debian unstable (LP: #113365), remaining changes:
  - Added back 09_xpdfrc_manpage.dpatch (LP #71753)
  - Set Ubuntu maintainer

Show diffs side-by-side

added added

removed removed

Lines of Context:
splash/SplashXPath.cc
19
19
 
20
20
//------------------------------------------------------------------------
21
21
 
22
 
#define maxCurveSplits (1 << 10)
 
22
struct SplashXPathPoint {
 
23
  SplashCoord x, y;
 
24
};
 
25
 
 
26
struct SplashXPathAdjust {
 
27
  int firstPt, lastPt;          // range of points
 
28
  GBool vert;                   // vertical or horizontal hint
 
29
  SplashCoord x0a, x0b,         // hint boundaries
 
30
              xma, xmb,
 
31
              x1a, x1b;
 
32
  SplashCoord x0, x1, xm;       // adjusted coordinates
 
33
};
 
34
 
 
35
//------------------------------------------------------------------------
 
36
 
 
37
// Transform a point from user space to device space.
 
38
inline void SplashXPath::transform(SplashCoord *matrix,
 
39
                                   SplashCoord xi, SplashCoord yi,
 
40
                                   SplashCoord *xo, SplashCoord *yo) {
 
41
  //                          [ m[0] m[1] 0 ]
 
42
  // [xo yo 1] = [xi yi 1] *  [ m[2] m[3] 0 ]
 
43
  //                          [ m[4] m[5] 1 ]
 
44
  *xo = xi * matrix[0] + yi * matrix[2] + matrix[4];
 
45
  *yo = xi * matrix[1] + yi * matrix[3] + matrix[5];
 
46
}
23
47
 
24
48
//------------------------------------------------------------------------
25
49
// SplashXPath
30
54
  length = size = 0;
31
55
}
32
56
 
33
 
SplashXPath::SplashXPath(SplashPath *path, SplashCoord flatness,
34
 
                         GBool closeSubpaths) {
35
 
  SplashCoord xc, yc, dx, dy, r, x0, y0, x1, y1;
36
 
  int quad0, quad1, quad;
37
 
  int curSubpath, n, i, j;
 
57
SplashXPath::SplashXPath(SplashPath *path, SplashCoord *matrix,
 
58
                         SplashCoord flatness, GBool closeSubpaths) {
 
59
  SplashPathHint *hint;
 
60
  SplashXPathPoint *pts;
 
61
  SplashXPathAdjust *adjusts, *adjust;
 
62
  SplashCoord x0, y0, x1, y1, x2, y2, x3, y3, xsp, ysp;
 
63
  SplashCoord adj0, adj1, w;
 
64
  int ww;
 
65
  int curSubpath, curSubpathX, i, j;
 
66
 
 
67
  // transform the points
 
68
  pts = (SplashXPathPoint *)gmallocn(path->length, sizeof(SplashXPathPoint));
 
69
  for (i = 0; i < path->length; ++i) {
 
70
    transform(matrix, path->pts[i].x, path->pts[i].y, &pts[i].x, &pts[i].y);
 
71
  }
 
72
 
 
73
  // set up the stroke adjustment hints
 
74
  if (path->hints) {
 
75
    adjusts = (SplashXPathAdjust *)gmallocn(path->hintsLength,
 
76
                                            sizeof(SplashXPathAdjust));
 
77
    for (i = 0; i < path->hintsLength; ++i) {
 
78
      hint = &path->hints[i];
 
79
      x0 = pts[hint->ctrl0    ].x;    y0 = pts[hint->ctrl0    ].y;
 
80
      x1 = pts[hint->ctrl0 + 1].x;    y1 = pts[hint->ctrl0 + 1].y;
 
81
      x2 = pts[hint->ctrl1    ].x;    y2 = pts[hint->ctrl1    ].y;
 
82
      x3 = pts[hint->ctrl1 + 1].x;    y3 = pts[hint->ctrl1 + 1].y;
 
83
      if (x0 == x1 && x2 == x3) {
 
84
        adjusts[i].vert = gTrue;
 
85
        adj0 = x0;
 
86
        adj1 = x2;
 
87
      } else if (y0 == y1 && y2 == y3) {
 
88
        adjusts[i].vert = gFalse;
 
89
        adj0 = y0;
 
90
        adj1 = y2;
 
91
      } else {
 
92
        gfree(adjusts);
 
93
        adjusts = NULL;
 
94
        break;
 
95
      }
 
96
      if (adj0 > adj1) {
 
97
        x0 = adj0;
 
98
        adj0 = adj1;
 
99
        adj1 = x0;
 
100
      }
 
101
      w = adj1 - adj0;
 
102
      ww = splashRound(w);
 
103
      if (ww == 0) {
 
104
        ww = 1;
 
105
      }
 
106
      adjusts[i].x0a = adj0 - 0.01;
 
107
      adjusts[i].x0b = adj0 + 0.01;
 
108
      adjusts[i].xma = (SplashCoord)0.5 * (adj0 + adj1) - 0.01;
 
109
      adjusts[i].xmb = (SplashCoord)0.5 * (adj0 + adj1) + 0.01;
 
110
      adjusts[i].x1a = adj1 - 0.01;
 
111
      adjusts[i].x1b = adj1 + 0.01;
 
112
      adjusts[i].x0 = (SplashCoord)splashRound(adj0);
 
113
      adjusts[i].x1 = adjusts[i].x0 + ww - 0.01;
 
114
      adjusts[i].xm = (SplashCoord)0.5 * (adjusts[i].x0 + adjusts[i].x1);
 
115
      adjusts[i].firstPt = hint->firstPt;
 
116
      adjusts[i].lastPt = hint->lastPt;
 
117
    }
 
118
 
 
119
  } else {
 
120
    adjusts = NULL;
 
121
  }
 
122
 
 
123
  // perform stroke adjustment
 
124
  if (adjusts) {
 
125
    for (i = 0, adjust = adjusts; i < path->hintsLength; ++i, ++adjust) {
 
126
      for (j = adjust->firstPt; j <= adjust->lastPt; ++j) {
 
127
        strokeAdjust(adjust, &pts[j].x, &pts[j].y);
 
128
      }
 
129
    }
 
130
    gfree(adjusts);
 
131
  }
38
132
 
39
133
  segs = NULL;
40
134
  length = size = 0;
41
135
 
 
136
  x0 = y0 = xsp = ysp = 0; // make gcc happy
 
137
  adj0 = adj1 = 0; // make gcc happy
 
138
  curSubpath = 0;
 
139
  curSubpathX = 0;
42
140
  i = 0;
43
 
  curSubpath = 0;
44
141
  while (i < path->length) {
45
142
 
46
143
    // first point in subpath - skip it
47
144
    if (path->flags[i] & splashPathFirst) {
 
145
      x0 = pts[i].x;
 
146
      y0 = pts[i].y;
 
147
      xsp = x0;
 
148
      ysp = y0;
48
149
      curSubpath = i;
 
150
      curSubpathX = length;
49
151
      ++i;
50
152
 
51
153
    } else {
52
154
 
53
155
      // curve segment
54
156
      if (path->flags[i] & splashPathCurve) {
55
 
        addCurve(path->pts[i-1].x, path->pts[i-1].y,
56
 
                 path->pts[i  ].x, path->pts[i  ].y,
57
 
                 path->pts[i+1].x, path->pts[i+1].y,
58
 
                 path->pts[i+2].x, path->pts[i+2].y,
 
157
        x1 = pts[i].x;
 
158
        y1 = pts[i].y;
 
159
        x2 = pts[i+1].x;
 
160
        y2 = pts[i+1].y;
 
161
        x3 = pts[i+2].x;
 
162
        y3 = pts[i+2].y;
 
163
        addCurve(x0, y0, x1, y1, x2, y2, x3, y3,
59
164
                 flatness,
60
165
                 (path->flags[i-1] & splashPathFirst),
61
166
                 (path->flags[i+2] & splashPathLast),
65
170
                 !closeSubpaths &&
66
171
                   (path->flags[i+2] & splashPathLast) &&
67
172
                   !(path->flags[i+2] & splashPathClosed));
 
173
        x0 = x3;
 
174
        y0 = y3;
68
175
        i += 3;
69
176
 
70
 
      // clockwise circular arc
71
 
      } else if (path->flags[i] & splashPathArcCW) {
72
 
        xc = path->pts[i].x;
73
 
        yc = path->pts[i].y;
74
 
        dx = path->pts[i+1].x - xc;
75
 
        dy = path->pts[i+1].y - yc;
76
 
        r = splashSqrt(dx * dx + dy * dy);
77
 
        if (path->pts[i-1].x < xc && path->pts[i-1].y <= yc) {
78
 
          quad0 = 0;
79
 
        } else if (path->pts[i-1].x >= xc && path->pts[i-1].y < yc) {
80
 
          quad0 = 1;
81
 
        } else if (path->pts[i-1].x > xc && path->pts[i-1].y >= yc) {
82
 
          quad0 = 2;
83
 
        } else {
84
 
          quad0 = 3;
85
 
        }
86
 
        if (path->pts[i+1].x <= xc && path->pts[i+1].y < yc) {
87
 
          quad1 = 0;
88
 
        } else if (path->pts[i+1].x > xc && path->pts[i+1].y <= yc) {
89
 
          quad1 = 1;
90
 
        } else if (path->pts[i+1].x >= xc && path->pts[i+1].y > yc) {
91
 
          quad1 = 2;
92
 
        } else {
93
 
          quad1 = 3;
94
 
        }
95
 
        n = 0; // make gcc happy
96
 
        if (quad0 == quad1) {
97
 
          switch (quad0) {
98
 
          case 0:
99
 
          case 1: n = path->pts[i-1].x < path->pts[i+1].x ? 0 : 4; break;
100
 
          case 2:
101
 
          case 3: n = path->pts[i-1].x > path->pts[i+1].x ? 0 : 4; break;
102
 
          }
103
 
        } else {
104
 
          n = (quad1 - quad0) & 3;
105
 
        }
106
 
        x0 = path->pts[i-1].x;
107
 
        y0 = path->pts[i-1].y;
108
 
        x1 = y1 = 0; // make gcc happy
109
 
        quad = quad0;
110
 
        for (j = 0; j < n; ++j) {
111
 
          switch (quad) {
112
 
          case 0: x1 = xc;     y1 = yc - r; break;
113
 
          case 1: x1 = xc + r; y1 = yc;     break;
114
 
          case 2: x1 = xc;     y1 = yc + r; break;
115
 
          case 3: x1 = xc - r; y1 = yc;     break;
116
 
          }
117
 
          addArc(x0, y0, x1, y1,
118
 
                 xc, yc, r, quad, flatness,
119
 
                 quad == quad0 && (path->flags[i-1] & splashPathFirst),
120
 
                 gFalse,
121
 
                 quad == quad0 && !closeSubpaths &&
122
 
                   (path->flags[i-1] & splashPathFirst) &&
123
 
                   !(path->flags[i-1] & splashPathClosed),
124
 
                 gFalse);
125
 
          x0 = x1;
126
 
          y0 = y1;
127
 
          quad = (quad + 1) & 3;
128
 
        }
129
 
        addArc(x0, y0, path->pts[i+1].x, path->pts[i+1].y,
130
 
               xc, yc, r, quad, flatness,
131
 
               quad == quad0 && (path->flags[i-1] & splashPathFirst),
132
 
               (path->flags[i+1] & splashPathLast),
133
 
               quad == quad0 && !closeSubpaths &&
134
 
                 (path->flags[i-1] & splashPathFirst) &&
135
 
                 !(path->flags[i-1] & splashPathClosed),
136
 
               !closeSubpaths &&
137
 
                 (path->flags[i+1] & splashPathLast) &&
138
 
                 !(path->flags[i+1] & splashPathClosed));
139
 
        i += 2;
140
 
 
141
177
      // line segment
142
178
      } else {
143
 
        addSegment(path->pts[i-1].x, path->pts[i-1].y,
144
 
                   path->pts[i].x, path->pts[i].y,
 
179
        x1 = pts[i].x;
 
180
        y1 = pts[i].y;
 
181
        addSegment(x0, y0, x1, y1,
145
182
                   path->flags[i-1] & splashPathFirst,
146
183
                   path->flags[i] & splashPathLast,
147
184
                   !closeSubpaths &&
150
187
                   !closeSubpaths &&
151
188
                     (path->flags[i] & splashPathLast) &&
152
189
                     !(path->flags[i] & splashPathClosed));
 
190
        x0 = x1;
 
191
        y0 = y1;
153
192
        ++i;
154
193
      }
155
194
 
156
195
      // close a subpath
157
196
      if (closeSubpaths &&
158
197
          (path->flags[i-1] & splashPathLast) &&
159
 
          (path->pts[i-1].x != path->pts[curSubpath].x ||
160
 
           path->pts[i-1].y != path->pts[curSubpath]. y)) {
161
 
        addSegment(path->pts[i-1].x, path->pts[i-1].y,
162
 
                   path->pts[curSubpath].x, path->pts[curSubpath].y,
 
198
          (pts[i-1].x != pts[curSubpath].x ||
 
199
           pts[i-1].y != pts[curSubpath].y)) {
 
200
        addSegment(x0, y0, xsp, ysp,
163
201
                   gFalse, gTrue, gFalse, gFalse);
164
202
      }
165
203
    }
166
204
  }
 
205
 
 
206
  gfree(pts);
 
207
}
 
208
 
 
209
// Apply the stroke adjust hints to point <pt>: (*<xp>, *<yp>).
 
210
void SplashXPath::strokeAdjust(SplashXPathAdjust *adjust,
 
211
                               SplashCoord *xp, SplashCoord *yp) {
 
212
  SplashCoord x, y;
 
213
 
 
214
  if (adjust->vert) {
 
215
    x = *xp;
 
216
    if (x > adjust->x0a && x < adjust->x0b) {
 
217
      *xp = adjust->x0;
 
218
    } else if (x > adjust->xma && x < adjust->xmb) {
 
219
      *xp = adjust->xm;
 
220
    } else if (x > adjust->x1a && x < adjust->x1b) {
 
221
      *xp = adjust->x1;
 
222
    }
 
223
  } else {
 
224
    y = *yp;
 
225
    if (y > adjust->x0a && y < adjust->x0b) {
 
226
      *yp = adjust->x0;
 
227
    } else if (y > adjust->xma && y < adjust->xmb) {
 
228
      *yp = adjust->xm;
 
229
    } else if (y > adjust->x1a && y < adjust->x1b) {
 
230
      *yp = adjust->x1;
 
231
    }
 
232
  }
167
233
}
168
234
 
169
235
SplashXPath::SplashXPath(SplashXPath *xPath) {
196
262
                           SplashCoord x3, SplashCoord y3,
197
263
                           SplashCoord flatness,
198
264
                           GBool first, GBool last, GBool end0, GBool end1) {
199
 
  SplashCoord cx[maxCurveSplits + 1][3];
200
 
  SplashCoord cy[maxCurveSplits + 1][3];
201
 
  int cNext[maxCurveSplits + 1];
 
265
  SplashCoord cx[splashMaxCurveSplits + 1][3];
 
266
  SplashCoord cy[splashMaxCurveSplits + 1][3];
 
267
  int cNext[splashMaxCurveSplits + 1];
202
268
  SplashCoord xl0, xl1, xl2, xr0, xr1, xr2, xr3, xx1, xx2, xh;
203
269
  SplashCoord yl0, yl1, yl2, yr0, yr1, yr2, yr3, yy1, yy2, yh;
204
270
  SplashCoord dx, dy, mx, my, d1, d2, flatness2;
208
274
 
209
275
  // initial segment
210
276
  p1 = 0;
211
 
  p2 = maxCurveSplits;
 
277
  p2 = splashMaxCurveSplits;
212
278
  cx[p1][0] = x0;  cy[p1][0] = y0;
213
279
  cx[p1][1] = x1;  cy[p1][1] = y1;
214
280
  cx[p1][2] = x2;  cy[p1][2] = y2;
215
281
  cx[p2][0] = x3;  cy[p2][0] = y3;
216
282
  cNext[p1] = p2;
217
283
 
218
 
  while (p1 < maxCurveSplits) {
 
284
  while (p1 < splashMaxCurveSplits) {
219
285
 
220
286
    // get the next segment
221
287
    xl0 = cx[p1][0];  yl0 = cy[p1][0];
242
308
    if (p2 - p1 == 1 || (d1 <= flatness2 && d2 <= flatness2)) {
243
309
      addSegment(xl0, yl0, xr3, yr3,
244
310
                 p1 == 0 && first,
245
 
                 p2 == maxCurveSplits && last,
 
311
                 p2 == splashMaxCurveSplits && last,
246
312
                 p1 == 0 && end0,
247
 
                 p2 == maxCurveSplits && end1);
 
313
                 p2 == splashMaxCurveSplits && end1);
248
314
      p1 = p2;
249
315
 
250
316
    // otherwise, subdivide the curve
274
340
  }
275
341
}
276
342
 
277
 
void SplashXPath::addArc(SplashCoord x0, SplashCoord y0,
278
 
                         SplashCoord x1, SplashCoord y1,
279
 
                         SplashCoord xc, SplashCoord yc,
280
 
                         SplashCoord r, int quad,
281
 
                         SplashCoord flatness,
282
 
                         GBool first, GBool last, GBool end0, GBool end1) {
283
 
  SplashCoord px[maxCurveSplits + 1];
284
 
  SplashCoord py[maxCurveSplits + 1];
285
 
  int pNext[maxCurveSplits + 1];
286
 
  SplashCoord r2, flatness2;
287
 
  SplashCoord xx0, yy0, xx1, yy1, xm, ym, t, dx, dy;
288
 
  int p1, p2, p3;
289
 
 
290
 
  r2 = r * r;
291
 
  flatness2 = flatness * flatness;
292
 
 
293
 
  // initial segment
294
 
  p1 = 0;
295
 
  p2 = maxCurveSplits;
296
 
  px[p1] = x0;  py[p1] = y0;
297
 
  px[p2] = x1;  py[p2] = y1;
298
 
  pNext[p1] = p2;
299
 
 
300
 
  while (p1 < maxCurveSplits) {
301
 
 
302
 
    // get the next segment
303
 
    xx0 = px[p1];  yy0 = py[p1];
304
 
    p2 = pNext[p1];
305
 
    xx1 = px[p2];  yy1 = py[p2];
306
 
 
307
 
    // compute the arc midpoint
308
 
    t = (xx0 - xc) * (xx1 - xc) - (yy0 - yc) * (yy1 - yc);
309
 
    xm = splashSqrt((SplashCoord)0.5 * (r2 + t));
310
 
    ym = splashSqrt((SplashCoord)0.5 * (r2 - t));
311
 
    switch (quad) {
312
 
    case 0: xm = xc - xm;  ym = yc - ym;  break;
313
 
    case 1: xm = xc + xm;  ym = yc - ym;  break;
314
 
    case 2: xm = xc + xm;  ym = yc + ym;  break;
315
 
    case 3: xm = xc - xm;  ym = yc + ym;  break;
316
 
    }
317
 
 
318
 
    // compute distance from midpoint of straight segment to midpoint
319
 
    // of arc
320
 
    dx = (SplashCoord)0.5 * (xx0 + xx1) - xm;
321
 
    dy = (SplashCoord)0.5 * (yy0 + yy1) - ym;
322
 
 
323
 
    // if the arc is flat enough, or no more subdivisions are allowed,
324
 
    // add the straight line segment
325
 
    if (p2 - p1 == 1 || dx * dx + dy * dy <= flatness2) {
326
 
      addSegment(xx0, yy0, xx1, yy1,
327
 
                 p1 == 0 && first,
328
 
                 p2 == maxCurveSplits && last,
329
 
                 p1 == 0 && end0,
330
 
                 p2 == maxCurveSplits && end1);
331
 
      p1 = p2;
332
 
 
333
 
    // otherwise, subdivide the arc
334
 
    } else {
335
 
      p3 = (p1 + p2) / 2;
336
 
      px[p3] = xm;
337
 
      py[p3] = ym;
338
 
      pNext[p1] = p3;
339
 
      pNext[p3] = p2;
340
 
    }
341
 
  }
342
 
}
343
 
 
344
343
void SplashXPath::addSegment(SplashCoord x0, SplashCoord y0,
345
344
                             SplashCoord x1, SplashCoord y1,
346
345
                             GBool first, GBool last, GBool end0, GBool end1) {
372
371
    segs[length].dxdy = segs[length].dydx = 0;
373
372
    segs[length].flags |= splashXPathVert;
374
373
  } else {
 
374
#if USE_FIXEDPOINT
 
375
    if (FixedPoint::divCheck(x1 - x0, y1 - y0, &segs[length].dxdy)) {
 
376
      segs[length].dydx = (SplashCoord)1 / segs[length].dxdy;
 
377
    } else {
 
378
      segs[length].dxdy = segs[length].dydx = 0;
 
379
      if (splashAbs(x1 - x0) > splashAbs(y1 - y0)) {
 
380
        segs[length].flags |= splashXPathHoriz;
 
381
      } else {
 
382
        segs[length].flags |= splashXPathVert;
 
383
      }
 
384
    }
 
385
#else
375
386
    segs[length].dxdy = (x1 - x0) / (y1 - y0);
376
387
    segs[length].dydx = (SplashCoord)1 / segs[length].dxdy;
 
388
#endif
377
389
  }
378
390
  if (y0 > y1) {
379
391
    segs[length].flags |= splashXPathFlip;
409
421
  return 0;
410
422
}
411
423
 
 
424
void SplashXPath::aaScale() {
 
425
  SplashXPathSeg *seg;
 
426
  int i;
 
427
 
 
428
  for (i = 0, seg = segs; i < length; ++i, ++seg) {
 
429
    seg->x0 *= splashAASize;
 
430
    seg->y0 *= splashAASize;
 
431
    seg->x1 *= splashAASize;
 
432
    seg->y1 *= splashAASize;
 
433
  }
 
434
}
 
435
 
412
436
void SplashXPath::sort() {
413
437
  qsort(segs, length, sizeof(SplashXPathSeg), &cmpXPathSegs);
414
438
}