Bug 1461046 Part 4: Change PolygonShapeInfo to tolerate polygons with only 1 or 2 vertices. r=dholbert
authorBrad Werth <bwerth@mozilla.com>
Tue, 22 May 2018 15:54:21 -0700
changeset 421163 128f8e1b8dcd0d8201c7e6ef9711e346576d2709
parent 421162 b3375f24897bf84da24d4e9391dedb235f6a6435
child 421164 b818a0c11897bea461e16a61c505db686fbd4010
push id64818
push userbwerth@mozilla.com
push dateMon, 04 Jun 2018 17:18:30 +0000
treeherderautoland@bd46d28842ff [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdholbert
bugs1461046
milestone62.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 1461046 Part 4: Change PolygonShapeInfo to tolerate polygons with only 1 or 2 vertices. r=dholbert MozReview-Commit-ID: ICcIUulgSCW
layout/generic/nsFloatManager.cpp
--- a/layout/generic/nsFloatManager.cpp
+++ b/layout/generic/nsFloatManager.cpp
@@ -1272,24 +1272,30 @@ public:
                    const nsRect& aMarginRect);
 
   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; }
   nscoord BEnd() const override { return mBEnd; }
-  bool IsEmpty() const override { return mEmpty; }
+  bool IsEmpty() const override {
+    // A PolygonShapeInfo is never empty, because the parser prevents us from
+    // creating a shape with no vertices. If we only have 1 vertex, the
+    // shape acts like a point. With 2 non-coincident vertices, the shape
+    // acts like a line.
+    return false;
+  }
 
   void Translate(nscoord aLineLeft, nscoord aBlockStart) override;
 
 private:
-  // Helper method for determining if the vertices define a float area at
-  // all, and to set mBStart and mBEnd based on the vertices' y extent.
-  void ComputeEmptinessAndExtent();
+  // Helper method for determining the mBStart and mBEnd based on the
+  // vertices' y extent.
+  void ComputeExtent();
 
   // Helper method for implementing LineLeft() and LineRight().
   nscoord ComputeLineIntercept(
     const nscoord aBStart,
     const nscoord aBEnd,
     nscoord (*aCompareOp) (std::initializer_list<nscoord>),
     const nscoord aLineInterceptInitialValue) const;
 
@@ -1307,52 +1313,41 @@ private:
   // These are only generated and used in float area calculations for
   // shape-margin > 0. Each interval is a rectangle that is one device pixel
   // deep in the block axis. The values are stored as block edges in the y
   // coordinates, and inline edges as the x coordinates.
 
   // The intervals are stored in ascending order on y.
   nsTArray<nsRect> mIntervals;
 
