1 /* 2 * Copyright (C) 2008 Apple Inc. 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 copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of 14 * its contributors may be used to endorse or promote products derived 15 * from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 #include "config.h" 30 #include "FloatQuad.h" 31 32 #include <algorithm> 33 34 using std::max; 35 using std::min; 36 37 namespace WebCore { 38 39 static inline float min4(float a, float b, float c, float d) 40 { 41 return min(min(a, b), min(c, d)); 42 } 43 44 static inline float max4(float a, float b, float c, float d) 45 { 46 return max(max(a, b), max(c, d)); 47 } 48 49 inline float dot(const FloatSize& a, const FloatSize& b) 50 { 51 return a.width() * b.width() + a.height() * b.height(); 52 } 53 54 inline bool isPointInTriangle(const FloatPoint& p, const FloatPoint& t1, const FloatPoint& t2, const FloatPoint& t3) 55 { 56 // Compute vectors 57 FloatSize v0 = t3 - t1; 58 FloatSize v1 = t2 - t1; 59 FloatSize v2 = p - t1; 60 61 // Compute dot products 62 float dot00 = dot(v0, v0); 63 float dot01 = dot(v0, v1); 64 float dot02 = dot(v0, v2); 65 float dot11 = dot(v1, v1); 66 float dot12 = dot(v1, v2); 67 68 // Compute barycentric coordinates 69 float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01); 70 float u = (dot11 * dot02 - dot01 * dot12) * invDenom; 71 float v = (dot00 * dot12 - dot01 * dot02) * invDenom; 72 73 // Check if point is in triangle 74 return (u >= 0) && (v >= 0) && (u + v <= 1); 75 } 76 77 FloatRect FloatQuad::boundingBox() const 78 { 79 float left = min4(m_p1.x(), m_p2.x(), m_p3.x(), m_p4.x()); 80 float top = min4(m_p1.y(), m_p2.y(), m_p3.y(), m_p4.y()); 81 82 float right = max4(m_p1.x(), m_p2.x(), m_p3.x(), m_p4.x()); 83 float bottom = max4(m_p1.y(), m_p2.y(), m_p3.y(), m_p4.y()); 84 85 return FloatRect(left, top, right - left, bottom - top); 86 } 87 88 bool FloatQuad::isRectilinear() const 89 { 90 return (m_p1.x() == m_p2.x() && m_p2.y() == m_p3.y() && m_p3.x() == m_p4.x() && m_p4.y() == m_p1.y()) 91 || (m_p1.y() == m_p2.y() && m_p2.x() == m_p3.x() && m_p3.y() == m_p4.y() && m_p4.x() == m_p1.x()); 92 } 93 94 bool FloatQuad::containsPoint(const FloatPoint& p) const 95 { 96 return isPointInTriangle(p, m_p1, m_p2, m_p3) || isPointInTriangle(p, m_p1, m_p3, m_p4); 97 } 98 99 // Note that we only handle convex quads here. 100 bool FloatQuad::containsQuad(const FloatQuad& other) const 101 { 102 return containsPoint(other.p1()) && containsPoint(other.p2()) && containsPoint(other.p3()) && containsPoint(other.p4()); 103 } 104 105 } // namespace WebCore 106
