Diff
Modified: trunk/LayoutTests/ChangeLog (140605 => 140606)
--- trunk/LayoutTests/ChangeLog 2013-01-23 23:08:08 UTC (rev 140605)
+++ trunk/LayoutTests/ChangeLog 2013-01-23 23:11:31 UTC (rev 140606)
@@ -1,3 +1,22 @@
+2013-01-23 Hans Muller <[email protected]>
+
+ [CSS Exclusions] Add support for computing first included interval position for polygons
+ https://bugs.webkit.org/show_bug.cgi?id=103429
+
+ Reviewed by Dirk Schulze.
+
+ All of the existing shape-inside tests exercise the new code. Added new tests which
+ verify that layout works correctly when layout can not begin at the shape's logical top.
+ Test 001 additionally checks all writing-modes, test 002 verifies that the topmost/leftmost
+ rule is followed, and test3 checks a self-intersecting polygon.
+
+ * fast/exclusions/shape-inside/shape-inside-first-fit-001-expected.html: Added.
+ * fast/exclusions/shape-inside/shape-inside-first-fit-001.html: Added.
+ * fast/exclusions/shape-inside/shape-inside-first-fit-002-expected.html: Added.
+ * fast/exclusions/shape-inside/shape-inside-first-fit-002.html: Added.
+ * fast/exclusions/shape-inside/shape-inside-first-fit-003-expected.html: Added.
+ * fast/exclusions/shape-inside/shape-inside-first-fit-003.html: Added.
+
2013-01-23 Dirk Schulze <[email protected]>
Implement Canvas Path object
Added: trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001-expected.html (0 => 140606)
--- trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001-expected.html (rev 0)
+++ trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001-expected.html 2013-01-23 23:11:31 UTC (rev 140606)
@@ -0,0 +1,52 @@
+<!DOCTYPE html>
+<html>
+<head>
+<style>
+ .shape-inside {
+ position: relative;
+ width: 200px;
+ height: 200px;
+ font: 50px/1 Ahem, sans-serif;
+ color: green;
+ }
+
+ .blue {
+ color: blue;
+ }
+
+ .shape-outline {
+ position: absolute;
+ top: 0px;
+ left: 0px;
+ width: 200px;
+ height: 200px;
+ }
+</style>
+</head>
+<body>
+ <p>The solid green and blue rectangles should be contained by the blue triangle outlines.</p>
+ <div class="shape-inside">
+ <svg class="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 200,200 0,200" stroke="blue" fill="none"/>
+ </svg>
+ <br/>X<br/><span class="blue">XX</span><br/>XXX
+ </div>
+ <p>Writing-mode is horizontal-tb</p>
+
+ <div class="shape-inside" style="-webkit-writing-mode: vertical-rl">
+ <svg class="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 200,200 0,200" stroke="blue" fill="none"/>
+ </svg>
+ </br/> X<br/> <span class="blue">XX</span><br/> XXX
+ </div>
+ <p>Writing-mode is vertical-rl.</p>
+
+ <div class="shape-inside" style="-webkit-writing-mode: vertical-lr">
+ <svg class="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 200,200 0,200" stroke="blue" fill="none"/>
+ </svg>
+ XXX<br/> <span class="blue">XX</span><br/> X
+ </div>
+ <p>Writing-mode is vertical-lr.</p>
+</body>
+</html>
Added: trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001.html (0 => 140606)
--- trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001.html (rev 0)
+++ trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-001.html 2013-01-23 23:11:31 UTC (rev 140606)
@@ -0,0 +1,57 @@
+<!DOCTYPE html>
+<html>
+<head>
+<script>
+ if (window.internals)
+ window.internals.settings.setCSSExclusionsEnabled(true);
+</script>
+<style>
+ .shape-inside {
+ position: relative;
+ width: 200px;
+ height: 200px;
+ -webkit-shape-inside: polygon(0px 0px, 200px 200px, 0px 200px);
+ font: 50px/1 Ahem, sans-serif;
+ color: green;
+ }
+
+ .blue {
+ color: blue;
+ }
+
+ .shape-outline {
+ position: absolute;
+ top: 0px;
+ left: 0px;
+ width: 200px;
+ height: 200px;
+ }
+</style>
+</head>
+<body>
+ <p>The solid green and blue rectangles should be contained by the blue triangle outlines.</p>
+ <div class="shape-inside">
+ <svg class="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 200,200 0,200" stroke="blue" fill="none"/>
+ </svg>
+ X <span class="blue">XX</span> XXX
+ </div>
+ <p>Writing-mode is horizontal-tb</p>
+
+ <div class="shape-inside" style="-webkit-writing-mode: vertical-rl">
+ <svg class="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 200,200 0,200" stroke="blue" fill="none"/>
+ </svg>
+ X <span class="blue">XX</span> XXX
+ </div>
+ <p>Writing-mode is vertical-rl.</p>
+
+ <div class="shape-inside" style="-webkit-writing-mode: vertical-lr">
+ <svg class="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 200,200 0,200" stroke="blue" fill="none"/>
+ </svg>
+ XXX <span class="blue">XX</span> X
+ </div>
+ <p>Writing-mode is vertical-lr.</p>
+</body>
+</html>
Added: trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-002-expected.html (0 => 140606)
--- trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-002-expected.html (rev 0)
+++ trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-002-expected.html 2013-01-23 23:11:31 UTC (rev 140606)
@@ -0,0 +1,37 @@
+<!DOCTYPE html>
+<html>
+<head>
+<style>
+ #shape-inside {
+ position: relative;
+ }
+
+ #shape-outline {
+ position: absolute;
+ top: 0px;
+ left: 0px;
+ width: 300px;
+ height: 200px;
+ }
+
+ #shape-contents {
+ position: absolute;
+ top: 0px;
+ left: 0px;
+ font: 50px/1 Ahem, sans-serif;
+ color: green;
+ }
+</style>
+</head>
+<body>
+ <p>The solid green rectangles should be contained by the blue outline.</p>
+ <div id="shape-inside">
+ <pre id="shape-contents">
+X X
+XX XX
+XXXXXX </pre>
+ <svg id="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 150,150 300,0 300,200 0,200" stroke="blue" fill="none"/>
+ </svg>
+</body>
+</html>
Added: trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-002.html (0 => 140606)
--- trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-002.html (rev 0)
+++ trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-002.html 2013-01-23 23:11:31 UTC (rev 140606)
@@ -0,0 +1,36 @@
+<!DOCTYPE html>
+<html>
+<head>
+<script>
+ if (window.internals)
+ window.internals.settings.setCSSExclusionsEnabled(true);
+</script>
+<style>
+ #shape-inside {
+ position: relative;
+ width: 300px;
+ height: 200px;
+ -webkit-shape-inside: polygon(0px 0px, 150px 150px, 300px 0px, 300px 200px, 0px 200px);
+ font: 50px/1 Ahem, sans-serif;
+ color: green;
+ }
+
+ #shape-outline {
+ position: absolute;
+ top: 0px;
+ left: 0px;
+ width: 300px;
+ height: 200px;
+ }
+</style>
+</head>
+<body>
+ <p>The solid green rectangles should be contained by the blue outline.</p>
+ <div id="shape-inside">
+ <svg id="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 150,150 300,0 300,200 0,200" stroke="blue" fill="none"/>
+ </svg>
+ X X XX XX XXXXXX
+ </div>
+</body>
+</html>
Added: trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-003-expected.html (0 => 140606)
--- trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-003-expected.html (rev 0)
+++ trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-003-expected.html 2013-01-23 23:11:31 UTC (rev 140606)
@@ -0,0 +1,37 @@
+<!DOCTYPE html>
+<html>
+<head>
+<style>
+ #shape-inside {
+ position: relative;
+ }
+
+ #shape-outline {
+ position: absolute;
+ top: 0px;
+ left: 0px;
+ width: 400px;
+ height: 200px;
+ }
+
+ #shape-contents {
+ position: absolute;
+ top: 0px;
+ left: 0px;
+ font: 50px/1 Ahem, sans-serif;
+ color: green;
+ }
+</style>
+</head>
+<body>
+ <p>The solid green rectangles should be contained by the blue outline.</p>
+ <div id="shape-inside">
+ <pre id="shape-contents">
+X X
+ XX </pre>
+ <svg id="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 200,200 400,0 400,100 0,100" stroke="blue" fill="none"/>
+ </svg>
+ </div>
+</body>
+</html>
Added: trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-003.html (0 => 140606)
--- trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-003.html (rev 0)
+++ trunk/LayoutTests/fast/exclusions/shape-inside/shape-inside-first-fit-003.html 2013-01-23 23:11:31 UTC (rev 140606)
@@ -0,0 +1,36 @@
+<!DOCTYPE html>
+<html>
+<head>
+<script>
+ if (window.internals)
+ window.internals.settings.setCSSExclusionsEnabled(true);
+</script>
+<style>
+ #shape-inside {
+ position: relative;
+ width: 400px;
+ height: 200px;
+ -webkit-shape-inside: polygon(0px 0px, 200px 200px, 400px 0px, 400px 100px, 0px 100px);
+ font: 50px/1 Ahem, sans-serif;
+ color: green;
+ }
+
+ #shape-outline {
+ position: absolute;
+ top: 0px;
+ left: 0px;
+ width: 400px;
+ height: 200px;
+ }
+</style>
+</head>
+<body>
+ <p>The solid green rectangles should be contained by the blue outline.</p>
+ <div id="shape-inside">
+ <svg id="shape-outline" xmlns="http://www.w3.org/2000/svg">
+ <polygon points="0,0 200,200 400,0 400,100 0,100" stroke="blue" fill="none"/>
+ </svg>
+ X X XX
+ </div>
+</body>
+</html>
Modified: trunk/Source/WebCore/ChangeLog (140605 => 140606)
--- trunk/Source/WebCore/ChangeLog 2013-01-23 23:08:08 UTC (rev 140605)
+++ trunk/Source/WebCore/ChangeLog 2013-01-23 23:11:31 UTC (rev 140606)
@@ -1,3 +1,36 @@
+2013-01-23 Hans Muller <[email protected]>
+
+ [CSS Exclusions] Add support for computing first included interval position for polygons
+ https://bugs.webkit.org/show_bug.cgi?id=103429
+
+ Reviewed by Dirk Schulze.
+
+ Added support for computing the "first fit" location, i.e. the logical shape-inside
+ location where a line's layout begins. The algorithm for doing so is described here:
+ http://hansmuller-webkit.blogspot.com/2012/08/revised-algorithm-for-finding-first.html.
+
+ Tests: fast/exclusions/shape-inside/shape-inside-first-fit-001.html
+ fast/exclusions/shape-inside/shape-inside-first-fit-002.html
+ fast/exclusions/shape-inside/shape-inside-first-fit-003.html
+
+ * platform/graphics/FloatSize.h:
+ (WebCore::operator*): Scale a FloatSize. This simplified the final _expression_ in VertexPair::intersection().
+ * rendering/ExclusionPolygon.cpp:
+ (WebCore::isPointOnLineSegment): Returns true if the specified point is collinear and within the line segement's bounds.
+ (WebCore::leftSide): Return a value > 0 if point is on the left side of the line segment, < 0 if it's on the right, 0 if it's collinear.
+ (WebCore::ExclusionPolygon::contains): Return true if the point is within the polygon or on an edge.
+ (WebCore::VertexPair::overlapsRect): Returns true if the line segment from vertex1 to vertex2 overlaps the specified FloatRect.
+ (WebCore::VertexPair::intersection): Finds the intersection of a pair of line segments defined by VertexPairs.
+ (WebCore::ExclusionPolygon::firstFitRectInPolygon): Returns true if none of the polygon's edges, except the two used
+ to define by the offset edges, overlap the FloatRect.
+ (WebCore::aboveOrToTheLeft): Defines the top/left preference for "first fit" locations.
+ (WebCore::ExclusionPolygon::firstIncludedIntervalLogicalTop): Replaced the stub implementation of this method.
+ * rendering/ExclusionPolygon.h:
+ (ExclusionPolygon): Added declarations noted above.
+ (VertexPair): Abstract class that defines a pair of FloatPoints.
+ (OffsetPolygonEdge): Represents an edge that's horizontally offset from a polygon edge.
+ (WebCore::OffsetPolygonEdge::edgeIndex): The ExclusionPolygon edge index used to define this OffsetEdge.
+
2013-01-23 Dirk Schulze <[email protected]>
Implement Canvas Path object
Modified: trunk/Source/WebCore/platform/graphics/FloatSize.h (140605 => 140606)
--- trunk/Source/WebCore/platform/graphics/FloatSize.h 2013-01-23 23:08:08 UTC (rev 140605)
+++ trunk/Source/WebCore/platform/graphics/FloatSize.h 2013-01-23 23:11:31 UTC (rev 140606)
@@ -175,6 +175,16 @@
return FloatSize(-size.width(), -size.height());
}
+inline FloatSize operator*(const FloatSize& a, const float b)
+{
+ return FloatSize(a.width() * b, a.height() * b);
+}
+
+inline FloatSize operator*(const float a, const FloatSize& b)
+{
+ return FloatSize(a * b.width(), a * b.height());
+}
+
inline bool operator==(const FloatSize& a, const FloatSize& b)
{
return a.width() == b.width() && a.height() == b.height();
Modified: trunk/Source/WebCore/rendering/ExclusionPolygon.cpp (140605 => 140606)
--- trunk/Source/WebCore/rendering/ExclusionPolygon.cpp 2013-01-23 23:08:08 UTC (rev 140605)
+++ trunk/Source/WebCore/rendering/ExclusionPolygon.cpp 2013-01-23 23:11:31 UTC (rev 140606)
@@ -62,6 +62,13 @@
return p0.x() == p1.x() && p0.y() == p1.y();
}
+static inline bool isPointOnLineSegment(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
+{
+ return point.x() >= std::min(vertex1.x(), vertex2.x())
+ && point.x() <= std::max(vertex1.x(), vertex2.x())
+ && areCollinearPoints(vertex1, vertex2, point);
+}
+
static inline unsigned nextVertexIndex(unsigned vertexIndex, unsigned nVertices, bool clockwise)
{
return ((clockwise) ? vertexIndex + 1 : vertexIndex - 1 + nVertices) % nVertices;
@@ -119,7 +126,7 @@
m_edges[edgeIndex].m_vertexIndex1 = vertexIndex1;
m_edges[edgeIndex].m_vertexIndex2 = vertexIndex2;
m_edges[edgeIndex].m_edgeIndex = edgeIndex;
- edgeIndex++;
+ ++edgeIndex;
vertexIndex1 = vertexIndex2;
} while (vertexIndex1);
@@ -138,7 +145,7 @@
if (m_empty)
return;
- for (unsigned i = 0; i < m_edges.size(); i++) {
+ for (unsigned i = 0; i < m_edges.size(); ++i) {
ExclusionPolygonEdge* edge = &m_edges[i];
m_edgeTree.add(EdgeInterval(edge->minY(), edge->maxY(), edge));
}
@@ -226,7 +233,7 @@
Vector<EdgeIntersection> intersections;
EdgeIntersection intersection;
- for (unsigned i = 0; i < overlappingEdges.size(); i++) {
+ for (unsigned i = 0; i < overlappingEdges.size(); ++i) {
ExclusionPolygonEdge* edge = static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
if (computeXIntersection(edge, y, intersection) && intersection.type != VertexYBoth)
intersections.append(intersection);
@@ -250,7 +257,7 @@
index += 2;
} else {
// Replace pairs of intersections whose types are VertexMinY,VertexMaxY or VertexMaxY,VertexMinY with one intersection.
- index++;
+ ++index;
}
continue;
}
@@ -284,7 +291,7 @@
inside = appendIntervalX(thisIntersection.point.x(), inside, result);
}
- index++;
+ ++index;
}
}
@@ -295,7 +302,7 @@
m_edgeTree.allOverlaps(ExclusionPolygon::EdgeInterval(y1, y2, 0), overlappingEdges);
EdgeIntersection intersection;
- for (unsigned i = 0; i < overlappingEdges.size(); i++) {
+ for (unsigned i = 0; i < overlappingEdges.size(); ++i) {
const ExclusionPolygonEdge *edge = static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
float x1;
float x2;
@@ -343,7 +350,7 @@
Vector<ExclusionInterval> excludedIntervals;
mergeExclusionIntervals(mergedIntervals, edgeIntervals, excludedIntervals);
- for (unsigned i = 0; i < excludedIntervals.size(); i++) {
+ for (unsigned i = 0; i < excludedIntervals.size(); ++i) {
ExclusionInterval interval = excludedIntervals[i];
result.append(LineSegment(interval.x1, interval.x2));
}
@@ -370,26 +377,174 @@
Vector<ExclusionInterval> includedIntervals;
subtractExclusionIntervals(commonIntervals, edgeIntervals, includedIntervals);
- for (unsigned i = 0; i < includedIntervals.size(); i++) {
+ for (unsigned i = 0; i < includedIntervals.size(); ++i) {
ExclusionInterval interval = includedIntervals[i];
result.append(LineSegment(interval.x1, interval.x2));
}
}
+static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
+{
+ return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y()));
+}
+
+bool ExclusionPolygon::contains(const FloatPoint& point) const
+{
+ if (!m_boundingBox.contains(point))
+ return false;
+
+ int windingNumber = 0;
+ for (unsigned i = 0; i < numberOfEdges(); ++i) {
+ const FloatPoint& vertex1 = edgeAt(i).vertex1();
+ const FloatPoint& vertex2 = edgeAt(i).vertex2();
+ if (isPointOnLineSegment(vertex1, vertex2, point))
+ return true;
+ if (vertex2.y() < point.y()) {
+ if ((vertex1.y() > point.y()) && (leftSide(vertex1, vertex2, point) > 0))
+ ++windingNumber;
+ } else if (vertex2.y() > point.y()) {
+ if ((vertex1.y() <= point.y()) && (leftSide(vertex1, vertex2, point) < 0))
+ --windingNumber;
+ }
+ }
+
+ return windingNumber;
+}
+
+bool VertexPair::overlapsRect(const FloatRect& rect) const
+{
+ bool boundsOverlap = (minX() < rect.maxX()) && (maxX() > rect.x()) && (minY() < rect.maxY()) && (maxY() > rect.y());
+ if (!boundsOverlap)
+ return false;
+
+ float leftSideValues[4] = {
+ leftSide(vertex1(), vertex2(), rect.minXMinYCorner()),
+ leftSide(vertex1(), vertex2(), rect.maxXMinYCorner()),
+ leftSide(vertex1(), vertex2(), rect.minXMaxYCorner()),
+ leftSide(vertex1(), vertex2(), rect.maxXMaxYCorner())
+ };
+
+ int currentLeftSideSign = 0;
+ for (unsigned i = 0; i < 4; ++i) {
+ if (!leftSideValues[i])
+ continue;
+ int leftSideSign = leftSideValues[i] > 0 ? 1 : -1;
+ if (!currentLeftSideSign)
+ currentLeftSideSign = leftSideSign;
+ else if (currentLeftSideSign != leftSideSign)
+ return true;
+ }
+
+ return false;
+}
+
+bool VertexPair::intersection(const VertexPair& other, FloatPoint& point) const
+{
+ // See: http://paulbourke.net/geometry/pointlineplane/, "Intersection point of two lines in 2 dimensions"
+
+ const FloatSize& thisDelta = vertex2() - vertex1();
+ const FloatSize& otherDelta = other.vertex2() - other.vertex1();
+ float denominator = determinant(thisDelta, otherDelta);
+ if (!denominator)
+ return false;
+
+ // The two line segments: "this" vertex1,vertex2 and "other" vertex1,vertex2, have been defined
+ // in parametric form. Each point on the line segment is: vertex1 + u * (vertex2 - vertex1),
+ // when 0 <= u <= 1. We're computing the values of u for each line at their intersection point.
+
+ const FloatSize& vertex1Delta = vertex1() - other.vertex1();
+ float uThisLine = determinant(otherDelta, vertex1Delta) / denominator;
+ float uOtherLine = determinant(thisDelta, vertex1Delta) / denominator;
+
+ if (uThisLine < 0 || uOtherLine < 0 || uThisLine > 1 || uOtherLine > 1)
+ return false;
+
+ point = vertex1() + uThisLine * thisDelta;
+ return true;
+}
+
+bool ExclusionPolygon::firstFitRectInPolygon(const FloatRect& rect, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex2) const
+{
+ Vector<ExclusionPolygon::EdgeInterval> overlappingEdges;
+ m_edgeTree.allOverlaps(ExclusionPolygon::EdgeInterval(rect.y(), rect.maxY(), 0), overlappingEdges);
+
+ for (unsigned i = 0; i < overlappingEdges.size(); ++i) {
+ const ExclusionPolygonEdge* edge = static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
+ if (edge->edgeIndex() != offsetEdgeIndex1 && edge->edgeIndex() != offsetEdgeIndex2 && edge->overlapsRect(rect))
+ return false;
+ }
+
+ return true;
+}
+
+static inline bool aboveOrToTheLeft(const FloatRect& r1, const FloatRect& r2)
+{
+ if (r1.y() < r2.y())
+ return true;
+ if (r1.y() == r2.y())
+ return r1.x() < r2.x();
+ return false;
+}
+
bool ExclusionPolygon::firstIncludedIntervalLogicalTop(float minLogicalIntervalTop, const FloatSize& minLogicalIntervalSize, float& result) const
{
- // FIXME: This is just a temporary stub, https://bugs.webkit.org/show_bug.cgi?id=103429
-
if (minLogicalIntervalSize.width() > m_boundingBox.width())
return false;
float minY = std::max(m_boundingBox.y(), minLogicalIntervalTop);
float maxY = minY + minLogicalIntervalSize.height();
- if (minY < m_boundingBox.y() || maxY > m_boundingBox.maxY())
+
+ if (maxY > m_boundingBox.maxY())
return false;
- result = minLogicalIntervalTop;
- return true;
+ float dx = minLogicalIntervalSize.width() / 2;
+ float dy = minLogicalIntervalSize.height() / 2;
+ Vector<OffsetPolygonEdge> offsetEdges;
+
+ for (unsigned i = 0; i < numberOfEdges(); ++i) {
+ const ExclusionPolygonEdge& edge = edgeAt(i);
+ const FloatPoint& vertex1 = edge.vertex1();
+ const FloatPoint& vertex2 = edge.vertex2();
+ Vector<OffsetPolygonEdge> offsetEdgePair;
+
+ if (vertex2.y() > vertex1.y() ? vertex2.x() >= vertex1.x() : vertex1.x() >= vertex2.x()) {
+ offsetEdgePair.append(OffsetPolygonEdge(edge, FloatSize(dx, -dy)));
+ offsetEdgePair.append(OffsetPolygonEdge(edge, FloatSize(-dx, dy)));
+ } else {
+ offsetEdgePair.append(OffsetPolygonEdge(edge, FloatSize(dx, dy)));
+ offsetEdgePair.append(OffsetPolygonEdge(edge, FloatSize(-dx, -dy)));
+ }
+
+ for (unsigned j = 0; j < offsetEdgePair.size(); ++j)
+ if (offsetEdgePair[j].maxY() >= minY)
+ offsetEdges.append(offsetEdgePair[j]);
+ }
+
+ offsetEdges.append(OffsetPolygonEdge(*this, minLogicalIntervalTop, FloatSize(0, dy)));
+
+ FloatPoint offsetEdgesIntersection;
+ FloatRect firstFitRect;
+ bool firstFitFound = false;
+
+ for (unsigned i = 0; i < offsetEdges.size() - 1; ++i) {
+ for (unsigned j = i + 1; j < offsetEdges.size(); ++j) {
+ if (offsetEdges[i].intersection(offsetEdges[j], offsetEdgesIntersection)) {
+ FloatPoint potentialFirstFitLocation(offsetEdgesIntersection.x() - dx, offsetEdgesIntersection.y() - dy);
+ FloatRect potentialFirstFitRect(potentialFirstFitLocation, minLogicalIntervalSize);
+ if ((potentialFirstFitLocation.y() >= minLogicalIntervalTop)
+ && (!firstFitFound || aboveOrToTheLeft(potentialFirstFitRect, firstFitRect))
+ && contains(offsetEdgesIntersection)
+ && firstFitRectInPolygon(potentialFirstFitRect, offsetEdges[i].edgeIndex(), offsetEdges[j].edgeIndex())) {
+ firstFitFound = true;
+ firstFitRect = potentialFirstFitRect;
+ }
+ }
+ }
+ }
+
+ if (firstFitFound)
+ result = firstFitRect.y();
+ return firstFitFound;
}
} // namespace WebCore
Modified: trunk/Source/WebCore/rendering/ExclusionPolygon.h (140605 => 140606)
--- trunk/Source/WebCore/rendering/ExclusionPolygon.h 2013-01-23 23:08:08 UTC (rev 140605)
+++ trunk/Source/WebCore/rendering/ExclusionPolygon.h 2013-01-23 23:11:31 UTC (rev 140606)
@@ -62,6 +62,8 @@
const ExclusionPolygonEdge& edgeAt(unsigned index) const { return m_edges[index]; }
unsigned numberOfEdges() const { return m_edges.size(); }
+ bool contains(const FloatPoint&) const;
+
virtual FloatRect shapeLogicalBoundingBox() const OVERRIDE { return m_boundingBox; }
virtual bool isEmpty() const OVERRIDE { return m_empty; }
virtual void getExcludedIntervals(float logicalTop, float logicalHeight, SegmentList&) const OVERRIDE;
@@ -72,6 +74,7 @@
void computeXIntersections(float y, bool isMinY, Vector<ExclusionInterval>&) const;
void computeEdgeIntersections(float minY, float maxY, Vector<ExclusionInterval>&) const;
unsigned findNextEdgeVertexIndex(unsigned vertexIndex1, bool clockwise) const;
+ bool firstFitRectInPolygon(const FloatRect&, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex) const;
typedef PODInterval<float, ExclusionPolygonEdge*> EdgeInterval;
typedef PODIntervalTree<float, ExclusionPolygonEdge*> EdgeIntervalTree;
@@ -95,6 +98,9 @@
float minY() const { return std::min(vertex1().y(), vertex2().y()); }
float maxX() const { return std::max(vertex1().x(), vertex2().x()); }
float maxY() const { return std::max(vertex1().y(), vertex2().y()); }
+
+ bool overlapsRect(const FloatRect&) const;
+ bool intersection(const VertexPair&, FloatPoint&) const;
};
// EdgeIntervalTree nodes store minY, maxY, and a ("UserData") pointer to an ExclusionPolygonEdge. Edge vertex
@@ -150,6 +156,32 @@
};
#endif
+class OffsetPolygonEdge : public VertexPair {
+public:
+ OffsetPolygonEdge(const ExclusionPolygonEdge& edge, const FloatSize& offset)
+ : m_vertex1(edge.vertex1() + offset)
+ , m_vertex2(edge.vertex2() + offset)
+ , m_edgeIndex(edge.edgeIndex())
+ {
+ }
+
+ OffsetPolygonEdge(const ExclusionPolygon& polygon, float minLogicalIntervalTop, const FloatSize& offset)
+ : m_vertex1(FloatPoint(polygon.shapeLogicalBoundingBox().x(), minLogicalIntervalTop) + offset)
+ , m_vertex2(FloatPoint(polygon.shapeLogicalBoundingBox().maxX(), minLogicalIntervalTop) + offset)
+ , m_edgeIndex(polygon.numberOfEdges())
+ {
+ }
+
+ virtual const FloatPoint& vertex1() const OVERRIDE { return m_vertex1; }
+ virtual const FloatPoint& vertex2() const OVERRIDE { return m_vertex2; }
+ unsigned edgeIndex() const { return m_edgeIndex; }
+
+private:
+ FloatPoint m_vertex1;
+ FloatPoint m_vertex2;
+ unsigned m_edgeIndex;
+};
+
} // namespace WebCore
#endif // ExclusionPolygon_h
