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 "core/rendering/shapes/PolygonShape.h" 32 33 #include "core/platform/graphics/LayoutPoint.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 inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point) 52 { 53 return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y())); 54 } 55 56 static inline bool isReflexVertex(const FloatPoint& prevVertex, const FloatPoint& vertex, const FloatPoint& nextVertex) 57 { 58 return leftSide(prevVertex, nextVertex, vertex) < 0; 59 } 60 61 static bool computeXIntersection(const FloatPolygonEdge* edgePointer, float y, EdgeIntersection& result) 62 { 63 const FloatPolygonEdge& edge = *edgePointer; 64 65 if (edge.minY() > y || edge.maxY() < y) 66 return false; 67 68 const FloatPoint& vertex1 = edge.vertex1(); 69 const FloatPoint& vertex2 = edge.vertex2(); 70 float dy = vertex2.y() - vertex1.y(); 71 72 float intersectionX; 73 EdgeIntersectionType intersectionType; 74 75 if (!dy) { 76 intersectionType = VertexYBoth; 77 intersectionX = edge.minX(); 78 } else if (y == edge.minY()) { 79 intersectionType = VertexMinY; 80 intersectionX = (vertex1.y() < vertex2.y()) ? vertex1.x() : vertex2.x(); 81 } else if (y == edge.maxY()) { 82 intersectionType = VertexMaxY; 83 intersectionX = (vertex1.y() > vertex2.y()) ? vertex1.x() : vertex2.x(); 84 } else { 85 intersectionType = Normal; 86 intersectionX = ((y - vertex1.y()) * (vertex2.x() - vertex1.x()) / dy) + vertex1.x(); 87 } 88 89 result.edge = edgePointer; 90 result.type = intersectionType; 91 result.point.set(intersectionX, y); 92 93 return true; 94 } 95 96 static inline FloatSize inwardEdgeNormal(const FloatPolygonEdge& edge) 97 { 98 FloatSize edgeDelta = edge.vertex2() - edge.vertex1(); 99 if (!edgeDelta.width()) 100 return FloatSize((edgeDelta.height() > 0 ? -1 : 1), 0); 101 if (!edgeDelta.height()) 102 return FloatSize(0, (edgeDelta.width() > 0 ? 1 : -1)); 103 float edgeLength = edgeDelta.diagonalLength(); 104 return FloatSize(-edgeDelta.height() / edgeLength, edgeDelta.width() / edgeLength); 105 } 106 107 static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge) 108 { 109 return -inwardEdgeNormal(edge); 110 } 111 112 static inline void appendArc(Vector<FloatPoint>& vertices, const FloatPoint& arcCenter, float arcRadius, const FloatPoint& startArcVertex, const FloatPoint& endArcVertex, bool padding) 113 { 114 float startAngle = atan2(startArcVertex.y() - arcCenter.y(), startArcVertex.x() - arcCenter.x()); 115 float endAngle = atan2(endArcVertex.y() - arcCenter.y(), endArcVertex.x() - arcCenter.x()); 116 const float twoPI = piFloat * 2; 117 if (startAngle < 0) 118 startAngle += twoPI; 119 if (endAngle < 0) 120 endAngle += twoPI; 121 float angle = (startAngle > endAngle) ? (startAngle - endAngle) : (startAngle + twoPI - endAngle); 122 const float arcSegmentCount = 6; // An even number so that one arc vertex will be eactly arcRadius from arcCenter. 123 float arcSegmentAngle = ((padding) ? -angle : twoPI - angle) / arcSegmentCount; 124 125 vertices.append(startArcVertex); 126 for (unsigned i = 1; i < arcSegmentCount; ++i) { 127 float angle = startAngle + arcSegmentAngle * i; 128 vertices.append(arcCenter + FloatPoint(cos(angle) * arcRadius, sin(angle) * arcRadius)); 129 } 130 vertices.append(endArcVertex); 131 } 132 133 static inline void snapVerticesToLayoutUnitGrid(Vector<FloatPoint>& vertices) 134 { 135 for (unsigned i = 0; i < vertices.size(); ++i) 136 vertices[i] = flooredLayoutPoint(vertices[i]); 137 } 138 139 static inline PassOwnPtr<FloatPolygon> computeShapePaddingBounds(const FloatPolygon& polygon, float padding, WindRule fillRule) 140 { 141 OwnPtr<Vector<FloatPoint> > paddedVertices = adoptPtr(new Vector<FloatPoint>()); 142 FloatPoint intersection; 143 144 for (unsigned i = 0; i < polygon.numberOfEdges(); ++i) { 145 const FloatPolygonEdge& thisEdge = polygon.edgeAt(i); 146 const FloatPolygonEdge& prevEdge = thisEdge.previousEdge(); 147 OffsetPolygonEdge thisOffsetEdge(thisEdge, inwardEdgeNormal(thisEdge) * padding); 148 OffsetPolygonEdge prevOffsetEdge(prevEdge, inwardEdgeNormal(prevEdge) * padding); 149 150 if (prevOffsetEdge.intersection(thisOffsetEdge, intersection)) 151 paddedVertices->append(intersection); 152 else if (isReflexVertex(prevEdge.vertex1(), thisEdge.vertex1(), thisEdge.vertex2())) 153 appendArc(*paddedVertices, thisEdge.vertex1(), padding, prevOffsetEdge.vertex2(), thisOffsetEdge.vertex1(), true); 154 } 155 156 snapVerticesToLayoutUnitGrid(*paddedVertices); 157 return adoptPtr(new FloatPolygon(paddedVertices.release(), fillRule)); 158 } 159 160 static inline PassOwnPtr<FloatPolygon> computeShapeMarginBounds(const FloatPolygon& polygon, float margin, WindRule fillRule) 161 { 162 OwnPtr<Vector<FloatPoint> > marginVertices = adoptPtr(new Vector<FloatPoint>()); 163 FloatPoint intersection; 164 165 for (unsigned i = 0; i < polygon.numberOfEdges(); ++i) { 166 const FloatPolygonEdge& thisEdge = polygon.edgeAt(i); 167 const FloatPolygonEdge& prevEdge = thisEdge.previousEdge(); 168 OffsetPolygonEdge thisOffsetEdge(thisEdge, outwardEdgeNormal(thisEdge) * margin); 169 OffsetPolygonEdge prevOffsetEdge(prevEdge, outwardEdgeNormal(prevEdge) * margin); 170 171 if (prevOffsetEdge.intersection(thisOffsetEdge, intersection)) 172 marginVertices->append(intersection); 173 else 174 appendArc(*marginVertices, thisEdge.vertex1(), margin, prevOffsetEdge.vertex2(), thisOffsetEdge.vertex1(), false); 175 } 176 177 snapVerticesToLayoutUnitGrid(*marginVertices); 178 return adoptPtr(new FloatPolygon(marginVertices.release(), fillRule)); 179 } 180 181 const FloatPolygon& PolygonShape::shapePaddingBounds() const 182 { 183 ASSERT(shapePadding() >= 0); 184 if (!shapePadding()) 185 return m_polygon; 186 187 if (!m_paddingBounds) 188 m_paddingBounds = computeShapePaddingBounds(m_polygon, shapePadding(), m_polygon.fillRule()); 189 190 return *m_paddingBounds; 191 } 192 193 const FloatPolygon& PolygonShape::shapeMarginBounds() const 194 { 195 ASSERT(shapeMargin() >= 0); 196 if (!shapeMargin()) 197 return m_polygon; 198 199 if (!m_marginBounds) 200 m_marginBounds = computeShapeMarginBounds(m_polygon, shapeMargin(), m_polygon.fillRule()); 201 202 return *m_marginBounds; 203 } 204 205 static inline bool getVertexIntersectionVertices(const EdgeIntersection& intersection, FloatPoint& prevVertex, FloatPoint& thisVertex, FloatPoint& nextVertex) 206 { 207 if (intersection.type != VertexMinY && intersection.type != VertexMaxY) 208 return false; 209 210 ASSERT(intersection.edge && intersection.edge->polygon()); 211 const FloatPolygon& polygon = *(intersection.edge->polygon()); 212 const FloatPolygonEdge& thisEdge = *(intersection.edge); 213 214 if ((intersection.type == VertexMinY && (thisEdge.vertex1().y() < thisEdge.vertex2().y())) 215 || (intersection.type == VertexMaxY && (thisEdge.vertex1().y() > thisEdge.vertex2().y()))) { 216 prevVertex = polygon.vertexAt(thisEdge.previousEdge().vertexIndex1()); 217 thisVertex = polygon.vertexAt(thisEdge.vertexIndex1()); 218 nextVertex = polygon.vertexAt(thisEdge.vertexIndex2()); 219 } else { 220 prevVertex = polygon.vertexAt(thisEdge.vertexIndex1()); 221 thisVertex = polygon.vertexAt(thisEdge.vertexIndex2()); 222 nextVertex = polygon.vertexAt(thisEdge.nextEdge().vertexIndex2()); 223 } 224 225 return true; 226 } 227 228 static inline bool appendIntervalX(float x, bool inside, Vector<ShapeInterval>& result) 229 { 230 if (!inside) 231 result.append(ShapeInterval(x)); 232 else 233 result[result.size() - 1].x2 = x; 234 235 return !inside; 236 } 237 238 static bool compareEdgeIntersectionX(const EdgeIntersection& intersection1, const EdgeIntersection& intersection2) 239 { 240 float x1 = intersection1.point.x(); 241 float x2 = intersection2.point.x(); 242 return (x1 == x2) ? intersection1.type < intersection2.type : x1 < x2; 243 } 244 245 static void computeXIntersections(const FloatPolygon& polygon, float y, bool isMinY, Vector<ShapeInterval>& result) 246 { 247 Vector<const FloatPolygonEdge*> edges; 248 if (!polygon.overlappingEdges(y, y, edges)) 249 return; 250 251 Vector<EdgeIntersection> intersections; 252 EdgeIntersection intersection; 253 for (unsigned i = 0; i < edges.size(); ++i) { 254 if (computeXIntersection(edges[i], y, intersection) && intersection.type != VertexYBoth) 255 intersections.append(intersection); 256 } 257 258 if (intersections.size() < 2) 259 return; 260 261 std::sort(intersections.begin(), intersections.end(), WebCore::compareEdgeIntersectionX); 262 263 unsigned index = 0; 264 int windCount = 0; 265 bool inside = false; 266 267 while (index < intersections.size()) { 268 const EdgeIntersection& thisIntersection = intersections[index]; 269 if (index + 1 < intersections.size()) { 270 const EdgeIntersection& nextIntersection = intersections[index + 1]; 271 if ((thisIntersection.point.x() == nextIntersection.point.x()) && (thisIntersection.type == VertexMinY || thisIntersection.type == VertexMaxY)) { 272 if (thisIntersection.type == nextIntersection.type) { 273 // Skip pairs of intersections whose types are VertexMaxY,VertexMaxY and VertexMinY,VertexMinY. 274 index += 2; 275 } else { 276 // Replace pairs of intersections whose types are VertexMinY,VertexMaxY or VertexMaxY,VertexMinY with one intersection. 277 ++index; 278 } 279 continue; 280 } 281 } 282 283 const FloatPolygonEdge& thisEdge = *thisIntersection.edge; 284 bool evenOddCrossing = !windCount; 285 286 if (polygon.fillRule() == RULE_EVENODD) { 287 windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? 1 : -1; 288 evenOddCrossing = evenOddCrossing || !windCount; 289 } 290 291 if (evenOddCrossing) { 292 bool edgeCrossing = thisIntersection.type == Normal; 293 if (!edgeCrossing) { 294 FloatPoint prevVertex; 295 FloatPoint thisVertex; 296 FloatPoint nextVertex; 297 298 if (getVertexIntersectionVertices(thisIntersection, prevVertex, thisVertex, nextVertex)) { 299 if (nextVertex.y() == y) 300 edgeCrossing = (isMinY) ? prevVertex.y() > y : prevVertex.y() < y; 301 else if (prevVertex.y() == y) 302 edgeCrossing = (isMinY) ? nextVertex.y() > y : nextVertex.y() < y; 303 else 304 edgeCrossing = true; 305 } 306 } 307 if (edgeCrossing) 308 inside = appendIntervalX(thisIntersection.point.x(), inside, result); 309 } 310 311 ++index; 312 } 313 } 314 315 static void computeOverlappingEdgeXProjections(const FloatPolygon& polygon, float y1, float y2, Vector<ShapeInterval>& result) 316 { 317 Vector<const FloatPolygonEdge*> edges; 318 if (!polygon.overlappingEdges(y1, y2, edges)) 319 return; 320 321 EdgeIntersection intersection; 322 for (unsigned i = 0; i < edges.size(); ++i) { 323 const FloatPolygonEdge *edge = edges[i]; 324 float x1; 325 float x2; 326 327 if (edge->minY() < y1) { 328 computeXIntersection(edge, y1, intersection); 329 x1 = intersection.point.x(); 330 } else { 331 x1 = (edge->vertex1().y() < edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x(); 332 } 333 334 if (edge->maxY() > y2) { 335 computeXIntersection(edge, y2, intersection); 336 x2 = intersection.point.x(); 337 } else { 338 x2 = (edge->vertex1().y() > edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x(); 339 } 340 341 if (x1 > x2) 342 std::swap(x1, x2); 343 344 if (x2 > x1) 345 result.append(ShapeInterval(x1, x2)); 346 } 347 348 sortShapeIntervals(result); 349 } 350 351 void PolygonShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const 352 { 353 const FloatPolygon& polygon = shapeMarginBounds(); 354 if (polygon.isEmpty()) 355 return; 356 357 float y1 = logicalTop; 358 float y2 = logicalTop + logicalHeight; 359 360 Vector<ShapeInterval> y1XIntervals, y2XIntervals; 361 computeXIntersections(polygon, y1, true, y1XIntervals); 362 computeXIntersections(polygon, y2, false, y2XIntervals); 363 364 Vector<ShapeInterval> mergedIntervals; 365 mergeShapeIntervals(y1XIntervals, y2XIntervals, mergedIntervals); 366 367 Vector<ShapeInterval> edgeIntervals; 368 computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals); 369 370 Vector<ShapeInterval> excludedIntervals; 371 mergeShapeIntervals(mergedIntervals, edgeIntervals, excludedIntervals); 372 373 for (unsigned i = 0; i < excludedIntervals.size(); ++i) { 374 ShapeInterval interval = excludedIntervals[i]; 375 result.append(LineSegment(interval.x1, interval.x2)); 376 } 377 } 378 379 void PolygonShape::getIncludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const 380 { 381 const FloatPolygon& polygon = shapePaddingBounds(); 382 if (polygon.isEmpty()) 383 return; 384 385 float y1 = logicalTop; 386 float y2 = logicalTop + logicalHeight; 387 388 Vector<ShapeInterval> y1XIntervals, y2XIntervals; 389 computeXIntersections(polygon, y1, true, y1XIntervals); 390 computeXIntersections(polygon, y2, false, y2XIntervals); 391 392 Vector<ShapeInterval> commonIntervals; 393 intersectShapeIntervals(y1XIntervals, y2XIntervals, commonIntervals); 394 395 Vector<ShapeInterval> edgeIntervals; 396 computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals); 397 398 Vector<ShapeInterval> includedIntervals; 399 subtractShapeIntervals(commonIntervals, edgeIntervals, includedIntervals); 400 401 for (unsigned i = 0; i < includedIntervals.size(); ++i) { 402 ShapeInterval interval = includedIntervals[i]; 403 result.append(LineSegment(interval.x1, interval.x2)); 404 } 405 } 406 407 static inline bool firstFitRectInPolygon(const FloatPolygon& polygon, const FloatRect& rect, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex2) 408 { 409 Vector<const FloatPolygonEdge*> edges; 410 if (!polygon.overlappingEdges(rect.y(), rect.maxY(), edges)) 411 return true; 412 413 for (unsigned i = 0; i < edges.size(); ++i) { 414 const FloatPolygonEdge* edge = edges[i]; 415 if (edge->edgeIndex() != offsetEdgeIndex1 && edge->edgeIndex() != offsetEdgeIndex2 && edge->overlapsRect(rect)) 416 return false; 417 } 418 419 return true; 420 } 421 422 static inline bool aboveOrToTheLeft(const FloatRect& r1, const FloatRect& r2) 423 { 424 if (r1.y() < r2.y()) 425 return true; 426 if (r1.y() == r2.y()) 427 return r1.x() < r2.x(); 428 return false; 429 } 430 431 bool PolygonShape::firstIncludedIntervalLogicalTop(LayoutUnit minLogicalIntervalTop, const LayoutSize& minLogicalIntervalSize, LayoutUnit& result) const 432 { 433 float minIntervalTop = minLogicalIntervalTop; 434 float minIntervalHeight = minLogicalIntervalSize.height(); 435 float minIntervalWidth = minLogicalIntervalSize.width(); 436 437 const FloatPolygon& polygon = shapePaddingBounds(); 438 const FloatRect boundingBox = polygon.boundingBox(); 439 if (minIntervalWidth > boundingBox.width()) 440 return false; 441 442 float minY = std::max(boundingBox.y(), minIntervalTop); 443 float maxY = minY + minIntervalHeight; 444 445 if (maxY > boundingBox.maxY()) 446 return false; 447 448 Vector<const FloatPolygonEdge*> edges; 449 polygon.overlappingEdges(minIntervalTop, boundingBox.maxY(), edges); 450 451 float dx = minIntervalWidth / 2; 452 float dy = minIntervalHeight / 2; 453 Vector<OffsetPolygonEdge> offsetEdges; 454 455 for (unsigned i = 0; i < edges.size(); ++i) { 456 const FloatPolygonEdge& edge = *(edges[i]); 457 const FloatPoint& vertex0 = edge.previousEdge().vertex1(); 458 const FloatPoint& vertex1 = edge.vertex1(); 459 const FloatPoint& vertex2 = edge.vertex2(); 460 Vector<OffsetPolygonEdge> offsetEdgeBuffer; 461 462 if (vertex2.y() > vertex1.y() ? vertex2.x() >= vertex1.x() : vertex1.x() >= vertex2.x()) { 463 offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, -dy))); 464 offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, dy))); 465 } else { 466 offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, dy))); 467 offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, -dy))); 468 } 469 470 if (isReflexVertex(vertex0, vertex1, vertex2)) { 471 if (vertex2.x() <= vertex1.x() && vertex0.x() <= vertex1.x()) 472 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(dx, -dy), FloatSize(dx, dy))); 473 else if (vertex2.x() >= vertex1.x() && vertex0.x() >= vertex1.x()) 474 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(-dx, dy))); 475 if (vertex2.y() <= vertex1.y() && vertex0.y() <= vertex1.y()) 476 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, dy), FloatSize(dx, dy))); 477 else if (vertex2.y() >= vertex1.y() && vertex0.y() >= vertex1.y()) 478 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(dx, -dy))); 479 } 480 481 for (unsigned j = 0; j < offsetEdgeBuffer.size(); ++j) { 482 if (offsetEdgeBuffer[j].maxY() >= minY) 483 offsetEdges.append(offsetEdgeBuffer[j]); 484 } 485 } 486 487 offsetEdges.append(OffsetPolygonEdge(polygon, minIntervalTop, FloatSize(0, dy))); 488 489 FloatPoint offsetEdgesIntersection; 490 FloatRect firstFitRect; 491 bool firstFitFound = false; 492 493 for (unsigned i = 0; i < offsetEdges.size() - 1; ++i) { 494 for (unsigned j = i + 1; j < offsetEdges.size(); ++j) { 495 if (offsetEdges[i].intersection(offsetEdges[j], offsetEdgesIntersection)) { 496 FloatPoint potentialFirstFitLocation(offsetEdgesIntersection.x() - dx, offsetEdgesIntersection.y() - dy); 497 FloatRect potentialFirstFitRect(potentialFirstFitLocation, minLogicalIntervalSize); 498 if ((offsetEdges[i].basis() == OffsetPolygonEdge::LineTop 499 || offsetEdges[j].basis() == OffsetPolygonEdge::LineTop 500 || potentialFirstFitLocation.y() >= minIntervalTop) 501 && (!firstFitFound || aboveOrToTheLeft(potentialFirstFitRect, firstFitRect)) 502 && polygon.contains(offsetEdgesIntersection) 503 && firstFitRectInPolygon(polygon, potentialFirstFitRect, offsetEdges[i].edgeIndex(), offsetEdges[j].edgeIndex())) { 504 firstFitFound = true; 505 firstFitRect = potentialFirstFitRect; 506 } 507 } 508 } 509 } 510 511 if (firstFitFound) 512 result = LayoutUnit::fromFloatCeil(firstFitRect.y()); 513 return firstFitFound; 514 } 515 516 } // namespace WebCore 517