[thirdparty/cups.git] / pdftops / SplashXPath.cxx

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

#include <config.h>

#ifdef USE_GCC_PRAGMAS
#pragma implementation
#endif

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