LineCubicIntersections Class Reference

Public Types
enum	PinTPoint { kPointUninitialized , kPointInitialized }

Public Member Functions
	LineCubicIntersections (const SkDCubic &c, const SkDLine &l, SkIntersections *i)
void	allowNear (bool allow)
void	checkCoincident ()
int	intersectRay (double roots[3])
int	intersect ()
int	horizontalIntersect (double axisIntercept, double left, double right, bool flipped)
bool	uniqueAnswer (double cubicT, const SkDPoint &pt)
int	verticalIntersect (double axisIntercept, double top, double bottom, bool flipped)

Static Public Member Functions
static int	HorizontalIntersect (const SkDCubic &c, double axisIntercept, double roots[3])
static int	VerticalIntersect (const SkDCubic &c, double axisIntercept, double roots[3])

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 *cubicT, double *lineT, SkDPoint *pt, PinTPoint ptSet)

Detailed Description

Definition at line 87 of file SkDCubicLineIntersection.cpp.

Member Enumeration Documentation

PinTPoint

enum LineCubicIntersections::PinTPoint

Enumerator
kPointUninitialized
kPointInitialized

Definition at line 89 of file SkDCubicLineIntersection.cpp.

                   {
        kPointUninitialized,
        kPointInitialized
    };

Constructor & Destructor Documentation

LineCubicIntersections()

LineCubicIntersections::LineCubicIntersections ( const SkDCubic &  c, const SkDLine &  l, SkIntersections *  i  )

inline

Definition at line 94 of file SkDCubicLineIntersection.cpp.

        : fCubic(c)
        , fLine(l)
        , fIntersections(i)
        , fAllowNear(true) {
        i->setMax(4);
    }

Member Function Documentation

addExactEndPoints()

void LineCubicIntersections::addExactEndPoints ( )

inlineprotected

Definition at line 280 of file SkDCubicLineIntersection.cpp.

                             {
        for (int cIndex = 0; cIndex < 4; cIndex += 3) {
            double lineT = fLine.exactPoint(fCubic[cIndex]);
            if (lineT < 0) {
                continue;
            }
            double cubicT = (double) (cIndex >> 1);
            fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
        }
    }

addExactHorizontalEndPoints()

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

inlineprotected

Definition at line 323 of file SkDCubicLineIntersection.cpp.

                                                                          {
        for (int cIndex = 0; cIndex < 4; cIndex += 3) {
            double lineT = SkDLine::ExactPointH(fCubic[cIndex], left, right, y);
            if (lineT < 0) {
                continue;
            }
            double cubicT = (double) (cIndex >> 1);
            fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
        }
    }

addExactVerticalEndPoints()

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

inlineprotected

Definition at line 349 of file SkDCubicLineIntersection.cpp.

                                                                        {
        for (int cIndex = 0; cIndex < 4; cIndex += 3) {
            double lineT = SkDLine::ExactPointV(fCubic[cIndex], top, bottom, x);
            if (lineT < 0) {
                continue;
            }
            double cubicT = (double) (cIndex >> 1);
            fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
        }
    }

addLineNearEndPoints()

void LineCubicIntersections::addLineNearEndPoints ( )

inlineprotected

Definition at line 308 of file SkDCubicLineIntersection.cpp.

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

addNearEndPoints()

void LineCubicIntersections::addNearEndPoints ( )

inlineprotected

Definition at line 293 of file SkDCubicLineIntersection.cpp.

                            {
        for (int cIndex = 0; cIndex < 4; cIndex += 3) {
            double cubicT = (double) (cIndex >> 1);
            if (fIntersections->hasT(cubicT)) {
                continue;
            }
            double lineT = fLine.nearPoint(fCubic[cIndex], nullptr);
            if (lineT < 0) {
                continue;
            }
            fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
        }
        this->addLineNearEndPoints();
    }

addNearHorizontalEndPoints()

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

inlineprotected

