splash/SplashXPath.cc

//========================================================================
//
// SplashXPath.cc
//
//========================================================================

#include <config.h>

#ifdef USE_GCC_PRAGMAS
#pragma implementation
#endif

#include <stdlib.h>
#include <string.h>
#include "goo/gmem.h"
#include "SplashMath.h"
#include "SplashPath.h"
#include "SplashXPath.h"

//------------------------------------------------------------------------

#define maxCurveSplits (1 << 10)

//------------------------------------------------------------------------
// SplashXPath
//------------------------------------------------------------------------

SplashXPath::SplashXPath() {
  segs = NULL;
  length = size = 0;
}

SplashXPath::SplashXPath(SplashPath *path, SplashCoord flatness,
			 GBool closeSubpaths) {
  SplashCoord xc, yc, dx, dy, r, x0, y0, x1, y1;
  int quad0, quad1, quad;
  int curSubpath, n, i, j;

  segs = NULL;
  length = size = 0;

  i = 0;
  curSubpath = 0;
  while (i < path->length) {

    // first point in subpath - skip it
    if (path->flags[i] & splashPathFirst) {
      curSubpath = i;
      ++i;

    } else {

      // curve segment
      if (path->flags[i] & splashPathCurve) {
	addCurve(path->pts[i-1].x, path->pts[i-1].y,
		 path->pts[i  ].x, path->pts[i  ].y,
		 path->pts[i+1].x, path->pts[i+1].y,
		 path->pts[i+2].x, path->pts[i+2].y,
		 flatness,
		 (path->flags[i-1] & splashPathFirst),
		 (path->flags[i+2] & splashPathLast),
		 !closeSubpaths &&
		   (path->flags[i-1] & splashPathFirst) &&
		   !(path->flags[i-1] & splashPathClosed),
		 !closeSubpaths &&
		   (path->flags[i+2] & splashPathLast) &&
		   !(path->flags[i+2] & splashPathClosed));
	i += 3;

      // clockwise circular arc
      } else if (path->flags[i] & splashPathArcCW) {
	xc = path->pts[i].x;
	yc = path->pts[i].y;
	dx = path->pts[i+1].x - xc;
	dy = path->pts[i+1].y - yc;
	r = splashSqrt(dx * dx + dy * dy);
	if (path->pts[i-1].x < xc && path->pts[i-1].y <= yc) {
	  quad0 = 0;
	} else if (path->pts[i-1].x >= xc && path->pts[i-1].y < yc) {
	  quad0 = 1;
	} else if (path->pts[i-1].x > xc && path->pts[i-1].y >= yc) {
	  quad0 = 2;
	} else {
	  quad0 = 3;
	}
	if (path->pts[i+1].x <= xc && path->pts[i+1].y < yc) {
	  quad1 = 0;
	} else if (path->pts[i+1].x > xc && path->pts[i+1].y <= yc) {
	  quad1 = 1;
	} else if (path->pts[i+1].x >= xc && path->pts[i+1].y > yc) {
	  quad1 = 2;
	} else {
	  quad1 = 3;
	}
	n = 0; // make gcc happy
	if (quad0 == quad1) {
	  switch (quad0) {
	  case 0:
	  case 1: n = path->pts[i-1].x < path->pts[i+1].x ? 0 : 4; break;
	  case 2:
	  case 3: n = path->pts[i-1].x > path->pts[i+1].x ? 0 : 4; break;
	  }
	} else {
	  n = (quad1 - quad0) & 3;
	}
	x0 = path->pts[i-1].x;
	y0 = path->pts[i-1].y;
	x1 = y1 = 0; // make gcc happy
	quad = quad0;
	for (j = 0; j < n; ++j) {
	  switch (quad) {
	  case 0: x1 = xc;     y1 = yc - r; break;
	  case 1: x1 = xc + r; y1 = yc;     break;
	  case 2: x1 = xc;     y1 = yc + r; break;
	  case 3: x1 = xc - r; y1 = yc;     break;
	  }
	  addArc(x0, y0, x1, y1,
		 xc, yc, r, quad, flatness,
		 quad == quad0 && (path->flags[i-1] & splashPathFirst),
		 gFalse,
		 quad == quad0 && !closeSubpaths &&
		   (path->flags[i-1] & splashPathFirst) &&
		   !(path->flags[i-1] & splashPathClosed),
		 gFalse);
	  x0 = x1;
	  y0 = y1;
	  quad = (quad + 1) & 3;
	}
	addArc(x0, y0, path->pts[i+1].x, path->pts[i+1].y,
	       xc, yc, r, quad, flatness,
	       quad == quad0 && (path->flags[i-1] & splashPathFirst),
	       (path->flags[i+1] & splashPathLast),
	       quad == quad0 && !closeSubpaths &&
	         (path->flags[i-1] & splashPathFirst) &&
	         !(path->flags[i-1] & splashPathClosed),
	       !closeSubpaths &&
	         (path->flags[i+1] & splashPathLast) &&
	         !(path->flags[i+1] & splashPathClosed));
	i += 2;

      // line segment
      } else {
	addSegment(path->pts[i-1].x, path->pts[i-1].y,
		   path->pts[i].x, path->pts[i].y,
		   path->flags[i-1] & splashPathFirst,
		   path->flags[i] & splashPathLast,
		   !closeSubpaths &&
		     (path->flags[i-1] & splashPathFirst) &&
		     !(path->flags[i-1] & splashPathClosed),
		   !closeSubpaths &&
		     (path->flags[i] & splashPathLast) &&
		     !(path->flags[i] & splashPathClosed));
	++i;
      }

      // close a subpath
      if (closeSubpaths &&
	  (path->flags[i-1] & splashPathLast) &&
	  (path->pts[i-1].x != path->pts[curSubpath].x ||
	   path->pts[i-1].y != path->pts[curSubpath]. y)) {
	addSegment(path->pts[i-1].x, path->pts[i-1].y,
		   path->pts[curSubpath].x, path->pts[curSubpath].y,
		   gFalse, gTrue, gFalse, gFalse);
      }
    }
  }
}

