1fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot/* 2fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * Copyright 2015 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 "SkPathOpsConic.h" 9fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkPathOpsCurve.h" 10fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkPathOpsLine.h" 11fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 12fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotclass LineConicIntersections { 13fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotpublic: 14fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot enum PinTPoint { 15fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot kPointUninitialized, 16fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot kPointInitialized 17fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot }; 18fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 19fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineConicIntersections(const SkDConic& c, const SkDLine& l, SkIntersections* i) 20fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot : fConic(c) 21fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot , fLine(&l) 22fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot , fIntersections(i) 23fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot , fAllowNear(true) { 24fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot i->setMax(4); // allow short partial coincidence plus discrete intersection 25fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 26fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 27fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineConicIntersections(const SkDConic& c) 28fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot : fConic(c) 29fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDEBUGPARAMS(fLine(nullptr)) 30fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDEBUGPARAMS(fIntersections(nullptr)) 31fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDEBUGPARAMS(fAllowNear(false)) { 32fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 33fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 34fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void allowNear(bool allow) { 35fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fAllowNear = allow; 36fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 37fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 38fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void checkCoincident() { 39fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int last = fIntersections->used() - 1; 40fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < last; ) { 41fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2; 42fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint conicMidPt = fConic.ptAtT(conicMidT); 43fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double t = fLine->nearPoint(conicMidPt, nullptr); 44fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (t < 0) { 45fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot ++index; 46fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 47fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 48fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->isCoincident(index)) { 49fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->removeOne(index); 50fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot --last; 51fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else if (fIntersections->isCoincident(index + 1)) { 52fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->removeOne(index + 1); 53fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot --last; 54fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else { 55fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->setCoincident(index++); 56fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 57fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->setCoincident(index); 58fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 59fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 60fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 61fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#ifdef SK_DEBUG 62fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot static bool close_to(double a, double b, const double c[3]) { 63fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double max = SkTMax(-SkTMin(SkTMin(c[0], c[1]), c[2]), SkTMax(SkTMax(c[0], c[1]), c[2])); 64fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return approximately_zero_when_compared_to(a - b, max); 65fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 66fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#endif 67fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int horizontalIntersect(double axisIntercept, double roots[2]) { 68fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }; 69fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return this->validT(conicVals, axisIntercept, roots); 70fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 71fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 72fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { 73fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addExactHorizontalEndPoints(left, right, axisIntercept); 74fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fAllowNear) { 75fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addNearHorizontalEndPoints(left, right, axisIntercept); 76fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 77fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double roots[2]; 78fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int count = this->horizontalIntersect(axisIntercept, roots); 79fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < count; ++index) { 80fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = roots[index]; 81fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint pt = fConic.ptAtT(conicT); 82fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDEBUGCODE(double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }); 83fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkOPOBJASSERT(fIntersections, close_to(pt.fY, axisIntercept, conicVals)); 84fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = (pt.fX - left) / (right - left); 85fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) 86fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot && this->uniqueAnswer(conicT, pt)) { 87fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, pt); 88fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 89fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 90fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (flipped) { 91fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->flip(); 92fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 93fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->checkCoincident(); 94fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fIntersections->used(); 95fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 96fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 97fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int intersect() { 98fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addExactEndPoints(); 99fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fAllowNear) { 100fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addNearEndPoints(); 101fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 102fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double rootVals[2]; 103fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int roots = this->intersectRay(rootVals); 104fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < roots; ++index) { 105fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = rootVals[index]; 106fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = this->findLineT(conicT); 107fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#ifdef SK_DEBUG 108fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!fIntersections->globalState() 109fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot || !fIntersections->globalState()->debugSkipAssert()) { 110fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDEBUGCODE(SkDPoint conicPt = fConic.ptAtT(conicT)); 111fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDEBUGCODE(SkDPoint linePt = fLine->ptAtT(lineT)); 112fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkASSERT(conicPt.approximatelyDEqual(linePt)); 113fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 114fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#endif 115fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint pt; 116fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (this->pinTs(&conicT, &lineT, &pt, kPointUninitialized) 117fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot && this->uniqueAnswer(conicT, pt)) { 118fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, pt); 119fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 120fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 121fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->checkCoincident(); 122fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fIntersections->used(); 123fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 124fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 125fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int intersectRay(double roots[2]) { 126fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double adj = (*fLine)[1].fX - (*fLine)[0].fX; 127fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double opp = (*fLine)[1].fY - (*fLine)[0].fY; 128fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double r[3]; 129fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int n = 0; n < 3; ++n) { 130fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot r[n] = (fConic[n].fY - (*fLine)[0].fY) * adj - (fConic[n].fX - (*fLine)[0].fX) * opp; 131fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 132fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return this->validT(r, 0, roots); 133fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 134fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 135fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int validT(double r[3], double axisIntercept, double roots[2]) { 136fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double A = r[2]; 137fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double B = r[1] * fConic.fWeight - axisIntercept * fConic.fWeight + axisIntercept; 138fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double C = r[0]; 139fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot A += C - 2 * B; // A = a + c - 2*(b*w - xCept*w + xCept) 140fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot B -= C; // B = b*w - w * xCept + xCept - a 141fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot C -= axisIntercept; 142fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return SkDQuad::RootsValidT(A, 2 * B, C, roots); 143fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 144fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 145fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int verticalIntersect(double axisIntercept, double roots[2]) { 146fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }; 147fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return this->validT(conicVals, axisIntercept, roots); 148fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 149fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 150fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { 151fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addExactVerticalEndPoints(top, bottom, axisIntercept); 152fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fAllowNear) { 153fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addNearVerticalEndPoints(top, bottom, axisIntercept); 154fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 155fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double roots[2]; 156fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int count = this->verticalIntersect(axisIntercept, roots); 157fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < count; ++index) { 158fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = roots[index]; 159fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint pt = fConic.ptAtT(conicT); 160fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDEBUGCODE(double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }); 161fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkOPOBJASSERT(fIntersections, close_to(pt.fX, axisIntercept, conicVals)); 162fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = (pt.fY - top) / (bottom - top); 163fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) 164fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot && this->uniqueAnswer(conicT, pt)) { 165fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, pt); 166fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 167fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 168fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (flipped) { 169fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->flip(); 170fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 171fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->checkCoincident(); 172fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fIntersections->used(); 173fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 174fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 175fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotprotected: 176fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// OPTIMIZE: Functions of the form add .. points are indentical to the conic routines. 177fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // add endpoints first to get zero and one t values exactly 178fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addExactEndPoints() { 179fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 180fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = fLine->exactPoint(fConic[cIndex]); 181fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 182fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 183fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 184fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = (double) (cIndex >> 1); 185fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, fConic[cIndex]); 186fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 187fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 188fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 189fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addNearEndPoints() { 190fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 191fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = (double) (cIndex >> 1); 192fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->hasT(conicT)) { 193fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 194fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 195fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = fLine->nearPoint(fConic[cIndex], nullptr); 196fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 197fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 198fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 199fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, fConic[cIndex]); 200fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 201fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addLineNearEndPoints(); 202fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 203fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 204fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addLineNearEndPoints() { 205fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int lIndex = 0; lIndex < 2; ++lIndex) { 206fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = (double) lIndex; 207fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->hasOppT(lineT)) { 208fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 209fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 210fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = ((SkDCurve*) &fConic)->nearPoint(SkPath::kConic_Verb, 211fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot (*fLine)[lIndex], (*fLine)[!lIndex]); 212fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (conicT < 0) { 213fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 214fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 215fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, (*fLine)[lIndex]); 216fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 217fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 218fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 219fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addExactHorizontalEndPoints(double left, double right, double y) { 220fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 221fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = SkDLine::ExactPointH(fConic[cIndex], left, right, y); 222fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 223fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 224fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 225fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = (double) (cIndex >> 1); 226fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, fConic[cIndex]); 227fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 228fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 229fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 230fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addNearHorizontalEndPoints(double left, double right, double y) { 231fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 232fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = (double) (cIndex >> 1); 233fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->hasT(conicT)) { 234fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 235fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 236fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = SkDLine::NearPointH(fConic[cIndex], left, right, y); 237fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 238fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 239fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 240fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, fConic[cIndex]); 241fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 242fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addLineNearEndPoints(); 243fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 244fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 245fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addExactVerticalEndPoints(double top, double bottom, double x) { 246fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 247fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = SkDLine::ExactPointV(fConic[cIndex], top, bottom, x); 248fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 249fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 250fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 251fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = (double) (cIndex >> 1); 252fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, fConic[cIndex]); 253fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 254fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 255fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 256fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void addNearVerticalEndPoints(double top, double bottom, double x) { 257fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 258fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicT = (double) (cIndex >> 1); 259fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->hasT(conicT)) { 260fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 261fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 262fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lineT = SkDLine::NearPointV(fConic[cIndex], top, bottom, x); 263fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lineT < 0) { 264fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 265fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 266fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fIntersections->insert(conicT, lineT, fConic[cIndex]); 267fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 268fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot this->addLineNearEndPoints(); 269fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 270fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 271fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double findLineT(double t) { 272fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint xy = fConic.ptAtT(t); 273fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dx = (*fLine)[1].fX - (*fLine)[0].fX; 274fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dy = (*fLine)[1].fY - (*fLine)[0].fY; 275fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fabs(dx) > fabs(dy)) { 276fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return (xy.fX - (*fLine)[0].fX) / dx; 277fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 278fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return (xy.fY - (*fLine)[0].fY) / dy; 279fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 280fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 281fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool pinTs(double* conicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { 282fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!approximately_one_or_less_double(*lineT)) { 283fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 284fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 285fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!approximately_zero_or_more_double(*lineT)) { 286fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 287fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 288fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double qT = *conicT = SkPinT(*conicT); 289fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double lT = *lineT = SkPinT(*lineT); 290fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) { 291fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *pt = (*fLine).ptAtT(lT); 292fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else if (ptSet == kPointUninitialized) { 293fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *pt = fConic.ptAtT(qT); 294fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 295fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkPoint gridPt = pt->asSkPoint(); 296fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[0].asSkPoint())) { 297fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *pt = (*fLine)[0]; 298fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *lineT = 0; 299fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[1].asSkPoint())) { 300fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *pt = (*fLine)[1]; 301fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *lineT = 1; 302fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 303fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) { 304fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 305fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 306fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (gridPt == fConic[0].asSkPoint()) { 307fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *pt = fConic[0]; 308fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *conicT = 0; 309fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } else if (gridPt == fConic[2].asSkPoint()) { 310fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *pt = fConic[2]; 311fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *conicT = 1; 312fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 313fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 314fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 315fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 316fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool uniqueAnswer(double conicT, const SkDPoint& pt) { 317fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int inner = 0; inner < fIntersections->used(); ++inner) { 318fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (fIntersections->pt(inner) != pt) { 319fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot continue; 320fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 321fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double existingConicT = (*fIntersections)[0][inner]; 322fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (conicT == existingConicT) { 323fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 324fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 325fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // check if midway on conic is also same point. If so, discard this 326fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double conicMidT = (existingConicT + conicT) / 2; 327fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint conicMidPt = fConic.ptAtT(conicMidT); 328fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (conicMidPt.approximatelyEqual(pt)) { 329fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 330fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 331fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 332fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#if ONE_OFF_DEBUG 333fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint qPt = fConic.ptAtT(conicT); 334fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, 335fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot qPt.fX, qPt.fY); 336fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#endif 337fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 338fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 339fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 340fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotprivate: 341fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot const SkDConic& fConic; 342fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot const SkDLine* fLine; 343fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkIntersections* fIntersections; 344fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool fAllowNear; 345fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot}; 346fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 347fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::horizontal(const SkDConic& conic, double left, double right, double y, 348fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool flipped) { 349fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDLine line = {{{ left, y }, { right, y }}}; 350fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineConicIntersections c(conic, line, this); 351fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return c.horizontalIntersect(y, left, right, flipped); 352fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 353fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 354fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::vertical(const SkDConic& conic, double top, double bottom, double x, 355fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool flipped) { 356fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDLine line = {{{ x, top }, { x, bottom }}}; 357fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineConicIntersections c(conic, line, this); 358fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return c.verticalIntersect(x, top, bottom, flipped); 359fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 360fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 361fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::intersect(const SkDConic& conic, const SkDLine& line) { 362fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineConicIntersections c(conic, line, this); 363fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot c.allowNear(fAllowNear); 364fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return c.intersect(); 365fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 366fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 367fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::intersectRay(const SkDConic& conic, const SkDLine& line) { 368fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineConicIntersections c(conic, line, this); 369fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fUsed = c.intersectRay(fT[0]); 370fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < fUsed; ++index) { 371fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fPt[index] = conic.ptAtT(fT[0][index]); 372fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 373fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fUsed; 374fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 375fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 376fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots) { 377fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineConicIntersections c(conic); 378fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return c.horizontalIntersect(y, roots); 379fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 380fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 381fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotint SkIntersections::VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots) { 382fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot LineConicIntersections c(conic); 383fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return c.verticalIntersect(x, roots); 384fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 385