source: trunk/poppler/mypoppler/splash/SplashXPathScanner.cc @ 44

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

First import

File size: 6.4 KB
Line 
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 "goo/gmem.h"
15#include "SplashMath.h"
16#include "SplashXPath.h"
17#include "SplashXPathScanner.h"
18
19//------------------------------------------------------------------------
20
21struct SplashIntersect {
22  int x0, x1;                   // intersection of segment with [y, y+1)
23  int count;                    // EO/NZWN counter increment
24};
25
26static int cmpIntersect(const void *p0, const void *p1) {
27  return ((SplashIntersect *)p0)->x0 - ((SplashIntersect *)p1)->x0;
28}
29
30//------------------------------------------------------------------------
31// SplashXPathScanner
32//------------------------------------------------------------------------
33
34SplashXPathScanner::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
96SplashXPathScanner::~SplashXPathScanner() {
97  gfree(inter);
98}
99
100void 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
113GBool 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
129GBool 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
161GBool 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
188void SplashXPathScanner::computeIntersections(int y) {
189  SplashCoord xSegMin, xSegMax, 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 (seg->x0 < seg->x1) {
240        xSegMin = seg->x0;
241        xSegMax = seg->x1;
242      } else {
243        xSegMin = seg->x1;
244        xSegMax = seg->x0;
245      }
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;
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}
Note: See TracBrowser for help on using the repository browser.