experimental/Intersection/Simplify.cpp - Issue 867213004: remove prototype pathops code

Side by Side Diff: experimental/Intersection/Simplify.cpp

Issue 867213004: remove prototype pathops code (Closed) Base URL: https://skia.googlesource.com/skia.git@master

Patch Set: Created 5 years, 10 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 /*

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 "Simplify.h"

8

9 #undef SkASSERT

10 #define SkASSERT(cond) while (!(cond)) { sk_throw(); }

11

12 // Terminology:

13 // A Path contains one of more Contours

14 // A Contour is made up of Segment array

15 // A Segment is described by a Verb and a Point array with 2, 3, or 4 points

16 // A Verb is one of Line, Quad(ratic), or Cubic

17 // A Segment contains a Span array

18 // A Span is describes a portion of a Segment using starting and ending T

19 // T values range from 0 to 1, where 0 is the first Point in the Segment

20 // An Edge is a Segment generated from a Span

21

22 // FIXME: remove once debugging is complete

23 #ifdef SK_DEBUG

24 int gDebugMaxWindSum = SK_MaxS32;

25 int gDebugMaxWindValue = SK_MaxS32;

26 #endif

27

28 #define PIN_ADD_T 0

29 #define TRY_ROTATE 1

30 #define ONE_PASS_COINCIDENCE_CHECK 0

31 #define APPROXIMATE_CUBICS 1

32 #define COMPACT_DEBUG_SORT 0

33

34 #define DEBUG_UNUSED 0 // set to expose unused functions

35

36 #if FORCE_RELEASE \|\| defined SK_RELEASE

37

38 const bool gRunTestsInOneThread = false;

39

40 #define DEBUG_ACTIVE_OP 0

41 #define DEBUG_ACTIVE_SPANS 0

42 #define DEBUG_ACTIVE_SPANS_SHORT_FORM 0

43 #define DEBUG_ADD_INTERSECTING_TS 0

44 #define DEBUG_ADD_T_PAIR 0

45 #define DEBUG_ANGLE 0

46 #define DEBUG_AS_C_CODE 1

47 #define DEBUG_ASSEMBLE 0

48 #define DEBUG_CONCIDENT 0

49 #define DEBUG_CROSS 0

50 #define DEBUG_FLOW 0

51 #define DEBUG_MARK_DONE 0

52 #define DEBUG_PATH_CONSTRUCTION 0

53 #define DEBUG_SHOW_WINDING 0

54 #define DEBUG_SORT 0

55 #define DEBUG_SWAP_TOP 0

56 #define DEBUG_UNSORTABLE 0

57 #define DEBUG_WIND_BUMP 0

58 #define DEBUG_WINDING 0

59 #define DEBUG_WINDING_AT_T 0

60

61 #else

62

63 const bool gRunTestsInOneThread = true;

64

65 #define DEBUG_ACTIVE_OP 1

66 #define DEBUG_ACTIVE_SPANS 1

67 #define DEBUG_ACTIVE_SPANS_SHORT_FORM 0

68 #define DEBUG_ADD_INTERSECTING_TS 1

69 #define DEBUG_ADD_T_PAIR 1

70 #define DEBUG_ANGLE 1

71 #define DEBUG_AS_C_CODE 1

72 #define DEBUG_ASSEMBLE 1

73 #define DEBUG_CONCIDENT 1

74 #define DEBUG_CROSS 0

75 #define DEBUG_FLOW 1

76 #define DEBUG_MARK_DONE 1

77 #define DEBUG_PATH_CONSTRUCTION 1

78 #define DEBUG_SHOW_WINDING 0

79 #define DEBUG_SORT 1

80 #define DEBUG_SWAP_TOP 1

81 #define DEBUG_UNSORTABLE 1

82 #define DEBUG_WIND_BUMP 0

83 #define DEBUG_WINDING 1

84 #define DEBUG_WINDING_AT_T 1

85

86 #endif

87

88 #define DEBUG_DUMP (DEBUG_ACTIVE_OP \| DEBUG_ACTIVE_SPANS \| DEBUG_CONCIDENT \| DEB UG_SORT \| \

89 DEBUG_PATH_CONSTRUCTION)

90

91 #if DEBUG_AS_C_CODE

92 #define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1 .17g,%1.17g}}"

93 #define QUAD_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"

94 #define LINE_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}}"

95 #define PT_DEBUG_STR "{{%1.17g,%1.17g}}"

96 #else

97 #define CUBIC_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"

98 #define QUAD_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"

99 #define LINE_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g)"

100 #define PT_DEBUG_STR "(%1.9g,%1.9g)"

101 #endif

102 #define T_DEBUG_STR(t, n) #t "[" #n "]=%1.9g"

103 #define TX_DEBUG_STR(t) #t "[%d]=%1.9g"

104 #define CUBIC_DEBUG_DATA(c) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY , c[3].fX, c[3].fY

105 #define QUAD_DEBUG_DATA(q) q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY

106 #define LINE_DEBUG_DATA(l) l[0].fX, l[0].fY, l[1].fX, l[1].fY

107 #define PT_DEBUG_DATA(i, n) i.fPt[n].x, i.fPt[n].y

108

109 #if DEBUG_DUMP

110 static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};

111 // static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};

112 static int gContourID;

113 static int gSegmentID;

114 #endif

115

116 #if DEBUG_SORT \|\| DEBUG_SWAP_TOP

117 static int gDebugSortCountDefault = SK_MaxS32;

118 static int gDebugSortCount;

119 #endif

120

121 #if DEBUG_ACTIVE_OP

122 static const char* kShapeOpStr[] = {"diff", "sect", "union", "xor"};

123 #endif

124

125 #ifndef DEBUG_TEST

126 #define DEBUG_TEST 0

127 #endif

128

129 #define MAKE_CONST_LINE(line, pts) \

130 const _Line line = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}}

131 #define MAKE_CONST_QUAD(quad, pts) \

132 const Quadratic quad = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \

133 {pts[2].fX, pts[2].fY}}

134 #define MAKE_CONST_CUBIC(cubic, pts) \

135 const Cubic cubic = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \

136 {pts[2].fX, pts[2].fY}, {pts[3].fX, pts[3].fY}}

137

138 static int LineIntersect(const SkPoint a[2], const SkPoint b[2],

139 Intersections& intersections) {

140 MAKE_CONST_LINE(aLine, a);

141 MAKE_CONST_LINE(bLine, b);

142 return intersect(aLine, bLine, intersections);

143 }

144

145 static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],

146 Intersections& intersections) {

147 MAKE_CONST_QUAD(aQuad, a);

148 MAKE_CONST_LINE(bLine, b);

149 return intersect(aQuad, bLine, intersections);

150 }

151

152 static int CubicLineIntersect(const SkPoint a[4], const SkPoint b[2],

153 Intersections& intersections) {

154 MAKE_CONST_CUBIC(aCubic, a);

155 MAKE_CONST_LINE(bLine, b);

156 return intersect(aCubic, bLine, intersections);

157 }

158

159 static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],

160 Intersections& intersections) {

161 MAKE_CONST_QUAD(aQuad, a);

162 MAKE_CONST_QUAD(bQuad, b);

163 #define TRY_QUARTIC_SOLUTION 1

164 #if TRY_QUARTIC_SOLUTION

165 intersect2(aQuad, bQuad, intersections);

166 #else

167 intersect(aQuad, bQuad, intersections);

168 #endif

169 return intersections.fUsed;

170 }

171

172 #if APPROXIMATE_CUBICS

173 static int CubicQuadIntersect(const SkPoint a[4], const SkPoint b[3],

174 Intersections& intersections) {

175 MAKE_CONST_CUBIC(aCubic, a);

176 MAKE_CONST_QUAD(bQuad, b);

177 return intersect(aCubic, bQuad, intersections);

178 }

179 #endif

180

181 static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], Intersections& intersections) {

182 MAKE_CONST_CUBIC(aCubic, a);

183 MAKE_CONST_CUBIC(bCubic, b);

184 #if APPROXIMATE_CUBICS

185 intersect3(aCubic, bCubic, intersections);

186 #else

187 intersect(aCubic, bCubic, intersections);

188 #endif

189 return intersections.fUsed;

190 }

191

192 static int CubicIntersect(const SkPoint a[4], Intersections& intersections) {

193 MAKE_CONST_CUBIC(aCubic, a);

194 return intersect(aCubic, intersections);

195 }

196

197 static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,

198 SkScalar y, bool flipped, Intersections& intersections) {

199 MAKE_CONST_LINE(aLine, a);

200 return horizontalIntersect(aLine, left, right, y, flipped, intersections);

201 }

202

203 static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,

204 SkScalar y, bool flipped, Intersections& intersections) {

205 MAKE_CONST_QUAD(aQuad, a);

206 return horizontalIntersect(aQuad, left, right, y, flipped, intersections);

207 }

208

209 static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,

210 SkScalar y, bool flipped, Intersections& intersections) {

211 MAKE_CONST_CUBIC(aCubic, a);

212 return horizontalIntersect(aCubic, left, right, y, flipped, intersections);

213 }

214

215 static int (* const HSegmentIntersect[])(const SkPoint [], SkScalar ,

216 SkScalar , SkScalar , bool , Intersections& ) = {

217 NULL,

218 HLineIntersect,

219 HQuadIntersect,

220 HCubicIntersect

221 };

222

223 static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom,

224 SkScalar x, bool flipped, Intersections& intersections) {

225 MAKE_CONST_LINE(aLine, a);

226 return verticalIntersect(aLine, top, bottom, x, flipped, intersections);

227 }

228

229 static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom,

230 SkScalar x, bool flipped, Intersections& intersections) {

231 MAKE_CONST_QUAD(aQuad, a);

232 return verticalIntersect(aQuad, top, bottom, x, flipped, intersections);

233 }

234

235 static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom,

236 SkScalar x, bool flipped, Intersections& intersections) {

237 MAKE_CONST_CUBIC(aCubic, a);

238 return verticalIntersect(aCubic, top, bottom, x, flipped, intersections);

239 }

240

241 static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar ,

242 SkScalar , SkScalar , bool , Intersections& ) = {

243 NULL,

244 VLineIntersect,

245 VQuadIntersect,

246 VCubicIntersect

247 };

248

249 static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {

250 MAKE_CONST_LINE(line, a);

251 double x, y;

252 xy_at_t(line, t, x, y);

253 out->fX = SkDoubleToScalar(x);

254 out->fY = SkDoubleToScalar(y);

255 }

256

257 static void LineXYAtT(const SkPoint a[2], double t, _Point* out) {

258 MAKE_CONST_LINE(line, a);

259 xy_at_t(line, t, out->x, out->y);

260 }

261

262 static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {

263 MAKE_CONST_QUAD(quad, a);

264 double x, y;

265 xy_at_t(quad, t, x, y);

266 out->fX = SkDoubleToScalar(x);

267 out->fY = SkDoubleToScalar(y);

268 }

269

270 static void QuadXYAtT(const SkPoint a[3], double t, _Point* out) {

271 MAKE_CONST_QUAD(quad, a);

272 xy_at_t(quad, t, out->x, out->y);

273 }

274

275 static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {

276 MAKE_CONST_CUBIC(cubic, a);

277 double x, y;

278 xy_at_t(cubic, t, x, y);

279 out->fX = SkDoubleToScalar(x);

280 out->fY = SkDoubleToScalar(y);

281 }

282

283 static void CubicXYAtT(const SkPoint a[4], double t, _Point* out) {

284 MAKE_CONST_CUBIC(cubic, a);

285 xy_at_t(cubic, t, out->x, out->y);

286 }

287

288 static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = {

289 NULL,

290 LineXYAtT,

291 QuadXYAtT,

292 CubicXYAtT

293 };

294

295 static void (* const SegmentXYAtT2[])(const SkPoint [], double , _Point* ) = {

296 NULL,

297 LineXYAtT,

298 QuadXYAtT,

299 CubicXYAtT

300 };

301

302 static SkScalar LineXAtT(const SkPoint a[2], double t) {

303 MAKE_CONST_LINE(aLine, a);

304 double x;

305 xy_at_t(aLine, t, x, (double) 0);

306 return SkDoubleToScalar(x);

307 }

308

309 static SkScalar QuadXAtT(const SkPoint a[3], double t) {

310 MAKE_CONST_QUAD(quad, a);

311 double x;

312 xy_at_t(quad, t, x, (double) 0);

313 return SkDoubleToScalar(x);

314 }

315

316 static SkScalar CubicXAtT(const SkPoint a[4], double t) {

317 MAKE_CONST_CUBIC(cubic, a);

318 double x;

319 xy_at_t(cubic, t, x, (double) 0);

320 return SkDoubleToScalar(x);

321 }

322

323 static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = {

324 NULL,

325 LineXAtT,

326 QuadXAtT,

327 CubicXAtT

328 };

329

330 static SkScalar LineYAtT(const SkPoint a[2], double t) {

331 MAKE_CONST_LINE(aLine, a);

332 double y;

333 xy_at_t(aLine, t, (double) 0, y);

334 return SkDoubleToScalar(y);

335 }

336

337 static SkScalar QuadYAtT(const SkPoint a[3], double t) {

338 MAKE_CONST_QUAD(quad, a);

339 double y;

340 xy_at_t(quad, t, (double) 0, y);

341 return SkDoubleToScalar(y);

342 }

343

344 static SkScalar CubicYAtT(const SkPoint a[4], double t) {

345 MAKE_CONST_CUBIC(cubic, a);

346 double y;

347 xy_at_t(cubic, t, (double) 0, y);

348 return SkDoubleToScalar(y);

349 }

350

351 static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = {

352 NULL,

353 LineYAtT,

354 QuadYAtT,

355 CubicYAtT

356 };

357

358 static SkScalar LineDXAtT(const SkPoint a[2], double ) {

359 return a[1].fX - a[0].fX;

360 }

361

362 static SkScalar QuadDXAtT(const SkPoint a[3], double t) {

363 MAKE_CONST_QUAD(quad, a);

364 double x = dx_at_t(quad, t);

365 return SkDoubleToScalar(x);

366 }

367

368 static SkScalar CubicDXAtT(const SkPoint a[4], double t) {

369 MAKE_CONST_CUBIC(cubic, a);

370 double x = dx_at_t(cubic, t);

371 return SkDoubleToScalar(x);

372 }

373

374 static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = {

375 NULL,

376 LineDXAtT,

377 QuadDXAtT,

378 CubicDXAtT

379 };

380

381 static SkScalar LineDYAtT(const SkPoint a[2], double ) {

382 return a[1].fY - a[0].fY;

383 }

384

385 static SkScalar QuadDYAtT(const SkPoint a[3], double t) {

386 MAKE_CONST_QUAD(quad, a);

387 double y = dy_at_t(quad, t);

388 return SkDoubleToScalar(y);

389 }

390

391 static SkScalar CubicDYAtT(const SkPoint a[4], double t) {

392 MAKE_CONST_CUBIC(cubic, a);

393 double y = dy_at_t(cubic, t);

394 return SkDoubleToScalar(y);

395 }

396

397 static SkScalar (* const SegmentDYAtT[])(const SkPoint [], double ) = {

398 NULL,

399 LineDYAtT,

400 QuadDYAtT,

401 CubicDYAtT

402 };

403

404 static SkVector LineDXDYAtT(const SkPoint a[2], double ) {

405 return a[1] - a[0];

406 }

407

408 static SkVector QuadDXDYAtT(const SkPoint a[3], double t) {

409 MAKE_CONST_QUAD(quad, a);

410 _Vector v = dxdy_at_t(quad, t);

411 return v.asSkVector();

412 }

413

414 static SkVector CubicDXDYAtT(const SkPoint a[4], double t) {

415 MAKE_CONST_CUBIC(cubic, a);

416 _Vector v = dxdy_at_t(cubic, t);

417 return v.asSkVector();

418 }

419

420 static SkVector (* const SegmentDXDYAtT[])(const SkPoint [], double ) = {

421 NULL,

422 LineDXDYAtT,

423 QuadDXDYAtT,

424 CubicDXDYAtT

425 };

426

427 static void LineSubDivide(const SkPoint a[2], double startT, double endT,

428 SkPoint sub[2]) {

429 MAKE_CONST_LINE(aLine, a);

430 _Line dst;

431 sub_divide(aLine, startT, endT, dst);

432 sub[0].fX = SkDoubleToScalar(dst[0].x);

433 sub[0].fY = SkDoubleToScalar(dst[0].y);

434 sub[1].fX = SkDoubleToScalar(dst[1].x);

435 sub[1].fY = SkDoubleToScalar(dst[1].y);

436 }

437

438 static void QuadSubDivide(const SkPoint a[3], double startT, double endT,

439 SkPoint sub[3]) {

440 MAKE_CONST_QUAD(aQuad, a);

441 Quadratic dst;

442 sub_divide(aQuad, startT, endT, dst);

443 sub[0].fX = SkDoubleToScalar(dst[0].x);

444 sub[0].fY = SkDoubleToScalar(dst[0].y);

445 sub[1].fX = SkDoubleToScalar(dst[1].x);

446 sub[1].fY = SkDoubleToScalar(dst[1].y);

447 sub[2].fX = SkDoubleToScalar(dst[2].x);

448 sub[2].fY = SkDoubleToScalar(dst[2].y);

449 }

450

451 static void CubicSubDivide(const SkPoint a[4], double startT, double endT,

452 SkPoint sub[4]) {

453 MAKE_CONST_CUBIC(aCubic, a);

454 Cubic dst;

455 sub_divide(aCubic, startT, endT, dst);

456 sub[0].fX = SkDoubleToScalar(dst[0].x);

457 sub[0].fY = SkDoubleToScalar(dst[0].y);

458 sub[1].fX = SkDoubleToScalar(dst[1].x);

459 sub[1].fY = SkDoubleToScalar(dst[1].y);

460 sub[2].fX = SkDoubleToScalar(dst[2].x);

461 sub[2].fY = SkDoubleToScalar(dst[2].y);

462 sub[3].fX = SkDoubleToScalar(dst[3].x);

463 sub[3].fY = SkDoubleToScalar(dst[3].y);

464 }

465

466 static void (* const SegmentSubDivide[])(const SkPoint [], double , double ,

467 SkPoint []) = {

468 NULL,

469 LineSubDivide,

470 QuadSubDivide,

471 CubicSubDivide

472 };

473

474 static void LineSubDivideHD(const SkPoint a[2], double startT, double endT, _Lin e& dst) {

475 MAKE_CONST_LINE(aLine, a);

476 sub_divide(aLine, startT, endT, dst);

477 }

478

479 static void QuadSubDivideHD(const SkPoint a[3], double startT, double endT, Quad ratic& dst) {

480 MAKE_CONST_QUAD(aQuad, a);

481 sub_divide(aQuad, startT, endT, dst);

482 }

483

484 static void CubicSubDivideHD(const SkPoint a[4], double startT, double endT, Cub ic& dst) {

485 MAKE_CONST_CUBIC(aCubic, a);

486 sub_divide(aCubic, startT, endT, dst);

487 }

488

489 static SkPoint QuadTop(const SkPoint a[3], double startT, double endT) {

490 MAKE_CONST_QUAD(quad, a);

491 _Point topPt = top(quad, startT, endT);

492 return topPt.asSkPoint();

493 }

494

495 static SkPoint CubicTop(const SkPoint a[3], double startT, double endT) {

496 MAKE_CONST_CUBIC(cubic, a);

497 _Point topPt = top(cubic, startT, endT);

498 return topPt.asSkPoint();

499 }

500

501 static SkPoint (* SegmentTop[])(const SkPoint[], double , double ) = {

502 NULL,

503 NULL,

504 QuadTop,

505 CubicTop

506 };

507

508 #if DEBUG_UNUSED

509 static void QuadSubBounds(const SkPoint a[3], double startT, double endT,

510 SkRect& bounds) {

511 SkPoint dst[3];

512 QuadSubDivide(a, startT, endT, dst);

513 bounds.fLeft = bounds.fRight = dst[0].fX;

514 bounds.fTop = bounds.fBottom = dst[0].fY;

515 for (int index = 1; index < 3; ++index) {

516 bounds.growToInclude(dst[index].fX, dst[index].fY);

517 }

518 }

519

520 static void CubicSubBounds(const SkPoint a[4], double startT, double endT,

521 SkRect& bounds) {

522 SkPoint dst[4];

523 CubicSubDivide(a, startT, endT, dst);

524 bounds.fLeft = bounds.fRight = dst[0].fX;

525 bounds.fTop = bounds.fBottom = dst[0].fY;

526 for (int index = 1; index < 4; ++index) {

527 bounds.growToInclude(dst[index].fX, dst[index].fY);

528 }

529 }

530 #endif

531

532 static SkPath::Verb QuadReduceOrder(const SkPoint a[3],

533 SkTDArray<SkPoint>& reducePts) {

534 MAKE_CONST_QUAD(aQuad, a);

535 Quadratic dst;

536 int order = reduceOrder(aQuad, dst, kReduceOrder_TreatAsFill);

537 if (order == 2) { // quad became line

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

539 SkPoint* pt = reducePts.append();

540 pt->fX = SkDoubleToScalar(dst[index].x);

541 pt->fY = SkDoubleToScalar(dst[index].y);

542 }

543 }

544 return (SkPath::Verb) (order - 1);

545 }

546

547 static SkPath::Verb CubicReduceOrder(const SkPoint a[4],

548 SkTDArray<SkPoint>& reducePts) {

549 MAKE_CONST_CUBIC(aCubic, a);

550 Cubic dst;

551 int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed, kReduce Order_TreatAsFill);

552 if (order == 2 \|\| order == 3) { // cubic became line or quad

553 for (int index = 0; index < order; ++index) {

554 SkPoint* pt = reducePts.append();

555 pt->fX = SkDoubleToScalar(dst[index].x);

556 pt->fY = SkDoubleToScalar(dst[index].y);

557 }

558 }

559 return (SkPath::Verb) (order - 1);

560 }

561

562 static bool QuadIsLinear(const SkPoint a[3]) {

563 MAKE_CONST_QUAD(aQuad, a);

564 return isLinear(aQuad, 0, 2);

565 }

566

567 static bool CubicIsLinear(const SkPoint a[4]) {

568 MAKE_CONST_CUBIC(aCubic, a);

569 return isLinear(aCubic, 0, 3);

570 }

571

572 static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) {

573 MAKE_CONST_LINE(aLine, a);

574 double x[2];

575 xy_at_t(aLine, startT, x[0], (double) 0);

576 xy_at_t(aLine, endT, x[1], (double) 0);

577 return SkMinScalar((float) x[0], (float) x[1]);

578 }

579

580 static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) {

581 MAKE_CONST_QUAD(aQuad, a);

582 return (float) leftMostT(aQuad, startT, endT);

583 }

584

585 static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) {

586 MAKE_CONST_CUBIC(aCubic, a);

587 return (float) leftMostT(aCubic, startT, endT);

588 }

589

590 static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = {

591 NULL,

592 LineLeftMost,

593 QuadLeftMost,

594 CubicLeftMost

595 };

596

597 #if 0 // currently unused

598 static int QuadRayIntersect(const SkPoint a[3], const SkPoint b[2],

599 Intersections& intersections) {

600 MAKE_CONST_QUAD(aQuad, a);

601 MAKE_CONST_LINE(bLine, b);

602 return intersectRay(aQuad, bLine, intersections);

603 }

604 #endif

605

606 static int QuadRayIntersect(const SkPoint a[3], const _Line& bLine, Intersection s& intersections) {

607 MAKE_CONST_QUAD(aQuad, a);

608 return intersectRay(aQuad, bLine, intersections);

609 }

610

611 static int CubicRayIntersect(const SkPoint a[3], const _Line& bLine, Intersectio ns& intersections) {

612 MAKE_CONST_CUBIC(aCubic, a);

613 return intersectRay(aCubic, bLine, intersections);

614 }

615

616 static int (* const SegmentRayIntersect[])(const SkPoint [], const _Line& , Inte rsections&) = {

617 NULL,

618 NULL,

619 QuadRayIntersect,

620 CubicRayIntersect

621 };

622

623

624

625 static bool LineVertical(const SkPoint a[2], double startT, double endT) {

626 MAKE_CONST_LINE(aLine, a);

627 double x[2];

628 xy_at_t(aLine, startT, x[0], (double) 0);

629 xy_at_t(aLine, endT, x[1], (double) 0);

630 return AlmostEqualUlps((float) x[0], (float) x[1]);

631 }

632

633 static bool QuadVertical(const SkPoint a[3], double startT, double endT) {

634 SkPoint dst[3];

635 QuadSubDivide(a, startT, endT, dst);

636 return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, d st[2].fX);

637 }

638

639 static bool CubicVertical(const SkPoint a[4], double startT, double endT) {

640 SkPoint dst[4];

641 CubicSubDivide(a, startT, endT, dst);

642 return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, d st[2].fX)

643 && AlmostEqualUlps(dst[2].fX, dst[3].fX);

644 }

645

646 static bool (* const SegmentVertical[])(const SkPoint [], double , double) = {

647 NULL,

648 LineVertical,

649 QuadVertical,

650 CubicVertical

651 };

652

653 class Segment;

654

655 struct Span {

656 Segment* fOther;

657 mutable SkPoint fPt; // lazily computed as needed

658 double fT;

659 double fOtherT; // value at fOther[fOtherIndex].fT

660 int fOtherIndex; // can't be used during intersection

661 int fWindSum; // accumulated from contours surrounding this one.

662 int fOppSum; // for binary operators: the opposite winding sum

663 int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident

664 int fOppValue; // normally 0 -- when binary coincident edges combine, opp va lue goes here

665 bool fDone; // if set, this span to next higher T has been processed

666 bool fUnsortableStart; // set when start is part of an unsortable pair

667 bool fUnsortableEnd; // set when end is part of an unsortable pair

668 bool fTiny; // if set, span may still be considered once for edge following

669 bool fLoop; // set when a cubic loops back to this point

670 };

671

672 // sorting angles

673 // given angles of {dx dy ddx ddy dddx dddy} sort them

674 class Angle {

675 public:

676 // FIXME: this is bogus for quads and cubics

677 // if the quads and cubics' line from end pt to ctrl pt are coincident,

678 // there's no obvious way to determine the curve ordering from the

679 // derivatives alone. In particular, if one quadratic's coincident tangent

680 // is longer than the other curve, the final control point can place the

681 // longer curve on either side of the shorter one.

682 // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf

683 // may provide some help, but nothing has been figured out yet.

684

685 /*(

686 for quads and cubics, set up a parameterized line (e.g. LineParameters )

687 for points [0] to [1]. See if point [2] is on that line, or on one side

688 or the other. If it both quads' end points are on the same side, choose

689 the shorter tangent. If the tangents are equal, choose the better second

690 tangent angle

691

692 maybe I could set up LineParameters lazily

693 */

694 bool operator<(const Angle& rh) const {

695 double y = dy();

696 double ry = rh.dy();

697 if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ?

698 return y < 0;

699 }

700 double x = dx();

701 double rx = rh.dx();

702 if (y == 0 && ry == 0 && x * rx < 0) {

703 return x < rx;

704 }

705 double x_ry = x * ry;

706 double rx_y = rx * y;

707 double cmp = x_ry - rx_y;

708 if (!approximately_zero(cmp)) {

709 return cmp < 0;

710 }

711 if (approximately_zero(x_ry) && approximately_zero(rx_y)

712 && !approximately_zero_squared(cmp)) {

713 return cmp < 0;

714 }

715 // at this point, the initial tangent line is coincident

716 // see if edges curl away from each other

717 if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide)

718 \|\| !approximately_zero(rh.fSide))) {

719 // FIXME: running demo will trigger this assertion

720 // (don't know if commenting out will trigger further assertion or n ot)

721 // commenting it out allows demo to run in release, though

722 // SkASSERT(fSide != rh.fSide);

723 return fSide < rh.fSide;

724 }

725 // see if either curve can be lengthened and try the tangent compare aga in

726 if (cmp && (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolut ely identical

727 && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not inters ecting

728 Angle longer = *this;

729 Angle rhLonger = rh;

730 if (longer.lengthen() \| rhLonger.lengthen()) {

731 return longer < rhLonger;

732 }

733 #if 0

734 // what if we extend in the other direction?

735 longer = *this;

736 rhLonger = rh;

737 if (longer.reverseLengthen() \| rhLonger.reverseLengthen()) {

738 return longer < rhLonger;

739 }

740 #endif

741 }

742 if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximate ly_zero(y))

743 \|\| (rh.fVerb == SkPath::kLine_Verb

744 && approximately_zero(rx) && approximately_zero(ry))) {

745 // See general unsortable comment below. This case can happen when

746 // one line has a non-zero change in t but no change in x and y.

747 fUnsortable = true;

748 rh.fUnsortable = true;

749 return this < &rh; // even with no solution, return a stable sort

750 }

751 if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny

752 \|\| (*fSpans)[SkMin32(fStart, fEnd)].fTiny) {

753 fUnsortable = true;

754 rh.fUnsortable = true;

755 return this < &rh; // even with no solution, return a stable sort

756 }

757 SkASSERT(fVerb >= SkPath::kQuad_Verb);

758 SkASSERT(rh.fVerb >= SkPath::kQuad_Verb);

759 // FIXME: until I can think of something better, project a ray from the

760 // end of the shorter tangent to midway between the end points

761 // through both curves and use the resulting angle to sort

762 // FIXME: some of this setup can be moved to set() if it works, or cache d if it's expensive

763 double len = fTangent1.normalSquared();

764 double rlen = rh.fTangent1.normalSquared();

765 _Line ray;

766 Intersections i, ri;

767 int roots, rroots;

768 bool flip = false;

769 do {

770 bool useThis = (len < rlen) ^ flip;

771 const Cubic& part = useThis ? fCurvePart : rh.fCurvePart;

772 SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb;

773 ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqu al(part[1]) ?

774 part[2] : part[1];

775 ray[1].x = (part[0].x + part[partVerb].x) / 2;

776 ray[1].y = (part[0].y + part[partVerb].y) / 2;

777 SkASSERT(ray[0] != ray[1]);

778 roots = (*SegmentRayIntersect[fVerb])(fPts, ray, i);

779 rroots = (*SegmentRayIntersect[rh.fVerb])(rh.fPts, ray, ri);

780 } while ((roots == 0 \|\| rroots == 0) && (flip ^= true));

