Bug 1265342 Part 4a: Complete the implementation of shape-margin for shape-outside: image (handling shape-margin: > 0). r=dholbert
authorBrad Werth <bwerth@mozilla.com>
Thu, 22 Feb 2018 11:11:03 -0800
changeset 415557 e5c0631408b2159c4e7ccba4998b2dc35e00eacf
parent 415556 3b2ffd07d8e669327b56864f71e77d7b1eaa4be9
child 415558 546464551e6411c46b85203a43375ad205827bbb
push id33900
push userdluca@mozilla.com
push dateThu, 26 Apr 2018 04:51:04 +0000
treeherdermozilla-central@76f35d0ecaa6 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdholbert
bugs1265342
milestone61.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1265342 Part 4a: Complete the implementation of shape-margin for shape-outside: image (handling shape-margin: > 0). r=dholbert MozReview-Commit-ID: 4xqfqWB78Oh
layout/generic/nsFloatManager.cpp
--- a/layout/generic/nsFloatManager.cpp
+++ b/layout/generic/nsFloatManager.cpp
@@ -1066,22 +1066,23 @@ nsFloatManager::ImageShapeInfo::ImageSha
       // iMin and max store the start and end of the float area for the row
       // or column represented by this iteration of the outer loop.
       int32_t iMin = -1;
       int32_t iMax = -1;
 
       for (int32_t i = 0; i < iSize; ++i) {
         const int32_t col = aWM.IsVertical() ? b : i;
         const int32_t row = aWM.IsVertical() ? i : b;
+        const int32_t index = col + row * aStride;
 
         // Determine if the alpha pixel at this row and column has a value
-        // greater than the threshold. If it does, update our iMin and iMax values
-        // to track the edges of the float area for this row or column.
+        // greater than the threshold. If it does, update our iMin and iMax
+        // values to track the edges of the float area for this row or column.
         // https://drafts.csswg.org/css-shapes-1/#valdef-shape-image-threshold-number
-        const uint8_t alpha = aAlphaPixels[col + row * aStride];
+        const uint8_t alpha = aAlphaPixels[index];
         if (alpha > threshold) {
           if (iMin == -1) {
             iMin = i;
           }
           MOZ_ASSERT(iMax < i);
           iMax = i;
         }
       }
