src/pathops/SkDQuadIntersection.cpp - Issue 1002693002: pathops version two

Side by Side Diff: src/pathops/SkDQuadIntersection.cpp

Issue 1002693002: pathops version two (Closed) Base URL: https://skia.googlesource.com/skia.git@master

Patch Set: fix arm 64 inspired coincident handling Created 5 years, 9 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
1 // Another approach is to start with the implicit form of one curve and solve

2 // (seek implicit coefficients in QuadraticParameter.cpp

3 // by substituting in the parametric form of the other.

4 // The downside of this approach is that early rejects are difficult to come by.

5 // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormu la.html#step

6

7 #include "SkDQuadImplicit.h"

8 #include "SkIntersections.h"

9 #include "SkPathOpsLine.h"

10 #include "SkQuarticRoot.h"

11 #include "SkTArray.h"

12 #include "SkTSort.h"

13

14 /* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F

15 * and given x = at^2 + bt + c (the parameterized form)

16 * y = dt^2 + et + f

17 * then

18 * 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D (at^2+bt+c)+E(dt^2+et+f)+F

19 */

20

21 static int findRoots(const SkDQuadImplicit& i, const SkDQuad& quad, double roots [4],

22 bool oneHint, bool flip, int firstCubicRoot) {

23 SkDQuad flipped;

24 const SkDQuad& q = flip ? (flipped = quad.flip()) : quad;

25 double a, b, c;

26 SkDQuad::SetABC(&q[0].fX, &a, &b, &c);

27 double d, e, f;

28 SkDQuad::SetABC(&q[0].fY, &d, &e, &f);

29 const double t4 = i.x2() * a * a

30 + i.xy() * a * d

31 + i.y2() * d * d;

32 const double t3 = 2 * i.x2() * a * b

33 + i.xy() * (a * e + b * d)

34 + 2 * i.y2() * d * e;

35 const double t2 = i.x2() * (b * b + 2 * a * c)

36 + i.xy() * (c * d + b * e + a * f)

37 + i.y2() * (e * e + 2 * d * f)

38 + i.x() * a

39 + i.y() * d;

40 const double t1 = 2 * i.x2() * b * c

41 + i.xy() * (c * e + b * f)

42 + 2 * i.y2() * e * f

43 + i.x() * b

44 + i.y() * e;

45 const double t0 = i.x2() * c * c

46 + i.xy() * c * f

47 + i.y2() * f * f

48 + i.x() * c

49 + i.y() * f

50 + i.c();

51 int rootCount = SkReducedQuarticRoots(t4, t3, t2, t1, t0, oneHint, roots);

52 if (rootCount < 0) {

53 rootCount = SkQuarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots );

54 }

55 if (flip) {

56 for (int index = 0; index < rootCount; ++index) {

57 roots[index] = 1 - roots[index];

58 }

59 }

60 return rootCount;

61 }

62

63 static int addValidRoots(const double roots[4], const int count, double valid[4] ) {

64 int result = 0;

65 int index;

66 for (index = 0; index < count; ++index) {

67 if (!approximately_zero_or_more(roots[index]) \|\| !approximately_one_or_l ess(roots[index])) {

68 continue;

69 }

70 double t = 1 - roots[index];

71 if (approximately_less_than_zero(t)) {

72 t = 0;

73 } else if (approximately_greater_than_one(t)) {

74 t = 1;

75 }

76 SkASSERT(t >= 0 && t <= 1);

77 valid[result++] = t;

78 }

79 return result;

80 }

81