781 if (roots == 0 \|\| rroots == 0) {

782 // FIXME: we don't have a solution in this case. The interim solutio n

783 // is to mark the edges as unsortable, exclude them from this and

784 // future computations, and allow the returned path to be fragmented

785 fUnsortable = true;

786 rh.fUnsortable = true;

787 return this < &rh; // even with no solution, return a stable sort

788 }

789 _Point loc;

790 double best = SK_ScalarInfinity;

791 double dx, dy, dist;

792 int index;

793 for (index = 0; index < roots; ++index) {

794 (*SegmentXYAtT2[fVerb])(fPts, i.fT[0][index], &loc);

795 dx = loc.x - ray[0].x;

796 dy = loc.y - ray[0].y;

797 dist = dx * dx + dy * dy;

798 if (best > dist) {

799 best = dist;

800 }

801 }

802 for (index = 0; index < rroots; ++index) {

803 (*SegmentXYAtT2[rh.fVerb])(rh.fPts, ri.fT[0][index], &loc);

804 dx = loc.x - ray[0].x;

805 dy = loc.y - ray[0].y;

806 dist = dx * dx + dy * dy;

807 if (best > dist) {

808 return fSide < 0;

809 }

810 }

811 return fSide > 0;

812 }

813

814 double dx() const {

815 return fTangent1.dx();

816 }

817

818 double dy() const {

819 return fTangent1.dy();

820 }

821

822 int end() const {

823 return fEnd;

824 }

825

826 bool isHorizontal() const {

827 return dy() == 0 && fVerb == SkPath::kLine_Verb;

828 }

829

830 bool lengthen() {

831 int newEnd = fEnd;

832 if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {

833 fEnd = newEnd;

834 setSpans();

835 return true;

836 }

837 return false;

838 }

839

840 bool reverseLengthen() {

841 if (fReversed) {

842 return false;

843 }

844 int newEnd = fStart;

845 if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {

846 fEnd = newEnd;

847 fReversed = true;

848 setSpans();

849 return true;

850 }

851 return false;

852 }

853

854 void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment,

855 int start, int end, const SkTDArray<Span>& spans) {

856 fSegment = segment;

857 fStart = start;

858 fEnd = end;

859 fPts = orig;

860 fVerb = verb;

861 fSpans = &spans;

862 fReversed = false;

863 fUnsortable = false;

864 setSpans();

865 }

866

867

868 void setSpans() {

869 double startT = (*fSpans)[fStart].fT;

870 double endT = (*fSpans)[fEnd].fT;

871 switch (fVerb) {

872 case SkPath::kLine_Verb:

873 _Line l;

874 LineSubDivideHD(fPts, startT, endT, l);

875 // OPTIMIZATION: for pure line compares, we never need fTangent1.c

876 fTangent1.lineEndPoints(l);

877 fSide = 0;

878 break;

879 case SkPath::kQuad_Verb: {

880 Quadratic& quad = (Quadratic&)fCurvePart;

881 QuadSubDivideHD(fPts, startT, endT, quad);

882 fTangent1.quadEndPoints(quad, 0, 1);

883 if (dx() == 0 && dy() == 0) {

884 fTangent1.quadEndPoints(quad);

885 }

886 fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized - - compare sign only

887 } break;

888 case SkPath::kCubic_Verb: {

889 int nextC = 2;

890 CubicSubDivideHD(fPts, startT, endT, fCurvePart);

891 fTangent1.cubicEndPoints(fCurvePart, 0, 1);

892 if (dx() == 0 && dy() == 0) {

893 fTangent1.cubicEndPoints(fCurvePart, 0, 2);

894 nextC = 3;

895 if (dx() == 0 && dy() == 0) {

896 fTangent1.cubicEndPoints(fCurvePart, 0, 3);

897 }

898 }

899 fSide = -fTangent1.pointDistance(fCurvePart[nextC]); // compare sign only

900 if (nextC == 2 && approximately_zero(fSide)) {

901 fSide = -fTangent1.pointDistance(fCurvePart[3]);

902 }

903 } break;

904 default:

905 SkASSERT(0);

906 }

907 fUnsortable = dx() == 0 && dy() == 0;

908 if (fUnsortable) {

909 return;

910 }

911 SkASSERT(fStart != fEnd);

912 int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 3 1 type macro?

913 for (int index = fStart; index != fEnd; index += step) {

914 #if 1

915 const Span& thisSpan = (*fSpans)[index];

916 const Span& nextSpan = (*fSpans)[index + step];

917 if (thisSpan.fTiny \|\| precisely_equal(thisSpan.fT, nextSpan.fT)) {

918 continue;

919 }

920 fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsor tableEnd;

921 #if DEBUG_UNSORTABLE

922 if (fUnsortable) {

923 SkPoint iPt, ePt;

924 (*SegmentXYAtT[fVerb])(fPts, thisSpan.fT, &iPt);

925 (*SegmentXYAtT[fVerb])(fPts, nextSpan.fT, &ePt);

926 SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n" , __FUNCTION__,

927 index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);

928 }

929 #endif

930 return;

931 #else

932 if ((*fSpans)[index].fUnsortableStart) {

933 fUnsortable = true;

934 return;

935 }

936 #endif

937 }

938 #if 1

939 #if DEBUG_UNSORTABLE

940 SkPoint iPt, ePt;

941 (*SegmentXYAtT[fVerb])(fPts, startT, &iPt);

942 (*SegmentXYAtT[fVerb])(fPts, endT, &ePt);

943 SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n ", __FUNCTION__,

944 fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);

945 #endif

946 fUnsortable = true;

947 #endif

948 }

949

950 Segment* segment() const {

951 return const_cast<Segment*>(fSegment);

952 }

953

954 int sign() const {

955 return SkSign32(fStart - fEnd);

956 }

957

958 const SkTDArray<Span>* spans() const {

959 return fSpans;

960 }

961

962 int start() const {

963 return fStart;

964 }

965

966 bool unsortable() const {

967 return fUnsortable;

968 }

969

970 #if DEBUG_ANGLE

971 const SkPoint* pts() const {

972 return fPts;

973 }

974

975 SkPath::Verb verb() const {

976 return fVerb;

977 }

978

979 void debugShow(const SkPoint& a) const {

980 SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);

981 }

982 #endif

983

984 private:

985 const SkPoint* fPts;

986 Cubic fCurvePart;

987 SkPath::Verb fVerb;

988 double fSide;

989 LineParameters fTangent1;

990 const SkTDArray<Span>* fSpans;

991 const Segment* fSegment;

992 int fStart;

993 int fEnd;

994 bool fReversed;

995 mutable bool fUnsortable; // this alone is editable by the less than operato r

996 };

997

998 // Bounds, unlike Rect, does not consider a line to be empty.

999 struct Bounds : public SkRect {

1000 static bool Intersects(const Bounds& a, const Bounds& b) {

1001 return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&

1002 a.fTop <= b.fBottom && b.fTop <= a.fBottom;

1003 }

1004

1005 void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {

1006 if (left < fLeft) {

1007 fLeft = left;

1008 }

1009 if (top < fTop) {

1010 fTop = top;

1011 }

1012 if (right > fRight) {

1013 fRight = right;

1014 }

1015 if (bottom > fBottom) {

1016 fBottom = bottom;

1017 }

1018 }

1019

1020 void add(const Bounds& toAdd) {

1021 add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);

1022 }

1023

1024 void add(const SkPoint& pt) {

1025 if (pt.fX < fLeft) fLeft = pt.fX;

1026 if (pt.fY < fTop) fTop = pt.fY;

1027 if (pt.fX > fRight) fRight = pt.fX;

1028 if (pt.fY > fBottom) fBottom = pt.fY;

1029 }

1030

1031 bool isEmpty() {

1032 return fLeft > fRight \|\| fTop > fBottom

1033 \|\| (fLeft == fRight && fTop == fBottom)

1034 \|\| sk_double_isnan(fLeft) \|\| sk_double_isnan(fRight)

1035 \|\| sk_double_isnan(fTop) \|\| sk_double_isnan(fBottom);

1036 }

1037

1038 void setCubicBounds(const SkPoint a[4]) {

1039 _Rect dRect;

1040 MAKE_CONST_CUBIC(cubic, a);

1041 dRect.setBounds(cubic);

1042 set((float) dRect.left, (float) dRect.top, (float) dRect.right,

1043 (float) dRect.bottom);

1044 }

1045

1046 void setLineBounds(const SkPoint a[2]) {

1047 setPoint(a[0]);

1048 add(a[1]);

1049 }

1050

1051 void setQuadBounds(const SkPoint a[3]) {

1052 MAKE_CONST_QUAD(quad, a);

1053 _Rect dRect;

1054 dRect.setBounds(quad);

1055 set((float) dRect.left, (float) dRect.top, (float) dRect.right,

1056 (float) dRect.bottom);

1057 }

1058

1059 void setPoint(const SkPoint& pt) {

1060 fLeft = fRight = pt.fX;

1061 fTop = fBottom = pt.fY;

1062 }

1063 };

1064

1065 static void (Bounds::*setSegmentBounds[])(const SkPoint[]) = {

1066 NULL,

1067 &Bounds::setLineBounds,

1068 &Bounds::setQuadBounds,

1069 &Bounds::setCubicBounds

1070 };

1071

1072 // OPTIMIZATION: does the following also work, and is it any faster?

1073 // return outerWinding * innerWinding > 0

1074 // \|\| ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))

1075 static bool useInnerWinding(int outerWinding, int innerWinding) {

1076 SkASSERT(outerWinding != SK_MaxS32);

1077 SkASSERT(innerWinding != SK_MaxS32);

1078 int absOut = abs(outerWinding);

1079 int absIn = abs(innerWinding);

1080 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;

1081 #if 0 && DEBUG_WINDING

1082 if (outerWinding * innerWinding < 0) {

1083 SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__,

1084 outerWinding, innerWinding, result ? "true" : "false");

1085 }

1086 #endif

1087 return result;

1088 }

1089

1090 #define F (false) // discard the edge

1091 #define T (true) // keep the edge

1092

1093 static const bool gUnaryActiveEdge[2][2] = {

1094 // from=0 from=1

1095 // to=0,1 to=0,1

1096 {F, T}, {T, F},

1097 };

1098

1099 static const bool gActiveEdge[kShapeOp_Count][2][2][2][2] = {

1100 // miFrom=0 miFrom=1

1101 // miTo=0 miTo=1 miTo=0 miTo=1

1102 // suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1

1103 // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1

1104 {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}} , // mi - su

1105 {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}} , // mi & su

1106 {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}} , // mi \| su

1107 {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}} , // mi ^ su

1108 };

1109

1110 #undef F

1111 #undef T

1112

1113 // wrap path to keep track of whether the contour is initialized and non-empty

1114 class PathWrapper {

1115 public:

1116 PathWrapper(SkPath& path)

1117 : fPathPtr(&path)

1118 , fCloses(0)

1119 , fMoves(0)

1120 {

1121 init();

1122 }

1123

1124 void close() {

1125 if (!fHasMove) {

1126 return;

1127 }

1128 bool callClose = isClosed();

1129 lineTo();

1130 if (fEmpty) {

1131 return;

1132 }

1133 if (callClose) {

1134 #if DEBUG_PATH_CONSTRUCTION

1135 SkDebugf("path.close();\n");

1136 #endif

1137 fPathPtr->close();

1138 fCloses++;

1139 }

1140 init();

1141 }

1142

1143 void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) {

1144 lineTo();

1145 moveTo();

1146 fDefer[1] = pt3;

1147 nudge();

1148 fDefer[0] = fDefer[1];

1149 #if DEBUG_PATH_CONSTRUCTION

1150 SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",

1151 pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);

1152 #endif

1153 fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1 ].fY);

1154 fEmpty = false;

1155 }

1156

1157 void deferredLine(const SkPoint& pt) {

1158 if (pt == fDefer[1]) {

1159 return;

1160 }

1161 if (changedSlopes(pt)) {

1162 lineTo();

1163 fDefer[0] = fDefer[1];

1164 }

1165 fDefer[1] = pt;

1166 }

1167

1168 void deferredMove(const SkPoint& pt) {

1169 fMoved = true;

1170 fHasMove = true;

1171 fEmpty = true;

1172 fDefer[0] = fDefer[1] = pt;

1173 }

1174

1175 void deferredMoveLine(const SkPoint& pt) {

1176 if (!fHasMove) {

1177 deferredMove(pt);

1178 }

1179 deferredLine(pt);

1180 }

1181

1182 bool hasMove() const {

1183 return fHasMove;

1184 }

1185

1186 void init() {

1187 fEmpty = true;

1188 fHasMove = false;

1189 fMoved = false;

1190 }

1191

1192 bool isClosed() const {

1193 return !fEmpty && fFirstPt == fDefer[1];

1194 }

1195

1196 void lineTo() {

1197 if (fDefer[0] == fDefer[1]) {

1198 return;

1199 }

1200 moveTo();

1201 nudge();

1202 fEmpty = false;

1203 #if DEBUG_PATH_CONSTRUCTION

1204 SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY);

1205 #endif

1206 fPathPtr->lineTo(fDefer[1].fX, fDefer[1].fY);

1207 fDefer[0] = fDefer[1];

1208 }

1209

1210 const SkPath* nativePath() const {

1211 return fPathPtr;

1212 }

1213

1214 void nudge() {

1215 if (fEmpty \|\| !AlmostEqualUlps(fDefer[1].fX, fFirstPt.fX)

1216 \|\| !AlmostEqualUlps(fDefer[1].fY, fFirstPt.fY)) {

1217 return;

1218 }

1219 fDefer[1] = fFirstPt;

1220 }

1221

1222 void quadTo(const SkPoint& pt1, const SkPoint& pt2) {

1223 lineTo();

1224 moveTo();

1225 fDefer[1] = pt2;

1226 nudge();

1227 fDefer[0] = fDefer[1];

1228 #if DEBUG_PATH_CONSTRUCTION

1229 SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",

1230 pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);

1231 #endif

1232 fPathPtr->quadTo(pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);

1233 fEmpty = false;

1234 }

1235

1236 bool someAssemblyRequired() const {

1237 return fCloses < fMoves;

1238 }

1239

1240 protected:

1241 bool changedSlopes(const SkPoint& pt) const {

1242 if (fDefer[0] == fDefer[1]) {

1243 return false;

1244 }

1245 SkScalar deferDx = fDefer[1].fX - fDefer[0].fX;

1246 SkScalar deferDy = fDefer[1].fY - fDefer[0].fY;

1247 SkScalar lineDx = pt.fX - fDefer[1].fX;

1248 SkScalar lineDy = pt.fY - fDefer[1].fY;

1249 return deferDx * lineDy != deferDy * lineDx;

1250 }

1251

1252 void moveTo() {

1253 if (!fMoved) {

1254 return;

1255 }

1256 fFirstPt = fDefer[0];

1257 #if DEBUG_PATH_CONSTRUCTION

1258 SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fDefer[0].fX, fDefer[0].fY);

1259 #endif

1260 fPathPtr->moveTo(fDefer[0].fX, fDefer[0].fY);

1261 fMoved = false;

1262 fMoves++;

1263 }

1264

1265 private:

1266 SkPath* fPathPtr;

1267 SkPoint fDefer[2];

1268 SkPoint fFirstPt;

1269 int fCloses;

1270 int fMoves;

1271 bool fEmpty;

1272 bool fHasMove;

1273 bool fMoved;

1274 };

1275

1276 class Segment {

1277 public:

1278 Segment() {

1279 #if DEBUG_DUMP

1280 fID = ++gSegmentID;

1281 #endif

1282 }

1283

1284 bool operator<(const Segment& rh) const {

1285 return fBounds.fTop < rh.fBounds.fTop;

1286 }

1287

1288 bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) {

1289 if (activeAngleInner(index, done, angles)) {

1290 return true;

1291 }

1292 int lesser = index;

1293 while (--lesser >= 0 && equalPoints(index, lesser)) {

1294 if (activeAngleOther(lesser, done, angles)) {

1295 return true;

1296 }

1297 }

1298 lesser = index;

1299 do {

1300 if (activeAngleOther(index, done, angles)) {

1301 return true;

1302 }

1303 } while (++index < fTs.count() && equalPoints(index, lesser));

1304 return false;

1305 }

1306

1307 bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) {

1308 Span* span = &fTs[index];

1309 Segment* other = span->fOther;

1310 int oIndex = span->fOtherIndex;

1311 return other->activeAngleInner(oIndex, done, angles);

1312 }

1313

1314 bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) {

1315 int next = nextExactSpan(index, 1);

1316 if (next > 0) {

1317 Span& upSpan = fTs[index];

1318 if (upSpan.fWindValue \|\| upSpan.fOppValue) {

1319 addAngle(angles, index, next);

1320 if (upSpan.fDone \|\| upSpan.fUnsortableEnd) {

1321 done++;

1322 } else if (upSpan.fWindSum != SK_MinS32) {

1323 return true;

1324 }

1325 } else if (!upSpan.fDone) {

1326 upSpan.fDone = true;

1327 fDoneSpans++;

1328 }

1329 }

1330 int prev = nextExactSpan(index, -1);

1331 // edge leading into junction

1332 if (prev >= 0) {

1333 Span& downSpan = fTs[prev];

1334 if (downSpan.fWindValue \|\| downSpan.fOppValue) {

1335 addAngle(angles, index, prev);

1336 if (downSpan.fDone) {

1337 done++;

1338 } else if (downSpan.fWindSum != SK_MinS32) {

1339 return true;

1340 }

1341 } else if (!downSpan.fDone) {

1342 downSpan.fDone = true;

1343 fDoneSpans++;

1344 }

1345 }

1346 return false;

1347 }

1348

1349 SkPoint activeLeftTop(bool onlySortable, int* firstT) const {

1350 SkASSERT(!done());

1351 SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};

1352 int count = fTs.count();

1353 // see if either end is not done since we want smaller Y of the pair

1354 bool lastDone = true;

1355 bool lastUnsortable = false;

1356 double lastT = -1;

1357 for (int index = 0; index < count; ++index) {

1358 const Span& span = fTs[index];

1359 if (onlySortable && (span.fUnsortableStart \|\| lastUnsortable)) {

1360 goto next;

1361 }

1362 if (span.fDone && lastDone) {

1363 goto next;

1364 }

1365 if (approximately_negative(span.fT - lastT)) {

1366 goto next;

1367 }

1368 {

1369 const SkPoint& xy = xyAtT(&span);

1370 if (topPt.fY > xy.fY \|\| (topPt.fY == xy.fY && topPt.fX > xy.fX)) {

1371 topPt = xy;

1372 if (firstT) {

1373 *firstT = index;

1374 }

1375 }

1376 if (fVerb != SkPath::kLine_Verb && !lastDone) {

1377 SkPoint curveTop = (*SegmentTop[fVerb])(fPts, lastT, span.fT );

1378 if (topPt.fY > curveTop.fY \|\| (topPt.fY == curveTop.fY

1379 && topPt.fX > curveTop.fX)) {

1380 topPt = curveTop;

1381 if (firstT) {

1382 *firstT = index;

1383 }

1384 }

1385 }

1386 lastT = span.fT;

1387 }

1388 next:

1389 lastDone = span.fDone;

1390 lastUnsortable = span.fUnsortableEnd;

1391 }

1392 return topPt;

1393 }

1394

1395 bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, ShapeOp op) {

1396 int sumMiWinding = updateWinding(endIndex, index);

1397 int sumSuWinding = updateOppWinding(endIndex, index);

1398 if (fOperand) {

1399 SkTSwap<int>(sumMiWinding, sumSuWinding);

1400 }

1401 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;

1402 return activeOp(xorMiMask, xorSuMask, index, endIndex, op, sumMiWinding, sumSuWinding,

1403 maxWinding, sumWinding, oppMaxWinding, oppSumWinding);

1404 }

1405

1406 bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, ShapeOp op,

1407 int& sumMiWinding, int& sumSuWinding,

1408 int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWin ding) {

1409 setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,

1410 maxWinding, sumWinding, oppMaxWinding, oppSumWinding);

1411 bool miFrom;

1412 bool miTo;

1413 bool suFrom;

1414 bool suTo;

1415 if (operand()) {

1416 miFrom = (oppMaxWinding & xorMiMask) != 0;

1417 miTo = (oppSumWinding & xorMiMask) != 0;

1418 suFrom = (maxWinding & xorSuMask) != 0;

1419 suTo = (sumWinding & xorSuMask) != 0;

1420 } else {

1421 miFrom = (maxWinding & xorMiMask) != 0;

1422 miTo = (sumWinding & xorMiMask) != 0;

1423 suFrom = (oppMaxWinding & xorSuMask) != 0;

1424 suTo = (oppSumWinding & xorSuMask) != 0;

1425 }

1426 bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];

1427 #if DEBUG_ACTIVE_OP

1428 SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __F UNCTION__,

1429 kShapeOpStr[op], miFrom, miTo, suFrom, suTo, result);

1430 #endif

1431 SkASSERT(result != -1);

1432 return result;

1433 }

1434

1435 bool activeWinding(int index, int endIndex) {

1436 int sumWinding = updateWinding(endIndex, index);

1437 int maxWinding;

1438 return activeWinding(index, endIndex, maxWinding, sumWinding);

1439 }

1440

1441 bool activeWinding(int index, int endIndex, int& maxWinding, int& sumWinding ) {

1442 setUpWinding(index, endIndex, maxWinding, sumWinding);

1443 bool from = maxWinding != 0;

1444 bool to = sumWinding != 0;

1445 bool result = gUnaryActiveEdge[from][to];

1446 SkASSERT(result != -1);

1447 return result;

1448 }

1449

1450 void addAngle(SkTDArray<Angle>& angles, int start, int end) const {

1451 SkASSERT(start != end);

1452 Angle* angle = angles.append();

1453 #if DEBUG_ANGLE

1454 if (angles.count() > 1 && !fTs[start].fTiny) {

1455 SkPoint angle0Pt, newPt;

1456 (*SegmentXYAtT[angles[0].verb()])(angles[0].pts(),

1457 (*angles[0].spans())[angles[0].start()].fT, &angle0Pt);

1458 (*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt);

1459 SkASSERT(AlmostEqualUlps(angle0Pt.fX, newPt.fX));

1460 SkASSERT(AlmostEqualUlps(angle0Pt.fY, newPt.fY));

1461 }

1462 #endif

1463 angle->set(fPts, fVerb, this, start, end, fTs);

1464 }

1465

1466 void addCancelOutsides(double tStart, double oStart, Segment& other,

1467 double oEnd) {

1468 int tIndex = -1;

1469 int tCount = fTs.count();

1470 int oIndex = -1;

1471 int oCount = other.fTs.count();

1472 do {

1473 ++tIndex;

1474 } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tC ount);

1475 int tIndexStart = tIndex;

1476 do {

1477 ++oIndex;

1478 } while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oInde x < oCount);

1479 int oIndexStart = oIndex;

1480 double nextT;

1481 do {

1482 nextT = fTs[++tIndex].fT;

1483 } while (nextT < 1 && approximately_negative(nextT - tStart));

1484 double oNextT;

1485 do {

1486 oNextT = other.fTs[++oIndex].fT;

1487 } while (oNextT < 1 && approximately_negative(oNextT - oStart));

1488 // at this point, spans before and after are at:

1489 // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]

1490 // if tIndexStart == 0, no prior span

1491 // if nextT == 1, no following span

1492

1493 // advance the span with zero winding

1494 // if the following span exists (not past the end, non-zero winding)

1495 // connect the two edges

1496 if (!fTs[tIndexStart].fWindValue) {

1497 if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {

1498 #if DEBUG_CONCIDENT

1499 SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",

1500 __FUNCTION__, fID, other.fID, tIndexStart - 1,

1501 fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,

1502 xyAtT(tIndexStart).fY);

1503 #endif

1504 addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false ,

1505 fTs[tIndexStart].fPt);

1506 }

1507 if (nextT < 1 && fTs[tIndex].fWindValue) {

1508 #if DEBUG_CONCIDENT

1509 SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",

1510 __FUNCTION__, fID, other.fID, tIndex,

1511 fTs[tIndex].fT, xyAtT(tIndex).fX,

1512 xyAtT(tIndex).fY);

1513 #endif

1514 addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false , fTs[tIndex].fPt);

1515 }

1516 } else {

1517 SkASSERT(!other.fTs[oIndexStart].fWindValue);

1518 if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) {

1519 #if DEBUG_CONCIDENT

1520 SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",

1521 __FUNCTION__, fID, other.fID, oIndexStart - 1,

1522 other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX,

1523 other.xyAtT(oIndexStart).fY);

1524 other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex ].fT);

1525 #endif

1526 }

1527 if (oNextT < 1 && other.fTs[oIndex].fWindValue) {

1528 #if DEBUG_CONCIDENT

1529 SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",

1530 __FUNCTION__, fID, other.fID, oIndex,

1531 other.fTs[oIndex].fT, other.xyAtT(oIndex).fX,

1532 other.xyAtT(oIndex).fY);

1533 other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart ].fT);

1534 #endif

1535 }

1536 }

1537 }

1538

1539 void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other,

1540 double oEnd) {

1541 // walk this to outsideTs[0]

1542 // walk other to outsideTs[1]

1543 // if either is > 0, add a pointer to the other, copying adjacent windin g

1544 int tIndex = -1;

1545 int oIndex = -1;

1546 double tStart = outsideTs[0];

1547 double oStart = outsideTs[1];

1548 do {

1549 ++tIndex;

1550 } while (!approximately_negative(tStart - fTs[tIndex].fT));

1551 SkPoint ptStart = fTs[tIndex].fPt;

1552 do {

1553 ++oIndex;

1554 } while (!approximately_negative(oStart - other.fTs[oIndex].fT));

1555 if (tIndex > 0 \|\| oIndex > 0 \|\| fOperand != other.fOperand) {

1556 addTPair(tStart, other, oStart, false, ptStart);

1557 }

1558 tStart = fTs[tIndex].fT;

1559 oStart = other.fTs[oIndex].fT;

1560 do {

1561 double nextT;

1562 do {

1563 nextT = fTs[++tIndex].fT;

1564 } while (approximately_negative(nextT - tStart));

1565 tStart = nextT;

1566 ptStart = fTs[tIndex].fPt;

1567 do {

1568 nextT = other.fTs[++oIndex].fT;

1569 } while (approximately_negative(nextT - oStart));

1570 oStart = nextT;

1571 if (tStart == 1 && oStart == 1 && fOperand == other.fOperand) {

1572 break;

1573 }

1574 addTPair(tStart, other, oStart, false, ptStart);

1575 } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oSta rt));

1576 }

1577

1578 void addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {

1579 init(pts, SkPath::kCubic_Verb, operand, evenOdd);

1580 fBounds.setCubicBounds(pts);

1581 }

1582

1583 /* SkPoint */ void addCurveTo(int start, int end, PathWrapper& path, bool ac tive) const {

1584 SkPoint edge[4];

1585 const SkPoint* ePtr;

1586 int lastT = fTs.count() - 1;

1587 if (lastT < 0 \|\| (start == 0 && end == lastT) \|\| (start == lastT && end == 0)) {

1588 ePtr = fPts;

1589 } else {

1590 // OPTIMIZE? if not active, skip remainder and return xy_at_t(end)

1591 subDivide(start, end, edge);

1592 ePtr = edge;

1593 }

1594 if (active) {

1595 bool reverse = ePtr == fPts && start != 0;

1596 if (reverse) {

1597 path.deferredMoveLine(ePtr[fVerb]);

1598 switch (fVerb) {

1599 case SkPath::kLine_Verb:

1600 path.deferredLine(ePtr[0]);

1601 break;

1602 case SkPath::kQuad_Verb:

1603 path.quadTo(ePtr[1], ePtr[0]);

1604 break;

1605 case SkPath::kCubic_Verb:

1606 path.cubicTo(ePtr[2], ePtr[1], ePtr[0]);

1607 break;

1608 default:

1609 SkASSERT(0);

1610 }

1611 // return ePtr[0];

1612 } else {

1613 path.deferredMoveLine(ePtr[0]);

1614 switch (fVerb) {

1615 case SkPath::kLine_Verb:

1616 path.deferredLine(ePtr[1]);

1617 break;

1618 case SkPath::kQuad_Verb:

1619 path.quadTo(ePtr[1], ePtr[2]);

1620 break;

1621 case SkPath::kCubic_Verb:

1622 path.cubicTo(ePtr[1], ePtr[2], ePtr[3]);

1623 break;

1624 default:

1625 SkASSERT(0);

1626 }

1627 }

1628 }

1629 // return ePtr[fVerb];

1630 }

1631

1632 void addLine(const SkPoint pts[2], bool operand, bool evenOdd) {

1633 init(pts, SkPath::kLine_Verb, operand, evenOdd);

1634 fBounds.set(pts, 2);

1635 }

1636

1637 #if 0

1638 const SkPoint& addMoveTo(int tIndex, PathWrapper& path, bool active) const {

1639 const SkPoint& pt = xyAtT(tIndex);

1640 if (active) {

1641 path.deferredMove(pt);

1642 }

1643 return pt;

1644 }

1645 #endif

1646

1647 // add 2 to edge or out of range values to get T extremes

1648 void addOtherT(int index, double otherT, int otherIndex) {

1649 Span& span = fTs[index];

1650 #if PIN_ADD_T

1651 if (precisely_less_than_zero(otherT)) {

1652 otherT = 0;

1653 } else if (precisely_greater_than_one(otherT)) {

1654 otherT = 1;

1655 }

1656 #endif

1657 span.fOtherT = otherT;

1658 span.fOtherIndex = otherIndex;

1659 }

1660

1661 void addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {

1662 init(pts, SkPath::kQuad_Verb, operand, evenOdd);

1663 fBounds.setQuadBounds(pts);

1664 }

1665

1666 // Defer all coincident edge processing until

1667 // after normal intersections have been computed

1668

1669 // no need to be tricky; insert in normal T order

1670 // resolve overlapping ts when considering coincidence later

1671

1672 // add non-coincident intersection. Resulting edges are sorted in T.