Definition at line 334 of file SkDCubicLineIntersection.cpp.

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

addNearVerticalEndPoints()

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

inlineprotected

Definition at line 360 of file SkDCubicLineIntersection.cpp.

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

allowNear()

void LineCubicIntersections::allowNear ( bool  allow )

inline

Definition at line 102 of file SkDCubicLineIntersection.cpp.

                               {
        fAllowNear = allow;
    }

checkCoincident()

void LineCubicIntersections::checkCoincident ( )

inline

Definition at line 106 of file SkDCubicLineIntersection.cpp.

                           {
        int last = fIntersections->used() - 1;
        for (int index = 0; index < last; ) {
            double cubicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2;
            SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT);
            double t = fLine.nearPoint(cubicMidPt, 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 LineCubicIntersections::findLineT ( double  t )

inlineprotected

Definition at line 375 of file SkDCubicLineIntersection.cpp.

                               {
        SkDPoint xy = fCubic.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()

static int LineCubicIntersections::HorizontalIntersect ( const SkDCubic &  c, double  axisIntercept, double  roots[3]  )

inlinestatic

Definition at line 176 of file SkDCubicLineIntersection.cpp.

                                                                                             {
        double A, B, C, D;
        SkDCubic::Coefficients(&c[0].fY, &A, &B, &C, &D);
        D -= axisIntercept;
        int count = SkDCubic::RootsValidT(A, B, C, D, roots);
        for (int index = 0; index < count; ++index) {
            SkDPoint calcPt = c.ptAtT(roots[index]);
            if (!approximately_equal(calcPt.fY, axisIntercept)) {
                double extremeTs[6];
                int extrema = SkDCubic::FindExtrema(&c[0].fY, extremeTs);
                count = c.searchRoots(extremeTs, extrema, axisIntercept, SkDCubic::kYAxis, roots);
                break;
            }
        }
        return count;
    }

horizontalIntersect()

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

inline

Definition at line 193 of file SkDCubicLineIntersection.cpp.

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

intersect()

int LineCubicIntersections::intersect ( )

inline

Definition at line 157 of file SkDCubicLineIntersection.cpp.

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

intersectRay()

int LineCubicIntersections::intersectRay ( double  roots[3] )

inline

Definition at line 130 of file SkDCubicLineIntersection.cpp.

                                      {
        double adj = fLine[1].fX - fLine[0].fX;
        double opp = fLine[1].fY - fLine[0].fY;
        SkDCubic c;
        SkDEBUGCODE(c.fDebugGlobalState = fIntersections->globalState());
        for (int n = 0; n < 4; ++n) {
            c[n].fX = (fCubic[n].fY - fLine[0].fY) * adj - (fCubic[n].fX - fLine[0].fX) * opp;
        }
        double A, B, C, D;
        SkDCubic::Coefficients(&c[0].fX, &A, &B, &C, &D);
        int count = SkDCubic::RootsValidT(A, B, C, D, roots);
        for (int index = 0; index < count; ++index) {
            SkDPoint calcPt = c.ptAtT(roots[index]);
            if (!approximately_zero(calcPt.fX)) {
                for (int n = 0; n < 4; ++n) {
                    c[n].fY = (fCubic[n].fY - fLine[0].fY) * opp
                            + (fCubic[n].fX - fLine[0].fX) * adj;
                }
                double extremeTs[6];
                int extrema = SkDCubic::FindExtrema(&c[0].fX, extremeTs);
                count = c.searchRoots(extremeTs, extrema, 0, SkDCubic::kXAxis, roots);
                break;
            }
        }
        return count;
    }

pinTs()

bool LineCubicIntersections::pinTs ( double *  cubicT, double *  lineT, SkDPoint *  pt, PinTPoint  ptSet  )

inlineprotected

Definition at line 385 of file SkDCubicLineIntersection.cpp.

                                                                             {
        if (!approximately_one_or_less(*lineT)) {
            return false;
        }
        if (!approximately_zero_or_more(*lineT)) {
            return false;
        }
        double cT = *cubicT = SkPinT(*cubicT);
        double lT = *lineT = SkPinT(*lineT);
        SkDPoint lPt = fLine.ptAtT(lT);
        SkDPoint cPt = fCubic.ptAtT(cT);
        if (!lPt.roughlyEqual(cPt)) {
            return false;
        }
        // FIXME: if points are roughly equal but not approximately equal, need to do
        // a binary search like quad/quad intersection to find more precise t values
        if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && cT != 0 && cT != 1)) {
            *pt = lPt;
        } else if (ptSet == kPointUninitialized) {
            *pt = cPt;
        }
        SkPoint gridPt = pt->asSkPoint();
        if (gridPt == fLine[0].asSkPoint()) {
            *lineT = 0;
        } else if (gridPt == fLine[1].asSkPoint()) {
            *lineT = 1;
        }
        if (gridPt == fCubic[0].asSkPoint() && approximately_equal(*cubicT, 0)) {
            *cubicT = 0;
        } else if (gridPt == fCubic[3].asSkPoint() && approximately_equal(*cubicT, 1)) {
            *cubicT = 1;
        }
        return true;
    }

uniqueAnswer()

bool LineCubicIntersections::uniqueAnswer ( double  cubicT, const SkDPoint &  pt  )

inline

Definition at line 215 of file SkDCubicLineIntersection.cpp.

                                                             {
            for (int inner = 0; inner < fIntersections->used(); ++inner) {
                if (fIntersections->pt(inner) != pt) {
                    continue;
                }
                double existingCubicT = (*fIntersections)[0][inner];
                if (cubicT == existingCubicT) {
                    return false;
                }
                // check if midway on cubic is also same point. If so, discard this
                double cubicMidT = (existingCubicT + cubicT) / 2;
                SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT);
                if (cubicMidPt.approximatelyEqual(pt)) {
                    return false;
                }
            }
#if ONE_OFF_DEBUG
            SkDPoint cPt = fCubic.ptAtT(cubicT);
            SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
                    cPt.fX, cPt.fY);
#endif
            return true;
        }

VerticalIntersect()

static int LineCubicIntersections::VerticalIntersect ( const SkDCubic &  c, double  axisIntercept, double  roots[3]  )

inlinestatic

Definition at line 239 of file SkDCubicLineIntersection.cpp.

                                                                                           {
        double A, B, C, D;
        SkDCubic::Coefficients(&c[0].fX, &A, &B, &C, &D);
        D -= axisIntercept;
        int count = SkDCubic::RootsValidT(A, B, C, D, roots);
        for (int index = 0; index < count; ++index) {
            SkDPoint calcPt = c.ptAtT(roots[index]);
            if (!approximately_equal(calcPt.fX, axisIntercept)) {
                double extremeTs[6];
                int extrema = SkDCubic::FindExtrema(&c[0].fX, extremeTs);
                count = c.searchRoots(extremeTs, extrema, axisIntercept, SkDCubic::kXAxis, roots);
                break;
            }
        }
        return count;
    }

verticalIntersect()

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

inline

Definition at line 256 of file SkDCubicLineIntersection.cpp.

                                                                                         {
        addExactVerticalEndPoints(top, bottom, axisIntercept);
        if (fAllowNear) {
            addNearVerticalEndPoints(top, bottom, axisIntercept);
        }
        double roots[3];
        int count = VerticalIntersect(fCubic, axisIntercept, roots);
        for (int index = 0; index < count; ++index) {
            double cubicT = roots[index];
            SkDPoint pt = { axisIntercept, fCubic.ptAtT(cubicT).fY };
            double lineT = (pt.fY - top) / (bottom - top);
            if (pinTs(&cubicT, &lineT, &pt, kPointInitialized) && uniqueAnswer(cubicT, pt)) {
                fIntersections->insert(cubicT, 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/SkDCubicLineIntersection.cpp