82 static bool only_end_pts_in_common(const SkDQuad& q1, const SkDQuad& q2) {

83 // the idea here is to see at minimum do a quick reject by rotating all points

84 // to either side of the line formed by connecting the endpoints

85 // if the opposite curves points are on the line or on the other side, the

86 // curves at most intersect at the endpoints

87 for (int oddMan = 0; oddMan < 3; ++oddMan) {

88 const SkDPoint* endPt[2];

89 for (int opp = 1; opp < 3; ++opp) {

90 int end = oddMan ^ opp; // choose a value not equal to oddMan

91 if (3 == end) { // and correct so that largest value is 1 or 2

92 end = opp;

93 }

94 endPt[opp - 1] = &q1[end];

95 }

96 double origX = endPt[0]->fX;

97 double origY = endPt[0]->fY;

98 double adj = endPt[1]->fX - origX;

99 double opp = endPt[1]->fY - origY;

100 double sign = (q1[oddMan].fY - origY) * adj - (q1[oddMan].fX - origX) * opp;

101 if (approximately_zero(sign)) {

102 goto tryNextHalfPlane;

103 }

104 for (int n = 0; n < 3; ++n) {

105 double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;

106 if (test * sign > 0 && !precisely_zero(test)) {

107 goto tryNextHalfPlane;

108 }

109 }

110 return true;

111 tryNextHalfPlane:

112 ;

113 }

114 return false;

115 }

116

117 // returns false if there's more than one intercept or the intercept doesn't mat ch the point

118 // returns true if the intercept was successfully added or if the

119 // original quads need to be subdivided

120 static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou ble tMax,

121 SkIntersections* i, bool* subDivide) {

122 double tMid = (tMin + tMax) / 2;

123 SkDPoint mid = q2.ptAtT(tMid);

124 SkDLine line;

125 line[0] = line[1] = mid;

126 SkDVector dxdy = q2.dxdyAtT(tMid);

127 line[0] -= dxdy;

128 line[1] += dxdy;

129 SkIntersections rootTs;

130 rootTs.allowNear(false);

131 int roots = rootTs.intersect(q1, line);

132 if (roots == 0) {

133 if (subDivide) {

134 *subDivide = true;

135 }

136 return true;

137 }

138 if (roots == 2) {

139 return false;

140 }

141 SkDPoint pt2 = q1.ptAtT(rootTs[0][0]);

142 if (!pt2.approximatelyEqual(mid)) {

143 return false;

144 }

145 i->insertSwap(rootTs[0][0], tMid, pt2);

146 return true;

147 }

148

149 static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD Quad& q2,

150 double t2s, double t2e, SkIntersections* i, bool* su bDivide) {

151 SkDQuad hull = q1.subDivide(t1s, t1e);

152 SkDLine line = {{hull[2], hull[0]}};

153 const SkDLine* testLines[] = { &line, (const SkDLine) &hull[0], (const SkDL ine) &hull[1] };

154 const size_t kTestCount = SK_ARRAY_COUNT(testLines);

155 SkSTArray<kTestCount * 2, double, true> tsFound;

156 for (size_t index = 0; index < kTestCount; ++index) {

157 SkIntersections rootTs;

158 rootTs.allowNear(false);

159 int roots = rootTs.intersect(q2, *testLines[index]);

160 for (int idx2 = 0; idx2 < roots; ++idx2) {

161 double t = rootTs[0][idx2];

162 #if 0 // def SK_DEBUG // FIXME : accurate for error = 16, error of 17.5 seen

163 // {{{136.08723965397621, 1648.2814535211637}, {593.49031197259478, 1190.8784277 439891}, {593.49031197259478, 544.0128173828125}}}

164 // {{{-968.181396484375, 544.0128173828125}, {592.2825927734375, 870.55249023437 5}, {593.435302734375, 557.8828125}}}

165

166 SkDPoint qPt = q2.ptAtT(t);

167 SkDPoint lPt = testLines[index]->ptAtT(rootTs[1][idx2]);

168 SkASSERT(qPt.approximatelyDEqual(lPt));

169 #endif

170 if (approximately_negative(t - t2s) \|\| approximately_positive(t - t2 e)) {

171 continue;

172 }

173 tsFound.push_back(rootTs[0][idx2]);

174 }

175 }

176 int tCount = tsFound.count();

177 if (tCount <= 0) {

178 return true;

179 }

180 double tMin, tMax;

181 if (tCount == 1) {

182 tMin = tMax = tsFound[0];

183 } else {

184 SkASSERT(tCount > 1);

185 SkTQSort<double>(tsFound.begin(), tsFound.end() - 1);

186 tMin = tsFound[0];

187 tMax = tsFound[tsFound.count() - 1];

188 }

189 SkDPoint end = q2.ptAtT(t2s);

190 bool startInTriangle = hull.pointInHull(end);

191 if (startInTriangle) {

192 tMin = t2s;

193 }

194 end = q2.ptAtT(t2e);

195 bool endInTriangle = hull.pointInHull(end);

196 if (endInTriangle) {

197 tMax = t2e;

198 }

199 int split = 0;

200 SkDVector dxy1, dxy2;

201 if (tMin != tMax \|\| tCount > 2) {

202 dxy2 = q2.dxdyAtT(tMin);

203 for (int index = 1; index < tCount; ++index) {

204 dxy1 = dxy2;

205 dxy2 = q2.dxdyAtT(tsFound[index]);

206 double dot = dxy1.dot(dxy2);

207 if (dot < 0) {

208 split = index - 1;

209 break;

210 }

211 }

212 }

213 if (split == 0) { // there's one point

214 if (add_intercept(q1, q2, tMin, tMax, i, subDivide)) {

215 return true;

216 }

217 i->swap();

218 return is_linear_inner(q2, tMin, tMax, q1, t1s, t1e, i, subDivide);

219 }

220 // At this point, we have two ranges of t values -- treat each separately at the split

221 bool result;

222 if (add_intercept(q1, q2, tMin, tsFound[split - 1], i, subDivide)) {

223 result = true;

224 } else {

225 i->swap();

226 result = is_linear_inner(q2, tMin, tsFound[split - 1], q1, t1s, t1e, i, subDivide);

227 }

228 if (add_intercept(q1, q2, tsFound[split], tMax, i, subDivide)) {

229 result = true;

230 } else {

231 i->swap();

232 result \|= is_linear_inner(q2, tsFound[split], tMax, q1, t1s, t1e, i, sub Divide);

233 }

234 return result;

235 }

