180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2009 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkQuadClipper.h" 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkGeometry.h" 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline void clamp_le(SkScalar& value, SkScalar max) { 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (value > max) { 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru value = max; 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline void clamp_ge(SkScalar& value, SkScalar min) { 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (value < min) { 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru value = min; 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkQuadClipper::SkQuadClipper() { 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fClip.setEmpty(); 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkQuadClipper::setClip(const SkIRect& clip) { 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // conver to scalars, since that's where we'll see the points 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fClip.set(clip); 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2, 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar target, SkScalar* t) { 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * We solve for t, using quadratic equation, hence we have to rearrange 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * our cooefficents to look like At^2 + Bt + C 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = c0 - c1 - c1 + c2; 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = 2*(c1 - c0); 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar C = c0 - target; 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar roots[2]; // we only expect one, but make room for 2 for safety 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = SkFindUnitQuadRoots(A, B, C, roots); 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count) { 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *t = roots[0]; 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t); 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* If we somehow returned the fact that we had to flip the pts in Y, we could 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru communicate that to setQuadratic, and then avoid having to flip it back 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru here (only to have setQuadratic do the flip again) 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querubool SkQuadClipper::clipQuad(const SkPoint srcPts[3], SkPoint dst[3]) { 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool reverse; 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // we need the data to be monotonically increasing in Y 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (srcPts[0].fY > srcPts[2].fY) { 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[0] = srcPts[2]; 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[1] = srcPts[1]; 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[2] = srcPts[0]; 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru reverse = true; 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(dst, srcPts, 3 * sizeof(SkPoint)); 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru reverse = false; 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we completely above or below 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const SkScalar ctop = fClip.fTop; 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const SkScalar cbot = fClip.fBottom; 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst[2].fY <= ctop || dst[0].fY >= cbot) { 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t; 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint tmp[5]; // for SkChopQuadAt 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially above 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst[0].fY < ctop) { 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoQuadAtY(dst, ctop, &t)) { 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // take the 2nd chopped quad 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(dst, tmp, t); 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[0] = tmp[2]; 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[1] = tmp[3]; 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonoQuadAtY failed, then we may have hit inexact numerics 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the top 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < 3; i++) { 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst[i].fY < ctop) { 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[i].fY = ctop; 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially below 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst[2].fY > cbot) { 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoQuadAtY(dst, cbot, &t)) { 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(dst, tmp, t); 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[1] = tmp[1]; 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[2] = tmp[2]; 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonoQuadAtY failed, then we may have hit inexact numerics 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the bottom 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < 3; i++) { 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst[i].fY > cbot) { 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[i].fY = cbot; 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (reverse) { 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap<SkPoint>(dst[0], dst[2]); 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 129