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