@@ -1098,16 +1099,251 @@ nsFloatManager::ImageShapeInfo::ImageSha
 
     if (aWM.IsVerticalRL()) {
       // vertical-rl or sideways-rl.
       // 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 opaque pixel.
+
+    // Roughly: for each pixel in the margin box, we need to determine the
+    // distance to the nearest opaque image-pixel.  If that distance is less
+    // than aShapeMargin, we consider this margin-box pixel as being part of
+    // the float area.
+
+    // Computing the distance 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 shape-margin value that we care about faithfully rendering,
+    // times 5. A 16-bit unsigned int can represent up to ~ 65K which means
+    // we can handle a margin up to ~ 13K device pixels. That's good enough
+    // for practical usage. Any supplied shape-margin value higher than this
+    // maximum will be clamped.
+    typedef uint16_t dfType;
+    const dfType MAX_CHAMFER_VALUE = 11;
+    const dfType MAX_MARGIN = (std::numeric_limits<dfType>::max() -
+                               MAX_CHAMFER_VALUE) / 5;
+    const dfType MAX_MARGIN_5X = MAX_MARGIN * 5;
+
+    // Convert aShapeMargin to dev pixels, convert that into 5x-dev-pixel
+    // space, then clamp to MAX_MARGIN_5X.
+    float shapeMarginDevPixels =
+      NSAppUnitsToFloatPixels(aShapeMargin, aAppUnitsPerDevPixel);
+    int32_t shapeMarginDevPixelsInt5X =
+      NSToIntRound(5.0f * shapeMarginDevPixels);
+    NS_WARNING_ASSERTION(shapeMarginDevPixelsInt5X <= MAX_MARGIN_5X,
+                         "shape-margin is too large and is being clamped.");
+    dfType usedMargin5X = (dfType)std::min((int32_t)MAX_MARGIN_5X,
+                                           shapeMarginDevPixelsInt5X);
+
+    // 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. To make this work,
+    // we calculate a dfOffset value which is the top left of the content
+    // rect relative to the margin rect.
+    nsPoint offsetPoint = aContentRect.TopLeft() - aMarginRect.TopLeft();
+    LayoutDeviceIntPoint dfOffset =
+      LayoutDevicePixel::FromAppUnitsRounded(offsetPoint,
+                                             aAppUnitsPerDevPixel);
+
+    // 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, 2 on the leading edge and 2 on the trailing edge.
+    // We call this edge area the "expanded region".
+
+    // Since dfOffset will be used in comparisons against expanded region
+    // pixel values, it's convenient to add 2 to dfOffset in both axes, to
+    // simplify comparison math later.
+    dfOffset.x += 2;
+    dfOffset.y += 2;
+
+    // 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 LayoutDeviceIntSize marginRectDevPixels =
+      LayoutDevicePixel::FromAppUnitsRounded(aMarginRect.Size(),
+                                             aAppUnitsPerDevPixel);
+    const int32_t wEx = marginRectDevPixels.width + 4;
+    const int32_t hEx = marginRectDevPixels.height + 4;
+
+    // Since the margin-box size is CSS controlled, and large values will
+    // generate large wEx and hEx values, we do a falliable allocation for
+    // the distance field. If allocation fails, we early exit and layout will
+    // be wrong, but we'll avoid aborting from OOM.
+    auto df = MakeUniqueFallible<dfType[]>(wEx * hEx);
+    if (!df) {
+      // Without a distance field, we can't reason about the float area.
+      return;
+    }
+
+    const int32_t bSize = aWM.IsVertical() ? wEx : hEx;
+    const int32_t iSize = aWM.IsVertical() ? hEx : wEx;
+
+    // First pass setting distance field, starting at top-left, 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.
+
+    // Scan the pixels in a double loop. For horizontal writing modes, we do
+    // this row by row, from top to bottom. For vertical writing modes, we do
+    // column by column, from left to right. We define the two loops
+    // generically, then figure out the rows and cols within the inner loop.
+    for (int32_t b = 0; b < bSize; ++b) {
+      for (int32_t i = 0; i < iSize; ++i) {
+        const int32_t col = aWM.IsVertical() ? b : i;
+        const int32_t row = aWM.IsVertical() ? i : b;
+        const int32_t index = col + row * 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 &&
+                   col < (dfOffset.x + w) &&
+                   row >= dfOffset.y &&
+                   row < (dfOffset.y + h) &&
+                   aAlphaPixels[col - dfOffset.x +
+                                (row - dfOffset.y) * 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 in reverse order from
+    // the first pass. All of our opaque pixels have been set to 0, and all
+    // of our expanded region 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 that were processed
+    // after them in the first pass. This time we reverse iterate so we can
+    // apply the forward-looking chamfer.
+
+    // This time, we constrain our outer and inner loop to ignore the
+    // expanded region pixels. For each pixel we iterate, we set the df value
+    // to the minimum forward-looking neighborhood distance value, computed
+    // with a 5-7-11 chamfer. We also check each df value against the
+    // usedMargin5X threshold, and use that to set the iMin and iMax values
+    // for the interval we'll create for that block axis value (b).
+
+    // 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.
+    for (int32_t b = bSize - 3; b >= 2; --b) {
+      // iMin tracks the first df pixel and iMax the last df pixel whose
+      // df[] value is less than usedMargin5X. Set iMin and iMax in
+      // preparation for this row or column.
+      int32_t iMin = iSize;
+      int32_t iMax = -1;
+
+      for (int32_t i = iSize - 3; i >= 2; --i) {
+        const int32_t col = aWM.IsVertical() ? b : i;
+        const int32_t row = aWM.IsVertical() ? i : b;
+        const int32_t index = col + row * wEx;
+
+        // 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 it's less than
+        // or equal to the usedMargin5X value.
+        if (df[index] <= usedMargin5X) {
+          if (iMax == -1) {
+            iMax = i;
+          }
+          MOZ_ASSERT(iMin > i);
+          iMin = i;
+        }
+      }
+
+      if (iMax != -1) {
+        // Our interval values, iMin, iMax, and b are all calculated from
+        // the expanded region, which is based on the margin rect. To create
+        // our interval, we have to subtract 2 from (iMin, iMax, and b) to
+        // account for the expanded region edges.  This produces coords that
+        // are relative to our margin-rect, so we pass in
+        // aMarginRect.TopLeft() to make CreateInterval convert to our
+        // container's coordinate space.
+        CreateInterval(iMin - 2, iMax - 2, b - 2, aAppUnitsPerDevPixel,
+                       aMarginRect.TopLeft(), aWM, aContainerSize);
+      }
+    }
+
+    if (!aWM.IsVerticalRL()) {
+      // Anything other than vertical-rl or sideways-rl.
+      // 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].Y();
     mBEnd = mIntervals.LastElement().YMost();
   }
 }