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