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 "SkIntersections.h"
9 #include "SkPathOpsCubic.h"
10 #include "SkPathOpsLine.h"
11 #include "SkPathOpsPoint.h"
12 #include "SkPathOpsQuad.h"
13 #include "SkPathOpsRect.h"
14 #include "SkReduceOrder.h"
15 #include "SkTSort.h"
16
17 #if ONE_OFF_DEBUG
18 static const double tLimits1[2][2] = {{0.3, 0.4}, {0.8, 0.9}};
19 static const double tLimits2[2][2] = {{-0.8, -0.9}, {-0.8, -0.9}};
20 #endif
21
22 #define DEBUG_QUAD_PART ONE_OFF_DEBUG && 1
23 #define DEBUG_QUAD_PART_SHOW_SIMPLE DEBUG_QUAD_PART && 0
24 #define SWAP_TOP_DEBUG 0
25
26 static const int kCubicToQuadSubdivisionDepth = 8; // slots reserved for cubic to quads subdivision
27
quadPart(const SkDCubic & cubic,double tStart,double tEnd,SkReduceOrder * reducer)28 static int quadPart(const SkDCubic& cubic, double tStart, double tEnd, SkReduceOrder* reducer) {
29 SkDCubic part = cubic.subDivide(tStart, tEnd);
30 SkDQuad quad = part.toQuad();
31 // FIXME: should reduceOrder be looser in this use case if quartic is going to blow up on an
32 // extremely shallow quadratic?
33 int order = reducer->reduce(quad);
34 #if DEBUG_QUAD_PART
35 SkDebugf("%s cubic=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
36 " t=(%1.9g,%1.9g)\n", __FUNCTION__, cubic[0].fX, cubic[0].fY,
37 cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY,
38 cubic[3].fX, cubic[3].fY, tStart, tEnd);
39 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n"
40 " {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
41 part[0].fX, part[0].fY, part[1].fX, part[1].fY, part[2].fX, part[2].fY,
42 part[3].fX, part[3].fY, quad[0].fX, quad[0].fY,
43 quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
44 #if DEBUG_QUAD_PART_SHOW_SIMPLE
45 SkDebugf("%s simple=(%1.9g,%1.9g", __FUNCTION__, reducer->fQuad[0].fX, reducer->fQuad[0].fY);
46 if (order > 1) {
47 SkDebugf(" %1.9g,%1.9g", reducer->fQuad[1].fX, reducer->fQuad[1].fY);
48 }
49 if (order > 2) {
50 SkDebugf(" %1.9g,%1.9g", reducer->fQuad[2].fX, reducer->fQuad[2].fY);
51 }
52 SkDebugf(")\n");
53 SkASSERT(order < 4 && order > 0);
54 #endif
55 #endif
56 return order;
57 }
58
intersectWithOrder(const SkDQuad & simple1,int order1,const SkDQuad & simple2,int order2,SkIntersections & i)59 static void intersectWithOrder(const SkDQuad& simple1, int order1, const SkDQuad& simple2,
60 int order2, SkIntersections& i) {
61 if (order1 == 3 && order2 == 3) {
62 i.intersect(simple1, simple2);
63 } else if (order1 <= 2 && order2 <= 2) {
64 i.intersect((const SkDLine&) simple1, (const SkDLine&) simple2);
65 } else if (order1 == 3 && order2 <= 2) {
66 i.intersect(simple1, (const SkDLine&) simple2);
67 } else {
68 SkASSERT(order1 <= 2 && order2 == 3);
69 i.intersect(simple2, (const SkDLine&) simple1);
70 i.swapPts();
71 }
72 }
73
74 // this flavor centers potential intersections recursively. In contrast, '2' may inadvertently
75 // chase intersections near quadratic ends, requiring odd hacks to find them.
intersect(const SkDCubic & cubic1,double t1s,double t1e,const SkDCubic & cubic2,double t2s,double t2e,double precisionScale,SkIntersections & i)76 static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDCubic& cubic2,
77 double t2s, double t2e, double precisionScale, SkIntersections& i) {
78 i.upDepth();
79 SkDCubic c1 = cubic1.subDivide(t1s, t1e);
80 SkDCubic c2 = cubic2.subDivide(t2s, t2e);
81 SkSTArray<kCubicToQuadSubdivisionDepth, double, true> ts1;
82 // OPTIMIZE: if c1 == c2, call once (happens when detecting self-intersection)
83 c1.toQuadraticTs(c1.calcPrecision() * precisionScale, &ts1);
84 SkSTArray<kCubicToQuadSubdivisionDepth, double, true> ts2;
85 c2.toQuadraticTs(c2.calcPrecision() * precisionScale, &ts2);
86 double t1Start = t1s;
87 int ts1Count = ts1.count();
88 for (int i1 = 0; i1 <= ts1Count; ++i1) {
89 const double tEnd1 = i1 < ts1Count ? ts1[i1] : 1;
90 const double t1 = t1s + (t1e - t1s) * tEnd1;
91 SkReduceOrder s1;
92 int o1 = quadPart(cubic1, t1Start, t1, &s1);
93 double t2Start = t2s;
94 int ts2Count = ts2.count();
95 for (int i2 = 0; i2 <= ts2Count; ++i2) {
96 const double tEnd2 = i2 < ts2Count ? ts2[i2] : 1;
97 const double t2 = t2s + (t2e - t2s) * tEnd2;
98 if (&cubic1 == &cubic2 && t1Start >= t2Start) {
99 t2Start = t2;
100 continue;
101 }
102 SkReduceOrder s2;
103 int o2 = quadPart(cubic2, t2Start, t2, &s2);
104 #if ONE_OFF_DEBUG
105 char tab[] = " ";
106 if (tLimits1[0][0] >= t1Start && tLimits1[0][1] <= t1
107 && tLimits1[1][0] >= t2Start && tLimits1[1][1] <= t2) {
108 SkDebugf("%.*s %s t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)", i.depth()*2, tab,
109 __FUNCTION__, t1Start, t1, t2Start, t2);
110 SkIntersections xlocals;
111 xlocals.allowNear(false);
112 intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, xlocals);
113 SkDebugf(" xlocals.fUsed=%d\n", xlocals.used());
114 }
115 #endif
116 SkIntersections locals;
117 locals.allowNear(false);
118 intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, locals);
119 int tCount = locals.used();
120 for (int tIdx = 0; tIdx < tCount; ++tIdx) {
121 double to1 = t1Start + (t1 - t1Start) * locals[0][tIdx];
122 double to2 = t2Start + (t2 - t2Start) * locals[1][tIdx];
123 // if the computed t is not sufficiently precise, iterate
124 SkDPoint p1 = cubic1.ptAtT(to1);
125 SkDPoint p2 = cubic2.ptAtT(to2);
126 if (p1.approximatelyEqual(p2)) {
127 // FIXME: local edge may be coincident -- experiment with not propagating coincidence to caller
128 // SkASSERT(!locals.isCoincident(tIdx));
129 if (&cubic1 != &cubic2 || !approximately_equal(to1, to2)) {
130 if (i.swapped()) { // FIXME: insert should respect swap
131 i.insert(to2, to1, p1);
132 } else {
133 i.insert(to1, to2, p1);
134 }
135 }
136 } else {
137 double offset = precisionScale / 16; // FIME: const is arbitrary: test, refine
138 double c1Bottom = tIdx == 0 ? 0 :
139 (t1Start + (t1 - t1Start) * locals[0][tIdx - 1] + to1) / 2;
140 double c1Min = SkTMax(c1Bottom, to1 - offset);
141 double c1Top = tIdx == tCount - 1 ? 1 :
142 (t1Start + (t1 - t1Start) * locals[0][tIdx + 1] + to1) / 2;
143 double c1Max = SkTMin(c1Top, to1 + offset);
144 double c2Min = SkTMax(0., to2 - offset);
145 double c2Max = SkTMin(1., to2 + offset);
146 #if ONE_OFF_DEBUG
147 SkDebugf("%.*s %s 1 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab,
148 __FUNCTION__,
149 c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max
150 && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max,
151 to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset
152 && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset,
153 c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max
154 && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max,
155 to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset
156 && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset);
157 SkDebugf("%.*s %s 1 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
158 " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
159 i.depth()*2, tab, __FUNCTION__, c1Bottom, c1Top, 0., 1.,
160 to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
161 SkDebugf("%.*s %s 1 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
162 " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min,
163 c1Max, c2Min, c2Max);
164 #endif
165 intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
166 #if ONE_OFF_DEBUG
167 SkDebugf("%.*s %s 1 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__,
168 i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1);
169 #endif
170 if (tCount > 1) {
171 c1Min = SkTMax(0., to1 - offset);
172 c1Max = SkTMin(1., to1 + offset);
173 double c2Bottom = tIdx == 0 ? to2 :
174 (t2Start + (t2 - t2Start) * locals[1][tIdx - 1] + to2) / 2;
175 double c2Top = tIdx == tCount - 1 ? to2 :
176 (t2Start + (t2 - t2Start) * locals[1][tIdx + 1] + to2) / 2;
177 if (c2Bottom > c2Top) {
178 SkTSwap(c2Bottom, c2Top);
179 }
180 if (c2Bottom == to2) {
181 c2Bottom = 0;
182 }
183 if (c2Top == to2) {
184 c2Top = 1;
185 }
186 c2Min = SkTMax(c2Bottom, to2 - offset);
187 c2Max = SkTMin(c2Top, to2 + offset);
188 #if ONE_OFF_DEBUG
189 SkDebugf("%.*s %s 2 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab,
190 __FUNCTION__,
191 c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max
192 && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max,
193 to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset
194 && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset,
195 c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max
196 && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max,
197 to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset
198 && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset);
199 SkDebugf("%.*s %s 2 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
200 " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
201 i.depth()*2, tab, __FUNCTION__, 0., 1., c2Bottom, c2Top,
202 to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
203 SkDebugf("%.*s %s 2 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
204 " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min,
205 c1Max, c2Min, c2Max);
206 #endif
207 intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
208 #if ONE_OFF_DEBUG
209 SkDebugf("%.*s %s 2 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__,
210 i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1);
211 #endif
212 c1Min = SkTMax(c1Bottom, to1 - offset);
213 c1Max = SkTMin(c1Top, to1 + offset);
214 #if ONE_OFF_DEBUG
215 SkDebugf("%.*s %s 3 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab,
216 __FUNCTION__,
217 c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max
218 && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max,
219 to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset
220 && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset,
221 c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max
222 && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max,
223 to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset
224 && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset);
225 SkDebugf("%.*s %s 3 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
226 " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
227 i.depth()*2, tab, __FUNCTION__, 0., 1., c2Bottom, c2Top,
228 to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
229 SkDebugf("%.*s %s 3 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
230 " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min,
231 c1Max, c2Min, c2Max);
232 #endif
233 intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
234 #if ONE_OFF_DEBUG
235 SkDebugf("%.*s %s 3 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__,
236 i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1);
237 #endif
238 }
239 // intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
240 // FIXME: if no intersection is found, either quadratics intersected where
241 // cubics did not, or the intersection was missed. In the former case, expect
242 // the quadratics to be nearly parallel at the point of intersection, and check
243 // for that.
244 }
245 }
246 t2Start = t2;
247 }
248 t1Start = t1;
249 }
250 i.downDepth();
251 }
252
253 // if two ends intersect, check middle for coincidence
cubicCheckCoincidence(const SkDCubic & c1,const SkDCubic & c2)254 bool SkIntersections::cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2) {
255 if (fUsed < 2) {
256 return false;
257 }
258 int last = fUsed - 1;
259 double tRange1 = fT[0][last] - fT[0][0];
260 double tRange2 = fT[1][last] - fT[1][0];
261 for (int index = 1; index < 5; ++index) {
262 double testT1 = fT[0][0] + tRange1 * index / 5;
263 double testT2 = fT[1][0] + tRange2 * index / 5;
264 SkDPoint testPt1 = c1.ptAtT(testT1);
265 SkDPoint testPt2 = c2.ptAtT(testT2);
266 if (!testPt1.approximatelyEqual(testPt2)) {
267 return false;
268 }
269 }
270 if (fUsed > 2) {
271 fPt[1] = fPt[last];
272 fT[0][1] = fT[0][last];
273 fT[1][1] = fT[1][last];
274 fUsed = 2;
275 }
276 fIsCoincident[0] = fIsCoincident[1] = 0x03;
277 return true;
278 }
279
280 #define LINE_FRACTION 0.1
281
282 // intersect the end of the cubic with the other. Try lines from the end to control and opposite
283 // end to determine range of t on opposite cubic.
cubicExactEnd(const SkDCubic & cubic1,bool start,const SkDCubic & cubic2)284 bool SkIntersections::cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2) {
285 int t1Index = start ? 0 : 3;
286 double testT = (double) !start;
287 bool swap = swapped();
288 // quad/quad at this point checks to see if exact matches have already been found
289 // cubic/cubic can't reject so easily since cubics can intersect same point more than once
290 SkDLine tmpLine;
291 tmpLine[0] = tmpLine[1] = cubic2[t1Index];
292 tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY;
293 tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX;
294 SkIntersections impTs;
295 impTs.allowNear(false);
296 impTs.intersectRay(cubic1, tmpLine);
297 for (int index = 0; index < impTs.used(); ++index) {
298 SkDPoint realPt = impTs.pt(index);
299 if (!tmpLine[0].approximatelyEqual(realPt)) {
300 continue;
301 }
302 if (swap) {
303 insert(testT, impTs[0][index], tmpLine[0]);
304 } else {
305 insert(impTs[0][index], testT, tmpLine[0]);
306 }
307 return true;
308 }
309 return false;
310 }
311
cubicNearEnd(const SkDCubic & cubic1,bool start,const SkDCubic & cubic2,const SkDRect & bounds2)312 void SkIntersections::cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2,
313 const SkDRect& bounds2) {
314 SkDLine line;
315 int t1Index = start ? 0 : 3;
316 double testT = (double) !start;
317 // don't bother if the two cubics are connnected
318 static const int kPointsInCubic = 4; // FIXME: move to DCubic, replace '4' with this
319 static const int kMaxLineCubicIntersections = 3;
320 SkSTArray<(kMaxLineCubicIntersections - 1) * kMaxLineCubicIntersections, double, true> tVals;
321 line[0] = cubic1[t1Index];
322 // this variant looks for intersections with the end point and lines parallel to other points
323 for (int index = 0; index < kPointsInCubic; ++index) {
324 if (index == t1Index) {
325 continue;
326 }
327 SkDVector dxy1 = cubic1[index] - line[0];
328 dxy1 /= SkDCubic::gPrecisionUnit;
329 line[1] = line[0] + dxy1;
330 SkDRect lineBounds;
331 lineBounds.setBounds(line);
332 if (!bounds2.intersects(&lineBounds)) {
333 continue;
334 }
335 SkIntersections local;
336 if (!local.intersect(cubic2, line)) {
337 continue;
338 }
339 for (int idx2 = 0; idx2 < local.used(); ++idx2) {
340 double foundT = local[0][idx2];
341 if (approximately_less_than_zero(foundT)
342 || approximately_greater_than_one(foundT)) {
343 continue;
344 }
345 if (local.pt(idx2).approximatelyEqual(line[0])) {
346 if (swapped()) { // FIXME: insert should respect swap
347 insert(foundT, testT, line[0]);
348 } else {
349 insert(testT, foundT, line[0]);
350 }
351 } else {
352 tVals.push_back(foundT);
353 }
354 }
355 }
356 if (tVals.count() == 0) {
357 return;
358 }
359 SkTQSort<double>(tVals.begin(), tVals.end() - 1);
360 double tMin1 = start ? 0 : 1 - LINE_FRACTION;
361 double tMax1 = start ? LINE_FRACTION : 1;
362 int tIdx = 0;
363 do {
364 int tLast = tIdx;
365 while (tLast + 1 < tVals.count() && roughly_equal(tVals[tLast + 1], tVals[tIdx])) {
366 ++tLast;
367 }
368 double tMin2 = SkTMax(tVals[tIdx] - LINE_FRACTION, 0.0);
369 double tMax2 = SkTMin(tVals[tLast] + LINE_FRACTION, 1.0);
370 int lastUsed = used();
371 ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this);
372 if (lastUsed == used()) {
373 tMin2 = SkTMax(tVals[tIdx] - (1.0 / SkDCubic::gPrecisionUnit), 0.0);
374 tMax2 = SkTMin(tVals[tLast] + (1.0 / SkDCubic::gPrecisionUnit), 1.0);
375 ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this);
376 }
377 tIdx = tLast + 1;
378 } while (tIdx < tVals.count());
379 return;
380 }
381
382 const double CLOSE_ENOUGH = 0.001;
383
closeStart(const SkDCubic & cubic,int cubicIndex,SkIntersections & i,SkDPoint & pt)384 static bool closeStart(const SkDCubic& cubic, int cubicIndex, SkIntersections& i, SkDPoint& pt) {
385 if (i[cubicIndex][0] != 0 || i[cubicIndex][1] > CLOSE_ENOUGH) {
386 return false;
387 }
388 pt = cubic.ptAtT((i[cubicIndex][0] + i[cubicIndex][1]) / 2);
389 return true;
390 }
391
closeEnd(const SkDCubic & cubic,int cubicIndex,SkIntersections & i,SkDPoint & pt)392 static bool closeEnd(const SkDCubic& cubic, int cubicIndex, SkIntersections& i, SkDPoint& pt) {
393 int last = i.used() - 1;
394 if (i[cubicIndex][last] != 1 || i[cubicIndex][last - 1] < 1 - CLOSE_ENOUGH) {
395 return false;
396 }
397 pt = cubic.ptAtT((i[cubicIndex][last] + i[cubicIndex][last - 1]) / 2);
398 return true;
399 }
400
only_end_pts_in_common(const SkDCubic & c1,const SkDCubic & c2)401 static bool only_end_pts_in_common(const SkDCubic& c1, const SkDCubic& c2) {
402 // the idea here is to see at minimum do a quick reject by rotating all points
403 // to either side of the line formed by connecting the endpoints
404 // if the opposite curves points are on the line or on the other side, the
405 // curves at most intersect at the endpoints
406 for (int oddMan = 0; oddMan < 4; ++oddMan) {
407 const SkDPoint* endPt[3];
408 for (int opp = 1; opp < 4; ++opp) {
409 int end = oddMan ^ opp; // choose a value not equal to oddMan
410 endPt[opp - 1] = &c1[end];
411 }
412 for (int triTest = 0; triTest < 3; ++triTest) {
413 double origX = endPt[triTest]->fX;
414 double origY = endPt[triTest]->fY;
415 int oppTest = triTest + 1;
416 if (3 == oppTest) {
417 oppTest = 0;
418 }
419 double adj = endPt[oppTest]->fX - origX;
420 double opp = endPt[oppTest]->fY - origY;
421 double sign = (c1[oddMan].fY - origY) * adj - (c1[oddMan].fX - origX) * opp;
422 if (approximately_zero(sign)) {
423 goto tryNextHalfPlane;
424 }
425 for (int n = 0; n < 4; ++n) {
426 double test = (c2[n].fY - origY) * adj - (c2[n].fX - origX) * opp;
427 if (test * sign > 0 && !precisely_zero(test)) {
428 goto tryNextHalfPlane;
429 }
430 }
431 }
432 return true;
433 tryNextHalfPlane:
434 ;
435 }
436 return false;
437 }
438
intersect(const SkDCubic & c1,const SkDCubic & c2)439 int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) {
440 if (fMax == 0) {
441 fMax = 9;
442 }
443 bool selfIntersect = &c1 == &c2;
444 if (selfIntersect) {
445 if (c1[0].approximatelyEqual(c1[3])) {
446 insert(0, 1, c1[0]);
447 return fUsed;
448 }
449 } else {
450 // OPTIMIZATION: set exact end bits here to avoid cubic exact end later
451 for (int i1 = 0; i1 < 4; i1 += 3) {
452 for (int i2 = 0; i2 < 4; i2 += 3) {
453 if (c1[i1].approximatelyEqual(c2[i2])) {
454 insert(i1 >> 1, i2 >> 1, c1[i1]);
455 }
456 }
457 }
458 }
459 SkASSERT(fUsed < 4);
460 if (!selfIntersect) {
461 if (only_end_pts_in_common(c1, c2)) {
462 return fUsed;
463 }
464 if (only_end_pts_in_common(c2, c1)) {
465 return fUsed;
466 }
467 }
468 // quad/quad does linear test here -- cubic does not
469 // cubics which are really lines should have been detected in reduce step earlier
470 int exactEndBits = 0;
471 if (selfIntersect) {
472 if (fUsed) {
473 return fUsed;
474 }
475 } else {
476 exactEndBits |= cubicExactEnd(c1, false, c2) << 0;
477 exactEndBits |= cubicExactEnd(c1, true, c2) << 1;
478 swap();
479 exactEndBits |= cubicExactEnd(c2, false, c1) << 2;
480 exactEndBits |= cubicExactEnd(c2, true, c1) << 3;
481 swap();
482 }
483 if (cubicCheckCoincidence(c1, c2)) {
484 SkASSERT(!selfIntersect);
485 return fUsed;
486 }
487 // FIXME: pass in cached bounds from caller
488 SkDRect c2Bounds;
489 c2Bounds.setBounds(c2);
490 if (!(exactEndBits & 4)) {
491 cubicNearEnd(c1, false, c2, c2Bounds);
492 }
493 if (!(exactEndBits & 8)) {
494 cubicNearEnd(c1, true, c2, c2Bounds);
495 }
496 if (!selfIntersect) {
497 SkDRect c1Bounds;
498 c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ?
499 swap();
500 if (!(exactEndBits & 1)) {
501 cubicNearEnd(c2, false, c1, c1Bounds);
502 }
503 if (!(exactEndBits & 2)) {
504 cubicNearEnd(c2, true, c1, c1Bounds);
505 }
506 swap();
507 }
508 if (cubicCheckCoincidence(c1, c2)) {
509 SkASSERT(!selfIntersect);
510 return fUsed;
511 }
512 SkIntersections i;
513 i.fAllowNear = false;
514 i.fMax = 9;
515 ::intersect(c1, 0, 1, c2, 0, 1, 1, i);
516 int compCount = i.used();
517 if (compCount) {
518 int exactCount = used();
519 if (exactCount == 0) {
520 set(i);
521 } else {
522 // at least one is exact or near, and at least one was computed. Eliminate duplicates
523 for (int exIdx = 0; exIdx < exactCount; ++exIdx) {
524 for (int cpIdx = 0; cpIdx < compCount; ) {
525 if (fT[0][0] == i[0][0] && fT[1][0] == i[1][0]) {
526 i.removeOne(cpIdx);
527 --compCount;
528 continue;
529 }
530 double tAvg = (fT[0][exIdx] + i[0][cpIdx]) / 2;
531 SkDPoint pt = c1.ptAtT(tAvg);
532 if (!pt.approximatelyEqual(fPt[exIdx])) {
533 ++cpIdx;
534 continue;
535 }
536 tAvg = (fT[1][exIdx] + i[1][cpIdx]) / 2;
537 pt = c2.ptAtT(tAvg);
538 if (!pt.approximatelyEqual(fPt[exIdx])) {
539 ++cpIdx;
540 continue;
541 }
542 i.removeOne(cpIdx);
543 --compCount;
544 }
545 }
546 // if mid t evaluates to nearly the same point, skip the t
547 for (int cpIdx = 0; cpIdx < compCount - 1; ) {
548 double tAvg = (fT[0][cpIdx] + i[0][cpIdx + 1]) / 2;
549 SkDPoint pt = c1.ptAtT(tAvg);
550 if (!pt.approximatelyEqual(fPt[cpIdx])) {
551 ++cpIdx;
552 continue;
553 }
554 tAvg = (fT[1][cpIdx] + i[1][cpIdx + 1]) / 2;
555 pt = c2.ptAtT(tAvg);
556 if (!pt.approximatelyEqual(fPt[cpIdx])) {
557 ++cpIdx;
558 continue;
559 }
560 i.removeOne(cpIdx);
561 --compCount;
562 }
563 // in addition to adding below missing function, think about how to say
564 append(i);
565 }
566 }
567 // If an end point and a second point very close to the end is returned, the second
568 // point may have been detected because the approximate quads
569 // intersected at the end and close to it. Verify that the second point is valid.
570 if (fUsed <= 1) {
571 return fUsed;
572 }
573 SkDPoint pt[2];
574 if (closeStart(c1, 0, *this, pt[0]) && closeStart(c2, 1, *this, pt[1])
575 && pt[0].approximatelyEqual(pt[1])) {
576 removeOne(1);
577 }
578 if (closeEnd(c1, 0, *this, pt[0]) && closeEnd(c2, 1, *this, pt[1])
579 && pt[0].approximatelyEqual(pt[1])) {
580 removeOne(used() - 2);
581 }
582 // vet the pairs of t values to see if the mid value is also on the curve. If so, mark
583 // the span as coincident
584 if (fUsed >= 2 && !coincidentUsed()) {
585 int last = fUsed - 1;
586 int match = 0;
587 for (int index = 0; index < last; ++index) {
588 double mid1 = (fT[0][index] + fT[0][index + 1]) / 2;
589 double mid2 = (fT[1][index] + fT[1][index + 1]) / 2;
590 pt[0] = c1.ptAtT(mid1);
591 pt[1] = c2.ptAtT(mid2);
592 if (pt[0].approximatelyEqual(pt[1])) {
593 match |= 1 << index;
594 }
595 }
596 if (match) {
597 #if DEBUG_CONCIDENT
598 if (((match + 1) & match) != 0) {
599 SkDebugf("%s coincident hole\n", __FUNCTION__);
600 }
601 #endif
602 // for now, assume that everything from start to finish is coincident
603 if (fUsed > 2) {
604 fPt[1] = fPt[last];
605 fT[0][1] = fT[0][last];
606 fT[1][1] = fT[1][last];
607 fIsCoincident[0] = 0x03;
608 fIsCoincident[1] = 0x03;
609 fUsed = 2;
610 }
611 }
612 }
613 return fUsed;
614 }
615
616 // Up promote the quad to a cubic.
617 // OPTIMIZATION If this is a common use case, optimize by duplicating
618 // the intersect 3 loop to avoid the promotion / demotion code
intersect(const SkDCubic & cubic,const SkDQuad & quad)619 int SkIntersections::intersect(const SkDCubic& cubic, const SkDQuad& quad) {
620 fMax = 6;
621 SkDCubic up = quad.toCubic();
622 (void) intersect(cubic, up);
623 return used();
624 }
625
626 /* http://www.ag.jku.at/compass/compasssample.pdf
627 ( Self-Intersection Problems and Approximate Implicitization by Jan B. Thomassen
628 Centre of Mathematics for Applications, University of Oslo http://www.cma.uio.no janbth@math.uio.no
629 SINTEF Applied Mathematics http://www.sintef.no )
630 describes a method to find the self intersection of a cubic by taking the gradient of the implicit
631 form dotted with the normal, and solving for the roots. My math foo is too poor to implement this.*/
632
intersect(const SkDCubic & c)633 int SkIntersections::intersect(const SkDCubic& c) {
634 fMax = 1;
635 // check to see if x or y end points are the extrema. Are other quick rejects possible?
636 if (c.endsAreExtremaInXOrY()) {
637 return false;
638 }
639 (void) intersect(c, c);
640 if (used() > 0) {
641 SkASSERT(used() == 1);
642 if (fT[0][0] > fT[1][0]) {
643 swapPts();
644 }
645 }
646 return used();
647 }
648