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 
11 class LineConicIntersections {
12 public:
13     enum PinTPoint {
14         kPointUninitialized,
15         kPointInitialized
16     };
17 
LineConicIntersections(const SkDConic & c,const SkDLine & l,SkIntersections * i)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 
LineConicIntersections(const SkDConic & c)26     LineConicIntersections(const SkDConic& c)
27         : fConic(c)
28         SkDEBUGPARAMS(fLine(NULL))
29         SkDEBUGPARAMS(fIntersections(NULL))
30         SkDEBUGPARAMS(fAllowNear(false)) {
31     }
32 
allowNear(bool allow)33     void allowNear(bool allow) {
34         fAllowNear = allow;
35     }
36 
checkCoincident()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, NULL);
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
close_to(double a,double b,const double c[3])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
horizontalIntersect(double axisIntercept,double roots[2])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 
horizontalIntersect(double axisIntercept,double left,double right,bool flipped)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 
intersect()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 
intersectRay(double roots[2])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 
validT(double r[3],double axisIntercept,double roots[2])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 
verticalIntersect(double axisIntercept,double roots[2])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 
verticalIntersect(double axisIntercept,double top,double bottom,bool flipped)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 
169 protected:
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
addExactEndPoints()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 
addNearEndPoints()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], NULL);
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 
addExactHorizontalEndPoints(double left,double right,double y)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 
addNearHorizontalEndPoints(double left,double right,double y)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 
addExactVerticalEndPoints(double top,double bottom,double x)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 
addNearVerticalEndPoints(double top,double bottom,double x)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 
findLineT(double t)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 
pinTs(double * conicT,double * lineT,SkDPoint * pt,PinTPoint ptSet)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 
uniqueAnswer(double conicT,const SkDPoint & pt)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 
319 private:
320     const SkDConic& fConic;
321     const SkDLine* fLine;
322     SkIntersections* fIntersections;
323     bool fAllowNear;
324 };
325 
horizontal(const SkDConic & conic,double left,double right,double y,bool flipped)326 int 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 
vertical(const SkDConic & conic,double top,double bottom,double x,bool flipped)333 int 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 
intersect(const SkDConic & conic,const SkDLine & line)340 int SkIntersections::intersect(const SkDConic& conic, const SkDLine& line) {
341     LineConicIntersections c(conic, line, this);
342     c.allowNear(fAllowNear);
343     return c.intersect();
344 }
345 
intersectRay(const SkDConic & conic,const SkDLine & line)346 int 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 
HorizontalIntercept(const SkDConic & conic,SkScalar y,double * roots)355 int SkIntersections::HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots) {
356     LineConicIntersections c(conic);
357     return c.horizontalIntersect(y, roots);
358 }
359 
VerticalIntercept(const SkDConic & conic,SkScalar x,double * roots)360 int SkIntersections::VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots) {
361     LineConicIntersections c(conic);
362     return c.verticalIntersect(x, roots);
363 }
364