--- a/layout/generic/nsFloatManager.cpp
+++ b/layout/generic/nsFloatManager.cpp
@@ -1090,16 +1090,226 @@ nsFloatManager::ImageShapeInfo::ImageSha
}
if (aWM.IsVerticalRL()) {
// Because we scan the columns from left to right, we need to reverse
// the array so that it's sorted (in ascending order) on the block
// direction.
mIntervals.Reverse();
}
+ } else {
+ // With a positive aShapeMargin, we have to calculate a distance
+ // field from the opaque pixels, then build intervals based on
+ // them being within aShapeMargin distance to an edge pixel.
+
+ // Computing the difference field is a two-pass O(n) operation.
+ // We use a chamfer 5-7-11 5x5 matrix to compute minimum distance
+ // to an opaque pixel. This integer math computation is reasonably
+ // close to the true Euclidean distance. The distances will be
+ // approximately 5x the true distance, quantized in integer units.
+ // The 5x is factored away in the comparison used in the final
+ // pass which builds the intervals.
+
+ // Our distance field has to be able to hold values equal to the
+ // maximum allowed shape-margin value, times 5. A 16-bit unsigned
+ // int is ~ 65K which can handle a margin up to ~ 13K. That's good
+ // enough for practical usage.
+ typedef uint16_t dfType;
+ const dfType MAX_MARGIN = 13000;
+ const dfType MAX_MARGIN_5X = MAX_MARGIN * 5;
+
+ // Calculate aShapeMargin upper bounded by MAX_MARGIN and
+ // multiplied by 5 in a typesafe fashion.
+ NS_WARNING_ASSERTION(CSSPixel::FromAppUnits(aShapeMargin) <= MAX_MARGIN,
+ "shape-margin is too large and is being clamped.");
+ dfType usedMargin5X = 5 * (dfType)std::min((int32_t)MAX_MARGIN,
+ NSToIntRound(CSSPixel::FromAppUnits(aShapeMargin)));
+
+ // Allocate our distance field. The distance field has to cover
+ // the entire aMarginRect, since aShapeMargin could bleed into it,
+ // beyond the content rect covered by aAlphaPixels.
+
+ // Since our distance field is computed with a 5x5 neighborhood,
+ // we need to expand our distance field by a further 4 pixels in
+ // both axes. We call this border area the "expanded region".
+
+ // In all these calculations, we purposely ignore aStride, because
+ // we don't have to replicate the packing that we received in
+ // aAlphaPixels. When we need to convert from df coordinates to
+ // alpha coordinates, we do that with math based on row and col.
+ const CSSIntPoint dfOffset =
+ CSSPixel::FromAppUnitsRounded(aContentRect.TopLeft());
+ const CSSIntRect margin = CSSPixel::FromAppUnitsRounded(aMarginRect);
+ const int32_t wEx = margin.width + 4;
+ const int32_t hEx = margin.width + 4;
+ const int32_t dfSize = wEx * hEx;
+ auto df = MakeUnique<dfType[]>(dfSize);
+
+ // First pass setting difference field, top-to-bottom, three cases:
+ // 1) Expanded region pixel: set to MAX_MARGIN_5X.
+ // 2) Image pixel with alpha greater than threshold: set to 0.
+ // 3) Other pixel: set to minimum backward-looking neighborhood
+ // distance value, computed with 5-7-11 chamfer.
+ for (int32_t index = 0; index < dfSize; ++index) {
+ const int32_t col = aWM.IsVertical() ? index / hEx : index % wEx;
+ const int32_t row = aWM.IsVertical() ? index % hEx : index / wEx;
+
+ // Handle our three cases, in order.
+ if (col < 2 ||
+ col >= wEx - 2 ||
+ row < 2 ||
+ row >= hEx - 2) {
+ // Case 1: Expanded pixel.
+ df[index] = MAX_MARGIN_5X;
+ } else if (col >= (dfOffset.x + 2) &&
+ col < (dfOffset.x + 2 + w) &&
+ row >= (dfOffset.y + 2) &&
+ row < (dfOffset.y + 2 + h) &&
+ aAlphaPixels[col - (dfOffset.x + 2) +
+ (row - (dfOffset.y + 2)) * aStride] > threshold) {
+ // Case 2: Image pixel that is opaque.
+ df[index] = 0;
+ } else {
+ // Case 3: Other pixel.
+
+ // Backward-looking neighborhood distance from target pixel X
+ // with chamfer 5-7-11 looks like:
+ //
+ // +--+--+--+--+--+
+ // | |11| |11| |
+ // +--+--+--+--+--+
+ // |11| 7| 5| 7|11|
+ // +--+--+--+--+--+
+ // | | 5| X| | |
+ // +--+--+--+--+--+
+ //
+ // X should be set to the minimum of MAX_MARGIN_5X and the
+ // values of all of the numbered neighbors summed with the
+ // value in that chamfer cell.
+ df[index] = std::min<dfType>(MAX_MARGIN_5X,
+ std::min<dfType>(df[index - (wEx * 2) - 1] + 11,
+ std::min<dfType>(df[index - (wEx * 2) + 1] + 11,
+ std::min<dfType>(df[index - wEx - 2] + 11,
+ std::min<dfType>(df[index - wEx - 1] + 7,
+ std::min<dfType>(df[index - wEx] + 5,
+ std::min<dfType>(df[index - wEx + 1] + 7,
+ std::min<dfType>(df[index - wEx + 2] + 11,
+ df[index - 1] + 5))))))));
+ }
+ }
+
+ // Okay, time for the second pass. This pass is bottom-to-top.
+ // All of our opaque pixels have been set to 0, and all of our
+ // expanded pixels have been set to MAX_MARGIN_5X. Other pixels
+ // have been set to some value between those two (inclusive) but
+ // this hasn't yet taken into account the neighbors below them.
+ // This time we reverse iterate so we can apply the backward-
+ // looking chamfer.
+
+ // This time, only two cases:
+ // 1) Expanded region pixel: skip.
+ // 2) Other pixel: set to minimum backward-looking neighborhood
+ // distance value, computed with 5-7-11 chamfer,
+ // then check against the usedMargin5X threshold.
+
+ // At the end of each row (or column in vertical writing modes),
+ // if any of the other pixels had a value less than usedMargin5X,
+ // we create an interval.
+
+ // Set min and max in preparation for the first row.
+ min = dfSize;
+ max = -1;
+
+ for (int32_t index = dfSize - 1; index >= 0; --index) {
+ const int32_t col = aWM.IsVertical() ? index / hEx : index % wEx;
+ const int32_t row = aWM.IsVertical() ? index % hEx : index / wEx;
+ const int32_t curr = aWM.IsVertical() ? row : col;
+
+ // Check our two cases, in order.
+ // For expanded pixels, we can skip whole rows and columns of
+ // iteration, depending on the writing mode.
+ if (col < 2 || col >= wEx - 2) {
+ if (aWM.IsVertical()) {
+ index -= (hEx - 1);
+ }
+ continue;
+ }
+ if (row < 2 || row >= hEx - 2) {
+ if (!aWM.IsVertical()) {
+ index -= (wEx - 1);
+ }
+ continue;
+ }
+
+ // If we've gotten this far, we're in Case 2: Other pixel.
+
+ // Only apply the chamfer calculation if the df value is not
+ // already 0, since the chamfer can only reduce the value.
+ if (df[index]) {
+ // Forward-looking neighborhood distance from target pixel X
+ // with chamfer 5-7-11 looks like:
+ //
+ // +--+--+--+--+--+
+ // | | | X| 5| |
+ // +--+--+--+--+--+
+ // |11| 7| 5| 7|11|
+ // +--+--+--+--+--+
+ // | |11| |11| |
+ // +--+--+--+--+--+
+ //
+ // X should be set to the minimum of its current value and
+ // the values of all of the numbered neighbors summed with
+ // the value in that chamfer cell.
+ df[index] = std::min<dfType>(df[index],
+ std::min<dfType>(df[index + (wEx * 2) + 1] + 11,
+ std::min<dfType>(df[index + (wEx * 2) - 1] + 11,
+ std::min<dfType>(df[index + wEx + 2] + 11,
+ std::min<dfType>(df[index + wEx + 1] + 7,
+ std::min<dfType>(df[index + wEx] + 5,
+ std::min<dfType>(df[index + wEx - 1] + 7,
+ std::min<dfType>(df[index + wEx - 2] + 11,
+ df[index + 1] + 5))))))));
+ }
+
+ // Finally, we can check the df value and see if its less than
+ // or equal to the usedMargin5X value.
+ if (df[index] <= usedMargin5X) {
+ if (max == -1) {
+ max = curr;
+ }
+ if (min > curr) {
+ min = curr;
+ }
+ }
+
+ // At the end of a row (or column if vertical).
+ if (curr == 2) {
+ // If we found something, create an interval.
+ if (max != -1) {
+ // Supply a zero offset for this interval, because our
+ // col and row are calculated from the margin rect.
+ // We likewise need to subtract 2 from both col and row
+ // because those indices are relative to the expanded
+ // pixel area.
+ CreateInterval(min, max, col - 2, row - 2, nsPoint(),
+ aWM, aContainerSize);
+ }
+
+ // Reset min and max for the next row or column.
+ min = dfSize;
+ max = -1;
+ }
+ }
+
+ if (!aWM.IsVerticalRL()) {
+ // Because we assembled our intervals on the bottom-up pass,
+ // they are reversed for most writing modes. Reverse them to
+ // keep the array sorted on the block direction.
+ mIntervals.Reverse();
+ }
}
if (!mIntervals.IsEmpty()) {
mBStart = mIntervals[0].mLineLeft.Y();
mBEnd = mIntervals[mIntervals.Length() - 1].mLineLeft.Y();
}
}