236

237 static double flat_measure(const SkDQuad& q) {

238 SkDVector mid = q[1] - q[0];

239 SkDVector dxy = q[2] - q[0];

240 double length = dxy.length(); // OPTIMIZE: get rid of sqrt

241 return fabs(mid.cross(dxy) / length);

242 }

243

244 // FIXME ? should this measure both and then use the quad that is the flattest a s the line?

245 static bool is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i) {

246 if (i->flatMeasure()) {

247 // for backward compatibility, use the old method when called from cubic s

248 // FIXME: figure out how to fix cubics when it calls the new path

249 double measure = flat_measure(q1);

250 // OPTIMIZE: (get rid of sqrt) use approximately_zero

251 if (!approximately_zero_sqrt(measure)) { // approximately_zero_sqrt

252 return false;

253 }

254 } else {

255 if (!q1.isLinear(0, 2)) {

256 return false;

257 }

258 }

259 return is_linear_inner(q1, 0, 1, q2, 0, 1, i, NULL);

260 }

261

262 // FIXME: if flat measure is sufficiently large, then probably the quartic solut ion failed

263 // avoid imprecision incurred with chopAt

264 static void relaxed_is_linear(const SkDQuad* q1, double s1, double e1, const SkD Quad* q2,

265 double s2, double e2, SkIntersections* i) {

266 double m1 = flat_measure(*q1);

267 double m2 = flat_measure(*q2);

268 i->reset();

269 const SkDQuad* rounder, *flatter;

270 double sf, midf, ef, sr, er;

271 if (m2 < m1) {

272 rounder = q1;

273 sr = s1;

274 er = e1;

275 flatter = q2;

276 sf = s2;

277 midf = (s2 + e2) / 2;

278 ef = e2;

279 } else {

280 rounder = q2;

281 sr = s2;

282 er = e2;

283 flatter = q1;

284 sf = s1;

285 midf = (s1 + e1) / 2;

286 ef = e1;

287 }

288 bool subDivide = false;

289 is_linear_inner(flatter, sf, ef, rounder, sr, er, i, &subDivide);

290 if (subDivide) {

291 relaxed_is_linear(flatter, sf, midf, rounder, sr, er, i);

292 relaxed_is_linear(flatter, midf, ef, rounder, sr, er, i);

293 }

294 if (m2 < m1) {

295 i->swapPts();

296 }

297 }

298

299 // each time through the loop, this computes values it had from the last loop

300 // if i == j == 1, the center values are still good

301 // otherwise, for i != 1 or j != 1, four of the values are still good

