Changeset 154349 in webkit

Timestamp:

Aug 20, 2013 12:21:36 PM (11 years ago)

Author:

hmuller@adobe.com

Message:

<​https://webkit.org/b/119849> [CSS Shapes] Complete RasterShape::firstIncludedIntervalLogicalTop()

Reviewed by Alexandru Chiculita.

Source/WebCore:

Completed the implementation of RasterShape::firstIncludedIntervalLogicalTop(). The
method now computes first logical top location where a line segment can be laid
out within a RasterShape, i.e. a shape derived from an image valued URL resource.

A detailed description of the algorithm can be found in
​http://hansmuller-webkit.blogspot.com/2013/08/first-fit-location-for-image-shapes.html.

The new tests exposed a bug in the existing getIncludedIntervals() method. A shape
with a vertical gap that spans the entire line now causes the method to short circuit
and return an empty interval list.

Tests: fast/shapes/shape-inside/shape-inside-image-003.html

fast/shapes/shape-inside/shape-inside-image-004.html
fast/shapes/shape-inside/shape-inside-image-005.html

• rendering/shapes/RasterShape.cpp:

(WebCore::RasterShapeIntervals::firstIncludedIntervalY):
(WebCore::RasterShapeIntervals::getIncludedIntervals):
(WebCore::RasterShape::firstIncludedIntervalLogicalTop):

• rendering/shapes/RasterShape.h:

LayoutTests:

Verify that the first fit algorithm works correctly for complex image shapes.
For this set of tests the image is specified with an SVG file.

• fast/shapes/resources/svg-shape-001.svg: Added.
• fast/shapes/shape-inside/shape-inside-image-003-expected.html: Added.
• fast/shapes/shape-inside/shape-inside-image-003.html: Added.
• fast/shapes/shape-inside/shape-inside-image-004-expected.html: Added.
• fast/shapes/shape-inside/shape-inside-image-004.html: Added.
• fast/shapes/shape-inside/shape-inside-image-005-expected.html: Added.
• fast/shapes/shape-inside/shape-inside-image-005.html: Added.

Location:

trunk

Files:

• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/fast/shapes/resources/svg-shape-001.svg (added)
• LayoutTests/fast/shapes/shape-inside/shape-inside-image-003-expected.html (added)
• LayoutTests/fast/shapes/shape-inside/shape-inside-image-003.html (added)
• LayoutTests/fast/shapes/shape-inside/shape-inside-image-004-expected.html (added)
• LayoutTests/fast/shapes/shape-inside/shape-inside-image-004.html (added)
• LayoutTests/fast/shapes/shape-inside/shape-inside-image-005-expected.html (added)
• LayoutTests/fast/shapes/shape-inside/shape-inside-image-005.html (added)
• Source/WebCore/ChangeLog (modified) (1 diff)
• Source/WebCore/rendering/shapes/RasterShape.cpp (modified) (6 diffs)
• Source/WebCore/rendering/shapes/RasterShape.h (modified) (1 diff)

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2013-08-20  Hans Muller  <hmuller@adobe.com>
+        <https://webkit.org/b/119849> [CSS Shapes] Complete RasterShape::firstIncludedIntervalLogicalTop()
+
+        Reviewed by Alexandru Chiculita.
+
+        Verify that the first fit algorithm works correctly for complex image shapes.
+        For this set of tests the image is specified with an SVG file.
+
+        * fast/shapes/resources/svg-shape-001.svg: Added.
+        * fast/shapes/shape-inside/shape-inside-image-003-expected.html: Added.
+        * fast/shapes/shape-inside/shape-inside-image-003.html: Added.
+        * fast/shapes/shape-inside/shape-inside-image-004-expected.html: Added.
+        * fast/shapes/shape-inside/shape-inside-image-004.html: Added.
+        * fast/shapes/shape-inside/shape-inside-image-005-expected.html: Added.
+        * fast/shapes/shape-inside/shape-inside-image-005.html: Added.
+
 2013-08-20  Michael Saboff  <msaboff@apple.com>
 

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2013-08-20  Hans Muller  <hmuller@adobe.com>
+
+        <https://webkit.org/b/119849> [CSS Shapes] Complete RasterShape::firstIncludedIntervalLogicalTop()
+
+        Reviewed by Alexandru Chiculita.
+
+        Completed the implementation of RasterShape::firstIncludedIntervalLogicalTop(). The
+        method now computes first logical top location where a line segment can be laid
+        out within a RasterShape, i.e. a shape derived from an image valued URL resource.
+
+        A detailed description of the algorithm can be found in
+        http://hansmuller-webkit.blogspot.com/2013/08/first-fit-location-for-image-shapes.html.
+
+        The new tests exposed a bug in the existing getIncludedIntervals() method. A shape
+        with a vertical gap that spans the entire line now causes the method to short circuit
+        and return an empty interval list.
+
+        Tests: fast/shapes/shape-inside/shape-inside-image-003.html
+               fast/shapes/shape-inside/shape-inside-image-004.html
+               fast/shapes/shape-inside/shape-inside-image-005.html
+
+        * rendering/shapes/RasterShape.cpp:
+        (WebCore::RasterShapeIntervals::firstIncludedIntervalY):
+        (WebCore::RasterShapeIntervals::getIncludedIntervals):
+        (WebCore::RasterShape::firstIncludedIntervalLogicalTop):
+        * rendering/shapes/RasterShape.h:
+
 2013-08-20  Pratik Solanki  <psolanki@apple.com>
 

