Bug 1265342 Part 3: Implement shape-margin for shape-outside: image. draft
authorBrad Werth <bwerth@mozilla.com>
Thu, 22 Feb 2018 11:11:03 -0800
changeset 762273 cb1e6a9f04671da0f3c275479f213f975a5e6903
parent 762272 a953a115b7dd8244b66d4e235d5c91e4e1251195
child 762274 7e4e3a9cccd3841d19fba08d7f82d87d4537a4a9
push id101114
push userbwerth@mozilla.com
push dateThu, 01 Mar 2018 23:33:31 +0000
bugs1265342
milestone60.0a1
Bug 1265342 Part 3: Implement shape-margin for shape-outside: image. MozReview-Commit-ID: 4xqfqWB78Oh
layout/generic/nsFloatManager.cpp
--- a/layout/generic/nsFloatManager.cpp
+++ b/layout/generic/nsFloatManager.cpp
@@ -580,17 +580,19 @@ public:
     const UniquePtr<StyleBasicShape>& aBasicShape,
     const LogicalRect& aShapeBoxRect,
     WritingMode aWM,
     const nsSize& aContainerSize);
 
   static UniquePtr<ShapeInfo> CreateImageShape(
     const UniquePtr<nsStyleImage>& aShapeImage,
     float aShapeImageThreshold,
+    nscoord aShapeMargin,
     nsIFrame* const aFrame,
+    const LogicalRect& aMarginRect,
     WritingMode aWM,
     const nsSize& aContainerSize);
 
 protected:
   // Compute the minimum line-axis difference between the bounding shape
   // box and its rounded corner within the given band (block-axis region).
   // This is used as a helper function to compute the LineRight() and
   // LineLeft(). See the picture in the implementation for an example.
