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 35namespace WebCore { 36 37enum EdgeIntersectionType { 38 Normal, 39 VertexMinY, 40 VertexMaxY, 41 VertexYBoth 42}; 43 44struct EdgeIntersection { 45 const FloatPolygonEdge* edge; 46 FloatPoint point; 47 EdgeIntersectionType type; 48}; 49 50static 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 55static inline bool isReflexVertex(const FloatPoint& prevVertex, const FloatPoint& vertex, const FloatPoint& nextVertex) 56{ 57 return leftSide(prevVertex, nextVertex, vertex) < 0; 58} 59 60static 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 95static 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 106static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge) 107{ 108 return -inwardEdgeNormal(edge); 109} 110 111static 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 132static 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 138static 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 159static 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 180const 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 192const 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 204static 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 227static 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 237static 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 244static 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 314static 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 348void 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 376void 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 404static 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 419static 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 428bool 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 513