From 8e3e6e838a9a6cbf5f37f8e4b5319b28de53b587 Mon Sep 17 00:00:00 2001 From: Carlos Garcia Campos Date: Wed, 3 Jun 2009 20:55:12 +0200 Subject: [PATCH] Implement axialShadedFill() in cairo backend using cairo linear gradient patterns See bug #10942. --- poppler/CairoOutputDev.cc | 297 +++++++++++++++++++++++++++++++++++++++++++++ poppler/CairoOutputDev.h | 6 + 2 files changed, 303 insertions(+), 0 deletions(-) diff --git a/poppler/CairoOutputDev.cc b/poppler/CairoOutputDev.cc index 199e5ea..79a5f43 100644 --- a/poppler/CairoOutputDev.cc +++ b/poppler/CairoOutputDev.cc @@ -586,6 +586,303 @@ void CairoOutputDev::eoFill(GfxState *state) { } +#define axialMaxSplits 256 +#define axialColorDelta (dblToCol(1 / 256.0)) +static void bubbleSort(double array[]) +{ + for (int j = 0; j < 3; ++j) { + int kk = j; + for (int k = j + 1; k < 4; ++k) { + if (array[k] < array[kk]) { + kk = k; + } + } + double tmp = array[j]; + array[j] = array[kk]; + array[kk] = tmp; + } +} + +GBool CairoOutputDev::axialShadedFill(GfxState *state, GfxAxialShading *shading) { + double xMin, yMin, xMax, yMax; + double x0, y0, x1, y1; + double dx, dy, mul; + GBool dxZero, dyZero; + double bboxIntersections[4]; + double tMin, tMax, 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; + GfxRGB rgbColor; + cairo_pattern_t *pattern; + + // 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); + pattern = cairo_pattern_create_linear (x0, y0, x1, y1); + + dx = x1 - x0; + dy = y1 - y0; + dxZero = fabs(dx) < 0.01; + dyZero = fabs(dy) < 0.01; + if (dxZero && dyZero) { + tMin = tMax = 0; + } else { + mul = 1 / (dx * dx + dy * dy); + bboxIntersections[0] = ((xMin - x0) * dx + (yMin - y0) * dy) * mul; + bboxIntersections[1] = ((xMin - x0) * dx + (yMax - y0) * dy) * mul; + bboxIntersections[2] = ((xMax - x0) * dx + (yMin - y0) * dy) * mul; + bboxIntersections[3] = ((xMax - x0) * dx + (yMax - y0) * dy) * mul; + bubbleSort(bboxIntersections); + tMin = bboxIntersections[0]; + tMax = bboxIntersections[3]; + 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: require at least one split to avoid problems when the two + // ends of the t axis have the same color + nComps = shading->getColorSpace()->getNComps(); + ta[0] = tMin; + next[0] = axialMaxSplits / 2; + ta[axialMaxSplits / 2] = 0.5 * (tMin + tMax); + next[axialMaxSplits / 2] = axialMaxSplits; + ta[axialMaxSplits] = tMax; + + // 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); + shading->getColorSpace()->getRGB(&color0, &rgbColor); + cairo_pattern_add_color_stop_rgb(pattern, tt / t1, + rgbColor.r / 65535.0, + rgbColor.g / 65535.0, + rgbColor.b / 65535.0); + + // 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 (dxZero && dyZero) { + sMin = sMax = 0; + } else if (dxZero) { + sMin = (xMin - tx) / -dy; + sMax = (xMax - tx) / -dy; + if (sMin > sMax) { tmp = sMin; sMin = sMax; sMax = tmp; } + } else if (dyZero) { + 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; + bubbleSort(s); + sMin = s[1]; + sMax = s[2]; + } + ux0 = tx - sMin * dy; + uy0 = ty + sMin * dx; + vx0 = tx - sMax * dy; + vy0 = ty + sMax * dx; + + i = 0; + bool doneBBox1, doneBBox2; + if (dxZero && dyZero) { + doneBBox1 = doneBBox2 = true; + } else { + doneBBox1 = bboxIntersections[1] < tMin; + doneBBox2 = bboxIntersections[2] > tMax; + } + 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 (abs(color1.c[k] - color0.c[k]) > axialColorDelta) { + break; + } + } + if (k == nComps) { + // in these two if what we guarantee is that if we are skipping lots of + // positions because the colors are the same, we still create a region + // with vertexs passing by bboxIntersections[1] and bboxIntersections[2] + // otherwise we can have empty regions that should really be painted + // like happened in bug 19896 + // What we do to ensure that we pass a line through this points + // is making sure use the exact bboxIntersections[] value as one of the used ta[] values + if (!doneBBox1 && ta[i] < bboxIntersections[1] && ta[j] > bboxIntersections[1]) { + int teoricalj = (bboxIntersections[1] - tMin) * axialMaxSplits / (tMax - tMin); + if (teoricalj <= i) teoricalj = i + 1; + if (teoricalj < j) { + next[i] = teoricalj; + next[teoricalj] = j; + } + else { + teoricalj = j; + } + ta[teoricalj] = bboxIntersections[1]; + j = teoricalj; + doneBBox1 = true; + } + if (!doneBBox2 && ta[i] < bboxIntersections[2] && ta[j] > bboxIntersections[2]) { + int teoricalj = (bboxIntersections[2] - tMin) * axialMaxSplits / (tMax - tMin); + if (teoricalj <= i) teoricalj = i + 1; + if (teoricalj < j) { + next[i] = teoricalj; + next[teoricalj] = j; + } + else { + teoricalj = j; + } + ta[teoricalj] = bboxIntersections[2]; + j = teoricalj; + doneBBox2 = true; + } + 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] = (color0.c[k] + color1.c[k]) / 2; + } + + // 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 (dxZero && dyZero) { + sMin = sMax = 0; + } else if (dxZero) { + sMin = (xMin - tx) / -dy; + sMax = (xMax - tx) / -dy; + if (sMin > sMax) { tmp = sMin; sMin = sMax; sMax = tmp; } + } else if (dyZero) { + 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; + bubbleSort(s); + 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 + shading->getColorSpace()->getRGB(&color0, &rgbColor); + cairo_pattern_add_color_stop_rgb(pattern, tt / t1, + rgbColor.r / 65535.0, + rgbColor.g / 65535.0, + rgbColor.b / 65535.0); + + // fill the region + state->moveTo(ux0, uy0); + state->lineTo(vx0, vy0); + state->lineTo(vx1, vy1); + state->lineTo(ux1, uy1); + state->closePath(); + + // set up for next region + ux0 = ux1; + uy0 = uy1; + vx0 = vx1; + vy0 = vy1; + color0 = color1; + i = next[i]; + } + + LOG(printf ("axialShadedFill\n")); + + doPath (cairo, state, state->getPath()); + cairo_set_fill_rule (cairo, CAIRO_FILL_RULE_WINDING); + cairo_set_source (cairo, pattern); + cairo_pattern_destroy (pattern); + cairo_fill (cairo); + if (cairo_shape) { + doPath (cairo_shape, state, state->getPath()); + cairo_set_fill_rule (cairo_shape, CAIRO_FILL_RULE_WINDING); + cairo_fill (cairo_shape); + } + + return gTrue; +} + void CairoOutputDev::clip(GfxState *state) { doPath (cairo, state, state->getPath()); cairo_set_fill_rule (cairo, CAIRO_FILL_RULE_WINDING); diff --git a/poppler/CairoOutputDev.h b/poppler/CairoOutputDev.h index 7a9283f..2dd8c74 100644 --- a/poppler/CairoOutputDev.h +++ b/poppler/CairoOutputDev.h @@ -98,6 +98,11 @@ public: // Does this device use drawChar() or drawString()? virtual GBool useDrawChar() { return gTrue; } + // Does this device use functionShadedFill(), axialShadedFill(), and + // radialShadedFill()? If this returns false, these shaded fills + // will be reduced to a series of other drawing operations. + virtual GBool useShadedFills() { return gTrue; } + // Does this device use beginType3Char/endType3Char? Otherwise, // text in Type 3 fonts will be drawn with drawChar/drawString. virtual GBool interpretType3Chars() { return gFalse; } @@ -141,6 +146,7 @@ public: virtual void stroke(GfxState *state); virtual void fill(GfxState *state); virtual void eoFill(GfxState *state); + virtual GBool axialShadedFill(GfxState *state, GfxAxialShading *shading); //----- path clipping virtual void clip(GfxState *state); -- 1.6.0.4