[CSS Shapes] Improve the performance of image valued shapes with large shape-margins
https://bugs.webkit.org/show_bug.cgi?id=122613
Reviewed by Andreas Kling.
The cost of computing the shape-margin boundary of an image-valued shape-outside
is now proportional to (2 * shape-margin + image.height) rather than
(2 * shape-margin * image.height). The performance improvement comes from skipping
sequences of rounded-rectangle intervals that will not contribute to the final
result. Each non-empty row in the original image contributes one rounded-rectangle
whose corner radius is shape-margin, height is 2 * shape-margin, and width is
2 * shape-margin plus the width of the limits of the intervals on the row.
Renamed private method RasterShape::getIntervals() to intervalsAt() to be a little
more consistent with WebKit naming conventions.
There are no new tests since is just an internal refactoring.
* rendering/shapes/RasterShape.cpp:
(WebCore::MarginIntervalGenerator::set): Changed the x1,x2 parameters to an IntShapeInterval.
(WebCore::RasterShapeIntervals::contains): Refactor for the getIntervals() => intervalsAt() rename.
(WebCore::RasterShapeIntervals::getIntervalX1Values): Ditto.
(WebCore::RasterShapeIntervals::getIncludedIntervals): Ditto.
(WebCore::RasterShapeIntervals::getExcludedIntervals): Ditto.
(WebCore::RasterShapeIntervals::computeShapeMarginIntervals): Performance tuning.
* rendering/shapes/RasterShape.h:
(WebCore::RasterShapeIntervals::intervalsAt): Renamed getIntervals().
(WebCore::RasterShapeIntervals::limitIntervalAt): Return the min/max limits of the intervals at Y.
* rendering/shapes/ShapeInterval.h:
(WebCore::ShapeInterval::isEmpty): Added.
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@157574 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
index a85bada..47ca430 100644
--- a/Source/WebCore/ChangeLog
+++ b/Source/WebCore/ChangeLog
@@ -1,3 +1,36 @@
+2013-10-17 Hans Muller <hmuller@adobe.com>
+
+ [CSS Shapes] Improve the performance of image valued shapes with large shape-margins
+ https://bugs.webkit.org/show_bug.cgi?id=122613
+
+ Reviewed by Andreas Kling.
+
+ The cost of computing the shape-margin boundary of an image-valued shape-outside
+ is now proportional to (2 * shape-margin + image.height) rather than
+ (2 * shape-margin * image.height). The performance improvement comes from skipping
+ sequences of rounded-rectangle intervals that will not contribute to the final
+ result. Each non-empty row in the original image contributes one rounded-rectangle
+ whose corner radius is shape-margin, height is 2 * shape-margin, and width is
+ 2 * shape-margin plus the width of the limits of the intervals on the row.
+
+ Renamed private method RasterShape::getIntervals() to intervalsAt() to be a little
+ more consistent with WebKit naming conventions.
+
+ There are no new tests since is just an internal refactoring.
+
+ * rendering/shapes/RasterShape.cpp:
+ (WebCore::MarginIntervalGenerator::set): Changed the x1,x2 parameters to an IntShapeInterval.
+ (WebCore::RasterShapeIntervals::contains): Refactor for the getIntervals() => intervalsAt() rename.
+ (WebCore::RasterShapeIntervals::getIntervalX1Values): Ditto.
+ (WebCore::RasterShapeIntervals::getIncludedIntervals): Ditto.
+ (WebCore::RasterShapeIntervals::getExcludedIntervals): Ditto.
+ (WebCore::RasterShapeIntervals::computeShapeMarginIntervals): Performance tuning.
+ * rendering/shapes/RasterShape.h:
+ (WebCore::RasterShapeIntervals::intervalsAt): Renamed getIntervals().
+ (WebCore::RasterShapeIntervals::limitIntervalAt): Return the min/max limits of the intervals at Y.
+ * rendering/shapes/ShapeInterval.h:
+ (WebCore::ShapeInterval::isEmpty): Added.
+
2013-10-15 Philippe Normand <pnormand@igalia.com>
[GTK] Add URLMediaStream in the build
diff --git a/Source/WebCore/rendering/shapes/RasterShape.cpp b/Source/WebCore/rendering/shapes/RasterShape.cpp
index dbeda00..3aa065d 100644
--- a/Source/WebCore/rendering/shapes/RasterShape.cpp
+++ b/Source/WebCore/rendering/shapes/RasterShape.cpp
@@ -37,7 +37,7 @@
class MarginIntervalGenerator {
public:
MarginIntervalGenerator(unsigned radius);
- void set(int y, int x1, int x2);
+ void set(int y, const IntShapeInterval&);
IntShapeInterval intervalAt(int y) const;
private:
@@ -58,12 +58,12 @@
m_xIntercepts[y] = sqrt(static_cast<double>(radiusSquared - y * y));
}
-void MarginIntervalGenerator::set(int y, int x1, int x2)
+void MarginIntervalGenerator::set(int y, const IntShapeInterval& interval)
{
- ASSERT(y >= 0 && x1 >= 0 && x2 > x1);
+ ASSERT(y >= 0 && interval.x1() >= 0);
m_y = y;
- m_x1 = x1;
- m_x2 = x2;
+ m_x1 = interval.x1();
+ m_x2 = interval.x2();
}
IntShapeInterval MarginIntervalGenerator::intervalAt(int y) const
@@ -114,7 +114,7 @@
const IntShapeInterval& rectInterval = IntShapeInterval(rect.x(), rect.maxX());
for (int y = rect.y(); y < rect.maxY(); y++) {
- if (!shapeIntervalsContain(getIntervals(y), rectInterval))
+ if (!shapeIntervalsContain(intervalsAt(y), rectInterval))
return false;
}
@@ -133,14 +133,14 @@
ASSERT(y1 >= 0 && y2 > y1);
for (int y = y1; y < y2; y++) {
- if (getIntervals(y).isEmpty())
+ if (intervalsAt(y).isEmpty())
return false;
}
- appendX1Values(getIntervals(y1), minIntervalWidth, result);
+ appendX1Values(intervalsAt(y1), minIntervalWidth, result);
for (int y = y1 + 1; y < y2; y++) {
- if (getIntervals(y) != getIntervals(y - 1))
- appendX1Values(getIntervals(y), minIntervalWidth, result);
+ if (intervalsAt(y) != intervalsAt(y - 1))
+ appendX1Values(intervalsAt(y), minIntervalWidth, result);
}
return true;
@@ -186,14 +186,14 @@
return;
for (int y = y1; y < y2; y++) {
- if (getIntervals(y).isEmpty())
+ if (intervalsAt(y).isEmpty())
return;
}
- result = getIntervals(y1);
+ result = intervalsAt(y1);
for (int y = y1 + 1; y < y2 && !result.isEmpty(); y++) {
IntShapeIntervals intervals;
- IntShapeInterval::intersectShapeIntervals(result, getIntervals(y), intervals);
+ IntShapeInterval::intersectShapeIntervals(result, intervalsAt(y), intervals);
result.swap(intervals);
}
}
@@ -206,33 +206,47 @@
return;
for (int y = y1; y < y2; y++) {
- if (getIntervals(y).isEmpty())
+ if (intervalsAt(y).isEmpty())
return;
}
- result = getIntervals(y1);
+ result = intervalsAt(y1);
for (int y = y1 + 1; y < y2; y++) {
IntShapeIntervals intervals;
- IntShapeInterval::uniteShapeIntervals(result, getIntervals(y), intervals);
+ IntShapeInterval::uniteShapeIntervals(result, intervalsAt(y), intervals);
result.swap(intervals);
}
}
// Currently limited to computing the margin boundary for shape-outside for floats, see https://bugs.webkit.org/show_bug.cgi?id=116348.
+
PassOwnPtr<RasterShapeIntervals> RasterShapeIntervals::computeShapeMarginIntervals(unsigned margin) const
{
OwnPtr<RasterShapeIntervals> result = adoptPtr(new RasterShapeIntervals(size() + margin));
- MarginIntervalGenerator intervalGenerator(margin);
+ MarginIntervalGenerator marginIntervalGenerator(margin);
for (int y = bounds().y(); y < bounds().maxY(); ++y) {
- const IntShapeIntervals& intervalsAtY = getIntervals(y);
- if (intervalsAtY.isEmpty())
+ const IntShapeInterval& intervalAtY = limitIntervalAt(y);
+ if (intervalAtY.isEmpty())
continue;
+
+ marginIntervalGenerator.set(y, intervalAtY);
int marginY0 = std::max(0, clampToPositiveInteger(y - margin));
int marginY1 = std::min(result->size() - 1, clampToPositiveInteger(y + margin));
- intervalGenerator.set(y, intervalsAtY[0].x1(), intervalsAtY.last().x2());
- for (int marginY = marginY0; marginY <= marginY1; ++marginY)
- result->uniteMarginInterval(marginY, intervalGenerator.intervalAt(marginY));
+
+ for (int marginY = y - 1; marginY >= marginY0; --marginY) {
+ if (limitIntervalAt(marginY).contains(intervalAtY))
+ break;
+ result->uniteMarginInterval(marginY, marginIntervalGenerator.intervalAt(marginY));
+ }
+
+ result->uniteMarginInterval(y, marginIntervalGenerator.intervalAt(y));
+
+ for (int marginY = y + 1; marginY <= marginY1; ++marginY) {
+ if (marginY < size() && limitIntervalAt(marginY).contains(intervalAtY))
+ break;
+ result->uniteMarginInterval(marginY, marginIntervalGenerator.intervalAt(marginY));
+ }
}
return result.release();
diff --git a/Source/WebCore/rendering/shapes/RasterShape.h b/Source/WebCore/rendering/shapes/RasterShape.h
index aa5b8ab..e448949 100644
--- a/Source/WebCore/rendering/shapes/RasterShape.h
+++ b/Source/WebCore/rendering/shapes/RasterShape.h
@@ -57,12 +57,18 @@
private:
int size() const { return m_intervalLists.size(); }
- const IntShapeIntervals& getIntervals(int y) const
+ const IntShapeIntervals& intervalsAt(int y) const
{
ASSERT(y >= 0 && y < size());
return m_intervalLists[y];
}
+ IntShapeInterval limitIntervalAt(int y) const
+ {
+ const IntShapeIntervals& intervals = intervalsAt(y);
+ return intervals.size() ? IntShapeInterval(intervals[0].x1(), intervals.last().x2()) : IntShapeInterval();
+ }
+
bool contains(const IntRect&) const;
bool getIntervalX1Values(int minY, int maxY, int minIntervalWidth, Vector<int>& result) const;
void uniteMarginInterval(int y, const IntShapeInterval&);
diff --git a/Source/WebCore/rendering/shapes/ShapeInterval.h b/Source/WebCore/rendering/shapes/ShapeInterval.h
index 84a5a9a..9efa0fe 100644
--- a/Source/WebCore/rendering/shapes/ShapeInterval.h
+++ b/Source/WebCore/rendering/shapes/ShapeInterval.h
@@ -48,6 +48,7 @@
T x1() const { return m_x1; }
T x2() const { return m_x2; }
T width() const { return m_x2 - m_x1; }
+ bool isEmpty() const { return m_x1 == m_x2; }
void setX1(T x1)
{
