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 "src/pathops/SkIntersections.h"
8 #include "src/pathops/SkPathOpsConic.h"
9 #include "src/pathops/SkPathOpsCurve.h"
10 #include "src/pathops/SkPathOpsLine.h"
11 
12 class LineConicIntersections {
13 public:
14     enum PinTPoint {
15         kPointUninitialized,
16         kPointInitialized
17     };
18 
LineConicIntersections(const SkDConic & c,const SkDLine & l,SkIntersections * i)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 
LineConicIntersections(const SkDConic & c)27     LineConicIntersections(const SkDConic& c)
28         : fConic(c)
29         SkDEBUGPARAMS(fLine(nullptr))
30         SkDEBUGPARAMS(fIntersections(nullptr))
31         SkDEBUGPARAMS(fAllowNear(false)) {
32     }
33 
allowNear(bool allow)34     void allowNear(bool allow) {
35         fAllowNear = allow;
36     }
37 
checkCoincident()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
close_to(double a,double b,const double c[3])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
horizontalIntersect(double axisIntercept,double roots[2])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 
horizontalIntersect(double axisIntercept,double left,double right,bool flipped)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 
intersect()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 
intersectRay(double roots[2])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 
validT(double r[3],double axisIntercept,double roots[2])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 
verticalIntersect(double axisIntercept,double roots[2])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 
verticalIntersect(double axisIntercept,double top,double bottom,bool flipped)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 
175 protected:
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
addExactEndPoints()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 
addNearEndPoints()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 
addLineNearEndPoints()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 
addExactHorizontalEndPoints(double left,double right,double y)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 
addNearHorizontalEndPoints(double left,double right,double y)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 
addExactVerticalEndPoints(double top,double bottom,double x)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 
addNearVerticalEndPoints(double top,double bottom,double x)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 
findLineT(double t)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 
pinTs(double * conicT,double * lineT,SkDPoint * pt,PinTPoint ptSet)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 
uniqueAnswer(double conicT,const SkDPoint & pt)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 
340 private:
341     const SkDConic& fConic;
342     const SkDLine* fLine;
343     SkIntersections* fIntersections;
344     bool fAllowNear;
345 };
346 
horizontal(const SkDConic & conic,double left,double right,double y,bool flipped)347 int 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 
vertical(const SkDConic & conic,double top,double bottom,double x,bool flipped)354 int 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 
intersect(const SkDConic & conic,const SkDLine & line)361 int SkIntersections::intersect(const SkDConic& conic, const SkDLine& line) {
362     LineConicIntersections c(conic, line, this);
363     c.allowNear(fAllowNear);
364     return c.intersect();
365 }
366 
intersectRay(const SkDConic & conic,const SkDLine & line)367 int 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 
HorizontalIntercept(const SkDConic & conic,SkScalar y,double * roots)376 int SkIntersections::HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots) {
377     LineConicIntersections c(conic);
378     return c.horizontalIntersect(y, roots);
379 }
380 
VerticalIntercept(const SkDConic & conic,SkScalar x,double * roots)381 int SkIntersections::VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots) {
382     LineConicIntersections c(conic);
383     return c.verticalIntersect(x, roots);
384 }
385