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