18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2008 Apple Inc. All rights reserved. 38e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Redistribution and use in source and binary forms, with or without 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modification, are permitted provided that the following conditions 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * are met: 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 1. Redistributions of source code must retain the above copyright 9635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project * notice, this list of conditions and the following disclaimer. 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer in the 12635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project * documentation and/or other materials provided with the distribution. 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * its contributors may be used to endorse or promote products derived 15635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project * from this software without specific prior written permission. 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "config.h" 30635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project#include "FloatQuad.h" 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 32635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project#include <algorithm> 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 34635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Projectusing std::max; 35635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Projectusing std::min; 36635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 37635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Projectnamespace WebCore { 38635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 39635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Projectstatic inline float min4(float a, float b, float c, float d) 40635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project{ 41635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project return min(min(a, b), min(c, d)); 42635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project} 43635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 44635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Projectstatic inline float max4(float a, float b, float c, float d) 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 46635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project return max(max(a, b), max(c, d)); 47635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project} 48635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qianinline float dot(const FloatSize& a, const FloatSize& b) 505f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian{ 515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian return a.width() * b.width() + a.height() * b.height(); 525f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian} 535f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian 545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qianinline bool isPointInTriangle(const FloatPoint& p, const FloatPoint& t1, const FloatPoint& t2, const FloatPoint& t3) 555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian{ 565f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian // Compute vectors 575f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian FloatSize v0 = t3 - t1; 585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian FloatSize v1 = t2 - t1; 595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian FloatSize v2 = p - t1; 605f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian 615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian // Compute dot products 625f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian float dot00 = dot(v0, v0); 635f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian float dot01 = dot(v0, v1); 645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian float dot02 = dot(v0, v2); 655f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian float dot11 = dot(v1, v1); 665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian float dot12 = dot(v1, v2); 675f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian 685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian // Compute barycentric coordinates 695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01); 705f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian float u = (dot11 * dot02 - dot01 * dot12) * invDenom; 715f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian float v = (dot00 * dot12 - dot01 * dot02) * invDenom; 725f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian 735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian // Check if point is in triangle 745f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian return (u >= 0) && (v >= 0) && (u + v <= 1); 755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian} 765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian 77635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source ProjectFloatRect FloatQuad::boundingBox() const 78635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project{ 79635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project float left = min4(m_p1.x(), m_p2.x(), m_p3.x(), m_p4.x()); 80635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project float top = min4(m_p1.y(), m_p2.y(), m_p3.y(), m_p4.y()); 81635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 82635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project float right = max4(m_p1.x(), m_p2.x(), m_p3.x(), m_p4.x()); 83635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project float bottom = max4(m_p1.y(), m_p2.y(), m_p3.y(), m_p4.y()); 84635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 85635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project return FloatRect(left, top, right - left, bottom - top); 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 88d0825bca7fe65beaee391d30da42e937db621564Steve Blockbool FloatQuad::isRectilinear() const 89d0825bca7fe65beaee391d30da42e937db621564Steve Block{ 90d0825bca7fe65beaee391d30da42e937db621564Steve Block 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()) 91d0825bca7fe65beaee391d30da42e937db621564Steve Block || (m_p1.y() == m_p2.y() && m_p2.x() == m_p3.x() && m_p3.y() == m_p4.y() && m_p4.x() == m_p1.x()); 92d0825bca7fe65beaee391d30da42e937db621564Steve Block} 93d0825bca7fe65beaee391d30da42e937db621564Steve Block 945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qianbool FloatQuad::containsPoint(const FloatPoint& p) const 955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian{ 965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian return isPointInTriangle(p, m_p1, m_p2, m_p3) || isPointInTriangle(p, m_p1, m_p3, m_p4); 975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian} 985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian 995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian// Note that we only handle convex quads here. 1005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qianbool FloatQuad::containsQuad(const FloatQuad& other) const 1015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian{ 1025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian return containsPoint(other.p1()) && containsPoint(other.p2()) && containsPoint(other.p3()) && containsPoint(other.p4()); 1035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian} 1045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian 105635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project} // namespace WebCore 106