1fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot/* 2fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * Copyright 2012 Google Inc. 3fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * 4fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * Use of this source code is governed by a BSD-style license that can be 5fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * found in the LICENSE file. 6fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot */ 7fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkIntersections.h" 8fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkPathOpsCubic.h" 9fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkPathOpsCurve.h" 10fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkPathOpsLine.h" 11fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 12fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot/* 13fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team RobotFind the interection of a line and cubic by solving for valid t values. 14fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 15fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team RobotAnalogous to line-quadratic intersection, solve line-cubic intersection by 16fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotrepresenting the cubic as: 17fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot x = a(1-t)^3 + 2b(1-t)^2t + c(1-t)t^2 + dt^3 18fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot y = e(1-t)^3 + 2f(1-t)^2t + g(1-t)t^2 + ht^3 19fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotand the line as: 20fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot y = i*x + j (if the line is more horizontal) 21fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotor: 22fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot x = i*y + j (if the line is more vertical) 23fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 24fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team RobotThen using Mathematica, solve for the values of t where the cubic intersects the 25fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotline: 26fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 27fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot (in) Resultant[ 28fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - x, 29fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - i*x - j, x] 30fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot (out) -e + j + 31fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 e t - 3 f t - 32fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 e t^2 + 6 f t^2 - 3 g t^2 + 33fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot e t^3 - 3 f t^3 + 3 g t^3 - h t^3 + 34fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot i ( a - 35fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 a t + 3 b t + 36fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 a t^2 - 6 b t^2 + 3 c t^2 - 37fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot a t^3 + 3 b t^3 - 3 c t^3 + d t^3 ) 38fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 39fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotif i goes to infinity, we can rewrite the line in terms of x. Mathematica: 40fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 41fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot (in) Resultant[ 42fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - i*y - j, 43fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y] 44fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot (out) a - j - 45fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 a t + 3 b t + 46fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 a t^2 - 6 b t^2 + 3 c t^2 - 47fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot a t^3 + 3 b t^3 - 3 c t^3 + d t^3 - 48fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot i ( e - 49fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 e t + 3 f t + 50fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 e t^2 - 6 f t^2 + 3 g t^2 - 51fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot e t^3 + 3 f t^3 - 3 g t^3 + h t^3 ) 52fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 53fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team RobotSolving this with Mathematica produces an expression with hundreds of terms; 54fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotinstead, use Numeric Solutions recipe to solve the cubic. 55fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 56fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team RobotThe near-horizontal case, in terms of: Ax^3 + Bx^2 + Cx + D == 0 57fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot A = (-(-e + 3*f - 3*g + h) + i*(-a + 3*b - 3*c + d) ) 58fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot B = 3*(-( e - 2*f + g ) + i*( a - 2*b + c ) ) 59fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot C = 3*(-(-e + f ) + i*(-a + b ) ) 60fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot D = (-( e ) + i*( a ) + j ) 61fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 62fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team RobotThe near-vertical case, in terms of: Ax^3 + Bx^2 + Cx + D == 0 63fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot A = ( (-a + 3*b - 3*c + d) - i*(-e + 3*f - 3*g + h) ) 64fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot B = 3*( ( a - 2*b + c ) - i*( e - 2*f + g ) ) 65fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot C = 3*( (-a + b ) - i*(-e + f ) ) 66fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot D = ( ( a ) - i*( e ) - j ) 67fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 68fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team RobotFor horizontal lines: 69fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot(in) Resultant[ 70fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - j, 71fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y] 72fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot(out) e - j - 73fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 e t + 3 f t + 74fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 3 e t^2 - 6 f t^2 + 3 g t^2 - 75fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot e t^3 + 3 f t^3 - 3 g t^3 + h t^3 76fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot */ 77fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 78fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotclass LineCubicIntersections { 79fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotpublic: 80fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot enum PinTPoint { 81fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot kPointUninitialized, 82fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot kPointInitialized 83fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot }; 84fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 85fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections* i) 86fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot : fCubic(c) 87fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot , fLine(l) 88fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot , fIntersections(i) 89fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot , fAllowNear(true) { 90fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot i->setMax(4); 91fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 92fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 93fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void allowNear(bool allow) { 94fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fAllowNear = allow; 95fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 96fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 97fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void checkCoincident() { 98fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int last = fIntersections->used() - 1; 99fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < last; ) { 100fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2; 101fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT); 102fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double t = fLine.nearPoint(cubicMidPt, nullptr); 103fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (t < 0) { 104fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot ++index; 105fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 106fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 107fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->isCoincident(index)) { 108fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->removeOne(index); 109fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot --last; 110fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else if (fIntersections->isCoincident(index + 1)) { 111fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->removeOne(index + 1); 112fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot --last; 113fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else { 114fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->setCoincident(index++); 115fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 116fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->setCoincident(index); 117fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 118fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 119fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 120fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // see parallel routine in line quadratic intersections 121fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int intersectRay(double roots[3]) { 122fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double adj = fLine[1].fX - fLine[0].fX; 123fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double opp = fLine[1].fY - fLine[0].fY; 124fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDCubic c; 125fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDEBUGCODE(c.fDebugGlobalState = fIntersections->globalState()); 126fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int n = 0; n < 4; ++n) { 127fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot c[n].fX = (fCubic[n].fY - fLine[0].fY) * adj - (fCubic[n].fX - fLine[0].fX) * opp; 128fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 129fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double A, B, C, D; 130fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDCubic::Coefficients(&c[0].fX, &A, &B, &C, &D); 131fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int count = SkDCubic::RootsValidT(A, B, C, D, roots); 132fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < count; ++index) { 133fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint calcPt = c.ptAtT(roots[index]); 134fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!approximately_zero(calcPt.fX)) { 135fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int n = 0; n < 4; ++n) { 136fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot c[n].fY = (fCubic[n].fY - fLine[0].fY) * opp 137fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot + (fCubic[n].fX - fLine[0].fX) * adj; 138fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 139fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double extremeTs[6]; 140fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int extrema = SkDCubic::FindExtrema(&c[0].fX, extremeTs); 141fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot count = c.searchRoots(extremeTs, extrema, 0, SkDCubic::kXAxis, roots); 142fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot break; 143fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 144fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 145fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return count; 146fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 147fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 148fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int intersect() { 149fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot addExactEndPoints(); 150fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fAllowNear) { 151fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot addNearEndPoints(); 152fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 153fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double rootVals[3]; 154fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int roots = intersectRay(rootVals); 155fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < roots; ++index) { 156fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = rootVals[index]; 157fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = findLineT(cubicT); 158fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint pt; 159fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (pinTs(&cubicT, &lineT, &pt, kPointUninitialized) && uniqueAnswer(cubicT, pt)) { 160fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, pt); 161fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 162fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 163fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot checkCoincident(); 164fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fIntersections->used(); 165fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 166fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 167fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot static int HorizontalIntersect(const SkDCubic& c, double axisIntercept, double roots[3]) { 168fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double A, B, C, D; 169fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDCubic::Coefficients(&c[0].fY, &A, &B, &C, &D); 170fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot D -= axisIntercept; 171fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int count = SkDCubic::RootsValidT(A, B, C, D, roots); 172fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < count; ++index) { 173fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint calcPt = c.ptAtT(roots[index]); 174fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!approximately_equal(calcPt.fY, axisIntercept)) { 175fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double extremeTs[6]; 176fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int extrema = SkDCubic::FindExtrema(&c[0].fY, extremeTs); 177fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot count = c.searchRoots(extremeTs, extrema, axisIntercept, SkDCubic::kYAxis, roots); 178fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot break; 179fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 180fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 181fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return count; 182fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 183fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 184fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { 185fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot addExactHorizontalEndPoints(left, right, axisIntercept); 186fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fAllowNear) { 187fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot addNearHorizontalEndPoints(left, right, axisIntercept); 188fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 189fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double roots[3]; 190fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int count = HorizontalIntersect(fCubic, axisIntercept, roots); 191fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < count; ++index) { 192fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = roots[index]; 193fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint pt = { fCubic.ptAtT(cubicT).fX, axisIntercept }; 194fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = (pt.fX - left) / (right - left); 195fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (pinTs(&cubicT, &lineT, &pt, kPointInitialized) && uniqueAnswer(cubicT, pt)) { 196fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, pt); 197fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 198fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 199fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (flipped) { 200fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->flip(); 201fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 202fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot checkCoincident(); 203fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fIntersections->used(); 204fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 205fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 206fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool uniqueAnswer(double cubicT, const SkDPoint& pt) { 207fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int inner = 0; inner < fIntersections->used(); ++inner) { 208fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->pt(inner) != pt) { 209fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 210fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 211fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double existingCubicT = (*fIntersections)[0][inner]; 212fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (cubicT == existingCubicT) { 213fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 214fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 215fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // check if midway on cubic is also same point. If so, discard this 216fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicMidT = (existingCubicT + cubicT) / 2; 217fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT); 218fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (cubicMidPt.approximatelyEqual(pt)) { 219fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 220fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 221fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 222fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#if ONE_OFF_DEBUG 223fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint cPt = fCubic.ptAtT(cubicT); 224fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, 225fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot cPt.fX, cPt.fY); 226fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#endif 227fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 228fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 229fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 230fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot static int VerticalIntersect(const SkDCubic& c, double axisIntercept, double roots[3]) { 231fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double A, B, C, D; 232fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDCubic::Coefficients(&c[0].fX, &A, &B, &C, &D); 233fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot D -= axisIntercept; 234fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int count = SkDCubic::RootsValidT(A, B, C, D, roots); 235fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < count; ++index) { 236fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint calcPt = c.ptAtT(roots[index]); 237fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!approximately_equal(calcPt.fX, axisIntercept)) { 238fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double extremeTs[6]; 239fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int extrema = SkDCubic::FindExtrema(&c[0].fX, extremeTs); 240fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot count = c.searchRoots(extremeTs, extrema, axisIntercept, SkDCubic::kXAxis, roots); 241fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot break; 242fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 243fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 244fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return count; 245fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 246fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 247fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { 248fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot addExactVerticalEndPoints(top, bottom, axisIntercept); 249fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fAllowNear) { 250fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot addNearVerticalEndPoints(top, bottom, axisIntercept); 251fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 252fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double roots[3]; 253fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int count = VerticalIntersect(fCubic, axisIntercept, roots); 254fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < count; ++index) { 255fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = roots[index]; 256fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint pt = { axisIntercept, fCubic.ptAtT(cubicT).fY }; 257fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = (pt.fY - top) / (bottom - top); 258fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (pinTs(&cubicT, &lineT, &pt, kPointInitialized) && uniqueAnswer(cubicT, pt)) { 259fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, pt); 260fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 261fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 262fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (flipped) { 263fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->flip(); 264fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 265fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot checkCoincident(); 266fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fIntersections->used(); 267fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 268fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 269fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot protected: 270fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 271fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addExactEndPoints() { 272fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < 4; cIndex += 3) { 273fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = fLine.exactPoint(fCubic[cIndex]); 274fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 275fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 276fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 277fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = (double) (cIndex >> 1); 278fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, fCubic[cIndex]); 279fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 280fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 281fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 282fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot /* Note that this does not look for endpoints of the line that are near the cubic. 283fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot These points are found later when check ends looks for missing points */ 284fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addNearEndPoints() { 285fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < 4; cIndex += 3) { 286fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = (double) (cIndex >> 1); 287fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->hasT(cubicT)) { 288fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 289fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 290fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = fLine.nearPoint(fCubic[cIndex], nullptr); 291fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 292fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 293fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 294fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, fCubic[cIndex]); 295fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 296fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addLineNearEndPoints(); 297fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 298fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 299fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addLineNearEndPoints() { 300fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int lIndex = 0; lIndex < 2; ++lIndex) { 301fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = (double) lIndex; 302fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->hasOppT(lineT)) { 303fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 304fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 305fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = ((SkDCurve*) &fCubic)->nearPoint(SkPath::kCubic_Verb, 306fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fLine[lIndex], fLine[!lIndex]); 307fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (cubicT < 0) { 308fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 309fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 310fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, fLine[lIndex]); 311fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 312fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 313fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 314fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addExactHorizontalEndPoints(double left, double right, double y) { 315fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < 4; cIndex += 3) { 316fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = SkDLine::ExactPointH(fCubic[cIndex], left, right, y); 317fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 318fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 319fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 320fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = (double) (cIndex >> 1); 321fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, fCubic[cIndex]); 322fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 323fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 324fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 325fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addNearHorizontalEndPoints(double left, double right, double y) { 326fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < 4; cIndex += 3) { 327fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = (double) (cIndex >> 1); 328fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->hasT(cubicT)) { 329fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 330fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 331fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = SkDLine::NearPointH(fCubic[cIndex], left, right, y); 332fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 333fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 334fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 335fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, fCubic[cIndex]); 336fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 337fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addLineNearEndPoints(); 338fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 339fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 340fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addExactVerticalEndPoints(double top, double bottom, double x) { 341fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < 4; cIndex += 3) { 342fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = SkDLine::ExactPointV(fCubic[cIndex], top, bottom, x); 343fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 344fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 345fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 346fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = (double) (cIndex >> 1); 347fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, fCubic[cIndex]); 348fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 349fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 350fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 351fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addNearVerticalEndPoints(double top, double bottom, double x) { 352fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < 4; cIndex += 3) { 353fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicT = (double) (cIndex >> 1); 354fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->hasT(cubicT)) { 355fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 356fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 357fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = SkDLine::NearPointV(fCubic[cIndex], top, bottom, x); 358fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 359fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 360fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 361fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(cubicT, lineT, fCubic[cIndex]); 362fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 363fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addLineNearEndPoints(); 364fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 365fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 366fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double findLineT(double t) { 367fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint xy = fCubic.ptAtT(t); 368fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dx = fLine[1].fX - fLine[0].fX; 369fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dy = fLine[1].fY - fLine[0].fY; 370fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fabs(dx) > fabs(dy)) { 371fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return (xy.fX - fLine[0].fX) / dx; 372fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 373fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return (xy.fY - fLine[0].fY) / dy; 374fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 375fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 376fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool pinTs(double* cubicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { 377fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!approximately_one_or_less(*lineT)) { 378fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 379fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 380fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!approximately_zero_or_more(*lineT)) { 381fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 382fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 383fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cT = *cubicT = SkPinT(*cubicT); 384fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lT = *lineT = SkPinT(*lineT); 385fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint lPt = fLine.ptAtT(lT); 386fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint cPt = fCubic.ptAtT(cT); 387fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!lPt.roughlyEqual(cPt)) { 388fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 389fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 390fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // FIXME: if points are roughly equal but not approximately equal, need to do 391fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // a binary search like quad/quad intersection to find more precise t values 392fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && cT != 0 && cT != 1)) { 393fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *pt = lPt; 394fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else if (ptSet == kPointUninitialized) { 395fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *pt = cPt; 396fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 397fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkPoint gridPt = pt->asSkPoint(); 398fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (gridPt == fLine[0].asSkPoint()) { 399fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *lineT = 0; 400fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else if (gridPt == fLine[1].asSkPoint()) { 401fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *lineT = 1; 402fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 403fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (gridPt == fCubic[0].asSkPoint() && approximately_equal(*cubicT, 0)) { 404fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *cubicT = 0; 405fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else if (gridPt == fCubic[3].asSkPoint() && approximately_equal(*cubicT, 1)) { 406fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *cubicT = 1; 407fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 408fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 409fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 410fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 411fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotprivate: 412fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot const SkDCubic& fCubic; 413fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot const SkDLine& fLine; 414fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkIntersections* fIntersections; 415fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool fAllowNear; 416fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot}; 417fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 418fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::horizontal(const SkDCubic& cubic, double left, double right, double y, 419fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool flipped) { 420fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDLine line = {{{ left, y }, { right, y }}}; 421fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineCubicIntersections c(cubic, line, this); 422fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return c.horizontalIntersect(y, left, right, flipped); 423fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 424fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 425fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::vertical(const SkDCubic& cubic, double top, double bottom, double x, 426fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool flipped) { 427fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDLine line = {{{ x, top }, { x, bottom }}}; 428fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineCubicIntersections c(cubic, line, this); 429fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return c.verticalIntersect(x, top, bottom, flipped); 430fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 431fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 432fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) { 433fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineCubicIntersections c(cubic, line, this); 434fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot c.allowNear(fAllowNear); 435fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return c.intersect(); 436fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 437fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 438fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::intersectRay(const SkDCubic& cubic, const SkDLine& line) { 439fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineCubicIntersections c(cubic, line, this); 440fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fUsed = c.intersectRay(fT[0]); 441fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < fUsed; ++index) { 442fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fPt[index] = cubic.ptAtT(fT[0][index]); 443fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 444fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fUsed; 445fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 446fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 447fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// SkDCubic accessors to Intersection utilities 448fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 449fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkDCubic::horizontalIntersect(double yIntercept, double roots[3]) const { 450fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return LineCubicIntersections::HorizontalIntersect(*this, yIntercept, roots); 451fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 452fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 453fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkDCubic::verticalIntersect(double xIntercept, double roots[3]) const { 454fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return LineCubicIntersections::VerticalIntersect(*this, xIntercept, roots); 455fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 456