SplashXPath::SplashXPath(SplashXPath *xPath) {
  length = xPath->length;
  size = xPath->size;
  segs = (SplashXPathSeg *)gmallocn(size, sizeof(SplashXPathSeg));
  memcpy(segs, xPath->segs, length * sizeof(SplashXPathSeg));
}

SplashXPath::~SplashXPath() {
  gfree(segs);
}

// Add space for <nSegs> more segments
void SplashXPath::grow(int nSegs) {
  if (length + nSegs > size) {
    if (size == 0) {
      size = 32;
    }
    while (size < length + nSegs) {
      size *= 2;
    }
    segs = (SplashXPathSeg *)greallocn(segs, size, sizeof(SplashXPathSeg));
  }
}

void SplashXPath::addCurve(SplashCoord x0, SplashCoord y0,
			   SplashCoord x1, SplashCoord y1,
			   SplashCoord x2, SplashCoord y2,
			   SplashCoord x3, SplashCoord y3,
			   SplashCoord flatness,
			   GBool first, GBool last, GBool end0, GBool end1) {
  SplashCoord cx[maxCurveSplits + 1][3];
  SplashCoord cy[maxCurveSplits + 1][3];
  int cNext[maxCurveSplits + 1];
  SplashCoord xl0, xl1, xl2, xr0, xr1, xr2, xr3, xx1, xx2, xh;
  SplashCoord yl0, yl1, yl2, yr0, yr1, yr2, yr3, yy1, yy2, yh;
  SplashCoord dx, dy, mx, my, d1, d2, flatness2;
  int p1, p2, p3;

  flatness2 = flatness * flatness;

  // initial segment
  p1 = 0;
  p2 = maxCurveSplits;
  cx[p1][0] = x0;  cy[p1][0] = y0;
  cx[p1][1] = x1;  cy[p1][1] = y1;
  cx[p1][2] = x2;  cy[p1][2] = y2;
  cx[p2][0] = x3;  cy[p2][0] = y3;
  cNext[p1] = p2;

  while (p1 < maxCurveSplits) {

    // get the next segment
    xl0 = cx[p1][0];  yl0 = cy[p1][0];
    xx1 = cx[p1][1];  yy1 = cy[p1][1];
    xx2 = cx[p1][2];  yy2 = cy[p1][2];
    p2 = cNext[p1];
    xr3 = cx[p2][0];  yr3 = cy[p2][0];

    // compute the distances from the control points to the
    // midpoint of the straight line (this is a bit of a hack, but
    // it's much faster than computing the actual distances to the
    // line)
    mx = (xl0 + xr3) * 0.5;
    my = (yl0 + yr3) * 0.5;
    dx = xx1 - mx;
    dy = yy1 - my;
    d1 = dx*dx + dy*dy;
    dx = xx2 - mx;
    dy = yy2 - my;
    d2 = dx*dx + dy*dy;

    // if the curve is flat enough, or no more subdivisions are
    // allowed, add the straight line segment
    if (p2 - p1 == 1 || (d1 <= flatness2 && d2 <= flatness2)) {
      addSegment(xl0, yl0, xr3, yr3,
		 p1 == 0 && first,
		 p2 == maxCurveSplits && last,
		 p1 == 0 && end0,
		 p2 == maxCurveSplits && end1);
      p1 = p2;

    // otherwise, subdivide the curve
    } else {
      xl1 = (xl0 + xx1) * 0.5;
      yl1 = (yl0 + yy1) * 0.5;
      xh = (xx1 + xx2) * 0.5;
      yh = (yy1 + yy2) * 0.5;
      xl2 = (xl1 + xh) * 0.5;
      yl2 = (yl1 + yh) * 0.5;
      xr2 = (xx2 + xr3) * 0.5;
      yr2 = (yy2 + yr3) * 0.5;
      xr1 = (xh + xr2) * 0.5;
      yr1 = (yh + yr2) * 0.5;
      xr0 = (xl2 + xr1) * 0.5;
      yr0 = (yl2 + yr1) * 0.5;
      // add the new subdivision points
      p3 = (p1 + p2) / 2;
      cx[p1][1] = xl1;  cy[p1][1] = yl1;
      cx[p1][2] = xl2;  cy[p1][2] = yl2;
      cNext[p1] = p3;
      cx[p3][0] = xr0;  cy[p3][0] = yr0;
      cx[p3][1] = xr1;  cy[p3][1] = yr1;
      cx[p3][2] = xr2;  cy[p3][2] = yr2;
      cNext[p3] = p2;
    }
  }
}

