pdf/splash/SplashXPath.cc

   1 //========================================================================
   2 //
   3 // SplashXPath.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 <string.h>
  15 #include "gmem.h"
  16 #include "SplashMath.h"
  17 #include "SplashPath.h"
  18 #include "SplashXPath.h"
  19
  20 //------------------------------------------------------------------------
  21
  22 #define maxCurveSplits (1 << 10)
  23
  24 //------------------------------------------------------------------------
  25 // SplashXPath
  26 //------------------------------------------------------------------------
  27
  28 SplashXPath::SplashXPath() {
  29   segs = NULL;
  30   length = size = 0;
  31 }
  32
  33 SplashXPath::SplashXPath(SplashPath *path, SplashCoord flatness,
  34                          GBool closeSubpaths) {
  35   SplashCoord xc, yc, dx, dy, r, x0, y0, x1, y1;
  36   int quad0, quad1, quad;
  37   int i, curSubpath;
  38   GBool last;
  39
  40   segs = NULL;
  41   length = size = 0;
  42
  43   i = 0;
  44   curSubpath = 0;
  45   while (i < path->length) {
  46
  47     // first point in subpath - skip it
  48     if (path->flags[i] & splashPathFirst) {
  49       curSubpath = i;
  50       ++i;
  51
  52     } else {
  53
  54       // curve segment
  55       if (path->flags[i] & splashPathCurve) {
  56         addCurve(path->pts[i-1].x, path->pts[i-1].y,
  57                  path->pts[i  ].x, path->pts[i  ].y,
  58                  path->pts[i+1].x, path->pts[i+1].y,
  59                  path->pts[i+2].x, path->pts[i+2].y,
  60                  flatness,
  61                  (path->flags[i-1] & splashPathFirst),
  62                  (path->flags[i+2] & splashPathLast),
  63                  !closeSubpaths &&
  64                    (path->flags[i-1] & splashPathFirst) &&
  65                    !(path->flags[i-1] & splashPathClosed),
  66                  !closeSubpaths &&
  67                    (path->flags[i+2] & splashPathLast) &&
  68                    !(path->flags[i+2] & splashPathClosed));
  69         i += 3;
  70
  71       // clockwise circular arc
  72       } else if (path->flags[i] & splashPathArcCW) {
  73         xc = path->pts[i].x;
  74         yc = path->pts[i].y;
  75         dx = path->pts[i+1].x - xc;
  76         dy = path->pts[i+1].y - yc;
  77         r = splashSqrt(dx * dx + dy * dy);
  78         if (path->pts[i-1].x < xc && path->pts[i-1].y <= yc) {
  79           quad0 = 0;
  80         } else if (path->pts[i-1].x >= xc && path->pts[i-1].y < yc) {
  81           quad0 = 1;
  82         } else if (path->pts[i-1].x > xc && path->pts[i-1].y >= yc) {
  83           quad0 = 2;
  84         } else {
  85           quad0 = 3;
  86         }
  87         if (path->pts[i+1].x <= xc && path->pts[i+1].y < yc) {
  88           quad1 = 0;
  89         } else if (path->pts[i+1].x > xc && path->pts[i+1].y <= yc) {
  90           quad1 = 1;
  91         } else if (path->pts[i+1].x >= xc && path->pts[i+1].y > yc) {
  92           quad1 = 2;
  93         } else {
  94           quad1 = 3;
  95         }
  96         x0 = path->pts[i-1].x;
  97         y0 = path->pts[i-1].y;
  98         x1 = y1 = 0; // make gcc happy
  99         quad = quad0;
 100         while (1) {
 101           switch (quad) {
 102           case 0: x1 = xc;     y1 = yc - r; break;
 103           case 1: x1 = xc + r; y1 = yc;     break;
 104           case 2: x1 = xc;     y1 = yc + r; break;
 105           case 3: x1 = xc - r; y1 = yc;     break;
 106           }
 107           last = gFalse;
 108           if (quad == quad1) {
 109             switch (quad) {
 110             case 0:
 111             case 1: last = path->pts[i+1].x > x0; break;
 112             case 2:
 113             case 3: last = path->pts[i+1].x < x0; break;
 114             }
 115           }
 116           if (last) {
 117             addArc(x0, y0, path->pts[i+1].x, path->pts[i+1].y,
 118                    xc, yc, r, quad, flatness,
 119                    quad == quad0 && (path->flags[i-1] & splashPathFirst),
 120                    (path->flags[i+1] & splashPathLast),
 121                    quad == quad0 && !closeSubpaths &&
 122                      (path->flags[i-1] & splashPathFirst) &&
 123                      !(path->flags[i-1] & splashPathClosed),
 124                    !closeSubpaths &&
 125                      (path->flags[i+1] & splashPathLast) &&
 126                      !(path->flags[i+1] & splashPathClosed));
 127             break;
 128           } else {
 129             addArc(x0, y0, x1, y1,
 130                    xc, yc, r, quad, flatness,
 131                    quad == quad0 && (path->flags[i-1] & splashPathFirst),
 132                    gFalse,
 133                    quad == quad0 && !closeSubpaths &&
 134                      (path->flags[i-1] & splashPathFirst) &&
 135                      !(path->flags[i-1] & splashPathClosed),
 136                    gFalse);
 137             x0 = x1;
 138             y0 = y1;
 139             quad = (quad + 1) & 3;
 140           }
 141         }
 142         i += 2;
 143
 144       // line segment
 145       } else {
 146         addSegment(path->pts[i-1].x, path->pts[i-1].y,
 147                    path->pts[i].x, path->pts[i].y,
 148                    path->flags[i-1] & splashPathFirst,
 149                    path->flags[i] & splashPathLast,
 150                    !closeSubpaths &&
 151                      (path->flags[i-1] & splashPathFirst) &&
 152                      !(path->flags[i-1] & splashPathClosed),
 153                    !closeSubpaths &&
 154                      (path->flags[i] & splashPathLast) &&
 155                      !(path->flags[i] & splashPathClosed));
 156         ++i;
 157       }
 158
 159       // close a subpath
 160       if (closeSubpaths &&
 161           (path->flags[i-1] & splashPathLast) &&
 162           (path->pts[i-1].x != path->pts[curSubpath].x ||
 163            path->pts[i-1].y != path->pts[curSubpath]. y)) {
 164         addSegment(path->pts[i-1].x, path->pts[i-1].y,
 165                    path->pts[curSubpath].x, path->pts[curSubpath].y,
 166                    gFalse, gTrue, gFalse, gFalse);
 167       }
 168     }
 169   }
 170 }
 171
 172 SplashXPath::SplashXPath(SplashXPath *xPath) {
 173   length = xPath->length;
 174   size = xPath->size;
 175   segs = (SplashXPathSeg *)gmalloc(size * sizeof(SplashXPathSeg));
 176   memcpy(segs, xPath->segs, length * sizeof(SplashXPathSeg));
 177 }
 178
 179 SplashXPath::~SplashXPath() {
 180   gfree(segs);
 181 }
 182
 183 // Add space for <nSegs> more segments
 184 void SplashXPath::grow(int nSegs) {
 185   if (length + nSegs > size) {
 186     if (size == 0) {
 187       size = 32;
 188     }
 189     while (size < length + nSegs) {
 190       size *= 2;
 191     }
 192     segs = (SplashXPathSeg *)grealloc(segs, size * sizeof(SplashXPathSeg));
 193   }
 194 }
 195
 196 void SplashXPath::addCurve(SplashCoord x0, SplashCoord y0,
 197                            SplashCoord x1, SplashCoord y1,
 198                            SplashCoord x2, SplashCoord y2,
 199                            SplashCoord x3, SplashCoord y3,
 200                            SplashCoord flatness,
 201                            GBool first, GBool last, GBool end0, GBool end1) {
 202   SplashCoord cx[maxCurveSplits + 1][3];
 203   SplashCoord cy[maxCurveSplits + 1][3];
 204   int cNext[maxCurveSplits + 1];
 205   SplashCoord xl0, xl1, xl2, xr0, xr1, xr2, xr3, xx1, xx2, xh;
 206   SplashCoord yl0, yl1, yl2, yr0, yr1, yr2, yr3, yy1, yy2, yh;
 207   SplashCoord dx, dy, mx, my, d1, d2, flatness2;
 208   int p1, p2, p3;
 209
 210   flatness2 = flatness * flatness;
 211
 212   // initial segment
 213   p1 = 0;
 214   p2 = maxCurveSplits;
 215   cx[p1][0] = x0;  cy[p1][0] = y0;
 216   cx[p1][1] = x1;  cy[p1][1] = y1;
 217   cx[p1][2] = x2;  cy[p1][2] = y2;
 218   cx[p2][0] = x3;  cy[p2][0] = y3;
 219   cNext[p1] = p2;
 220
 221   while (p1 < maxCurveSplits) {
 222
 223     // get the next segment
 224     xl0 = cx[p1][0];  yl0 = cy[p1][0];
 225     xx1 = cx[p1][1];  yy1 = cy[p1][1];
 226     xx2 = cx[p1][2];  yy2 = cy[p1][2];
 227     p2 = cNext[p1];
 228     xr3 = cx[p2][0];  yr3 = cy[p2][0];
 229
 230     // compute the distances from the control points to the
 231     // midpoint of the straight line (this is a bit of a hack, but
 232     // it's much faster than computing the actual distances to the
 233     // line)
 234     mx = (xl0 + xr3) * 0.5;
 235     my = (yl0 + yr3) * 0.5;
 236     dx = xx1 - mx;
 237     dy = yy1 - my;
 238     d1 = dx*dx + dy*dy;
 239     dx = xx2 - mx;
 240     dy = yy2 - my;
 241     d2 = dx*dx + dy*dy;
 242
 243     // if the curve is flat enough, or no more subdivisions are
 244     // allowed, add the straight line segment
 245     if (p2 - p1 == 1 || (d1 <= flatness2 && d2 <= flatness2)) {
 246       addSegment(xl0, yl0, xr3, yr3,
 247                  p1 == 0 && first,
 248                  p2 == maxCurveSplits && last,
 249                  p1 == 0 && end0,
 250                  p2 == maxCurveSplits && end1);
 251       p1 = p2;
 252
 253     // otherwise, subdivide the curve
 254     } else {
 255       xl1 = (xl0 + xx1) * 0.5;
 256       yl1 = (yl0 + yy1) * 0.5;
 257       xh = (xx1 + xx2) * 0.5;
 258       yh = (yy1 + yy2) * 0.5;
 259       xl2 = (xl1 + xh) * 0.5;
 260       yl2 = (yl1 + yh) * 0.5;
 261       xr2 = (xx2 + xr3) * 0.5;
 262       yr2 = (yy2 + yr3) * 0.5;
 263       xr1 = (xh + xr2) * 0.5;
 264       yr1 = (yh + yr2) * 0.5;
 265       xr0 = (xl2 + xr1) * 0.5;
 266       yr0 = (yl2 + yr1) * 0.5;
 267       // add the new subdivision points
 268       p3 = (p1 + p2) / 2;
 269       cx[p1][1] = xl1;  cy[p1][1] = yl1;
 270       cx[p1][2] = xl2;  cy[p1][2] = yl2;
 271       cNext[p1] = p3;
 272       cx[p3][0] = xr0;  cy[p3][0] = yr0;
 273       cx[p3][1] = xr1;  cy[p3][1] = yr1;
 274       cx[p3][2] = xr2;  cy[p3][2] = yr2;
 275       cNext[p3] = p2;
 276     }
 277   }
 278 }
 279
 280 void SplashXPath::addArc(SplashCoord x0, SplashCoord y0,
 281                          SplashCoord x1, SplashCoord y1,
 282                          SplashCoord xc, SplashCoord yc,
 283                          SplashCoord r, int quad,
 284                          SplashCoord flatness,
 285                          GBool first, GBool last, GBool end0, GBool end1) {
 286   SplashCoord px[maxCurveSplits + 1];
 287   SplashCoord py[maxCurveSplits + 1];
 288   int pNext[maxCurveSplits + 1];
 289   SplashCoord r2, flatness2;
 290   SplashCoord xx0, yy0, xx1, yy1, xm, ym, t, dx, dy;
 291   int p1, p2, p3;
 292
 293   r2 = r * r;
 294   flatness2 = flatness * flatness;
 295
 296   // initial segment
 297   p1 = 0;
 298   p2 = maxCurveSplits;
 299   px[p1] = x0;  py[p1] = y0;
 300   px[p2] = x1;  py[p2] = y1;
 301   pNext[p1] = p2;
 302
 303   while (p1 < maxCurveSplits) {
 304
 305     // get the next segment
 306     xx0 = px[p1];  yy0 = py[p1];
 307     p2 = pNext[p1];
 308     xx1 = px[p2];  yy1 = py[p2];
 309
 310     // compute the arc midpoint
 311     t = (xx0 - xc) * (xx1 - xc) - (yy0 - yc) * (yy1 - yc);
 312     xm = splashSqrt(0.5 * (r2 + t));
 313     ym = splashSqrt(0.5 * (r2 - t));
 314     switch (quad) {
 315     case 0: xm = xc - xm;  ym = yc - ym;  break;
 316     case 1: xm = xc + xm;  ym = yc - ym;  break;
 317     case 2: xm = xc + xm;  ym = yc + ym;  break;
 318     case 3: xm = xc - xm;  ym = yc + ym;  break;
 319     }
 320
 321     // compute distance from midpoint of straight segment to midpoint
 322     // of arc
 323     dx = 0.5 * (xx0 + xx1) - xm;
 324     dy = 0.5 * (yy0 + yy1) - ym;
 325
 326     // if the arc is flat enough, or no more subdivisions are allowed,
 327     // add the straight line segment
 328     if (p2 - p1 == 1 || dx * dx + dy * dy <= flatness2) {
 329       addSegment(xx0, yy0, xx1, yy1,
 330                  p1 == 0 && first,
 331                  p2 == maxCurveSplits && last,
 332                  p1 == 0 && end0,
 333                  p2 == maxCurveSplits && end1);
 334       p1 = p2;
 335
 336     // otherwise, subdivide the arc
 337     } else {
 338       p3 = (p1 + p2) / 2;
 339       px[p3] = xm;
 340       py[p3] = ym;
 341       pNext[p1] = p3;
 342       pNext[p3] = p2;
 343     }
 344   }
 345 }
 346
 347 void SplashXPath::addSegment(SplashCoord x0, SplashCoord y0,
 348                              SplashCoord x1, SplashCoord y1,
 349                              GBool first, GBool last, GBool end0, GBool end1) {
 350   grow(1);
 351   segs[length].x0 = x0;
 352   segs[length].y0 = y0;
 353   segs[length].x1 = x1;
 354   segs[length].y1 = y1;
 355   segs[length].flags = 0;
 356   if (first) {
 357     segs[length].flags |= splashXPathFirst;
 358   }
 359   if (last) {
 360     segs[length].flags |= splashXPathLast;
 361   }
 362   if (end0) {
 363     segs[length].flags |= splashXPathEnd0;
 364   }
 365   if (end1) {
 366     segs[length].flags |= splashXPathEnd1;
 367   }
 368   if (y1 == y0) {
 369     segs[length].dxdy = segs[length].dydx = 0;
 370     segs[length].flags |= splashXPathHoriz;
 371     if (x1 == x0) {
 372       segs[length].flags |= splashXPathVert;
 373     }
 374   } else if (x1 == x0) {
 375     segs[length].dxdy = segs[length].dydx = 0;
 376     segs[length].flags |= splashXPathVert;
 377   } else {
 378     segs[length].dxdy = (x1 - x0) / (y1 - y0);
 379     segs[length].dydx = 1 / segs[length].dxdy;
 380   }
 381   if (y0 > y1) {
 382     segs[length].flags |= splashXPathFlip;
 383   }
 384   ++length;
 385 }
 386
 387 static int cmpXPathSegs(const void *arg0, const void *arg1) {
 388   SplashXPathSeg *seg0 = (SplashXPathSeg *)arg0;
 389   SplashXPathSeg *seg1 = (SplashXPathSeg *)arg1;
 390   SplashCoord x0, y0, x1, y1;
 391
 392   if (seg0->flags & splashXPathFlip) {
 393     x0 = seg0->x1;
 394     y0 = seg0->y1;
 395   } else {
 396     x0 = seg0->x0;
 397     y0 = seg0->y0;
 398   }
 399   if (seg1->flags & splashXPathFlip) {
 400     x1 = seg1->x1;
 401     y1 = seg1->y1;
 402   } else {
 403     x1 = seg1->x0;
 404     y1 = seg1->y0;
 405   }
 406   if (y0 != y1) {
 407     return (y0 > y1) ? 1 : -1;
 408   }
 409   if (x0 != x1) {
 410     return (x0 > x1) ? 1 : -1;
 411   }
 412   return 0;
 413 }
 414
 415 void SplashXPath::sort() {
 416   qsort(segs, length, sizeof(SplashXPathSeg), &cmpXPathSegs);
 417 }