1685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com 2b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com/* 3685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com * Copyright 2009 The Android Open Source Project 4b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com * 5685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com * found in the LICENSE file. 7b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com */ 8b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com 9685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com 10b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com#include "SkQuadClipper.h" 11b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com#include "SkGeometry.h" 12b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com 13de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.comstatic inline void clamp_le(SkScalar& value, SkScalar max) { 14de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com if (value > max) { 15de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com value = max; 16de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com } 17de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com} 18de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com 19de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.comstatic inline void clamp_ge(SkScalar& value, SkScalar min) { 20de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com if (value < min) { 21de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com value = min; 22de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com } 23de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com} 24de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com 25a8a02b7a570cbfb0966453a1e0fc4275975e734bvandebo@chromium.orgSkQuadClipper::SkQuadClipper() { 26a8a02b7a570cbfb0966453a1e0fc4275975e734bvandebo@chromium.org fClip.setEmpty(); 27a8a02b7a570cbfb0966453a1e0fc4275975e734bvandebo@chromium.org} 2868779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com 2968779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.comvoid SkQuadClipper::setClip(const SkIRect& clip) { 3068779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // conver to scalars, since that's where we'll see the points 3168779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com fClip.set(clip); 3268779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com} 3368779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com 3468779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com/////////////////////////////////////////////////////////////////////////////// 3568779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com 36001bd97fe25bbaefe62915ac6f803b765230282breed@android.comstatic bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2, 37001bd97fe25bbaefe62915ac6f803b765230282breed@android.com SkScalar target, SkScalar* t) { 38b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2 39b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com * We solve for t, using quadratic equation, hence we have to rearrange 40b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com * our cooefficents to look like At^2 + Bt + C 41b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com */ 42001bd97fe25bbaefe62915ac6f803b765230282breed@android.com SkScalar A = c0 - c1 - c1 + c2; 43001bd97fe25bbaefe62915ac6f803b765230282breed@android.com SkScalar B = 2*(c1 - c0); 44001bd97fe25bbaefe62915ac6f803b765230282breed@android.com SkScalar C = c0 - target; 45935e9f4fafdfc64130e6be9ea2bb30e3bafd852armistry@google.com 46b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com SkScalar roots[2]; // we only expect one, but make room for 2 for safety 47b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com int count = SkFindUnitQuadRoots(A, B, C, roots); 48b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com if (count) { 49b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com *t = roots[0]; 50b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com return true; 51b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com } 52b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com return false; 53b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com} 54b35fe4e1b04229a849227ea6c2561fe84929ab8breed@android.com 55001bd97fe25bbaefe62915ac6f803b765230282breed@android.comstatic bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { 56001bd97fe25bbaefe62915ac6f803b765230282breed@android.com return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t); 57001bd97fe25bbaefe62915ac6f803b765230282breed@android.com} 58001bd97fe25bbaefe62915ac6f803b765230282breed@android.com 59de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com/////////////////////////////////////////////////////////////////////////////// 60de9ef40fffa82d1ace8f3736f1e50591915c05c6reed@android.com 6168779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com/* If we somehow returned the fact that we had to flip the pts in Y, we could 6268779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com communicate that to setQuadratic, and then avoid having to flip it back 6368779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com here (only to have setQuadratic do the flip again) 6468779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com */ 6568779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.combool SkQuadClipper::clipQuad(const SkPoint srcPts[3], SkPoint dst[3]) { 6668779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com bool reverse; 67935e9f4fafdfc64130e6be9ea2bb30e3bafd852armistry@google.com 6868779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // we need the data to be monotonically increasing in Y 6968779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com if (srcPts[0].fY > srcPts[2].fY) { 7068779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com dst[0] = srcPts[2]; 7168779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com dst[1] = srcPts[1]; 7268779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com dst[2] = srcPts[0]; 7368779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com reverse = true; 7468779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } else { 7568779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com memcpy(dst, srcPts, 3 * sizeof(SkPoint)); 7668779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com reverse = false; 7768779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 78935e9f4fafdfc64130e6be9ea2bb30e3bafd852armistry@google.com 7968779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // are we completely above or below 8068779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com const SkScalar ctop = fClip.fTop; 8168779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com const SkScalar cbot = fClip.fBottom; 8268779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com if (dst[2].fY <= ctop || dst[0].fY >= cbot) { 8368779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com return false; 8468779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 85935e9f4fafdfc64130e6be9ea2bb30e3bafd852armistry@google.com 8668779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com SkScalar t; 8768779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com SkPoint tmp[5]; // for SkChopQuadAt 88935e9f4fafdfc64130e6be9ea2bb30e3bafd852armistry@google.com 8968779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // are we partially above 9068779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com if (dst[0].fY < ctop) { 9168779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com if (chopMonoQuadAtY(dst, ctop, &t)) { 9268779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // take the 2nd chopped quad 9368779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com SkChopQuadAt(dst, tmp, t); 9468779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com dst[0] = tmp[2]; 9568779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com dst[1] = tmp[3]; 9668779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } else { 9768779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 9868779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // so we just clamp against the top 9968779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com for (int i = 0; i < 3; i++) { 10068779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com if (dst[i].fY < ctop) { 10168779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com dst[i].fY = ctop; 10268779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 10368779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 10468779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 10568779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 106935e9f4fafdfc64130e6be9ea2bb30e3bafd852armistry@google.com 10768779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // are we partially below 10868779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com if (dst[2].fY > cbot) { 10968779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com if (chopMonoQuadAtY(dst, cbot, &t)) { 11068779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com SkChopQuadAt(dst, tmp, t); 11168779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com dst[1] = tmp[1]; 11268779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com dst[2] = tmp[2]; 11368779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } else { 11468779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 11568779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com // so we just clamp against the bottom 11668779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com for (int i = 0; i < 3; i++) { 11768779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com if (dst[i].fY > cbot) { 11868779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com dst[i].fY = cbot; 11968779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 12068779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 12168779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 12268779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 123935e9f4fafdfc64130e6be9ea2bb30e3bafd852armistry@google.com 12468779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com if (reverse) { 12568779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com SkTSwap<SkPoint>(dst[0], dst[2]); 12668779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com } 12768779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com return true; 12868779c3e307771162ed2a55d2bfc9c63c807fc09reed@android.com} 129