1c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2009 The Android Open Source Project 3c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com */ 7c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com 8c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com#include "SkQuadClipper.h" 9c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com#include "SkGeometry.h" 10c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com 11a728e35edcffd99216e3965a4b908ad0df7f69c2vandebo@chromium.orgSkQuadClipper::SkQuadClipper() { 12a728e35edcffd99216e3965a4b908ad0df7f69c2vandebo@chromium.org fClip.setEmpty(); 13a728e35edcffd99216e3965a4b908ad0df7f69c2vandebo@chromium.org} 14bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com 15bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.comvoid SkQuadClipper::setClip(const SkIRect& clip) { 16bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // conver to scalars, since that's where we'll see the points 17bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com fClip.set(clip); 18bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com} 19bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com 20bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com/////////////////////////////////////////////////////////////////////////////// 21bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com 2277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.comstatic bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2, 2377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar target, SkScalar* t) { 24c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2 25c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com * We solve for t, using quadratic equation, hence we have to rearrange 26c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com * our cooefficents to look like At^2 + Bt + C 27c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com */ 2877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar A = c0 - c1 - c1 + c2; 2977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar B = 2*(c1 - c0); 3077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar C = c0 - target; 31fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 32c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com SkScalar roots[2]; // we only expect one, but make room for 2 for safety 33c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com int count = SkFindUnitQuadRoots(A, B, C, roots); 34c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com if (count) { 35c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com *t = roots[0]; 36c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com return true; 37c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com } 38c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com return false; 39c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com} 40c07d23a6e220c0aff36e3e4e06c1b685a440108ereed@android.com 4177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.comstatic bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { 4277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t); 4377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com} 4477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com 453a0cd7f0e80115a8cf525c9e0cf231df06d30a42reed@android.com/////////////////////////////////////////////////////////////////////////////// 463a0cd7f0e80115a8cf525c9e0cf231df06d30a42reed@android.com 47bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com/* If we somehow returned the fact that we had to flip the pts in Y, we could 48bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com communicate that to setQuadratic, and then avoid having to flip it back 49bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com here (only to have setQuadratic do the flip again) 50bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com */ 51bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.combool SkQuadClipper::clipQuad(const SkPoint srcPts[3], SkPoint dst[3]) { 52bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com bool reverse; 53fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 54bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // we need the data to be monotonically increasing in Y 55bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (srcPts[0].fY > srcPts[2].fY) { 56bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com dst[0] = srcPts[2]; 57bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com dst[1] = srcPts[1]; 58bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com dst[2] = srcPts[0]; 59bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com reverse = true; 60bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } else { 61bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com memcpy(dst, srcPts, 3 * sizeof(SkPoint)); 62bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com reverse = false; 63bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 64fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 65bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // are we completely above or below 66bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com const SkScalar ctop = fClip.fTop; 67bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com const SkScalar cbot = fClip.fBottom; 68bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst[2].fY <= ctop || dst[0].fY >= cbot) { 69bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com return false; 70bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 71fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 72bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkScalar t; 73bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkPoint tmp[5]; // for SkChopQuadAt 74fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 75bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // are we partially above 76bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst[0].fY < ctop) { 77bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (chopMonoQuadAtY(dst, ctop, &t)) { 78bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // take the 2nd chopped quad 79bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkChopQuadAt(dst, tmp, t); 80bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com dst[0] = tmp[2]; 81bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com dst[1] = tmp[3]; 82bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } else { 83bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 84bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // so we just clamp against the top 85bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com for (int i = 0; i < 3; i++) { 86bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst[i].fY < ctop) { 87bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com dst[i].fY = ctop; 88bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 89bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 90bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 91bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 92fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 93bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // are we partially below 94bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst[2].fY > cbot) { 95bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (chopMonoQuadAtY(dst, cbot, &t)) { 96bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkChopQuadAt(dst, tmp, t); 97bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com dst[1] = tmp[1]; 98bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com dst[2] = tmp[2]; 99bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } else { 100bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 101bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // so we just clamp against the bottom 102bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com for (int i = 0; i < 3; i++) { 103bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst[i].fY > cbot) { 104bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com dst[i].fY = cbot; 105bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 106bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 107bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 108bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 109fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 110bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (reverse) { 111bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkTSwap<SkPoint>(dst[0], dst[2]); 112bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 113bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com return true; 114bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com} 115