Bug 1265342 Part 4: Complete the implementation of shape-margin for shape-outside: image, for shape-margin: > 0. draft
 author Brad Werth Thu, 22 Feb 2018 11:11:03 -0800 changeset 767049 cfca91346fdf97eaeb01b5331a52411f48b5073e parent 767048 e500d452953077e1e540bd1e2516382f7cbdbd8c child 767050 48eb103ff6780378e020c78e0989f01ed4a4d61b push id 102494 push user bwerth@mozilla.com push date Tue, 13 Mar 2018 20:51:39 +0000 bugs 1265342 milestone 61.0a1
Bug 1265342 Part 4: Complete the implementation of shape-margin for shape-outside: image, for shape-margin: > 0. MozReview-Commit-ID: 4xqfqWB78Oh
```--- 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();
}
}
```