1112711afefcfcd43680c7c4aa8d38ef180e8811esewardj/* 2112711afefcfcd43680c7c4aa8d38ef180e8811esewardj * Copyright 2015 Google Inc. 3112711afefcfcd43680c7c4aa8d38ef180e8811esewardj * 4112711afefcfcd43680c7c4aa8d38ef180e8811esewardj * Use of this source code is governed by a BSD-style license that can be 5112711afefcfcd43680c7c4aa8d38ef180e8811esewardj * found in the LICENSE file. 6112711afefcfcd43680c7c4aa8d38ef180e8811esewardj */ 7112711afefcfcd43680c7c4aa8d38ef180e8811esewardj#include "SkIntersections.h" 8112711afefcfcd43680c7c4aa8d38ef180e8811esewardj#include "SkPathOpsConic.h" 9112711afefcfcd43680c7c4aa8d38ef180e8811esewardj#include "SkPathOpsLine.h" 10b3a1e4bffbdbbf38304f216af405009868f43628sewardj 11112711afefcfcd43680c7c4aa8d38ef180e8811esewardjclass LineConicIntersections { 12112711afefcfcd43680c7c4aa8d38ef180e8811esewardjpublic: 13112711afefcfcd43680c7c4aa8d38ef180e8811esewardj enum PinTPoint { 14112711afefcfcd43680c7c4aa8d38ef180e8811esewardj kPointUninitialized, 15112711afefcfcd43680c7c4aa8d38ef180e8811esewardj kPointInitialized 16112711afefcfcd43680c7c4aa8d38ef180e8811esewardj }; 17112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 18112711afefcfcd43680c7c4aa8d38ef180e8811esewardj LineConicIntersections(const SkDConic& c, const SkDLine& l, SkIntersections* i) 19112711afefcfcd43680c7c4aa8d38ef180e8811esewardj : fConic(c) 20112711afefcfcd43680c7c4aa8d38ef180e8811esewardj , fLine(&l) 21112711afefcfcd43680c7c4aa8d38ef180e8811esewardj , fIntersections(i) 22112711afefcfcd43680c7c4aa8d38ef180e8811esewardj , fAllowNear(true) { 23112711afefcfcd43680c7c4aa8d38ef180e8811esewardj i->setMax(3); // allow short partial coincidence plus discrete intersection 24112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 25112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 26112711afefcfcd43680c7c4aa8d38ef180e8811esewardj LineConicIntersections(const SkDConic& c) 27112711afefcfcd43680c7c4aa8d38ef180e8811esewardj : fConic(c) 28112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDEBUGPARAMS(fLine(nullptr)) 29112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDEBUGPARAMS(fIntersections(nullptr)) 30112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDEBUGPARAMS(fAllowNear(false)) { 31112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 32112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 33112711afefcfcd43680c7c4aa8d38ef180e8811esewardj void allowNear(bool allow) { 34112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fAllowNear = allow; 35112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 36112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 37112711afefcfcd43680c7c4aa8d38ef180e8811esewardj void checkCoincident() { 38112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int last = fIntersections->used() - 1; 39112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int index = 0; index < last; ) { 40112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2; 41112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDPoint conicMidPt = fConic.ptAtT(conicMidT); 42112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double t = fLine->nearPoint(conicMidPt, nullptr); 43112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (t < 0) { 44112711afefcfcd43680c7c4aa8d38ef180e8811esewardj ++index; 45112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 46112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 47112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fIntersections->isCoincident(index)) { 48112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->removeOne(index); 49112711afefcfcd43680c7c4aa8d38ef180e8811esewardj --last; 50112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } else if (fIntersections->isCoincident(index + 1)) { 51112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->removeOne(index + 1); 52112711afefcfcd43680c7c4aa8d38ef180e8811esewardj --last; 53112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } else { 54112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->setCoincident(index++); 55112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 56112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->setCoincident(index); 57112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 58112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 59112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 60112711afefcfcd43680c7c4aa8d38ef180e8811esewardj#ifdef SK_DEBUG 61112711afefcfcd43680c7c4aa8d38ef180e8811esewardj static bool close_to(double a, double b, const double c[3]) { 62112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double max = SkTMax(-SkTMin(SkTMin(c[0], c[1]), c[2]), SkTMax(SkTMax(c[0], c[1]), c[2])); 63112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return approximately_zero_when_compared_to(a - b, max); 64112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 65112711afefcfcd43680c7c4aa8d38ef180e8811esewardj#endif 66112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int horizontalIntersect(double axisIntercept, double roots[2]) { 67112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }; 68112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return this->validT(conicVals, axisIntercept, roots); 69112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 70112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 71112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { 72112711afefcfcd43680c7c4aa8d38ef180e8811esewardj this->addExactHorizontalEndPoints(left, right, axisIntercept); 73112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fAllowNear) { 74112711afefcfcd43680c7c4aa8d38ef180e8811esewardj this->addNearHorizontalEndPoints(left, right, axisIntercept); 75112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 76112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double roots[2]; 77112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int count = this->horizontalIntersect(axisIntercept, roots); 78112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int index = 0; index < count; ++index) { 79112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicT = roots[index]; 80112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDPoint pt = fConic.ptAtT(conicT); 81112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDEBUGCODE_(double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }); 82112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkASSERT(close_to(pt.fY, axisIntercept, conicVals)); 83112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lineT = (pt.fX - left) / (right - left); 84112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) 85112711afefcfcd43680c7c4aa8d38ef180e8811esewardj && this->uniqueAnswer(conicT, pt)) { 86112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->insert(conicT, lineT, pt); 87112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 88112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 89112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (flipped) { 90112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->flip(); 91112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 92112711afefcfcd43680c7c4aa8d38ef180e8811esewardj this->checkCoincident(); 93112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return fIntersections->used(); 94112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 95112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 96112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int intersect() { 97112711afefcfcd43680c7c4aa8d38ef180e8811esewardj this->addExactEndPoints(); 98112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fAllowNear) { 99112711afefcfcd43680c7c4aa8d38ef180e8811esewardj this->addNearEndPoints(); 100112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 101112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double rootVals[2]; 102112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int roots = this->intersectRay(rootVals); 103112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int index = 0; index < roots; ++index) { 104112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicT = rootVals[index]; 105112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lineT = this->findLineT(conicT); 106112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDEBUGCODE(SkDPoint conicPt = fConic.ptAtT(conicT)); 107112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDEBUGCODE(SkDPoint linePt = fLine->ptAtT(lineT)); 108112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkASSERT(conicPt.approximatelyEqual(linePt)); 109112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDPoint pt; 110112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (this->pinTs(&conicT, &lineT, &pt, kPointUninitialized) 111112711afefcfcd43680c7c4aa8d38ef180e8811esewardj && this->uniqueAnswer(conicT, pt)) { 112112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->insert(conicT, lineT, pt); 113112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 114112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 115112711afefcfcd43680c7c4aa8d38ef180e8811esewardj this->checkCoincident(); 116112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return fIntersections->used(); 117112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 118112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 119112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int intersectRay(double roots[2]) { 120112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double adj = (*fLine)[1].fX - (*fLine)[0].fX; 121112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double opp = (*fLine)[1].fY - (*fLine)[0].fY; 122112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double r[3]; 123112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int n = 0; n < 3; ++n) { 124112711afefcfcd43680c7c4aa8d38ef180e8811esewardj r[n] = (fConic[n].fY - (*fLine)[0].fY) * adj - (fConic[n].fX - (*fLine)[0].fX) * opp; 125112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 126112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return this->validT(r, 0, roots); 127112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 128112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 129112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int validT(double r[3], double axisIntercept, double roots[2]) { 130112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double A = r[2]; 131112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double B = r[1] * fConic.fWeight - axisIntercept * fConic.fWeight + axisIntercept; 132112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double C = r[0]; 133112711afefcfcd43680c7c4aa8d38ef180e8811esewardj A += C - 2 * B; // A = a + c - 2*(b*w - xCept*w + xCept) 134112711afefcfcd43680c7c4aa8d38ef180e8811esewardj B -= C; // B = b*w - w * xCept + xCept - a 135112711afefcfcd43680c7c4aa8d38ef180e8811esewardj C -= axisIntercept; 136112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return SkDQuad::RootsValidT(A, 2 * B, C, roots); 137112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 138112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 139112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int verticalIntersect(double axisIntercept, double roots[2]) { 140112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }; 141112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return this->validT(conicVals, axisIntercept, roots); 142112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 143112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 144112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { 145112711afefcfcd43680c7c4aa8d38ef180e8811esewardj this->addExactVerticalEndPoints(top, bottom, axisIntercept); 146112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fAllowNear) { 147112711afefcfcd43680c7c4aa8d38ef180e8811esewardj this->addNearVerticalEndPoints(top, bottom, axisIntercept); 148112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 149112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double roots[2]; 150112711afefcfcd43680c7c4aa8d38ef180e8811esewardj int count = this->verticalIntersect(axisIntercept, roots); 151112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int index = 0; index < count; ++index) { 152112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicT = roots[index]; 153112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDPoint pt = fConic.ptAtT(conicT); 154112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDEBUGCODE_(double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }); 155112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkASSERT(close_to(pt.fX, axisIntercept, conicVals)); 156112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lineT = (pt.fY - top) / (bottom - top); 157112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) 158112711afefcfcd43680c7c4aa8d38ef180e8811esewardj && this->uniqueAnswer(conicT, pt)) { 159112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->insert(conicT, lineT, pt); 160112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 161112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 162112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (flipped) { 163112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->flip(); 164112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 165112711afefcfcd43680c7c4aa8d38ef180e8811esewardj this->checkCoincident(); 166112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return fIntersections->used(); 167112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 168112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 169112711afefcfcd43680c7c4aa8d38ef180e8811esewardjprotected: 170112711afefcfcd43680c7c4aa8d38ef180e8811esewardj// OPTIMIZE: Functions of the form add .. points are indentical to the conic routines. 171112711afefcfcd43680c7c4aa8d38ef180e8811esewardj // add endpoints first to get zero and one t values exactly 172112711afefcfcd43680c7c4aa8d38ef180e8811esewardj void addExactEndPoints() { 173112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 174112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lineT = fLine->exactPoint(fConic[cIndex]); 175112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (lineT < 0) { 176112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 177112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 178112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicT = (double) (cIndex >> 1); 179112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->insert(conicT, lineT, fConic[cIndex]); 180112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 181112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 182112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 183112711afefcfcd43680c7c4aa8d38ef180e8811esewardj void addNearEndPoints() { 184112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 185112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicT = (double) (cIndex >> 1); 186112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fIntersections->hasT(conicT)) { 187112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 188112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 189112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lineT = fLine->nearPoint(fConic[cIndex], nullptr); 190112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (lineT < 0) { 191112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 192112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 193112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->insert(conicT, lineT, fConic[cIndex]); 194112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 195112711afefcfcd43680c7c4aa8d38ef180e8811esewardj // FIXME: see if line end is nearly on conic 196112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 197112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 198112711afefcfcd43680c7c4aa8d38ef180e8811esewardj void addExactHorizontalEndPoints(double left, double right, double y) { 199112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 200112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lineT = SkDLine::ExactPointH(fConic[cIndex], left, right, y); 201112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (lineT < 0) { 202112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 203112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 204112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicT = (double) (cIndex >> 1); 205112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->insert(conicT, lineT, fConic[cIndex]); 206112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 207112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 208112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 209112711afefcfcd43680c7c4aa8d38ef180e8811esewardj void addNearHorizontalEndPoints(double left, double right, double y) { 210112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 211112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicT = (double) (cIndex >> 1); 212112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fIntersections->hasT(conicT)) { 213112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 214112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 215112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lineT = SkDLine::NearPointH(fConic[cIndex], left, right, y); 216112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (lineT < 0) { 217112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 218112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 219112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->insert(conicT, lineT, fConic[cIndex]); 220112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 221112711afefcfcd43680c7c4aa8d38ef180e8811esewardj // FIXME: see if line end is nearly on conic 222112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 223112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 224112711afefcfcd43680c7c4aa8d38ef180e8811esewardj void addExactVerticalEndPoints(double top, double bottom, double x) { 225112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 226112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lineT = SkDLine::ExactPointV(fConic[cIndex], top, bottom, x); 227112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (lineT < 0) { 228112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 229112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 230112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicT = (double) (cIndex >> 1); 231112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->insert(conicT, lineT, fConic[cIndex]); 232112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 233112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 234112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 235112711afefcfcd43680c7c4aa8d38ef180e8811esewardj void addNearVerticalEndPoints(double top, double bottom, double x) { 236112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 237112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicT = (double) (cIndex >> 1); 238112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fIntersections->hasT(conicT)) { 239112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 240112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 241112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lineT = SkDLine::NearPointV(fConic[cIndex], top, bottom, x); 242112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (lineT < 0) { 243112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 244112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 245112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fIntersections->insert(conicT, lineT, fConic[cIndex]); 246112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 247112711afefcfcd43680c7c4aa8d38ef180e8811esewardj // FIXME: see if line end is nearly on conic 248112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 249112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 250112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double findLineT(double t) { 251112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDPoint xy = fConic.ptAtT(t); 252112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double dx = (*fLine)[1].fX - (*fLine)[0].fX; 253112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double dy = (*fLine)[1].fY - (*fLine)[0].fY; 254112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fabs(dx) > fabs(dy)) { 255112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return (xy.fX - (*fLine)[0].fX) / dx; 256112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 257112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return (xy.fY - (*fLine)[0].fY) / dy; 258112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 259112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 260112711afefcfcd43680c7c4aa8d38ef180e8811esewardj bool pinTs(double* conicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { 261112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (!approximately_one_or_less_double(*lineT)) { 262112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return false; 263112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 264112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (!approximately_zero_or_more_double(*lineT)) { 265112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return false; 266112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 267112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double qT = *conicT = SkPinT(*conicT); 268112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double lT = *lineT = SkPinT(*lineT); 269112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) { 270112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *pt = (*fLine).ptAtT(lT); 271112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } else if (ptSet == kPointUninitialized) { 272112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *pt = fConic.ptAtT(qT); 273112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 274112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkPoint gridPt = pt->asSkPoint(); 275112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[0].asSkPoint())) { 276112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *pt = (*fLine)[0]; 277112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *lineT = 0; 278112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } else if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[1].asSkPoint())) { 279112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *pt = (*fLine)[1]; 280112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *lineT = 1; 281112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 282112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) { 283112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return false; 284112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 285112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (gridPt == fConic[0].asSkPoint()) { 286112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *pt = fConic[0]; 287112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *conicT = 0; 288112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } else if (gridPt == fConic[2].asSkPoint()) { 289112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *pt = fConic[2]; 290112711afefcfcd43680c7c4aa8d38ef180e8811esewardj *conicT = 1; 291112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 292112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return true; 293112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 294112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 295112711afefcfcd43680c7c4aa8d38ef180e8811esewardj bool uniqueAnswer(double conicT, const SkDPoint& pt) { 296112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int inner = 0; inner < fIntersections->used(); ++inner) { 297112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (fIntersections->pt(inner) != pt) { 298112711afefcfcd43680c7c4aa8d38ef180e8811esewardj continue; 299112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 300112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double existingConicT = (*fIntersections)[0][inner]; 301112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (conicT == existingConicT) { 302112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return false; 303112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 304112711afefcfcd43680c7c4aa8d38ef180e8811esewardj // check if midway on conic is also same point. If so, discard this 305112711afefcfcd43680c7c4aa8d38ef180e8811esewardj double conicMidT = (existingConicT + conicT) / 2; 306112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDPoint conicMidPt = fConic.ptAtT(conicMidT); 307112711afefcfcd43680c7c4aa8d38ef180e8811esewardj if (conicMidPt.approximatelyEqual(pt)) { 308112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return false; 309112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 310112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 311112711afefcfcd43680c7c4aa8d38ef180e8811esewardj#if ONE_OFF_DEBUG 312112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDPoint qPt = fConic.ptAtT(conicT); 313112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, 314112711afefcfcd43680c7c4aa8d38ef180e8811esewardj qPt.fX, qPt.fY); 315112711afefcfcd43680c7c4aa8d38ef180e8811esewardj#endif 316112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return true; 317112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 318112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 319112711afefcfcd43680c7c4aa8d38ef180e8811esewardjprivate: 320112711afefcfcd43680c7c4aa8d38ef180e8811esewardj const SkDConic& fConic; 321112711afefcfcd43680c7c4aa8d38ef180e8811esewardj const SkDLine* fLine; 322112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkIntersections* fIntersections; 323112711afefcfcd43680c7c4aa8d38ef180e8811esewardj bool fAllowNear; 324112711afefcfcd43680c7c4aa8d38ef180e8811esewardj}; 325112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 326112711afefcfcd43680c7c4aa8d38ef180e8811esewardjint SkIntersections::horizontal(const SkDConic& conic, double left, double right, double y, 327112711afefcfcd43680c7c4aa8d38ef180e8811esewardj bool flipped) { 328112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDLine line = {{{ left, y }, { right, y }}}; 329112711afefcfcd43680c7c4aa8d38ef180e8811esewardj LineConicIntersections c(conic, line, this); 330112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return c.horizontalIntersect(y, left, right, flipped); 331112711afefcfcd43680c7c4aa8d38ef180e8811esewardj} 332112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 333112711afefcfcd43680c7c4aa8d38ef180e8811esewardjint SkIntersections::vertical(const SkDConic& conic, double top, double bottom, double x, 334112711afefcfcd43680c7c4aa8d38ef180e8811esewardj bool flipped) { 335112711afefcfcd43680c7c4aa8d38ef180e8811esewardj SkDLine line = {{{ x, top }, { x, bottom }}}; 336112711afefcfcd43680c7c4aa8d38ef180e8811esewardj LineConicIntersections c(conic, line, this); 337112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return c.verticalIntersect(x, top, bottom, flipped); 338112711afefcfcd43680c7c4aa8d38ef180e8811esewardj} 339112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 340112711afefcfcd43680c7c4aa8d38ef180e8811esewardjint SkIntersections::intersect(const SkDConic& conic, const SkDLine& line) { 341112711afefcfcd43680c7c4aa8d38ef180e8811esewardj LineConicIntersections c(conic, line, this); 342112711afefcfcd43680c7c4aa8d38ef180e8811esewardj c.allowNear(fAllowNear); 343112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return c.intersect(); 344112711afefcfcd43680c7c4aa8d38ef180e8811esewardj} 345112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 346112711afefcfcd43680c7c4aa8d38ef180e8811esewardjint SkIntersections::intersectRay(const SkDConic& conic, const SkDLine& line) { 347112711afefcfcd43680c7c4aa8d38ef180e8811esewardj LineConicIntersections c(conic, line, this); 348112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fUsed = c.intersectRay(fT[0]); 349112711afefcfcd43680c7c4aa8d38ef180e8811esewardj for (int index = 0; index < fUsed; ++index) { 350112711afefcfcd43680c7c4aa8d38ef180e8811esewardj fPt[index] = conic.ptAtT(fT[0][index]); 351112711afefcfcd43680c7c4aa8d38ef180e8811esewardj } 352112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return fUsed; 353112711afefcfcd43680c7c4aa8d38ef180e8811esewardj} 354112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 355112711afefcfcd43680c7c4aa8d38ef180e8811esewardjint SkIntersections::HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots) { 356112711afefcfcd43680c7c4aa8d38ef180e8811esewardj LineConicIntersections c(conic); 357112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return c.horizontalIntersect(y, roots); 358112711afefcfcd43680c7c4aa8d38ef180e8811esewardj} 359112711afefcfcd43680c7c4aa8d38ef180e8811esewardj 360112711afefcfcd43680c7c4aa8d38ef180e8811esewardjint SkIntersections::VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots) { 361112711afefcfcd43680c7c4aa8d38ef180e8811esewardj LineConicIntersections c(conic); 362112711afefcfcd43680c7c4aa8d38ef180e8811esewardj return c.verticalIntersect(x, roots); 363112711afefcfcd43680c7c4aa8d38ef180e8811esewardj} 364112711afefcfcd43680c7c4aa8d38ef180e8811esewardj