1673 int addT(Segment* other, const SkPoint& pt, double& newT) {

1674 // FIXME: in the pathological case where there is a ton of intercepts,

1675 // binary search?

1676 int insertedAt = -1;

1677 size_t tCount = fTs.count();

1678 #if PIN_ADD_T

1679 // FIXME: only do this pinning here (e.g. this is done also in quad/line intersect)

1680 if (precisely_less_than_zero(newT)) {

1681 newT = 0;

1682 } else if (precisely_greater_than_one(newT)) {

1683 newT = 1;

1684 }

1685 #endif

1686 for (size_t index = 0; index < tCount; ++index) {

1687 // OPTIMIZATION: if there are three or more identical Ts, then

1688 // the fourth and following could be further insertion-sorted so

1689 // that all the edges are clockwise or counterclockwise.

1690 // This could later limit segment tests to the two adjacent

1691 // neighbors, although it doesn't help with determining which

1692 // circular direction to go in.

1693 if (newT < fTs[index].fT) {

1694 insertedAt = index;

1695 break;

1696 }

1697 }

1698 Span* span;

1699 if (insertedAt >= 0) {

1700 span = fTs.insert(insertedAt);

1701 } else {

1702 insertedAt = tCount;

1703 span = fTs.append();

1704 }

1705 span->fT = newT;

1706 span->fOther = other;

1707 span->fPt = pt;

1708 span->fWindSum = SK_MinS32;

1709 span->fOppSum = SK_MinS32;

1710 span->fWindValue = 1;

1711 span->fOppValue = 0;

1712 span->fTiny = false;

1713 span->fLoop = false;

1714 if ((span->fDone = newT == 1)) {

1715 ++fDoneSpans;

1716 }

1717 span->fUnsortableStart = false;

1718 span->fUnsortableEnd = false;

1719 int less = -1;

1720 while (&span[less + 1] - fTs.begin() > 0 && xyAtT(&span[less]) == xyAtT( span)) {

1721 #if 1

1722 if (span[less].fDone) {

1723 break;

1724 }

1725 double tInterval = newT - span[less].fT;

1726 if (precisely_negative(tInterval)) {

1727 break;

1728 }

1729 if (fVerb == SkPath::kCubic_Verb) {

1730 double tMid = newT - tInterval / 2;

1731 _Point midPt;

1732 CubicXYAtT(fPts, tMid, &midPt);

1733 if (!midPt.approximatelyEqual(xyAtT(span))) {

1734 break;

1735 }

1736 }

1737 span[less].fTiny = true;

1738 span[less].fDone = true;

1739 if (approximately_negative(newT - span[less].fT)) {

1740 if (approximately_greater_than_one(newT)) {

1741 span[less].fUnsortableStart = true;

1742 span[less - 1].fUnsortableEnd = true;

1743 }

1744 if (approximately_less_than_zero(span[less].fT)) {

1745 span[less + 1].fUnsortableStart = true;

1746 span[less].fUnsortableEnd = true;

1747 }

1748 }

1749 ++fDoneSpans;

1750 #else

1751 double tInterval = newT - span[less].fT;

1752 if (precisely_negative(tInterval)) {

1753 break;

1754 }

1755 if (fVerb == SkPath::kCubic_Verb) {

1756 double tMid = newT - tInterval / 2;

1757 _Point midPt;

1758 CubicXYAtT(fPts, tMid, &midPt);

1759 if (!midPt.approximatelyEqual(xyAtT(span))) {

1760 break;

1761 }

1762 }

1763 SkASSERT(span[less].fDone == span->fDone);

1764 if (span[less].fT == 0) {

1765 span->fT = newT = 0;

1766 } else {

1767 setSpanT(less, newT);

1768 }

1769 #endif

1770 --less;

1771 }

1772 int more = 1;

1773 while (fTs.end() - &span[more - 1] > 1 && xyAtT(&span[more]) == xyAtT(sp an)) {

1774 #if 1

1775 if (span[more - 1].fDone) {

1776 break;

1777 }

1778 double tEndInterval = span[more].fT - newT;

1779 if (precisely_negative(tEndInterval)) {

1780 break;

1781 }

1782 if (fVerb == SkPath::kCubic_Verb) {

1783 double tMid = newT - tEndInterval / 2;

1784 _Point midEndPt;

1785 CubicXYAtT(fPts, tMid, &midEndPt);

1786 if (!midEndPt.approximatelyEqual(xyAtT(span))) {

1787 break;

1788 }

1789 }

1790 span[more - 1].fTiny = true;

1791 span[more - 1].fDone = true;

1792 if (approximately_negative(span[more].fT - newT)) {

1793 if (approximately_greater_than_one(span[more].fT)) {

1794 span[more + 1].fUnsortableStart = true;

1795 span[more].fUnsortableEnd = true;

1796 }

1797 if (approximately_less_than_zero(newT)) {

1798 span[more].fUnsortableStart = true;

1799 span[more - 1].fUnsortableEnd = true;

1800 }

1801 }

1802 ++fDoneSpans;

1803 #else

1804 double tEndInterval = span[more].fT - newT;

1805 if (precisely_negative(tEndInterval)) {

1806 break;

1807 }

1808 if (fVerb == SkPath::kCubic_Verb) {

1809 double tMid = newT - tEndInterval / 2;

1810 _Point midEndPt;

1811 CubicXYAtT(fPts, tMid, &midEndPt);

1812 if (!midEndPt.approximatelyEqual(xyAtT(span))) {

1813 break;

1814 }

1815 }

1816 SkASSERT(span[more - 1].fDone == span[more].fDone);

1817 if (newT == 0) {

1818 setSpanT(more, 0);

1819 } else {

1820 span->fT = newT = span[more].fT;

1821 }

1822 #endif

1823 ++more;

1824 }

1825 return insertedAt;

1826 }

1827

1828 // set spans from start to end to decrement by one

1829 // note this walks other backwards

1830 // FIMXE: there's probably an edge case that can be constructed where

1831 // two span in one segment are separated by float epsilon on one span but

1832 // not the other, if one segment is very small. For this

1833 // case the counts asserted below may or may not be enough to separate the

1834 // spans. Even if the counts work out, what if the spans aren't correctly

1835 // sorted? It feels better in such a case to match the span's other span

1836 // pointer since both coincident segments must contain the same spans.

1837 void addTCancel(double startT, double endT, Segment& other,

1838 double oStartT, double oEndT) {

1839 SkASSERT(!approximately_negative(endT - startT));

1840 SkASSERT(!approximately_negative(oEndT - oStartT));

1841 bool binary = fOperand != other.fOperand;

1842 int index = 0;

1843 while (!approximately_negative(startT - fTs[index].fT)) {

1844 ++index;

1845 }

1846 int oIndex = other.fTs.count();

1847 while (approximately_positive(other.fTs[--oIndex].fT - oEndT))

1848 ;

1849 double tRatio = (oEndT - oStartT) / (endT - startT);

1850 Span* test = &fTs[index];

1851 Span* oTest = &other.fTs[oIndex];

1852 SkTDArray<double> outsideTs;

1853 SkTDArray<double> oOutsideTs;

1854 do {

1855 bool decrement = test->fWindValue && oTest->fWindValue && !binary;

1856 bool track = test->fWindValue \|\| oTest->fWindValue;

1857 double testT = test->fT;

1858 double oTestT = oTest->fT;

1859 Span* span = test;

1860 do {

1861 if (decrement) {

1862 decrementSpan(span);

1863 } else if (track && span->fT < 1 && oTestT < 1) {

1864 TrackOutside(outsideTs, span->fT, oTestT);

1865 }

1866 span = &fTs[++index];

1867 } while (approximately_negative(span->fT - testT));

1868 Span* oSpan = oTest;

1869 double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;

1870 double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;

1871 SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);

1872 while (approximately_negative(otherTMatchStart - oSpan->fT)

1873 && !approximately_negative(otherTMatchEnd - oSpan->fT)) {

1874 #ifdef SK_DEBUG

1875 SkASSERT(originalWindValue == oSpan->fWindValue);

1876 #endif

1877 if (decrement) {

1878 other.decrementSpan(oSpan);

1879 } else if (track && oSpan->fT < 1 && testT < 1) {

1880 TrackOutside(oOutsideTs, oSpan->fT, testT);

1881 }

1882 if (!oIndex) {

1883 break;

1884 }

1885 oSpan = &other.fTs[--oIndex];

1886 }

1887 test = span;

1888 oTest = oSpan;

1889 } while (!approximately_negative(endT - test->fT));

1890 SkASSERT(!oIndex \|\| approximately_negative(oTest->fT - oStartT));

1891 // FIXME: determine if canceled edges need outside ts added

1892 if (!done() && outsideTs.count()) {

1893 double tStart = outsideTs[0];

1894 double oStart = outsideTs[1];

1895 addCancelOutsides(tStart, oStart, other, oEndT);

1896 int count = outsideTs.count();

1897 if (count > 2) {

1898 double tStart = outsideTs[count - 2];

1899 double oStart = outsideTs[count - 1];

1900 addCancelOutsides(tStart, oStart, other, oEndT);

1901 }

1902 }

1903 if (!other.done() && oOutsideTs.count()) {

1904 double tStart = oOutsideTs[0];

1905 double oStart = oOutsideTs[1];

1906 other.addCancelOutsides(tStart, oStart, *this, endT);

1907 }

1908 }

1909

1910 int addSelfT(Segment* other, const SkPoint& pt, double& newT) {

1911 int result = addT(other, pt, newT);

1912 Span* span = &fTs[result];

1913 span->fLoop = true;

1914 return result;

1915 }

1916

1917 int addUnsortableT(Segment* other, bool start, const SkPoint& pt, double& ne wT) {

1918 int result = addT(other, pt, newT);

1919 Span* span = &fTs[result];

1920 if (start) {

1921 if (result > 0) {

1922 span[result - 1].fUnsortableEnd = true;

1923 }

1924 span[result].fUnsortableStart = true;

1925 } else {

1926 span[result].fUnsortableEnd = true;

1927 if (result + 1 < fTs.count()) {

1928 span[result + 1].fUnsortableStart = true;

1929 }

1930 }

1931 return result;

1932 }

1933

1934 int bumpCoincidentThis(const Span* oTest, bool opp, int index,

1935 SkTDArray<double>& outsideTs) {

1936 int oWindValue = oTest->fWindValue;

1937 int oOppValue = oTest->fOppValue;

1938 if (opp) {

1939 SkTSwap<int>(oWindValue, oOppValue);

1940 }

1941 Span* const test = &fTs[index];

1942 Span* end = test;

1943 const double oStartT = oTest->fT;

1944 do {

1945 if (bumpSpan(end, oWindValue, oOppValue)) {

1946 TrackOutside(outsideTs, end->fT, oStartT);

1947 }

1948 end = &fTs[++index];

1949 } while (approximately_negative(end->fT - test->fT));

1950 return index;

1951 }

1952

1953 // because of the order in which coincidences are resolved, this and other

1954 // may not have the same intermediate points. Compute the corresponding

1955 // intermediate T values (using this as the master, other as the follower)

1956 // and walk other conditionally -- hoping that it catches up in the end

1957 int bumpCoincidentOther(const Span* test, double oEndT, int& oIndex,

1958 SkTDArray<double>& oOutsideTs) {

1959 Span* const oTest = &fTs[oIndex];

1960 Span* oEnd = oTest;

1961 const double startT = test->fT;

1962 const double oStartT = oTest->fT;

1963 while (!approximately_negative(oEndT - oEnd->fT)

1964 && approximately_negative(oEnd->fT - oStartT)) {

1965 zeroSpan(oEnd);

1966 TrackOutside(oOutsideTs, oEnd->fT, startT);

1967 oEnd = &fTs[++oIndex];

1968 }

1969 return oIndex;

1970 }

1971

1972 // FIXME: need to test this case:

1973 // contourA has two segments that are coincident

1974 // contourB has two segments that are coincident in the same place

1975 // each ends up with +2/0 pairs for winding count

1976 // since logic below doesn't transfer count (only increments/decrements) can this be

1977 // resolved to +4/0 ?

1978

1979 // set spans from start to end to increment the greater by one and decrement

1980 // the lesser

1981 void addTCoincident(double startT, double endT, Segment& other, double oStar tT, double oEndT) {

1982 SkASSERT(!approximately_negative(endT - startT));

1983 SkASSERT(!approximately_negative(oEndT - oStartT));

1984 bool opp = fOperand ^ other.fOperand;

1985 int index = 0;

1986 while (!approximately_negative(startT - fTs[index].fT)) {

1987 ++index;

1988 }

1989 int oIndex = 0;

1990 while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) {

1991 ++oIndex;

1992 }

1993 Span* test = &fTs[index];

1994 Span* oTest = &other.fTs[oIndex];

1995 SkTDArray<double> outsideTs;

1996 SkTDArray<double> oOutsideTs;

1997 do {

1998 // if either span has an opposite value and the operands don't match , resolve first

1999 // SkASSERT(!test->fDone \|\| !oTest->fDone);

2000 if (test->fDone \|\| oTest->fDone) {

2001 index = advanceCoincidentThis(oTest, opp, index);

2002 oIndex = other.advanceCoincidentOther(test, oEndT, oIndex);

2003 } else {

2004 index = bumpCoincidentThis(oTest, opp, index, outsideTs);

2005 oIndex = other.bumpCoincidentOther(test, oEndT, oIndex, oOutside Ts);

2006 }

2007 test = &fTs[index];

2008 oTest = &other.fTs[oIndex];

2009 } while (!approximately_negative(endT - test->fT));

2010 SkASSERT(approximately_negative(oTest->fT - oEndT));

2011 SkASSERT(approximately_negative(oEndT - oTest->fT));

2012 if (!done() && outsideTs.count()) {

2013 addCoinOutsides(outsideTs, other, oEndT);

2014 }

2015 if (!other.done() && oOutsideTs.count()) {

2016 other.addCoinOutsides(oOutsideTs, *this, endT);

2017 }

2018 }

2019

2020 // FIXME: this doesn't prevent the same span from being added twice

2021 // fix in caller, SkASSERT here?

2022 void addTPair(double t, Segment& other, double otherT, bool borrowWind, cons t SkPoint& pt) {

2023 int tCount = fTs.count();

2024 for (int tIndex = 0; tIndex < tCount; ++tIndex) {

2025 const Span& span = fTs[tIndex];

2026 if (!approximately_negative(span.fT - t)) {

2027 break;

2028 }

2029 if (approximately_negative(span.fT - t) && span.fOther == &other

2030 && approximately_equal(span.fOtherT, otherT)) {

2031 #if DEBUG_ADD_T_PAIR

2032 SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",

2033 __FUNCTION__, fID, t, other.fID, otherT);

2034 #endif

2035 return;

2036 }

2037 }

2038 #if DEBUG_ADD_T_PAIR

2039 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",

2040 __FUNCTION__, fID, t, other.fID, otherT);

2041 #endif

2042 int insertedAt = addT(&other, pt, t);

2043 int otherInsertedAt = other.addT(this, pt, otherT);

2044 addOtherT(insertedAt, otherT, otherInsertedAt);

2045 other.addOtherT(otherInsertedAt, t, insertedAt);

2046 matchWindingValue(insertedAt, t, borrowWind);

2047 other.matchWindingValue(otherInsertedAt, otherT, borrowWind);

2048 }

2049

2050 void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {

2051 // add edge leading into junction

2052 int min = SkMin32(end, start);

2053 if (fTs[min].fWindValue > 0 \|\| fTs[min].fOppValue > 0) {

2054 addAngle(angles, end, start);

2055 }

2056 // add edge leading away from junction

2057 int step = SkSign32(end - start);

2058 int tIndex = nextExactSpan(end, step);

2059 min = SkMin32(end, tIndex);

2060 if (tIndex >= 0 && (fTs[min].fWindValue > 0 \|\| fTs[min].fOppValue > 0)) {

2061 addAngle(angles, end, tIndex);

2062 }

2063 }

2064

2065 int advanceCoincidentThis(const Span* oTest, bool opp, int index) {

2066 Span* const test = &fTs[index];

2067 Span* end = test;

2068 do {

2069 end = &fTs[++index];

2070 } while (approximately_negative(end->fT - test->fT));

2071 return index;

2072 }

2073

2074 int advanceCoincidentOther(const Span* test, double oEndT, int& oIndex) {

2075 Span* const oTest = &fTs[oIndex];

2076 Span* oEnd = oTest;

2077 const double oStartT = oTest->fT;

2078 while (!approximately_negative(oEndT - oEnd->fT)

2079 && approximately_negative(oEnd->fT - oStartT)) {

2080 oEnd = &fTs[++oIndex];

2081 }

2082 return oIndex;

2083 }

2084

2085 bool betweenTs(int lesser, double testT, int greater) {

2086 if (lesser > greater) {

2087 SkTSwap<int>(lesser, greater);

2088 }

2089 return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);

2090 }

2091

2092 const Bounds& bounds() const {

2093 return fBounds;

2094 }

2095

2096 void buildAngles(int index, SkTDArray<Angle>& angles, bool includeOpp) const {

2097 double referenceT = fTs[index].fT;

2098 int lesser = index;

2099 while (--lesser >= 0 && (includeOpp \|\| fTs[lesser].fOther->fOperand == f Operand)

2100 && precisely_negative(referenceT - fTs[lesser].fT)) {

2101 buildAnglesInner(lesser, angles);

2102 }

2103 do {

2104 buildAnglesInner(index, angles);

2105 } while (++index < fTs.count() && (includeOpp \|\| fTs[index].fOther->fOpe rand == fOperand)

2106 && precisely_negative(fTs[index].fT - referenceT));

2107 }

2108

2109 void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {

2110 const Span* span = &fTs[index];

2111 Segment* other = span->fOther;

2112 // if there is only one live crossing, and no coincidence, continue

2113 // in the same direction

2114 // if there is coincidence, the only choice may be to reverse direction

2115 // find edge on either side of intersection

2116 int oIndex = span->fOtherIndex;

2117 // if done == -1, prior span has already been processed

2118 int step = 1;

2119 int next = other->nextExactSpan(oIndex, step);

2120 if (next < 0) {

2121 step = -step;

2122 next = other->nextExactSpan(oIndex, step);

2123 }

2124 // add candidate into and away from junction

2125 other->addTwoAngles(next, oIndex, angles);

2126 }

2127

2128 int computeSum(int startIndex, int endIndex, bool binary) {

2129 SkTDArray<Angle> angles;

2130 addTwoAngles(startIndex, endIndex, angles);

2131 buildAngles(endIndex, angles, false);

2132 // OPTIMIZATION: check all angles to see if any have computed wind sum

2133 // before sorting (early exit if none)

2134 SkTDArray<Angle*> sorted;

2135 bool sortable = SortAngles(angles, sorted);

2136 #if DEBUG_SORT

2137 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);

2138 #endif

2139 if (!sortable) {

2140 return SK_MinS32;

2141 }

2142 int angleCount = angles.count();

2143 const Angle* angle;

2144 const Segment* base;

2145 int winding;

2146 int oWinding;

2147 int firstIndex = 0;

2148 do {

2149 angle = sorted[firstIndex];

2150 base = angle->segment();

2151 winding = base->windSum(angle);

2152 if (winding != SK_MinS32) {

2153 oWinding = base->oppSum(angle);

2154 break;

2155 }

2156 if (++firstIndex == angleCount) {

2157 return SK_MinS32;

2158 }

2159 } while (true);

2160 // turn winding into contourWinding

2161 int spanWinding = base->spanSign(angle);

2162 bool inner = useInnerWinding(winding + spanWinding, winding);

2163 #if DEBUG_WINDING

2164 SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __ FUNCTION__,

2165 spanWinding, winding, angle->sign(), inner,

2166 inner ? winding + spanWinding : winding);

2167 #endif

2168 if (inner) {

2169 winding += spanWinding;

2170 }

2171 #if DEBUG_SORT

2172 base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding) ;

2173 #endif

2174 int nextIndex = firstIndex + 1;

2175 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;

2176 winding -= base->spanSign(angle);

2177 oWinding -= base->oppSign(angle);

2178 do {

2179 if (nextIndex == angleCount) {

2180 nextIndex = 0;

2181 }

2182 angle = sorted[nextIndex];

2183 Segment* segment = angle->segment();

2184 bool opp = base->fOperand ^ segment->fOperand;

2185 int maxWinding, oMaxWinding;

2186 int spanSign = segment->spanSign(angle);

2187 int oppoSign = segment->oppSign(angle);

2188 if (opp) {

2189 oMaxWinding = oWinding;

2190 oWinding -= spanSign;

2191 maxWinding = winding;

2192 if (oppoSign) {

2193 winding -= oppoSign;

2194 }

2195 } else {

2196 maxWinding = winding;

2197 winding -= spanSign;

2198 oMaxWinding = oWinding;

2199 if (oppoSign) {

2200 oWinding -= oppoSign;

2201 }

2202 }

2203 if (segment->windSum(angle) == SK_MinS32) {

2204 if (opp) {

2205 if (useInnerWinding(oMaxWinding, oWinding)) {

2206 oMaxWinding = oWinding;

2207 }

2208 if (oppoSign && useInnerWinding(maxWinding, winding)) {

2209 maxWinding = winding;

2210 }

2211 (void) segment->markAndChaseWinding(angle, oMaxWinding, maxW inding);

2212 } else {

2213 if (useInnerWinding(maxWinding, winding)) {

2214 maxWinding = winding;

2215 }

2216 if (oppoSign && useInnerWinding(oMaxWinding, oWinding)) {

2217 oMaxWinding = oWinding;

2218 }

2219 (void) segment->markAndChaseWinding(angle, maxWinding,

2220 binary ? oMaxWinding : 0);

2221 }

2222 }

2223 } while (++nextIndex != lastIndex);

2224 int minIndex = SkMin32(startIndex, endIndex);

2225 return windSum(minIndex);

2226 }

2227

2228 int crossedSpanY(const SkPoint& basePt, SkScalar& bestY, double& hitT, bool& hitSomething,

2229 double mid, bool opp, bool current) const {

2230 SkScalar bottom = fBounds.fBottom;

2231 int bestTIndex = -1;

2232 if (bottom <= bestY) {

2233 return bestTIndex;

2234 }

2235 SkScalar top = fBounds.fTop;

2236 if (top >= basePt.fY) {

2237 return bestTIndex;

2238 }

2239 if (fBounds.fLeft > basePt.fX) {

2240 return bestTIndex;

2241 }

2242 if (fBounds.fRight < basePt.fX) {

2243 return bestTIndex;

2244 }

2245 if (fBounds.fLeft == fBounds.fRight) {

2246 // if vertical, and directly above test point, wait for another one

2247 return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestT Index;

2248 }

2249 // intersect ray starting at basePt with edge

2250 Intersections intersections;

2251 // OPTIMIZE: use specialty function that intersects ray with curve,

2252 // returning t values only for curve (we don't care about t on ray)

2253 int pts = (*VSegmentIntersect[fVerb])(fPts, top, bottom, basePt.fX, fals e, intersections);

2254 if (pts == 0 \|\| (current && pts == 1)) {

2255 return bestTIndex;

2256 }

2257 if (current) {

2258 SkASSERT(pts > 1);

2259 int closestIdx = 0;

2260 double closest = fabs(intersections.fT[0][0] - mid);

2261 for (int idx = 1; idx < pts; ++idx) {

2262 double test = fabs(intersections.fT[0][idx] - mid);

2263 if (closest > test) {

2264 closestIdx = idx;

2265 closest = test;

2266 }

2267 }

2268 if (closestIdx < pts - 1) {

2269 intersections.fT[0][closestIdx] = intersections.fT[0][pts - 1];

2270 }

2271 --pts;

2272 }

2273 double bestT = -1;

2274 for (int index = 0; index < pts; ++index) {

2275 double foundT = intersections.fT[0][index];

2276 if (approximately_less_than_zero(foundT)

2277 \|\| approximately_greater_than_one(foundT)) {

2278 continue;

2279 }

2280 SkScalar testY = (*SegmentYAtT[fVerb])(fPts, foundT);

2281 if (approximately_negative(testY - bestY)

2282 \|\| approximately_negative(basePt.fY - testY)) {

2283 continue;

2284 }

2285 if (pts > 1 && fVerb == SkPath::kLine_Verb) {

2286 return SK_MinS32; // if the intersection is edge on, wait for an other one

2287 }

2288 if (fVerb > SkPath::kLine_Verb) {

2289 SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, foundT);

2290 if (approximately_zero(dx)) {

2291 return SK_MinS32; // hit vertical, wait for another one

2292 }

2293 }

2294 bestY = testY;

2295 bestT = foundT;

2296 }

2297 if (bestT < 0) {

2298 return bestTIndex;

2299 }

2300 SkASSERT(bestT >= 0);

2301 SkASSERT(bestT <= 1);

2302 int start;

2303 int end = 0;

2304 do {

2305 start = end;

2306 end = nextSpan(start, 1);

2307 } while (fTs[end].fT < bestT);

2308 // FIXME: see next candidate for a better pattern to find the next start /end pair

2309 while (start + 1 < end && fTs[start].fDone) {

2310 ++start;

2311 }

2312 if (!isCanceled(start)) {

2313 hitT = bestT;

2314 bestTIndex = start;

2315 hitSomething = true;

2316 }

2317 return bestTIndex;

2318 }

2319

2320 void decrementSpan(Span* span) {

2321 SkASSERT(span->fWindValue > 0);

2322 if (--(span->fWindValue) == 0) {

2323 if (!span->fOppValue && !span->fDone) {

2324 span->fDone = true;

2325 ++fDoneSpans;

2326 }

2327 }

2328 }

2329

2330 bool bumpSpan(Span* span, int windDelta, int oppDelta) {

2331 SkASSERT(!span->fDone);

2332 span->fWindValue += windDelta;

2333 SkASSERT(span->fWindValue >= 0);

2334 span->fOppValue += oppDelta;

2335 SkASSERT(span->fOppValue >= 0);

2336 if (fXor) {

2337 span->fWindValue &= 1;

2338 }

2339 if (fOppXor) {

2340 span->fOppValue &= 1;

2341 }

2342 if (!span->fWindValue && !span->fOppValue) {

2343 span->fDone = true;

2344 ++fDoneSpans;

2345 return true;

2346 }

2347 return false;

2348 }

2349

2350 // OPTIMIZE

2351 // when the edges are initially walked, they don't automatically get the pri or and next

2352 // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,

2353 // and would additionally remove the need for similar checks in condition ed ges. It would

2354 // also allow intersection code to assume end of segment intersections (mayb e?)

2355 bool complete() const {

2356 int count = fTs.count();

2357 return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;

2358 }

2359

2360 bool done() const {

2361 SkASSERT(fDoneSpans <= fTs.count());

2362 return fDoneSpans == fTs.count();

2363 }

2364

2365 bool done(int min) const {

2366 return fTs[min].fDone;

2367 }

2368

2369 bool done(const Angle* angle) const {

2370 return done(SkMin32(angle->start(), angle->end()));

2371 }

2372

2373 SkVector dxdy(int index) const {

2374 return (*SegmentDXDYAtT[fVerb])(fPts, fTs[index].fT);

2375 }

2376

2377 SkScalar dy(int index) const {

2378 return (*SegmentDYAtT[fVerb])(fPts, fTs[index].fT);

2379 }

2380

2381 bool equalPoints(int greaterTIndex, int lesserTIndex) {

2382 SkASSERT(greaterTIndex >= lesserTIndex);

2383 double greaterT = fTs[greaterTIndex].fT;

2384 double lesserT = fTs[lesserTIndex].fT;

2385 if (greaterT == lesserT) {

2386 return true;

2387 }

2388 if (!approximately_negative(greaterT - lesserT)) {

2389 return false;

2390 }

2391 return xyAtT(greaterTIndex) == xyAtT(lesserTIndex);

2392 }

2393

2394 /*

2395 The M and S variable name parts stand for the operators.

2396 Mi stands for Minuend (see wiki subtraction, analogous to difference)

2397 Su stands for Subtrahend

2398 The Opp variable name part designates that the value is for the Opposite op erator.

2399 Opposite values result from combining coincident spans.

2400 */

2401

2402 Segment* findNextOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd,

2403 bool& unsortable, ShapeOp op, const int xorMiMask, const int xorSuMa sk) {

2404 const int startIndex = nextStart;

2405 const int endIndex = nextEnd;

2406 SkASSERT(startIndex != endIndex);

2407 const int count = fTs.count();

2408 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0 );

2409 const int step = SkSign32(endIndex - startIndex);

2410 const int end = nextExactSpan(startIndex, step);

2411 SkASSERT(end >= 0);

2412 Span* endSpan = &fTs[end];

2413 Segment* other;

2414 if (isSimple(end)) {

2415 // mark the smaller of startIndex, endIndex done, and all adjacent

2416 // spans with the same T value (but not 'other' spans)

2417 #if DEBUG_WINDING

2418 SkDebugf("%s simple\n", __FUNCTION__);

2419 #endif

2420 int min = SkMin32(startIndex, endIndex);

2421 if (fTs[min].fDone) {

2422 return NULL;

2423 }

2424 markDoneBinary(min);

2425 other = endSpan->fOther;

2426 nextStart = endSpan->fOtherIndex;

2427 double startT = other->fTs[nextStart].fT;

2428 nextEnd = nextStart;

2429 do {

2430 nextEnd += step;

2431 }

2432 while (precisely_zero(startT - other->fTs[nextEnd].fT));

2433 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());

2434 return other;

2435 }

2436 // more than one viable candidate -- measure angles to find best

2437 SkTDArray<Angle> angles;

2438 SkASSERT(startIndex - endIndex != 0);

2439 SkASSERT((startIndex - endIndex < 0) ^ (step < 0));

2440 addTwoAngles(startIndex, end, angles);

2441 buildAngles(end, angles, true);

2442 SkTDArray<Angle*> sorted;

2443 bool sortable = SortAngles(angles, sorted);

2444 int angleCount = angles.count();

2445 int firstIndex = findStartingEdge(sorted, startIndex, end);

2446 SkASSERT(firstIndex >= 0);

2447 #if DEBUG_SORT

2448 debugShowSort(__FUNCTION__, sorted, firstIndex);

2449 #endif

2450 if (!sortable) {

2451 unsortable = true;

2452 return NULL;

2453 }

2454 SkASSERT(sorted[firstIndex]->segment() == this);

2455 #if DEBUG_WINDING

2456 SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,

2457 sorted[firstIndex]->sign());

2458 #endif

