[CSS Shapes][CSS Exclusions] Split CSS Exclusions and CSS Shapes code
[WebKit-https.git] / Source / WebCore / rendering / shapes / PolygonShape.cpp
1 /*
2  * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1. Redistributions of source code must retain the above
9  *    copyright notice, this list of conditions and the following
10  *    disclaimer.
11  * 2. Redistributions in binary form must reproduce the above
12  *    copyright notice, this list of conditions and the following
13  *    disclaimer in the documentation and/or other materials
14  *    provided with the distribution.
15  * 
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
21  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
25  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
27  * OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 #include "config.h"
31 #include "PolygonShape.h"
32
33 #include <wtf/MathExtras.h>
34
35 namespace WebCore {
36
37 enum EdgeIntersectionType {
38     Normal,
39     VertexMinY,
40     VertexMaxY,
41     VertexYBoth
42 };
43
44 struct EdgeIntersection {
45     const FloatPolygonEdge* edge;
46     FloatPoint point;
47     EdgeIntersectionType type;
48 };
49
50 static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
51 {
52     return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y()));
53 }
54
55 static inline bool isReflexVertex(const FloatPoint& prevVertex, const FloatPoint& vertex, const FloatPoint& nextVertex)
56 {
57     return leftSide(prevVertex, nextVertex, vertex) < 0;
58 }
59
60 static bool computeXIntersection(const FloatPolygonEdge* edgePointer, float y, EdgeIntersection& result)
61 {
62     const FloatPolygonEdge& edge = *edgePointer;
63
64     if (edge.minY() > y || edge.maxY() < y)
65         return false;
66
67     const FloatPoint& vertex1 = edge.vertex1();
68     const FloatPoint& vertex2 = edge.vertex2();
69     float dy = vertex2.y() - vertex1.y();
70
71     float intersectionX;
72     EdgeIntersectionType intersectionType;
73
74     if (!dy) {
75         intersectionType = VertexYBoth;
76         intersectionX = edge.minX();
77     } else if (y == edge.minY()) {
78         intersectionType = VertexMinY;
79         intersectionX = (vertex1.y() < vertex2.y()) ? vertex1.x() : vertex2.x();
80     } else if (y == edge.maxY()) {
81         intersectionType = VertexMaxY;
82         intersectionX = (vertex1.y() > vertex2.y()) ? vertex1.x() : vertex2.x();
83     } else {
84         intersectionType = Normal;
85         intersectionX = ((y - vertex1.y()) * (vertex2.x() - vertex1.x()) / dy) + vertex1.x();
86     }
87
88     result.edge = edgePointer;
89     result.type = intersectionType;
90     result.point.set(intersectionX, y);
91
92     return true;
93 }
94
95 static inline FloatSize inwardEdgeNormal(const FloatPolygonEdge& edge)
96 {
97     FloatSize edgeDelta = edge.vertex2() - edge.vertex1();
98     if (!edgeDelta.width())
99         return FloatSize((edgeDelta.height() > 0 ? -1 : 1), 0);
100     if (!edgeDelta.height())
101         return FloatSize(0, (edgeDelta.width() > 0 ? 1 : -1));
102     float edgeLength = edgeDelta.diagonalLength();
103     return FloatSize(-edgeDelta.height() / edgeLength, edgeDelta.width() / edgeLength);
104 }
105
106 static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge)
107 {
108     return -inwardEdgeNormal(edge);
109 }
110
111 static inline void appendArc(Vector<FloatPoint>& vertices, const FloatPoint& arcCenter, float arcRadius, const FloatPoint& startArcVertex, const FloatPoint& endArcVertex, bool padding)
112 {
113     float startAngle = atan2(startArcVertex.y() - arcCenter.y(), startArcVertex.x() - arcCenter.x());
114     float endAngle = atan2(endArcVertex.y() - arcCenter.y(), endArcVertex.x() - arcCenter.x());
115     const float twoPI = piFloat * 2;
116     if (startAngle < 0)
117         startAngle += twoPI;
118     if (endAngle < 0)
119         endAngle += twoPI;
120     float angle = (startAngle > endAngle) ? (startAngle - endAngle) : (startAngle + twoPI - endAngle);
121     const float arcSegmentCount = 6; // An even number so that one arc vertex will be eactly arcRadius from arcCenter.
122     float arcSegmentAngle =  ((padding) ? -angle : twoPI - angle) / arcSegmentCount;
123
124     vertices.append(startArcVertex);
125     for (unsigned i = 1; i < arcSegmentCount; ++i) {
126         float angle = startAngle + arcSegmentAngle * i;
127         vertices.append(arcCenter + FloatPoint(cos(angle) * arcRadius, sin(angle) * arcRadius));
128     }
129     vertices.append(endArcVertex);
130 }
131
132 static inline void snapVerticesToLayoutUnitGrid(Vector<FloatPoint>& vertices)
133 {
134     for (unsigned i = 0; i < vertices.size(); ++i)
135         vertices[i].set(LayoutUnit(vertices[i].x()).toFloat(), LayoutUnit(vertices[i].y()).toFloat());
136 }
137
138 static inline PassOwnPtr<FloatPolygon> computeShapePaddingBounds(const FloatPolygon& polygon, float padding, WindRule fillRule)
139 {
140     OwnPtr<Vector<FloatPoint> > paddedVertices = adoptPtr(new Vector<FloatPoint>());
141     FloatPoint intersection;
142
143     for (unsigned i = 0; i < polygon.numberOfEdges(); ++i) {
144         const FloatPolygonEdge& thisEdge = polygon.edgeAt(i);
145         const FloatPolygonEdge& prevEdge = thisEdge.previousEdge();
146         OffsetPolygonEdge thisOffsetEdge(thisEdge, inwardEdgeNormal(thisEdge) * padding);
147         OffsetPolygonEdge prevOffsetEdge(prevEdge, inwardEdgeNormal(prevEdge) * padding);
148
149         if (prevOffsetEdge.intersection(thisOffsetEdge, intersection))
150             paddedVertices->append(intersection);
151         else if (isReflexVertex(prevEdge.vertex1(), thisEdge.vertex1(), thisEdge.vertex2()))
152             appendArc(*paddedVertices, thisEdge.vertex1(), padding, prevOffsetEdge.vertex2(), thisOffsetEdge.vertex1(), true);
153     }
154
155     snapVerticesToLayoutUnitGrid(*paddedVertices);
156     return adoptPtr(new FloatPolygon(paddedVertices.release(), fillRule));
157 }
158
159 static inline PassOwnPtr<FloatPolygon> computeShapeMarginBounds(const FloatPolygon& polygon, float margin, WindRule fillRule)
160 {
161     OwnPtr<Vector<FloatPoint> > marginVertices = adoptPtr(new Vector<FloatPoint>());
162     FloatPoint intersection;
163
164     for (unsigned i = 0; i < polygon.numberOfEdges(); ++i) {
165         const FloatPolygonEdge& thisEdge = polygon.edgeAt(i);
166         const FloatPolygonEdge& prevEdge = thisEdge.previousEdge();
167         OffsetPolygonEdge thisOffsetEdge(thisEdge, outwardEdgeNormal(thisEdge) * margin);
168         OffsetPolygonEdge prevOffsetEdge(prevEdge, outwardEdgeNormal(prevEdge) * margin);
169
170         if (prevOffsetEdge.intersection(thisOffsetEdge, intersection))
171             marginVertices->append(intersection);
172         else
173             appendArc(*marginVertices, thisEdge.vertex1(), margin, prevOffsetEdge.vertex2(), thisOffsetEdge.vertex1(), false);
174     }
175
176     snapVerticesToLayoutUnitGrid(*marginVertices);
177     return adoptPtr(new FloatPolygon(marginVertices.release(), fillRule));
178 }
179
180 const FloatPolygon& PolygonShape::shapePaddingBounds() const
181 {
182     ASSERT(shapePadding() >= 0);
183     if (!shapePadding())
184         return m_polygon;
185
186     if (!m_paddingBounds)
187         m_paddingBounds = computeShapePaddingBounds(m_polygon, shapePadding(), m_polygon.fillRule());
188
189     return *m_paddingBounds;
190 }
191
192 const FloatPolygon& PolygonShape::shapeMarginBounds() const
193 {
194     ASSERT(shapeMargin() >= 0);
195     if (!shapeMargin())
196         return m_polygon;
197
198     if (!m_marginBounds)
199         m_marginBounds = computeShapeMarginBounds(m_polygon, shapeMargin(), m_polygon.fillRule());
200
201     return *m_marginBounds;
202 }
203
204 static inline bool getVertexIntersectionVertices(const EdgeIntersection& intersection, FloatPoint& prevVertex, FloatPoint& thisVertex, FloatPoint& nextVertex)
205 {
206     if (intersection.type != VertexMinY && intersection.type != VertexMaxY)
207         return false;
208
209     ASSERT(intersection.edge && intersection.edge->polygon());
210     const FloatPolygon& polygon = *(intersection.edge->polygon());
211     const FloatPolygonEdge& thisEdge = *(intersection.edge);
212
213     if ((intersection.type == VertexMinY && (thisEdge.vertex1().y() < thisEdge.vertex2().y()))
214         || (intersection.type == VertexMaxY && (thisEdge.vertex1().y() > thisEdge.vertex2().y()))) {
215         prevVertex = polygon.vertexAt(thisEdge.previousEdge().vertexIndex1());
216         thisVertex = polygon.vertexAt(thisEdge.vertexIndex1());
217         nextVertex = polygon.vertexAt(thisEdge.vertexIndex2());
218     } else {
219         prevVertex = polygon.vertexAt(thisEdge.vertexIndex1());
220         thisVertex = polygon.vertexAt(thisEdge.vertexIndex2());
221         nextVertex = polygon.vertexAt(thisEdge.nextEdge().vertexIndex2());
222     }
223
224     return true;
225 }
226
227 static inline bool appendIntervalX(float x, bool inside, Vector<ShapeInterval>& result)
228 {
229     if (!inside)
230         result.append(ShapeInterval(x));
231     else
232         result[result.size() - 1].x2 = x;
233
234     return !inside;
235 }
236
237 static bool compareEdgeIntersectionX(const EdgeIntersection& intersection1, const EdgeIntersection& intersection2)
238 {
239     float x1 = intersection1.point.x();
240     float x2 = intersection2.point.x();
241     return (x1 == x2) ? intersection1.type < intersection2.type : x1 < x2;
242 }
243
244 static void computeXIntersections(const FloatPolygon& polygon, float y, bool isMinY, Vector<ShapeInterval>& result)
245 {
246     Vector<const FloatPolygonEdge*> edges;
247     if (!polygon.overlappingEdges(y, y, edges))
248         return;
249
250     Vector<EdgeIntersection> intersections;
251     EdgeIntersection intersection;
252     for (unsigned i = 0; i < edges.size(); ++i) {
253         if (computeXIntersection(edges[i], y, intersection) && intersection.type != VertexYBoth)
254             intersections.append(intersection);
255     }
256
257     if (intersections.size() < 2)
258         return;
259
260     std::sort(intersections.begin(), intersections.end(), WebCore::compareEdgeIntersectionX);
261
262     unsigned index = 0;
263     int windCount = 0;
264     bool inside = false;
265
266     while (index < intersections.size()) {
267         const EdgeIntersection& thisIntersection = intersections[index];
268         if (index + 1 < intersections.size()) {
269             const EdgeIntersection& nextIntersection = intersections[index + 1];
270             if ((thisIntersection.point.x() == nextIntersection.point.x()) && (thisIntersection.type == VertexMinY || thisIntersection.type == VertexMaxY)) {
271                 if (thisIntersection.type == nextIntersection.type) {
272                     // Skip pairs of intersections whose types are VertexMaxY,VertexMaxY and VertexMinY,VertexMinY.
273                     index += 2;
274                 } else {
275                     // Replace pairs of intersections whose types are VertexMinY,VertexMaxY or VertexMaxY,VertexMinY with one intersection.
276                     ++index;
277                 }
278                 continue;
279             }
280         }
281
282         const FloatPolygonEdge& thisEdge = *thisIntersection.edge;
283         bool evenOddCrossing = !windCount;
284
285         if (polygon.fillRule() == RULE_EVENODD) {
286             windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? 1 : -1;
287             evenOddCrossing = evenOddCrossing || !windCount;
288         }
289
290         if (evenOddCrossing) {
291             bool edgeCrossing = thisIntersection.type == Normal;
292             if (!edgeCrossing) {
293                 FloatPoint prevVertex;
294                 FloatPoint thisVertex;
295                 FloatPoint nextVertex;
296
297                 if (getVertexIntersectionVertices(thisIntersection, prevVertex, thisVertex, nextVertex)) {
298                     if (nextVertex.y() == y)
299                         edgeCrossing = (isMinY) ? prevVertex.y() > y : prevVertex.y() < y;
300                     else if (prevVertex.y() == y)
301                         edgeCrossing = (isMinY) ? nextVertex.y() > y : nextVertex.y() < y;
302                     else
303                         edgeCrossing = true;
304                 }
305             }
306             if (edgeCrossing)
307                 inside = appendIntervalX(thisIntersection.point.x(), inside, result);
308         }
309
310         ++index;
311     }
312 }
313
314 static void computeOverlappingEdgeXProjections(const FloatPolygon& polygon, float y1, float y2, Vector<ShapeInterval>& result)
315 {
316     Vector<const FloatPolygonEdge*> edges;
317     if (!polygon.overlappingEdges(y1, y2, edges))
318         return;
319
320     EdgeIntersection intersection;
321     for (unsigned i = 0; i < edges.size(); ++i) {
322         const FloatPolygonEdge *edge = edges[i];
323         float x1;
324         float x2;
325
326         if (edge->minY() < y1) {
327             computeXIntersection(edge, y1, intersection);
328             x1 = intersection.point.x();
329         } else
330             x1 = (edge->vertex1().y() < edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
331
332         if (edge->maxY() > y2) {
333             computeXIntersection(edge, y2, intersection);
334             x2 = intersection.point.x();
335         } else
336             x2 = (edge->vertex1().y() > edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
337
338         if (x1 > x2)
339             std::swap(x1, x2);
340
341         if (x2 > x1)
342             result.append(ShapeInterval(x1, x2));
343     }
344
345     sortShapeIntervals(result);
346 }
347
348 void PolygonShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
349 {
350     const FloatPolygon& polygon = shapeMarginBounds();
351     if (polygon.isEmpty())
352         return;
353
354     float y1 = logicalTop;
355     float y2 = logicalTop + logicalHeight;
356
357     Vector<ShapeInterval> y1XIntervals, y2XIntervals;
358     computeXIntersections(polygon, y1, true, y1XIntervals);
359     computeXIntersections(polygon, y2, false, y2XIntervals);
360
361     Vector<ShapeInterval> mergedIntervals;
362     mergeShapeIntervals(y1XIntervals, y2XIntervals, mergedIntervals);
363
364     Vector<ShapeInterval> edgeIntervals;
365     computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals);
366
367     Vector<ShapeInterval> excludedIntervals;
368     mergeShapeIntervals(mergedIntervals, edgeIntervals, excludedIntervals);
369
370     for (unsigned i = 0; i < excludedIntervals.size(); ++i) {
371         ShapeInterval interval = excludedIntervals[i];
372         result.append(LineSegment(interval.x1, interval.x2));
373     }
374 }
375
376 void PolygonShape::getIncludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
377 {
378     const FloatPolygon& polygon = shapePaddingBounds();
379     if (polygon.isEmpty())
380         return;
381
382     float y1 = logicalTop;
383     float y2 = logicalTop + logicalHeight;
384
385     Vector<ShapeInterval> y1XIntervals, y2XIntervals;
386     computeXIntersections(polygon, y1, true, y1XIntervals);
387     computeXIntersections(polygon, y2, false, y2XIntervals);
388
389     Vector<ShapeInterval> commonIntervals;
390     intersectShapeIntervals(y1XIntervals, y2XIntervals, commonIntervals);
391
392     Vector<ShapeInterval> edgeIntervals;
393     computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals);
394
395     Vector<ShapeInterval> includedIntervals;
396     subtractShapeIntervals(commonIntervals, edgeIntervals, includedIntervals);
397
398     for (unsigned i = 0; i < includedIntervals.size(); ++i) {
399         ShapeInterval interval = includedIntervals[i];
400         result.append(LineSegment(interval.x1, interval.x2));
401     }
402 }
403
404 static inline bool firstFitRectInPolygon(const FloatPolygon& polygon, const FloatRect& rect, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex2)
405 {
406     Vector<const FloatPolygonEdge*> edges;
407     if (!polygon.overlappingEdges(rect.y(), rect.maxY(), edges))
408         return true;
409
410     for (unsigned i = 0; i < edges.size(); ++i) {
411         const FloatPolygonEdge* edge = edges[i];
412         if (edge->edgeIndex() != offsetEdgeIndex1 && edge->edgeIndex() != offsetEdgeIndex2 && edge->overlapsRect(rect))
413             return false;
414     }
415
416     return true;
417 }
418
419 static inline bool aboveOrToTheLeft(const FloatRect& r1, const FloatRect& r2)
420 {
421     if (r1.y() < r2.y())
422         return true;
423     if (r1.y() == r2.y())
424         return r1.x() < r2.x();
425     return false;
426 }
427
428 bool PolygonShape::firstIncludedIntervalLogicalTop(LayoutUnit minLogicalIntervalTop, const LayoutSize& minLogicalIntervalSize, LayoutUnit& result) const
429 {
430     float minIntervalTop = minLogicalIntervalTop;
431     float minIntervalHeight = minLogicalIntervalSize.height();
432     float minIntervalWidth = minLogicalIntervalSize.width();
433
434     const FloatPolygon& polygon = shapePaddingBounds();
435     const FloatRect boundingBox = polygon.boundingBox();
436     if (minIntervalWidth > boundingBox.width())
437         return false;
438
439     float minY = std::max(boundingBox.y(), minIntervalTop);
440     float maxY = minY + minIntervalHeight;
441
442     if (maxY > boundingBox.maxY())
443         return false;
444
445     Vector<const FloatPolygonEdge*> edges;
446     polygon.overlappingEdges(minIntervalTop, boundingBox.maxY(), edges);
447
448     float dx = minIntervalWidth / 2;
449     float dy = minIntervalHeight / 2;
450     Vector<OffsetPolygonEdge> offsetEdges;
451
452     for (unsigned i = 0; i < edges.size(); ++i) {
453         const FloatPolygonEdge& edge = *(edges[i]);
454         const FloatPoint& vertex0 = edge.previousEdge().vertex1();
455         const FloatPoint& vertex1 = edge.vertex1();
456         const FloatPoint& vertex2 = edge.vertex2();
457         Vector<OffsetPolygonEdge> offsetEdgeBuffer;
458
459         if (vertex2.y() > vertex1.y() ? vertex2.x() >= vertex1.x() : vertex1.x() >= vertex2.x()) {
460             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, -dy)));
461             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, dy)));
462         } else {
463             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, dy)));
464             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, -dy)));
465         }
466
467         if (isReflexVertex(vertex0, vertex1, vertex2)) {
468             if (vertex2.x() <= vertex1.x() && vertex0.x() <= vertex1.x())
469                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(dx, -dy), FloatSize(dx, dy)));
470             else if (vertex2.x() >= vertex1.x() && vertex0.x() >= vertex1.x())
471                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(-dx, dy)));
472             if (vertex2.y() <= vertex1.y() && vertex0.y() <= vertex1.y())
473                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, dy), FloatSize(dx, dy)));
474             else if (vertex2.y() >= vertex1.y() && vertex0.y() >= vertex1.y())
475                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(dx, -dy)));
476         }
477
478         for (unsigned j = 0; j < offsetEdgeBuffer.size(); ++j)
479             if (offsetEdgeBuffer[j].maxY() >= minY)
480                 offsetEdges.append(offsetEdgeBuffer[j]);
481     }
482
483     offsetEdges.append(OffsetPolygonEdge(polygon, minIntervalTop, FloatSize(0, dy)));
484
485     FloatPoint offsetEdgesIntersection;
486     FloatRect firstFitRect;
487     bool firstFitFound = false;
488
489     for (unsigned i = 0; i < offsetEdges.size() - 1; ++i) {
490         for (unsigned j = i + 1; j < offsetEdges.size(); ++j) {
491             if (offsetEdges[i].intersection(offsetEdges[j], offsetEdgesIntersection)) {
492                 FloatPoint potentialFirstFitLocation(offsetEdgesIntersection.x() - dx, offsetEdgesIntersection.y() - dy);
493                 FloatRect potentialFirstFitRect(potentialFirstFitLocation, minLogicalIntervalSize);
494                 if ((offsetEdges[i].basis() == OffsetPolygonEdge::LineTop
495                     || offsetEdges[j].basis() == OffsetPolygonEdge::LineTop
496                     || potentialFirstFitLocation.y() >= minIntervalTop)
497                     && (!firstFitFound || aboveOrToTheLeft(potentialFirstFitRect, firstFitRect))
498                     && polygon.contains(offsetEdgesIntersection)
499                     && firstFitRectInPolygon(polygon, potentialFirstFitRect, offsetEdges[i].edgeIndex(), offsetEdges[j].edgeIndex())) {
500                     firstFitFound = true;
501                     firstFitRect = potentialFirstFitRect;
502                 }
503             }
504         }
505     }
506
507     if (firstFitFound)
508         result = ceiledLayoutUnit(firstFitRect.y());
509     return firstFitFound;
510 }
511
512 } // namespace WebCore