302 // and if i == 1 ^ j == 1, an additional value is good

303 static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1 Seed,

304 double* t2Seed, SkDPoint* pt) {

305 double tStep = ROUGH_EPSILON;

306 SkDPoint t1[3], t2[3];

307 int calcMask = ~0;

308 do {

309 if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed);

310 if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed);

311 if (t1[1].approximatelyEqual(t2[1])) {

312 *pt = t1[1];

313 #if ONE_OFF_DEBUG

314 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __ FUNCTION__,

315 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t2[1].fX, t2[1].fY);

316 #endif

317 if (*t1Seed < 0) {

318 *t1Seed = 0;

319 } else if (*t1Seed > 1) {

320 *t1Seed = 1;

321 }

322 if (*t2Seed < 0) {

323 *t2Seed = 0;

324 } else if (*t2Seed > 1) {

325 *t2Seed = 1;

326 }

327 return true;

328 }

329 if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(SkTMax(0., *t1Seed - tStep) );

330 if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(SkTMin(1., *t1Seed + tStep) );

331 if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(SkTMax(0., *t2Seed - tStep) );

332 if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(SkTMin(1., *t2Seed + tStep) );

333 double dist[3][3];

334 // OPTIMIZE: using calcMask value permits skipping some distance calcuat ions

335 // if prior loop's results are moved to correct slot for reuse

336 dist[1][1] = t1[1].distanceSquared(t2[1]);

337 int best_i = 1, best_j = 1;

338 for (int i = 0; i < 3; ++i) {

339 for (int j = 0; j < 3; ++j) {

340 if (i == 1 && j == 1) {

341 continue;

342 }

343 dist[i][j] = t1[i].distanceSquared(t2[j]);

344 if (dist[best_i][best_j] > dist[i][j]) {

345 best_i = i;

346 best_j = j;

347 }

348 }

349 }

350 if (best_i == 1 && best_j == 1) {

351 tStep /= 2;

352 if (tStep < FLT_EPSILON_HALF) {

353 break;

354 }

355 calcMask = (1 << 0) \| (1 << 2) \| (1 << 3) \| (1 << 5);

356 continue;

357 }

358 if (best_i == 0) {

359 *t1Seed -= tStep;

360 t1[2] = t1[1];

361 t1[1] = t1[0];

362 calcMask = 1 << 0;

363 } else if (best_i == 2) {

364 *t1Seed += tStep;

365 t1[0] = t1[1];

366 t1[1] = t1[2];

367 calcMask = 1 << 2;

368 } else {

369 calcMask = 0;

370 }

371 if (best_j == 0) {

372 *t2Seed -= tStep;

373 t2[2] = t2[1];

374 t2[1] = t2[0];

375 calcMask \|= 1 << 3;

376 } else if (best_j == 2) {

377 *t2Seed += tStep;

378 t2[0] = t2[1];

379 t2[1] = t2[2];

380 calcMask \|= 1 << 5;

381 }

382 } while (true);

383 #if ONE_OFF_DEBUG

384 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) != (%1.9g,%1.9g) %s\n", __FUNCT ION__,

385 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY);

386 #endif

387 return false;

388 }

389

390 static void lookNearEnd(const SkDQuad& q1, const SkDQuad& q2, int testT,

391 const SkIntersections& orig, bool swap, SkIntersections* i) {

392 if (orig.used() == 1 && orig[!swap][0] == testT) {

393 return;

394 }

395 if (orig.used() == 2 && orig[!swap][1] == testT) {

396 return;

397 }

398 SkDLine tmpLine;

399 int testTIndex = testT << 1;

400 tmpLine[0] = tmpLine[1] = q2[testTIndex];

401 tmpLine[1].fX += q2[1].fY - q2[testTIndex].fY;

402 tmpLine[1].fY -= q2[1].fX - q2[testTIndex].fX;

403 SkIntersections impTs;

404 impTs.intersectRay(q1, tmpLine);

405 for (int index = 0; index < impTs.used(); ++index) {

406 SkDPoint realPt = impTs.pt(index);

407 if (!tmpLine[0].approximatelyPEqual(realPt)) {

408 continue;

409 }

410 if (swap) {

411 i->insert(testT, impTs[0][index], tmpLine[0]);

412 } else {

413 i->insert(impTs[0][index], testT, tmpLine[0]);

414 }

415 }

416 }

