OLD | NEW |
| (Empty) |
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.86520769
6, -0.865208078}}; | |
25 #endif | |
26 | |
27 #define DEBUG_QUAD_PART 0 | |
28 #define SWAP_TOP_DEBUG 0 | |
29 | |
30 static int quadPart(const Cubic& cubic, double tStart, double tEnd, Quadratic& s
imple) { | |
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, qu
ad[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 | |
59 static void intersectWithOrder(const Quadratic& simple1, int order1, const Quadr
atic& 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. | |
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-intersectio
n) | |
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 arbit
rary -- 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.de
pth()*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.9
g 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 + offs
et, 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__, to
1, to2, c1Min, c1Max, c2Min, c2Max); | |
179 #endif | |
180 intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offse
t, 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 c1Ma
x=%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, o
ffset, 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 c1Ma
x=%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, o
ffset, 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 + offs
et, offset); | |
286 SkDebugf("%s to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2M
in=%1.9g" | |
287 " c2Max=%1.9g\n", __FUNCTION__, to1, to2, c1Min, c1M
ax, c2Min, c2Max); | |
288 #endif | |
289 #endif | |
290 intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offse
t, i); | |
291 // TODO: if no intersection is found, either quadratics inte
rsected where | |
292 // cubics did not, or the intersection was missed. In the fo
rmer case, expect | |
293 // the quadratics to be nearly parallel at the point of inte
rsection, 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 cont
rol and opposite | |
313 // end to determine range of t on opposite cubic. | |
314 static bool intersectEnd(const Cubic& cubic1, bool start, const Cubic& cubic2, c
onst _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], tVal
s[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 | |
391 static bool closeStart(const Cubic& cubic, int cubicIndex, Intersections& i, _Po
int& 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 | |
399 static bool closeEnd(const Cubic& cubic, int cubicIndex, Intersections& i, _Poin
t& pt) { | |
400 int last = i.used() - 1; | |
401 if (i.fT[cubicIndex][last] != 1 || i.fT[cubicIndex][last - 1] < 1 - CLOSE_EN
OUGH) { | |
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 | |
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 v
alid. | |
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 | |
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 gradie
nt of the implicit | |
456 form dotted with the normal, and solving for the roots. My math foo is too poor
to implement this.*/ | |
457 | |
458 int intersect(const Cubic& c, Intersections& i) { | |
459 // check to see if x or y end points are the extrema. Are other quick reject
s 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 } | |
OLD | NEW |