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
8 #include "CubicUtilities.h"
9 #include "CurveIntersection.h"
10 #include "Intersections.h"
11 #include "IntersectionUtilities.h"
12 #include "LineIntersection.h"
13 #include "LineUtilities.h"
14 #include "QuadraticUtilities.h"
15 #include "TSearch.h"
16
17 #if 0
18 #undef ONE_OFF_DEBUG
19 #define ONE_OFF_DEBUG 0
20 #endif
21
22 #if ONE_OFF_DEBUG
23 static const double tLimits1[2][2] = {{0.36, 0.37}, {0.63, 0.64}};
24 static const double tLimits2[2][2] = {{-0.865211397, -0.865215212}, {-0.865207696, -0.865208078}};
25 #endif
26
27 #define DEBUG_QUAD_PART 0
28 #define SWAP_TOP_DEBUG 0
29
quadPart(const Cubic & cubic,double tStart,double tEnd,Quadratic & simple)30 static int quadPart(const Cubic& cubic, double tStart, double tEnd, Quadratic& simple) {
31 Cubic part;
32 sub_divide(cubic, tStart, tEnd, part);
33 Quadratic quad;
34 demote_cubic_to_quad(part, quad);
35 // FIXME: should reduceOrder be looser in this use case if quartic is going to blow up on an
36 // extremely shallow quadratic?
37 int order = reduceOrder(quad, simple, kReduceOrder_TreatAsFill);
38 #if DEBUG_QUAD_PART
39 SkDebugf("%s cubic=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g) t=(%1.17g,%1.17g)\n",
40 __FUNCTION__, cubic[0].x, cubic[0].y, cubic[1].x, cubic[1].y, cubic[2].x, cubic[2].y,
41 cubic[3].x, cubic[3].y, tStart, tEnd);
42 SkDebugf("%s part=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)"
43 " quad=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)\n", __FUNCTION__, part[0].x, part[0].y,
44 part[1].x, part[1].y, part[2].x, part[2].y, part[3].x, part[3].y, quad[0].x, quad[0].y,
45 quad[1].x, quad[1].y, quad[2].x, quad[2].y);
46 SkDebugf("%s simple=(%1.17g,%1.17g", __FUNCTION__, simple[0].x, simple[0].y);
47 if (order > 1) {
48 SkDebugf(" %1.17g,%1.17g", simple[1].x, simple[1].y);
49 }
50 if (order > 2) {
51 SkDebugf(" %1.17g,%1.17g", simple[2].x, simple[2].y);
52 }
53 SkDebugf(")\n");
54 SkASSERT(order < 4 && order > 0);
55 #endif
56 return order;
57 }
58
intersectWithOrder(const Quadratic & simple1,int order1,const Quadratic & simple2,int order2,Intersections & i)59 static void intersectWithOrder(const Quadratic& simple1, int order1, const Quadratic& simple2,
60 int order2, Intersections& i) {
61 if (order1 == 3 && order2 == 3) {
62 intersect2(simple1, simple2, i);
63 } else if (order1 <= 2 && order2 <= 2) {
64 intersect((const _Line&) simple1, (const _Line&) simple2, i);
65 } else if (order1 == 3 && order2 <= 2) {
66 intersect(simple1, (const _Line&) simple2, i);
67 } else {
68 SkASSERT(order1 <= 2 && order2 == 3);
69 intersect(simple2, (const _Line&) simple1, i);
70 for (int s = 0; s < i.fUsed; ++s) {
71 SkTSwap(i.fT[0][s], i.fT[1][s]);
72 }
73 }
74 }
75
76 // this flavor centers potential intersections recursively. In contrast, '2' may inadvertently
77 // chase intersections near quadratic ends, requiring odd hacks to find them.
intersect3(const Cubic & cubic1,double t1s,double t1e,const Cubic & cubic2,double t2s,double t2e,double precisionScale,Intersections & i)78 static bool intersect3(const Cubic& cubic1, double t1s, double t1e, const Cubic& cubic2,
79 double t2s, double t2e, double precisionScale, Intersections& i) {
80 i.upDepth();
81 bool result = false;
82 Cubic c1, c2;
83 sub_divide(cubic1, t1s, t1e, c1);
84 sub_divide(cubic2, t2s, t2e, c2);
85 SkTDArray<double> ts1;
86 // OPTIMIZE: if c1 == c2, call once (happens when detecting self-intersection)
87 cubic_to_quadratics(c1, calcPrecision(c1) * precisionScale, ts1);
88 SkTDArray<double> ts2;
89 cubic_to_quadratics(c2, calcPrecision(c2) * precisionScale, ts2);
90 double t1Start = t1s;
91 int ts1Count = ts1.count();
92 for (int i1 = 0; i1 <= ts1Count; ++i1) {
93 const double tEnd1 = i1 < ts1Count ? ts1[i1] : 1;
94 const double t1 = t1s + (t1e - t1s) * tEnd1;
95 Quadratic s1;
96 int o1 = quadPart(cubic1, t1Start, t1, s1);
97 double t2Start = t2s;
98 int ts2Count = ts2.count();
99 for (int i2 = 0; i2 <= ts2Count; ++i2) {
100 const double tEnd2 = i2 < ts2Count ? ts2[i2] : 1;
101 const double t2 = t2s + (t2e - t2s) * tEnd2;
102 if (cubic1 == cubic2 && t1Start >= t2Start) {
103 t2Start = t2;
104 continue;
105 }
106 Quadratic s2;
107 int o2 = quadPart(cubic2, t2Start, t2, s2);
108 #if ONE_OFF_DEBUG
109 char tab[] = " ";
110 if (tLimits1[0][0] >= t1Start && tLimits1[0][1] <= t1
111 && tLimits1[1][0] >= t2Start && tLimits1[1][1] <= t2) {
112 Cubic cSub1, cSub2;
113 sub_divide(cubic1, t1Start, t1, cSub1);
114 sub_divide(cubic2, t2Start, t2, cSub2);
115 SkDebugf("%.*s %s t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)", i.depth()*2, tab, __FUNCTION__,
116 t1Start, t1, t2Start, t2);
117 Intersections xlocals;
118 intersectWithOrder(s1, o1, s2, o2, xlocals);
119 SkDebugf(" xlocals.fUsed=%d\n", xlocals.used());
120 }
121 #endif
122 Intersections locals;
123 intersectWithOrder(s1, o1, s2, o2, locals);
124 double coStart[2] = { -1 };
125 _Point coPoint;
126 int tCount = locals.used();
127 for (int tIdx = 0; tIdx < tCount; ++tIdx) {
128 double to1 = t1Start + (t1 - t1Start) * locals.fT[0][tIdx];
129 double to2 = t2Start + (t2 - t2Start) * locals.fT[1][tIdx];
130 // if the computed t is not sufficiently precise, iterate
131 _Point p1 = xy_at_t(cubic1, to1);
132 _Point p2 = xy_at_t(cubic2, to2);
133 if (p1.approximatelyEqual(p2)) {
134 if (locals.fIsCoincident[0] & 1 << tIdx) {
135 if (coStart[0] < 0) {
136 coStart[0] = to1;
137 coStart[1] = to2;
138 coPoint = p1;
139 } else {
140 i.insertCoincidentPair(coStart[0], to1, coStart[1], to2, coPoint, p1);
141 coStart[0] = -1;
142 }
143 result = true;
144 } else if (cubic1 != cubic2 || !approximately_equal(to1, to2)) {
145 if (i.swapped()) { // FIXME: insert should respect swap
146 i.insert(to2, to1, p1);
147 } else {
148 i.insert(to1, to2, p1);
149 }
150 result = true;
151 }
152 } else {
153 double offset = precisionScale / 16; // FIME: const is arbitrary -- test & refine
154 #if 1
155 double c1Bottom = tIdx == 0 ? 0 :
156 (t1Start + (t1 - t1Start) * locals.fT[0][tIdx - 1] + to1) / 2;
157 double c1Min = SkTMax(c1Bottom, to1 - offset);
158 double c1Top = tIdx == tCount - 1 ? 1 :
159 (t1Start + (t1 - t1Start) * locals.fT[0][tIdx + 1] + to1) / 2;
160 double c1Max = SkTMin(c1Top, to1 + offset);
161 double c2Min = SkTMax(0., to2 - offset);
162 double c2Max = SkTMin(1., to2 + offset);
163 #if ONE_OFF_DEBUG
164 SkDebugf("%.*s %s 1 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab, __FUNCTION__,
165 c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max
166 && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max,
167 to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset
168 && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset,
169 c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max
170 && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max,
171 to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset
172 && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset);
173 SkDebugf("%.*s %s 1 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
174 " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
175 i.depth()*2, tab, __FUNCTION__, c1Bottom, c1Top, 0., 1.,
176 to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
177 SkDebugf("%.*s %s 1 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
178 " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min, c1Max, c2Min, c2Max);
179 #endif
180 intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
181 #if ONE_OFF_DEBUG
182 SkDebugf("%.*s %s 1 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__, i.used(),
183 i.used() > 0 ? i.fT[0][i.used() - 1] : -1);
184 #endif
185 if (tCount > 1) {
186 c1Min = SkTMax(0., to1 - offset);
187 c1Max = SkTMin(1., to1 + offset);
188 double c2Bottom = tIdx == 0 ? to2 :
189 (t2Start + (t2 - t2Start) * locals.fT[1][tIdx - 1] + to2) / 2;
190 double c2Top = tIdx == tCount - 1 ? to2 :
191 (t2Start + (t2 - t2Start) * locals.fT[1][tIdx + 1] + to2) / 2;
192 if (c2Bottom > c2Top) {
193 SkTSwap(c2Bottom, c2Top);
194 }
195 if (c2Bottom == to2) {
196 c2Bottom = 0;
197 }
198 if (c2Top == to2) {
199 c2Top = 1;
200 }
201 c2Min = SkTMax(c2Bottom, to2 - offset);
202 c2Max = SkTMin(c2Top, to2 + offset);
203 #if ONE_OFF_DEBUG
204 SkDebugf("%.*s %s 2 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab, __FUNCTION__,
205 c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max
206 && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max,
207 to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset
208 && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset,
209 c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max
210 && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max,
211 to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset
212 && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset);
213 SkDebugf("%.*s %s 2 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
214 " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
215 i.depth()*2, tab, __FUNCTION__, 0., 1., c2Bottom, c2Top,
216 to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
217 SkDebugf("%.*s %s 2 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
218 " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min, c1Max, c2Min, c2Max);
219 #endif
220 intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
221 #if ONE_OFF_DEBUG
222 SkDebugf("%.*s %s 2 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__, i.used(),
223 i.used() > 0 ? i.fT[0][i.used() - 1] : -1);
224 #endif
225 c1Min = SkTMax(c1Bottom, to1 - offset);
226 c1Max = SkTMin(c1Top, to1 + offset);
227 #if ONE_OFF_DEBUG
228 SkDebugf("%.*s %s 3 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab, __FUNCTION__,
229 c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max
230 && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max,
231 to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset
232 && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset,
233 c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max
234 && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max,
235 to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset
236 && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset);
237 SkDebugf("%.*s %s 3 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
238 " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
239 i.depth()*2, tab, __FUNCTION__, 0., 1., c2Bottom, c2Top,
240 to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
241 SkDebugf("%.*s %s 3 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
242 " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min, c1Max, c2Min, c2Max);
243 #endif
244 intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
245 #if ONE_OFF_DEBUG
246 SkDebugf("%.*s %s 3 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__, i.used(),
247 i.used() > 0 ? i.fT[0][i.used() - 1] : -1);
248 #endif
249 }
250 #else
251 double c1Bottom = tIdx == 0 ? 0 :
252 (t1Start + (t1 - t1Start) * locals.fT[0][tIdx - 1] + to1) / 2;
253 double c1Min = SkTMax(c1Bottom, to1 - offset);
254 double c1Top = tIdx == tCount - 1 ? 1 :
255 (t1Start + (t1 - t1Start) * locals.fT[0][tIdx + 1] + to1) / 2;
256 double c1Max = SkTMin(c1Top, to1 + offset);
257 double c2Bottom = tIdx == 0 ? to2 :
258 (t2Start + (t2 - t2Start) * locals.fT[1][tIdx - 1] + to2) / 2;
259 double c2Top = tIdx == tCount - 1 ? to2 :
260 (t2Start + (t2 - t2Start) * locals.fT[1][tIdx + 1] + to2) / 2;
261 if (c2Bottom > c2Top) {
262 SkTSwap(c2Bottom, c2Top);
263 }
264 if (c2Bottom == to2) {
265 c2Bottom = 0;
266 }
267 if (c2Top == to2) {
268 c2Top = 1;
269 }
270 double c2Min = SkTMax(c2Bottom, to2 - offset);
271 double c2Max = SkTMin(c2Top, to2 + offset);
272 #if ONE_OFF_DEBUG
273 SkDebugf("%s contains1=%d/%d contains2=%d/%d\n", __FUNCTION__,
274 c1Min <= 0.210357794 && 0.210357794 <= c1Max
275 && c2Min <= 0.223476406 && 0.223476406 <= c2Max,
276 to1 - offset <= 0.210357794 && 0.210357794 <= to1 + offset
277 && to2 - offset <= 0.223476406 && 0.223476406 <= to2 + offset,
278 c1Min <= 0.211324707 && 0.211324707 <= c1Max
279 && c2Min <= 0.211327209 && 0.211327209 <= c2Max,
280 to1 - offset <= 0.211324707 && 0.211324707 <= to1 + offset
281 && to2 - offset <= 0.211327209 && 0.211327209 <= to2 + offset);
282 SkDebugf("%s c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
283 " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
284 __FUNCTION__, c1Bottom, c1Top, c2Bottom, c2Top,
285 to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
286 SkDebugf("%s to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
287 " c2Max=%1.9g\n", __FUNCTION__, to1, to2, c1Min, c1Max, c2Min, c2Max);
288 #endif
289 #endif
290 intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
291 // TODO: if no intersection is found, either quadratics intersected where
292 // cubics did not, or the intersection was missed. In the former case, expect
293 // the quadratics to be nearly parallel at the point of intersection, and check
294 // for that.
295 }
296 }
297 SkASSERT(coStart[0] == -1);
298 t2Start = t2;
299 }
300 t1Start = t1;
301 }
302 i.downDepth();
303 return result;
304 }
305
306 #if 0
307 #define LINE_FRACTION (1.0 / gPrecisionUnit)
308 #else
309 #define LINE_FRACTION 0.1
310 #endif
311
312 // intersect the end of the cubic with the other. Try lines from the end to control and opposite
313 // end to determine range of t on opposite cubic.
intersectEnd(const Cubic & cubic1,bool start,const Cubic & cubic2,const _Rect & bounds2,Intersections & i)314 static bool intersectEnd(const Cubic& cubic1, bool start, const Cubic& cubic2, const _Rect& bounds2,
315 Intersections& i) {
316 // bool selfIntersect = cubic1 == cubic2;
317 _Line line;
318 int t1Index = start ? 0 : 3;
319 line[0] = cubic1[t1Index];
320 // don't bother if the two cubics are connnected
321 #if 0
322 if (!selfIntersect && (line[0].approximatelyEqual(cubic2[0])
323 || line[0].approximatelyEqual(cubic2[3]))) {
324 return false;
325 }
326 #endif
327 bool result = false;
328 SkTDArray<double> tVals; // OPTIMIZE: replace with hard-sized array
329 for (int index = 0; index < 4; ++index) {
330 if (index == t1Index) {
331 continue;
332 }
333 _Vector dxy1 = cubic1[index] - line[0];
334 dxy1 /= gPrecisionUnit;
335 line[1] = line[0] + dxy1;
336 _Rect lineBounds;
337 lineBounds.setBounds(line);
338 if (!bounds2.intersects(lineBounds)) {
339 continue;
340 }
341 Intersections local;
342 if (!intersect(cubic2, line, local)) {
343 continue;
344 }
345 for (int idx2 = 0; idx2 < local.used(); ++idx2) {
346 double foundT = local.fT[0][idx2];
347 if (approximately_less_than_zero(foundT)
348 || approximately_greater_than_one(foundT)) {
349 continue;
350 }
351 if (local.fPt[idx2].approximatelyEqual(line[0])) {
352 if (i.swapped()) { // FIXME: insert should respect swap
353 i.insert(foundT, start ? 0 : 1, line[0]);
354 } else {
355 i.insert(start ? 0 : 1, foundT, line[0]);
356 }
357 result = true;
358 } else {
359 *tVals.append() = local.fT[0][idx2];
360 }
361 }
362 }
363 if (tVals.count() == 0) {
364 return result;
365 }
366 QSort<double>(tVals.begin(), tVals.end() - 1);
367 double tMin1 = start ? 0 : 1 - LINE_FRACTION;
368 double tMax1 = start ? LINE_FRACTION : 1;
369 int tIdx = 0;
370 do {
371 int tLast = tIdx;
372 while (tLast + 1 < tVals.count() && roughly_equal(tVals[tLast + 1], tVals[tIdx])) {
373 ++tLast;
374 }
375 double tMin2 = SkTMax(tVals[tIdx] - LINE_FRACTION, 0.0);
376 double tMax2 = SkTMin(tVals[tLast] + LINE_FRACTION, 1.0);
377 int lastUsed = i.used();
378 result |= intersect3(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i);
379 if (lastUsed == i.used()) {
380 tMin2 = SkTMax(tVals[tIdx] - (1.0 / gPrecisionUnit), 0.0);
381 tMax2 = SkTMin(tVals[tLast] + (1.0 / gPrecisionUnit), 1.0);
382 result |= intersect3(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i);
383 }
384 tIdx = tLast + 1;
385 } while (tIdx < tVals.count());
386 return result;
387 }
388
389 const double CLOSE_ENOUGH = 0.001;
390
closeStart(const Cubic & cubic,int cubicIndex,Intersections & i,_Point & pt)391 static bool closeStart(const Cubic& cubic, int cubicIndex, Intersections& i, _Point& pt) {
392 if (i.fT[cubicIndex][0] != 0 || i.fT[cubicIndex][1] > CLOSE_ENOUGH) {
393 return false;
394 }
395 pt = xy_at_t(cubic, (i.fT[cubicIndex][0] + i.fT[cubicIndex][1]) / 2);
396 return true;
397 }
398
closeEnd(const Cubic & cubic,int cubicIndex,Intersections & i,_Point & pt)399 static bool closeEnd(const Cubic& cubic, int cubicIndex, Intersections& i, _Point& pt) {
400 int last = i.used() - 1;
401 if (i.fT[cubicIndex][last] != 1 || i.fT[cubicIndex][last - 1] < 1 - CLOSE_ENOUGH) {
402 return false;
403 }
404 pt = xy_at_t(cubic, (i.fT[cubicIndex][last] + i.fT[cubicIndex][last - 1]) / 2);
405 return true;
406 }
407
intersect3(const Cubic & c1,const Cubic & c2,Intersections & i)408 bool intersect3(const Cubic& c1, const Cubic& c2, Intersections& i) {
409 bool result = intersect3(c1, 0, 1, c2, 0, 1, 1, i);
410 // FIXME: pass in cached bounds from caller
411 _Rect c1Bounds, c2Bounds;
412 c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ?
413 c2Bounds.setBounds(c2);
414 result |= intersectEnd(c1, false, c2, c2Bounds, i);
415 result |= intersectEnd(c1, true, c2, c2Bounds, i);
416 bool selfIntersect = c1 == c2;
417 if (!selfIntersect) {
418 i.swap();
419 result |= intersectEnd(c2, false, c1, c1Bounds, i);
420 result |= intersectEnd(c2, true, c1, c1Bounds, i);
421 i.swap();
422 }
423 // If an end point and a second point very close to the end is returned, the second
424 // point may have been detected because the approximate quads
425 // intersected at the end and close to it. Verify that the second point is valid.
426 if (i.used() <= 1 || i.coincidentUsed()) {
427 return result;
428 }
429 _Point pt[2];
430 if (closeStart(c1, 0, i, pt[0]) && closeStart(c2, 1, i, pt[1])
431 && pt[0].approximatelyEqual(pt[1])) {
432 i.removeOne(1);
433 }
434 if (closeEnd(c1, 0, i, pt[0]) && closeEnd(c2, 1, i, pt[1])
435 && pt[0].approximatelyEqual(pt[1])) {
436 i.removeOne(i.used() - 2);
437 }
438 return result;
439 }
440
441 // Up promote the quad to a cubic.
442 // OPTIMIZATION If this is a common use case, optimize by duplicating
443 // the intersect 3 loop to avoid the promotion / demotion code
intersect(const Cubic & cubic,const Quadratic & quad,Intersections & i)444 int intersect(const Cubic& cubic, const Quadratic& quad, Intersections& i) {
445 Cubic up;
446 toCubic(quad, up);
447 (void) intersect3(cubic, up, i);
448 return i.used();
449 }
450
451 /* http://www.ag.jku.at/compass/compasssample.pdf
452 ( Self-Intersection Problems and Approximate Implicitization by Jan B. Thomassen
453 Centre of Mathematics for Applications, University of Oslo http://www.cma.uio.no janbth@math.uio.no
454 SINTEF Applied Mathematics http://www.sintef.no )
455 describes a method to find the self intersection of a cubic by taking the gradient of the implicit
456 form dotted with the normal, and solving for the roots. My math foo is too poor to implement this.*/
457
intersect(const Cubic & c,Intersections & i)458 int intersect(const Cubic& c, Intersections& i) {
459 // check to see if x or y end points are the extrema. Are other quick rejects possible?
460 if (ends_are_extrema_in_x_or_y(c)) {
461 return false;
462 }
463 (void) intersect3(c, c, i);
464 if (i.used() > 0) {
465 SkASSERT(i.used() == 1);
466 if (i.fT[0][0] > i.fT[1][0]) {
467 SkTSwap(i.fT[0][0], i.fT[1][0]);
468 }
469 }
470 return i.used();
471 }
472