2459 int sumMiWinding = updateWinding(endIndex, startIndex);

2460 int sumSuWinding = updateOppWinding(endIndex, startIndex);

2461 if (operand()) {

2462 SkTSwap<int>(sumMiWinding, sumSuWinding);

2463 }

2464 int nextIndex = firstIndex + 1;

2465 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;

2466 const Angle* foundAngle = NULL;

2467 bool foundDone = false;

2468 // iterate through the angle, and compute everyone's winding

2469 Segment* nextSegment;

2470 int activeCount = 0;

2471 do {

2472 SkASSERT(nextIndex != firstIndex);

2473 if (nextIndex == angleCount) {

2474 nextIndex = 0;

2475 }

2476 const Angle* nextAngle = sorted[nextIndex];

2477 nextSegment = nextAngle->segment();

2478 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;

2479 bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextA ngle->start(),

2480 nextAngle->end(), op, sumMiWinding, sumSuWinding,

2481 maxWinding, sumWinding, oppMaxWinding, oppSumWinding);

2482 if (activeAngle) {

2483 ++activeCount;

2484 if (!foundAngle \|\| (foundDone && activeCount & 1)) {

2485 if (nextSegment->tiny(nextAngle)) {

2486 unsortable = true;

2487 return NULL;

2488 }

2489 foundAngle = nextAngle;

2490 foundDone = nextSegment->done(nextAngle) && !nextSegment->ti ny(nextAngle);

2491 }

2492 }

2493 if (nextSegment->done()) {

2494 continue;

2495 }

2496 if (nextSegment->windSum(nextAngle) != SK_MinS32) {

2497 continue;

2498 }

2499 Span* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWi nding,

2500 oppSumWinding, activeAngle, nextAngle);

2501 if (last) {

2502 *chase.append() = last;

2503 #if DEBUG_WINDING

2504 SkDebugf("%s chase.append id=%d\n", __FUNCTION__,

2505 last->fOther->fTs[last->fOtherIndex].fOther->debugID());

2506 #endif

2507 }

2508 } while (++nextIndex != lastIndex);

2509 markDoneBinary(SkMin32(startIndex, endIndex));

2510 if (!foundAngle) {

2511 return NULL;

2512 }

2513 nextStart = foundAngle->start();

2514 nextEnd = foundAngle->end();

2515 nextSegment = foundAngle->segment();

2516

2517 #if DEBUG_WINDING

2518 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",

2519 __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, next End);

2520 #endif

2521 return nextSegment;

2522 }

2523

2524 Segment* findNextWinding(SkTDArray<Span*>& chase, int& nextStart, int& nextE nd,

2525 bool& unsortable) {

2526 const int startIndex = nextStart;

2527 const int endIndex = nextEnd;

2528 SkASSERT(startIndex != endIndex);

2529 const int count = fTs.count();

2530 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0 );

2531 const int step = SkSign32(endIndex - startIndex);

2532 const int end = nextExactSpan(startIndex, step);

2533 SkASSERT(end >= 0);

2534 Span* endSpan = &fTs[end];

2535 Segment* other;

2536 if (isSimple(end)) {

2537 // mark the smaller of startIndex, endIndex done, and all adjacent

2538 // spans with the same T value (but not 'other' spans)

2539 #if DEBUG_WINDING

2540 SkDebugf("%s simple\n", __FUNCTION__);

2541 #endif

2542 int min = SkMin32(startIndex, endIndex);

2543 if (fTs[min].fDone) {

2544 return NULL;

2545 }

2546 markDoneUnary(min);

2547 other = endSpan->fOther;

2548 nextStart = endSpan->fOtherIndex;

2549 double startT = other->fTs[nextStart].fT;

2550 nextEnd = nextStart;

2551 do {

2552 nextEnd += step;

2553 }

2554 while (precisely_zero(startT - other->fTs[nextEnd].fT));

2555 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());

2556 return other;

2557 }

2558 // more than one viable candidate -- measure angles to find best

2559 SkTDArray<Angle> angles;

2560 SkASSERT(startIndex - endIndex != 0);

2561 SkASSERT((startIndex - endIndex < 0) ^ (step < 0));

2562 addTwoAngles(startIndex, end, angles);

2563 buildAngles(end, angles, true);

2564 SkTDArray<Angle*> sorted;

2565 bool sortable = SortAngles(angles, sorted);

2566 int angleCount = angles.count();

2567 int firstIndex = findStartingEdge(sorted, startIndex, end);

2568 SkASSERT(firstIndex >= 0);

2569 #if DEBUG_SORT

2570 debugShowSort(__FUNCTION__, sorted, firstIndex);

2571 #endif

2572 if (!sortable) {

2573 unsortable = true;

2574 return NULL;

2575 }

2576 SkASSERT(sorted[firstIndex]->segment() == this);

2577 #if DEBUG_WINDING

2578 SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,

2579 sorted[firstIndex]->sign());

2580 #endif

2581 int sumWinding = updateWinding(endIndex, startIndex);

2582 int nextIndex = firstIndex + 1;

2583 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;

2584 const Angle* foundAngle = NULL;

2585 bool foundDone = false;

2586 // iterate through the angle, and compute everyone's winding

2587 Segment* nextSegment;

2588 int activeCount = 0;

2589 do {

2590 SkASSERT(nextIndex != firstIndex);

2591 if (nextIndex == angleCount) {

2592 nextIndex = 0;

2593 }

2594 const Angle* nextAngle = sorted[nextIndex];

2595 nextSegment = nextAngle->segment();

2596 int maxWinding;

2597 bool activeAngle = nextSegment->activeWinding(nextAngle->start(), ne xtAngle->end(),

2598 maxWinding, sumWinding);

2599 if (activeAngle) {

2600 ++activeCount;

2601 if (!foundAngle \|\| (foundDone && activeCount & 1)) {

2602 if (nextSegment->tiny(nextAngle)) {

2603 unsortable = true;

2604 return NULL;

2605 }

2606 foundAngle = nextAngle;

2607 foundDone = nextSegment->done(nextAngle);

2608 }

2609 }

2610 if (nextSegment->done()) {

2611 continue;

2612 }

2613 if (nextSegment->windSum(nextAngle) != SK_MinS32) {

2614 continue;

2615 }

2616 Span* last = nextSegment->markAngle(maxWinding, sumWinding, activeAn gle, nextAngle);

2617 if (last) {

2618 *chase.append() = last;

2619 #if DEBUG_WINDING

2620 SkDebugf("%s chase.append id=%d\n", __FUNCTION__,

2621 last->fOther->fTs[last->fOtherIndex].fOther->debugID());

2622 #endif

2623 }

2624 } while (++nextIndex != lastIndex);

2625 markDoneUnary(SkMin32(startIndex, endIndex));

2626 if (!foundAngle) {

2627 return NULL;

2628 }

2629 nextStart = foundAngle->start();

2630 nextEnd = foundAngle->end();

2631 nextSegment = foundAngle->segment();

2632 #if DEBUG_WINDING

2633 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",

2634 __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, next End);

2635 #endif

2636 return nextSegment;

2637 }

2638

2639 Segment* findNextXor(int& nextStart, int& nextEnd, bool& unsortable) {

2640 const int startIndex = nextStart;

2641 const int endIndex = nextEnd;

2642 SkASSERT(startIndex != endIndex);

2643 int count = fTs.count();

2644 SkASSERT(startIndex < endIndex ? startIndex < count - 1

2645 : startIndex > 0);

2646 int step = SkSign32(endIndex - startIndex);

2647 int end = nextExactSpan(startIndex, step);

2648 SkASSERT(end >= 0);

2649 Span* endSpan = &fTs[end];

2650 Segment* other;

2651 if (isSimple(end)) {

2652 #if DEBUG_WINDING

2653 SkDebugf("%s simple\n", __FUNCTION__);

2654 #endif

2655 int min = SkMin32(startIndex, endIndex);

2656 if (fTs[min].fDone) {

2657 return NULL;

2658 }

2659 markDone(min, 1);

2660 other = endSpan->fOther;

2661 nextStart = endSpan->fOtherIndex;

2662 double startT = other->fTs[nextStart].fT;

2663 #if 01 // FIXME: I don't know why the logic here is difference from the winding case

2664 SkDEBUGCODE(bool firstLoop = true;)

2665 if ((approximately_less_than_zero(startT) && step < 0)

2666 \|\| (approximately_greater_than_one(startT) && step > 0)) {

2667 step = -step;

2668 SkDEBUGCODE(firstLoop = false;)

2669 }

2670 do {

2671 #endif

2672 nextEnd = nextStart;

2673 do {

2674 nextEnd += step;

2675 }

2676 while (precisely_zero(startT - other->fTs[nextEnd].fT));

2677 #if 01

2678 if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) {

2679 break;

2680 }

2681 #ifdef SK_DEBUG

2682 SkASSERT(firstLoop);

2683 #endif

2684 SkDEBUGCODE(firstLoop = false;)

2685 step = -step;

2686 } while (true);

2687 #endif

2688 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());

2689 return other;

2690 }

2691 SkTDArray<Angle> angles;

2692 SkASSERT(startIndex - endIndex != 0);

2693 SkASSERT((startIndex - endIndex < 0) ^ (step < 0));

2694 addTwoAngles(startIndex, end, angles);

2695 buildAngles(end, angles, false);

2696 SkTDArray<Angle*> sorted;

2697 bool sortable = SortAngles(angles, sorted);

2698 if (!sortable) {

2699 unsortable = true;

2700 #if DEBUG_SORT

2701 debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIn dex, end), 0, 0);

2702 #endif

2703 return NULL;

2704 }

2705 int angleCount = angles.count();

2706 int firstIndex = findStartingEdge(sorted, startIndex, end);

2707 SkASSERT(firstIndex >= 0);

2708 #if DEBUG_SORT

2709 debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0);

2710 #endif

2711 SkASSERT(sorted[firstIndex]->segment() == this);

2712 int nextIndex = firstIndex + 1;

2713 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;

2714 const Angle* foundAngle = NULL;

2715 bool foundDone = false;

2716 Segment* nextSegment;

2717 int activeCount = 0;

2718 do {

2719 SkASSERT(nextIndex != firstIndex);

2720 if (nextIndex == angleCount) {

2721 nextIndex = 0;

2722 }

2723 const Angle* nextAngle = sorted[nextIndex];

2724 nextSegment = nextAngle->segment();

2725 ++activeCount;

2726 if (!foundAngle \|\| (foundDone && activeCount & 1)) {

2727 if (nextSegment->tiny(nextAngle)) {

2728 unsortable = true;

2729 return NULL;

2730 }

2731 foundAngle = nextAngle;

2732 foundDone = nextSegment->done(nextAngle);

2733 }

2734 if (nextSegment->done()) {

2735 continue;

2736 }

2737 } while (++nextIndex != lastIndex);

2738 markDone(SkMin32(startIndex, endIndex), 1);

2739 if (!foundAngle) {

2740 return NULL;

2741 }

2742 nextStart = foundAngle->start();

2743 nextEnd = foundAngle->end();

2744 nextSegment = foundAngle->segment();

2745 #if DEBUG_WINDING

2746 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",

2747 __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, next End);

2748 #endif

2749 return nextSegment;

2750 }

2751

2752 int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) {

2753 int angleCount = sorted.count();

2754 int firstIndex = -1;

2755 for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {

2756 const Angle* angle = sorted[angleIndex];

2757 if (angle->segment() == this && angle->start() == end &&

2758 angle->end() == start) {

2759 firstIndex = angleIndex;

2760 break;

2761 }

2762 }

2763 return firstIndex;

2764 }

2765

2766 // FIXME: this is tricky code; needs its own unit test

2767 // note that fOtherIndex isn't computed yet, so it can't be used here

2768 void findTooCloseToCall() {

2769 int count = fTs.count();

2770 if (count < 3) { // require t=0, x, 1 at minimum

2771 return;

2772 }

2773 int matchIndex = 0;

2774 int moCount;

2775 Span* match;

2776 Segment* mOther;

2777 do {

2778 match = &fTs[matchIndex];

2779 mOther = match->fOther;

2780 // FIXME: allow quads, cubics to be near coincident?

2781 if (mOther->fVerb == SkPath::kLine_Verb) {

2782 moCount = mOther->fTs.count();

2783 if (moCount >= 3) {

2784 break;

2785 }

2786 }

2787 if (++matchIndex >= count) {

2788 return;

2789 }

2790 } while (true); // require t=0, x, 1 at minimum

2791 // OPTIMIZATION: defer matchPt until qualifying toCount is found?

2792 const SkPoint* matchPt = &xyAtT(match);

2793 // look for a pair of nearby T values that map to the same (x,y) value

2794 // if found, see if the pair of other segments share a common point. If

2795 // so, the span from here to there is coincident.

2796 for (int index = matchIndex + 1; index < count; ++index) {

2797 Span* test = &fTs[index];

2798 if (test->fDone) {

2799 continue;

2800 }

2801 Segment* tOther = test->fOther;

2802 if (tOther->fVerb != SkPath::kLine_Verb) {

2803 continue; // FIXME: allow quads, cubics to be near coincident?

2804 }

2805 int toCount = tOther->fTs.count();

2806 if (toCount < 3) { // require t=0, x, 1 at minimum

2807 continue;

2808 }

2809 const SkPoint* testPt = &xyAtT(test);

2810 if (matchPt != testPt) {

2811 matchIndex = index;

2812 moCount = toCount;

2813 match = test;

2814 mOther = tOther;

2815 matchPt = testPt;

2816 continue;

2817 }

2818 int moStart = -1;

2819 int moEnd = -1;

2820 double moStartT, moEndT;

2821 for (int moIndex = 0; moIndex < moCount; ++moIndex) {

2822 Span& moSpan = mOther->fTs[moIndex];

2823 if (moSpan.fDone) {

2824 continue;

2825 }

2826 if (moSpan.fOther == this) {

2827 if (moSpan.fOtherT == match->fT) {

2828 moStart = moIndex;

2829 moStartT = moSpan.fT;

2830 }

2831 continue;

2832 }

2833 if (moSpan.fOther == tOther) {

2834 if (tOther->windValueAt(moSpan.fOtherT) == 0) {

2835 moStart = -1;

2836 break;

2837 }

2838 SkASSERT(moEnd == -1);

2839 moEnd = moIndex;

2840 moEndT = moSpan.fT;

2841 }

2842 }

2843 if (moStart < 0 \|\| moEnd < 0) {

2844 continue;

2845 }

2846 // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test

2847 if (approximately_equal(moStartT, moEndT)) {

2848 continue;

2849 }

2850 int toStart = -1;

2851 int toEnd = -1;

2852 double toStartT, toEndT;

2853 for (int toIndex = 0; toIndex < toCount; ++toIndex) {

2854 Span& toSpan = tOther->fTs[toIndex];

2855 if (toSpan.fDone) {

2856 continue;

2857 }

2858 if (toSpan.fOther == this) {

2859 if (toSpan.fOtherT == test->fT) {

2860 toStart = toIndex;

2861 toStartT = toSpan.fT;

2862 }

2863 continue;

2864 }

2865 if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) {

2866 if (mOther->windValueAt(toSpan.fOtherT) == 0) {

2867 moStart = -1;

2868 break;

2869 }

2870 SkASSERT(toEnd == -1);

2871 toEnd = toIndex;

2872 toEndT = toSpan.fT;

2873 }

2874 }

2875 // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test

2876 if (toStart <= 0 \|\| toEnd <= 0) {

2877 continue;

2878 }

2879 if (approximately_equal(toStartT, toEndT)) {

2880 continue;

2881 }

2882 // test to see if the segment between there and here is linear

2883 if (!mOther->isLinear(moStart, moEnd)

2884 \|\| !tOther->isLinear(toStart, toEnd)) {

2885 continue;

2886 }

2887 bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1;

2888 if (flipped) {

2889 mOther->addTCancel(moStartT, moEndT, *tOther, toEndT, toStartT);

2890 } else {

2891 mOther->addTCoincident(moStartT, moEndT, *tOther, toStartT, toEn dT);

2892 }

2893 }

2894 }

2895

2896 // FIXME: either:

2897 // a) mark spans with either end unsortable as done, or

2898 // b) rewrite findTop / findTopSegment / findTopContour to iterate further

2899 // when encountering an unsortable span

2900

2901 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)

2902 // and use more concise logic like the old edge walker code?

2903 // FIXME: this needs to deal with coincident edges

2904 Segment* findTop(int& tIndex, int& endIndex, bool& unsortable, bool onlySort able) {

2905 // iterate through T intersections and return topmost

2906 // topmost tangent from y-min to first pt is closer to horizontal

2907 SkASSERT(!done());

2908 int firstT = -1;

2909 /* SkPoint topPt = */ activeLeftTop(onlySortable, &firstT);

2910 if (firstT < 0) {

2911 unsortable = true;

2912 firstT = 0;

2913 while (fTs[firstT].fDone) {

2914 SkASSERT(firstT < fTs.count());

2915 ++firstT;

2916 }

2917 tIndex = firstT;

2918 endIndex = nextExactSpan(firstT, 1);

2919 return this;

2920 }

2921 // sort the edges to find the leftmost

2922 int step = 1;

2923 int end = nextSpan(firstT, step);

2924 if (end == -1) {

2925 step = -1;

2926 end = nextSpan(firstT, step);

2927 SkASSERT(end != -1);

2928 }

2929 // if the topmost T is not on end, or is three-way or more, find left

2930 // look for left-ness from tLeft to firstT (matching y of other)

2931 SkTDArray<Angle> angles;

2932 SkASSERT(firstT - end != 0);

2933 addTwoAngles(end, firstT, angles);

2934 buildAngles(firstT, angles, true);

2935 SkTDArray<Angle*> sorted;

2936 bool sortable = SortAngles(angles, sorted);

2937 int first = SK_MaxS32;

2938 SkScalar top = SK_ScalarMax;

2939 int count = sorted.count();

2940 for (int index = 0; index < count; ++index) {

2941 const Angle* angle = sorted[index];

2942 Segment* next = angle->segment();

2943 Bounds bounds;

2944 next->subDivideBounds(angle->end(), angle->start(), bounds);

2945 if (approximately_greater(top, bounds.fTop)) {

2946 top = bounds.fTop;

2947 first = index;

2948 }

2949 }

2950 SkASSERT(first < SK_MaxS32);

2951 #if DEBUG_SORT // \|\| DEBUG_SWAP_TOP

2952 sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0);

2953 #endif

2954 if (onlySortable && !sortable) {

2955 unsortable = true;

2956 return NULL;

2957 }

2958 // skip edges that have already been processed

2959 firstT = first - 1;

2960 Segment* leftSegment;

2961 do {

2962 if (++firstT == count) {

2963 firstT = 0;

2964 }

2965 const Angle* angle = sorted[firstT];

2966 SkASSERT(!onlySortable \|\| !angle->unsortable());

2967 leftSegment = angle->segment();

2968 tIndex = angle->end();

2969 endIndex = angle->start();

2970 } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);

2971 if (leftSegment->verb() >= SkPath::kQuad_Verb) {

2972 if (!leftSegment->clockwise(tIndex, endIndex)) {

2973 bool swap = leftSegment->verb() == SkPath::kQuad_Verb

2974 \|\| (!leftSegment->monotonic_in_y(tIndex, endIndex)

2975 && !leftSegment->serpentine(tIndex, endIndex));

2976 #if DEBUG_SWAP_TOP

2977 SkDebugf("%s swap=%d serpentine=%d controls_contained_by_ends=%d \n", __FUNCTION__,

2978 swap,

2979 leftSegment->serpentine(tIndex, endIndex),

2980 leftSegment->controls_contained_by_ends(tIndex, endIndex ),

2981 leftSegment->monotonic_in_y(tIndex, endIndex));

2982 #endif

2983 if (swap) {

2984 // FIXME: I doubt it makes sense to (necessarily) swap if the edge was n ot the first

2985 // sorted but merely the first not already processed (i.e., not done)

2986 SkTSwap(tIndex, endIndex);

2987 }

2988 }

2989 }

2990 SkASSERT(!leftSegment->fTs[SkMin32(tIndex, endIndex)].fTiny);

2991 return leftSegment;

2992 }

2993

2994 // FIXME: not crazy about this

2995 // when the intersections are performed, the other index is into an

2996 // incomplete array. As the array grows, the indices become incorrect

2997 // while the following fixes the indices up again, it isn't smart about

2998 // skipping segments whose indices are already correct

2999 // assuming we leave the code that wrote the index in the first place

3000 void fixOtherTIndex() {

3001 int iCount = fTs.count();

3002 for (int i = 0; i < iCount; ++i) {

3003 Span& iSpan = fTs[i];

3004 double oT = iSpan.fOtherT;

3005 Segment* other = iSpan.fOther;

3006 int oCount = other->fTs.count();

3007 for (int o = 0; o < oCount; ++o) {

3008 Span& oSpan = other->fTs[o];

3009 if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == i Span.fT) {

3010 iSpan.fOtherIndex = o;

3011 break;

3012 }

3013 }

3014 }

3015 }

3016

3017 void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd ) {

3018 fDoneSpans = 0;

3019 fOperand = operand;

3020 fXor = evenOdd;

3021 fPts = pts;

3022 fVerb = verb;

3023 }

3024

3025 void initWinding(int start, int end) {

3026 int local = spanSign(start, end);

3027 int oppLocal = oppSign(start, end);

3028 (void) markAndChaseWinding(start, end, local, oppLocal);

3029 // OPTIMIZATION: the reverse mark and chase could skip the first marking

3030 (void) markAndChaseWinding(end, start, local, oppLocal);

3031 }

3032

3033 void initWinding(int start, int end, int winding, int oppWinding) {

3034 int local = spanSign(start, end);

3035 if (local * winding >= 0) {

3036 winding += local;

3037 }

3038 int oppLocal = oppSign(start, end);

3039 if (oppLocal * oppWinding >= 0) {

3040 oppWinding += oppLocal;

3041 }

3042 (void) markAndChaseWinding(start, end, winding, oppWinding);

3043 }

3044

3045 /*

3046 when we start with a vertical intersect, we try to use the dx to determine if th e edge is to

3047 the left or the right of vertical. This determines if we need to add the span's

3048 sign or not. However, this isn't enough.

3049 If the supplied sign (winding) is zero, then we didn't hit another vertical span , so dx is needed.

3050 If there was a winding, then it may or may not need adjusting. If the span the w inding was borrowed

3051 from has the same x direction as this span, the winding should change. If the dx is opposite, then

3052 the same winding is shared by both.

3053 */

3054 void initWinding(int start, int end, double tHit, int winding, SkScalar hitD x, int oppWind,

3055 SkScalar hitOppDx) {

3056 SkASSERT(hitDx \|\| !winding);

3057 SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, tHit);

3058 SkASSERT(dx);

3059 int windVal = windValue(SkMin32(start, end));

3060 #if DEBUG_WINDING_AT_T

3061 SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, win ding,

3062 hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal );

3063 #endif

3064 if (!winding) {

3065 winding = dx < 0 ? windVal : -windVal;

3066 } else if (winding * dx < 0) {

3067 int sideWind = winding + (dx < 0 ? windVal : -windVal);

3068 if (abs(winding) < abs(sideWind)) {

3069 winding = sideWind;

3070 }

3071 }

3072 #if DEBUG_WINDING_AT_T

3073 SkDebugf(" winding=%d\n", winding);

3074 #endif

3075 int oppLocal = oppSign(start, end);

3076 SkASSERT(hitOppDx \|\| !oppWind \|\| !oppLocal);

3077 int oppWindVal = oppValue(SkMin32(start, end));

3078 if (!oppWind) {

3079 oppWind = dx < 0 ? oppWindVal : -oppWindVal;

3080 } else if (hitOppDx * dx >= 0) {

3081 int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);

3082 if (abs(oppWind) < abs(oppSideWind)) {

3083 oppWind = oppSideWind;

3084 }

3085 }

3086 (void) markAndChaseWinding(start, end, winding, oppWind);

3087 }

3088

3089 bool intersected() const {

3090 return fTs.count() > 0;

3091 }

3092

3093 bool isCanceled(int tIndex) const {

3094 return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;

3095 }

3096

3097 bool isConnected(int startIndex, int endIndex) const {

3098 return fTs[startIndex].fWindSum != SK_MinS32

3099 \|\| fTs[endIndex].fWindSum != SK_MinS32;

3100 }

3101

3102 bool isHorizontal() const {

3103 return fBounds.fTop == fBounds.fBottom;

3104 }

3105

3106 bool isLinear(int start, int end) const {

3107 if (fVerb == SkPath::kLine_Verb) {

3108 return true;

3109 }

3110 if (fVerb == SkPath::kQuad_Verb) {

3111 SkPoint qPart[3];

3112 QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart);

3113 return QuadIsLinear(qPart);

3114 } else {

3115 SkASSERT(fVerb == SkPath::kCubic_Verb);

3116 SkPoint cPart[4];

3117 CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart);

3118 return CubicIsLinear(cPart);

3119 }

3120 }

3121

3122 // OPTIMIZE: successive calls could start were the last leaves off

3123 // or calls could specialize to walk forwards or backwards

3124 bool isMissing(double startT) const {

3125 size_t tCount = fTs.count();

3126 for (size_t index = 0; index < tCount; ++index) {

3127 if (approximately_zero(startT - fTs[index].fT)) {

3128 return false;

3129 }

3130 }

3131 return true;

3132 }

3133

3134 bool isSimple(int end) const {

3135 int count = fTs.count();

3136 if (count == 2) {

3137 return true;

3138 }

3139 double t = fTs[end].fT;

3140 if (approximately_less_than_zero(t)) {

3141 return !approximately_less_than_zero(fTs[1].fT);

3142 }

3143 if (approximately_greater_than_one(t)) {

3144 return !approximately_greater_than_one(fTs[count - 2].fT);

3145 }

3146 return false;

3147 }

3148

3149 bool isVertical() const {

3150 return fBounds.fLeft == fBounds.fRight;

3151 }

3152

3153 bool isVertical(int start, int end) const {

3154 return (*SegmentVertical[fVerb])(fPts, start, end);

3155 }

3156

3157 SkScalar leftMost(int start, int end) const {

3158 return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);

3159 }

3160

3161 // this span is excluded by the winding rule -- chase the ends

3162 // as long as they are unambiguous to mark connections as done

3163 // and give them the same winding value

3164 Span* markAndChaseDone(const Angle* angle, int winding) {

3165 int index = angle->start();

3166 int endIndex = angle->end();

3167 return markAndChaseDone(index, endIndex, winding);

3168 }

3169

3170 Span* markAndChaseDone(int index, int endIndex, int winding) {

3171 int step = SkSign32(endIndex - index);

3172 int min = SkMin32(index, endIndex);

3173 markDone(min, winding);

3174 Span* last;

3175 Segment* other = this;

3176 while ((other = other->nextChase(index, step, min, last))) {

3177 other->markDone(min, winding);

3178 }

3179 return last;

3180 }

3181

3182 Span* markAndChaseDoneBinary(const Angle* angle, int winding, int oppWinding ) {

3183 int index = angle->start();

3184 int endIndex = angle->end();

3185 int step = SkSign32(endIndex - index);

3186 int min = SkMin32(index, endIndex);

3187 markDoneBinary(min, winding, oppWinding);

3188 Span* last;

3189 Segment* other = this;

3190 while ((other = other->nextChase(index, step, min, last))) {

3191 other->markDoneBinary(min, winding, oppWinding);

3192 }

3193 return last;

3194 }

3195

3196 Span* markAndChaseDoneBinary(int index, int endIndex) {

3197 int step = SkSign32(endIndex - index);

3198 int min = SkMin32(index, endIndex);

3199 markDoneBinary(min);

3200 Span* last;

3201 Segment* other = this;

3202 while ((other = other->nextChase(index, step, min, last))) {

3203 if (other->done()) {

3204 return NULL;

3205 }

3206 other->markDoneBinary(min);

3207 }

3208 return last;

3209 }

3210

3211 Span* markAndChaseDoneUnary(int index, int endIndex) {

3212 int step = SkSign32(endIndex - index);

3213 int min = SkMin32(index, endIndex);

3214 markDoneUnary(min);

3215 Span* last;

3216 Segment* other = this;

3217 while ((other = other->nextChase(index, step, min, last))) {

3218 if (other->done()) {

3219 return NULL;

3220 }

3221 other->markDoneUnary(min);

3222 }

3223 return last;

3224 }

3225

3226 Span* markAndChaseDoneUnary(const Angle* angle, int winding) {

3227 int index = angle->start();

3228 int endIndex = angle->end();

3229 return markAndChaseDone(index, endIndex, winding);

3230 }

3231

3232 Span* markAndChaseWinding(const Angle* angle, const int winding) {

3233 int index = angle->start();

3234 int endIndex = angle->end();

3235 int step = SkSign32(endIndex - index);

3236 int min = SkMin32(index, endIndex);

3237 markWinding(min, winding);

3238 Span* last;

3239 Segment* other = this;

3240 while ((other = other->nextChase(index, step, min, last))) {

3241 if (other->fTs[min].fWindSum != SK_MinS32) {

3242 SkASSERT(other->fTs[min].fWindSum == winding);

3243 return NULL;

3244 }

3245 other->markWinding(min, winding);

3246 }

3247 return last;

3248 }

3249

3250 Span* markAndChaseWinding(int index, int endIndex, int winding, int oppWindi ng) {

3251 int min = SkMin32(index, endIndex);

3252 int step = SkSign32(endIndex - index);

3253 markWinding(min, winding, oppWinding);

3254 Span* last;

3255 Segment* other = this;

3256 while ((other = other->nextChase(index, step, min, last))) {

3257 if (other->fTs[min].fWindSum != SK_MinS32) {

3258 SkASSERT(other->fTs[min].fWindSum == winding \|\| other->fTs[min]. fLoop);

3259 return NULL;

3260 }

3261 other->markWinding(min, winding, oppWinding);

3262 }

3263 return last;

3264 }

3265

3266 Span* markAndChaseWinding(const Angle* angle, int winding, int oppWinding) {

3267 int start = angle->start();

3268 int end = angle->end();

3269 return markAndChaseWinding(start, end, winding, oppWinding);

3270 }

3271

