Load cups into easysw/current.
[thirdparty/cups.git] / pdftops / SplashXPathScanner.cxx
1 //========================================================================
2 //
3 // SplashXPathScanner.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 "gmem.h"
15 #include "SplashMath.h"
16 #include "SplashXPath.h"
17 #include "SplashXPathScanner.h"
18
19 //------------------------------------------------------------------------
20
21 struct SplashIntersect {
22   int x0, x1;                   // intersection of segment with [y, y+1)
23   int count;                    // EO/NZWN counter increment
24 };
25
26 static int cmpIntersect(const void *p0, const void *p1) {
27   return ((SplashIntersect *)p0)->x0 - ((SplashIntersect *)p1)->x0;
28 }
29
30 //------------------------------------------------------------------------
31 // SplashXPathScanner
32 //------------------------------------------------------------------------
33
34 SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA) {
35   SplashXPathSeg *seg;
36   SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
37   int i;
38
39   xPath = xPathA;
40   eo = eoA;
41
42   // compute the bbox
43   if (xPath->length == 0) {
44     xMin = yMin = 1;
45     xMax = yMax = 0;
46   } else {
47     seg = &xPath->segs[0];
48     if (seg->x0 <= seg->x1) {
49       xMinFP = seg->x0;
50       xMaxFP = seg->x1;
51     } else {
52       xMinFP = seg->x1;
53       xMaxFP = seg->x0;
54     }
55     if (seg->flags & splashXPathFlip) {
56       yMinFP = seg->y1;
57       yMaxFP = seg->y0;
58     } else {
59       yMinFP = seg->y0;
60       yMaxFP = seg->y1;
61     }
62     for (i = 1; i < xPath->length; ++i) {
63       seg = &xPath->segs[i];
64       if (seg->x0 < xMinFP) {
65         xMinFP = seg->x0;
66       } else if (seg->x0 > xMaxFP) {
67         xMaxFP = seg->x0;
68       }
69       if (seg->x1 < xMinFP) {
70         xMinFP = seg->x1;
71       } else if (seg->x1 > xMaxFP) {
72         xMaxFP = seg->x1;
73       }
74       if (seg->flags & splashXPathFlip) {
75         if (seg->y0 > yMaxFP) {
76           yMaxFP = seg->y0;
77         }
78       } else {
79         if (seg->y1 > yMaxFP) {
80           yMaxFP = seg->y1;
81         }
82       }
83     }
84     xMin = splashFloor(xMinFP);
85     xMax = splashFloor(xMaxFP);
86     yMin = splashFloor(yMinFP);
87     yMax = splashFloor(yMaxFP);
88   }
89
90   interY = yMin - 1;
91   xPathIdx = 0;
92   inter = NULL;
93   interLen = interSize = 0;
94 }
95
96 SplashXPathScanner::~SplashXPathScanner() {
97   gfree(inter);
98 }
99
100 void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) {
101   if (interY != y) {
102     computeIntersections(y);
103   }
104   if (interLen > 0) {
105     *spanXMin = inter[0].x0;
106     *spanXMax = inter[interLen - 1].x1;
107   } else {
108     *spanXMin = xMax + 1;
109     *spanXMax = xMax;
110   }
111 }
112
113 GBool SplashXPathScanner::test(int x, int y) {
114   int count, i;
115
116   if (interY != y) {
117     computeIntersections(y);
118   }
119   count = 0;
120   for (i = 0; i < interLen && inter[i].x0 <= x; ++i) {
121     if (x <= inter[i].x1) {
122       return gTrue;
123     }
124     count += inter[i].count;
125   }
126   return eo ? (count & 1) : (count != 0);
127 }
128
129 GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
130   int count, xx1, i;
131
132   if (interY != y) {
133     computeIntersections(y);
134   }
135
136   count = 0;
137   for (i = 0; i < interLen && inter[i].x1 < x0; ++i) {
138     count += inter[i].count;
139   }
140
141   // invariant: the subspan [x0,xx1] is inside the path
142   xx1 = x0 - 1;
143   while (xx1 < x1) {
144     if (i >= interLen) {
145       return gFalse;
146     }
147     if (inter[i].x0 > xx1 + 1 &&
148         !(eo ? (count & 1) : (count != 0))) {
149       return gFalse;
150     }
151     if (inter[i].x1 > xx1) {
152       xx1 = inter[i].x1;
153     }
154     count += inter[i].count;
155     ++i;
156   }
157
158   return gTrue;
159 }
160
161 GBool SplashXPathScanner::getNextSpan(int y, int *x0, int *x1) {
162   int xx0, xx1;
163
164   if (interY != y) {
165     computeIntersections(y);
166   }
167   if (interIdx >= interLen) {
168     return gFalse;
169   }
170   xx0 = inter[interIdx].x0;
171   xx1 = inter[interIdx].x1;
172   interCount += inter[interIdx].count;
173   ++interIdx;
174   while (interIdx < interLen &&
175          (inter[interIdx].x0 <= xx1 ||
176           (eo ? (interCount & 1) : (interCount != 0)))) {
177     if (inter[interIdx].x1 > xx1) {
178       xx1 = inter[interIdx].x1;
179     }
180     interCount += inter[interIdx].count;
181     ++interIdx;
182   }
183   *x0 = xx0;
184   *x1 = xx1;
185   return gTrue;
186 }
187
188 void SplashXPathScanner::computeIntersections(int y) {
189   SplashCoord ySegMin, ySegMax, xx0, xx1;
190   SplashXPathSeg *seg;
191   int i, j;
192
193   // find the first segment that intersects [y, y+1)
194   i = (y >= interY) ? xPathIdx : 0;
195   while (i < xPath->length &&
196          xPath->segs[i].y0 < y && xPath->segs[i].y1 < y) {
197     ++i;
198   }
199   xPathIdx = i;
200
201   // find all of the segments that intersect [y, y+1) and create an
202   // Intersect element for each one
203   interLen = 0;
204   for (j = i; j < xPath->length; ++j) {
205     seg = &xPath->segs[j];
206     if (seg->flags & splashXPathFlip) {
207       ySegMin = seg->y1;
208       ySegMax = seg->y0;
209     } else {
210       ySegMin = seg->y0;
211       ySegMax = seg->y1;
212     }
213
214     // ensure that:      ySegMin < y+1
215     //              y <= ySegMax
216     if (ySegMin >= y + 1) {
217       break;
218     }
219     if (ySegMax < y) {
220       continue;
221     }
222
223     if (interLen == interSize) {
224       if (interSize == 0) {
225         interSize = 16;
226       } else {
227         interSize *= 2;
228       }
229       inter = (SplashIntersect *)greallocn(inter, interSize,
230                                            sizeof(SplashIntersect));
231     }
232
233     if (seg->flags & splashXPathHoriz) {
234       xx0 = seg->x0;
235       xx1 = seg->x1;
236     } else if (seg->flags & splashXPathVert) {
237       xx0 = xx1 = seg->x0;
238     } else {
239       if (ySegMin <= y) {
240         // intersection with top edge
241         xx0 = seg->x0 + ((SplashCoord)y - seg->y0) * seg->dxdy;
242       } else {
243         // x coord of segment endpoint with min y coord
244         xx0 = (seg->flags & splashXPathFlip) ? seg->x1 : seg->x0;
245       }
246       if (ySegMax >= y + 1) {
247         // intersection with bottom edge
248         xx1 = seg->x0 + ((SplashCoord)y + 1 - seg->y0) * seg->dxdy;
249       } else {
250         // x coord of segment endpoint with max y coord
251         xx1 = (seg->flags & splashXPathFlip) ? seg->x0 : seg->x1;
252       }
253     }
254     if (xx0 < xx1) {
255       inter[interLen].x0 = splashFloor(xx0);
256       inter[interLen].x1 = splashFloor(xx1);
257     } else {
258       inter[interLen].x0 = splashFloor(xx1);
259       inter[interLen].x1 = splashFloor(xx0);
260     }
261     if (ySegMin <= y &&
262         (SplashCoord)y < ySegMax &&
263         !(seg->flags & splashXPathHoriz)) {
264       inter[interLen].count = eo ? 1
265                                  : (seg->flags & splashXPathFlip) ? 1 : -1;
266     } else {
267       inter[interLen].count = 0;
268     }
269     ++interLen;
270   }
271
272   qsort(inter, interLen, sizeof(SplashIntersect), &cmpIntersect);
273
274   interY = y;
275   interIdx = 0;
276   interCount = 0;
277 }