trunk/Source/WebCore/rendering/shapes/RasterShape.cpp

@@ -49 +49 @@
 }
 
+bool RasterShapeIntervals::firstIncludedIntervalY(int minY, const IntSize& minSize, LayoutUnit& result) const
+{
+    for (int y = minY; y <= bounds().maxY() - minSize.height(); y++) {
+        Region lineRegion(IntRect(bounds().x(), y, bounds().width(), minSize.height()));
+        lineRegion.intersect(m_region);
+        if (lineRegion.isEmpty())
+            continue;
+
+        const Vector<IntRect>& lineRects = lineRegion.rects();
+        ASSERT(lineRects.size() > 0);
+
+        for (unsigned i = 0; i < lineRects.size(); i++) {
+            IntRect rect = lineRects[i];
+            if (rect.width() >= minSize.width() && lineRegion.contains(Region(IntRect(IntPoint(rect.x(), y), minSize)))) {
+                result = y;
+                return true;
+            }
+        }
+    }
+    return false;
+}
+
 static inline IntRect alignedRect(IntRect r, int y1, int y2)
 {
@@ -64 +86 @@
         return;
 
-    Vector<IntRect> lineRects = lineRegion.rects();
+    const Vector<IntRect>& lineRects = lineRegion.rects();
     ASSERT(lineRects.size() > 0);
 
@@ -72 +94 @@
     // The loop below uses Regions to compute the intersection of the horizontal
     // shape intervals that fall within the line's box.
-    int lineY = lineRects[0].y();
+    int currentLineY = lineRects[0].y();
+    int currentLineMaxY = lineRects[0].maxY();
     for (unsigned i = 0; i < lineRects.size(); ++i) {
-        if (lineRects[i].y() != lineY) {
+        int lineY = lineRects[i].y();
+        ASSERT(lineY >= currentLineY);
+        if (lineY > currentLineMaxY) {
+            // We've encountered a vertical gap in lineRects, there are no included intervals.
+            return;
+        }
+        if (lineY > currentLineY) {
+            currentLineY = lineY;
+            currentLineMaxY = lineRects[i].maxY();
             segmentsRegion.intersect(intervalsRegion);
             intervalsRegion = Region();
-        }
+        } else
+            currentLineMaxY = std::max<int>(currentLineMaxY, lineRects[i].maxY());
         intervalsRegion.unite(Region(alignedRect(lineRects[i], y1, y2)));
-        lineY = lineRects[i].y();
     }
     if (!intervalsRegion.isEmpty())
         segmentsRegion.intersect(intervalsRegion);
 
-    Vector<IntRect> segmentRects = segmentsRegion.rects();
+    const Vector<IntRect>& segmentRects = segmentsRegion.rects();
     for (unsigned i = 0; i < segmentRects.size(); ++i)
         result.append(LineSegment(segmentRects[i].x(), segmentRects[i].maxX()));
@@ -99 +130 @@
         return;
 
-    Vector<IntRect> lineRects = lineRegion.rects();
+    const Vector<IntRect>& lineRects = lineRegion.rects();
     ASSERT(lineRects.size() > 0);
 
@@ -106 +137 @@
         segmentsRegion.unite(Region(alignedRect(lineRects[i], y1, y2)));
 
-    Vector<IntRect> segmentRects = segmentsRegion.rects();
+    const Vector<IntRect>& segmentRects = segmentsRegion.rects();
     for (unsigned i = 0; i < segmentRects.size(); i++)
         result.append(LineSegment(segmentRects[i].x(), segmentRects[i].maxX() + 1));
@@ -173 +204 @@
     float minY = std::max<float>(intervals.bounds().y(), minIntervalTop);
     float maxY = minY + minIntervalHeight;
-
     if (maxY > intervals.bounds().maxY())
         return false;
 
-    // FIXME: Complete this method, see https://bugs.webkit.org/show_bug.cgi?id=116348.
-    result = minY;
-    return true;
+    return intervals.firstIncludedIntervalY(minY, flooredIntSize(minLogicalIntervalSize), result);
 }
 

trunk/Source/WebCore/rendering/shapes/RasterShape.h

@@ -48 +48 @@
     void getIncludedIntervals(int y1, int y2, SegmentList&) const;
     void getExcludedIntervals(int y1, int y2, SegmentList&) const;
+    bool firstIncludedIntervalY(int minY, const IntSize& minIntervalSize, LayoutUnit&) const;
 
 private: