LineQuadraticIntersections Class Reference

Public Types
enum	PinTPoint { kPointUninitialized , kPointInitialized }

Public Member Functions
	LineQuadraticIntersections (const SkDQuad &q, const SkDLine &l, SkIntersections *i)
	LineQuadraticIntersections (const SkDQuad &q)
void	allowNear (bool allow)
void	checkCoincident ()
int	intersectRay (double roots[2])
int	intersect ()
int	horizontalIntersect (double axisIntercept, double roots[2])
int	horizontalIntersect (double axisIntercept, double left, double right, bool flipped)
bool	uniqueAnswer (double quadT, const SkDPoint &pt)
int	verticalIntersect (double axisIntercept, double roots[2])
int	verticalIntersect (double axisIntercept, double top, double bottom, bool flipped)

Protected Member Functions
void	addExactEndPoints ()
void	addNearEndPoints ()
void	addLineNearEndPoints ()
void	addExactHorizontalEndPoints (double left, double right, double y)
void	addNearHorizontalEndPoints (double left, double right, double y)
void	addExactVerticalEndPoints (double top, double bottom, double x)
void	addNearVerticalEndPoints (double top, double bottom, double x)
double	findLineT (double t)
bool	pinTs (double *quadT, double *lineT, SkDPoint *pt, PinTPoint ptSet)

Detailed Description

Definition at line 98 of file SkDQuadLineIntersection.cpp.

Member Enumeration Documentation

PinTPoint

enum LineQuadraticIntersections::PinTPoint

Enumerator
kPointUninitialized
kPointInitialized

Definition at line 100 of file SkDQuadLineIntersection.cpp.

                   {
        kPointUninitialized,
        kPointInitialized
    };

Constructor & Destructor Documentation

LineQuadraticIntersections() [1/2]

LineQuadraticIntersections::LineQuadraticIntersections ( const SkDQuad &  q, const SkDLine &  l, SkIntersections *  i  )

inline

Definition at line 105 of file SkDQuadLineIntersection.cpp.

        : fQuad(q)
        , fLine(&l)
        , fIntersections(i)
        , fAllowNear(true) {
        i->setMax(5);  // allow short partial coincidence plus discrete intersections
    }

LineQuadraticIntersections() [2/2]

LineQuadraticIntersections::LineQuadraticIntersections ( const SkDQuad &  q )

inline

Definition at line 113 of file SkDQuadLineIntersection.cpp.

        : fQuad(q)
        SkDEBUGPARAMS(fLine(nullptr))
        SkDEBUGPARAMS(fIntersections(nullptr))
        SkDEBUGPARAMS(fAllowNear(false)) {
    }

Member Function Documentation

addExactEndPoints()

void LineQuadraticIntersections::addExactEndPoints ( )

inlineprotected

Definition at line 286 of file SkDQuadLineIntersection.cpp.

                             {
        for (int qIndex = 0; qIndex < 3; qIndex += 2) {
            double lineT = fLine->exactPoint(fQuad[qIndex]);
            if (lineT < 0) {
                continue;
            }
            double quadT = (double) (qIndex >> 1);
            fIntersections->insert(quadT, lineT, fQuad[qIndex]);
        }
    }

addExactHorizontalEndPoints()

void LineQuadraticIntersections::addExactHorizontalEndPoints ( double  left, double  right, double  y  )

inlineprotected

Definition at line 327 of file SkDQuadLineIntersection.cpp.

                                                                          {
        for (int qIndex = 0; qIndex < 3; qIndex += 2) {
            double lineT = SkDLine::ExactPointH(fQuad[qIndex], left, right, y);
            if (lineT < 0) {
                continue;
            }
            double quadT = (double) (qIndex >> 1);
            fIntersections->insert(quadT, lineT, fQuad[qIndex]);
        }
    }

addExactVerticalEndPoints()

void LineQuadraticIntersections::addExactVerticalEndPoints ( double  top, double  bottom, double  x  )

inlineprotected

Definition at line 353 of file SkDQuadLineIntersection.cpp.

                                                                        {
        for (int qIndex = 0; qIndex < 3; qIndex += 2) {
            double lineT = SkDLine::ExactPointV(fQuad[qIndex], top, bottom, x);
            if (lineT < 0) {
                continue;
            }
            double quadT = (double) (qIndex >> 1);
            fIntersections->insert(quadT, lineT, fQuad[qIndex]);
        }
    }

addLineNearEndPoints()

void LineQuadraticIntersections::addLineNearEndPoints ( )

inlineprotected

Definition at line 312 of file SkDQuadLineIntersection.cpp.

                                {
        for (int lIndex = 0; lIndex < 2; ++lIndex) {
            double lineT = (double) lIndex;
            if (fIntersections->hasOppT(lineT)) {
                continue;
            }
            double quadT = ((const SkDCurve*) &fQuad)->nearPoint(SkPath::kQuad_Verb,
                    (*fLine)[lIndex], (*fLine)[!lIndex]);
            if (quadT < 0) {
                continue;
            }
            fIntersections->insert(quadT, lineT, (*fLine)[lIndex]);
        }
    }