@@ -967,19 +969,21 @@ nsFloatManager::PolygonShapeInfo::XInter
 //
 // Implements shape-outside: <image>
 //
 class nsFloatManager::ImageShapeInfo final : public nsFloatManager::ShapeInfo
 {
 public:
   ImageShapeInfo(uint8_t* aAlphaPixels,
                  int32_t aStride,
-                 const CSSIntSize& aSize,
+                 const CSSIntSize& aImageSize,
                  float aShapeImageThreshold,
+                 nscoord aShapeMargin,
                  const nsRect& aContentRect,
+                 const nsRect& aMarginRect,
                  WritingMode aWM,
                  const nsSize& aContainerSize);
 
   nscoord LineLeft(const nscoord aBStart,
                    const nscoord aBEnd) const override;
   nscoord LineRight(const nscoord aBStart,
                     const nscoord aBEnd) const override;
   nscoord BStart() const override { return mBStart; }
@@ -1017,76 +1021,300 @@ private:
                       const nsSize& aContainerSize);
 };
 
 nsFloatManager::ImageShapeInfo::ImageShapeInfo(
   uint8_t* aAlphaPixels,
   int32_t aStride,
   const CSSIntSize& aImageSize,
   float aShapeImageThreshold,
+  nscoord aShapeMargin,
   const nsRect& aContentRect,
+  const nsRect& aMarginRect,
   WritingMode aWM,
   const nsSize& aContainerSize)
 {
   MOZ_ASSERT(aShapeImageThreshold >=0.0 && aShapeImageThreshold <=1.0,
              "The computed value of shape-image-threshold is wrong!");
 
   const uint8_t threshold = NSToIntRound(aShapeImageThreshold * 255);
   const int32_t w = aImageSize.width;
   const int32_t h = aImageSize.height;
   const int32_t alphaSize = aStride * h;
 
   int32_t min = -1;
   int32_t max = -1;
 
-  // Scan the pixels row by row, from top to bottom (if vertical, column by
-  // column, from left to right).
-  for (int32_t index = 0; index < alphaSize; ++index) {
-    const int32_t col = aWM.IsVertical() ? index / h : index % aStride;
-    const int32_t row = aWM.IsVertical() ? index % h : index / aStride;
-    const int32_t curr = aWM.IsVertical() ? row : col;
+  if (aShapeMargin <= 0) {
+    // Without a positive aShapeMargin, all we have to do is a
+    // direct threshold comparison of the alpha pixels.
+    // https://drafts.csswg.org/css-shapes-1/#valdef-shape-image-threshold-number
 
-    // If we're in the area between w and aStride, skip this pixel,
-    // or if we're vertical, skip the remainder of the loop.
-    if (col >= w) {
-      if (aWM.IsVertical()) {
-        break;
+    // Scan the pixels row by row, from top to bottom (if vertical, column by
+    // column, from left to right).
+    for (int32_t index = 0; index < alphaSize; ++index) {
+      const int32_t col = aWM.IsVertical() ? index / h : index % aStride;
+      const int32_t row = aWM.IsVertical() ? index % h : index / aStride;
+      const int32_t curr = aWM.IsVertical() ? row : col;
+
+      // If we're in the area between w and aStride, skip this pixel,
+      // or if we're vertical, skip the remainder of the loop.
+      if (col >= w) {
+        if (aWM.IsVertical()) {
+          break;
+        }
+        continue;
       }
-      continue;
-    }
+
+      // Find the min and max columns (rows if vertical) in those pixels whose
+      // alpha channel is greater than the threshold.
+      // https://drafts.csswg.org/css-shapes-1/#valdef-shape-image-threshold-number
+      const uint8_t alpha = aAlphaPixels[col + row * aStride];
+      if (alpha > threshold) {
+        if (min == -1) {
+          min = curr;
+        }
+        if (max < curr) {
+          max = curr;
+        }
+      }
 
-    // Find the min and max columns (rows if vertical) in those pixels whose
-    // alpha channel is greater than the threshold.
-    // https://drafts.csswg.org/css-shapes-1/#valdef-shape-image-threshold-number
-    const uint8_t alpha = aAlphaPixels[col + row * aStride];
-    if (alpha > threshold) {
-      if (min == -1) {
-        min = curr;
-      }
-      if (max < curr) {
-        max = curr;
+      // At the end of a row (or column if vertical).
+      if (curr == (aWM.IsVertical() ? h - 1 : w - 1)) {
+        // If we found something, create an interval.
+        if (min != -1) {
+          // We need to supply an offset of the content rect top left, since
+          // our col and row have been calculated from the content rect,
+          // instead of the margin rect (against which floats are applied).
+          CreateInterval(min, max, col, row, aContentRect.TopLeft(),
+                         aWM, aContainerSize);
+        }
+
+        // Reset min and max for the next row or column.
+        min = -1;
+        max = -1;
       }
     }
 
-    // At the end of a row (or column if vertical), and found something.
-    if (curr == (aWM.IsVertical() ? h - 1 : w - 1) && (min != -1)) {
-      // We need to supply an offset of the content rect top left, since
-      // our col and row have been calculated from the content rect,
-      // instead of the margin rect (against which floats are applied).
-      CreateInterval(min, max, col, row, aContentRect.TopLeft(),
-                     aWM, aContainerSize);
+    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 difference 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;
+    dfType* df = new 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.
 
-  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();
+      // 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.
+          CreateInterval(min, max, col, row, nsPoint(),
+                         aWM, aContainerSize);
+        }
+
+        // Reset min and max for the next row or column.
+        min = dfSize;
+        max = -1;
+      }
+    }
+
+    // We've finished with the difference field.
+    delete[] df;
+
+    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();
   }
 }
 
@@ -1194,16 +1422,32 @@ nsFloatManager::ImageShapeInfo::Translat
 
   mBStart += aBlockStart;
   mBEnd += aBlockStart;
 }
 
 /////////////////////////////////////////////////////////////////////////////
 // FloatInfo
 
+static bool
+IsPercentOfIndefiniteSize(const nsStyleCoord& aCoord, nscoord aPercentBasis)
+{
+  return aPercentBasis == NS_UNCONSTRAINEDSIZE && aCoord.HasPercent();
+}
+
+static nscoord
+ResolveToDefiniteSize(const nsStyleCoord& aCoord, nscoord aPercentBasis)
+{
+  MOZ_ASSERT(aCoord.IsCoordPercentCalcUnit());
+  if (::IsPercentOfIndefiniteSize(aCoord, aPercentBasis)) {
+    return nscoord(0);
+  }
+  return std::max(nscoord(0), aCoord.ComputeCoordPercentCalc(aPercentBasis));
+}
+
 nsFloatManager::FloatInfo::FloatInfo(nsIFrame* aFrame,
                                      nscoord aLineLeft, nscoord aBlockStart,
                                      const LogicalRect& aMarginRect,
                                      WritingMode aWM,
                                      const nsSize& aContainerSize)
   : mFrame(aFrame)
   , mRect(ShapeInfo::ConvertToFloatLogical(aMarginRect, aWM, aContainerSize) +
           nsPoint(aLineLeft, aBlockStart))
@@ -1225,19 +1469,24 @@ nsFloatManager::FloatInfo::FloatInfo(nsI
       return;
 
     case StyleShapeSourceType::URL:
       MOZ_ASSERT_UNREACHABLE("shape-outside doesn't have URL source type!");
       return;
 
     case StyleShapeSourceType::Image: {
       float shapeImageThreshold = mFrame->StyleDisplay()->mShapeImageThreshold;
+      nscoord shapeMargin =
+        ::ResolveToDefiniteSize(mFrame->StyleDisplay()->mShapeMargin,
+                                aContainerSize.width);
       mShapeInfo = ShapeInfo::CreateImageShape(shapeOutside.GetShapeImage(),
                                                shapeImageThreshold,
+                                               shapeMargin,
                                                mFrame,
+                                               aMarginRect,
                                                aWM,
                                                aContainerSize);
       if (!mShapeInfo) {
         // Image is not ready, or fails to load, etc.
         return;
       }
 
       break;
@@ -1537,17 +1786,19 @@ nsFloatManager::ShapeInfo::CreatePolygon
 
   return MakeUnique<PolygonShapeInfo>(Move(vertices));
 }
 
 /* static */ UniquePtr<nsFloatManager::ShapeInfo>
 nsFloatManager::ShapeInfo::CreateImageShape(
   const UniquePtr<nsStyleImage>& aShapeImage,
   float aShapeImageThreshold,
+  nscoord aShapeMargin,
   nsIFrame* const aFrame,
+  const LogicalRect& aMarginRect,
   WritingMode aWM,
   const nsSize& aContainerSize)
 {
   MOZ_ASSERT(aShapeImage ==
              aFrame->StyleDisplay()->mShapeOutside.GetShapeImage(),
              "aFrame should be the frame that we got aShapeImage from");
 
   nsImageRenderer imageRenderer(aFrame, aShapeImage.get(),
@@ -1586,22 +1837,28 @@ nsFloatManager::ShapeInfo::CreateImageSh
 
   if (!map.IsMapped()) {
     return nullptr;
   }
 
   MOZ_ASSERT(sourceSurface->GetSize() == imageIntSize.ToUnknownSize(),
              "Who changes the size?");
 
+  nsRect marginRect = aMarginRect.GetPhysicalRect(aWM, aContainerSize);
+
   uint8_t* alphaPixels = map.GetData();
   int32_t stride = map.GetStride();
   return MakeUnique<ImageShapeInfo>(alphaPixels,
                                     stride,
                                     imageIntSize,
-                                    aShapeImageThreshold, contentRect, aWM,
+                                    aShapeImageThreshold,
+                                    aShapeMargin,
+                                    contentRect,
+                                    marginRect,
+                                    aWM,
                                     aContainerSize);
 }
 
 /* static */ nscoord
 nsFloatManager::ShapeInfo::ComputeEllipseLineInterceptDiff(
   const nscoord aShapeBoxBStart, const nscoord aShapeBoxBEnd,
   const nscoord aBStartCornerRadiusL, const nscoord aBStartCornerRadiusB,
   const nscoord aBEndCornerRadiusL, const nscoord aBEndCornerRadiusB,