void SplashXPath::addArc(SplashCoord x0, SplashCoord y0,
			 SplashCoord x1, SplashCoord y1,
			 SplashCoord xc, SplashCoord yc,
			 SplashCoord r, int quad,
			 SplashCoord flatness,
			 GBool first, GBool last, GBool end0, GBool end1) {
  SplashCoord px[maxCurveSplits + 1];
  SplashCoord py[maxCurveSplits + 1];
  int pNext[maxCurveSplits + 1];
  SplashCoord r2, flatness2;
  SplashCoord xx0, yy0, xx1, yy1, xm, ym, t, dx, dy;
  int p1, p2, p3;

  r2 = r * r;
  flatness2 = flatness * flatness;

  // initial segment
  p1 = 0;
  p2 = maxCurveSplits;
  px[p1] = x0;  py[p1] = y0;
  px[p2] = x1;  py[p2] = y1;
  pNext[p1] = p2;

  while (p1 < maxCurveSplits) {

    // get the next segment
    xx0 = px[p1];  yy0 = py[p1];
    p2 = pNext[p1];
    xx1 = px[p2];  yy1 = py[p2];

    // compute the arc midpoint
    t = (xx0 - xc) * (xx1 - xc) - (yy0 - yc) * (yy1 - yc);
    xm = splashSqrt((SplashCoord)0.5 * (r2 + t));
    ym = splashSqrt((SplashCoord)0.5 * (r2 - t));
    switch (quad) {
    case 0: xm = xc - xm;  ym = yc - ym;  break;
    case 1: xm = xc + xm;  ym = yc - ym;  break;
    case 2: xm = xc + xm;  ym = yc + ym;  break;
    case 3: xm = xc - xm;  ym = yc + ym;  break;
    }

    // compute distance from midpoint of straight segment to midpoint
    // of arc
    dx = (SplashCoord)0.5 * (xx0 + xx1) - xm;
    dy = (SplashCoord)0.5 * (yy0 + yy1) - ym;

    // if the arc is flat enough, or no more subdivisions are allowed,
    // add the straight line segment
    if (p2 - p1 == 1 || dx * dx + dy * dy <= flatness2) {
      addSegment(xx0, yy0, xx1, yy1,
		 p1 == 0 && first,
		 p2 == maxCurveSplits && last,
		 p1 == 0 && end0,
		 p2 == maxCurveSplits && end1);
      p1 = p2;

    // otherwise, subdivide the arc
    } else {
      p3 = (p1 + p2) / 2;
      px[p3] = xm;
      py[p3] = ym;
      pNext[p1] = p3;
      pNext[p3] = p2;
    }
  }
}

