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 804098 128f8e1b8dcd0d8201c7e6ef9711e346576d2709
parent 804097 b3375f24897bf84da24d4e9391dedb235f6a6435
child 804099 b818a0c11897bea461e16a61c505db686fbd4010
push id112312
push userbmo:standard8@mozilla.com
push dateTue, 05 Jun 2018 16:07:56 +0000
reviewersdholbert
bugs1461046
milestone62.0a1
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;