1 /*
2  * Copyright 2012 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 "SkPathOpsLine.h"
9 
cleanUpParallelLines(bool parallel)10 void SkIntersections::cleanUpParallelLines(bool parallel) {
11     while (fUsed > 2) {
12         removeOne(1);
13     }
14     if (fUsed == 2 && !parallel) {
15         bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1;
16         bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1;
17         if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1])) {
18             SkASSERT(startMatch || endMatch);
19             removeOne(endMatch);
20         }
21     }
22     if (fUsed == 2) {
23         fIsCoincident[0] = fIsCoincident[1] = 0x03;
24     }
25 }
26 
computePoints(const SkDLine & line,int used)27 void SkIntersections::computePoints(const SkDLine& line, int used) {
28     fPt[0] = line.ptAtT(fT[0][0]);
29     if ((fUsed = used) == 2) {
30         fPt[1] = line.ptAtT(fT[0][1]);
31     }
32 }
33 
intersectRay(const SkDLine & a,const SkDLine & b)34 int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
35     fMax = 2;
36     SkDVector aLen = a[1] - a[0];
37     SkDVector bLen = b[1] - b[0];
38     /* Slopes match when denom goes to zero:
39                       axLen / ayLen ==                   bxLen / byLen
40     (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
41              byLen  * axLen         ==  ayLen          * bxLen
42              byLen  * axLen         -   ayLen          * bxLen == 0 ( == denom )
43      */
44     double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX;
45     SkDVector ab0 = a[0] - b[0];
46     double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX;
47     double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX;
48     numerA /= denom;
49     numerB /= denom;
50     int used;
51     if (!approximately_zero(denom)) {
52         fT[0][0] = numerA;
53         fT[1][0] = numerB;
54         used = 1;
55     } else {
56        /* See if the axis intercepts match:
57                   ay - ax * ayLen / axLen  ==          by - bx * ayLen / axLen
58          axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
59          axLen *  ay - ax * ayLen          == axLen *  by - bx * ayLen
60         */
61         if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX,
62                 aLen.fX * b[0].fY - aLen.fY * b[0].fX)) {
63             return fUsed = 0;
64         }
65         // there's no great answer for intersection points for coincident rays, but return something
66         fT[0][0] = fT[1][0] = 0;
67         fT[1][0] = fT[1][1] = 1;
68         used = 2;
69     }
70     computePoints(a, used);
71     return fUsed;
72 }
73 
74 // note that this only works if both lines are neither horizontal nor vertical
intersect(const SkDLine & a,const SkDLine & b)75 int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
76     fMax = 3;  // note that we clean up so that there is no more than two in the end
77     // see if end points intersect the opposite line
78     double t;
79     for (int iA = 0; iA < 2; ++iA) {
80         if ((t = b.exactPoint(a[iA])) >= 0) {
81             insert(iA, t, a[iA]);
82         }
83     }
84     for (int iB = 0; iB < 2; ++iB) {
85         if ((t = a.exactPoint(b[iB])) >= 0) {
86             insert(t, iB, b[iB]);
87         }
88     }
89     /* Determine the intersection point of two line segments
90        Return FALSE if the lines don't intersect
91        from: http://paulbourke.net/geometry/lineline2d/ */
92     double axLen = a[1].fX - a[0].fX;
93     double ayLen = a[1].fY - a[0].fY;
94     double bxLen = b[1].fX - b[0].fX;
95     double byLen = b[1].fY - b[0].fY;
96     /* Slopes match when denom goes to zero:
97                       axLen / ayLen ==                   bxLen / byLen
98     (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
99              byLen  * axLen         ==  ayLen          * bxLen
100              byLen  * axLen         -   ayLen          * bxLen == 0 ( == denom )
101      */
102     double axByLen = axLen * byLen;
103     double ayBxLen = ayLen * bxLen;
104     // detect parallel lines the same way here and in SkOpAngle operator <
105     // so that non-parallel means they are also sortable
106     bool unparallel = fAllowNear ? NotAlmostEqualUlps(axByLen, ayBxLen)
107             : NotAlmostDequalUlps(axByLen, ayBxLen);
108     if (unparallel && fUsed == 0) {
109         double ab0y = a[0].fY - b[0].fY;
110         double ab0x = a[0].fX - b[0].fX;
111         double numerA = ab0y * bxLen - byLen * ab0x;
112         double numerB = ab0y * axLen - ayLen * ab0x;
113         double denom = axByLen - ayBxLen;
114         if (between(0, numerA, denom) && between(0, numerB, denom)) {
115             fT[0][0] = numerA / denom;
116             fT[1][0] = numerB / denom;
117             computePoints(a, 1);
118         }
119     }
120 /* Allow tracking that both sets of end points are near each other -- the lines are entirely
121    coincident -- even when the end points are not exactly the same.
122    Mark this as a 'wild card' for the end points, so that either point is considered totally
123    coincident. Then, avoid folding the lines over each other, but allow either end to mate
124    to the next set of lines.
125  */
126     if (fAllowNear || !unparallel) {
127         double aNearB[2];
128         double bNearA[2];
129         bool aNotB[2] = {false, false};
130         bool bNotA[2] = {false, false};
131         int nearCount = 0;
132         for (int index = 0; index < 2; ++index) {
133             aNearB[index] = t = b.nearPoint(a[index], &aNotB[index]);
134             nearCount += t >= 0;
135             bNearA[index] = t = a.nearPoint(b[index], &bNotA[index]);
136             nearCount += t >= 0;
137         }
138         if (nearCount > 0) {
139             // Skip if each segment contributes to one end point.
140             if (nearCount != 2 || aNotB[0] == aNotB[1]) {
141                 for (int iA = 0; iA < 2; ++iA) {
142                     if (!aNotB[iA]) {
143                         continue;
144                     }
145                     int nearer = aNearB[iA] > 0.5;
146                     if (!bNotA[nearer]) {
147                         continue;
148                     }
149                     SkASSERT(a[iA] != b[nearer]);
150                     SkASSERT(iA == (bNearA[nearer] > 0.5));
151                     insertNear(iA, nearer, a[iA], b[nearer]);
152                     aNearB[iA] = -1;
153                     bNearA[nearer] = -1;
154                     nearCount -= 2;
155                 }
156             }
157             if (nearCount > 0) {
158                 for (int iA = 0; iA < 2; ++iA) {
159                     if (aNearB[iA] >= 0) {
160                         insert(iA, aNearB[iA], a[iA]);
161                     }
162                 }
163                 for (int iB = 0; iB < 2; ++iB) {
164                     if (bNearA[iB] >= 0) {
165                         insert(bNearA[iB], iB, b[iB]);
166                     }
167                 }
168             }
169         }
170     }
171     cleanUpParallelLines(!unparallel);
172     SkASSERT(fUsed <= 2);
173     return fUsed;
174 }
175 
horizontal_coincident(const SkDLine & line,double y)176 static int horizontal_coincident(const SkDLine& line, double y) {
177     double min = line[0].fY;
178     double max = line[1].fY;
179     if (min > max) {
180         SkTSwap(min, max);
181     }
182     if (min > y || max < y) {
183         return 0;
184     }
185     if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) {
186         return 2;
187     }
188     return 1;
189 }
190 
HorizontalIntercept(const SkDLine & line,double y)191 double SkIntersections::HorizontalIntercept(const SkDLine& line, double y) {
192      return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY));
193 }
194 
horizontal(const SkDLine & line,double left,double right,double y,bool flipped)195 int SkIntersections::horizontal(const SkDLine& line, double left, double right,
196                                 double y, bool flipped) {
197     fMax = 3;  // clean up parallel at the end will limit the result to 2 at the most
198     // see if end points intersect the opposite line
199     double t;
200     const SkDPoint leftPt = { left, y };
201     if ((t = line.exactPoint(leftPt)) >= 0) {
202         insert(t, (double) flipped, leftPt);
203     }
204     if (left != right) {
205         const SkDPoint rightPt = { right, y };
206         if ((t = line.exactPoint(rightPt)) >= 0) {
207             insert(t, (double) !flipped, rightPt);
208         }
209         for (int index = 0; index < 2; ++index) {
210             if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) {
211                 insert((double) index, flipped ? 1 - t : t, line[index]);
212             }
213         }
214     }
215     int result = horizontal_coincident(line, y);
216     if (result == 1 && fUsed == 0) {
217         fT[0][0] = HorizontalIntercept(line, y);
218         double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
219         if (between(left, xIntercept, right)) {
220             fT[1][0] = (xIntercept - left) / (right - left);
221             if (flipped) {
222                 // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX
223                 for (int index = 0; index < result; ++index) {
224                     fT[1][index] = 1 - fT[1][index];
225                 }
226             }
227             fPt[0].fX = xIntercept;
228             fPt[0].fY = y;
229             fUsed = 1;
230         }
231     }
232     if (fAllowNear || result == 2) {
233         if ((t = line.nearPoint(leftPt, NULL)) >= 0) {
234             insert(t, (double) flipped, leftPt);
235         }
236         if (left != right) {
237             const SkDPoint rightPt = { right, y };
238             if ((t = line.nearPoint(rightPt, NULL)) >= 0) {
239                 insert(t, (double) !flipped, rightPt);
240             }
241             for (int index = 0; index < 2; ++index) {
242                 if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) {
243                     insert((double) index, flipped ? 1 - t : t, line[index]);
244                 }
245             }
246         }
247     }
248     cleanUpParallelLines(result == 2);
249     return fUsed;
250 }
251 
vertical_coincident(const SkDLine & line,double x)252 static int vertical_coincident(const SkDLine& line, double x) {
253     double min = line[0].fX;
254     double max = line[1].fX;
255     if (min > max) {
256         SkTSwap(min, max);
257     }
258     if (!precisely_between(min, x, max)) {
259         return 0;
260     }
261     if (AlmostEqualUlps(min, max)) {
262         return 2;
263     }
264     return 1;
265 }
266 
VerticalIntercept(const SkDLine & line,double x)267 double SkIntersections::VerticalIntercept(const SkDLine& line, double x) {
268     return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX));
269 }
270 
vertical(const SkDLine & line,double top,double bottom,double x,bool flipped)271 int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
272                               double x, bool flipped) {
273     fMax = 3;  // cleanup parallel lines will bring this back line
274     // see if end points intersect the opposite line
275     double t;
276     SkDPoint topPt = { x, top };
277     if ((t = line.exactPoint(topPt)) >= 0) {
278         insert(t, (double) flipped, topPt);
279     }
280     if (top != bottom) {
281         SkDPoint bottomPt = { x, bottom };
282         if ((t = line.exactPoint(bottomPt)) >= 0) {
283             insert(t, (double) !flipped, bottomPt);
284         }
285         for (int index = 0; index < 2; ++index) {
286             if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) {
287                 insert((double) index, flipped ? 1 - t : t, line[index]);
288             }
289         }
290     }
291     int result = vertical_coincident(line, x);
292     if (result == 1 && fUsed == 0) {
293         fT[0][0] = VerticalIntercept(line, x);
294         double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
295         if (between(top, yIntercept, bottom)) {
296             fT[1][0] = (yIntercept - top) / (bottom - top);
297             if (flipped) {
298                 // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY
299                 for (int index = 0; index < result; ++index) {
300                     fT[1][index] = 1 - fT[1][index];
301                 }
302             }
303             fPt[0].fX = x;
304             fPt[0].fY = yIntercept;
305             fUsed = 1;
306         }
307     }
308     if (fAllowNear || result == 2) {
309         if ((t = line.nearPoint(topPt, NULL)) >= 0) {
310             insert(t, (double) flipped, topPt);
311         }
312         if (top != bottom) {
313             SkDPoint bottomPt = { x, bottom };
314             if ((t = line.nearPoint(bottomPt, NULL)) >= 0) {
315                 insert(t, (double) !flipped, bottomPt);
316             }
317             for (int index = 0; index < 2; ++index) {
318                 if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) {
319                     insert((double) index, flipped ? 1 - t : t, line[index]);
320                 }
321             }
322         }
323     }
324     cleanUpParallelLines(result == 2);
325     SkASSERT(fUsed <= 2);
326     return fUsed;
327 }
328 
329