3272 Span* markAngle(int maxWinding, int sumWinding, bool activeAngle, const Angl e* angle) {

3273 SkASSERT(angle->segment() == this);

3274 if (useInnerWinding(maxWinding, sumWinding)) {

3275 maxWinding = sumWinding;

3276 }

3277 Span* last;

3278 if (activeAngle) {

3279 last = markAndChaseWinding(angle, maxWinding);

3280 } else {

3281 last = markAndChaseDoneUnary(angle, maxWinding);

3282 }

3283 return last;

3284 }

3285

3286 Span* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSu mWinding,

3287 bool activeAngle, const Angle* angle) {

3288 SkASSERT(angle->segment() == this);

3289 if (useInnerWinding(maxWinding, sumWinding)) {

3290 maxWinding = sumWinding;

3291 }

3292 if (oppMaxWinding != oppSumWinding && useInnerWinding(oppMaxWinding, opp SumWinding)) {

3293 oppMaxWinding = oppSumWinding;

3294 }

3295 Span* last;

3296 if (activeAngle) {

3297 last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);

3298 } else {

3299 last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding);

3300 }

3301 return last;

3302 }

3303

3304 // FIXME: this should also mark spans with equal (x,y)

3305 // This may be called when the segment is already marked done. While this

3306 // wastes time, it shouldn't do any more than spin through the T spans.

3307 // OPTIMIZATION: abort on first done found (assuming that this code is

3308 // always called to mark segments done).

3309 void markDone(int index, int winding) {

3310 // SkASSERT(!done());

3311 SkASSERT(winding);

3312 double referenceT = fTs[index].fT;

3313 int lesser = index;

3314 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {

3315 markOneDone(__FUNCTION__, lesser, winding);

3316 }

3317 do {

3318 markOneDone(__FUNCTION__, index, winding);

3319 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - ref erenceT));

3320 }

3321

3322 void markDoneBinary(int index, int winding, int oppWinding) {

3323 // SkASSERT(!done());

3324 SkASSERT(winding \|\| oppWinding);

3325 double referenceT = fTs[index].fT;

3326 int lesser = index;

3327 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {

3328 markOneDoneBinary(__FUNCTION__, lesser, winding, oppWinding);

3329 }

3330 do {

3331 markOneDoneBinary(__FUNCTION__, index, winding, oppWinding);

3332 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - ref erenceT));

3333 }

3334

3335 void markDoneBinary(int index) {

3336 double referenceT = fTs[index].fT;

3337 int lesser = index;

3338 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {

3339 markOneDoneBinary(__FUNCTION__, lesser);

3340 }

3341 do {

3342 markOneDoneBinary(__FUNCTION__, index);

3343 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - ref erenceT));

3344 }

3345

3346 void markDoneUnary(int index, int winding) {

3347 // SkASSERT(!done());

3348 SkASSERT(winding);

3349 double referenceT = fTs[index].fT;

3350 int lesser = index;

3351 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {

3352 markOneDoneUnary(__FUNCTION__, lesser, winding);

3353 }

3354 do {

3355 markOneDoneUnary(__FUNCTION__, index, winding);

3356 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - ref erenceT));

3357 }

3358

3359 void markDoneUnary(int index) {

3360 double referenceT = fTs[index].fT;

3361 int lesser = index;

3362 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {

3363 markOneDoneUnary(__FUNCTION__, lesser);

3364 }

3365 do {

3366 markOneDoneUnary(__FUNCTION__, index);

3367 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - ref erenceT));

3368 }

3369

3370 void markOneDone(const char* funName, int tIndex, int winding) {

3371 Span* span = markOneWinding(funName, tIndex, winding);

3372 if (!span) {

3373 return;

3374 }

3375 span->fDone = true;

3376 fDoneSpans++;

3377 }

3378

3379 void markOneDoneBinary(const char* funName, int tIndex) {

3380 Span* span = verifyOneWinding(funName, tIndex);

3381 if (!span) {

3382 return;

3383 }

3384 span->fDone = true;

3385 fDoneSpans++;

3386 }

3387

3388 void markOneDoneBinary(const char* funName, int tIndex, int winding, int opp Winding) {

3389 Span* span = markOneWinding(funName, tIndex, winding, oppWinding);

3390 if (!span) {

3391 return;

3392 }

3393 span->fDone = true;

3394 fDoneSpans++;

3395 }

3396

3397 void markOneDoneUnary(const char* funName, int tIndex) {

3398 Span* span = verifyOneWindingU(funName, tIndex);

3399 if (!span) {

3400 return;

3401 }

3402 span->fDone = true;

3403 fDoneSpans++;

3404 }

3405

3406 void markOneDoneUnary(const char* funName, int tIndex, int winding) {

3407 Span* span = markOneWinding(funName, tIndex, winding);

3408 if (!span) {

3409 return;

3410 }

3411 span->fDone = true;

3412 fDoneSpans++;

3413 }

3414

3415 Span* markOneWinding(const char* funName, int tIndex, int winding) {

3416 Span& span = fTs[tIndex];

3417 if (span.fDone) {

3418 return NULL;

3419 }

3420 #if DEBUG_MARK_DONE

3421 debugShowNewWinding(funName, span, winding);

3422 #endif

3423 SkASSERT(span.fWindSum == SK_MinS32 \|\| span.fWindSum == winding);

3424 #ifdef SK_DEBUG

3425 SkASSERT(abs(winding) <= gDebugMaxWindSum);

3426 #endif

3427 span.fWindSum = winding;

3428 return &span;

3429 }

3430

3431 Span* markOneWinding(const char* funName, int tIndex, int winding, int oppWi nding) {

3432 Span& span = fTs[tIndex];

3433 if (span.fDone) {

3434 return NULL;

3435 }

3436 #if DEBUG_MARK_DONE

3437 debugShowNewWinding(funName, span, winding, oppWinding);

3438 #endif

3439 SkASSERT(span.fWindSum == SK_MinS32 \|\| span.fWindSum == winding);

3440 #ifdef SK_DEBUG

3441 SkASSERT(abs(winding) <= gDebugMaxWindSum);

3442 #endif

3443 span.fWindSum = winding;

3444 SkASSERT(span.fOppSum == SK_MinS32 \|\| span.fOppSum == oppWinding);

3445 #ifdef SK_DEBUG

3446 SkASSERT(abs(oppWinding) <= gDebugMaxWindSum);

3447 #endif

3448 span.fOppSum = oppWinding;

3449 return &span;

3450 }

3451

3452 bool controls_contained_by_ends(int tStart, int tEnd) const {

3453 if (fVerb != SkPath::kCubic_Verb) {

3454 return false;

3455 }

3456 MAKE_CONST_CUBIC(aCubic, fPts);

3457 Cubic dst;

3458 sub_divide(aCubic, fTs[tStart].fT, fTs[tEnd].fT, dst);

3459 return ::controls_contained_by_ends(dst);

3460 }

3461

3462 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-lis t-of-polygon-points-are-in-clockwise-order

3463 bool clockwise(int tStart, int tEnd) const {

3464 SkASSERT(fVerb != SkPath::kLine_Verb);

3465 SkPoint edge[4];

3466 subDivide(tStart, tEnd, edge);

3467 double sum = (edge[0].fX - edge[fVerb].fX) * (edge[0].fY + edge[fVerb].f Y);

3468 if (fVerb == SkPath::kCubic_Verb) {

3469 SkScalar lesser = SkTMin(edge[0].fY, edge[3].fY);

3470 if (edge[1].fY < lesser && edge[2].fY < lesser) {

3471 _Line tangent1 = { {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1 ].fY} };

3472 _Line tangent2 = { {edge[2].fX, edge[2].fY}, {edge[3].fX, edge[3 ].fY} };

3473 if (testIntersect(tangent1, tangent2)) {

3474 SkPoint topPt = CubicTop(fPts, fTs[tStart].fT, fTs[tEnd].fT) ;

3475 sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY);

3476 sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY);

3477 return sum <= 0;

3478 }

3479 }

3480 }

3481 for (int idx = 0; idx < fVerb; ++idx){

3482 sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[ idx].fY);

3483 }

3484 return sum <= 0;

3485 }

3486

3487 bool monotonic_in_y(int tStart, int tEnd) const {

3488 if (fVerb != SkPath::kCubic_Verb) {

3489 return false;

3490 }

3491 MAKE_CONST_CUBIC(aCubic, fPts);

3492 Cubic dst;

3493 sub_divide(aCubic, fTs[tStart].fT, fTs[tEnd].fT, dst);

3494 return ::monotonic_in_y(dst);

3495 }

3496

3497 bool serpentine(int tStart, int tEnd) const {

3498 if (fVerb != SkPath::kCubic_Verb) {

3499 return false;

3500 }

3501 MAKE_CONST_CUBIC(aCubic, fPts);

3502 Cubic dst;

3503 sub_divide(aCubic, fTs[tStart].fT, fTs[tEnd].fT, dst);

3504 return ::serpentine(dst);

3505 }

3506

3507 Span* verifyOneWinding(const char* funName, int tIndex) {

3508 Span& span = fTs[tIndex];

3509 if (span.fDone) {

3510 return NULL;

3511 }

3512 #if DEBUG_MARK_DONE

3513 debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);

3514 #endif

3515 SkASSERT(span.fWindSum != SK_MinS32);

3516 SkASSERT(span.fOppSum != SK_MinS32);

3517 return &span;

3518 }

3519

3520 Span* verifyOneWindingU(const char* funName, int tIndex) {

3521 Span& span = fTs[tIndex];

3522 if (span.fDone) {

3523 return NULL;

3524 }

3525 #if DEBUG_MARK_DONE

3526 debugShowNewWinding(funName, span, span.fWindSum);

3527 #endif

3528 SkASSERT(span.fWindSum != SK_MinS32);

3529 return &span;

3530 }

3531

3532 // note that just because a span has one end that is unsortable, that's

3533 // not enough to mark it done. The other end may be sortable, allowing the

3534 // span to be added.

3535 // FIXME: if abs(start - end) > 1, mark intermediates as unsortable on both ends

3536 void markUnsortable(int start, int end) {

3537 Span* span = &fTs[start];

3538 if (start < end) {

3539 #if DEBUG_UNSORTABLE

3540 debugShowNewWinding(__FUNCTION__, *span, 0);

3541 #endif

3542 span->fUnsortableStart = true;

3543 } else {

3544 --span;

3545 #if DEBUG_UNSORTABLE

3546 debugShowNewWinding(__FUNCTION__, *span, 0);

3547 #endif

3548 span->fUnsortableEnd = true;

3549 }

3550 if (!span->fUnsortableStart \|\| !span->fUnsortableEnd \|\| span->fDone) {

3551 return;

3552 }

3553 span->fDone = true;

3554 fDoneSpans++;

3555 }

3556

3557 void markWinding(int index, int winding) {

3558 // SkASSERT(!done());

3559 SkASSERT(winding);

3560 double referenceT = fTs[index].fT;

3561 int lesser = index;

3562 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {

3563 markOneWinding(__FUNCTION__, lesser, winding);

3564 }

3565 do {

3566 markOneWinding(__FUNCTION__, index, winding);

3567 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - refe renceT));

3568 }

3569

3570 void markWinding(int index, int winding, int oppWinding) {

3571 // SkASSERT(!done());

3572 SkASSERT(winding \|\| oppWinding);

3573 double referenceT = fTs[index].fT;

3574 int lesser = index;

3575 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {

3576 markOneWinding(__FUNCTION__, lesser, winding, oppWinding);

3577 }

3578 do {

3579 markOneWinding(__FUNCTION__, index, winding, oppWinding);

3580 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - refe renceT));

3581 }

3582

3583 void matchWindingValue(int tIndex, double t, bool borrowWind) {

3584 int nextDoorWind = SK_MaxS32;

3585 int nextOppWind = SK_MaxS32;

3586 if (tIndex > 0) {

3587 const Span& below = fTs[tIndex - 1];

3588 if (approximately_negative(t - below.fT)) {

3589 nextDoorWind = below.fWindValue;

3590 nextOppWind = below.fOppValue;

3591 }

3592 }

3593 if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {

3594 const Span& above = fTs[tIndex + 1];

3595 if (approximately_negative(above.fT - t)) {

3596 nextDoorWind = above.fWindValue;

3597 nextOppWind = above.fOppValue;

3598 }

3599 }

3600 if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {

3601 const Span& below = fTs[tIndex - 1];

3602 nextDoorWind = below.fWindValue;

3603 nextOppWind = below.fOppValue;

3604 }

3605 if (nextDoorWind != SK_MaxS32) {

3606 Span& newSpan = fTs[tIndex];

3607 newSpan.fWindValue = nextDoorWind;

3608 newSpan.fOppValue = nextOppWind;

3609 if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {

3610 newSpan.fDone = true;

3611 ++fDoneSpans;

3612 }

3613 }

3614 }

3615

3616 bool moreHorizontal(int index, int endIndex, bool& unsortable) const {

3617 // find bounds

3618 Bounds bounds;

3619 bounds.setPoint(xyAtT(index));

3620 bounds.add(xyAtT(endIndex));

3621 SkScalar width = bounds.width();

3622 SkScalar height = bounds.height();

3623 if (width > height) {

3624 if (approximately_negative(width)) {

3625 unsortable = true; // edge is too small to resolve meaningfully

3626 }

3627 return false;

3628 } else {

3629 if (approximately_negative(height)) {

3630 unsortable = true; // edge is too small to resolve meaningfully

3631 }

3632 return true;

3633 }

3634 }

3635

3636 // return span if when chasing, two or more radiating spans are not done

3637 // OPTIMIZATION: ? multiple spans is detected when there is only one valid

3638 // candidate and the remaining spans have windValue == 0 (canceled by

3639 // coincidence). The coincident edges could either be removed altogether,

3640 // or this code could be more complicated in detecting this case. Worth it?

3641 bool multipleSpans(int end) const {

3642 return end > 0 && end < fTs.count() - 1;

3643 }

3644

3645 bool nextCandidate(int& start, int& end) const {

3646 while (fTs[end].fDone) {

3647 if (fTs[end].fT == 1) {

3648 return false;

3649 }

3650 ++end;

3651 }

3652 start = end;

3653 end = nextExactSpan(start, 1);

3654 return true;

3655 }

3656

3657 Segment* nextChase(int& index, const int step, int& min, Span*& last) {

3658 int end = nextExactSpan(index, step);

3659 SkASSERT(end >= 0);

3660 if (multipleSpans(end)) {

3661 last = &fTs[end];

3662 return NULL;

3663 }

3664 const Span& endSpan = fTs[end];

3665 Segment* other = endSpan.fOther;

3666 index = endSpan.fOtherIndex;

3667 SkASSERT(index >= 0);

3668 int otherEnd = other->nextExactSpan(index, step);

3669 SkASSERT(otherEnd >= 0);

3670 min = SkMin32(index, otherEnd);

3671 return other;

3672 }

3673

3674 // This has callers for two different situations: one establishes the end

3675 // of the current span, and one establishes the beginning of the next span

3676 // (thus the name). When this is looking for the end of the current span,

3677 // coincidence is found when the beginning Ts contain -step and the end

3678 // contains step. When it is looking for the beginning of the next, the

3679 // first Ts found can be ignored and the last Ts should contain -step.

3680 // OPTIMIZATION: probably should split into two functions

3681 int nextSpan(int from, int step) const {

3682 const Span& fromSpan = fTs[from];

3683 int count = fTs.count();

3684 int to = from;

3685 while (step > 0 ? ++to < count : --to >= 0) {

3686 const Span& span = fTs[to];

3687 if (approximately_zero(span.fT - fromSpan.fT)) {

3688 continue;

3689 }

3690 return to;

3691 }

3692 return -1;

3693 }

3694

3695 // FIXME

3696 // this returns at any difference in T, vs. a preset minimum. It may be

3697 // that all callers to nextSpan should use this instead.

3698 // OPTIMIZATION splitting this into separate loops for up/down steps

3699 // would allow using precisely_negative instead of precisely_zero

3700 int nextExactSpan(int from, int step) const {

3701 const Span& fromSpan = fTs[from];

3702 int count = fTs.count();

3703 int to = from;

3704 while (step > 0 ? ++to < count : --to >= 0) {

3705 const Span& span = fTs[to];

3706 if (precisely_zero(span.fT - fromSpan.fT)) {

3707 continue;

3708 }

3709 return to;

3710 }

3711 return -1;

3712 }

3713

3714 bool operand() const {

3715 return fOperand;

3716 }

3717

3718 int oppSign(const Angle* angle) const {

3719 SkASSERT(angle->segment() == this);

3720 return oppSign(angle->start(), angle->end());

3721 }

3722

3723 int oppSign(int startIndex, int endIndex) const {

3724 int result = startIndex < endIndex ? -fTs[startIndex].fOppValue

3725 : fTs[endIndex].fOppValue;

3726 #if DEBUG_WIND_BUMP

3727 SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);

3728 #endif

3729 return result;

3730 }

3731

3732 int oppSum(int tIndex) const {

3733 return fTs[tIndex].fOppSum;

3734 }

3735

3736 int oppSum(const Angle* angle) const {

3737 int lesser = SkMin32(angle->start(), angle->end());

3738 return fTs[lesser].fOppSum;

3739 }

3740

3741 int oppValue(int tIndex) const {

3742 return fTs[tIndex].fOppValue;

3743 }

3744

3745 int oppValue(const Angle* angle) const {

3746 int lesser = SkMin32(angle->start(), angle->end());

3747 return fTs[lesser].fOppValue;

3748 }

3749

3750 const SkPoint* pts() const {

3751 return fPts;

3752 }

3753

3754 void reset() {

3755 init(NULL, (SkPath::Verb) -1, false, false);

3756 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);

3757 fTs.reset();

3758 }

3759

3760 void setOppXor(bool isOppXor) {

3761 fOppXor = isOppXor;

3762 }

3763

3764 void setSpanT(int index, double t) {

3765 Span& span = fTs[index];

3766 span.fT = t;

3767 span.fOther->fTs[span.fOtherIndex].fOtherT = t;

3768 }

3769

3770 void setUpWinding(int index, int endIndex, int& maxWinding, int& sumWinding) {

3771 int deltaSum = spanSign(index, endIndex);

3772 maxWinding = sumWinding;

3773 sumWinding = sumWinding -= deltaSum;

3774 }

3775

3776 void setUpWindings(int index, int endIndex, int& sumMiWinding, int& sumSuWin ding,

3777 int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWin ding) {

3778 int deltaSum = spanSign(index, endIndex);

3779 int oppDeltaSum = oppSign(index, endIndex);

3780 if (operand()) {

3781 maxWinding = sumSuWinding;

3782 sumWinding = sumSuWinding -= deltaSum;

3783 oppMaxWinding = sumMiWinding;

3784 oppSumWinding = sumMiWinding -= oppDeltaSum;

3785 } else {

3786 maxWinding = sumMiWinding;

3787 sumWinding = sumMiWinding -= deltaSum;

3788 oppMaxWinding = sumSuWinding;

3789 oppSumWinding = sumSuWinding -= oppDeltaSum;

3790 }

3791 }

3792

3793 // This marks all spans unsortable so that this info is available for early

3794 // exclusion in find top and others. This could be optimized to only mark

3795 // adjacent spans that unsortable. However, this makes it difficult to later

3796 // determine starting points for edge detection in find top and the like.

3797 static bool SortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleLis t) {

3798 bool sortable = true;

3799 int angleCount = angles.count();

3800 int angleIndex;

3801 angleList.setReserve(angleCount);

3802 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {

3803 Angle& angle = angles[angleIndex];

3804 *angleList.append() = &angle;

3805 sortable &= !angle.unsortable();

3806 }

3807 if (sortable) {

3808 QSort<Angle>(angleList.begin(), angleList.end() - 1);

3809 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {

3810 if (angles[angleIndex].unsortable()) {

3811 sortable = false;

3812 break;

3813 }

3814 }

3815 }

3816 if (!sortable) {

3817 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {

3818 Angle& angle = angles[angleIndex];

3819 angle.segment()->markUnsortable(angle.start(), angle.end());

3820 }

3821 }

3822 return sortable;

3823 }

3824

3825 // OPTIMIZATION: mark as debugging only if used solely by tests

3826 const Span& span(int tIndex) const {

3827 return fTs[tIndex];

3828 }

3829

3830 int spanSign(const Angle* angle) const {

3831 SkASSERT(angle->segment() == this);

3832 return spanSign(angle->start(), angle->end());

3833 }

3834

3835 int spanSign(int startIndex, int endIndex) const {

3836 int result = startIndex < endIndex ? -fTs[startIndex].fWindValue

3837 : fTs[endIndex].fWindValue;

3838 #if DEBUG_WIND_BUMP

3839 SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);

3840 #endif

3841 return result;

3842 }

3843

3844 void subDivide(int start, int end, SkPoint edge[4]) const {

3845 edge[0] = fTs[start].fPt;

3846 edge[fVerb] = fTs[end].fPt;

3847 if (fVerb == SkPath::kQuad_Verb \|\| fVerb == SkPath::kCubic_Verb) {

3848 _Point sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[fVerb].fX, edge[fV erb].fY }};

3849 if (fVerb == SkPath::kQuad_Verb) {

3850 MAKE_CONST_QUAD(aQuad, fPts);

3851 edge[1] = sub_divide(aQuad, sub[0], sub[1], fTs[start].fT, fTs[e nd].fT).asSkPoint();

3852 } else {

3853 MAKE_CONST_CUBIC(aCubic, fPts);

3854 sub_divide(aCubic, sub[0], sub[1], fTs[start].fT, fTs[end].fT, s ub);

3855 edge[1] = sub[0].asSkPoint();

3856 edge[2] = sub[1].asSkPoint();

3857 }

3858 }

3859 }

3860

3861 void subDivideBounds(int start, int end, Bounds& bounds) const {

3862 SkPoint edge[4];

3863 subDivide(start, end, edge);

3864 (bounds.*setSegmentBounds[fVerb])(edge);

3865 }

3866

3867 // OPTIMIZATION: mark as debugging only if used solely by tests

3868 double t(int tIndex) const {

3869 return fTs[tIndex].fT;

3870 }

3871

3872 double tAtMid(int start, int end, double mid) const {

3873 return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;

3874 }

3875

3876 bool tiny(const Angle* angle) const {

3877 int start = angle->start();

3878 int end = angle->end();

3879 const Span& mSpan = fTs[SkMin32(start, end)];

3880 return mSpan.fTiny;

3881 }

3882

3883 static void TrackOutside(SkTDArray<double>& outsideTs, double end,

3884 double start) {

3885 int outCount = outsideTs.count();

3886 if (outCount == 0 \|\| !approximately_negative(end - outsideTs[outCount - 2])) {

3887 *outsideTs.append() = end;

3888 *outsideTs.append() = start;

3889 }

3890 }

3891

3892 void undoneSpan(int& start, int& end) {

3893 size_t tCount = fTs.count();

3894 size_t index;

3895 for (index = 0; index < tCount; ++index) {

3896 if (!fTs[index].fDone) {

3897 break;

3898 }

3899 }

3900 SkASSERT(index < tCount - 1);

3901 start = index;

3902 double startT = fTs[index].fT;

3903 while (approximately_negative(fTs[++index].fT - startT))

3904 SkASSERT(index < tCount);

3905 SkASSERT(index < tCount);

3906 end = index;

3907 }

3908

3909 bool unsortable(int index) const {

3910 return fTs[index].fUnsortableStart \|\| fTs[index].fUnsortableEnd;

3911 }

3912

3913 void updatePts(const SkPoint pts[]) {

3914 fPts = pts;

3915 }

3916

3917 int updateOppWinding(int index, int endIndex) const {

3918 int lesser = SkMin32(index, endIndex);

3919 int oppWinding = oppSum(lesser);

3920 int oppSpanWinding = oppSign(index, endIndex);

3921 if (oppSpanWinding && useInnerWinding(oppWinding - oppSpanWinding, oppWi nding)

3922 && oppWinding != SK_MaxS32) {

3923 oppWinding -= oppSpanWinding;

3924 }

3925 return oppWinding;

3926 }

3927

3928 int updateOppWinding(const Angle* angle) const {

3929 int startIndex = angle->start();

3930 int endIndex = angle->end();

3931 return updateOppWinding(endIndex, startIndex);

3932 }

3933

3934 int updateOppWindingReverse(const Angle* angle) const {

3935 int startIndex = angle->start();

3936 int endIndex = angle->end();

3937 return updateOppWinding(startIndex, endIndex);

3938 }

3939

3940 int updateWinding(int index, int endIndex) const {

3941 int lesser = SkMin32(index, endIndex);

3942 int winding = windSum(lesser);

3943 int spanWinding = spanSign(index, endIndex);

3944 if (winding && useInnerWinding(winding - spanWinding, winding) && windin g != SK_MaxS32) {

3945 winding -= spanWinding;

3946 }

3947 return winding;

3948 }

3949

3950 int updateWinding(const Angle* angle) const {

3951 int startIndex = angle->start();

3952 int endIndex = angle->end();

3953 return updateWinding(endIndex, startIndex);

3954 }

3955

3956 int updateWindingReverse(const Angle* angle) const {

3957 int startIndex = angle->start();

3958 int endIndex = angle->end();

3959 return updateWinding(startIndex, endIndex);

3960 }

3961

3962 SkPath::Verb verb() const {

3963 return fVerb;

3964 }

3965

3966 int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar& dx) const {

3967 if (approximately_zero(tHit - t(tIndex))) { // if we hit the end of a sp an, disregard

3968 return SK_MinS32;

3969 }

3970 int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);

3971 SkASSERT(winding != SK_MinS32);

3972 int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);

3973 #if DEBUG_WINDING_AT_T

3974 SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal );

3975 #endif

3976 // see if a + change in T results in a +/- change in X (compute x'(T))

3977 dx = (*SegmentDXAtT[fVerb])(fPts, tHit);

3978 if (fVerb > SkPath::kLine_Verb && approximately_zero(dx)) {

3979 dx = fPts[2].fX - fPts[1].fX - dx;

3980 }

3981 if (dx == 0) {

3982 #if DEBUG_WINDING_AT_T

3983 SkDebugf(" dx=0 winding=SK_MinS32\n");

3984 #endif

3985 return SK_MinS32;

3986 }

3987 if (winding * dx > 0) { // if same signs, result is negative

3988 winding += dx > 0 ? -windVal : windVal;

3989 }

3990 #if DEBUG_WINDING_AT_T

3991 SkDebugf(" dx=%c winding=%d\n", dx > 0 ? '+' : '-', winding);

3992 #endif

3993 return winding;

3994 }

3995

3996 int windSum(int tIndex) const {

3997 return fTs[tIndex].fWindSum;

3998 }

3999

4000 int windSum(const Angle* angle) const {

4001 int start = angle->start();

4002 int end = angle->end();

4003 int index = SkMin32(start, end);

4004 return windSum(index);

4005 }

4006

4007 int windValue(int tIndex) const {

4008 return fTs[tIndex].fWindValue;

4009 }

4010

4011 int windValue(const Angle* angle) const {

4012 int start = angle->start();

4013 int end = angle->end();

4014 int index = SkMin32(start, end);

4015 return windValue(index);

4016 }

4017

4018 int windValueAt(double t) const {

4019 int count = fTs.count();

4020 for (int index = 0; index < count; ++index) {

4021 if (fTs[index].fT == t) {

4022 return fTs[index].fWindValue;

4023 }

4024 }

4025 SkASSERT(0);

4026 return 0;

4027 }

4028

4029 SkScalar xAtT(int index) const {

4030 return xAtT(&fTs[index]);

4031 }

4032

4033 SkScalar xAtT(const Span* span) const {

4034 return xyAtT(span).fX;

4035 }

4036

4037 const SkPoint& xyAtT(int index) const {

4038 return xyAtT(&fTs[index]);

4039 }

4040

4041 const SkPoint& xyAtT(const Span* span) const {

4042 if (SkScalarIsNaN(span->fPt.fX)) {

4043 SkASSERT(0); // make sure this path is never used

4044 if (span->fT == 0) {

4045 span->fPt = fPts[0];

4046 } else if (span->fT == 1) {

4047 span->fPt = fPts[fVerb];

4048 } else {

4049 (*SegmentXYAtT[fVerb])(fPts, span->fT, &span->fPt);

4050 }

4051 }

4052 return span->fPt;

4053 }

4054

4055 // used only by right angle winding finding

4056 void xyAtT(double mid, SkPoint& pt) const {

4057 (*SegmentXYAtT[fVerb])(fPts, mid, &pt);

4058 }

4059

4060 SkScalar yAtT(int index) const {

4061 return yAtT(&fTs[index]);

4062 }

4063

4064 SkScalar yAtT(const Span* span) const {

4065 return xyAtT(span).fY;

4066 }

4067

4068 void zeroCoincidentOpp(Span* oTest, int index) {

4069 Span* const test = &fTs[index];

4070 Span* end = test;

4071 do {

4072 end->fOppValue = 0;

4073 end = &fTs[++index];

4074 } while (approximately_negative(end->fT - test->fT));

4075 }

4076

4077 void zeroCoincidentOther(Span* test, const double tRatio, const double oEndT , int oIndex) {

4078 Span* const oTest = &fTs[oIndex];

4079 Span* oEnd = oTest;

4080 const double startT = test->fT;

4081 const double oStartT = oTest->fT;

4082 double otherTMatch = (test->fT - startT) * tRatio + oStartT;

4083 while (!approximately_negative(oEndT - oEnd->fT)

4084 && approximately_negative(oEnd->fT - otherTMatch)) {

4085 oEnd->fOppValue = 0;

4086 oEnd = &fTs[++oIndex];

4087 }

4088 }

4089

4090 void zeroSpan(Span* span) {

4091 SkASSERT(span->fWindValue > 0 \|\| span->fOppValue > 0);

4092 span->fWindValue = 0;

4093 span->fOppValue = 0;

4094 SkASSERT(!span->fDone);

4095 span->fDone = true;

4096 ++fDoneSpans;

4097 }

4098

4099 #if DEBUG_DUMP

4100 void dump() const {

4101 const char className[] = "Segment";

4102 const int tab = 4;

4103 for (int i = 0; i < fTs.count(); ++i) {

4104 SkPoint out;

4105 (*SegmentXYAtT[fVerb])(fPts, t(i), &out);

4106 SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"

4107 " otherT=%1.9g windSum=%d\n",

4108 tab + sizeof(className), className, fID,

4109 kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,

4110 fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum);

4111 }