-  // If mEmpty is true, that means the polygon encloses no area.
-  bool mEmpty = false;
-
-  // Computed block start and block end value of the polygon shape.
-  //
-  // If mEmpty is false, their initial values nscoord_MAX and nscoord_MIN
-  // are used as sentinels for computing min() and max() in the
-  // constructor, and mBStart is guaranteed to be less than or equal to
-  // mBEnd. If mEmpty is true, their values do not matter.
+  // Computed block start and block end value of the polygon shape. These
+  // initial values are set to correct values in ComputeExtent(), which is
+  // called from all constructors. Afterwards, mBStart is guaranteed to be
+  // less than or equal to mBEnd.
   nscoord mBStart = nscoord_MAX;
   nscoord mBEnd = nscoord_MIN;
 };
 
 nsFloatManager::PolygonShapeInfo::PolygonShapeInfo(nsTArray<nsPoint>&& aVertices)
   : mVertices(aVertices)
 {
-  ComputeEmptinessAndExtent();
+  ComputeExtent();
 }
 
 nsFloatManager::PolygonShapeInfo::PolygonShapeInfo(
   nsTArray<nsPoint>&& aVertices,
   nscoord aShapeMargin,
   int32_t aAppUnitsPerDevPixel,
   const nsRect& aMarginRect)
   : mVertices(aVertices)
 {
   MOZ_ASSERT(aShapeMargin > 0, "This constructor should only be used for a "
                                "polygon with a positive shape-margin.");
 
-  ComputeEmptinessAndExtent();
-
-  // If we're empty, then the float area stays empty, even with a positive
-  // shape-margin.
-  if (mEmpty) {
-    return;
-  }
+  ComputeExtent();
 
   // 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
@@ -1431,17 +1426,17 @@ nsFloatManager::PolygonShapeInfo::Polygo
     // the right edge of the polygon at one-dev-pixel-thick strip of b. We
     // have a ComputeLineIntercept function that takes and returns app unit
     // coordinates in the space of aMarginRect. So to pass in b values, we
     // first have to add the aMarginRect.y value. And for the values that we
     // get out, we have to subtract away the aMarginRect.x value before
     // converting the app units to dev pixels.
     nscoord bInAppUnitsMarginRect = bInAppUnits + aMarginRect.y;
     bool bIsLessThanPolygonBStart(bInAppUnitsMarginRect < mBStart);
-    bool bIsMoreThanPolygonBEnd(bInAppUnitsMarginRect >= mBEnd);
+    bool bIsMoreThanPolygonBEnd(bInAppUnitsMarginRect > mBEnd);
 
     const int32_t iLeftEdge = (bIsInExpandedRegion ||
                                bIsLessThanPolygonBStart ||
                                bIsMoreThanPolygonBEnd) ? nscoord_MAX :
       kiExpansionPerSide + NSAppUnitsToIntPixels(
         ComputeLineIntercept(bInAppUnitsMarginRect,
                              bInAppUnitsMarginRect + aAppUnitsPerDevPixel,
                              std::min<nscoord>, nscoord_MAX) - aMarginRect.x,
@@ -1462,19 +1457,21 @@ nsFloatManager::PolygonShapeInfo::Polygo
                  "Our distance field index should be in-bounds.");
 
       // Handle our three cases, in order.
       if (i < kiExpansionPerSide ||
           i >= iSize - kiExpansionPerSide ||
           bIsInExpandedRegion) {
         // Case 1: Expanded pixel.
         df[index] = MAX_MARGIN_5X;
-      } else if ((int32_t)i >= iLeftEdge && (int32_t)i < iRightEdge) {
-        // Case 2: Polygon pixel.
-        df[index] = 0;
+      } else if ((int32_t)i >= iLeftEdge && (int32_t)i <= iRightEdge) {
+        // Case 2: Polygon pixel, either inside or just adjacent to the right
+        // edge. We need this special distinction to detect a space between
+        // edges that is less than one dev pixel.
+        df[index] = (int32_t)i < iRightEdge ? 0 : 5;
       } else {
         // Case 3: Other pixel.
 
         // Backward-looking neighborhood distance from target pixel X
         // with chamfer 5-7-11 looks like:
         //
         // +--+--+--+--+--+
         // |  |11|  |11|  |
@@ -1617,18 +1614,16 @@ nsFloatManager::PolygonShapeInfo::Polygo
   mBStart = std::min(mBStart, mBStart - aShapeMargin);
   mBEnd = std::max(mBEnd, mBEnd + aShapeMargin);
 }
 
 nscoord
 nsFloatManager::PolygonShapeInfo::LineLeft(const nscoord aBStart,
                                            const nscoord aBEnd) const
 {
-  MOZ_ASSERT(!mEmpty, "Shouldn't be called if the polygon encloses no area.");
-
   // Use intervals if we have them.
   if (!mIntervals.IsEmpty()) {
     return LineEdge(mIntervals, aBStart, aBEnd, true);
   }
 
   // We want the line-left-most inline-axis coordinate where the
   // (block-axis) aBStart/aBEnd band crosses a line segment of the polygon.
   // To get that, we start as line-right as possible (at nscoord_MAX). Then
@@ -1640,120 +1635,117 @@ nsFloatManager::PolygonShapeInfo::LineLe
   // parameter nscoord, not the minimum value of nscoord.
   return ComputeLineIntercept(aBStart, aBEnd, std::min<nscoord>, nscoord_MAX);
 }
 
 nscoord
 nsFloatManager::PolygonShapeInfo::LineRight(const nscoord aBStart,
                                             const nscoord aBEnd) const
 {
-  MOZ_ASSERT(!mEmpty, "Shouldn't be called if the polygon encloses no area.");
-
   // Use intervals if we have them.
   if (!mIntervals.IsEmpty()) {
     return LineEdge(mIntervals, aBStart, aBEnd, false);
   }
 
   // Similar to LineLeft(). Though here, we want the line-right-most
   // inline-axis coordinate, so we instead start at nscoord_MIN and use
   // std::max() to get the biggest inline-coordinate among those
   // intersection points.
   return ComputeLineIntercept(aBStart, aBEnd, std::max<nscoord>, nscoord_MIN);
 }
 
 void
-nsFloatManager::PolygonShapeInfo::ComputeEmptinessAndExtent()
+nsFloatManager::PolygonShapeInfo::ComputeExtent()
 {
-  // Polygons with fewer than three vertices result in an empty area.
-  // https://drafts.csswg.org/css-shapes/#funcdef-polygon
-  if (mVertices.Length() < 3) {
-    mEmpty = true;
-    return;
-  }
-
-  auto Determinant = [] (const nsPoint& aP0, const nsPoint& aP1) {
-    // Returns the determinant of the 2x2 matrix [aP0 aP1].
-    // https://en.wikipedia.org/wiki/Determinant#2_.C3.97_2_matrices
-    return aP0.x * aP1.y - aP0.y * aP1.x;
-  };
-
-  // See if we have any vertices that are non-collinear with the first two.
-  // (If a polygon's vertices are all collinear, it encloses no area.)
-  bool isEntirelyCollinear = true;
-  const nsPoint& p0 = mVertices[0];
-  const nsPoint& p1 = mVertices[1];
-  for (size_t i = 2; i < mVertices.Length(); ++i) {
-    const nsPoint& p2 = mVertices[i];
-
-    // If the determinant of the matrix formed by two points is 0, that
-    // means they're collinear with respect to the origin. Here, if it's
-    // nonzero, then p1 and p2 are non-collinear with respect to p0, i.e.
-    // the three points are non-collinear.
-    if (Determinant(p2 - p0, p1 - p0) != 0) {
-      isEntirelyCollinear = false;
-      break;
-    }
-  }
-
-  if (isEntirelyCollinear) {
-    mEmpty = true;
-    return;
-  }
-
   // mBStart and mBEnd are the lower and the upper bounds of all the
   // vertex.y, respectively. The vertex.y is actually on the block-axis of
   // the float manager's writing mode.
   for (const nsPoint& vertex : mVertices) {
     mBStart = std::min(mBStart, vertex.y);
     mBEnd = std::max(mBEnd, vertex.y);
   }
+
+  MOZ_ASSERT(mBStart <= mBEnd, "Start of float area should be less than "
+                               "or equal to the end.");
 }
 
 nscoord
 nsFloatManager::PolygonShapeInfo::ComputeLineIntercept(
   const nscoord aBStart,
   const nscoord aBEnd,
   nscoord (*aCompareOp) (std::initializer_list<nscoord>),
   const nscoord aLineInterceptInitialValue) const
 {
   MOZ_ASSERT(aBStart <= aBEnd,
              "The band's block start is greater than its block end?");
 
   const size_t len = mVertices.Length();
   nscoord lineIntercept = aLineInterceptInitialValue;
 
+  // We have some special treatment of horizontal lines between vertices.
+  // Generally, we can ignore the impact of the horizontal lines since their
+  // endpoints will be included in the lines preceeding or following them.
+  // However, it's possible the polygon is entirely a horizontal line,
+  // possibly built from more than one horizontal segment. In such a case,
+  // we need to have the horizontal line(s) contribute to the line intercepts.
+  // We do this by accepting horizontal lines until we find a non-horizontal
+  // line, after which all further horizontal lines are ignored.
+  bool canIgnoreHorizontalLines = false;
+
   // Iterate each line segment {p0, p1}, {p1, p2}, ..., {pn, p0}.
   for (size_t i = 0; i < len; ++i) {
     const nsPoint* smallYVertex = &mVertices[i];
     const nsPoint* bigYVertex = &mVertices[(i + 1) % len];
 
     // Swap the two points to satisfy the requirement for calling
     // XInterceptAtY.
     if (smallYVertex->y > bigYVertex->y) {
       std::swap(smallYVertex, bigYVertex);
     }
 
-    if (aBStart >= bigYVertex->y || aBEnd <= smallYVertex->y ||
-        smallYVertex->y == bigYVertex->y) {
-      // Skip computing the intercept if a) the band doesn't intersect the
-      // line segment (even if it crosses one of two the vertices); or b)
-      // the line segment is horizontal. It's OK because the two end points
-      // forming this horizontal segment will still be considered if each of
-      // them is forming another non-horizontal segment with other points.
+    // Generally, we need to ignore line segments that either don't intersect
+    // the band, or merely touch it. However, if the polygon has no block extent
+    // (it is a point, or a horizontal line), and the band touches the line
+    // segment, we let that line segment through.
+    if ((aBStart >= bigYVertex->y || aBEnd <= smallYVertex->y) &&
+        !(mBStart == mBEnd && aBStart == bigYVertex->y)) {
+      // Skip computing the intercept if the band doesn't intersect the
+      // line segment.
       continue;
     }
 
-    nscoord bStartLineIntercept =
-      aBStart <= smallYVertex->y
-        ? smallYVertex->x
-        : XInterceptAtY(aBStart, *smallYVertex, *bigYVertex);
-    nscoord bEndLineIntercept =
-      aBEnd >= bigYVertex->y
-        ? bigYVertex->x
-        : XInterceptAtY(aBEnd, *smallYVertex, *bigYVertex);
+    nscoord bStartLineIntercept;
+    nscoord bEndLineIntercept;
+
+    if (smallYVertex->y == bigYVertex->y) {
+      // The line is horizontal; see if we can ignore it.
+      if (canIgnoreHorizontalLines) {
+        continue;
+      }
+
+      // For a horizontal line that we can't ignore, we treat the two x value
+      // ends as the bStartLineIntercept and bEndLineIntercept. It doesn't
+      // matter which is applied to which, because they'll both be applied
+      // to aCompareOp.
+      bStartLineIntercept = smallYVertex->x;
+      bEndLineIntercept = bigYVertex->x;
+    } else {
+      // This is not a horizontal line. We can now ignore all future
+      // horizontal lines.
+      canIgnoreHorizontalLines = true;
+
+      bStartLineIntercept =
+        aBStart <= smallYVertex->y
+          ? smallYVertex->x
+          : XInterceptAtY(aBStart, *smallYVertex, *bigYVertex);
+      bEndLineIntercept =
+        aBEnd >= bigYVertex->y
+          ? bigYVertex->x
+          : XInterceptAtY(aBEnd, *smallYVertex, *bigYVertex);
+    }
 
     // If either new intercept is more extreme than lineIntercept (per
     // aCompareOp), then update lineIntercept to that value.
     lineIntercept =
       aCompareOp({lineIntercept, bStartLineIntercept, bEndLineIntercept});
   }
 
   return lineIntercept;