diff options
Diffstat (limited to 'gfx/skia/skia/src/pathops/SkDConicLineIntersection.cpp')
| -rw-r--r-- | gfx/skia/skia/src/pathops/SkDConicLineIntersection.cpp | 396 |
1 files changed, 396 insertions, 0 deletions
diff --git a/gfx/skia/skia/src/pathops/SkDConicLineIntersection.cpp b/gfx/skia/skia/src/pathops/SkDConicLineIntersection.cpp new file mode 100644 index 0000000000..54c8178f7b --- /dev/null +++ b/gfx/skia/skia/src/pathops/SkDConicLineIntersection.cpp @@ -0,0 +1,396 @@ +/* + * Copyright 2015 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ +#include "include/core/SkPath.h" +#include "include/core/SkPoint.h" +#include "include/core/SkScalar.h" +#include "include/core/SkTypes.h" +#include "include/private/base/SkDebug.h" +#include "src/pathops/SkIntersections.h" +#include "src/pathops/SkPathOpsConic.h" +#include "src/pathops/SkPathOpsCurve.h" +#include "src/pathops/SkPathOpsDebug.h" +#include "src/pathops/SkPathOpsLine.h" +#include "src/pathops/SkPathOpsPoint.h" +#include "src/pathops/SkPathOpsQuad.h" +#include "src/pathops/SkPathOpsTypes.h" + +#include <algorithm> +#include <cmath> + +class LineConicIntersections { +public: + enum PinTPoint { + kPointUninitialized, + kPointInitialized + }; + + LineConicIntersections(const SkDConic& c, const SkDLine& l, SkIntersections* i) + : fConic(c) + , fLine(&l) + , fIntersections(i) + , fAllowNear(true) { + i->setMax(4); // allow short partial coincidence plus discrete intersection + } + + LineConicIntersections(const SkDConic& c) + : fConic(c) + SkDEBUGPARAMS(fLine(nullptr)) + SkDEBUGPARAMS(fIntersections(nullptr)) + SkDEBUGPARAMS(fAllowNear(false)) { + } + + void allowNear(bool allow) { + fAllowNear = allow; + } + + void checkCoincident() { + int last = fIntersections->used() - 1; + for (int index = 0; index < last; ) { + double conicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2; + SkDPoint conicMidPt = fConic.ptAtT(conicMidT); + double t = fLine->nearPoint(conicMidPt, nullptr); + if (t < 0) { + ++index; + continue; + } + if (fIntersections->isCoincident(index)) { + fIntersections->removeOne(index); + --last; + } else if (fIntersections->isCoincident(index + 1)) { + fIntersections->removeOne(index + 1); + --last; + } else { + fIntersections->setCoincident(index++); + } + fIntersections->setCoincident(index); + } + } + +#ifdef SK_DEBUG + static bool close_to(double a, double b, const double c[3]) { + double max = std::max(-std::min(std::min(c[0], c[1]), c[2]), std::max(std::max(c[0], c[1]), c[2])); + return approximately_zero_when_compared_to(a - b, max); + } +#endif + int horizontalIntersect(double axisIntercept, double roots[2]) { + double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }; + return this->validT(conicVals, axisIntercept, roots); + } + + int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { + this->addExactHorizontalEndPoints(left, right, axisIntercept); + if (fAllowNear) { + this->addNearHorizontalEndPoints(left, right, axisIntercept); + } + double roots[2]; + int count = this->horizontalIntersect(axisIntercept, roots); + for (int index = 0; index < count; ++index) { + double conicT = roots[index]; + SkDPoint pt = fConic.ptAtT(conicT); + SkDEBUGCODE(double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }); + SkOPOBJASSERT(fIntersections, close_to(pt.fY, axisIntercept, conicVals)); + double lineT = (pt.fX - left) / (right - left); + if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) + && this->uniqueAnswer(conicT, pt)) { + fIntersections->insert(conicT, lineT, pt); + } + } + if (flipped) { + fIntersections->flip(); + } + this->checkCoincident(); + return fIntersections->used(); + } + + int intersect() { + this->addExactEndPoints(); + if (fAllowNear) { + this->addNearEndPoints(); + } + double rootVals[2]; + int roots = this->intersectRay(rootVals); + for (int index = 0; index < roots; ++index) { + double conicT = rootVals[index]; + double lineT = this->findLineT(conicT); +#ifdef SK_DEBUG + if (!fIntersections->globalState() + || !fIntersections->globalState()->debugSkipAssert()) { + SkDEBUGCODE(SkDPoint conicPt = fConic.ptAtT(conicT)); + SkDEBUGCODE(SkDPoint linePt = fLine->ptAtT(lineT)); + SkASSERT(conicPt.approximatelyDEqual(linePt)); + } +#endif + SkDPoint pt; + if (this->pinTs(&conicT, &lineT, &pt, kPointUninitialized) + && this->uniqueAnswer(conicT, pt)) { + fIntersections->insert(conicT, lineT, pt); + } + } + this->checkCoincident(); + return fIntersections->used(); + } + + int intersectRay(double roots[2]) { + double adj = (*fLine)[1].fX - (*fLine)[0].fX; + double opp = (*fLine)[1].fY - (*fLine)[0].fY; + double r[3]; + for (int n = 0; n < 3; ++n) { + r[n] = (fConic[n].fY - (*fLine)[0].fY) * adj - (fConic[n].fX - (*fLine)[0].fX) * opp; + } + return this->validT(r, 0, roots); + } + + int validT(double r[3], double axisIntercept, double roots[2]) { + double A = r[2]; + double B = r[1] * fConic.fWeight - axisIntercept * fConic.fWeight + axisIntercept; + double C = r[0]; + A += C - 2 * B; // A = a + c - 2*(b*w - xCept*w + xCept) + B -= C; // B = b*w - w * xCept + xCept - a + C -= axisIntercept; + return SkDQuad::RootsValidT(A, 2 * B, C, roots); + } + + int verticalIntersect(double axisIntercept, double roots[2]) { + double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }; + return this->validT(conicVals, axisIntercept, roots); + } + + int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { + this->addExactVerticalEndPoints(top, bottom, axisIntercept); + if (fAllowNear) { + this->addNearVerticalEndPoints(top, bottom, axisIntercept); + } + double roots[2]; + int count = this->verticalIntersect(axisIntercept, roots); + for (int index = 0; index < count; ++index) { + double conicT = roots[index]; + SkDPoint pt = fConic.ptAtT(conicT); + SkDEBUGCODE(double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }); + SkOPOBJASSERT(fIntersections, close_to(pt.fX, axisIntercept, conicVals)); + double lineT = (pt.fY - top) / (bottom - top); + if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) + && this->uniqueAnswer(conicT, pt)) { + fIntersections->insert(conicT, lineT, pt); + } + } + if (flipped) { + fIntersections->flip(); + } + this->checkCoincident(); + return fIntersections->used(); + } + +protected: +// OPTIMIZE: Functions of the form add .. points are indentical to the conic routines. + // add endpoints first to get zero and one t values exactly + void addExactEndPoints() { + for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { + double lineT = fLine->exactPoint(fConic[cIndex]); + if (lineT < 0) { + continue; + } + double conicT = (double) (cIndex >> 1); + fIntersections->insert(conicT, lineT, fConic[cIndex]); + } + } + + void addNearEndPoints() { + for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { + double conicT = (double) (cIndex >> 1); + if (fIntersections->hasT(conicT)) { + continue; + } + double lineT = fLine->nearPoint(fConic[cIndex], nullptr); + if (lineT < 0) { + continue; + } + fIntersections->insert(conicT, lineT, fConic[cIndex]); + } + this->addLineNearEndPoints(); + } + + void addLineNearEndPoints() { + for (int lIndex = 0; lIndex < 2; ++lIndex) { + double lineT = (double) lIndex; + if (fIntersections->hasOppT(lineT)) { + continue; + } + double conicT = ((SkDCurve*) &fConic)->nearPoint(SkPath::kConic_Verb, + (*fLine)[lIndex], (*fLine)[!lIndex]); + if (conicT < 0) { + continue; + } + fIntersections->insert(conicT, lineT, (*fLine)[lIndex]); + } + } + + void addExactHorizontalEndPoints(double left, double right, double y) { + for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { + double lineT = SkDLine::ExactPointH(fConic[cIndex], left, right, y); + if (lineT < 0) { + continue; + } + double conicT = (double) (cIndex >> 1); + fIntersections->insert(conicT, lineT, fConic[cIndex]); + } + } + + void addNearHorizontalEndPoints(double left, double right, double y) { + for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { + double conicT = (double) (cIndex >> 1); + if (fIntersections->hasT(conicT)) { + continue; + } + double lineT = SkDLine::NearPointH(fConic[cIndex], left, right, y); + if (lineT < 0) { + continue; + } + fIntersections->insert(conicT, lineT, fConic[cIndex]); + } + this->addLineNearEndPoints(); + } + + void addExactVerticalEndPoints(double top, double bottom, double x) { + for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { + double lineT = SkDLine::ExactPointV(fConic[cIndex], top, bottom, x); + if (lineT < 0) { + continue; + } + double conicT = (double) (cIndex >> 1); + fIntersections->insert(conicT, lineT, fConic[cIndex]); + } + } + + void addNearVerticalEndPoints(double top, double bottom, double x) { + for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { + double conicT = (double) (cIndex >> 1); + if (fIntersections->hasT(conicT)) { + continue; + } + double lineT = SkDLine::NearPointV(fConic[cIndex], top, bottom, x); + if (lineT < 0) { + continue; + } + fIntersections->insert(conicT, lineT, fConic[cIndex]); + } + this->addLineNearEndPoints(); + } + + double findLineT(double t) { + SkDPoint xy = fConic.ptAtT(t); + double dx = (*fLine)[1].fX - (*fLine)[0].fX; + double dy = (*fLine)[1].fY - (*fLine)[0].fY; + if (fabs(dx) > fabs(dy)) { + return (xy.fX - (*fLine)[0].fX) / dx; + } + return (xy.fY - (*fLine)[0].fY) / dy; + } + + bool pinTs(double* conicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { + if (!approximately_one_or_less_double(*lineT)) { + return false; + } + if (!approximately_zero_or_more_double(*lineT)) { + return false; + } + double qT = *conicT = SkPinT(*conicT); + double lT = *lineT = SkPinT(*lineT); + if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) { + *pt = (*fLine).ptAtT(lT); + } else if (ptSet == kPointUninitialized) { + *pt = fConic.ptAtT(qT); + } + SkPoint gridPt = pt->asSkPoint(); + if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[0].asSkPoint())) { + *pt = (*fLine)[0]; + *lineT = 0; + } else if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[1].asSkPoint())) { + *pt = (*fLine)[1]; + *lineT = 1; + } + if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) { + return false; + } + if (gridPt == fConic[0].asSkPoint()) { + *pt = fConic[0]; + *conicT = 0; + } else if (gridPt == fConic[2].asSkPoint()) { + *pt = fConic[2]; + *conicT = 1; + } + return true; + } + + bool uniqueAnswer(double conicT, const SkDPoint& pt) { + for (int inner = 0; inner < fIntersections->used(); ++inner) { + if (fIntersections->pt(inner) != pt) { + continue; + } + double existingConicT = (*fIntersections)[0][inner]; + if (conicT == existingConicT) { + return false; + } + // check if midway on conic is also same point. If so, discard this + double conicMidT = (existingConicT + conicT) / 2; + SkDPoint conicMidPt = fConic.ptAtT(conicMidT); + if (conicMidPt.approximatelyEqual(pt)) { + return false; + } + } +#if ONE_OFF_DEBUG + SkDPoint qPt = fConic.ptAtT(conicT); + SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, + qPt.fX, qPt.fY); +#endif + return true; + } + +private: + const SkDConic& fConic; + const SkDLine* fLine; + SkIntersections* fIntersections; + bool fAllowNear; +}; + +int SkIntersections::horizontal(const SkDConic& conic, double left, double right, double y, + bool flipped) { + SkDLine line = {{{ left, y }, { right, y }}}; + LineConicIntersections c(conic, line, this); + return c.horizontalIntersect(y, left, right, flipped); +} + +int SkIntersections::vertical(const SkDConic& conic, double top, double bottom, double x, + bool flipped) { + SkDLine line = {{{ x, top }, { x, bottom }}}; + LineConicIntersections c(conic, line, this); + return c.verticalIntersect(x, top, bottom, flipped); +} + +int SkIntersections::intersect(const SkDConic& conic, const SkDLine& line) { + LineConicIntersections c(conic, line, this); + c.allowNear(fAllowNear); + return c.intersect(); +} + +int SkIntersections::intersectRay(const SkDConic& conic, const SkDLine& line) { + LineConicIntersections c(conic, line, this); + fUsed = c.intersectRay(fT[0]); + for (int index = 0; index < fUsed; ++index) { + fPt[index] = conic.ptAtT(fT[0][index]); + } + return fUsed; +} + +int SkIntersections::HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots) { + LineConicIntersections c(conic); + return c.horizontalIntersect(y, roots); +} + +int SkIntersections::VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots) { + LineConicIntersections c(conic); + return c.verticalIntersect(x, roots); +} |