4112 SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)",

4113 tab + sizeof(className), className, fID,

4114 fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);

4115 }

4116 #endif

4117

4118 #if DEBUG_CONCIDENT

4119 // SkASSERT if pair has not already been added

4120 void debugAddTPair(double t, const Segment& other, double otherT) const {

4121 for (int i = 0; i < fTs.count(); ++i) {

4122 if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == o therT) {

4123 return;

4124 }

4125 }

4126 SkASSERT(0);

4127 }

4128 #endif

4129

4130 #if DEBUG_DUMP

4131 int debugID() const {

4132 return fID;

4133 }

4134 #endif

4135

4136 #if DEBUG_WINDING

4137 void debugShowSums() const {

4138 SkDebugf("%s id=%d (%1.9g,%1.9g %1.9g,%1.9g)", __FUNCTION__, fID,

4139 fPts[0].fX, fPts[0].fY, fPts[fVerb].fX, fPts[fVerb].fY);

4140 for (int i = 0; i < fTs.count(); ++i) {

4141 const Span& span = fTs[i];

4142 SkDebugf(" [t=%1.3g %1.9g,%1.9g w=", span.fT, xAtT(&span), yAtT(&spa n));

4143 if (span.fWindSum == SK_MinS32) {

4144 SkDebugf("?");

4145 } else {

4146 SkDebugf("%d", span.fWindSum);

4147 }

4148 SkDebugf("]");

4149 }

4150 SkDebugf("\n");

4151 }

4152 #endif

4153

4154 #if DEBUG_CONCIDENT

4155 void debugShowTs() const {

4156 SkDebugf("%s id=%d", __FUNCTION__, fID);

4157 int lastWind = -1;

4158 int lastOpp = -1;

4159 double lastT = -1;

4160 int i;

4161 for (i = 0; i < fTs.count(); ++i) {

4162 bool change = lastT != fTs[i].fT \|\| lastWind != fTs[i].fWindValue

4163 \|\| lastOpp != fTs[i].fOppValue;

4164 if (change && lastWind >= 0) {

4165 SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",

4166 lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastO pp);

4167 }

4168 if (change) {

4169 SkDebugf(" [o=%d", fTs[i].fOther->fID);

4170 lastWind = fTs[i].fWindValue;

4171 lastOpp = fTs[i].fOppValue;

4172 lastT = fTs[i].fT;

4173 } else {

4174 SkDebugf(",%d", fTs[i].fOther->fID);

4175 }

4176 }

4177 if (i <= 0) {

4178 return;

4179 }

4180 SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",

4181 lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);

4182 if (fOperand) {

4183 SkDebugf(" operand");

4184 }

4185 if (done()) {

4186 SkDebugf(" done");

4187 }

4188 SkDebugf("\n");

4189 }

4190 #endif

4191

4192 #if DEBUG_ACTIVE_SPANS

4193 void debugShowActiveSpans() const {

4194 if (done()) {

4195 return;

4196 }

4197 #if DEBUG_ACTIVE_SPANS_SHORT_FORM

4198 int lastId = -1;

4199 double lastT = -1;

4200 #endif

4201 for (int i = 0; i < fTs.count(); ++i) {

4202 SkASSERT(&fTs[i] == &fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOther->

4203 fTs[fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOtherIndex]);

4204 if (fTs[i].fDone) {

4205 continue;

4206 }

4207 #if DEBUG_ACTIVE_SPANS_SHORT_FORM

4208 if (lastId == fID && lastT == fTs[i].fT) {

4209 continue;

4210 }

4211 lastId = fID;

4212 lastT = fTs[i].fT;

4213 #endif

4214 SkDebugf("%s id=%d", __FUNCTION__, fID);

4215 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);

4216 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {

4217 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);

4218 }

4219 const Span* span = &fTs[i];

4220 SkDebugf(") t=%1.9g (%1.9g,%1.9g)", fTs[i].fT,

4221 xAtT(span), yAtT(span));

4222 int iEnd = i + 1;

4223 while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd]. fT)) {

4224 ++iEnd;

4225 }

4226 SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT);

4227 const Segment* other = fTs[i].fOther;

4228 SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",

4229 other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);

4230 if (fTs[i].fWindSum == SK_MinS32) {

4231 SkDebugf("?");

4232 } else {

4233 SkDebugf("%d", fTs[i].fWindSum);

4234 }

4235 SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fO ppValue);

4236 }

4237 }

4238

4239 // This isn't useful yet -- but leaving it in for now in case i think of som ething

4240 // to use it for

4241 void validateActiveSpans() const {

4242 if (done()) {

4243 return;

4244 }

4245 int tCount = fTs.count();

4246 for (int index = 0; index < tCount; ++index) {

4247 if (fTs[index].fDone) {

4248 continue;

4249 }

4250 // count number of connections which are not done

4251 int first = index;

4252 double baseT = fTs[index].fT;

4253 while (first > 0 && approximately_equal(fTs[first - 1].fT, baseT)) {

4254 --first;

4255 }

4256 int last = index;

4257 while (last < tCount - 1 && approximately_equal(fTs[last + 1].fT, ba seT)) {

4258 ++last;

4259 }

4260 int connections = 0;

4261 connections += first > 0 && !fTs[first - 1].fDone;

4262 for (int test = first; test <= last; ++test) {

4263 connections += !fTs[test].fDone;

4264 const Segment* other = fTs[test].fOther;

4265 int oIndex = fTs[test].fOtherIndex;

4266 connections += !other->fTs[oIndex].fDone;

4267 connections += oIndex > 0 && !other->fTs[oIndex - 1].fDone;

4268 }

4269 // SkASSERT(!(connections & 1));

4270 }

4271 }

4272 #endif

4273

4274 #if DEBUG_MARK_DONE \|\| DEBUG_UNSORTABLE

4275 void debugShowNewWinding(const char* fun, const Span& span, int winding) {

4276 const SkPoint& pt = xyAtT(&span);

4277 SkDebugf("%s id=%d", fun, fID);

4278 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);

4279 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {

4280 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);

4281 }

4282 SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->

4283 fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);

4284 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d windSum= ",

4285 span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,

4286 (&span)[1].fT, winding);

4287 if (span.fWindSum == SK_MinS32) {

4288 SkDebugf("?");

4289 } else {

4290 SkDebugf("%d", span.fWindSum);

4291 }

4292 SkDebugf(" windValue=%d\n", span.fWindValue);

4293 }

4294

4295 void debugShowNewWinding(const char* fun, const Span& span, int winding, int oppWinding) {

4296 const SkPoint& pt = xyAtT(&span);

4297 SkDebugf("%s id=%d", fun, fID);

4298 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);

4299 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {

4300 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);

4301 }

4302 SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->

4303 fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);

4304 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d newOppSu m=%d oppSum=",

4305 span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,

4306 (&span)[1].fT, winding, oppWinding);

4307 if (span.fOppSum == SK_MinS32) {

4308 SkDebugf("?");

4309 } else {

4310 SkDebugf("%d", span.fOppSum);

4311 }

4312 SkDebugf(" windSum=");

4313 if (span.fWindSum == SK_MinS32) {

4314 SkDebugf("?");

4315 } else {

4316 SkDebugf("%d", span.fWindSum);

4317 }

4318 SkDebugf(" windValue=%d\n", span.fWindValue);

4319 }

4320 #endif

4321

4322 #if DEBUG_SORT \|\| DEBUG_SWAP_TOP

4323 void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int fir st,

4324 const int contourWinding, const int oppContourWinding) const {

4325 if (--gDebugSortCount < 0) {

4326 return;

4327 }

4328 SkASSERT(angles[first]->segment() == this);

4329 SkASSERT(angles.count() > 1);

4330 int lastSum = contourWinding;

4331 int oppLastSum = oppContourWinding;

4332 const Angle* firstAngle = angles[first];

4333 int windSum = lastSum - spanSign(firstAngle);

4334 int oppoSign = oppSign(firstAngle);

4335 int oppWindSum = oppLastSum - oppoSign;

4336 #define WIND_AS_STRING(x) char x##Str[12]; if (!valid_wind(x)) strcpy(x# #Str, "?"); \

4337 else snprintf(x##Str, sizeof(x##Str), "%d", x)

4338 WIND_AS_STRING(contourWinding);

4339 WIND_AS_STRING(oppContourWinding);

4340 SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__,

4341 contourWindingStr, oppContourWindingStr, spanSign(angles[first]) );

4342 int index = first;

4343 bool firstTime = true;

4344 do {

4345 const Angle& angle = *angles[index];

4346 const Segment& segment = *angle.segment();

4347 int start = angle.start();

4348 int end = angle.end();

4349 const Span& sSpan = segment.fTs[start];

4350 const Span& eSpan = segment.fTs[end];

4351 const Span& mSpan = segment.fTs[SkMin32(start, end)];

4352 bool opp = segment.fOperand ^ fOperand;

4353 if (!firstTime) {

4354 oppoSign = segment.oppSign(&angle);

4355 if (opp) {

4356 oppLastSum = oppWindSum;

4357 oppWindSum -= segment.spanSign(&angle);

4358 if (oppoSign) {

4359 lastSum = windSum;

4360 windSum -= oppoSign;

4361 }

4362 } else {

4363 lastSum = windSum;

4364 windSum -= segment.spanSign(&angle);

4365 if (oppoSign) {

4366 oppLastSum = oppWindSum;

4367 oppWindSum -= oppoSign;

4368 }

4369 }

4370 }

4371 SkDebugf("%s [%d] %s", __FUNCTION__, index,

4372 angle.unsortable() ? "* UNSORTABLE * " : "");

4373 #if COMPACT_DEBUG_SORT

4374 SkDebugf("id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)",

4375 segment.fID, kLVerbStr[segment.fVerb],

4376 start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,

4377 segment.xAtT(&eSpan), segment.yAtT(&eSpan));

4378 #else

4379 switch (segment.fVerb) {

4380 case SkPath::kLine_Verb:

4381 SkDebugf(LINE_DEBUG_STR, LINE_DEBUG_DATA(segment.fPts));

4382 break;

4383 case SkPath::kQuad_Verb:

4384 SkDebugf(QUAD_DEBUG_STR, QUAD_DEBUG_DATA(segment.fPts));

4385 break;

4386 case SkPath::kCubic_Verb:

4387 SkDebugf(CUBIC_DEBUG_STR, CUBIC_DEBUG_DATA(segment.fPts));

4388 break;

4389 default:

4390 SkASSERT(0);

4391 }

4392 SkDebugf(" tStart=%1.9g tEnd=%1.9g", sSpan.fT, eSpan.fT);

4393 #endif

4394 SkDebugf(" sign=%d windValue=%d windSum=", angle.sign(), mSpan.fWind Value);

4395 winding_printf(mSpan.fWindSum);

4396 int last, wind;

4397 if (opp) {

4398 last = oppLastSum;

4399 wind = oppWindSum;

4400 } else {

4401 last = lastSum;

4402 wind = windSum;

4403 }

4404 bool useInner = valid_wind(last) && valid_wind(wind) && useInnerWind ing(last, wind);

4405 WIND_AS_STRING(last);

4406 WIND_AS_STRING(wind);

4407 WIND_AS_STRING(lastSum);

4408 WIND_AS_STRING(oppLastSum);

4409 WIND_AS_STRING(windSum);

4410 WIND_AS_STRING(oppWindSum);

4411 #undef WIND_AS_STRING

4412 if (!oppoSign) {

4413 SkDebugf(" %s->%s (max=%s)", lastStr, windStr, useInner ? windSt r : lastStr);

4414 } else {

4415 SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr,

4416 opp ? windSumStr : oppWindSumStr);

4417 }

4418 SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp) ;

4419 #if false && DEBUG_ANGLE

4420 angle.debugShow(segment.xyAtT(&sSpan));

4421 #endif

4422 ++index;

4423 if (index == angles.count()) {

4424 index = 0;

4425 }

4426 if (firstTime) {

4427 firstTime = false;

4428 }

4429 } while (index != first);

4430 }

4431

4432 void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int fir st) {

4433 const Angle* firstAngle = angles[first];

4434 const Segment* segment = firstAngle->segment();

4435 int winding = segment->updateWinding(firstAngle);

4436 int oppWinding = segment->updateOppWinding(firstAngle);

4437 debugShowSort(fun, angles, first, winding, oppWinding);

4438 }

4439

4440 #endif

4441

4442 #if DEBUG_WINDING

4443 static char as_digit(int value) {

4444 return value < 0 ? '?' : value <= 9 ? '0' + value : '+';

4445 }

4446 #endif

4447

4448 #if DEBUG_SHOW_WINDING

4449 int debugShowWindingValues(int slotCount, int ofInterest) const {

4450 if (!(1 << fID & ofInterest)) {

4451 return 0;

4452 }

4453 int sum = 0;

4454 SkTDArray<char> slots;

4455 slots.setCount(slotCount * 2);

4456 memset(slots.begin(), ' ', slotCount * 2);

4457 for (int i = 0; i < fTs.count(); ++i) {

4458 // if (!(1 << fTs[i].fOther->fID & ofInterest)) {

4459 // continue;

4460 // }

4461 sum += fTs[i].fWindValue;

4462 slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue);

4463 sum += fTs[i].fOppValue;

4464 slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValu e);

4465 }

4466 SkDebugf("%s id=%2d %.s \| %.s\n", __FUNCTION__, fID, slotCount, slots. begin(), slotCount,

4467 slots.begin() + slotCount);

4468 return sum;

4469 }

4470 #endif

4471

4472 private:

4473 const SkPoint* fPts;

4474 Bounds fBounds;

4475 SkTDArray<Span> fTs; // two or more (always includes t=0 t=1)

4476 // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized v alue

4477 int fDoneSpans; // quick check that segment is finished

4478 // OPTIMIZATION: force the following to be byte-sized

4479 SkPath::Verb fVerb;

4480 bool fOperand;

4481 bool fXor; // set if original contour had even-odd fill

4482 bool fOppXor; // set if opposite operand had even-odd fill

4483 #if DEBUG_DUMP

4484 int fID;

4485 #endif

4486 };

4487

4488 class Contour;

4489

4490 struct Coincidence {

4491 Contour* fContours[2];

4492 int fSegments[2];

4493 double fTs[2][2];

4494 SkPoint fPts[2];

4495 };

4496

4497 class Contour {

4498 public:

4499 Contour() {

4500 reset();

4501 #if DEBUG_DUMP

4502 fID = ++gContourID;

4503 #endif

4504 }

4505

4506 bool operator<(const Contour& rh) const {

4507 return fBounds.fTop == rh.fBounds.fTop

4508 ? fBounds.fLeft < rh.fBounds.fLeft

4509 : fBounds.fTop < rh.fBounds.fTop;

4510 }

4511

4512 void addCoincident(int index, Contour* other, int otherIndex,

4513 const Intersections& ts, bool swap) {

4514 Coincidence& coincidence = *fCoincidences.append();

4515 coincidence.fContours[0] = this; // FIXME: no need to store

4516 coincidence.fContours[1] = other;

4517 coincidence.fSegments[0] = index;

4518 coincidence.fSegments[1] = otherIndex;

4519 coincidence.fTs[swap][0] = ts.fT[0][0];

4520 coincidence.fTs[swap][1] = ts.fT[0][1];

4521 coincidence.fTs[!swap][0] = ts.fT[1][0];

4522 coincidence.fTs[!swap][1] = ts.fT[1][1];

4523 coincidence.fPts[0] = ts.fPt[0].asSkPoint();

4524 coincidence.fPts[1] = ts.fPt[1].asSkPoint();

4525 }

4526

4527 void addCross(const Contour* crosser) {

4528 #ifdef DEBUG_CROSS

4529 for (int index = 0; index < fCrosses.count(); ++index) {

4530 SkASSERT(fCrosses[index] != crosser);

4531 }

4532 #endif

4533 *fCrosses.append() = crosser;

4534 }

4535

4536 void addCubic(const SkPoint pts[4]) {

4537 fSegments.push_back().addCubic(pts, fOperand, fXor);

4538 fContainsCurves = fContainsCubics = true;

4539 }

4540

4541 int addLine(const SkPoint pts[2]) {

4542 fSegments.push_back().addLine(pts, fOperand, fXor);

4543 return fSegments.count();

4544 }

4545

4546 void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {

4547 fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);

4548 }

4549

4550 int addQuad(const SkPoint pts[3]) {

4551 fSegments.push_back().addQuad(pts, fOperand, fXor);

4552 fContainsCurves = true;

4553 return fSegments.count();

4554 }

4555

4556 int addT(int segIndex, Contour* other, int otherIndex, const SkPoint& pt, do uble& newT) {

4557 setContainsIntercepts();

4558 return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT) ;

4559 }

4560

4561 int addSelfT(int segIndex, Contour* other, int otherIndex, const SkPoint& pt , double& newT) {

4562 setContainsIntercepts();

4563 return fSegments[segIndex].addSelfT(&other->fSegments[otherIndex], pt, n ewT);

4564 }

4565

4566 int addUnsortableT(int segIndex, Contour* other, int otherIndex, bool start,

4567 const SkPoint& pt, double& newT) {

4568 return fSegments[segIndex].addUnsortableT(&other->fSegments[otherIndex], start, pt, newT);

4569 }

4570

4571 const Bounds& bounds() const {

4572 return fBounds;

4573 }

4574

4575 void complete() {

4576 setBounds();

4577 fContainsIntercepts = false;

4578 }

4579

4580 bool containsCubics() const {

4581 return fContainsCubics;

4582 }

4583

4584 bool crosses(const Contour* crosser) const {

4585 for (int index = 0; index < fCrosses.count(); ++index) {

4586 if (fCrosses[index] == crosser) {

4587 return true;

4588 }

4589 }

4590 return false;

4591 }

4592

4593 bool done() const {

4594 return fDone;

4595 }

4596

4597 const SkPoint& end() const {

4598 const Segment& segment = fSegments.back();

4599 return segment.pts()[segment.verb()];

4600 }

4601

4602 void findTooCloseToCall() {

4603 int segmentCount = fSegments.count();

4604 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {

4605 fSegments[sIndex].findTooCloseToCall();

4606 }

4607 }

4608

4609 void fixOtherTIndex() {

4610 int segmentCount = fSegments.count();

4611 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {

4612 fSegments[sIndex].fixOtherTIndex();

4613 }

4614 }

4615

4616 Segment* nonVerticalSegment(int& start, int& end) {

4617 int segmentCount = fSortedSegments.count();

4618 SkASSERT(segmentCount > 0);

4619 for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sorte dIndex) {

4620 Segment* testSegment = fSortedSegments[sortedIndex];

4621 if (testSegment->done()) {

4622 continue;

4623 }

4624 start = end = 0;

4625 while (testSegment->nextCandidate(start, end)) {

4626 if (!testSegment->isVertical(start, end)) {

4627 return testSegment;

4628 }

4629 }

4630 }

4631 return NULL;

4632 }

4633

4634 bool operand() const {

4635 return fOperand;

4636 }

4637

4638 void reset() {

4639 fSegments.reset();

4640 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);

4641 fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = false;

4642 }

4643

4644 void resolveCoincidence(SkTDArray<Contour*>& contourList) {

4645 int count = fCoincidences.count();

4646 for (int index = 0; index < count; ++index) {

4647 Coincidence& coincidence = fCoincidences[index];

4648 SkASSERT(coincidence.fContours[0] == this);

4649 int thisIndex = coincidence.fSegments[0];

4650 Segment& thisOne = fSegments[thisIndex];

4651 Contour* otherContour = coincidence.fContours[1];

4652 int otherIndex = coincidence.fSegments[1];

4653 Segment& other = otherContour->fSegments[otherIndex];

4654 if ((thisOne.done() \|\| other.done()) && thisOne.complete() && other. complete()) {

4655 continue;

4656 }

4657 #if DEBUG_CONCIDENT

4658 thisOne.debugShowTs();

4659 other.debugShowTs();

4660 #endif

4661 double startT = coincidence.fTs[0][0];

4662 double endT = coincidence.fTs[0][1];

4663 bool cancelers = false;

4664 if (startT > endT) {

4665 SkTSwap<double>(startT, endT);

4666 cancelers ^= true; // FIXME: just assign true

4667 }

4668 SkASSERT(!approximately_negative(endT - startT));

4669 double oStartT = coincidence.fTs[1][0];

4670 double oEndT = coincidence.fTs[1][1];

4671 if (oStartT > oEndT) {

4672 SkTSwap<double>(oStartT, oEndT);

4673 cancelers ^= true;

4674 }

4675 SkASSERT(!approximately_negative(oEndT - oStartT));

4676 bool opp = fOperand ^ otherContour->fOperand;

4677 if (cancelers && !opp) {

4678 // make sure startT and endT have t entries

4679 if (startT > 0 \|\| oEndT < 1

4680 \|\| thisOne.isMissing(startT) \|\| other.isMissing(oEndT)) {

4681 thisOne.addTPair(startT, other, oEndT, true, coincidence.fPt s[0]);

4682 }

4683 if (oStartT > 0 \|\| endT < 1

4684 \|\| thisOne.isMissing(endT) \|\| other.isMissing(oStartT)) {

4685 other.addTPair(oStartT, thisOne, endT, true, coincidence.fPt s[1]);

4686 }

4687 if (!thisOne.done() && !other.done()) {

4688 thisOne.addTCancel(startT, endT, other, oStartT, oEndT);

4689 }

4690 } else {

4691 if (startT > 0 \|\| oStartT > 0

4692 \|\| thisOne.isMissing(startT) \|\| other.isMissing(oStartT) ) {

4693 thisOne.addTPair(startT, other, oStartT, true, coincidence.f Pts[0]);

4694 }

4695 if (endT < 1 \|\| oEndT < 1

4696 \|\| thisOne.isMissing(endT) \|\| other.isMissing(oEndT)) {

4697 other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[ 1]);

4698 }

4699 if (!thisOne.done() && !other.done()) {

4700 thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);

4701 }

4702 }

4703 #if DEBUG_CONCIDENT

4704 thisOne.debugShowTs();

4705 other.debugShowTs();

4706 #endif

4707 #if DEBUG_SHOW_WINDING

4708 debugShowWindingValues(contourList);

4709 #endif

4710 }

4711 }

4712

4713 // first pass, add missing T values

4714 // second pass, determine winding values of overlaps

4715 void addCoincidentPoints() {

4716 int count = fCoincidences.count();

4717 for (int index = 0; index < count; ++index) {

4718 Coincidence& coincidence = fCoincidences[index];

4719 SkASSERT(coincidence.fContours[0] == this);

4720 int thisIndex = coincidence.fSegments[0];

4721 Segment& thisOne = fSegments[thisIndex];

4722 Contour* otherContour = coincidence.fContours[1];

4723 int otherIndex = coincidence.fSegments[1];

4724 Segment& other = otherContour->fSegments[otherIndex];

4725 if ((thisOne.done() \|\| other.done()) && thisOne.complete() && other. complete()) {

4726 // OPTIMIZATION: remove from array

4727 continue;

4728 }

4729 #if DEBUG_CONCIDENT

4730 thisOne.debugShowTs();

4731 other.debugShowTs();

4732 #endif

4733 double startT = coincidence.fTs[0][0];

4734 double endT = coincidence.fTs[0][1];

4735 bool cancelers;

4736 if ((cancelers = startT > endT)) {

4737 SkTSwap(startT, endT);

4738 SkTSwap(coincidence.fPts[0], coincidence.fPts[1]);

4739 }

4740 SkASSERT(!approximately_negative(endT - startT));

4741 double oStartT = coincidence.fTs[1][0];

4742 double oEndT = coincidence.fTs[1][1];

4743 if (oStartT > oEndT) {

4744 SkTSwap<double>(oStartT, oEndT);

4745 cancelers ^= true;

4746 }

4747 SkASSERT(!approximately_negative(oEndT - oStartT));

4748 bool opp = fOperand ^ otherContour->fOperand;

4749 if (cancelers && !opp) {

4750 // make sure startT and endT have t entries

4751 if (startT > 0 \|\| oEndT < 1

4752 \|\| thisOne.isMissing(startT) \|\| other.isMissing(oEndT)) {

4753 thisOne.addTPair(startT, other, oEndT, true, coincidence.fPt s[0]);

4754 }

4755 if (oStartT > 0 \|\| endT < 1

4756 \|\| thisOne.isMissing(endT) \|\| other.isMissing(oStartT)) {

4757 other.addTPair(oStartT, thisOne, endT, true, coincidence.fPt s[1]);

4758 }

4759 } else {

4760 if (startT > 0 \|\| oStartT > 0

4761 \|\| thisOne.isMissing(startT) \|\| other.isMissing(oStartT) ) {

4762 thisOne.addTPair(startT, other, oStartT, true, coincidence.f Pts[0]);

4763 }

4764 if (endT < 1 \|\| oEndT < 1

4765 \|\| thisOne.isMissing(endT) \|\| other.isMissing(oEndT)) {

4766 other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[ 1]);

4767 }

4768 }

4769 #if DEBUG_CONCIDENT

4770 thisOne.debugShowTs();

4771 other.debugShowTs();

4772 #endif

4773 }

4774 }

4775

4776 void calcCoincidentWinding() {

4777 int count = fCoincidences.count();

4778 for (int index = 0; index < count; ++index) {

4779 Coincidence& coincidence = fCoincidences[index];

4780 SkASSERT(coincidence.fContours[0] == this);

4781 int thisIndex = coincidence.fSegments[0];

4782 Segment& thisOne = fSegments[thisIndex];

4783 if (thisOne.done()) {

4784 continue;

4785 }

4786 Contour* otherContour = coincidence.fContours[1];

4787 int otherIndex = coincidence.fSegments[1];

4788 Segment& other = otherContour->fSegments[otherIndex];

4789 if (other.done()) {

4790 continue;

4791 }

4792 double startT = coincidence.fTs[0][0];

4793 double endT = coincidence.fTs[0][1];

4794 bool cancelers;

4795 if ((cancelers = startT > endT)) {

4796 SkTSwap<double>(startT, endT);

4797 }

4798 SkASSERT(!approximately_negative(endT - startT));

4799 double oStartT = coincidence.fTs[1][0];

4800 double oEndT = coincidence.fTs[1][1];

4801 if (oStartT > oEndT) {

4802 SkTSwap<double>(oStartT, oEndT);

4803 cancelers ^= true;

4804 }

4805 SkASSERT(!approximately_negative(oEndT - oStartT));

4806 bool opp = fOperand ^ otherContour->fOperand;

4807 if (cancelers && !opp) {

4808 // make sure startT and endT have t entries

4809 if (!thisOne.done() && !other.done()) {

4810 thisOne.addTCancel(startT, endT, other, oStartT, oEndT);

4811 }

4812 } else {

4813 if (!thisOne.done() && !other.done()) {

4814 thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);

4815 }

4816 }

4817 #if DEBUG_CONCIDENT

4818 thisOne.debugShowTs();

4819 other.debugShowTs();

4820 #endif

4821 }

4822 }

4823

4824 SkTArray<Segment>& segments() {

4825 return fSegments;

4826 }

4827

4828 void setContainsIntercepts() {

4829 fContainsIntercepts = true;

4830 }

4831

4832 void setOperand(bool isOp) {

4833 fOperand = isOp;

4834 }

4835

4836 void setOppXor(bool isOppXor) {

4837 fOppXor = isOppXor;

4838 int segmentCount = fSegments.count();

4839 for (int test = 0; test < segmentCount; ++test) {

4840 fSegments[test].setOppXor(isOppXor);

4841 }

4842 }

4843

4844 void setXor(bool isXor) {

4845 fXor = isXor;

4846 }

4847

4848 void sortSegments() {

4849 int segmentCount = fSegments.count();

4850 fSortedSegments.setReserve(segmentCount);

4851 for (int test = 0; test < segmentCount; ++test) {

4852 *fSortedSegments.append() = &fSegments[test];

4853 }

4854 QSort<Segment>(fSortedSegments.begin(), fSortedSegments.end() - 1);

4855 fFirstSorted = 0;

4856 }

4857

4858 const SkPoint& start() const {

4859 return fSegments.front().pts()[0];

4860 }

4861

4862 void toPath(PathWrapper& path) const {

4863 int segmentCount = fSegments.count();

4864 const SkPoint& pt = fSegments.front().pts()[0];

4865 path.deferredMove(pt);

4866 for (int test = 0; test < segmentCount; ++test) {

4867 fSegments[test].addCurveTo(0, 1, path, true);

4868 }

4869 path.close();

4870 }

4871

4872 void toPartialBackward(PathWrapper& path) const {

4873 int segmentCount = fSegments.count();

4874 for (int test = segmentCount - 1; test >= 0; --test) {

4875 fSegments[test].addCurveTo(1, 0, path, true);

4876 }

4877 }

4878

4879 void toPartialForward(PathWrapper& path) const {

4880 int segmentCount = fSegments.count();

4881 for (int test = 0; test < segmentCount; ++test) {

4882 fSegments[test].addCurveTo(0, 1, path, true);

4883 }

4884 }

4885

4886 void topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY, Segment*& t opStart) {

4887 int segmentCount = fSortedSegments.count();

4888 SkASSERT(segmentCount > 0);

4889 int sortedIndex = fFirstSorted;

4890 fDone = true; // may be cleared below

4891 for ( ; sortedIndex < segmentCount; ++sortedIndex) {

4892 Segment* testSegment = fSortedSegments[sortedIndex];

4893 if (testSegment->done()) {

4894 if (sortedIndex == fFirstSorted) {

4895 ++fFirstSorted;

4896 }

4897 continue;

4898 }

4899 fDone = false;

4900 SkPoint testXY = testSegment->activeLeftTop(true, NULL);

4901 if (topStart) {

4902 if (testXY.fY < topLeft.fY) {

4903 continue;

4904 }

4905 if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {

4906 continue;

4907 }

4908 if (bestXY.fY < testXY.fY) {

4909 continue;

4910 }

4911 if (bestXY.fY == testXY.fY && bestXY.fX < testXY.fX) {

4912 continue;

4913 }

4914 }

4915 topStart = testSegment;

4916 bestXY = testXY;

4917 }

4918 }

4919

