+void Gfx::opShFill(Object args[], int numArgs) {
+ GfxShading *shading;
+ double xMin, yMin, xMax, yMax;
+
+ if (!(shading = res->lookupShading(args[0].getName()))) {
+ return;
+ }
+
+ // save current graphics state
+ out->saveState(state);
+ state = state->save();
+
+ // clip to bbox
+ if (shading->getHasBBox()) {
+ shading->getBBox(&xMin, &yMin, &xMax, &yMax);
+ state->moveTo(xMin, yMin);
+ state->lineTo(xMax, yMin);
+ state->lineTo(xMax, yMax);
+ state->lineTo(xMin, yMax);
+ state->closePath();
+ state->clip();
+ out->clip(state);
+ state->clearPath();
+ }
+
+ // set the color space
+ state->setFillColorSpace(shading->getColorSpace()->copy());
+
+ // do shading type-specific operations
+ switch (shading->getType()) {
+ case 2:
+ doAxialShFill((GfxAxialShading *)shading);
+ break;
+ case 3:
+ doRadialShFill((GfxRadialShading *)shading);
+ break;
+ }
+
+ // restore graphics state
+ state = state->restore();
+ out->restoreState(state);
+
+ delete shading;
+}
+
+void Gfx::doAxialShFill(GfxAxialShading *shading) {
+ double xMin, yMin, xMax, yMax;
+ double x0, y0, x1, y1;
+ double dx, dy, mul;
+ double tMin, tMax, t, tx, ty;
+ double s[4], sMin, sMax, tmp;
+ double ux0, uy0, ux1, uy1, vx0, vy0, vx1, vy1;
+ double t0, t1, tt;
+ double ta[axialMaxSplits + 1];
+ int next[axialMaxSplits + 1];
+ GfxColor color0, color1;
+ int nComps;
+ int i, j, k, kk;
+
+ // get the clip region bbox
+ state->getUserClipBBox(&xMin, &yMin, &xMax, &yMax);
+
+ // compute min and max t values, based on the four corners of the
+ // clip region bbox
+ shading->getCoords(&x0, &y0, &x1, &y1);
+ dx = x1 - x0;
+ dy = y1 - y0;
+ mul = 1 / (dx * dx + dy * dy);
+ tMin = tMax = ((xMin - x0) * dx + (yMin - y0) * dy) * mul;
+ t = ((xMin - x0) * dx + (yMax - y0) * dy) * mul;
+ if (t < tMin) {
+ tMin = t;
+ } else if (t > tMax) {
+ tMax = t;
+ }
+ t = ((xMax - x0) * dx + (yMin - y0) * dy) * mul;
+ if (t < tMin) {
+ tMin = t;
+ } else if (t > tMax) {
+ tMax = t;
+ }
+ t = ((xMax - x0) * dx + (yMax - y0) * dy) * mul;
+ if (t < tMin) {
+ tMin = t;
+ } else if (t > tMax) {
+ tMax = t;
+ }
+ if (tMin < 0 && !shading->getExtend0()) {
+ tMin = 0;
+ }
+ if (tMax > 1 && !shading->getExtend1()) {
+ tMax = 1;
+ }
+
+ // get the function domain
+ t0 = shading->getDomain0();
+ t1 = shading->getDomain1();
+
+ // Traverse the t axis and do the shading.
+ //
+ // For each point (tx, ty) on the t axis, consider a line through
+ // that point perpendicular to the t axis:
+ //
+ // x(s) = tx + s * -dy --> s = (x - tx) / -dy
+ // y(s) = ty + s * dx --> s = (y - ty) / dx
+ //
+ // Then look at the intersection of this line with the bounding box
+ // (xMin, yMin, xMax, yMax). In the general case, there are four
+ // intersection points:
+ //
+ // s0 = (xMin - tx) / -dy
+ // s1 = (xMax - tx) / -dy
+ // s2 = (yMin - ty) / dx
+ // s3 = (yMax - ty) / dx
+ //
+ // and we want the middle two s values.
+ //
+ // In the case where dx = 0, take s0 and s1; in the case where dy =
+ // 0, take s2 and s3.
+ //
+ // Each filled polygon is bounded by two of these line segments
+ // perpdendicular to the t axis.
+ //
+ // The t axis is bisected into smaller regions until the color
+ // difference across a region is small enough, and then the region
+ // is painted with a single color.
+
+ // set up
+ nComps = shading->getColorSpace()->getNComps();
+ ta[0] = tMin;
+ ta[axialMaxSplits] = tMax;
+ next[0] = axialMaxSplits;
+
+ // compute the color at t = tMin
+ if (tMin < 0) {
+ tt = t0;
+ } else if (tMin > 1) {
+ tt = t1;
+ } else {
+ tt = t0 + (t1 - t0) * tMin;
+ }
+ shading->getColor(tt, &color0);
+
+ // compute the coordinates of the point on the t axis at t = tMin;
+ // then compute the intersection of the perpendicular line with the
+ // bounding box
+ tx = x0 + tMin * dx;
+ ty = y0 + tMin * dy;
+ if (dx == 0 && dy == 0) {
+ sMin = sMax = 0;
+ } if (dx == 0) {
+ sMin = (xMin - tx) / -dy;
+ sMax = (xMax - tx) / -dy;
+ if (sMin > sMax) { tmp = sMin; sMin = sMax; sMax = tmp; }
+ } else if (dy == 0) {
+ sMin = (yMin - ty) / dx;
+ sMax = (yMax - ty) / dx;
+ if (sMin > sMax) { tmp = sMin; sMin = sMax; sMax = tmp; }
+ } else {
+ s[0] = (yMin - ty) / dx;
+ s[1] = (yMax - ty) / dx;
+ s[2] = (xMin - tx) / -dy;
+ s[3] = (xMax - tx) / -dy;
+ for (j = 0; j < 3; ++j) {
+ kk = j;
+ for (k = j + 1; k < 4; ++k) {
+ if (s[k] < s[kk]) {
+ kk = k;
+ }
+ }
+ tmp = s[j]; s[j] = s[kk]; s[kk] = tmp;
+ }
+ sMin = s[1];
+ sMax = s[2];
+ }
+ ux0 = tx - sMin * dy;
+ uy0 = ty + sMin * dx;
+ vx0 = tx - sMax * dy;
+ vy0 = ty + sMax * dx;
+
+ i = 0;
+ while (i < axialMaxSplits) {
+
+ // bisect until color difference is small enough or we hit the
+ // bisection limit
+ j = next[i];
+ while (j > i + 1) {
+ if (ta[j] < 0) {
+ tt = t0;
+ } else if (ta[j] > 1) {
+ tt = t1;
+ } else {
+ tt = t0 + (t1 - t0) * ta[j];
+ }
+ shading->getColor(tt, &color1);
+ for (k = 0; k < nComps; ++k) {
+ if (fabs(color1.c[k] - color0.c[k]) > axialColorDelta) {
+ break;
+ }
+ }
+ if (k == nComps) {
+ break;
+ }
+ k = (i + j) / 2;
+ ta[k] = 0.5 * (ta[i] + ta[j]);
+ next[i] = k;
+ next[k] = j;
+ j = k;
+ }
+
+ // use the average of the colors of the two sides of the region
+ for (k = 0; k < nComps; ++k) {
+ color0.c[k] = 0.5 * (color0.c[k] + color1.c[k]);
+ }
+
+ // compute the coordinates of the point on the t axis; then
+ // compute the intersection of the perpendicular line with the
+ // bounding box
+ tx = x0 + ta[j] * dx;
+ ty = y0 + ta[j] * dy;
+ if (dx == 0 && dy == 0) {
+ sMin = sMax = 0;
+ } if (dx == 0) {
+ sMin = (xMin - tx) / -dy;
+ sMax = (xMax - tx) / -dy;
+ if (sMin > sMax) { tmp = sMin; sMin = sMax; sMax = tmp; }
+ } else if (dy == 0) {
+ sMin = (yMin - ty) / dx;
+ sMax = (yMax - ty) / dx;
+ if (sMin > sMax) { tmp = sMin; sMin = sMax; sMax = tmp; }
+ } else {
+ s[0] = (yMin - ty) / dx;
+ s[1] = (yMax - ty) / dx;
+ s[2] = (xMin - tx) / -dy;
+ s[3] = (xMax - tx) / -dy;
+ for (j = 0; j < 3; ++j) {
+ kk = j;
+ for (k = j + 1; k < 4; ++k) {
+ if (s[k] < s[kk]) {
+ kk = k;
+ }
+ }
+ tmp = s[j]; s[j] = s[kk]; s[kk] = tmp;
+ }
+ sMin = s[1];
+ sMax = s[2];
+ }
+ ux1 = tx - sMin * dy;
+ uy1 = ty + sMin * dx;
+ vx1 = tx - sMax * dy;
+ vy1 = ty + sMax * dx;
+
+ // set the color
+ state->setFillColor(&color0);
+ out->updateFillColor(state);
+
+ // fill the region
+ state->moveTo(ux0, uy0);
+ state->lineTo(vx0, vy0);
+ state->lineTo(vx1, vy1);
+ state->lineTo(ux1, uy1);
+ state->closePath();
+ out->fill(state);
+ state->clearPath();
+
+ // set up for next region
+ ux0 = ux1;
+ uy0 = uy1;
+ vx0 = vx1;
+ vy0 = vy1;
+ color0 = color1;
+ i = next[i];
+ }
+}
+
+void Gfx::doRadialShFill(GfxRadialShading *shading) {
+ double sMin, sMax, xMin, yMin, xMax, yMax;
+ double x0, y0, r0, x1, y1, r1, t0, t1;
+ int nComps;
+ GfxColor colorA, colorB;
+ double xa, ya, xb, yb, ra, rb;
+ double ta, tb, sa, sb;
+ int ia, ib, k, n;
+ double *ctm;
+ double angle, t;
+
+ // get the shading info
+ shading->getCoords(&x0, &y0, &r0, &x1, &y1, &r1);
+ t0 = shading->getDomain0();
+ t1 = shading->getDomain1();
+ nComps = shading->getColorSpace()->getNComps();
+
+ // compute the (possibly extended) s range
+ sMin = 0;
+ sMax = 1;
+ if (shading->getExtend0()) {
+ if (r0 < r1) {
+ // extend the smaller end
+ sMin = -r0 / (r1 - r0);
+ } else {
+ // extend the larger end
+ //~ this computes the diagonal of the bounding box -- we should
+ //~ really compute the intersection of the moving/expanding
+ //~ circles with each of the four corners and look for the max
+ //~ radius
+ state->getUserClipBBox(&xMin, &yMin, &xMax, &yMax);
+ sMin = (sqrt((xMax - xMin) * (xMax - xMin) +
+ (yMax - yMin) * (yMax - yMin)) - r0) / (r1 - r0);
+ if (sMin > 0) {
+ sMin = 0;
+ } else if (sMin < -20) {
+ // sanity check
+ sMin = -20;
+ }
+ }
+ }
+ if (shading->getExtend1()) {
+ if (r1 < r0) {
+ // extend the smaller end
+ sMax = -r0 / (r1 - r0);
+ } else if (r1 > r0) {
+ // extend the larger end
+ state->getUserClipBBox(&xMin, &yMin, &xMax, &yMax);
+ sMax = (sqrt((xMax - xMin) * (xMax - xMin) +
+ (yMax - yMin) * (yMax - yMin)) - r0) / (r1 - r0);
+ if (sMax < 1) {
+ sMin = 1;
+ } else if (sMax > 20) {
+ // sanity check
+ sMax = 20;
+ }
+ }
+ }
+
+ // compute the number of steps into which circles must be divided to
+ // achieve a curve flatness of 0.1 pixel in device space for the
+ // largest circle (note that "device space" is 72 dpi when generating
+ // PostScript, hence the relatively small 0.1 pixel accuracy)
+ ctm = state->getCTM();
+ t = fabs(ctm[0]);
+ if (fabs(ctm[1]) > t) {
+ t = fabs(ctm[1]);
+ }
+ if (fabs(ctm[2]) > t) {
+ t = fabs(ctm[2]);
+ }
+ if (fabs(ctm[3]) > t) {
+ t = fabs(ctm[3]);
+ }
+ if (r0 > r1) {
+ t *= r0;
+ } else {
+ t *= r1;
+ }
+ if (t < 1) {
+ n = 3;
+ } else {
+ n = (int)(M_PI / acos(1 - 0.1 / t));
+ if (n < 3) {
+ n = 3;
+ } else if (n > 200) {
+ n = 200;
+ }
+ }
+
+ // Traverse the t axis and do the shading.
+ //
+ // This generates and fills a series of rings. Each ring is defined
+ // by two circles:
+ // sa, ta, xa, ya, ra, colorA
+ // sb, tb, xb, yb, rb, colorB
+ //
+ // The s/t axis is divided into radialMaxSplits parts; these parts
+ // are combined as much as possible while respecting the
+ // radialColorDelta parameter.
+
+ // setup for the start circle
+ ia = 0;
+ sa = sMin;
+ ta = t0 + sa * (t1 - t0);
+ xa = x0 + sa * (x1 - x0);
+ ya = y0 + sa * (y1 - y0);
+ ra = r0 + sa * (r1 - r0);
+ if (ta < t0) {
+ shading->getColor(t0, &colorA);
+ } else if (ta > t1) {
+ shading->getColor(t1, &colorA);
+ } else {
+ shading->getColor(ta, &colorA);
+ }
+
+ while (ia < radialMaxSplits) {
+
+ // go as far along the t axis (toward t1) as we can, such that the
+ // color difference is within the tolerance (radialColorDelta) --
+ // this uses bisection (between the current value, t, and t1),
+ // limited to radialMaxSplits points along the t axis
+ ib = radialMaxSplits;
+ sb = sMin + ((double)ib / (double)radialMaxSplits) * (sMax - sMin);
+ tb = t0 + sb * (t1 - t0);
+ if (tb < t0) {
+ shading->getColor(t0, &colorB);
+ } else if (tb > t1) {
+ shading->getColor(t1, &colorB);
+ } else {
+ shading->getColor(tb, &colorB);
+ }
+ while (ib - ia > 1) {
+ for (k = 0; k < nComps; ++k) {
+ if (fabs(colorB.c[k] - colorA.c[k]) > radialColorDelta) {
+ break;
+ }
+ }
+ if (k == nComps) {
+ break;
+ }
+ ib = (ia + ib) / 2;
+ sb = sMin + ((double)ib / (double)radialMaxSplits) * (sMax - sMin);
+ tb = t0 + sb * (t1 - t0);
+ if (tb < t0) {
+ shading->getColor(t0, &colorB);
+ } else if (tb > t1) {
+ shading->getColor(t1, &colorB);
+ } else {
+ shading->getColor(tb, &colorB);
+ }
+ }
+
+ // compute center and radius of the circle
+ xb = x0 + sb * (x1 - x0);
+ yb = y0 + sb * (y1 - y0);
+ rb = r0 + sb * (r1 - r0);
+
+ // use the average of the colors at the two circles
+ for (k = 0; k < nComps; ++k) {
+ colorA.c[k] = 0.5 * (colorA.c[k] + colorB.c[k]);
+ }
+ state->setFillColor(&colorA);
+ out->updateFillColor(state);
+
+ // construct path for first circle
+ state->moveTo(xa + ra, ya);
+ for (k = 1; k < n; ++k) {
+ angle = ((double)k / (double)n) * 2 * M_PI;
+ state->lineTo(xa + ra * cos(angle), ya + ra * sin(angle));
+ }
+ state->closePath();
+
+ // construct and append path for second circle
+ state->moveTo(xb + rb, yb);
+ for (k = 1; k < n; ++k) {
+ angle = ((double)k / (double)n) * 2 * M_PI;
+ state->lineTo(xb + rb * cos(angle), yb + rb * sin(angle));
+ }
+ state->closePath();
+
+ // fill the ring
+ out->eoFill(state);
+ state->clearPath();
+
+ // step to the next value of t
+ ia = ib;
+ sa = sb;
+ ta = tb;
+ xa = xb;
+ ya = yb;
+ ra = rb;
+ colorA = colorB;
+ }
+}
+