]>
Commit | Line | Data |
---|---|---|
ef416fc2 | 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) { | |
bd7854cb | 189 | SplashCoord xSegMin, xSegMax, ySegMin, ySegMax, xx0, xx1; |
ef416fc2 | 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 { | |
bd7854cb | 239 | if (seg->x0 < seg->x1) { |
240 | xSegMin = seg->x0; | |
241 | xSegMax = seg->x1; | |
ef416fc2 | 242 | } else { |
bd7854cb | 243 | xSegMin = seg->x1; |
244 | xSegMax = seg->x0; | |
ef416fc2 | 245 | } |
bd7854cb | 246 | // intersection with top edge |
247 | xx0 = seg->x0 + ((SplashCoord)y - seg->y0) * seg->dxdy; | |
248 | // intersection with bottom edge | |
249 | xx1 = seg->x0 + ((SplashCoord)y + 1 - seg->y0) * seg->dxdy; | |
250 | // the segment may not actually extend to the top and/or bottom edges | |
251 | if (xx0 < xSegMin) { | |
252 | xx0 = xSegMin; | |
253 | } else if (xx0 > xSegMax) { | |
254 | xx0 = xSegMax; | |
255 | } | |
256 | if (xx1 < xSegMin) { | |
257 | xx1 = xSegMin; | |
258 | } else if (xx1 > xSegMax) { | |
259 | xx1 = xSegMax; | |
ef416fc2 | 260 | } |
261 | } | |
262 | if (xx0 < xx1) { | |
263 | inter[interLen].x0 = splashFloor(xx0); | |
264 | inter[interLen].x1 = splashFloor(xx1); | |
265 | } else { | |
266 | inter[interLen].x0 = splashFloor(xx1); | |
267 | inter[interLen].x1 = splashFloor(xx0); | |
268 | } | |
269 | if (ySegMin <= y && | |
270 | (SplashCoord)y < ySegMax && | |
271 | !(seg->flags & splashXPathHoriz)) { | |
272 | inter[interLen].count = eo ? 1 | |
273 | : (seg->flags & splashXPathFlip) ? 1 : -1; | |
274 | } else { | |
275 | inter[interLen].count = 0; | |
276 | } | |
277 | ++interLen; | |
278 | } | |
279 | ||
280 | qsort(inter, interLen, sizeof(SplashIntersect), &cmpIntersect); | |
281 | ||
282 | interY = y; | |
283 | interIdx = 0; | |
284 | interCount = 0; | |
285 | } |