Home | History | Annotate | Download | only in graphics 
      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/platform/graphics/FloatPolygon.h"
     32 
     33 #include "wtf/MathExtras.h"
     34 
     35 namespace WebCore {
     36 
     37 static inline float determinant(const FloatSize& a, const FloatSize& b)
     38 {
     39     return a.width() * b.height() - a.height() * b.width();
     40 }
     41 
     42 static inline bool areCollinearPoints(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2)
     43 {
     44     return !determinant(p1 - p0, p2 - p0);
     45 }
     46 
     47 static inline bool areCoincidentPoints(const FloatPoint& p0, const FloatPoint& p1)
     48 {
     49     return p0.x() == p1.x() && p0.y() == p1.y();
     50 }
     51 
     52 static inline bool isPointOnLineSegment(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
     53 {
     54     return point.x() >= std::min(vertex1.x(), vertex2.x())
     55         && point.x() <= std::max(vertex1.x(), vertex2.x())
     56         && areCollinearPoints(vertex1, vertex2, point);
     57 }
     58 
     59 static inline unsigned nextVertexIndex(unsigned vertexIndex, unsigned nVertices, bool clockwise)
     60 {
     61     return ((clockwise) ? vertexIndex + 1 : vertexIndex - 1 + nVertices) % nVertices;
     62 }
     63 
     64 static unsigned findNextEdgeVertexIndex(const FloatPolygon& polygon, unsigned vertexIndex1, bool clockwise)
     65 {
     66     unsigned nVertices = polygon.numberOfVertices();
     67     unsigned vertexIndex2 = nextVertexIndex(vertexIndex1, nVertices, clockwise);
     68 
     69     while (vertexIndex2 && areCoincidentPoints(polygon.vertexAt(vertexIndex1), polygon.vertexAt(vertexIndex2)))
     70         vertexIndex2 = nextVertexIndex(vertexIndex2, nVertices, clockwise);
     71 
     72     while (vertexIndex2) {
     73         unsigned vertexIndex3 = nextVertexIndex(vertexIndex2, nVertices, clockwise);
     74         if (!areCollinearPoints(polygon.vertexAt(vertexIndex1), polygon.vertexAt(vertexIndex2), polygon.vertexAt(vertexIndex3)))
     75             break;
     76         vertexIndex2 = vertexIndex3;
     77     }
     78 
     79     return vertexIndex2;
     80 }
     81 
     82 FloatPolygon::FloatPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule)
     83     : m_vertices(vertices)
     84     , m_fillRule(fillRule)
     85 {
     86     unsigned nVertices = numberOfVertices();
     87     m_edges.resize(nVertices);
     88     m_empty = nVertices < 3;
     89 
     90     if (nVertices)
     91         m_boundingBox.setLocation(vertexAt(0));
     92 
     93     if (m_empty)
     94         return;
     95 
     96     unsigned minVertexIndex = 0;
     97     for (unsigned i = 1; i < nVertices; ++i) {
     98         const FloatPoint& vertex = vertexAt(i);
     99         if (vertex.y() < vertexAt(minVertexIndex).y() || (vertex.y() == vertexAt(minVertexIndex).y() && vertex.x() < vertexAt(minVertexIndex).x()))
    100             minVertexIndex = i;
    101     }
    102     FloatPoint nextVertex = vertexAt((minVertexIndex + 1) % nVertices);
    103     FloatPoint prevVertex = vertexAt((minVertexIndex + nVertices - 1) % nVertices);
    104     bool clockwise = determinant(vertexAt(minVertexIndex) - prevVertex, nextVertex - prevVertex) > 0;
    105 
    106     unsigned edgeIndex = 0;
    107     unsigned vertexIndex1 = 0;
    108     do {
    109         m_boundingBox.extend(vertexAt(vertexIndex1));
    110         unsigned vertexIndex2 = findNextEdgeVertexIndex(*this, vertexIndex1, clockwise);
    111         m_edges[edgeIndex].m_polygon = this;
    112         m_edges[edgeIndex].m_vertexIndex1 = vertexIndex1;
    113         m_edges[edgeIndex].m_vertexIndex2 = vertexIndex2;
    114         m_edges[edgeIndex].m_edgeIndex = edgeIndex;
    115         ++edgeIndex;
    116         vertexIndex1 = vertexIndex2;
    117     } while (vertexIndex1);
    118 
    119     if (edgeIndex > 3) {
    120         const FloatPolygonEdge& firstEdge = m_edges[0];
    121         const FloatPolygonEdge& lastEdge = m_edges[edgeIndex - 1];
    122         if (areCollinearPoints(lastEdge.vertex1(), lastEdge.vertex2(), firstEdge.vertex2())) {
    123             m_edges[0].m_vertexIndex1 = lastEdge.m_vertexIndex1;
    124             edgeIndex--;
    125         }
    126     }
    127 
    128     m_edges.resize(edgeIndex);
    129     m_empty = m_edges.size() < 3;
    130 
    131     if (m_empty)
    132         return;
    133 
    134     for (unsigned i = 0; i < m_edges.size(); ++i) {
    135         FloatPolygonEdge* edge = &m_edges[i];
    136         m_edgeTree.add(EdgeInterval(edge->minY(), edge->maxY(), edge));
    137     }
    138 }
    139 
    140 bool FloatPolygon::overlappingEdges(float minY, float maxY, Vector<const FloatPolygonEdge*>& result) const
    141 {
    142     Vector<FloatPolygon::EdgeInterval> overlappingEdgeIntervals;
    143     m_edgeTree.allOverlaps(FloatPolygon::EdgeInterval(minY, maxY, 0), overlappingEdgeIntervals);
    144     unsigned overlappingEdgeIntervalsSize = overlappingEdgeIntervals.size();
    145     result.resize(overlappingEdgeIntervalsSize);
    146     for (unsigned i = 0; i < overlappingEdgeIntervalsSize; ++i) {
    147         const FloatPolygonEdge* edge = static_cast<const FloatPolygonEdge*>(overlappingEdgeIntervals[i].data());
    148         ASSERT(edge);
    149         result[i] = edge;
    150     }
    151     return overlappingEdgeIntervalsSize > 0;
    152 }
    153 
    154 static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
    155 {
    156     return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y()));
    157 }
    158 
    159 bool FloatPolygon::contains(const FloatPoint& point) const
    160 {
    161     if (!m_boundingBox.contains(point))
    162         return false;
    163 
    164     int windingNumber = 0;
    165     for (unsigned i = 0; i < numberOfEdges(); ++i) {
    166         const FloatPoint& vertex1 = edgeAt(i).vertex1();
    167         const FloatPoint& vertex2 = edgeAt(i).vertex2();
    168         if (isPointOnLineSegment(vertex1, vertex2, point))
    169             return true;
    170         if (vertex2.y() < point.y()) {
    171             if ((vertex1.y() > point.y()) && (leftSide(vertex1, vertex2, point) > 0))
    172                 ++windingNumber;
    173         } else if (vertex2.y() > point.y()) {
    174             if ((vertex1.y() <= point.y()) && (leftSide(vertex1, vertex2, point) < 0))
    175                 --windingNumber;
    176         }
    177     }
    178 
    179     return windingNumber;
    180 }
    181 
    182 bool VertexPair::overlapsRect(const FloatRect& rect) const
    183 {
    184     bool boundsOverlap = (minX() < rect.maxX()) && (maxX() > rect.x()) && (minY() < rect.maxY()) && (maxY() > rect.y());
    185     if (!boundsOverlap)
    186         return false;
    187 
    188     float leftSideValues[4] = {
    189         leftSide(vertex1(), vertex2(), rect.minXMinYCorner()),
    190         leftSide(vertex1(), vertex2(), rect.maxXMinYCorner()),
    191         leftSide(vertex1(), vertex2(), rect.minXMaxYCorner()),
    192         leftSide(vertex1(), vertex2(), rect.maxXMaxYCorner())
    193     };
    194 
    195     int currentLeftSideSign = 0;
    196     for (unsigned i = 0; i < 4; ++i) {
    197         if (!leftSideValues[i])
    198             continue;
    199         int leftSideSign = leftSideValues[i] > 0 ? 1 : -1;
    200         if (!currentLeftSideSign)
    201             currentLeftSideSign = leftSideSign;
    202         else if (currentLeftSideSign != leftSideSign)
    203             return true;
    204     }
    205 
    206     return false;
    207 }
    208 
    209 bool VertexPair::intersection(const VertexPair& other, FloatPoint& point) const
    210 {
    211     // See: http://paulbourke.net/geometry/pointlineplane/, "Intersection point of two lines in 2 dimensions"
    212 
    213     const FloatSize& thisDelta = vertex2() - vertex1();
    214     const FloatSize& otherDelta = other.vertex2() - other.vertex1();
    215     float denominator = determinant(thisDelta, otherDelta);
    216     if (!denominator)
    217         return false;
    218 
    219     // The two line segments: "this" vertex1,vertex2 and "other" vertex1,vertex2, have been defined
    220     // in parametric form. Each point on the line segment is: vertex1 + u * (vertex2 - vertex1),
    221     // when 0 <= u <= 1. We're computing the values of u for each line at their intersection point.
    222 
    223     const FloatSize& vertex1Delta = vertex1() - other.vertex1();
    224     float uThisLine = determinant(otherDelta, vertex1Delta) / denominator;
    225     float uOtherLine = determinant(thisDelta, vertex1Delta) / denominator;
    226 
    227     if (uThisLine < 0 || uOtherLine < 0 || uThisLine > 1 || uOtherLine > 1)
    228         return false;
    229 
    230     point = vertex1() + uThisLine * thisDelta;
    231     return true;
    232 }
    233 
    234 } // namespace WebCore
    235