417

418 int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {

419 fMax = 4;

420 bool exactMatch = false;

421 // if the quads share an end point, check to see if they overlap

422 for (int i1 = 0; i1 < 3; i1 += 2) {

423 for (int i2 = 0; i2 < 3; i2 += 2) {

424 if (q1[i1].asSkPoint() == q2[i2].asSkPoint()) {

425 insert(i1 >> 1, i2 >> 1, q1[i1]);

426 exactMatch = true;

427 }

428 }

429 }

430 SkASSERT(fUsed < 3);

431 if (only_end_pts_in_common(q1, q2)) {

432 return fUsed;

433 }

434 if (only_end_pts_in_common(q2, q1)) {

435 return fUsed;

436 }

437 // see if either quad is really a line

438 // FIXME: figure out why reduce step didn't find this earlier

439 if (is_linear(q1, q2, this)) {

440 return fUsed;

441 }

442 SkIntersections swapped;

443 swapped.setMax(fMax);

444 if (is_linear(q2, q1, &swapped)) {

445 swapped.swapPts();

446 *this = swapped;

447 return fUsed;

448 }

449 SkIntersections copyI(*this);

450 lookNearEnd(q1, q2, 0, *this, false, &copyI);

451 lookNearEnd(q1, q2, 1, *this, false, &copyI);

452 lookNearEnd(q2, q1, 0, *this, true, &copyI);

453 lookNearEnd(q2, q1, 1, *this, true, &copyI);

454 int innerEqual = 0;

455 if (copyI.fUsed >= 2) {

456 SkASSERT(copyI.fUsed <= 4);

457 double width = copyI[0][1] - copyI[0][0];

458 int midEnd = 1;

459 for (int index = 2; index < copyI.fUsed; ++index) {

460 double testWidth = copyI[0][index] - copyI[0][index - 1];

461 if (testWidth <= width) {

462 continue;

463 }

464 midEnd = index;

465 }

466 for (int index = 0; index < 2; ++index) {

467 double testT = (copyI[0][midEnd] * (index + 1)

468 + copyI[0][midEnd - 1] * (2 - index)) / 3;

469 SkDPoint testPt1 = q1.ptAtT(testT);

470 testT = (copyI[1][midEnd] * (index + 1) + copyI[1][midEnd - 1] * (2 - index)) / 3;

471 SkDPoint testPt2 = q2.ptAtT(testT);

472 innerEqual += testPt1.approximatelyEqual(testPt2);

473 }

474 }

475 bool expectCoincident = copyI.fUsed >= 2 && innerEqual == 2;

476 if (expectCoincident) {

477 reset();

478 insertCoincident(copyI[0][0], copyI[1][0], copyI.fPt[0]);

479 int last = copyI.fUsed - 1;

480 insertCoincident(copyI[0][last], copyI[1][last], copyI.fPt[last]);

481 return fUsed;

482 }

483 SkDQuadImplicit i1(q1);

484 SkDQuadImplicit i2(q2);

485 int index;

486 bool flip1 = q1[2] == q2[0];

487 bool flip2 = q1[0] == q2[2];

488 bool useCubic = q1[0] == q2[0];

489 double roots1[4];

490 int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);

491 // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1

492 double roots1Copy[4];

493 SkDEBUGCODE(sk_bzero(roots1Copy, sizeof(roots1Copy)));

494 int r1Count = addValidRoots(roots1, rootCount, roots1Copy);

495 SkDPoint pts1[4];

496 for (index = 0; index < r1Count; ++index) {

497 pts1[index] = q1.ptAtT(roots1Copy[index]);

498 }

499 double roots2[4];

500 int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);

501 double roots2Copy[4];

502 int r2Count = addValidRoots(roots2, rootCount2, roots2Copy);

503 SkDPoint pts2[4];

504 for (index = 0; index < r2Count; ++index) {

505 pts2[index] = q2.ptAtT(roots2Copy[index]);

506 }

507 bool triedBinary = false;

