Source/WebCore/platform/graphics/FloatQuad.cpp

   1 /*
   2  * Copyright (C) 2008 Apple Inc. All rights reserved.
   3  * Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies)
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1.  Redistributions of source code must retain the above copyright
  10  *     notice, this list of conditions and the following disclaimer.
  11  * 2.  Redistributions in binary form must reproduce the above copyright
  12  *     notice, this list of conditions and the following disclaimer in the
  13  *     documentation and/or other materials provided with the distribution.
  14  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
  15  *     its contributors may be used to endorse or promote products derived
  16  *     from this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  21  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #include "config.h"
  31 #include "FloatQuad.h"
  32
  33 #include <algorithm>
  34 #include <limits>
  35
  36 using namespace std;
  37
  38 namespace WebCore {
  39
  40 static inline float min4(float a, float b, float c, float d)
  41 {
  42     return min(min(a, b), min(c, d));
  43 }
  44
  45 static inline float max4(float a, float b, float c, float d)
  46 {
  47     return max(max(a, b), max(c, d));
  48 }
  49
  50 inline float dot(const FloatSize& a, const FloatSize& b)
  51 {
  52     return a.width() * b.width() + a.height() * b.height();
  53 }
  54
  55 inline float determinant(const FloatSize& a, const FloatSize& b)
  56 {
  57     return a.width() * b.height() - a.height() * b.width();
  58 }
  59
  60 inline bool isPointInTriangle(const FloatPoint& p, const FloatPoint& t1, const FloatPoint& t2, const FloatPoint& t3)
  61 {
  62     // Compute vectors
  63     FloatSize v0 = t3 - t1;
  64     FloatSize v1 = t2 - t1;
  65     FloatSize v2 = p - t1;
  66
  67     // Compute dot products
  68     float dot00 = dot(v0, v0);
  69     float dot01 = dot(v0, v1);
  70     float dot02 = dot(v0, v2);
  71     float dot11 = dot(v1, v1);
  72     float dot12 = dot(v1, v2);
  73
  74     // Compute barycentric coordinates
  75     float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
  76     float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
  77     float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
  78
  79     // Check if point is in triangle
  80     return (u >= 0) && (v >= 0) && (u + v <= 1);
  81 }
  82
  83 FloatRect FloatQuad::boundingBox() const
  84 {
  85     float left   = min4(m_p1.x(), m_p2.x(), m_p3.x(), m_p4.x());
  86     float top    = min4(m_p1.y(), m_p2.y(), m_p3.y(), m_p4.y());
  87
  88     float right  = max4(m_p1.x(), m_p2.x(), m_p3.x(), m_p4.x());
  89     float bottom = max4(m_p1.y(), m_p2.y(), m_p3.y(), m_p4.y());
  90
  91     return FloatRect(left, top, right - left, bottom - top);
  92 }
  93
  94 static inline bool withinEpsilon(float a, float b)
  95 {
  96     return fabs(a - b) < numeric_limits<float>::epsilon();
  97 }
  98
  99 bool FloatQuad::isRectilinear() const
 100 {
 101     return (withinEpsilon(m_p1.x(), m_p2.x()) && withinEpsilon(m_p2.y(), m_p3.y()) && withinEpsilon(m_p3.x(), m_p4.x()) && withinEpsilon(m_p4.y(), m_p1.y()))
 102         || (withinEpsilon(m_p1.y(), m_p2.y()) && withinEpsilon(m_p2.x(), m_p3.x()) && withinEpsilon(m_p3.y(), m_p4.y()) && withinEpsilon(m_p4.x(), m_p1.x()));
 103 }
 104
 105 bool FloatQuad::containsPoint(const FloatPoint& p) const
 106 {
 107     return isPointInTriangle(p, m_p1, m_p2, m_p3) || isPointInTriangle(p, m_p1, m_p3, m_p4);
 108 }
 109
 110 // Note that we only handle convex quads here.
 111 bool FloatQuad::containsQuad(const FloatQuad& other) const
 112 {
 113     return containsPoint(other.p1()) && containsPoint(other.p2()) && containsPoint(other.p3()) && containsPoint(other.p4());
 114 }
 115
 116 static inline FloatPoint rightMostCornerToVector(const FloatRect& rect, const FloatSize& vector)
 117 {
 118     // Return the corner of the rectangle that if it is to the left of the vector
 119     // would mean all of the rectangle is to the left of the vector.
 120     // The vector here represents the side between two points in a clockwise convex polygon.
 121     //
 122     //  Q  XXX
 123     // QQQ XXX   If the lower left corner of X is left of the vector that goes from the top corner of Q to
 124     //  QQQ      the right corner of Q, then all of X is left of the vector, and intersection impossible.
 125     //   Q
 126     //
 127     FloatPoint point;
 128     if (vector.width() >= 0)
 129         point.setY(rect.maxY());
 130     else
 131         point.setY(rect.y());
 132     if (vector.height() >= 0)
 133         point.setX(rect.x());
 134     else
 135         point.setX(rect.maxX());
 136     return point;
 137 }
 138
 139 bool FloatQuad::intersectsRect(const FloatRect& rect) const
 140 {
 141     // For each side of the quad clockwise we check if the rectangle is to the left of it
 142     // since only content on the right can onlap with the quad.
 143     // This only works if the quad is convex.
 144     FloatSize v1, v2, v3, v4;
 145
 146     // Ensure we use clockwise vectors.
 147     if (!isCounterclockwise()) {
 148         v1 = m_p2 - m_p1;
 149         v2 = m_p3 - m_p2;
 150         v3 = m_p4 - m_p3;
 151         v4 = m_p1 - m_p4;
 152     } else {
 153         v1 = m_p4 - m_p1;
 154         v2 = m_p1 - m_p2;
 155         v3 = m_p2 - m_p3;
 156         v4 = m_p3 - m_p4;
 157     }
 158
 159     FloatPoint p = rightMostCornerToVector(rect, v1);
 160     if (determinant(v1, p - m_p1) < 0)
 161         return false;
 162
 163     p = rightMostCornerToVector(rect, v2);
 164     if (determinant(v2, p - m_p2) < 0)
 165         return false;
 166
 167     p = rightMostCornerToVector(rect, v3);
 168     if (determinant(v3, p - m_p3) < 0)
 169         return false;
 170
 171     p = rightMostCornerToVector(rect, v4);
 172     if (determinant(v4, p - m_p4) < 0)
 173         return false;
 174
 175     // If not all of the rectangle is outside one of the quad's four sides, then that means at least
 176     // a part of the rectangle is overlapping the quad.
 177     return true;
 178 }
 179
 180 bool FloatQuad::isCounterclockwise() const
 181 {
 182     // Return if the two first vectors are turning clockwise. If the quad is convex then all following vectors will turn the same way.
 183     return determinant(m_p2 - m_p1, m_p3 - m_p2) < 0;
 184 }
 185
 186 } // namespace WebCore