Move Source/WebCore/rendering/ code to std::unique_ptr
[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 "ShapeInterval.h"
34 #include <wtf/MathExtras.h>
35
36 namespace WebCore {
37
38 enum EdgeIntersectionType {
39     Normal,
40     VertexMinY,
41     VertexMaxY,
42     VertexYBoth
43 };
44
45 struct EdgeIntersection {
46     const FloatPolygonEdge* edge;
47     FloatPoint point;
48     EdgeIntersectionType type;
49 };
50
51 static bool computeXIntersection(const FloatPolygonEdge* edgePointer, float y, EdgeIntersection& result)
52 {
53     const FloatPolygonEdge& edge = *edgePointer;
54
55     if (edge.minY() > y || edge.maxY() < y)
56         return false;
57
58     const FloatPoint& vertex1 = edge.vertex1();
59     const FloatPoint& vertex2 = edge.vertex2();
60     float dy = vertex2.y() - vertex1.y();
61
62     float intersectionX;
63     EdgeIntersectionType intersectionType;
64
65     if (!dy) {
66         intersectionType = VertexYBoth;
67         intersectionX = edge.minX();
68     } else if (y == edge.minY()) {
69         intersectionType = VertexMinY;
70         intersectionX = (vertex1.y() < vertex2.y()) ? vertex1.x() : vertex2.x();
71     } else if (y == edge.maxY()) {
72         intersectionType = VertexMaxY;
73         intersectionX = (vertex1.y() > vertex2.y()) ? vertex1.x() : vertex2.x();
74     } else {
75         intersectionType = Normal;
76         intersectionX = ((y - vertex1.y()) * (vertex2.x() - vertex1.x()) / dy) + vertex1.x();
77     }
78
79     result.edge = edgePointer;
80     result.type = intersectionType;
81     result.point.set(intersectionX, y);
82
83     return true;
84 }
85
86 static inline FloatSize inwardEdgeNormal(const FloatPolygonEdge& edge)
87 {
88     FloatSize edgeDelta = edge.vertex2() - edge.vertex1();
89     if (!edgeDelta.width())
90         return FloatSize((edgeDelta.height() > 0 ? -1 : 1), 0);
91     if (!edgeDelta.height())
92         return FloatSize(0, (edgeDelta.width() > 0 ? 1 : -1));
93     float edgeLength = edgeDelta.diagonalLength();
94     return FloatSize(-edgeDelta.height() / edgeLength, edgeDelta.width() / edgeLength);
95 }
96
97 static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge)
98 {
99     return -inwardEdgeNormal(edge);
100 }
101
102 static inline void appendArc(Vector<FloatPoint>& vertices, const FloatPoint& arcCenter, float arcRadius, const FloatPoint& startArcVertex, const FloatPoint& endArcVertex, bool padding)
103 {
104     float startAngle = atan2(startArcVertex.y() - arcCenter.y(), startArcVertex.x() - arcCenter.x());
105     float endAngle = atan2(endArcVertex.y() - arcCenter.y(), endArcVertex.x() - arcCenter.x());
106     const float twoPI = piFloat * 2;
107     if (startAngle < 0)
108         startAngle += twoPI;
109     if (endAngle < 0)
110         endAngle += twoPI;
111     float angle = (startAngle > endAngle) ? (startAngle - endAngle) : (startAngle + twoPI - endAngle);
112     const float arcSegmentCount = 6; // An even number so that one arc vertex will be eactly arcRadius from arcCenter.
113     float arcSegmentAngle =  ((padding) ? -angle : twoPI - angle) / arcSegmentCount;
114
115     vertices.append(startArcVertex);
116     for (unsigned i = 1; i < arcSegmentCount; ++i) {
117         float angle = startAngle + arcSegmentAngle * i;
118         vertices.append(arcCenter + FloatPoint(cos(angle) * arcRadius, sin(angle) * arcRadius));
119     }
120     vertices.append(endArcVertex);
121 }
122
123 static inline void snapVerticesToLayoutUnitGrid(Vector<FloatPoint>& vertices)
124 {
125     for (unsigned i = 0; i < vertices.size(); ++i)
126         vertices[i].set(LayoutUnit(vertices[i].x()).toFloat(), LayoutUnit(vertices[i].y()).toFloat());
127 }
128
129 static inline std::unique_ptr<FloatPolygon> computeShapeMarginBounds(const FloatPolygon& polygon, float margin, WindRule fillRule)
130 {
131     auto marginVertices = std::make_unique<Vector<FloatPoint>>();
132     FloatPoint intersection;
133
134     for (unsigned i = 0; i < polygon.numberOfEdges(); ++i) {
135         const FloatPolygonEdge& thisEdge = polygon.edgeAt(i);
136         const FloatPolygonEdge& prevEdge = thisEdge.previousEdge();
137         OffsetPolygonEdge thisOffsetEdge(thisEdge, outwardEdgeNormal(thisEdge) * margin);
138         OffsetPolygonEdge prevOffsetEdge(prevEdge, outwardEdgeNormal(prevEdge) * margin);
139
140         if (prevOffsetEdge.intersection(thisOffsetEdge, intersection))
141             marginVertices->append(intersection);
142         else
143             appendArc(*marginVertices, thisEdge.vertex1(), margin, prevOffsetEdge.vertex2(), thisOffsetEdge.vertex1(), false);
144     }
145
146     snapVerticesToLayoutUnitGrid(*marginVertices);
147     return std::make_unique<FloatPolygon>(std::move(marginVertices), fillRule);
148 }
149
150
151 const FloatPolygon& PolygonShape::shapeMarginBounds() const
152 {
153     ASSERT(shapeMargin() >= 0);
154     if (!shapeMargin() || m_polygon.isEmpty())
155         return m_polygon;
156
157     if (!m_marginBounds)
158         m_marginBounds = computeShapeMarginBounds(m_polygon, shapeMargin(), m_polygon.fillRule());
159
160     return *m_marginBounds;
161 }
162
163 static inline bool getVertexIntersectionVertices(const EdgeIntersection& intersection, FloatPoint& prevVertex, FloatPoint& thisVertex, FloatPoint& nextVertex)
164 {
165     if (intersection.type != VertexMinY && intersection.type != VertexMaxY)
166         return false;
167
168     ASSERT(intersection.edge && intersection.edge->polygon());
169     const FloatPolygon& polygon = *(intersection.edge->polygon());
170     const FloatPolygonEdge& thisEdge = *(intersection.edge);
171
172     if ((intersection.type == VertexMinY && (thisEdge.vertex1().y() < thisEdge.vertex2().y()))
173         || (intersection.type == VertexMaxY && (thisEdge.vertex1().y() > thisEdge.vertex2().y()))) {
174         prevVertex = polygon.vertexAt(thisEdge.previousEdge().vertexIndex1());
175         thisVertex = polygon.vertexAt(thisEdge.vertexIndex1());
176         nextVertex = polygon.vertexAt(thisEdge.vertexIndex2());
177     } else {
178         prevVertex = polygon.vertexAt(thisEdge.vertexIndex1());
179         thisVertex = polygon.vertexAt(thisEdge.vertexIndex2());
180         nextVertex = polygon.vertexAt(thisEdge.nextEdge().vertexIndex2());
181     }
182
183     return true;
184 }
185
186 static inline bool appendIntervalX(float x, bool inside, FloatShapeIntervals& result)
187 {
188     if (!inside)
189         result.append(FloatShapeInterval(x, x));
190     else
191         result.last().setX2(x);
192
193     return !inside;
194 }
195
196 static bool compareEdgeIntersectionX(const EdgeIntersection& intersection1, const EdgeIntersection& intersection2)
197 {
198     float x1 = intersection1.point.x();
199     float x2 = intersection2.point.x();
200     return (x1 == x2) ? intersection1.type < intersection2.type : x1 < x2;
201 }
202
203 static void computeXIntersections(const FloatPolygon& polygon, float y, bool isMinY, FloatShapeIntervals& result)
204 {
205     Vector<const FloatPolygonEdge*> edges;
206     if (!polygon.overlappingEdges(y, y, edges))
207         return;
208
209     Vector<EdgeIntersection> intersections;
210     EdgeIntersection intersection;
211     for (unsigned i = 0; i < edges.size(); ++i) {
212         if (computeXIntersection(edges[i], y, intersection) && intersection.type != VertexYBoth)
213             intersections.append(intersection);
214     }
215
216     if (intersections.size() < 2)
217         return;
218
219     std::sort(intersections.begin(), intersections.end(), WebCore::compareEdgeIntersectionX);
220
221     unsigned index = 0;
222     int windCount = 0;
223     bool inside = false;
224
225     while (index < intersections.size()) {
226         const EdgeIntersection& thisIntersection = intersections[index];
227         if (index + 1 < intersections.size()) {
228             const EdgeIntersection& nextIntersection = intersections[index + 1];
229             if ((thisIntersection.point.x() == nextIntersection.point.x()) && (thisIntersection.type == VertexMinY || thisIntersection.type == VertexMaxY)) {
230                 if (thisIntersection.type == nextIntersection.type) {
231                     // Skip pairs of intersections whose types are VertexMaxY,VertexMaxY and VertexMinY,VertexMinY.
232                     index += 2;
233                 } else {
234                     // Replace pairs of intersections whose types are VertexMinY,VertexMaxY or VertexMaxY,VertexMinY with one intersection.
235                     ++index;
236                 }
237                 continue;
238             }
239         }
240
241         bool edgeCrossing = thisIntersection.type == Normal;
242         if (!edgeCrossing) {
243             FloatPoint prevVertex;
244             FloatPoint thisVertex;
245             FloatPoint nextVertex;
246
247             if (getVertexIntersectionVertices(thisIntersection, prevVertex, thisVertex, nextVertex)) {
248                 if (nextVertex.y() == y)
249                     edgeCrossing = (isMinY) ? prevVertex.y() > y : prevVertex.y() < y;
250                 else if (prevVertex.y() == y)
251                     edgeCrossing = (isMinY) ? nextVertex.y() > y : nextVertex.y() < y;
252                 else
253                     edgeCrossing = true;
254             }
255         }
256
257         if (edgeCrossing && polygon.fillRule() == RULE_NONZERO) {
258             const FloatPolygonEdge& thisEdge = *thisIntersection.edge;
259             windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? 1 : -1;
260         }
261
262         if (edgeCrossing && (!inside || !windCount))
263             inside = appendIntervalX(thisIntersection.point.x(), inside, result);
264
265         ++index;
266     }
267 }
268
269 static bool compareX1(const FloatShapeInterval a, const FloatShapeInterval& b) { return a.x1() < b.x1(); }
270
271 static void sortAndMergeShapeIntervals(FloatShapeIntervals& intervals)
272 {
273     std::sort(intervals.begin(), intervals.end(), compareX1);
274
275     for (unsigned i = 1; i < intervals.size(); ) {
276         const FloatShapeInterval& thisInterval = intervals[i];
277         FloatShapeInterval& previousInterval = intervals[i - 1];
278         if (thisInterval.overlaps(previousInterval)) {
279             previousInterval.setX2(std::max<float>(previousInterval.x2(), thisInterval.x2()));
280             intervals.remove(i);
281         } else
282             ++i;
283     }
284 }
285
286 static void computeOverlappingEdgeXProjections(const FloatPolygon& polygon, float y1, float y2, FloatShapeIntervals& result)
287 {
288     Vector<const FloatPolygonEdge*> edges;
289     if (!polygon.overlappingEdges(y1, y2, edges))
290         return;
291
292     EdgeIntersection intersection;
293     for (unsigned i = 0; i < edges.size(); ++i) {
294         const FloatPolygonEdge *edge = edges[i];
295         float x1;
296         float x2;
297
298         if (edge->minY() < y1) {
299             computeXIntersection(edge, y1, intersection);
300             x1 = intersection.point.x();
301         } else
302             x1 = (edge->vertex1().y() < edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
303
304         if (edge->maxY() > y2) {
305             computeXIntersection(edge, y2, intersection);
306             x2 = intersection.point.x();
307         } else
308             x2 = (edge->vertex1().y() > edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
309
310         if (x1 > x2)
311             std::swap(x1, x2);
312
313         if (x2 > x1)
314             result.append(FloatShapeInterval(x1, x2));
315     }
316
317     sortAndMergeShapeIntervals(result);
318 }
319
320 void PolygonShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
321 {
322     const FloatPolygon& polygon = shapeMarginBounds();
323     if (polygon.isEmpty())
324         return;
325
326     float y1 = logicalTop;
327     float y2 = logicalTop + logicalHeight;
328
329     FloatShapeIntervals y1XIntervals, y2XIntervals;
330     computeXIntersections(polygon, y1, true, y1XIntervals);
331     computeXIntersections(polygon, y2, false, y2XIntervals);
332
333     FloatShapeIntervals mergedIntervals;
334     FloatShapeInterval::uniteShapeIntervals(y1XIntervals, y2XIntervals, mergedIntervals);
335
336     FloatShapeIntervals edgeIntervals;
337     computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals);
338
339     FloatShapeIntervals excludedIntervals;
340     FloatShapeInterval::uniteShapeIntervals(mergedIntervals, edgeIntervals, excludedIntervals);
341
342     for (unsigned i = 0; i < excludedIntervals.size(); ++i) {
343         FloatShapeInterval interval = excludedIntervals[i];
344         result.append(LineSegment(interval.x1(), interval.x2()));
345     }
346 }
347
348 static void addPolygon(Path& path, const FloatPolygon& polygon)
349 {
350     if (!polygon.numberOfVertices())
351         return;
352
353     path.moveTo(polygon.vertexAt(0));
354
355     for (size_t i = 1; i < polygon.numberOfVertices(); i++)
356         path.addLineTo(polygon.vertexAt(i));
357
358     path.closeSubpath();
359 }
360
361 void PolygonShape::buildDisplayPaths(DisplayPaths& paths) const
362 {
363     addPolygon(paths.shape, m_polygon);
364     if (shapeMargin())
365         addPolygon(paths.marginShape, shapeMarginBounds());
366 }
367
368 } // namespace WebCore