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 37static inline FloatSize inwardEdgeNormal(const FloatPolygonEdge& edge) 38{ 39 FloatSize edgeDelta = edge.vertex2() - edge.vertex1(); 40 if (!edgeDelta.width()) 41 return FloatSize((edgeDelta.height() > 0 ? -1 : 1), 0); 42 if (!edgeDelta.height()) 43 return FloatSize(0, (edgeDelta.width() > 0 ? 1 : -1)); 44 float edgeLength = edgeDelta.diagonalLength(); 45 return FloatSize(-edgeDelta.height() / edgeLength, edgeDelta.width() / edgeLength); 46} 47 48static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge) 49{ 50 return -inwardEdgeNormal(edge); 51} 52 53float OffsetPolygonEdge::xIntercept(float y) const 54{ 55 ASSERT(y >= minY() && y <= maxY()); 56 57 if (vertex1().y() == vertex2().y() || vertex1().x() == vertex2().x()) 58 return minX(); 59 if (y == minY()) 60 return vertex1().y() < vertex2().y() ? vertex1().x() : vertex2().x(); 61 if (y == maxY()) 62 return vertex1().y() > vertex2().y() ? vertex1().x() : vertex2().x(); 63 64 return vertex1().x() + ((y - vertex1().y()) * (vertex2().x() - vertex1().x()) / (vertex2().y() - vertex1().y())); 65} 66 67FloatShapeInterval OffsetPolygonEdge::clippedEdgeXRange(float y1, float y2) const 68{ 69 if (!overlapsYRange(y1, y2) || (y1 == maxY() && minY() <= y1) || (y2 == minY() && maxY() >= y2)) 70 return FloatShapeInterval(); 71 72 if (isWithinYRange(y1, y2)) 73 return FloatShapeInterval(minX(), maxX()); 74 75 // Clip the edge line segment to the vertical range y1,y2 and then return 76 // the clipped line segment's horizontal range. 77 78 FloatPoint minYVertex; 79 FloatPoint maxYVertex; 80 if (vertex1().y() < vertex2().y()) { 81 minYVertex = vertex1(); 82 maxYVertex = vertex2(); 83 } else { 84 minYVertex = vertex2(); 85 maxYVertex = vertex1(); 86 } 87 float xForY1 = (minYVertex.y() < y1) ? xIntercept(y1) : minYVertex.x(); 88 float xForY2 = (maxYVertex.y() > y2) ? xIntercept(y2) : maxYVertex.x(); 89 return FloatShapeInterval(std::min(xForY1, xForY2), std::max(xForY1, xForY2)); 90} 91 92static float circleXIntercept(float y, float radius) 93{ 94 ASSERT(radius > 0); 95 return radius * sqrt(1 - (y * y) / (radius * radius)); 96} 97 98static FloatShapeInterval clippedCircleXRange(const FloatPoint& center, float radius, float y1, float y2) 99{ 100 if (y1 > center.y() + radius || y2 < center.y() - radius) 101 return FloatShapeInterval(); 102 103 if (center.y() >= y1 && center.y() <= y2) 104 return FloatShapeInterval(center.x() - radius, center.x() + radius); 105 106 // Clip the circle to the vertical range y1,y2 and return the extent of the clipped circle's 107 // projection on the X axis 108 109 float xi = circleXIntercept((y2 < center.y() ? y2 : y1) - center.y(), radius); 110 return FloatShapeInterval(center.x() - xi, center.x() + xi); 111} 112 113LayoutRect PolygonShape::shapeMarginLogicalBoundingBox() const 114{ 115 FloatRect box = m_polygon.boundingBox(); 116 box.inflate(shapeMargin()); 117 return LayoutRect(box); 118} 119 120void PolygonShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const 121{ 122 float y1 = logicalTop; 123 float y2 = logicalTop + logicalHeight; 124 125 if (m_polygon.isEmpty() || !m_polygon.boundingBox().overlapsYRange(y1 - shapeMargin(), y2 + shapeMargin())) 126 return; 127 128 Vector<const FloatPolygonEdge*> overlappingEdges; 129 if (!m_polygon.overlappingEdges(y1 - shapeMargin(), y2 + shapeMargin(), overlappingEdges)) 130 return; 131 132 FloatShapeInterval excludedInterval; 133 for (unsigned i = 0; i < overlappingEdges.size(); i++) { 134 const FloatPolygonEdge& edge = *(overlappingEdges[i]); 135 if (edge.maxY() == edge.minY()) 136 continue; 137 if (!shapeMargin()) 138 excludedInterval.unite(OffsetPolygonEdge(edge, FloatSize()).clippedEdgeXRange(y1, y2)); 139 else { 140 excludedInterval.unite(OffsetPolygonEdge(edge, outwardEdgeNormal(edge) * shapeMargin()).clippedEdgeXRange(y1, y2)); 141 excludedInterval.unite(OffsetPolygonEdge(edge, inwardEdgeNormal(edge) * shapeMargin()).clippedEdgeXRange(y1, y2)); 142 excludedInterval.unite(clippedCircleXRange(edge.vertex1(), shapeMargin(), y1, y2)); 143 } 144 } 145 146 if (!excludedInterval.isEmpty()) 147 result.append(LineSegment(excludedInterval.x1(), excludedInterval.x2())); 148} 149 150void PolygonShape::buildDisplayPaths(DisplayPaths& paths) const 151{ 152 if (m_polygon.isEmpty()) 153 return; 154 155 paths.shape.moveTo(m_polygon.vertexAt(0)); 156 for (unsigned i = 1; i < m_polygon.numberOfVertices(); i++) 157 paths.shape.addLineTo(m_polygon.vertexAt(i)); 158 159 paths.shape.closeSubpath(); 160} 161 162} // namespace WebCore 163