508 if (r1Count == r2Count && r1Count <= 1) {

509 if (r1Count == 1 && used() == 0) {

510 if (pts1[0].approximatelyEqual(pts2[0])) {

511 insert(roots1Copy[0], roots2Copy[0], pts1[0]);

512 } else {

513 // find intersection by chasing t

514 triedBinary = true;

515 if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) {

516 insert(roots1Copy[0], roots2Copy[0], pts1[0]);

517 }

518 }

519 }

520 return fUsed;

521 }

522 int closest[4];

523 double dist[4];

524 bool foundSomething = false;

525 for (index = 0; index < r1Count; ++index) {

526 dist[index] = DBL_MAX;

527 closest[index] = -1;

528 for (int ndex2 = 0; ndex2 < r2Count; ++ndex2) {

529 if (!pts2[ndex2].approximatelyEqual(pts1[index])) {

530 continue;

531 }

532 double dx = pts2[ndex2].fX - pts1[index].fX;

533 double dy = pts2[ndex2].fY - pts1[index].fY;

534 double distance = dx * dx + dy * dy;

535 if (dist[index] <= distance) {

536 continue;

537 }

538 for (int outer = 0; outer < index; ++outer) {

539 if (closest[outer] != ndex2) {

540 continue;

541 }

542 if (dist[outer] < distance) {

543 goto next;

544 }

545 closest[outer] = -1;

546 }

547 dist[index] = distance;

548 closest[index] = ndex2;

549 foundSomething = true;

550 next:

551 ;

552 }

553 }

554 if (r1Count && r2Count && !foundSomething) {

555 if (exactMatch) {

556 SkASSERT(fUsed > 0);

557 return fUsed;

558 }

559 relaxed_is_linear(&q1, 0, 1, &q2, 0, 1, this);

560 if (fUsed) {

561 return fUsed;

562 }

563 // maybe the curves are nearly coincident

564 if (!triedBinary && binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) {

565 insert(roots1Copy[0], roots2Copy[0], pts1[0]);

566 }

567 return fUsed;

568 }

569 int used = 0;

570 do {

571 double lowest = DBL_MAX;

572 int lowestIndex = -1;

573 for (index = 0; index < r1Count; ++index) {

574 if (closest[index] < 0) {

575 continue;

576 }

577 if (roots1Copy[index] < lowest) {

578 lowestIndex = index;

579 lowest = roots1Copy[index];

580 }

581 }

582 if (lowestIndex < 0) {

583 break;

584 }

585 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]],

586 pts1[lowestIndex]);

587 closest[lowestIndex] = -1;

588 } while (++used < r1Count);

589 return fUsed;

590 }

591

592 void SkIntersections::alignQuadPts(const SkPoint q1[3], const SkPoint q2[3]) {

593 for (int index = 0; index < used(); ++index) {

594 const SkPoint result = pt(index).asSkPoint();

595 if (q1[0] == result \|\| q1[2] == result \|\| q2[0] == result \|\| q2[2] == re sult) {

596 continue;

597 }

598 if (SkDPoint::ApproximatelyEqual(q1[0], result)) {

599 fPt[index].set(q1[0]);

600 // SkASSERT(way_roughly_zero(fT[0][index])); // this value can be bi gger than way rough

601 fT[0][index] = 0;

602 } else if (SkDPoint::ApproximatelyEqual(q1[2], result)) {

603 fPt[index].set(q1[2]);

604 // SkASSERT(way_roughly_equal(fT[0][index], 1));

605 fT[0][index] = 1;

606 }

607 if (SkDPoint::ApproximatelyEqual(q2[0], result)) {

608 fPt[index].set(q2[0]);

609 // SkASSERT(way_roughly_zero(fT[1][index]));

610 fT[1][index] = 0;

611 } else if (SkDPoint::ApproximatelyEqual(q2[2], result)) {

612 fPt[index].set(q2[2]);

613 // SkASSERT(way_roughly_equal(fT[1][index], 1));

614 fT[1][index] = 1;

615 }

616 }

617 }

OLD	NEW

« no previous file with comments | « src/pathops/SkDQuadImplicit.cpp ('k') | src/pathops/SkDQuadLineIntersection.cpp » ('j') | no next file with comments »