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