4920 Segment* undoneSegment(int& start, int& end) {

4921 int segmentCount = fSegments.count();

4922 for (int test = 0; test < segmentCount; ++test) {

4923 Segment* testSegment = &fSegments[test];

4924 if (testSegment->done()) {

4925 continue;

4926 }

4927 testSegment->undoneSpan(start, end);

4928 return testSegment;

4929 }

4930 return NULL;

4931 }

4932

4933 int updateSegment(int index, const SkPoint* pts) {

4934 Segment& segment = fSegments[index];

4935 segment.updatePts(pts);

4936 return segment.verb() + 1;

4937 }

4938

4939 #if DEBUG_TEST

4940 SkTArray<Segment>& debugSegments() {

4941 return fSegments;

4942 }

4943 #endif

4944

4945 #if DEBUG_DUMP

4946 void dump() {

4947 int i;

4948 const char className[] = "Contour";

4949 const int tab = 4;

4950 SkDebugf("%s %p (contour=%d)\n", className, this, fID);

4951 for (i = 0; i < fSegments.count(); ++i) {

4952 SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),

4953 className, i);

4954 fSegments[i].dump();

4955 }

4956 SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",

4957 tab + sizeof(className), className,

4958 fBounds.fLeft, fBounds.fTop,

4959 fBounds.fRight, fBounds.fBottom);

4960 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),

4961 className, fContainsIntercepts);

4962 SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),

4963 className, fContainsCurves);

4964 }

4965 #endif

4966

4967 #if DEBUG_ACTIVE_SPANS

4968 void debugShowActiveSpans() {

4969 for (int index = 0; index < fSegments.count(); ++index) {

4970 fSegments[index].debugShowActiveSpans();

4971 }

4972 }

4973

4974 void validateActiveSpans() {

4975 for (int index = 0; index < fSegments.count(); ++index) {

4976 fSegments[index].validateActiveSpans();

4977 }

4978 }

4979 #endif

4980

4981 #if DEBUG_SHOW_WINDING

4982 int debugShowWindingValues(int totalSegments, int ofInterest) {

4983 int count = fSegments.count();

4984 int sum = 0;

4985 for (int index = 0; index < count; ++index) {

4986 sum += fSegments[index].debugShowWindingValues(totalSegments, ofInte rest);

4987 }

4988 // SkDebugf("%s sum=%d\n", __FUNCTION__, sum);

4989 return sum;

4990 }

4991

4992 static void debugShowWindingValues(SkTDArray<Contour*>& contourList) {

4993 // int ofInterest = 1 << 1 \| 1 << 5 \| 1 << 9 \| 1 << 13;

4994 // int ofInterest = 1 << 4 \| 1 << 8 \| 1 << 12 \| 1 << 16;

4995 int ofInterest = 1 << 5 \| 1 << 8;

4996 int total = 0;

4997 int index;

4998 for (index = 0; index < contourList.count(); ++index) {

4999 total += contourList[index]->segments().count();

5000 }

5001 int sum = 0;

5002 for (index = 0; index < contourList.count(); ++index) {

5003 sum += contourList[index]->debugShowWindingValues(total, ofInterest) ;

5004 }

5005 // SkDebugf("%s total=%d\n", __FUNCTION__, sum);

5006 }

5007 #endif

5008

5009 protected:

5010 void setBounds() {

5011 int count = fSegments.count();

5012 if (count == 0) {

5013 SkDebugf("%s empty contour\n", __FUNCTION__);

5014 SkASSERT(0);

5015 // FIXME: delete empty contour?

5016 return;

5017 }

5018 fBounds = fSegments.front().bounds();

5019 for (int index = 1; index < count; ++index) {

5020 fBounds.add(fSegments[index].bounds());

5021 }

5022 }

5023

5024 private:

5025 SkTArray<Segment> fSegments;

5026 SkTDArray<Segment*> fSortedSegments;

5027 int fFirstSorted;

5028 SkTDArray<Coincidence> fCoincidences;

5029 SkTDArray<const Contour*> fCrosses;

5030 Bounds fBounds;

5031 bool fContainsIntercepts; // FIXME: is this used by anybody?

5032 bool fContainsCubics;

5033 bool fContainsCurves;

5034 bool fDone;

5035 bool fOperand; // true for the second argument to a binary operator

5036 bool fXor;

5037 bool fOppXor;

5038 #if DEBUG_DUMP

5039 int fID;

5040 #endif

5041 };

5042

5043 class EdgeBuilder {

5044 public:

5045

5046 EdgeBuilder(const PathWrapper& path, SkTArray<Contour>& contours)

5047 : fPath(path.nativePath())

5048 , fContours(contours)

5049 {

5050 init();

5051 }

5052

5053 EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours)

5054 : fPath(&path)

5055 , fContours(contours)

5056 {

5057 init();

5058 }

5059

5060 void init() {

5061 fCurrentContour = NULL;

5062 fOperand = false;

5063 fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWi nding_Mask;

5064 #if DEBUG_DUMP

5065 gContourID = 0;

5066 gSegmentID = 0;

5067 #endif

5068 fSecondHalf = preFetch();

5069 }

5070

5071 void addOperand(const SkPath& path) {

5072 SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Ver b);

5073 fPathVerbs.pop();

5074 fPath = &path;

5075 fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask;

5076 preFetch();

5077 }

5078

5079 void finish() {

5080 walk();

5081 complete();

5082 if (fCurrentContour && !fCurrentContour->segments().count()) {

5083 fContours.pop_back();

5084 }

5085 // correct pointers in contours since fReducePts may have moved as it grew

5086 int cIndex = 0;

5087 int extraCount = fExtra.count();

5088 SkASSERT(extraCount == 0 \|\| fExtra[0] == -1);

5089 int eIndex = 0;

5090 int rIndex = 0;

5091 while (++eIndex < extraCount) {

5092 int offset = fExtra[eIndex];

5093 if (offset < 0) {

5094 ++cIndex;

5095 continue;

5096 }

5097 fCurrentContour = &fContours[cIndex];

5098 rIndex += fCurrentContour->updateSegment(offset - 1,

5099 &fReducePts[rIndex]);

5100 }

5101 fExtra.reset(); // we're done with this

5102 }

5103

5104 ShapeOpMask xorMask() const {

5105 return fXorMask[fOperand];

5106 }

5107

5108 protected:

5109

5110 void complete() {

5111 if (fCurrentContour && fCurrentContour->segments().count()) {

5112 fCurrentContour->complete();

5113 fCurrentContour = NULL;

5114 }

5115 }

5116

5117 // FIXME:remove once we can access path pts directly

5118 int preFetch() {

5119 SkPath::RawIter iter(*fPath); // FIXME: access path directly when allowed

5120 SkPoint pts[4];

5121 SkPath::Verb verb;

5122 do {

5123 verb = iter.next(pts);

5124 *fPathVerbs.append() = verb;

5125 if (verb == SkPath::kMove_Verb) {

5126 *fPathPts.append() = pts[0];

5127 } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {

5128 fPathPts.append(verb, &pts[1]);

5129 }

5130 } while (verb != SkPath::kDone_Verb);

5131 return fPathVerbs.count() - 1;

5132 }

5133

5134 void walk() {

5135 SkPath::Verb reducedVerb;

5136 uint8_t* verbPtr = fPathVerbs.begin();

5137 uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];

5138 const SkPoint* pointsPtr = fPathPts.begin();

5139 const SkPoint* finalCurveStart = NULL;

5140 const SkPoint* finalCurveEnd = NULL;

5141 SkPath::Verb verb;

5142 while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) {

5143 switch (verb) {

5144 case SkPath::kMove_Verb:

5145 complete();

5146 if (!fCurrentContour) {

5147 fCurrentContour = fContours.push_back_n(1);

5148 fCurrentContour->setOperand(fOperand);

5149 fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_Mask) ;

5150 *fExtra.append() = -1; // start new contour

5151 }

5152 finalCurveEnd = pointsPtr++;

5153 goto nextVerb;

5154 case SkPath::kLine_Verb:

5155 // skip degenerate points

5156 if (pointsPtr[-1].fX != pointsPtr[0].fX

5157 \|\| pointsPtr[-1].fY != pointsPtr[0].fY) {

5158 fCurrentContour->addLine(&pointsPtr[-1]);

5159 }

5160 break;

5161 case SkPath::kQuad_Verb:

5162

5163 reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts);

5164 if (reducedVerb == 0) {

5165 break; // skip degenerate points

5166 }

5167 if (reducedVerb == 1) {

5168 *fExtra.append() =

5169 fCurrentContour->addLine(fReducePts.end() - 2);

5170 break;

5171 }

5172 fCurrentContour->addQuad(&pointsPtr[-1]);

5173 break;

5174 case SkPath::kCubic_Verb:

5175 reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);

5176 if (reducedVerb == 0) {

5177 break; // skip degenerate points

5178 }

5179 if (reducedVerb == 1) {

5180 *fExtra.append() =

5181 fCurrentContour->addLine(fReducePts.end() - 2);

5182 break;

5183 }

5184 if (reducedVerb == 2) {

5185 *fExtra.append() =

5186 fCurrentContour->addQuad(fReducePts.end() - 3);

5187 break;

5188 }

5189 fCurrentContour->addCubic(&pointsPtr[-1]);

5190 break;

5191 case SkPath::kClose_Verb:

5192 SkASSERT(fCurrentContour);

5193 if (finalCurveStart && finalCurveEnd

5194 && finalCurveStart != finalCurveEnd) {

5195 fReducePts.append() = finalCurveStart;

5196 fReducePts.append() = finalCurveEnd;

5197 *fExtra.append() =

5198 fCurrentContour->addLine(fReducePts.end() - 2);

5199 }

5200 complete();

5201 goto nextVerb;

5202 default:

5203 SkDEBUGFAIL("bad verb");

5204 return;

5205 }

5206 finalCurveStart = &pointsPtr[verb - 1];

5207 pointsPtr += verb;

5208 SkASSERT(fCurrentContour);

5209 nextVerb:

5210 if (verbPtr == endOfFirstHalf) {

5211 fOperand = true;

5212 }

5213 }

5214 }

5215

5216 private:

5217 const SkPath* fPath;

5218 SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead

5219 SkTDArray<uint8_t> fPathVerbs; // FIXME: remove

5220 Contour* fCurrentContour;

5221 SkTArray<Contour>& fContours;

5222 SkTDArray<SkPoint> fReducePts; // segments created on the fly

5223 SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour

5224 ShapeOpMask fXorMask[2];

5225 int fSecondHalf;

5226 bool fOperand;

5227 };

5228

5229 class Work {

5230 public:

5231 enum SegmentType {

5232 kHorizontalLine_Segment = -1,

5233 kVerticalLine_Segment = 0,

5234 kLine_Segment = SkPath::kLine_Verb,

5235 kQuad_Segment = SkPath::kQuad_Verb,

5236 kCubic_Segment = SkPath::kCubic_Verb,

5237 };

5238

5239 void addCoincident(Work& other, const Intersections& ts, bool swap) {

5240 fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap);

5241 }

5242

5243 // FIXME: does it make sense to write otherIndex now if we're going to

5244 // fix it up later?

5245 void addOtherT(int index, double otherT, int otherIndex) {

5246 fContour->addOtherT(fIndex, index, otherT, otherIndex);

5247 }

5248

5249 // Avoid collapsing t values that are close to the same since

5250 // we walk ts to describe consecutive intersections. Since a pair of ts can

5251 // be nearly equal, any problems caused by this should be taken care

5252 // of later.

5253 // On the edge or out of range values are negative; add 2 to get end

5254 int addT(const Work& other, const SkPoint& pt, double& newT) {

5255 return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT);

5256 }

5257

5258 int addSelfT(const Work& other, const SkPoint& pt, double& newT) {

5259 return fContour->addSelfT(fIndex, other.fContour, other.fIndex, pt, newT );

5260 }

5261

5262 int addUnsortableT(const Work& other, bool start, const SkPoint& pt, double& newT) {

5263 return fContour->addUnsortableT(fIndex, other.fContour, other.fIndex, st art, pt, newT);

5264 }

5265

5266 bool advance() {

5267 return ++fIndex < fLast;

5268 }

5269

5270 SkScalar bottom() const {

5271 return bounds().fBottom;

5272 }

5273

5274 const Bounds& bounds() const {

5275 return fContour->segments()[fIndex].bounds();

5276 }

5277

5278 #if !APPROXIMATE_CUBICS

5279 const SkPoint* cubic() const {

5280 return fCubic;

5281 }

5282 #endif

5283

5284 void init(Contour* contour) {

5285 fContour = contour;

5286 fIndex = 0;

5287 fLast = contour->segments().count();

5288 }

5289

5290 bool isAdjacent(const Work& next) {

5291 return fContour == next.fContour && fIndex + 1 == next.fIndex;

5292 }

5293

5294 bool isFirstLast(const Work& next) {

5295 return fContour == next.fContour && fIndex == 0

5296 && next.fIndex == fLast - 1;

5297 }

5298

5299 SkScalar left() const {

5300 return bounds().fLeft;

5301 }

5302

5303 #if !APPROXIMATE_CUBICS

5304 void promoteToCubic() {

5305 fCubic[0] = pts()[0];

5306 fCubic[2] = pts()[1];

5307 fCubic[3] = pts()[2];

5308 fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;

5309 fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;

5310 fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;

5311 fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;

5312 }

5313 #endif

5314

5315 const SkPoint* pts() const {

5316 return fContour->segments()[fIndex].pts();

5317 }

5318

5319 SkScalar right() const {

5320 return bounds().fRight;

5321 }

5322

5323 ptrdiff_t segmentIndex() const {

5324 return fIndex;

5325 }

5326

5327 SegmentType segmentType() const {

5328 const Segment& segment = fContour->segments()[fIndex];

5329 SegmentType type = (SegmentType) segment.verb();

5330 if (type != kLine_Segment) {

5331 return type;

5332 }

5333 if (segment.isHorizontal()) {

5334 return kHorizontalLine_Segment;

5335 }

5336 if (segment.isVertical()) {

5337 return kVerticalLine_Segment;

5338 }

5339 return kLine_Segment;

5340 }

5341

5342 bool startAfter(const Work& after) {

5343 fIndex = after.fIndex;

5344 return advance();

5345 }

5346

5347 SkScalar top() const {

5348 return bounds().fTop;

5349 }

5350

5351 SkPath::Verb verb() const {

5352 return fContour->segments()[fIndex].verb();

5353 }

5354

5355 SkScalar x() const {

5356 return bounds().fLeft;

5357 }

5358

5359 bool xFlipped() const {

5360 return x() != pts()[0].fX;

5361 }

5362

5363 SkScalar y() const {

5364 return bounds().fTop;

5365 }

5366

5367 bool yFlipped() const {

5368 return y() != pts()[0].fY;

5369 }

5370

5371 protected:

5372 Contour* fContour;

5373 #if !APPROXIMATE_CUBICS

5374 SkPoint fCubic[4];

5375 #endif

5376 int fIndex;

5377 int fLast;

5378 };

5379

5380 #if DEBUG_ADD_INTERSECTING_TS

5381

5382 static void debugShowLineIntersection(int pts, const Work& wt, const Work& wn,

5383 const Intersections& i) {

5384 SkASSERT(i.used() == pts);

5385 if (!pts) {

5386 SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n",

5387 __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts( )));

5388 return;

5389 }

5390 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __F UNCTION__,

5391 i.fT[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));

5392 if (pts == 2) {

5393 SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i.fT[0][1], PT_DEBUG _DATA(i, 1));

5394 }

5395 SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts() ));

5396 if (pts == 2) {

5397 SkDebugf(" " T_DEBUG_STR(wnTs, 1), i.fT[1][1]);

5398 }

5399 SkDebugf("\n");

5400 }

5401

5402 static void debugShowQuadLineIntersection(int pts, const Work& wt,

5403 const Work& wn, const Intersections& i) {

5404 SkASSERT(i.used() == pts);

5405 if (!pts) {

5406 SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n",

5407 __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts( )));

5408 return;

5409 }

5410 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __F UNCTION__,

5411 i.fT[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));

5412 for (int n = 1; n < pts; ++n) {

5413 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBU G_DATA(i, n));

5414 }

5415 SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts() ));

5416 for (int n = 1; n < pts; ++n) {

5417 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);

5418 }

5419 SkDebugf("\n");

5420 }

5421

5422 static void debugShowQuadIntersection(int pts, const Work& wt,

5423 const Work& wn, const Intersections& i) {

5424 SkASSERT(i.used() == pts);

5425 if (!pts) {

5426 SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n",

5427 __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts( )));

5428 return;

5429 }

5430 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __F UNCTION__,

5431 i.fT[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));

5432 for (int n = 1; n < pts; ++n) {

5433 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBU G_DATA(i, n));

5434 }

5435 SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i.fT[1][0], QUAD_DEBUG_DATA(wn.pts() ));

5436 for (int n = 1; n < pts; ++n) {

5437 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);

5438 }

5439 SkDebugf("\n");

5440 }

5441

5442 static void debugShowCubicLineIntersection(int pts, const Work& wt,

5443 const Work& wn, const Intersections& i) {

5444 SkASSERT(i.used() == pts);

5445 if (!pts) {

5446 SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n",

5447 __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts ()));

5448 return;

5449 }

5450 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __ FUNCTION__,

5451 i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));

5452 for (int n = 1; n < pts; ++n) {

5453 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBU G_DATA(i, n));

5454 }

5455 SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts() ));

5456 for (int n = 1; n < pts; ++n) {

5457 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);

5458 }

5459 SkDebugf("\n");

5460 }

5461

5462 static void debugShowCubicQuadIntersection(int pts, const Work& wt,

5463 const Work& wn, const Intersections& i) {

5464 SkASSERT(i.used() == pts);

5465 if (!pts) {

5466 SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n",

5467 __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts ()));

5468 return;

5469 }

5470 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __ FUNCTION__,

5471 i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));

5472 for (int n = 1; n < pts; ++n) {

5473 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBU G_DATA(i, n));

5474 }

5475 SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i.fT[1][0], QUAD_DEBUG_DATA(wn.pts() ));

5476 for (int n = 1; n < pts; ++n) {

5477 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);

5478 }

5479 SkDebugf("\n");

5480 }

5481

5482 static void debugShowCubicIntersection(int pts, const Work& wt,

5483 const Work& wn, const Intersections& i) {

5484 SkASSERT(i.used() == pts);

5485 if (!pts) {

5486 SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n",

5487 __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pt s()));

5488 return;

5489 }

5490 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __ FUNCTION__,

5491 i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));

5492 for (int n = 1; n < pts; ++n) {

5493 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBU G_DATA(i, n));

5494 }

5495 SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i.fT[1][0], CUBIC_DEBUG_DATA(wn.pts ()));

5496 for (int n = 1; n < pts; ++n) {

5497 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);

5498 }

5499 SkDebugf("\n");

5500 }

5501

5502 static void debugShowCubicIntersection(int pts, const Work& wt, const Intersecti ons& i) {

5503 SkASSERT(i.used() == pts);

5504 if (!pts) {

5505 SkDebugf("%s no self intersect " CUBIC_DEBUG_STR "\n", __FUNCTION__,

5506 CUBIC_DEBUG_DATA(wt.pts()));

5507 return;

5508 }

5509 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __ FUNCTION__,

5510 i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));

5511 SkDebugf(" " T_DEBUG_STR(wtTs, 1), i.fT[1][0]);

5512 SkDebugf("\n");

5513 }

5514

5515 #else

5516 static void debugShowLineIntersection(int , const Work& , const Work& , const In tersections& ) {

5517 }

5518

5519 static void debugShowQuadLineIntersection(int , const Work& , const Work& , cons t Intersections& ) {

5520 }

5521

5522 static void debugShowQuadIntersection(int , const Work& , const Work& , const In tersections& ) {

5523 }

5524

5525 static void debugShowCubicLineIntersection(int , const Work& , const Work& ,

5526 const Intersections& ) {

5527 }

5528

5529 static void debugShowCubicQuadIntersection(int , const Work& , const Work& ,

5530 const Intersections& ) {

5531 }

5532

5533 static void debugShowCubicIntersection(int , const Work& , const Work& , const I ntersections& ) {

5534 }

5535

5536 static void debugShowCubicIntersection(int , const Work& , const Intersections& ) {

5537 }

5538 #endif

5539

5540 static bool addIntersectTs(Contour* test, Contour* next) {

5541

5542 if (test != next) {

5543 if (test->bounds().fBottom < next->bounds().fTop) {

5544 return false;

5545 }

5546 if (!Bounds::Intersects(test->bounds(), next->bounds())) {

5547 return true;

5548 }

5549 }

5550 Work wt;

5551 wt.init(test);

5552 bool foundCommonContour = test == next;

5553 do {

5554 Work wn;

5555 wn.init(next);

5556 if (test == next && !wn.startAfter(wt)) {

5557 continue;

5558 }

5559 do {

5560 if (!Bounds::Intersects(wt.bounds(), wn.bounds())) {

5561 continue;

5562 }

5563 int pts;

5564 Intersections ts;

5565 bool swap = false;

5566 switch (wt.segmentType()) {

5567 case Work::kHorizontalLine_Segment:

5568 swap = true;

5569 switch (wn.segmentType()) {

5570 case Work::kHorizontalLine_Segment:

5571 case Work::kVerticalLine_Segment:

5572 case Work::kLine_Segment: {

5573 pts = HLineIntersect(wn.pts(), wt.left(),

5574 wt.right(), wt.y(), wt.xFlipped(), ts);

5575 debugShowLineIntersection(pts, wt, wn, ts);

5576 break;

5577 }

5578 case Work::kQuad_Segment: {

5579 pts = HQuadIntersect(wn.pts(), wt.left(),

5580 wt.right(), wt.y(), wt.xFlipped(), ts);

5581 break;

5582 }

5583 case Work::kCubic_Segment: {

5584 pts = HCubicIntersect(wn.pts(), wt.left(),

5585 wt.right(), wt.y(), wt.xFlipped(), ts);

5586 debugShowCubicLineIntersection(pts, wn, wt, ts);

5587 break;

5588 }

5589 default:

5590 SkASSERT(0);

5591 }

5592 break;

5593 case Work::kVerticalLine_Segment:

5594 swap = true;

5595 switch (wn.segmentType()) {

5596 case Work::kHorizontalLine_Segment:

5597 case Work::kVerticalLine_Segment:

5598 case Work::kLine_Segment: {

5599 pts = VLineIntersect(wn.pts(), wt.top(),

5600 wt.bottom(), wt.x(), wt.yFlipped(), ts);

5601 debugShowLineIntersection(pts, wt, wn, ts);

5602 break;

5603 }

5604 case Work::kQuad_Segment: {

5605 pts = VQuadIntersect(wn.pts(), wt.top(),

5606 wt.bottom(), wt.x(), wt.yFlipped(), ts);

5607 break;

5608 }

5609 case Work::kCubic_Segment: {

5610 pts = VCubicIntersect(wn.pts(), wt.top(),

5611 wt.bottom(), wt.x(), wt.yFlipped(), ts);

5612 debugShowCubicLineIntersection(pts, wn, wt, ts);

5613 break;

5614 }

5615 default:

5616 SkASSERT(0);

5617 }

5618 break;

5619 case Work::kLine_Segment:

5620 switch (wn.segmentType()) {

5621 case Work::kHorizontalLine_Segment:

5622 pts = HLineIntersect(wt.pts(), wn.left(),

5623 wn.right(), wn.y(), wn.xFlipped(), ts);

5624 debugShowLineIntersection(pts, wt, wn, ts);

5625 break;

5626 case Work::kVerticalLine_Segment:

5627 pts = VLineIntersect(wt.pts(), wn.top(),

5628 wn.bottom(), wn.x(), wn.yFlipped(), ts);

5629 debugShowLineIntersection(pts, wt, wn, ts);

5630 break;

5631 case Work::kLine_Segment: {

5632 pts = LineIntersect(wt.pts(), wn.pts(), ts);

5633 debugShowLineIntersection(pts, wt, wn, ts);

5634 break;

5635 }

5636 case Work::kQuad_Segment: {

5637 swap = true;

5638 pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);

5639 debugShowQuadLineIntersection(pts, wn, wt, ts);

5640 break;

5641 }

5642 case Work::kCubic_Segment: {

5643 swap = true;

5644 pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);

5645 debugShowCubicLineIntersection(pts, wn, wt, ts);

5646 break;

5647 }

5648 default:

5649 SkASSERT(0);

5650 }

5651 break;

5652 case Work::kQuad_Segment:

5653 switch (wn.segmentType()) {

5654 case Work::kHorizontalLine_Segment:

5655 pts = HQuadIntersect(wt.pts(), wn.left(),

5656 wn.right(), wn.y(), wn.xFlipped(), ts);

5657 break;

5658 case Work::kVerticalLine_Segment:

5659 pts = VQuadIntersect(wt.pts(), wn.top(),

5660 wn.bottom(), wn.x(), wn.yFlipped(), ts);

5661 break;

5662 case Work::kLine_Segment: {

5663 pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);

5664 debugShowQuadLineIntersection(pts, wt, wn, ts);

5665 break;

5666 }

5667 case Work::kQuad_Segment: {

5668 pts = QuadIntersect(wt.pts(), wn.pts(), ts);

5669 debugShowQuadIntersection(pts, wt, wn, ts);

5670 break;

5671 }

5672 case Work::kCubic_Segment: {

5673 #if APPROXIMATE_CUBICS

5674 swap = true;

5675 pts = CubicQuadIntersect(wn.pts(), wt.pts(), ts);

5676 debugShowCubicQuadIntersection(pts, wn, wt, ts);

5677 #else

5678 wt.promoteToCubic();

5679 pts = CubicIntersect(wt.cubic(), wn.pts(), ts);

5680 debugShowCubicIntersection(pts, wt, wn, ts);

5681 #endif

5682 break;

5683 }

5684 default:

5685 SkASSERT(0);

5686 }

5687 break;

5688 case Work::kCubic_Segment:

5689 switch (wn.segmentType()) {

5690 case Work::kHorizontalLine_Segment:

5691 pts = HCubicIntersect(wt.pts(), wn.left(),

5692 wn.right(), wn.y(), wn.xFlipped(), ts);

5693 debugShowCubicLineIntersection(pts, wt, wn, ts);

5694 break;

5695 case Work::kVerticalLine_Segment:

5696 pts = VCubicIntersect(wt.pts(), wn.top(),

5697 wn.bottom(), wn.x(), wn.yFlipped(), ts);

5698 debugShowCubicLineIntersection(pts, wt, wn, ts);

5699 break;

5700 case Work::kLine_Segment: {

5701 pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);

5702 debugShowCubicLineIntersection(pts, wt, wn, ts);

5703 break;

5704 }

5705 case Work::kQuad_Segment: {

5706 #if APPROXIMATE_CUBICS

5707 pts = CubicQuadIntersect(wt.pts(), wn.pts(), ts);

5708 debugShowCubicQuadIntersection(pts, wt, wn, ts);

5709 #else

5710 wn.promoteToCubic();

5711 pts = CubicIntersect(wt.pts(), wn.cubic(), ts);

5712 debugShowCubicIntersection(pts, wt, wn, ts);

5713 #endif

5714 break;

5715 }

5716 case Work::kCubic_Segment: {

5717 pts = CubicIntersect(wt.pts(), wn.pts(), ts);

5718 debugShowCubicIntersection(pts, wt, wn, ts);

5719 break;

5720 }

5721 default:

5722 SkASSERT(0);

5723 }

5724 break;

5725 default:

5726 SkASSERT(0);

5727 }

5728 if (!foundCommonContour && pts > 0) {

5729 test->addCross(next);

5730 next->addCross(test);

5731 foundCommonContour = true;

5732 }

5733 // in addition to recording T values, record matching segment

5734 if (ts.unsortable()) {

5735 bool start = true;

5736 for (int pt = 0; pt < ts.used(); ++pt) {

5737 // FIXME: if unsortable, the other points to the original. T his logic is

5738 // untested downstream.

5739 SkPoint point = ts.fPt[pt].asSkPoint();

5740 int testTAt = wt.addUnsortableT(wt, start, point, ts.fT[swap ][pt]);

5741 wt.addOtherT(testTAt, ts.fT[swap][pt], testTAt);

5742 testTAt = wn.addUnsortableT(wn, start ^ ts.fFlip, point, ts. fT[!swap][pt]);

5743 wn.addOtherT(testTAt, ts.fT[!swap][pt], testTAt);

5744 start ^= true;

5745 }

5746 continue;

5747 }

5748 if (pts == 2) {

5749 if (wn.segmentType() <= Work::kLine_Segment

5750 && wt.segmentType() <= Work::kLine_Segment) {

5751 wt.addCoincident(wn, ts, swap);

5752 continue;

5753 }

5754 if (wn.segmentType() >= Work::kQuad_Segment

5755 && wt.segmentType() >= Work::kQuad_Segment

5756 && ts.fIsCoincident[0]) {

5757 SkASSERT(ts.coincidentUsed() == 2);

5758 wt.addCoincident(wn, ts, swap);

5759 continue;

5760 }

5761

5762 }

5763 for (int pt = 0; pt < pts; ++pt) {

5764 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);

5765 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);

5766 SkPoint point = ts.fPt[pt].asSkPoint();

5767 int testTAt = wt.addT(wn, point, ts.fT[swap][pt]);

5768 int nextTAt = wn.addT(wt, point, ts.fT[!swap][pt]);

5769 wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);

5770 wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);

5771 }

5772 } while (wn.advance());

5773 } while (wt.advance());

5774 return true;

5775 }

5776

5777 static void addSelfIntersectTs(Contour* test) {

5778 Work wt;

5779 wt.init(test);

5780 do {

5781 if (wt.segmentType() != Work::kCubic_Segment) {

5782 continue;

5783 }

5784 Intersections ts;

5785 int pts = CubicIntersect(wt.pts(), ts);

5786 debugShowCubicIntersection(pts, wt, ts);

5787 if (!pts) {

5788 continue;

5789 }

5790 SkASSERT(pts == 1);

5791 SkASSERT(ts.fT[0][0] >= 0 && ts.fT[0][0] <= 1);

5792 SkASSERT(ts.fT[1][0] >= 0 && ts.fT[1][0] <= 1);

5793 SkPoint point = ts.fPt[0].asSkPoint();

5794 int testTAt = wt.addSelfT(wt, point, ts.fT[0][0]);

5795 int nextTAt = wt.addT(wt, point, ts.fT[1][0]);

5796 wt.addOtherT(testTAt, ts.fT[1][0], nextTAt);

5797 wt.addOtherT(nextTAt, ts.fT[0][0], testTAt);

5798 } while (wt.advance());

5799 }