void SplashXPath::addSegment(SplashCoord x0, SplashCoord y0,
			     SplashCoord x1, SplashCoord y1,
			     GBool first, GBool last, GBool end0, GBool end1) {
  grow(1);
  segs[length].x0 = x0;
  segs[length].y0 = y0;
  segs[length].x1 = x1;
  segs[length].y1 = y1;
  segs[length].flags = 0;
  if (first) {
    segs[length].flags |= splashXPathFirst;
  }
  if (last) {
    segs[length].flags |= splashXPathLast;
  }
  if (end0) {
    segs[length].flags |= splashXPathEnd0;
  }
  if (end1) {
    segs[length].flags |= splashXPathEnd1;
  }
  if (y1 == y0) {
    segs[length].dxdy = segs[length].dydx = 0;
    segs[length].flags |= splashXPathHoriz;
    if (x1 == x0) {
      segs[length].flags |= splashXPathVert;
    }
  } else if (x1 == x0) {
    segs[length].dxdy = segs[length].dydx = 0;
    segs[length].flags |= splashXPathVert;
  } else {
    segs[length].dxdy = (x1 - x0) / (y1 - y0);
    segs[length].dydx = (SplashCoord)1 / segs[length].dxdy;
  }
  if (y0 > y1) {
    segs[length].flags |= splashXPathFlip;
  }
  ++length;
}

static int cmpXPathSegs(const void *arg0, const void *arg1) {
  SplashXPathSeg *seg0 = (SplashXPathSeg *)arg0;
  SplashXPathSeg *seg1 = (SplashXPathSeg *)arg1;
  SplashCoord x0, y0, x1, y1;

  if (seg0->flags & splashXPathFlip) {
    x0 = seg0->x1;
    y0 = seg0->y1;
  } else {
    x0 = seg0->x0;
    y0 = seg0->y0;
  }
  if (seg1->flags & splashXPathFlip) {
    x1 = seg1->x1;
    y1 = seg1->y1;
  } else {
    x1 = seg1->x0;
    y1 = seg1->y0;
  }
  if (y0 != y1) {
    return (y0 > y1) ? 1 : -1;
  }
  if (x0 != x1) {
    return (x0 > x1) ? 1 : -1;
  }
  return 0;
}

void SplashXPath::sort() {
  qsort(segs, length, sizeof(SplashXPathSeg), &cmpXPathSegs);
}