void Gfx::doRadialShFill(GfxRadialShading *shading) {
  double 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;
  double sz, xz, yz, sMin, sMax;
  GBool enclosed;
  int ia, ib, k, n;
  double *ctm;
  double theta, alpha, angle, t;
  GBool needExtend = gTrue;

  // get the shading info
  shading->getCoords(&x0, &y0, &r0, &x1, &y1, &r1);
  t0 = shading->getDomain0();
  t1 = shading->getDomain1();
  nComps = shading->getColorSpace()->getNComps();

  // Compute the point at which r(s) = 0; check for the enclosed
  // circles case; and compute the angles for the tangent lines.
  if (x0 == x1 && y0 == y1) {
    enclosed = gTrue;
    theta = 0; // make gcc happy
    sz = 0; // make gcc happy
  } else if (r0 == r1) {
    enclosed = gFalse;
    theta = 0;
    sz = 0; // make gcc happy
  } else {
    sz = (r1 > r0) ? -r0 / (r1 - r0) : -r1 / (r0 - r1);
    xz = x0 + sz * (x1 - x0);
    yz = y0 + sz * (y1 - y0);
    enclosed = (xz - x0) * (xz - x0) + (yz - y0) * (yz - y0) <= r0 * r0;
    theta = asin(r0 / sqrt((x0 - xz) * (x0 - xz) + (y0 - yz) * (y0 - yz)));
    if (r0 > r1) {
      theta = -theta;
    }
  }
  if (enclosed) {
    alpha = 0;
  } else {
    alpha = atan2(y1 - y0, x1 - x0);
  }

  // compute the (possibly extended) s range
  state->getUserClipBBox(&xMin, &yMin, &xMax, &yMax);
  if (enclosed) {
    sMin = 0;
    sMax = 1;
  } else {
    sMin = 1;
    sMax = 0;
    // solve for x(s) + r(s) = xMin
    if ((x1 + r1) - (x0 + r0) != 0) {
      sa = (xMin - (x0 + r0)) / ((x1 + r1) - (x0 + r0));
      if (sa < sMin) {
	sMin = sa;
      } else if (sa > sMax) {
	sMax = sa;
      }
    }
    // solve for x(s) - r(s) = xMax
    if ((x1 - r1) - (x0 - r0) != 0) {
      sa = (xMax - (x0 - r0)) / ((x1 - r1) - (x0 - r0));
      if (sa < sMin) {
	sMin = sa;
      } else if (sa > sMax) {
	sMax = sa;
      }
    }
    // solve for y(s) + r(s) = yMin
    if ((y1 + r1) - (y0 + r0) != 0) {
      sa = (yMin - (y0 + r0)) / ((y1 + r1) - (y0 + r0));
      if (sa < sMin) {
	sMin = sa;
      } else if (sa > sMax) {
	sMax = sa;
      }
    }
    // solve for y(s) - r(s) = yMax
    if ((y1 - r1) - (y0 - r0) != 0) {
      sa = (yMax - (y0 - r0)) / ((y1 - r1) - (y0 - r0));
      if (sa < sMin) {
	sMin = sa;
      } else if (sa > sMax) {
	sMax = sa;
      }
    }
    // check against sz
    if (r0 < r1) {
      if (sMin < sz) {
	sMin = sz;
      }
    } else if (r0 > r1) {
      if (sMax > sz) {
	sMax = sz;
      }
    }
    // check the 'extend' flags
    if (!shading->getExtend0() && sMin < 0) {
      sMin = 0;
    }
    if (!shading->getExtend1() && sMax > 1) {
      sMax = 1;
    }
  }

  if (out->useShadedFills( shading->getType() ) &&
      out->radialShadedFill(state, shading, sMin, sMax)) {
    return;
  }

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

  // 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);
  getShadingColorRadialHelper(t0, t1, ta, shading, &colorA);

  needExtend = !out->radialShadedSupportExtend(state, shading);

  // fill the circles
  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; require at
    // least one split to avoid problems when the innermost and
    // outermost colors are the same
    ib = radialMaxSplits;
    sb = sMax;
    tb = t0 + sb * (t1 - t0);
    getShadingColorRadialHelper(t0, t1, tb, shading, &colorB);
    while (ib - ia > 1) {
      if (isSameGfxColor(colorB, colorA, nComps, radialColorDelta)) {
        // The shading is not necessarily lineal so having two points with the
        // same color does not mean all the areas in between have the same color too
        int ic = ia + 1;
        for (; ic <= ib; ic++) {
          GfxColor colorC;
          const double sc = sMin + ((double)ic / (double)radialMaxSplits) * (sMax - sMin);
          const double tc = t0 + sc * (t1 - t0);
          getShadingColorRadialHelper(t0, t1, tc, shading, &colorC);
          if (!isSameGfxColor(colorC, colorA, nComps, radialColorDelta)) {
            break;
          }
        }
        ib = (ic > ia + 1) ? ic - 1 : ia + 1;
        sb = sMin + ((double)ib / (double)radialMaxSplits) * (sMax - sMin);
        tb = t0 + sb * (t1 - t0);
        getShadingColorRadialHelper(t0, t1, tb, shading, &colorB);
        break;
      }
      ib = (ia + ib) / 2;
      sb = sMin + ((double)ib / (double)radialMaxSplits) * (sMax - sMin);
      tb = t0 + sb * (t1 - t0);
      getShadingColorRadialHelper(t0, t1, tb, shading, &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] = (colorA.c[k] + colorB.c[k]) / 2;
    }
    state->setFillColor(&colorA);
    if (out->useFillColorStop())
      out->updateFillColorStop(state, (sa - sMin)/(sMax - sMin));
    else
      out->updateFillColor(state);

    if (needExtend) {
      if (enclosed) {
        // construct path for first circle (counterclockwise)
        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 (clockwise)
        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();
      } else {
        // construct the first subpath (clockwise)
        state->moveTo(xa + ra * cos(alpha + theta + 0.5 * M_PI),
		      ya + ra * sin(alpha + theta + 0.5 * M_PI));
        for (k = 0; k < n; ++k) {
	  angle = alpha + theta + 0.5 * M_PI
		  - ((double)k / (double)n) * (2 * theta + M_PI);
	  state->lineTo(xb + rb * cos(angle), yb + rb * sin(angle));
        }
	for (k = 0; k < n; ++k) {
	  angle = alpha - theta - 0.5 * M_PI
		  + ((double)k / (double)n) * (2 * theta - M_PI);
	  state->lineTo(xa + ra * cos(angle), ya + ra * sin(angle));
	}
	state->closePath();

        // construct the second subpath (counterclockwise)
	state->moveTo(xa + ra * cos(alpha + theta + 0.5 * M_PI),
		      ya + ra * sin(alpha + theta + 0.5 * M_PI));
	for (k = 0; k < n; ++k) {
	  angle = alpha + theta + 0.5 * M_PI
		  + ((double)k / (double)n) * (-2 * theta + M_PI);
	  state->lineTo(xb + rb * cos(angle), yb + rb * sin(angle));
	}
	for (k = 0; k < n; ++k) {
	  angle = alpha - theta - 0.5 * M_PI
		  + ((double)k / (double)n) * (2 * theta + M_PI);
	  state->lineTo(xa + ra * cos(angle), ya + ra * sin(angle));
	}
	state->closePath();
      }
    }

    if (!out->useFillColorStop()) {
      // fill the path
      if (!contentIsHidden())
        out->fill(state);
      state->clearPath();
    }

    // step to the next value of t
    ia = ib;
    sa = sb;
    ta = tb;
    xa = xb;
    ya = yb;
    ra = rb;
    colorA = colorB;
  }

  if (out->useFillColorStop()) {
    // make sure we add stop color when sb = sMax
    state->setFillColor(&colorA);
    out->updateFillColorStop(state, (sb - sMin)/(sMax - sMin));

    // fill the path
    state->moveTo(xMin, yMin);
    state->lineTo(xMin, yMax);
    state->lineTo(xMax, yMax);
    state->lineTo(xMax, yMin);
    state->closePath();

    if (!contentIsHidden())
      out->fill(state);
    state->clearPath();
  }

  if (!needExtend)
    return;

  if (enclosed) {
    // extend the smaller circle
    if ((shading->getExtend0() && r0 <= r1) ||
	(shading->getExtend1() && r1 < r0)) {
      if (r0 <= r1) {
	ta = t0;
	ra = r0;
	xa = x0;
	ya = y0;
      } else {
	ta = t1;
	ra = r1;
	xa = x1;
	ya = y1;
      }
      shading->getColor(ta, &colorA);
      state->setFillColor(&colorA);
      out->updateFillColor(state);
      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();
      if (!contentIsHidden())
        out->fill(state);
      state->clearPath();
    }

    // extend the larger circle
    if ((shading->getExtend0() && r0 > r1) ||
	(shading->getExtend1() && r1 >= r0)) {
      if (r0 > r1) {
	ta = t0;
	ra = r0;
	xa = x0;
	ya = y0;
      } else {
	ta = t1;
	ra = r1;
	xa = x1;
	ya = y1;
      }
      shading->getColor(ta, &colorA);
      state->setFillColor(&colorA);
      out->updateFillColor(state);
      state->moveTo(xMin, yMin);
      state->lineTo(xMin, yMax);
      state->lineTo(xMax, yMax);
      state->lineTo(xMax, yMin);
      state->closePath();
      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();
      if (!contentIsHidden())
        out->fill(state);
      state->clearPath();
    }
  }
}
void Gfx::doRadialShFill(GfxRadialShading *shading) {
  double 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;
  double sz, xz, yz, sMin, sMax;
  GBool enclosed;
  int ia, ib, k, n;
  double *ctm;
  double theta, alpha, angle, t;
  GBool needExtend = gTrue;

   
  shading->getCoords(&x0, &y0, &r0, &x1, &y1, &r1);
  t0 = shading->getDomain0();
  t1 = shading->getDomain1();
  nComps = shading->getColorSpace()->getNComps();

   
   
  if (x0 == x1 && y0 == y1) {
    enclosed = gTrue;
    theta = 0;  
    sz = 0;  
  } else if (r0 == r1) {
    enclosed = gFalse;
    theta = 0;
    sz = 0;  
  } else {
    sz = (r1 > r0) ? -r0 / (r1 - r0) : -r1 / (r0 - r1);
    xz = x0 + sz * (x1 - x0);
    yz = y0 + sz * (y1 - y0);
    enclosed = (xz - x0) * (xz - x0) + (yz - y0) * (yz - y0) <= r0 * r0;
    theta = asin(r0 / sqrt((x0 - xz) * (x0 - xz) + (y0 - yz) * (y0 - yz)));
    if (r0 > r1) {
      theta = -theta;
    }
  }
  if (enclosed) {
    alpha = 0;
  } else {
    alpha = atan2(y1 - y0, x1 - x0);
  }

   
  state->getUserClipBBox(&xMin, &yMin, &xMax, &yMax);
  if (enclosed) {
    sMin = 0;
    sMax = 1;
  } else {
    sMin = 1;
    sMax = 0;
     
    if ((x1 + r1) - (x0 + r0) != 0) {
      sa = (xMin - (x0 + r0)) / ((x1 + r1) - (x0 + r0));
      if (sa < sMin) {
	sMin = sa;
      } else if (sa > sMax) {
	sMax = sa;
      }
    }
     
    if ((x1 - r1) - (x0 - r0) != 0) {
      sa = (xMax - (x0 - r0)) / ((x1 - r1) - (x0 - r0));
      if (sa < sMin) {
	sMin = sa;
      } else if (sa > sMax) {
	sMax = sa;
      }
    }
     
    if ((y1 + r1) - (y0 + r0) != 0) {
      sa = (yMin - (y0 + r0)) / ((y1 + r1) - (y0 + r0));
      if (sa < sMin) {
	sMin = sa;
      } else if (sa > sMax) {
	sMax = sa;
      }
    }
     
    if ((y1 - r1) - (y0 - r0) != 0) {
      sa = (yMax - (y0 - r0)) / ((y1 - r1) - (y0 - r0));
      if (sa < sMin) {
	sMin = sa;
      } else if (sa > sMax) {
	sMax = sa;
      }
    }
     
    if (r0 < r1) {
      if (sMin < sz) {
	sMin = sz;
      }
    } else if (r0 > r1) {
      if (sMax > sz) {
	sMax = sz;
      }
    }
     
    if (!shading->getExtend0() && sMin < 0) {
      sMin = 0;
    }
    if (!shading->getExtend1() && sMax > 1) {
      sMax = 1;
    }
  }

  if (out->useShadedFills( shading->getType() ) &&
      out->radialShadedFill(state, shading, sMin, sMax)) {
    return;
  }

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

   
  ia = 0;
  sa = sMin;
  ta = t0 + sa * (t1 - t0);
  xa = x0 + sa * (x1 - x0);
  ya = y0 + sa * (y1 - y0);
  ra = r0 + sa * (r1 - r0);
  getShadingColorRadialHelper(t0, t1, ta, shading, &colorA);

  needExtend = !out->radialShadedSupportExtend(state, shading);

   
  while (ia < radialMaxSplits) {

     
     
     
     
     
     
    ib = radialMaxSplits;
    sb = sMax;
    tb = t0 + sb * (t1 - t0);
    getShadingColorRadialHelper(t0, t1, tb, shading, &colorB);
    while (ib - ia > 1) {
      if (isSameGfxColor(colorB, colorA, nComps, radialColorDelta)) {
         
         
        int ic = ia + 1;
        for (; ic <= ib; ic++) {
          GfxColor colorC;
          const double sc = sMin + ((double)ic / (double)radialMaxSplits) * (sMax - sMin);
          const double tc = t0 + sc * (t1 - t0);
          getShadingColorRadialHelper(t0, t1, tc, shading, &colorC);
          if (!isSameGfxColor(colorC, colorA, nComps, radialColorDelta)) {
            break;
          }
        }
        ib = (ic > ia + 1) ? ic - 1 : ia + 1;
        sb = sMin + ((double)ib / (double)radialMaxSplits) * (sMax - sMin);
        tb = t0 + sb * (t1 - t0);
        getShadingColorRadialHelper(t0, t1, tb, shading, &colorB);
        break;
      }
      ib = (ia + ib) / 2;
      sb = sMin + ((double)ib / (double)radialMaxSplits) * (sMax - sMin);
      tb = t0 + sb * (t1 - t0);
      getShadingColorRadialHelper(t0, t1, tb, shading, &colorB);
    }

     
    xb = x0 + sb * (x1 - x0);
    yb = y0 + sb * (y1 - y0);
    rb = r0 + sb * (r1 - r0);

     
    for (k = 0; k < nComps; ++k) {
      colorA.c[k] = (colorA.c[k] + colorB.c[k]) / 2;
    }
    state->setFillColor(&colorA);
    if (out->useFillColorStop())
      out->updateFillColorStop(state, (sa - sMin)/(sMax - sMin));
    else
      out->updateFillColor(state);

    if (needExtend) {
      if (enclosed) {
         
        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();

         
        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();
      } else {
         
        state->moveTo(xa + ra * cos(alpha + theta + 0.5 * M_PI),
		      ya + ra * sin(alpha + theta + 0.5 * M_PI));
        for (k = 0; k < n; ++k) {
	  angle = alpha + theta + 0.5 * M_PI
		  - ((double)k / (double)n) * (2 * theta + M_PI);
	  state->lineTo(xb + rb * cos(angle), yb + rb * sin(angle));
        }
	for (k = 0; k < n; ++k) {
	  angle = alpha - theta - 0.5 * M_PI
		  + ((double)k / (double)n) * (2 * theta - M_PI);
	  state->lineTo(xa + ra * cos(angle), ya + ra * sin(angle));
	}
	state->closePath();

         
	state->moveTo(xa + ra * cos(alpha + theta + 0.5 * M_PI),
		      ya + ra * sin(alpha + theta + 0.5 * M_PI));
	for (k = 0; k < n; ++k) {
	  angle = alpha + theta + 0.5 * M_PI
		  + ((double)k / (double)n) * (-2 * theta + M_PI);
	  state->lineTo(xb + rb * cos(angle), yb + rb * sin(angle));
	}
	for (k = 0; k < n; ++k) {
	  angle = alpha - theta - 0.5 * M_PI
		  + ((double)k / (double)n) * (2 * theta + M_PI);
	  state->lineTo(xa + ra * cos(angle), ya + ra * sin(angle));
	}
	state->closePath();
      }
    }

    if (!out->useFillColorStop()) {
       
      if (!contentIsHidden())
        out->fill(state);
      state->clearPath();
    }

     
    ia = ib;
    sa = sb;
    ta = tb;
    xa = xb;
    ya = yb;
    ra = rb;
    colorA = colorB;
  }

  if (out->useFillColorStop()) {
     
    state->setFillColor(&colorA);
    out->updateFillColorStop(state, (sb - sMin)/(sMax - sMin));

     
    state->moveTo(xMin, yMin);
    state->lineTo(xMin, yMax);
    state->lineTo(xMax, yMax);
    state->lineTo(xMax, yMin);
    state->closePath();

    if (!contentIsHidden())
      out->fill(state);
    state->clearPath();
  }

  if (!needExtend)
    return;

  if (enclosed) {
     
    if ((shading->getExtend0() && r0 <= r1) ||
	(shading->getExtend1() && r1 < r0)) {
      if (r0 <= r1) {
	ta = t0;
	ra = r0;
	xa = x0;
	ya = y0;
      } else {
	ta = t1;
	ra = r1;
	xa = x1;
	ya = y1;
      }
      shading->getColor(ta, &colorA);
      state->setFillColor(&colorA);
      out->updateFillColor(state);
      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();
      if (!contentIsHidden())
        out->fill(state);
      state->clearPath();
    }

     
    if ((shading->getExtend0() && r0 > r1) ||
	(shading->getExtend1() && r1 >= r0)) {
      if (r0 > r1) {
	ta = t0;
	ra = r0;
	xa = x0;
	ya = y0;
      } else {
	ta = t1;
	ra = r1;
	xa = x1;
	ya = y1;
      }
      shading->getColor(ta, &colorA);
      state->setFillColor(&colorA);
      out->updateFillColor(state);
      state->moveTo(xMin, yMin);
      state->lineTo(xMin, yMax);
      state->lineTo(xMax, yMax);
      state->lineTo(xMax, yMin);
      state->closePath();
      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();
      if (!contentIsHidden())
        out->fill(state);
      state->clearPath();
    }
  }
}