pdf/splash/SplashXPathScanner.cc

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