19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Copyright 2009 The Android Open Source Project 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Use of this source code is governed by a BSD-style license that can be 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * found in the LICENSE file. 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "SkQuadClipper.h" 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "SkGeometry.h" 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectstatic inline void clamp_le(SkScalar& value, SkScalar max) { 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (value > max) { 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project value = max; 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1940e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapustatic inline void clamp_ge(SkScalar& value, SkScalar min) { 2040e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu if (value < min) { 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project value = min; 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 23039c68e75606e837cf021815a0210836724574adDianne Hackborn} 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectSkQuadClipper::SkQuadClipper() {} 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectvoid SkQuadClipper::setClip(const SkIRect& clip) { 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // conver to scalars, since that's where we'll see the points 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project fClip.set(clip); 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/////////////////////////////////////////////////////////////////////////////// 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectstatic bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2, 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project SkScalar target, SkScalar* t) { 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * We solve for t, using quadratic equation, hence we have to rearrange 3840e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu * our cooefficents to look like At^2 + Bt + C 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project SkScalar A = c0 - c1 - c1 + c2; 4123b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet SkScalar B = 2*(c1 - c0); 4223b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet SkScalar C = c0 - target; 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project SkScalar roots[2]; // we only expect one, but make room for 2 for safety 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int count = SkFindUnitQuadRoots(A, B, C, roots); 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (count) { 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *t = roots[0]; 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return true; 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return false; 5123b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet} 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectstatic bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { 5423b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t); 559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/////////////////////////////////////////////////////////////////////////////// 5823b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet 5923b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet/* If we somehow returned the fact that we had to flip the pts in Y, we could 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project communicate that to setQuadratic, and then avoid having to flip it back 6123b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet here (only to have setQuadratic do the flip again) 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectbool SkQuadClipper::clipQuad(const SkPoint srcPts[3], SkPoint dst[3]) { 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project bool reverse; 6523b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // we need the data to be monotonically increasing in Y 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (srcPts[0].fY > srcPts[2].fY) { 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project dst[0] = srcPts[2]; 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project dst[1] = srcPts[1]; 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project dst[2] = srcPts[0]; 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project reverse = true; 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project memcpy(dst, srcPts, 3 * sizeof(SkPoint)); 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project reverse = false; 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // are we completely above or below 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const SkScalar ctop = fClip.fTop; 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const SkScalar cbot = fClip.fBottom; 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (dst[2].fY <= ctop || dst[0].fY >= cbot) { 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return false; 8223b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet } 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project SkScalar t; 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project SkPoint tmp[5]; // for SkChopQuadAt 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 8723b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet // are we partially above 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (dst[0].fY < ctop) { 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (chopMonoQuadAtY(dst, ctop, &t)) { 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // take the 2nd chopped quad 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project SkChopQuadAt(dst, tmp, t); 9223b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet dst[0] = tmp[2]; 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project dst[1] = tmp[3]; 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // if chopMonoQuadAtY failed, then we may have hit inexact numerics 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // so we just clamp against the top 9723b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet for (int i = 0; i < 3; i++) { 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (dst[i].fY < ctop) { 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project dst[i].fY = ctop; 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 10223b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet } 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // are we partially below 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (dst[2].fY > cbot) { 10723b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet if (chopMonoQuadAtY(dst, cbot, &t)) { 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project SkChopQuadAt(dst, tmp, t); 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project dst[1] = tmp[1]; 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project dst[2] = tmp[2]; 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 11223b4faf69437b732d681d9bee5c9a84379d5ccadXavier Ducrohet // if chopMonoQuadAtY failed, then we may have hit inexact numerics 11340e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu // so we just clamp against the bottom 11440e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu for (int i = 0; i < 3; i++) { 11540e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu if (dst[i].fY > cbot) { 11640e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu dst[i].fY = cbot; 11740e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu } 11840e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu } 11940e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu } 12040e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu } 12140e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu 12240e472521a544f26cb6956995788f7c36fff1404Suchi Amalapurapu if (reverse) { 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project SkTSwap<SkPoint>(dst[0], dst[2]); 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return true; 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project