Bug 1265342 Part 5c: Change ellipse difference field math to use postive-inline, positive-block quadrant. draft
 author Brad Werth Mon, 16 Apr 2018 09:46:15 -0700 changeset 784563 47c1ebb4248f731279941d1ab978bd1731096381 parent 784562 0a94e486a45f0013452be760f36cb8e90590bd64 child 784564 ac11227d33abe01298e27e9dc1fa1858be9fc601 push id 106973 push user bwerth@mozilla.com push date Wed, 18 Apr 2018 20:27:33 +0000 bugs 1265342 milestone 61.0a1
Bug 1265342 Part 5c: Change ellipse difference field math to use postive-inline, positive-block quadrant. MozReview-Commit-ID: KBKv9BKPBdK
```--- a/layout/generic/nsFloatManager.cpp
+++ b/layout/generic/nsFloatManager.cpp
@@ -828,23 +828,25 @@ nsFloatManager::EllipseShapeInfo::Ellips

// We have to calculate a distance field from the ellipse edge, then build
// intervals based on pixels with less than aShapeMargin distance to an
// edge pixel.

// x = inline, y = block. Due to symmetry, we only need to calculate the
// distance field for one quadrant of the ellipse. We choose the positive-x,
-  // mode). When we apply these intervals in LineLeft() and LineRight(), we
+  // mode). We choose this quadrant because it allows us to traverse our
+  // distance field in memory order, which is more cache efficient.
+  // When we apply these intervals in LineLeft() and LineRight(), we
// account for block ranges that hit other quadrants, or hit multiple

// Given this setup, computing the distance field is a one-pass O(n)
-  // operation that runs from block bottom-to-top, inline left-to-right. We
+  // operation that runs from block top-to-bottom, inline left-to-right. We
// use a chamfer 5-7-11 5x5 matrix to compute minimum distance to an edge
// 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 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,
@@ -872,17 +874,17 @@ nsFloatManager::EllipseShapeInfo::Ellips
const LayoutDeviceIntSize bounds =
aAppUnitsPerDevPixel);
// Since our distance field is computed with a 5x5 neighborhood, but only
// looks in the negative block and negative inline directions, it is
// effectively a 3x3 neighborhood. We need to expand our distance field by
-  // a further 2 pixels in both axes, on the trailing block edge and the
+  // a further 2 pixels in both axes, on the leading block edge and the
// leading inline edge. We call this edge area the expanded region.
static const int32_t iExpand = 2;
static const int32_t bExpand = 2;
const int32_t iSize = bounds.width + iExpand;
const int32_t bSize = bounds.height + bExpand;
auto df = MakeUniqueFallible<dfType[]>(iSize * bSize);
if (!df) {
// Without a distance field, we can't reason about the float area.
@@ -891,31 +893,29 @@ nsFloatManager::EllipseShapeInfo::Ellips

// First pass setting distance field, in negative block direction, three
// cases:
// 1) Expanded region pixel: set to MAX_MARGIN_5X.
// 2) Pixel within the ellipse: set to 0.
// 3) Other pixel: set to minimum neighborhood distance value, computed
//                 with 5-7-11 chamfer.

-  for (int32_t b = bSize - 1; b >= 0; --b) {
+  for (int32_t b = 0; b < bSize; ++b) {
+    bool bIsInExpandedRegion(b < bExpand);
+    nscoord bInAppUnits = (b - bExpand) * aAppUnitsPerDevPixel;
+
// Find the i intercept of the ellipse edge for this block row, and
// adjust it to compensate for the expansion of the inline dimension.
-    // If we're in the expanded region, or if we're using a b that's less
-    // than the bStart of the ellipse, the intercept is -1 before adjustment.
-    bool bIsInExpandedRegion(b >= bSize - bExpand);
-    nscoord bInAppUnits = b * aAppUnitsPerDevPixel;
-    bool bIsLessThanEllipseBStart(bInAppUnits < aShapeMargin);
-
+    // If we're in the expanded region, or if we're using a b that's more
+    // than the bEnd of the ellipse, the intercept is -1 before adjustment.
const int32_t iIntercept = iExpand + (
-      (bIsInExpandedRegion || bIsLessThanEllipseBStart) ? -1 :
+      (bIsInExpandedRegion || bIsMoreThanEllipseBEnd) ? -1 :
NSAppUnitsToIntPixels(
aAppUnitsPerDevPixel));

// Set iMax in preparation for this block row.
int32_t iMax = iIntercept;

for (int32_t i = 0; i < iSize; ++i) {
const int32_t index = i + b * iSize;

@@ -929,59 +929,54 @@ nsFloatManager::EllipseShapeInfo::Ellips
df[index] = 0;
} else {
// Case 3: Other pixel.

// Backward-looking neighborhood distance from target pixel X
// with chamfer 5-7-11 looks like:
//
// +--+--+--+
-        // |  | 5| X|
+        // |  |11|  |
// +--+--+--+
// |11| 7| 5|
// +--+--+--+
-        // |  |11|  |
+        // |  | 5| X|
// +--+--+--+
//
// X should be set to the minimum of the values of all of the numbered
// neighbors summed with the value in that chamfer cell.
df[index] = std::min<dfType>(df[index - 1] + 5,
-                    std::min<dfType>(df[index + iSize] + 5,
-                    std::min<dfType>(df[index + iSize - 1] + 7,
-                    std::min<dfType>(df[index + iSize - 2] + 11,
-                                     df[index + (iSize * 2) - 1] + 11))));
+                    std::min<dfType>(df[index - iSize] + 5,
+                    std::min<dfType>(df[index - iSize - 1] + 7,
+                    std::min<dfType>(df[index - iSize - 2] + 11,
+                                     df[index - (iSize * 2) - 1] + 11))));

// Check the df value and see if it's less than or equal to the
// usedMargin5X value.
if (df[index] <= usedMargin5X) {
MOZ_ASSERT(iMax < i);
iMax = i;
}
}
}

if (!bIsInExpandedRegion) {
-      MOZ_ASSERT(!(bIsLessThanEllipseBStart && iMax == iIntercept),
+      MOZ_ASSERT(!(bIsMoreThanEllipseBEnd && iMax == iIntercept),
"In the shape-margin region, we should always find a pixel "
"within the margin for each block row.");
-      // Origin for this interval is at the minimum value in both axes
-      // (which is the top center for horizontal-tb writing mode) adjusted
+      // Origin for this interval is at the center of the ellipse, adjusted
// in the positive block direction by bInAppUnits.
-      nsPoint origin(aCenter.x,
-                     aCenter.y - radiiPlusShapeMargin.height + bInAppUnits);
+      nsPoint origin(aCenter.x, aCenter.y + bInAppUnits);
// Size is an inline iMax plus 1 (to account for the whole pixel) dev
// pixels, by 1 block dev pixel. We convert this to app units.
nsSize size((iMax - iExpand + 1) * aAppUnitsPerDevPixel,
aAppUnitsPerDevPixel);
mIntervals.AppendElement(nsRect(origin, size));
}
}
-
-  // Reverse the intervals to keep the array sorted on the block direction.
-  mIntervals.Reverse();
}

nscoord
nsFloatManager::EllipseShapeInfo::LineEdge(const nscoord aBStart,
const nscoord aBEnd,
bool aIsLineLeft) const
{
// If no mShapeMargin, just compute the edge using math.
@@ -997,48 +992,53 @@ nsFloatManager::EllipseShapeInfo::LineEd

// We are checking against our intervals. Make sure we have some.
if (mIntervals.IsEmpty()) {
NS_WARNING("With mShapeMargin > 0, we can't proceed without intervals.");
return 0;
}

// Map aBStart and aBEnd into our intervals. Our intervals are calculated
-  // for the upper-right quadrant (in terms of horizontal-tb writing mode).
+  // for the lower-right quadrant (in terms of horizontal-tb writing mode).
// If aBStart and aBEnd span the center of the ellipse, then we know we
// are at the maximum displacement from the center.
-  bool bStartIsAboveOrAtCenter = (aBStart <= mCenter.y);
+  bool bStartIsAboveCenter = (aBStart < mCenter.y);
bool bEndIsBelowOrAtCenter = (aBEnd >= mCenter.y);
-  if (bStartIsAboveOrAtCenter && bEndIsBelowOrAtCenter) {
+  if (bStartIsAboveCenter && bEndIsBelowOrAtCenter) {
return mCenter.x + (aIsLineLeft ? (-mRadii.width - mShapeMargin) :
}

// aBStart and aBEnd don't span the center. Since the intervals are
-  // strictly wider approaching the center (the end of the mIntervals array),
-  // we only need to find the interval at the block value closest to the
-  // center. We find the max of aBStart, aBEnd, and their reflections --
-  // whichever two of them are within the upper-right quadrant.
-  nscoord bLargestWithinIntervals = std::max(
-    bStartIsAboveOrAtCenter ? aBStart : aBStart - (aBStart - mCenter.y) * 2,
-    bEndIsBelowOrAtCenter ? aBEnd - (aBEnd - mCenter.y) * 2 : aBEnd);
+  // strictly wider approaching the center (the start of the mIntervals
+  // array), we only need to find the interval at the block value closest to
+  // the center. We find the min of aBStart, aBEnd, and their reflections --
+  // whichever two of them are within the lower-right quadrant. When we
+  // reflect from the upper-right quadrant to the lower-right, we have to
+  // subtract 1 from the reflection, to account that block values are always
+  nscoord bSmallestWithinIntervals = std::min(
+    bStartIsAboveCenter ? aBStart + (mCenter.y - aBStart) * 2 - 1 : aBStart,
+    bEndIsBelowOrAtCenter ? aBEnd : aBEnd + (mCenter.y - aBEnd) * 2 - 1);

-  MOZ_ASSERT(bLargestWithinIntervals >= BStart() &&
-             bLargestWithinIntervals < mCenter.y,
+  MOZ_ASSERT(bSmallestWithinIntervals >= mCenter.y &&
+             bSmallestWithinIntervals < BEnd(),
"We should have a block value within the intervals.");

size_t index = MinIntervalIndexContainingY(mIntervals,
-                                             bLargestWithinIntervals);
+                                             bSmallestWithinIntervals);
MOZ_ASSERT(index < mIntervals.Length(),
"We should have found a matching interval for this block value.");

// The interval is storing the line right value. If aIsLineLeft is true,
-  // return the line right value reflected about the center.
+  // return the line right value reflected about the center. Again, we
+  // subtract 1 from the reflection to account for leading inline edge.
nscoord iLineRight = mIntervals[index].XMost();
-  return aIsLineLeft ? iLineRight - (iLineRight - mCenter.x) * 2 : iLineRight;
+  return aIsLineLeft ? iLineRight - (iLineRight - mCenter.x) * 2 - 1
+                     : iLineRight;
}

nscoord
nsFloatManager::EllipseShapeInfo::LineLeft(const nscoord aBStart,
const nscoord aBEnd) const
{
return LineEdge(aBStart, aBEnd, true);
}```