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 34using std::max; 35using std::min; 36 37namespace WebCore { 38 39static inline float min4(float a, float b, float c, float d) 40{ 41 return min(min(a, b), min(c, d)); 42} 43 44static inline float max4(float a, float b, float c, float d) 45{ 46 return max(max(a, b), max(c, d)); 47} 48 49inline float dot(const FloatSize& a, const FloatSize& b) 50{ 51 return a.width() * b.width() + a.height() * b.height(); 52} 53 54inline 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 77FloatRect 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 88bool 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 94bool 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. 100bool 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