Load cups into easysw/current.
[thirdparty/cups.git] / pdftops / SplashXPath.cxx
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 "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
28 SplashXPath::SplashXPath() {
29   segs = NULL;
30   length = size = 0;
31 }
32
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;
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[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,
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
169 SplashXPath::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
176 SplashXPath::~SplashXPath() {
177   gfree(segs);
178 }
179
180 // Add space for <nSegs> more segments
181 void 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
193 void 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
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 void 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
384 static 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
412 void SplashXPath::sort() {
413   qsort(segs, length, sizeof(SplashXPathSeg), &cmpXPathSegs);
414 }