source: trunk/poppler/mypoppler/splash/SplashXPath.cc @ 2

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 15 years ago

First import

File size: 11.0 KB
Line 
1//========================================================================
2//
3// SplashXPath.cc
4//
5//========================================================================
6
7#include <config.h>
8
9#ifdef USE_GCC_PRAGMAS
10#pragma implementation
11#endif
12
13#include <stdlib.h>
14#include <string.h>
15#include "goo/gmem.h"
16#include "SplashMath.h"
17#include "SplashPath.h"
18#include "SplashXPath.h"
19
20//------------------------------------------------------------------------
21
22#define maxCurveSplits (1 << 10)
23
24//------------------------------------------------------------------------
25// SplashXPath
26//------------------------------------------------------------------------
27
28SplashXPath::SplashXPath() {
29  segs = NULL;
30  length = size = 0;
31}
32
33SplashXPath::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;
38
39  segs = NULL;
40  length = size = 0;
41
42  i = 0;
43  curSubpath = 0;
44  while (i < path->length) {
45
46    // first point in subpath - skip it
47    if (path->flags[i] & splashPathFirst) {
48      curSubpath = i;
49      ++i;
50
51    } else {
52
53      // curve segment
54      if (path->flags[i] & splashPathCurve) {
55        addCurve(path->pts[i-1].x, path->pts[i-1].y,
56                 path->pts[].x, path->pts[].y,
57                 path->pts[i+1].x, path->pts[i+1].y,
58                 path->pts[i+2].x, path->pts[i+2].y,
59                 flatness,
60                 (path->flags[i-1] & splashPathFirst),
61                 (path->flags[i+2] & splashPathLast),
62                 !closeSubpaths &&
63                   (path->flags[i-1] & splashPathFirst) &&
64                   !(path->flags[i-1] & splashPathClosed),
65                 !closeSubpaths &&
66                   (path->flags[i+2] & splashPathLast) &&
67                   !(path->flags[i+2] & splashPathClosed));
68        i += 3;
69
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      // line segment
142      } else {
143        addSegment(path->pts[i-1].x, path->pts[i-1].y,
144                   path->pts[i].x, path->pts[i].y,
145                   path->flags[i-1] & splashPathFirst,
146                   path->flags[i] & splashPathLast,
147                   !closeSubpaths &&
148                     (path->flags[i-1] & splashPathFirst) &&
149                     !(path->flags[i-1] & splashPathClosed),
150                   !closeSubpaths &&
151                     (path->flags[i] & splashPathLast) &&
152                     !(path->flags[i] & splashPathClosed));
153        ++i;
154      }
155
156      // close a subpath
157      if (closeSubpaths &&
158          (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,
163                   gFalse, gTrue, gFalse, gFalse);
164      }
165    }
166  }
167}
168
169SplashXPath::SplashXPath(SplashXPath *xPath) {
170  length = xPath->length;
171  size = xPath->size;
172  segs = (SplashXPathSeg *)gmallocn(size, sizeof(SplashXPathSeg));
173  memcpy(segs, xPath->segs, length * sizeof(SplashXPathSeg));
174}
175
176SplashXPath::~SplashXPath() {
177  gfree(segs);
178}
179
180// Add space for <nSegs> more segments
181void SplashXPath::grow(int nSegs) {
182  if (length + nSegs > size) {
183    if (size == 0) {
184      size = 32;
185    }
186    while (size < length + nSegs) {
187      size *= 2;
188    }
189    segs = (SplashXPathSeg *)greallocn(segs, size, sizeof(SplashXPathSeg));
190  }
191}
192
193void SplashXPath::addCurve(SplashCoord x0, SplashCoord y0,
194                           SplashCoord x1, SplashCoord y1,
195                           SplashCoord x2, SplashCoord y2,
196                           SplashCoord x3, SplashCoord y3,
197                           SplashCoord flatness,
198                           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];
202  SplashCoord xl0, xl1, xl2, xr0, xr1, xr2, xr3, xx1, xx2, xh;
203  SplashCoord yl0, yl1, yl2, yr0, yr1, yr2, yr3, yy1, yy2, yh;
204  SplashCoord dx, dy, mx, my, d1, d2, flatness2;
205  int p1, p2, p3;
206
207  flatness2 = flatness * flatness;
208
209  // initial segment
210  p1 = 0;
211  p2 = maxCurveSplits;
212  cx[p1][0] = x0;  cy[p1][0] = y0;
213  cx[p1][1] = x1;  cy[p1][1] = y1;
214  cx[p1][2] = x2;  cy[p1][2] = y2;
215  cx[p2][0] = x3;  cy[p2][0] = y3;
216  cNext[p1] = p2;
217
218  while (p1 < maxCurveSplits) {
219
220    // get the next segment
221    xl0 = cx[p1][0];  yl0 = cy[p1][0];
222    xx1 = cx[p1][1];  yy1 = cy[p1][1];
223    xx2 = cx[p1][2];  yy2 = cy[p1][2];
224    p2 = cNext[p1];
225    xr3 = cx[p2][0];  yr3 = cy[p2][0];
226
227    // compute the distances from the control points to the
228    // midpoint of the straight line (this is a bit of a hack, but
229    // it's much faster than computing the actual distances to the
230    // line)
231    mx = (xl0 + xr3) * 0.5;
232    my = (yl0 + yr3) * 0.5;
233    dx = xx1 - mx;
234    dy = yy1 - my;
235    d1 = dx*dx + dy*dy;
236    dx = xx2 - mx;
237    dy = yy2 - my;
238    d2 = dx*dx + dy*dy;
239
240    // if the curve is flat enough, or no more subdivisions are
241    // allowed, add the straight line segment
242    if (p2 - p1 == 1 || (d1 <= flatness2 && d2 <= flatness2)) {
243      addSegment(xl0, yl0, xr3, yr3,
244                 p1 == 0 && first,
245                 p2 == maxCurveSplits && last,
246                 p1 == 0 && end0,
247                 p2 == maxCurveSplits && end1);
248      p1 = p2;
249
250    // otherwise, subdivide the curve
251    } else {
252      xl1 = (xl0 + xx1) * 0.5;
253      yl1 = (yl0 + yy1) * 0.5;
254      xh = (xx1 + xx2) * 0.5;
255      yh = (yy1 + yy2) * 0.5;
256      xl2 = (xl1 + xh) * 0.5;
257      yl2 = (yl1 + yh) * 0.5;
258      xr2 = (xx2 + xr3) * 0.5;
259      yr2 = (yy2 + yr3) * 0.5;
260      xr1 = (xh + xr2) * 0.5;
261      yr1 = (yh + yr2) * 0.5;
262      xr0 = (xl2 + xr1) * 0.5;
263      yr0 = (yl2 + yr1) * 0.5;
264      // add the new subdivision points
265      p3 = (p1 + p2) / 2;
266      cx[p1][1] = xl1;  cy[p1][1] = yl1;
267      cx[p1][2] = xl2;  cy[p1][2] = yl2;
268      cNext[p1] = p3;
269      cx[p3][0] = xr0;  cy[p3][0] = yr0;
270      cx[p3][1] = xr1;  cy[p3][1] = yr1;
271      cx[p3][2] = xr2;  cy[p3][2] = yr2;
272      cNext[p3] = p2;
273    }
274  }
275}
276
277void 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
344void SplashXPath::addSegment(SplashCoord x0, SplashCoord y0,
345                             SplashCoord x1, SplashCoord y1,
346                             GBool first, GBool last, GBool end0, GBool end1) {
347  grow(1);
348  segs[length].x0 = x0;
349  segs[length].y0 = y0;
350  segs[length].x1 = x1;
351  segs[length].y1 = y1;
352  segs[length].flags = 0;
353  if (first) {
354    segs[length].flags |= splashXPathFirst;
355  }
356  if (last) {
357    segs[length].flags |= splashXPathLast;
358  }
359  if (end0) {
360    segs[length].flags |= splashXPathEnd0;
361  }
362  if (end1) {
363    segs[length].flags |= splashXPathEnd1;
364  }
365  if (y1 == y0) {
366    segs[length].dxdy = segs[length].dydx = 0;
367    segs[length].flags |= splashXPathHoriz;
368    if (x1 == x0) {
369      segs[length].flags |= splashXPathVert;
370    }
371  } else if (x1 == x0) {
372    segs[length].dxdy = segs[length].dydx = 0;
373    segs[length].flags |= splashXPathVert;
374  } else {
375    segs[length].dxdy = (x1 - x0) / (y1 - y0);
376    segs[length].dydx = (SplashCoord)1 / segs[length].dxdy;
377  }
378  if (y0 > y1) {
379    segs[length].flags |= splashXPathFlip;
380  }
381  ++length;
382}
383
384static int cmpXPathSegs(const void *arg0, const void *arg1) {
385  SplashXPathSeg *seg0 = (SplashXPathSeg *)arg0;
386  SplashXPathSeg *seg1 = (SplashXPathSeg *)arg1;
387  SplashCoord x0, y0, x1, y1;
388
389  if (seg0->flags & splashXPathFlip) {
390    x0 = seg0->x1;
391    y0 = seg0->y1;
392  } else {
393    x0 = seg0->x0;
394    y0 = seg0->y0;
395  }
396  if (seg1->flags & splashXPathFlip) {
397    x1 = seg1->x1;
398    y1 = seg1->y1;
399  } else {
400    x1 = seg1->x0;
401    y1 = seg1->y0;
402  }
403  if (y0 != y1) {
404    return (y0 > y1) ? 1 : -1;
405  }
406  if (x0 != x1) {
407    return (x0 > x1) ? 1 : -1;
408  }
409  return 0;
410}
411
412void SplashXPath::sort() {
413  qsort(segs, length, sizeof(SplashXPathSeg), &cmpXPathSegs);
414}
Note: See TracBrowser for help on using the repository browser.