11cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger/* 31cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Copyright 2009 The Android Open Source Project 440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger * 51cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Use of this source code is governed by a BSD-style license that can be 61cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * found in the LICENSE file. 740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger */ 840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 91cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#include "SkCubicClipper.h" 1140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#include "SkGeometry.h" 1240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 1340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek SollenbergerSkCubicClipper::SkCubicClipper() {} 1440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 1540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergervoid SkCubicClipper::setClip(const SkIRect& clip) { 1640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // conver to scalars, since that's where we'll see the points 1740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger fClip.set(clip); 1840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 1940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 2040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 2140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerstatic bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) { 2240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar ycrv[4]; 2340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger ycrv[0] = pts[0].fY - y; 2440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger ycrv[1] = pts[1].fY - y; 2540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger ycrv[2] = pts[2].fY - y; 2640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger ycrv[3] = pts[3].fY - y; 2740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 2840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#ifdef NEWTON_RAPHSON // Quadratic convergence, typically <= 3 iterations. 2940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // Initial guess. 3040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // TODO(turk): Check for zero denominator? Shouldn't happen unless the curve 3140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // is not only monotonic but degenerate. 3240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#ifdef SK_SCALAR_IS_FLOAT 3340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar t1 = ycrv[0] / (ycrv[0] - ycrv[3]); 3440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#else // !SK_SCALAR_IS_FLOAT 3540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar t1 = SkDivBits(ycrv[0], ycrv[0] - ycrv[3], 16); 3640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#endif // !SK_SCALAR_IS_FLOAT 3740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 3840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // Newton's iterations. 3940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const SkScalar tol = SK_Scalar1 / 16384; // This leaves 2 fixed noise bits. 4040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar t0; 4140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const int maxiters = 5; 4240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int iters = 0; 4340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger bool converged; 4440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger do { 4540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger t0 = t1; 4640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], t0); 4740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], t0); 4840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], t0); 4940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y012 = SkScalarInterp(y01, y12, t0); 5040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y123 = SkScalarInterp(y12, y23, t0); 5140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y0123 = SkScalarInterp(y012, y123, t0); 5240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar yder = (y123 - y012) * 3; 5340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // TODO(turk): check for yder==0: horizontal. 5440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#ifdef SK_SCALAR_IS_FLOAT 5540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger t1 -= y0123 / yder; 5640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#else // !SK_SCALAR_IS_FLOAT 5740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger t1 -= SkDivBits(y0123, yder, 16); 5840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#endif // !SK_SCALAR_IS_FLOAT 5940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger converged = SkScalarAbs(t1 - t0) <= tol; // NaN-safe 6040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger ++iters; 6140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } while (!converged && (iters < maxiters)); 6240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *t = t1; // Return the result. 6340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 6440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // The result might be valid, even if outside of the range [0, 1], but 6540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // we never evaluate a Bezier outside this interval, so we return false. 6640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (t1 < 0 || t1 > SK_Scalar1) 6740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return false; // This shouldn't happen, but check anyway. 6840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return converged; 6940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 7040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#else // BISECTION // Linear convergence, typically 16 iterations. 7140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 7240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // Check that the endpoints straddle zero. 7340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar tNeg, tPos; // Negative and positive function parameters. 7440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (ycrv[0] < 0) { 7540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (ycrv[3] < 0) 7640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return false; 7740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger tNeg = 0; 7840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger tPos = SK_Scalar1; 7940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } else if (ycrv[0] > 0) { 8040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (ycrv[3] > 0) 8140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return false; 8240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger tNeg = SK_Scalar1; 8340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger tPos = 0; 8440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } else { 8540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *t = 0; 8640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return true; 8740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 8840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 8940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const SkScalar tol = SK_Scalar1 / 65536; // 1 for fixed, 1e-5 for float. 9040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int iters = 0; 9140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger do { 9240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar tMid = (tPos + tNeg) / 2; 9340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], tMid); 9440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], tMid); 9540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], tMid); 9640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y012 = SkScalarInterp(y01, y12, tMid); 9740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y123 = SkScalarInterp(y12, y23, tMid); 9840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar y0123 = SkScalarInterp(y012, y123, tMid); 9940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (y0123 == 0) { 10040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *t = tMid; 10140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return true; 10240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 10340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (y0123 < 0) tNeg = tMid; 10440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger else tPos = tMid; 10540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger ++iters; 10640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } while (!(SkScalarAbs(tPos - tNeg) <= tol)); // Nan-safe 10740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 10840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *t = (tNeg + tPos) / 2; 10940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return true; 11040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#endif // BISECTION 11140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 11240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 11340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 11440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerbool SkCubicClipper::clipCubic(const SkPoint srcPts[4], SkPoint dst[4]) { 11540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger bool reverse; 11640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 11740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // we need the data to be monotonically descending in Y 11840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (srcPts[0].fY > srcPts[3].fY) { 11940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[0] = srcPts[3]; 12040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[1] = srcPts[2]; 12140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[2] = srcPts[1]; 12240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[3] = srcPts[0]; 12340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger reverse = true; 12440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } else { 12540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger memcpy(dst, srcPts, 4 * sizeof(SkPoint)); 12640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger reverse = false; 12740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 12840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 12940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // are we completely above or below 13040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const SkScalar ctop = fClip.fTop; 13140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const SkScalar cbot = fClip.fBottom; 13240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (dst[3].fY <= ctop || dst[0].fY >= cbot) { 13340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return false; 13440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 13540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 13640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkScalar t; 13740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkPoint tmp[7]; // for SkChopCubicAt 13840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 13940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // are we partially above 14040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (dst[0].fY < ctop && chopMonoCubicAtY(dst, ctop, &t)) { 14140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkChopCubicAt(dst, tmp, t); 14240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[0] = tmp[3]; 14340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[1] = tmp[4]; 14440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[2] = tmp[5]; 14540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 14640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 14740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // are we partially below 14840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (dst[3].fY > cbot && chopMonoCubicAtY(dst, cbot, &t)) { 14940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkChopCubicAt(dst, tmp, t); 15040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[1] = tmp[1]; 15140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[2] = tmp[2]; 15240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst[3] = tmp[3]; 15340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 15440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 15540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (reverse) { 15640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkTSwap<SkPoint>(dst[0], dst[3]); 15740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkTSwap<SkPoint>(dst[1], dst[2]); 15840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 15940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return true; 16040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 16140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 162