rosapps/smartpdf/poppler/splash/SplashXPathScanner.cc

   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
  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 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 }