addNearEndPoints()

void LineQuadraticIntersections::addNearEndPoints ( )

inlineprotected

Definition at line 297 of file SkDQuadLineIntersection.cpp.

                            {
        for (int qIndex = 0; qIndex < 3; qIndex += 2) {
            double quadT = (double) (qIndex >> 1);
            if (fIntersections->hasT(quadT)) {
                continue;
            }
            double lineT = fLine->nearPoint(fQuad[qIndex], nullptr);
            if (lineT < 0) {
                continue;
            }
            fIntersections->insert(quadT, lineT, fQuad[qIndex]);
        }
        this->addLineNearEndPoints();
    }

addNearHorizontalEndPoints()

void LineQuadraticIntersections::addNearHorizontalEndPoints ( double  left, double  right, double  y  )

inlineprotected

Definition at line 338 of file SkDQuadLineIntersection.cpp.

                                                                         {
        for (int qIndex = 0; qIndex < 3; qIndex += 2) {
            double quadT = (double) (qIndex >> 1);
            if (fIntersections->hasT(quadT)) {
                continue;
            }
            double lineT = SkDLine::NearPointH(fQuad[qIndex], left, right, y);
            if (lineT < 0) {
                continue;
            }
            fIntersections->insert(quadT, lineT, fQuad[qIndex]);
        }
        this->addLineNearEndPoints();
    }

addNearVerticalEndPoints()

void LineQuadraticIntersections::addNearVerticalEndPoints ( double  top, double  bottom, double  x  )

inlineprotected

Definition at line 364 of file SkDQuadLineIntersection.cpp.

                                                                       {
        for (int qIndex = 0; qIndex < 3; qIndex += 2) {
            double quadT = (double) (qIndex >> 1);
            if (fIntersections->hasT(quadT)) {
                continue;
            }
            double lineT = SkDLine::NearPointV(fQuad[qIndex], top, bottom, x);
            if (lineT < 0) {
                continue;
            }
            fIntersections->insert(quadT, lineT, fQuad[qIndex]);
        }
        this->addLineNearEndPoints();
    }

allowNear()

void LineQuadraticIntersections::allowNear ( bool  allow )

inline

Definition at line 120 of file SkDQuadLineIntersection.cpp.

                               {
        fAllowNear = allow;
    }

checkCoincident()

void LineQuadraticIntersections::checkCoincident ( )

inline

Definition at line 124 of file SkDQuadLineIntersection.cpp.

                           {
        int last = fIntersections->used() - 1;
        for (int index = 0; index < last; ) {
            double quadMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2;
            SkDPoint quadMidPt = fQuad.ptAtT(quadMidT);
            double t = fLine->nearPoint(quadMidPt, 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);
        }
    }

findLineT()

double LineQuadraticIntersections::findLineT ( double  t )

inlineprotected

Definition at line 379 of file SkDQuadLineIntersection.cpp.

                               {
        SkDPoint xy = fQuad.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;
    }

horizontalIntersect() [1/2]

int LineQuadraticIntersections::horizontalIntersect ( double  axisIntercept, double  left, double  right, bool  flipped  )

inline

Definition at line 206 of file SkDQuadLineIntersection.cpp.

                                                                                           {
        addExactHorizontalEndPoints(left, right, axisIntercept);
        if (fAllowNear) {
            addNearHorizontalEndPoints(left, right, axisIntercept);
        }
        double rootVals[2];
        int roots = horizontalIntersect(axisIntercept, rootVals);
        for (int index = 0; index < roots; ++index) {
            double quadT = rootVals[index];
            SkDPoint pt = fQuad.ptAtT(quadT);
            double lineT = (pt.fX - left) / (right - left);
            if (pinTs(&quadT, &lineT, &pt, kPointInitialized) && uniqueAnswer(quadT, pt)) {
                fIntersections->insert(quadT, lineT, pt);
            }
        }
        if (flipped) {
            fIntersections->flip();
        }
        checkCoincident();
        return fIntersections->used();
    }

horizontalIntersect() [2/2]

int LineQuadraticIntersections::horizontalIntersect ( double  axisIntercept, double  roots[2]  )

inline

Definition at line 196 of file SkDQuadLineIntersection.cpp.

                                                                   {
        double D = fQuad[2].fY;  // f
        double E = fQuad[1].fY;  // e
        double F = fQuad[0].fY;  // d
        D += F - 2 * E;         // D = d - 2*e + f
        E -= F;                 // E = -(d - e)
        F -= axisIntercept;
        return SkDQuad::RootsValidT(D, 2 * E, F, roots);
    }

intersect()

int LineQuadraticIntersections::intersect ( )

inline

Definition at line 177 of file SkDQuadLineIntersection.cpp.

                    {
        addExactEndPoints();
        if (fAllowNear) {
            addNearEndPoints();
        }
        double rootVals[2];
        int roots = intersectRay(rootVals);
        for (int index = 0; index < roots; ++index) {
            double quadT = rootVals[index];
            double lineT = findLineT(quadT);
            SkDPoint pt;
            if (pinTs(&quadT, &lineT, &pt, kPointUninitialized) && uniqueAnswer(quadT, pt)) {
                fIntersections->insert(quadT, lineT, pt);
            }
        }
        checkCoincident();
        return fIntersections->used();
    }