5800

5801 // resolve any coincident pairs found while intersecting, and

5802 // see if coincidence is formed by clipping non-concident segments

5803 static void coincidenceCheck(SkTDArray<Contour*>& contourList, int total) {

5804 int contourCount = contourList.count();

5805 #if ONE_PASS_COINCIDENCE_CHECK

5806 for (int cIndex = 0; cIndex < contourCount; ++cIndex) {

5807 Contour* contour = contourList[cIndex];

5808 contour->resolveCoincidence(contourList);

5809 }

5810 #else

5811 for (int cIndex = 0; cIndex < contourCount; ++cIndex) {

5812 Contour* contour = contourList[cIndex];

5813 contour->addCoincidentPoints();

5814 }

5815 for (int cIndex = 0; cIndex < contourCount; ++cIndex) {

5816 Contour* contour = contourList[cIndex];

5817 contour->calcCoincidentWinding();

5818 }

5819 #endif

5820 for (int cIndex = 0; cIndex < contourCount; ++cIndex) {

5821 Contour* contour = contourList[cIndex];

5822 contour->findTooCloseToCall();

5823 }

5824 }

5825

5826 static int contourRangeCheckY(SkTDArray<Contour>& contourList, Segment& curre nt, int& index,

5827 int& endIndex, double& bestHit, SkScalar& bestDx, bool& tryAgain, double & mid, bool opp) {

5828 SkPoint basePt;

5829 double tAtMid = current->tAtMid(index, endIndex, mid);

5830 current->xyAtT(tAtMid, basePt);

5831 int contourCount = contourList.count();

5832 SkScalar bestY = SK_ScalarMin;

5833 Segment* bestSeg = NULL;

5834 int bestTIndex;

5835 bool bestOpp;

5836 bool hitSomething = false;

5837 for (int cTest = 0; cTest < contourCount; ++cTest) {

5838 Contour* contour = contourList[cTest];

5839 bool testOpp = contour->operand() ^ current->operand() ^ opp;

5840 if (basePt.fY < contour->bounds().fTop) {

5841 continue;

5842 }

5843 if (bestY > contour->bounds().fBottom) {

5844 continue;

5845 }

5846 int segmentCount = contour->segments().count();

5847 for (int test = 0; test < segmentCount; ++test) {

5848 Segment* testSeg = &contour->segments()[test];

5849 SkScalar testY = bestY;

5850 double testHit;

5851 int testTIndex = testSeg->crossedSpanY(basePt, testY, testHit, hitSo mething, tAtMid,

5852 testOpp, testSeg == current);

5853 if (testTIndex < 0) {

5854 if (testTIndex == SK_MinS32) {

5855 hitSomething = true;

5856 bestSeg = NULL;

5857 goto abortContours; // vertical encountered, return and try different point

5858 }

5859 continue;

5860 }

5861 if (testSeg == current && current->betweenTs(index, testHit, endInde x)) {

5862 double baseT = current->t(index);

5863 double endT = current->t(endIndex);

5864 double newMid = (testHit - baseT) / (endT - baseT);

5865 #if DEBUG_WINDING

5866 SkPoint midXY, newXY;

5867 double midT = current->tAtMid(index, endIndex, mid);

5868 current->xyAtT(midT, midXY);

5869 double newMidT = current->tAtMid(index, endIndex, newMid);

5870 current->xyAtT(newMidT, newXY);

5871 SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)"

5872 " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNC TION__,

5873 current->debugID(), mid, newMid,

5874 baseT, current->xAtT(index), current->yAtT(index),

5875 baseT + mid * (endT - baseT), midXY.fX, midXY.fY,

5876 baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,

5877 endT, current->xAtT(endIndex), current->yAtT(endIndex));

5878 #endif

5879 mid = newMid * 2; // calling loop with divide by 2 before contin uing

5880 return SK_MinS32;

5881 }

5882 bestSeg = testSeg;

5883 bestHit = testHit;

5884 bestOpp = testOpp;

5885 bestTIndex = testTIndex;

5886 bestY = testY;

5887 }

5888 }

5889 abortContours:

5890 int result;

5891 if (!bestSeg) {

5892 result = hitSomething ? SK_MinS32 : 0;

5893 } else {

5894 if (bestSeg->windSum(bestTIndex) == SK_MinS32) {

5895 current = bestSeg;

5896 index = bestTIndex;

5897 endIndex = bestSeg->nextSpan(bestTIndex, 1);

5898 SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);

5899 tryAgain = true;

5900 return 0;

5901 }

5902 result = bestSeg->windingAtT(bestHit, bestTIndex, bestOpp, bestDx);

5903 SkASSERT(bestDx);

5904 }

5905 double baseT = current->t(index);

5906 double endT = current->t(endIndex);

5907 bestHit = baseT + mid * (endT - baseT);

5908 return result;

5909 }

5910

5911 static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& en d) {

5912 int contourCount = contourList.count();

5913 Segment* result;

5914 for (int cIndex = 0; cIndex < contourCount; ++cIndex) {

5915 Contour* contour = contourList[cIndex];

5916 result = contour->undoneSegment(start, end);

5917 if (result) {

5918 return result;

5919 }

5920 }

5921 return NULL;

5922 }

5923

5924 #define OLD_FIND_CHASE 1

5925

5926 static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) {

5927 while (chase.count()) {

5928 Span* span;

5929 chase.pop(&span);

5930 const Span& backPtr = span->fOther->span(span->fOtherIndex);

5931 Segment* segment = backPtr.fOther;

5932 tIndex = backPtr.fOtherIndex;

5933 SkTDArray<Angle> angles;

5934 int done = 0;

5935 if (segment->activeAngle(tIndex, done, angles)) {

5936 Angle* last = angles.end() - 1;

5937 tIndex = last->start();

5938 endIndex = last->end();

5939 #if TRY_ROTATE

5940 *chase.insert(0) = span;

5941 #else

5942 *chase.append() = span;

5943 #endif

5944 return last->segment();

5945 }

5946 if (done == angles.count()) {

5947 continue;

5948 }

5949 SkTDArray<Angle*> sorted;

5950 bool sortable = Segment::SortAngles(angles, sorted);

5951 int angleCount = sorted.count();

5952 #if DEBUG_SORT

5953 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);

5954 #endif

5955 if (!sortable) {

5956 continue;

5957 }

5958 // find first angle, initialize winding to computed fWindSum

5959 int firstIndex = -1;

5960 const Angle* angle;

5961 #if OLD_FIND_CHASE

5962 int winding;

5963 do {

5964 angle = sorted[++firstIndex];

5965 segment = angle->segment();

5966 winding = segment->windSum(angle);

5967 } while (winding == SK_MinS32);

5968 int spanWinding = segment->spanSign(angle->start(), angle->end());

5969 #if DEBUG_WINDING

5970 SkDebugf("%s winding=%d spanWinding=%d\n",

5971 __FUNCTION__, winding, spanWinding);

5972 #endif

5973 // turn span winding into contour winding

5974 if (spanWinding * winding < 0) {

5975 winding += spanWinding;

5976 }

5977 #if DEBUG_SORT

5978 segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0);

5979 #endif

5980 // we care about first sign and whether wind sum indicates this

5981 // edge is inside or outside. Maybe need to pass span winding

5982 // or first winding or something into this function?

5983 // advance to first undone angle, then return it and winding

5984 // (to set whether edges are active or not)

5985 int nextIndex = firstIndex + 1;

5986 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;

5987 angle = sorted[firstIndex];

5988 winding -= angle->segment()->spanSign(angle);

5989 #else

5990 do {

5991 angle = sorted[++firstIndex];

5992 segment = angle->segment();

5993 } while (segment->windSum(angle) == SK_MinS32);

5994 #if DEBUG_SORT

5995 segment->debugShowSort(__FUNCTION__, sorted, firstIndex);

5996 #endif

5997 int sumWinding = segment->updateWindingReverse(angle);

5998 int nextIndex = firstIndex + 1;

5999 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;

6000 Segment* first = NULL;

6001 #endif

6002 do {

6003 SkASSERT(nextIndex != firstIndex);

6004 if (nextIndex == angleCount) {

6005 nextIndex = 0;

6006 }

6007 angle = sorted[nextIndex];

6008 segment = angle->segment();

6009 #if OLD_FIND_CHASE

6010 int maxWinding = winding;

6011 winding -= segment->spanSign(angle);

6012 #if DEBUG_SORT

6013 SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__ ,

6014 segment->debugID(), maxWinding, winding, angle->sign());

6015 #endif

6016 tIndex = angle->start();

6017 endIndex = angle->end();

6018 int lesser = SkMin32(tIndex, endIndex);

6019 const Span& nextSpan = segment->span(lesser);

6020 if (!nextSpan.fDone) {

6021 #if 1

6022 // FIXME: this be wrong? assign startWinding if edge is in

6023 // same direction. If the direction is opposite, winding to

6024 // assign is flipped sign or +/- 1?

6025 if (useInnerWinding(maxWinding, winding)) {

6026 maxWinding = winding;

6027 }

6028 segment->markAndChaseWinding(angle, maxWinding, 0);

6029 #endif

6030 break;

6031 }

6032 #else

6033 int start = angle->start();

6034 int end = angle->end();

6035 int maxWinding;

6036 segment->setUpWinding(start, end, maxWinding, sumWinding);

6037 if (!segment->done(angle)) {

6038 if (!first) {

6039 first = segment;

6040 tIndex = start;

6041 endIndex = end;

6042 }

6043 (void) segment->markAngle(maxWinding, sumWinding, true, angle);

6044 }

6045 #endif

6046 } while (++nextIndex != lastIndex);

6047 #if TRY_ROTATE

6048 *chase.insert(0) = span;

6049 #else

6050 *chase.append() = span;

6051 #endif

6052 return segment;

6053 }

6054 return NULL;

6055 }

6056

6057 #if DEBUG_ACTIVE_SPANS

6058 static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) {

6059 int index;

6060 for (index = 0; index < contourList.count(); ++ index) {

6061 contourList[index]->debugShowActiveSpans();

6062 }

6063 for (index = 0; index < contourList.count(); ++ index) {

6064 contourList[index]->validateActiveSpans();

6065 }

6066 }

6067 #endif

6068

6069 static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index,

6070 int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool only Sortable) {

6071 Segment* result;

6072 do {

6073 SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};

6074 int contourCount = contourList.count();

6075 Segment* topStart = NULL;

6076 done = true;

6077 for (int cIndex = 0; cIndex < contourCount; ++cIndex) {

6078 Contour* contour = contourList[cIndex];

6079 if (contour->done()) {

6080 continue;

6081 }

6082 const Bounds& bounds = contour->bounds();

6083 if (bounds.fBottom < topLeft.fY) {

6084 done = false;

6085 continue;

6086 }

6087 if (bounds.fBottom == topLeft.fY && bounds.fRight < topLeft.fX) {

6088 done = false;

6089 continue;

6090 }

6091 contour->topSortableSegment(topLeft, bestXY, topStart);

6092 if (!contour->done()) {

6093 done = false;

6094 }

6095 }

6096 if (!topStart) {

6097 return NULL;

6098 }

6099 topLeft = bestXY;

6100 result = topStart->findTop(index, endIndex, unsortable, onlySortable);

6101 } while (!result);

6102 return result;

6103 }

6104

6105 static int rightAngleWinding(SkTDArray<Contour*>& contourList,

6106 Segment*& current, int& index, int& endIndex, double& tHit, SkScalar& hi tDx, bool& tryAgain,

6107 bool opp) {

6108 double test = 0.9;

6109 int contourWinding;

6110 do {

6111 contourWinding = contourRangeCheckY(contourList, current, index, endInde x, tHit, hitDx,

6112 tryAgain, test, opp);

6113 if (contourWinding != SK_MinS32 \|\| tryAgain) {

6114 return contourWinding;

6115 }

6116 test /= 2;

6117 } while (!approximately_negative(test));

6118 SkASSERT(0); // should be OK to comment out, but interested when this hits

6119 return contourWinding;

6120 }

6121

6122 static void skipVertical(SkTDArray<Contour*>& contourList,

6123 Segment*& current, int& index, int& endIndex) {

6124 if (!current->isVertical(index, endIndex)) {

6125 return;

6126 }

6127 int contourCount = contourList.count();

6128 for (int cIndex = 0; cIndex < contourCount; ++cIndex) {

6129 Contour* contour = contourList[cIndex];

6130 if (contour->done()) {

6131 continue;

6132 }

6133 current = contour->nonVerticalSegment(index, endIndex);

6134 if (current) {

6135 return;

6136 }

6137 }

6138 }

6139

6140 static Segment* findSortableTop(SkTDArray<Contour*>& contourList, bool& firstCon tour, int& index,

6141 int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool bina ry) {

6142 Segment* current = findSortableTop(contourList, index, endIndex, topLeft, un sortable, done,

6143 true);

6144 if (!current) {

6145 return NULL;

6146 }

6147 if (firstContour) {

6148 current->initWinding(index, endIndex);

6149 firstContour = false;

6150 return current;

6151 }

6152 int minIndex = SkMin32(index, endIndex);

6153 int sumWinding = current->windSum(minIndex);

6154 if (sumWinding != SK_MinS32) {

6155 return current;

6156 }

6157 sumWinding = current->computeSum(index, endIndex, binary);

6158 if (sumWinding != SK_MinS32) {

6159 return current;

6160 }

6161 int contourWinding;

6162 int oppContourWinding = 0;

6163 // the simple upward projection of the unresolved points hit unsortable angl es

6164 // shoot rays at right angles to the segment to find its winding, ignoring a ngle cases

6165 bool tryAgain;

6166 double tHit;

6167 SkScalar hitDx = 0;

6168 SkScalar hitOppDx = 0;

6169 do {

6170 // if current is vertical, find another candidate which is not

6171 // if only remaining candidates are vertical, then they can be marked do ne

6172 SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);

6173 skipVertical(contourList, current, index, endIndex);

6174 SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);

6175 tryAgain = false;

6176 contourWinding = rightAngleWinding(contourList, current, index, endIndex , tHit, hitDx,

6177 tryAgain, false);

6178 if (tryAgain) {

6179 continue;

6180 }

6181 if (!binary) {

6182 break;

6183 }

6184 oppContourWinding = rightAngleWinding(contourList, current, index, endIn dex, tHit, hitOppDx,

6185 tryAgain, true);

6186 } while (tryAgain);

6187

6188 current->initWinding(index, endIndex, tHit, contourWinding, hitDx, oppContou rWinding, hitOppDx);

6189 return current;

6190 }

6191

6192 // rewrite that abandons keeping local track of winding

6193 static bool bridgeWinding(SkTDArray<Contour*>& contourList, PathWrapper& simple) {

6194 bool firstContour = true;

6195 bool unsortable = false;

6196 bool topUnsortable = false;

6197 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};

6198 do {

6199 int index, endIndex;

6200 bool topDone;

6201 Segment* current = findSortableTop(contourList, firstContour, index, end Index, topLeft,

6202 topUnsortable, topDone, false);

6203 if (!current) {

6204 if (topUnsortable \|\| !topDone) {

6205 topUnsortable = false;

6206 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMi n);

6207 topLeft.fX = topLeft.fY = SK_ScalarMin;

6208 continue;

6209 }

6210 break;

6211 }

6212 SkTDArray<Span*> chaseArray;

6213 do {

6214 if (current->activeWinding(index, endIndex)) {

6215 do {

6216 #if DEBUG_ACTIVE_SPANS

6217 if (!unsortable && current->done()) {

6218 debugShowActiveSpans(contourList);

6219 }

6220 #endif

6221 SkASSERT(unsortable \|\| !current->done());

6222 int nextStart = index;

6223 int nextEnd = endIndex;

6224 Segment* next = current->findNextWinding(chaseArray, nextSta rt, nextEnd,

6225 unsortable);

6226 if (!next) {

6227 if (!unsortable && simple.hasMove()

6228 && current->verb() != SkPath::kLine_Verb

6229 && !simple.isClosed()) {

6230 current->addCurveTo(index, endIndex, simple, true);

6231 SkASSERT(simple.isClosed());

6232 }

6233 break;

6234 }

6235 #if DEBUG_FLOW

6236 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", _ _FUNCTION__,

6237 current->debugID(), current->xyAtT(index).fX, current->xyAtT (index).fY,

6238 current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);

6239 #endif

6240 current->addCurveTo(index, endIndex, simple, true);

6241 current = next;

6242 index = nextStart;

6243 endIndex = nextEnd;

6244 } while (!simple.isClosed() && (!unsortable

6245 \|\| !current->done(SkMin32(index, endIndex))));

6246 if (current->activeWinding(index, endIndex) && !simple.isClosed( )) {

6247 SkASSERT(unsortable);

6248 int min = SkMin32(index, endIndex);

6249 if (!current->done(min)) {

6250 current->addCurveTo(index, endIndex, simple, true);

6251 current->markDoneUnary(min);

6252 }

6253 }

6254 simple.close();

6255 } else {

6256 Span* last = current->markAndChaseDoneUnary(index, endIndex);

6257 if (last && !last->fLoop) {

6258 *chaseArray.append() = last;

6259 }

6260 }

6261 current = findChase(chaseArray, index, endIndex);

6262 #if DEBUG_ACTIVE_SPANS

6263 debugShowActiveSpans(contourList);

6264 #endif

6265 if (!current) {

6266 break;

6267 }

6268 } while (true);

6269 } while (true);

6270 return simple.someAssemblyRequired();

6271 }

6272

6273 // returns true if all edges were processed

6274 static bool bridgeXor(SkTDArray<Contour*>& contourList, PathWrapper& simple) {

6275 Segment* current;

6276 int start, end;

6277 bool unsortable = false;

6278 bool closable = true;

6279 while ((current = findUndone(contourList, start, end))) {

6280 do {

6281 #if DEBUG_ACTIVE_SPANS

6282 if (!unsortable && current->done()) {

6283 debugShowActiveSpans(contourList);

6284 }

6285 #endif

6286 SkASSERT(unsortable \|\| !current->done());

6287 int nextStart = start;

6288 int nextEnd = end;

6289 Segment* next = current->findNextXor(nextStart, nextEnd, unsortable) ;

6290 if (!next) {

6291 if (!unsortable && simple.hasMove()

6292 && current->verb() != SkPath::kLine_Verb

6293 && !simple.isClosed()) {

6294 current->addCurveTo(start, end, simple, true);

6295 SkASSERT(simple.isClosed());

6296 }

6297 break;

6298 }

6299 #if DEBUG_FLOW

6300 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", _ _FUNCTION__,

6301 current->debugID(), current->xyAtT(start).fX, current->xyAtT (start).fY,

6302 current->xyAtT(end).fX, current->xyAtT(end).fY);

6303 #endif

6304 current->addCurveTo(start, end, simple, true);

6305 current = next;

6306 start = nextStart;

6307 end = nextEnd;

6308 } while (!simple.isClosed() && (!unsortable \|\| !current->done(SkMin32(st art, end))));

6309 if (!simple.isClosed()) {

6310 SkASSERT(unsortable);

6311 int min = SkMin32(start, end);

6312 if (!current->done(min)) {

6313 current->addCurveTo(start, end, simple, true);

6314 current->markDone(min, 1);

6315 }

6316 closable = false;

6317 }

6318 simple.close();

6319 #if DEBUG_ACTIVE_SPANS

6320 debugShowActiveSpans(contourList);

6321 #endif

6322 }

6323 return closable;

6324 }

6325

6326 static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {

6327 int contourCount = contourList.count();

6328 for (int cTest = 0; cTest < contourCount; ++cTest) {

6329 Contour* contour = contourList[cTest];

6330 contour->fixOtherTIndex();

6331 }

6332 }

6333

6334 static void sortSegments(SkTDArray<Contour*>& contourList) {

6335 int contourCount = contourList.count();

6336 for (int cTest = 0; cTest < contourCount; ++cTest) {

6337 Contour* contour = contourList[cTest];

6338 contour->sortSegments();

6339 }

6340 }

6341

6342 static void makeContourList(SkTArray<Contour>& contours, SkTDArray<Contour*>& li st,

6343 bool evenOdd, bool oppEvenOdd) {

6344 int count = contours.count();

6345 if (count == 0) {

6346 return;

6347 }

6348 for (int index = 0; index < count; ++index) {

6349 Contour& contour = contours[index];

6350 contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd);

6351 *list.append() = &contour;

6352 }

6353 QSort<Contour>(list.begin(), list.end() - 1);

6354 }

6355

6356 static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) {

6357 return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY);

6358 }

6359

6360 static bool lessThan(SkTDArray<double>& distances, const int one, const int two) {

6361 return distances[one] < distances[two];

6362 }

6363 /*

6364 check start and end of each contour

6365 if not the same, record them

6366 match them up

6367 connect closest

6368 reassemble contour pieces into new path

6369 */

6370 static void assemble(const PathWrapper& path, PathWrapper& simple) {

6371 #if DEBUG_PATH_CONSTRUCTION

6372 SkDebugf("%s\n", __FUNCTION__);

6373 #endif

6374 SkTArray<Contour> contours;

6375 EdgeBuilder builder(path, contours);

6376 builder.finish();

6377 int count = contours.count();

6378 int outer;

6379 SkTDArray<int> runs; // indices of partial contours

6380 for (outer = 0; outer < count; ++outer) {

6381 const Contour& eContour = contours[outer];

6382 const SkPoint& eStart = eContour.start();

6383 const SkPoint& eEnd = eContour.end();

6384 #if DEBUG_ASSEMBLE

6385 SkDebugf("%s contour", __FUNCTION__);

6386 if (!approximatelyEqual(eStart, eEnd)) {

6387 SkDebugf("[%d]", runs.count());

6388 } else {

6389 SkDebugf(" ");

6390 }

6391 SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",

6392 eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);

6393 #endif

6394 if (approximatelyEqual(eStart, eEnd)) {

6395 eContour.toPath(simple);

6396 continue;

6397 }

6398 *runs.append() = outer;

6399 }

6400 count = runs.count();

6401 if (count == 0) {

6402 return;

6403 }

6404 SkTDArray<int> sLink, eLink;

6405 sLink.setCount(count);

6406 eLink.setCount(count);

6407 int rIndex, iIndex;

6408 for (rIndex = 0; rIndex < count; ++rIndex) {

6409 sLink[rIndex] = eLink[rIndex] = SK_MaxS32;

6410 }

6411 SkTDArray<double> distances;

6412 const int ends = count * 2; // all starts and ends

6413 const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2

6414 distances.setCount(entries);

6415 for (rIndex = 0; rIndex < ends - 1; ++rIndex) {

6416 outer = runs[rIndex >> 1];

6417 const Contour& oContour = contours[outer];

6418 const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start();

6419 const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)

6420 * ends - rIndex - 1;

6421 for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {

6422 int inner = runs[iIndex >> 1];

6423 const Contour& iContour = contours[inner];

6424 const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start();

6425 double dx = iPt.fX - oPt.fX;

6426 double dy = iPt.fY - oPt.fY;

6427 double dist = dx * dx + dy * dy;

6428 distances[row + iIndex] = dist; // oStart distance from iStart

6429 }

6430 }

6431 SkTDArray<int> sortedDist;

6432 sortedDist.setCount(entries);

6433 for (rIndex = 0; rIndex < entries; ++rIndex) {

6434 sortedDist[rIndex] = rIndex;

6435 }

6436 QSort<SkTDArray<double>, int>(distances, sortedDist.begin(), sortedDist.end( ) - 1, lessThan);

6437 int remaining = count; // number of start/end pairs

6438 for (rIndex = 0; rIndex < entries; ++rIndex) {

6439 int pair = sortedDist[rIndex];

6440 int row = pair / ends;

6441 int col = pair - row * ends;

6442 int thingOne = row < col ? row : ends - row - 2;

6443 int ndxOne = thingOne >> 1;

6444 bool endOne = thingOne & 1;

6445 int* linkOne = endOne ? eLink.begin() : sLink.begin();

6446 if (linkOne[ndxOne] != SK_MaxS32) {

6447 continue;

6448 }

6449 int thingTwo = row < col ? col : ends - row + col - 1;

6450 int ndxTwo = thingTwo >> 1;

6451 bool endTwo = thingTwo & 1;

6452 int* linkTwo = endTwo ? eLink.begin() : sLink.begin();

6453 if (linkTwo[ndxTwo] != SK_MaxS32) {

6454 continue;

6455 }

6456 SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);

6457 bool flip = endOne == endTwo;

6458 linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;

6459 linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;

6460 if (!--remaining) {

6461 break;

6462 }

6463 }

6464 SkASSERT(!remaining);

6465 #if DEBUG_ASSEMBLE

6466 for (rIndex = 0; rIndex < count; ++rIndex) {

6467 int s = sLink[rIndex];

6468 int e = eLink[rIndex];

6469 SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : ' e',

6470 s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);

6471 }

6472 #endif

6473 rIndex = 0;

6474 do {

6475 bool forward = true;

6476 bool first = true;

6477 int sIndex = sLink[rIndex];

6478 SkASSERT(sIndex != SK_MaxS32);

6479 sLink[rIndex] = SK_MaxS32;

6480 int eIndex;

6481 if (sIndex < 0) {

6482 eIndex = sLink[~sIndex];

6483 sLink[~sIndex] = SK_MaxS32;

6484 } else {

6485 eIndex = eLink[sIndex];

6486 eLink[sIndex] = SK_MaxS32;

6487 }

6488 SkASSERT(eIndex != SK_MaxS32);

6489 #if DEBUG_ASSEMBLE

6490 SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',

6491 sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',

6492 eIndex < 0 ? ~eIndex : eIndex);

6493 #endif

6494 do {

6495 outer = runs[rIndex];

6496 const Contour& contour = contours[outer];

6497 if (first) {

6498 first = false;

6499 const SkPoint* startPtr = &contour.start();

6500 simple.deferredMove(startPtr[0]);

6501 }

6502 if (forward) {

6503 contour.toPartialForward(simple);

6504 } else {

6505 contour.toPartialBackward(simple);

6506 }

6507 #if DEBUG_ASSEMBLE

6508 SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex ,

6509 eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,

6510 sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));

6511 #endif

6512 if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {

6513 simple.close();

6514 break;

6515 }

6516 if (forward) {

6517 eIndex = eLink[rIndex];

6518 SkASSERT(eIndex != SK_MaxS32);

6519 eLink[rIndex] = SK_MaxS32;

6520 if (eIndex >= 0) {

6521 SkASSERT(sLink[eIndex] == rIndex);

6522 sLink[eIndex] = SK_MaxS32;

6523 } else {

6524 SkASSERT(eLink[~eIndex] == ~rIndex);

6525 eLink[~eIndex] = SK_MaxS32;

6526 }

6527 } else {

6528 eIndex = sLink[rIndex];

6529 SkASSERT(eIndex != SK_MaxS32);

6530 sLink[rIndex] = SK_MaxS32;

6531 if (eIndex >= 0) {

6532 SkASSERT(eLink[eIndex] == rIndex);

6533 eLink[eIndex] = SK_MaxS32;

6534 } else {

6535 SkASSERT(sLink[~eIndex] == ~rIndex);

6536 sLink[~eIndex] = SK_MaxS32;

6537 }

6538 }

6539 rIndex = eIndex;

6540 if (rIndex < 0) {

6541 forward ^= 1;

6542 rIndex = ~rIndex;

6543 }

6544 } while (true);

6545 for (rIndex = 0; rIndex < count; ++rIndex) {

6546 if (sLink[rIndex] != SK_MaxS32) {

6547 break;

6548 }

6549 }

6550 } while (rIndex < count);

6551 #if DEBUG_ASSEMBLE

6552 for (rIndex = 0; rIndex < count; ++rIndex) {

6553 SkASSERT(sLink[rIndex] == SK_MaxS32);

6554 SkASSERT(eLink[rIndex] == SK_MaxS32);

6555 }

6556 #endif

6557 }

6558

6559 void simplifyx(const SkPath& path, SkPath& result) {

6560 #if DEBUG_SORT \|\| DEBUG_SWAP_TOP

6561 gDebugSortCount = gDebugSortCountDefault;

6562 #endif

6563 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness

6564 result.reset();

6565 result.setFillType(SkPath::kEvenOdd_FillType);

6566 PathWrapper simple(result);

6567

6568 // turn path into list of segments

6569 SkTArray<Contour> contours;

6570 EdgeBuilder builder(path, contours);

6571 builder.finish();

6572 SkTDArray<Contour*> contourList;

6573 makeContourList(contours, contourList, false, false);

6574 Contour** currentPtr = contourList.begin();

6575 if (!currentPtr) {

6576 return;

6577 }

6578 Contour** listEnd = contourList.end();

6579 // find all intersections between segments

6580 do {

6581 Contour** nextPtr = currentPtr;

6582 Contour* current = *currentPtr++;

6583 if (current->containsCubics()) {

6584 addSelfIntersectTs(current);

6585 }

6586 Contour* next;

6587 do {

6588 next = *nextPtr++;

6589 } while (addIntersectTs(current, next) && nextPtr != listEnd);

6590 } while (currentPtr != listEnd);

6591 // eat through coincident edges

6592 coincidenceCheck(contourList, 0);

6593 fixOtherTIndex(contourList);

6594 sortSegments(contourList);

6595 #if DEBUG_ACTIVE_SPANS

6596 debugShowActiveSpans(contourList);

6597 #endif

6598 // construct closed contours

6599 if (builder.xorMask() == kWinding_Mask ? bridgeWinding(contourList, simple)

6600 : !bridgeXor(contourList, simple))

6601 { // if some edges could not be resolved, assemble remaining fragments

6602 SkPath temp;

6603 temp.setFillType(SkPath::kEvenOdd_FillType);

6604 PathWrapper assembled(temp);

6605 assemble(simple, assembled);

6606 result = *assembled.nativePath();

6607 }

6608 }

OLD	NEW

« no previous file with comments | « experimental/Intersection/Simplify.h ('k') | experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp » ('j') | no next file with comments »