intersectRay()

int LineQuadraticIntersections::intersectRay ( double  roots[2] )

inline

Definition at line 147 of file SkDQuadLineIntersection.cpp.

                                      {
    /*
        solve by rotating line+quad so line is horizontal, then finding the roots
        set up matrix to rotate quad to x-axis
        |cos(a) -sin(a)|
        |sin(a)  cos(a)|
        note that cos(a) = A(djacent) / Hypoteneuse
                  sin(a) = O(pposite) / Hypoteneuse
        since we are computing Ts, we can ignore hypoteneuse, the scale factor:
        |  A     -O    |
        |  O      A    |
        A = line[1].fX - line[0].fX (adjacent side of the right triangle)
        O = line[1].fY - line[0].fY (opposite side of the right triangle)
        for each of the three points (e.g. n = 0 to 2)
        quad[n].fY' = (quad[n].fY - line[0].fY) * A - (quad[n].fX - line[0].fX) * O
    */
        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] = (fQuad[n].fY - (*fLine)[0].fY) * adj - (fQuad[n].fX - (*fLine)[0].fX) * opp;
        }
        double A = r[2];
        double B = r[1];
        double C = r[0];
        A += C - 2 * B;  // A = a - 2*b + c
        B -= C;  // B = -(b - c)
        return SkDQuad::RootsValidT(A, 2 * B, C, roots);
    }

pinTs()

bool LineQuadraticIntersections::pinTs ( double *  quadT, double *  lineT, SkDPoint *  pt, PinTPoint  ptSet  )

inlineprotected

Definition at line 389 of file SkDQuadLineIntersection.cpp.

                                                                            {
        if (!approximately_one_or_less_double(*lineT)) {
            return false;
        }
        if (!approximately_zero_or_more_double(*lineT)) {
            return false;
        }
        double qT = *quadT = SkPinT(*quadT);
        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 = fQuad.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 == fQuad[0].asSkPoint()) {
            *pt = fQuad[0];
            *quadT = 0;
        } else if (gridPt == fQuad[2].asSkPoint()) {
            *pt = fQuad[2];
            *quadT = 1;
        }
        return true;
    }

uniqueAnswer()

bool LineQuadraticIntersections::uniqueAnswer ( double  quadT, const SkDPoint &  pt  )

inline

Definition at line 228 of file SkDQuadLineIntersection.cpp.

                                                        {
        for (int inner = 0; inner < fIntersections->used(); ++inner) {
            if (fIntersections->pt(inner) != pt) {
                continue;
            }
            double existingQuadT = (*fIntersections)[0][inner];
            if (quadT == existingQuadT) {
                return false;
            }
            // check if midway on quad is also same point. If so, discard this
            double quadMidT = (existingQuadT + quadT) / 2;
            SkDPoint quadMidPt = fQuad.ptAtT(quadMidT);
            if (quadMidPt.approximatelyEqual(pt)) {
                return false;
            }
        }
#if ONE_OFF_DEBUG
        SkDPoint qPt = fQuad.ptAtT(quadT);
        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;
    }

verticalIntersect() [1/2]

int LineQuadraticIntersections::verticalIntersect ( double  axisIntercept, double  roots[2]  )

inline

Definition at line 252 of file SkDQuadLineIntersection.cpp.

                                                                 {
        double D = fQuad[2].fX;  // f
        double E = fQuad[1].fX;  // e
        double F = fQuad[0].fX;  // d
        D += F - 2 * E;         // D = d - 2*e + f
        E -= F;                 // E = -(d - e)
        F -= axisIntercept;
        return SkDQuad::RootsValidT(D, 2 * E, F, roots);
    }

verticalIntersect() [2/2]

int LineQuadraticIntersections::verticalIntersect ( double  axisIntercept, double  top, double  bottom, bool  flipped  )

inline

Definition at line 262 of file SkDQuadLineIntersection.cpp.

                                                                                         {
        addExactVerticalEndPoints(top, bottom, axisIntercept);
        if (fAllowNear) {
            addNearVerticalEndPoints(top, bottom, axisIntercept);
        }
        double rootVals[2];
        int roots = verticalIntersect(axisIntercept, rootVals);
        for (int index = 0; index < roots; ++index) {
            double quadT = rootVals[index];
            SkDPoint pt = fQuad.ptAtT(quadT);
            double lineT = (pt.fY - top) / (bottom - top);
            if (pinTs(&quadT, &lineT, &pt, kPointInitialized) && uniqueAnswer(quadT, pt)) {
                fIntersections->insert(quadT, lineT, pt);
            }
        }
        if (flipped) {
            fIntersections->flip();
        }
        checkCoincident();
        return fIntersections->used();
    }

---

The documentation for this class was generated from the following file:

• third_party/skia/src/pathops/SkDQuadLineIntersection.cpp