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

Side by Side Diff: experimental/Intersection/EdgeWalker.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

8 #include "Simplify.h"

9

10 #undef SkASSERT

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

12

13 // FIXME: remove once debugging is complete

14 #if 01 // set to 1 for no debugging whatsoever

15

16 //const bool gRunTestsInOneThread = false;

17

18 #define DEBUG_ACTIVE_LESS_THAN 0

19 #define DEBUG_ADD 0

20 #define DEBUG_ADD_BOTTOM_TS 0

21 #define DEBUG_ADD_INTERSECTING_TS 0

22 #define DEBUG_ADJUST_COINCIDENT 0

23 #define DEBUG_ASSEMBLE 0

24 #define DEBUG_BOTTOM 0

25 #define DEBUG_BRIDGE 0

26 #define DEBUG_DUMP 0

27 #define DEBUG_SORT_HORIZONTAL 0

28 #define DEBUG_OUT 0

29 #define DEBUG_OUT_LESS_THAN 0

30 #define DEBUG_SPLIT 0

31 #define DEBUG_STITCH_EDGE 0

32 #define DEBUG_TRIM_LINE 0

33

34 #else

35

36 //const bool gRunTestsInOneThread = true;

37

38 #define DEBUG_ACTIVE_LESS_THAN 0

39 #define DEBUG_ADD 01

40 #define DEBUG_ADD_BOTTOM_TS 0

41 #define DEBUG_ADD_INTERSECTING_TS 0

42 #define DEBUG_ADJUST_COINCIDENT 1

43 #define DEBUG_ASSEMBLE 1

44 #define DEBUG_BOTTOM 0

45 #define DEBUG_BRIDGE 1

46 #define DEBUG_DUMP 1

47 #define DEBUG_SORT_HORIZONTAL 01

48 #define DEBUG_OUT 01

49 #define DEBUG_OUT_LESS_THAN 0

50 #define DEBUG_SPLIT 1

51 #define DEBUG_STITCH_EDGE 1

52 #define DEBUG_TRIM_LINE 1

53

54 #endif

55

56 #if DEBUG_ASSEMBLE \|\| DEBUG_BRIDGE

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

58 #endif

59 #if DEBUG_STITCH_EDGE

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

61 #endif

62

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

64 Intersections& intersections) {

65 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};

66 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};

67 return intersect(aLine, bLine, intersections);

68 }

69

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

71 Intersections& intersections) {

72 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a [2].fY}};

73 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};

74 intersect(aQuad, bLine, intersections);

75 return intersections.fUsed;

76 }

77

78 static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3],

79 Intersections& intersections) {

80 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2] .fY},

81 {a[3].fX, a[3].fY}};

82 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};

83 return intersect(aCubic, bLine, intersections);

84 }

85

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

87 Intersections& intersections) {

88 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a [2].fY}};

89 const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b [2].fY}};

90 intersect2(aQuad, bQuad, intersections);

91 return intersections.fUsed;

92 }

93

94 static int CubicIntersect(const SkPoint a[4], const SkPoint b[4],

95 Intersections& intersections) {

96 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2] .fY},

97 {a[3].fX, a[3].fY}};

98 const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2] .fY},

99 {b[3].fX, b[3].fY}};

100 intersect(aCubic, bCubic, intersections);

101 return intersections.fUsed;

102 }

103

104 static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,

105 SkScalar y, double aRange[2]) {

106 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};

107 return horizontalLineIntersect(aLine, left, right, y, aRange);

108 }

109

110 static int QuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,

111 SkScalar y, double aRange[3]) {

112 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a [2].fY}};

113 return horizontalIntersect(aQuad, left, right, y, aRange);

114 }

115

116 static int CubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,

117 SkScalar y, double aRange[4]) {

118 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2] .fY},

119 {a[3].fX, a[3].fY}};

120 return horizontalIntersect(aCubic, left, right, y, aRange);

121 }

122

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

124 const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};

125 double x, y;

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

127 out->fX = SkDoubleToScalar(x);

128 out->fY = SkDoubleToScalar(y);

129 }

130

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

132 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[ 2].fY}};

133 double x, y;

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

135 out->fX = SkDoubleToScalar(x);

136 out->fY = SkDoubleToScalar(y);

137 }

138

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

140 const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2]. fY},

141 {a[3].fX, a[3].fY}};

142 double x, y;

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

144 out->fX = SkDoubleToScalar(x);

145 out->fY = SkDoubleToScalar(y);

146 }

147

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

149 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};

150 double y;

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

152 return SkDoubleToScalar(y);

153 }

154

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

156 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[ 2].fY}};

157 double y;

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

159 return SkDoubleToScalar(y);

160 }

161

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

163 const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2]. fY},

164 {a[3].fX, a[3].fY}};

165 double y;

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

167 return SkDoubleToScalar(y);

168 }

169

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

171 SkPoint sub[2]) {

172 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};

173 _Line dst;

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

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

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

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

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

179 }

180

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

182 SkPoint sub[3]) {

183 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},

184 {a[2].fX, a[2].fY}};

185 Quadratic dst;

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

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

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

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

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

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

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

193 }

194

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

196 SkPoint sub[4]) {

197 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},

198 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};

199 Cubic dst;

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

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

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

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

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

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

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

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

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

209 }

210

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

212 SkRect& bounds) {

213 SkPoint dst[3];

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

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

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

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

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

219 }

220 }

221

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

223 SkRect& bounds) {

224 SkPoint dst[4];

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

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

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

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

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

230 }

231 }

232

233 static SkPath::Verb QuadReduceOrder(SkPoint a[4]) {

234 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},

235 {a[2].fX, a[2].fY}};

236 Quadratic dst;

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

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

239 a[index].fX = SkDoubleToScalar(dst[index].x);

240 a[index].fY = SkDoubleToScalar(dst[index].y);

241 }

242 if (order == 1) { // FIXME: allow returning points, caller should discard

243 a[1] = a[0];

244 return (SkPath::Verb) order;

245 }

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

247 }

248

249 static SkPath::Verb CubicReduceOrder(SkPoint a[4]) {

250 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},

251 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};

252 Cubic dst;

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

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

255 a[index].fX = SkDoubleToScalar(dst[index].x);

256 a[index].fY = SkDoubleToScalar(dst[index].y);

257 }

258 if (order == 1) { // FIXME: allow returning points, caller should discard

259 a[1] = a[0];

260 return (SkPath::Verb) order;

261 }

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

263 }

264

265 static bool IsCoincident(const SkPoint a[2], const SkPoint& above,

266 const SkPoint& below) {

267 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};

268 const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}};

269 return implicit_matches_ulps(aLine, bLine, 32);

270 }

271

272 /*

273 list of edges

274 bounds for edge

275 sort

276 active T

277

278 if a contour's bounds is outside of the active area, no need to create edges

279 */

280

281 /* given one or more paths,

282 find the bounds of each contour, select the active contours

283 for each active contour, compute a set of edges

284 each edge corresponds to one or more lines and curves

285 leave edges unbroken as long as possible

286 when breaking edges, compute the t at the break but leave the control points al one

287

288 */

289

290 void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) {

291 SkPath::Iter iter(path, false);

292 SkPoint pts[4];

293 SkPath::Verb verb;

294 SkRect bounds;

295 bounds.setEmpty();

296 int count = 0;

297 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {

298 switch (verb) {

299 case SkPath::kMove_Verb:

300 if (!bounds.isEmpty()) {

301 *boundsArray.append() = bounds;

302 }

303 bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY);

304 count = 0;

305 break;

306 case SkPath::kLine_Verb:

307 count = 1;

308 break;

309 case SkPath::kQuad_Verb:

310 count = 2;

311 break;

312 case SkPath::kCubic_Verb:

313 count = 3;

314 break;

315 case SkPath::kClose_Verb:

316 count = 0;

317 break;

318 default:

319 SkDEBUGFAIL("bad verb");

320 return;

321 }

322 for (int i = 1; i <= count; ++i) {

323 bounds.growToInclude(pts[i].fX, pts[i].fY);

324 }

325 }

326 }

327

328 static bool extendLine(const SkPoint line[2], const SkPoint& add) {

329 // FIXME: allow this to extend lines that have slopes that are nearly equal

330 SkScalar dx1 = line[1].fX - line[0].fX;

331 SkScalar dy1 = line[1].fY - line[0].fY;

332 SkScalar dx2 = add.fX - line[0].fX;

333 SkScalar dy2 = add.fY - line[0].fY;

334 return dx1 * dy2 == dx2 * dy1;

335 }

336

337 // OPTIMIZATION: this should point to a list of input data rather than duplicati ng

338 // the line data here. This would reduce the need to assemble the results.

339 struct OutEdge {

340 bool operator<(const OutEdge& rh) const {

341 const SkPoint& first = fPts[0];

342 const SkPoint& rhFirst = rh.fPts[0];

343 return first.fY == rhFirst.fY

344 ? first.fX < rhFirst.fX

345 : first.fY < rhFirst.fY;

346 }

347

348 SkPoint fPts[4];

349 int fID; // id of edge generating data

350 uint8_t fVerb; // FIXME: not read from everywhere

351 bool fCloseCall; // edge is trimmable if not originally coincident

352 };

353

354 class OutEdgeBuilder {

355 public:

356 OutEdgeBuilder(bool fill)

357 : fFill(fill) {

358 }

359

360 void addCurve(const SkPoint line[4], SkPath::Verb verb, int id,

361 bool closeCall) {

362 OutEdge& newEdge = fEdges.push_back();

363 memcpy(newEdge.fPts, line, (verb + 1) * sizeof(SkPoint));

364 newEdge.fVerb = verb;

365 newEdge.fID = id;

366 newEdge.fCloseCall = closeCall;

367 }

368

369 bool trimLine(SkScalar y, int id) {

370 size_t count = fEdges.count();

371 while (count-- != 0) {

372 OutEdge& edge = fEdges[count];

373 if (edge.fID != id) {

374 continue;

375 }

376 if (edge.fCloseCall) {

377 return false;

378 }

379 SkASSERT(edge.fPts[0].fY <= y);

380 if (edge.fPts[1].fY <= y) {

381 continue;

382 }

383 edge.fPts[1].fX = edge.fPts[0].fX + (y - edge.fPts[0].fY)

384 * (edge.fPts[1].fX - edge.fPts[0].fX)

385 / (edge.fPts[1].fY - edge.fPts[0].fY);

386 edge.fPts[1].fY = y;

387 #if DEBUG_TRIM_LINE

388 SkDebugf("%s edge=%d %1.9g,%1.9g\n", __FUNCTION__, id,

389 edge.fPts[1].fX, y);

390 #endif

391 return true;

392 }

393 return false;

394 }

395

396 void assemble(SkPath& simple) {

397 size_t listCount = fEdges.count();

398 if (listCount == 0) {

399 return;

400 }

401 do {

402 size_t listIndex = 0;

403 int advance = 1;

404 while (listIndex < listCount && fTops[listIndex] == 0) {

405 ++listIndex;

406 }

407 if (listIndex >= listCount) {

408 break;

409 }

410 int closeEdgeIndex = -listIndex - 1;

411 // the curve is deferred and not added right away because the

412 // following edge may extend the first curve.

413 SkPoint firstPt, lastCurve[4];

414 uint8_t lastVerb;

415 #if DEBUG_ASSEMBLE

416 int firstIndex, lastIndex;

417 const int tab = 8;

418 #endif

419 bool doMove = true;

420 int edgeIndex;

421 do {

422 SkPoint* ptArray = fEdges[listIndex].fPts;

423 uint8_t verb = fEdges[listIndex].fVerb;

424 SkPoint* curve[4];

425 if (advance < 0) {

426 curve[0] = &ptArray[verb];

427 if (verb == SkPath::kCubic_Verb) {

428 curve[1] = &ptArray[2];

429 curve[2] = &ptArray[1];

430 }

431 curve[verb] = &ptArray[0];

432 } else {

433 curve[0] = &ptArray[0];

434 if (verb == SkPath::kCubic_Verb) {

435 curve[1] = &ptArray[1];

436 curve[2] = &ptArray[2];

437 }

438 curve[verb] = &ptArray[verb];

439 }

440 if (verb == SkPath::kQuad_Verb) {

441 curve[1] = &ptArray[1];

442 }

443 if (doMove) {

444 firstPt = *curve[0];

445 simple.moveTo(curve[0]->fX, curve[0]->fY);

446 #if DEBUG_ASSEMBLE

447 SkDebugf("%s %d moveTo (%g,%g)\n", __FUNCTION__,

448 listIndex + 1, curve[0]->fX, curve[0]->fY);

449 firstIndex = listIndex;

450 #endif

451 for (int index = 0; index <= verb; ++index) {

452 lastCurve[index] = *curve[index];

453 }

454 doMove = false;

455 } else {

456 bool gap = lastCurve[lastVerb] != *curve[0];

457 if (gap \|\| lastVerb != SkPath::kLine_Verb) { // output the a ccumulated curve before the gap

458 // FIXME: see comment in bridge -- this probably

459 // conceals errors

460 SkASSERT(fFill && UlpsDiff(lastCurve[lastVerb].fY,

461 curve[0]->fY) <= 10);

462 switch (lastVerb) {

463 case SkPath::kLine_Verb:

464 simple.lineTo(lastCurve[1].fX, lastCurve[1].fY);

465 break;

466 case SkPath::kQuad_Verb:

467 simple.quadTo(lastCurve[1].fX, lastCurve[1].fY,

468 lastCurve[2].fX, lastCurve[2].fY);

469 break;

470 case SkPath::kCubic_Verb:

471 simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY,

472 lastCurve[2].fX, lastCurve[2].fY,

473 lastCurve[3].fX, lastCurve[3].fY);

474 break;

475 }

476 #if DEBUG_ASSEMBLE

477 SkDebugf("%*s %d %sTo (%g,%g)\n", tab, "", lastIndex + 1 ,

478 kLVerbStr[lastVerb], lastCurve[lastVerb].fX,

479 lastCurve[lastVerb].fY);

480 #endif

481 }

482 int firstCopy = 1;

483 if (gap \|\| (lastVerb == SkPath::kLine_Verb

484 && (verb != SkPath::kLine_Verb

485 \|\| !extendLine(lastCurve, *curve[verb])))) {

486 // FIXME: see comment in bridge -- this probably

487 // conceals errors

488 SkASSERT(lastCurve[lastVerb] == *curve[0] \|\|

489 (fFill && UlpsDiff(lastCurve[lastVerb].fY,

490 curve[0]->fY) <= 10));

491 simple.lineTo(curve[0]->fX, curve[0]->fY);

492 #if DEBUG_ASSEMBLE

493 SkDebugf("%*s %d gap lineTo (%g,%g)\n", tab, "",

494 lastIndex + 1, curve[0]->fX, curve[0]->fY);

495 #endif

496 firstCopy = 0;

497 } else if (lastVerb != SkPath::kLine_Verb) {

498 firstCopy = 0;

499 }

500 for (int index = firstCopy; index <= verb; ++index) {

501 lastCurve[index] = *curve[index];

502 }

503 }

504 lastVerb = verb;

505 #if DEBUG_ASSEMBLE

506 lastIndex = listIndex;

507 #endif

508 if (advance < 0) {

509 edgeIndex = fTops[listIndex];

510 fTops[listIndex] = 0;

511 } else {

512 edgeIndex = fBottoms[listIndex];

513 fBottoms[listIndex] = 0;

514 }

515 if (edgeIndex) {

516 listIndex = abs(edgeIndex) - 1;

517 if (edgeIndex < 0) {

518 fTops[listIndex] = 0;

519 } else {

520 fBottoms[listIndex] = 0;

521 }

522 }

523 if (edgeIndex == closeEdgeIndex \|\| edgeIndex == 0) {

524 switch (lastVerb) {

525 case SkPath::kLine_Verb:

526 simple.lineTo(lastCurve[1].fX, lastCurve[1].fY);

527 break;

528 case SkPath::kQuad_Verb:

529 simple.quadTo(lastCurve[1].fX, lastCurve[1].fY,

530 lastCurve[2].fX, lastCurve[2].fY);

531 break;

532 case SkPath::kCubic_Verb:

533 simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY,

534 lastCurve[2].fX, lastCurve[2].fY,

535 lastCurve[3].fX, lastCurve[3].fY);

536 break;

537 }

538 #if DEBUG_ASSEMBLE

539 SkDebugf("%*s %d %sTo last (%g, %g)\n", tab, "",

540 lastIndex + 1, kLVerbStr[lastVerb],

541 lastCurve[lastVerb].fX, lastCurve[lastVerb].fY);

542 #endif

543 if (lastCurve[lastVerb] != firstPt) {

544 simple.lineTo(firstPt.fX, firstPt.fY);

545 #if DEBUG_ASSEMBLE

546 SkDebugf("%*s %d final line (%g, %g)\n", tab, "",

547 firstIndex + 1, firstPt.fX, firstPt.fY);

548 #endif

549 }

550 simple.close();

551 #if DEBUG_ASSEMBLE

552 SkDebugf("%*s close\n", tab, "");

553 #endif

554 break;

555 }

556 // if this and next edge go different directions

557 #if DEBUG_ASSEMBLE

558 SkDebugf("%*s advance=%d edgeIndex=%d flip=%s\n", tab, "",

559 advance, edgeIndex, advance > 0 ^ edgeIndex < 0 ?

560 "true" : "false");

561 #endif

562 if (advance > 0 ^ edgeIndex < 0) {

563 advance = -advance;

564 }

565 } while (edgeIndex);

566 } while (true);

567 }

568

569 // sort points by y, then x

570 // if x/y is identical, sort bottoms before tops

571 // if identical and both tops/bottoms, sort by angle

572 static bool lessThan(SkTArray<OutEdge>& edges, const int one,

573 const int two) {

574 const OutEdge& oneEdge = edges[abs(one) - 1];

575 int oneIndex = one < 0 ? 0 : oneEdge.fVerb;

576 const SkPoint& startPt1 = oneEdge.fPts[oneIndex];

577 const OutEdge& twoEdge = edges[abs(two) - 1];

578 int twoIndex = two < 0 ? 0 : twoEdge.fVerb;

579 const SkPoint& startPt2 = twoEdge.fPts[twoIndex];

580 if (startPt1.fY != startPt2.fY) {

581 #if DEBUG_OUT_LESS_THAN

582 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fY < startPt2.fY\n", __FUNCTI ON__,

583 one, two, startPt1.fY, startPt2.fY,

584 startPt1.fY < startPt2.fY ? "true" : "false");

585 #endif

586 return startPt1.fY < startPt2.fY;

587 }

588 if (startPt1.fX != startPt2.fX) {

589 #if DEBUG_OUT_LESS_THAN

590 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fX < startPt2.fX\n", __FUNCTI ON__,

591 one, two, startPt1.fX, startPt2.fX,

592 startPt1.fX < startPt2.fX ? "true" : "false");

593 #endif

594 return startPt1.fX < startPt2.fX;

595 }

596 const SkPoint& endPt1 = oneEdge.fPts[oneIndex ^ oneEdge.fVerb];

597 const SkPoint& endPt2 = twoEdge.fPts[twoIndex ^ twoEdge.fVerb];

598 SkScalar dy1 = startPt1.fY - endPt1.fY;

599 SkScalar dy2 = startPt2.fY - endPt2.fY;

600 SkScalar dy1y2 = dy1 * dy2;

601 if (dy1y2 < 0) { // different signs

602 #if DEBUG_OUT_LESS_THAN

603 SkDebugf("%s %d<%d %s dy1 > 0\n", __FUNCTION__, one, two,

604 dy1 > 0 ? "true" : "false");

605 #endif

606 return dy1 > 0; // one < two if one goes up and two goes down

607 }

608 if (dy1y2 == 0) {

609 #if DEBUG_OUT_LESS_THAN

610 SkDebugf("%s %d<%d %s endPt1.fX < endPt2.fX\n", __FUNCTION__,

611 one, two, endPt1.fX < endPt2.fX ? "true" : "false");

612 #endif

613 return endPt1.fX < endPt2.fX;

614 }

615 SkScalar dx1y2 = (startPt1.fX - endPt1.fX) * dy2;

616 SkScalar dx2y1 = (startPt2.fX - endPt2.fX) * dy1;

617 #if DEBUG_OUT_LESS_THAN

618 SkDebugf("%s %d<%d %s dy2 < 0 ^ dx1y2 < dx2y1\n", __FUNCTION__,

619 one, two, dy2 < 0 ^ dx1y2 < dx2y1 ? "true" : "false");

620 #endif

621 return dy2 > 0 ^ dx1y2 < dx2y1;

622 }

623

624 // Sort the indices of paired points and then create more indices so

625 // assemble() can find the next edge and connect the top or bottom

626 void bridge() {

627 size_t index;

628 size_t count = fEdges.count();

629 if (!count) {

630 return;

631 }

632 SkASSERT(!fFill \|\| count > 1);

633 fTops.setCount(count);

634 sk_bzero(fTops.begin(), sizeof(fTops[0]) * count);

635 fBottoms.setCount(count);

636 sk_bzero(fBottoms.begin(), sizeof(fBottoms[0]) * count);

637 SkTDArray<int> order;

638 for (index = 1; index <= count; ++index) {

639 *order.append() = -index;

640 }

641 for (index = 1; index <= count; ++index) {

642 *order.append() = index;

643 }

644 QSort<SkTArray<OutEdge>, int>(fEdges, order.begin(), order.end() - 1, le ssThan);

645 int* lastPtr = order.end() - 1;

646 int* leftPtr = order.begin();

647 while (leftPtr < lastPtr) {

648 int leftIndex = *leftPtr;

649 int leftOutIndex = abs(leftIndex) - 1;

650 const OutEdge& left = fEdges[leftOutIndex];

651 int* rightPtr = leftPtr + 1;

652 int rightIndex = *rightPtr;

653 int rightOutIndex = abs(rightIndex) - 1;

654 const OutEdge& right = fEdges[rightOutIndex];

655 bool pairUp = fFill;

656 if (!pairUp) {

657 const SkPoint& leftMatch =

658 left.fPts[leftIndex < 0 ? 0 : left.fVerb];

659 const SkPoint& rightMatch =

660 right.fPts[rightIndex < 0 ? 0 : right.fVerb];

661 pairUp = leftMatch == rightMatch;

662 } else {

663 #if DEBUG_OUT

664 // FIXME : not happy that error in low bit is allowed

665 // this probably conceals error elsewhere

666 if (UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY,

667 right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) > 1) {

668 *fMismatches.append() = leftIndex;

669 if (rightPtr == lastPtr) {

670 *fMismatches.append() = rightIndex;

671 }

672 pairUp = false;

673 }

674 #else

675 SkASSERT(UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY,

676 right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) <= 10);

677 #endif

678 }

679 if (pairUp) {

680 if (leftIndex < 0) {

681 fTops[leftOutIndex] = rightIndex;

682 } else {

683 fBottoms[leftOutIndex] = rightIndex;

684 }

685 if (rightIndex < 0) {

686 fTops[rightOutIndex] = leftIndex;

687 } else {

688 fBottoms[rightOutIndex] = leftIndex;

689 }

690 ++rightPtr;

691 }

692 leftPtr = rightPtr;

693 }

694 #if DEBUG_OUT

695 int* mismatch = fMismatches.begin();

696 while (mismatch != fMismatches.end()) {

697 int leftIndex = *mismatch++;

698 int leftOutIndex = abs(leftIndex) - 1;

699 const OutEdge& left = fEdges[leftOutIndex];

700 const SkPoint& leftPt = left.fPts[leftIndex < 0 ? 0 : left.fVerb];

701 SkDebugf("%s left=%d %s (%1.9g,%1.9g)\n",

702 __FUNCTION__, left.fID, leftIndex < 0 ? "top" : "bot",

703 leftPt.fX, leftPt.fY);

704 }

705 SkASSERT(fMismatches.count() == 0);

706 #endif

707 #if DEBUG_BRIDGE

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

709 const OutEdge& edge = fEdges[index];

710 uint8_t verb = edge.fVerb;

711 SkDebugf("%s %d edge=%d %s (%1.9g,%1.9g) (%1.9g,%1.9g)\n",

712 index == 0 ? __FUNCTION__ : " ",

713 index + 1, edge.fID, kLVerbStr[verb], edge.fPts[0].fX,

714 edge.fPts[0].fY, edge.fPts[verb].fX, edge.fPts[verb].fY);

715 }

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

717 SkDebugf(" top of % 2d connects to %s of % 2d\n", index + 1,

718 fTops[index] < 0 ? "top " : "bottom", abs(fTops[index]));

719 SkDebugf(" bottom of % 2d connects to %s of % 2d\n", index + 1,

720 fBottoms[index] < 0 ? "top " : "bottom", abs(fBottoms[index])) ;

721 }

722 #endif

723 }

724

725 protected:

726 SkTArray<OutEdge> fEdges;

727 SkTDArray<int> fTops;

728 SkTDArray<int> fBottoms;

729 bool fFill;

730 #if DEBUG_OUT

731 SkTDArray<int> fMismatches;

732 #endif

733 };

734

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

736 struct Bounds : public SkRect {

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

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

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

740 }

741

742 bool isEmpty() {

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

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

745 \|\| isnan(fLeft) \|\| isnan(fRight)

746 \|\| isnan(fTop) \|\| isnan(fBottom);

747 }

748 };

749

750 class Intercepts {

751 public:

752 Intercepts()

753 : fTopIntercepts(0)

754 , fBottomIntercepts(0)

755 , fExplicit(false) {

756 }

757

758 Intercepts& operator=(const Intercepts& src) {

759 fTs = src.fTs;

760 fTopIntercepts = src.fTopIntercepts;

761 fBottomIntercepts = src.fBottomIntercepts;

762 return *this;

763 }

764

765 // OPTIMIZATION: remove this function if it's never called

766 double t(int tIndex) const {

767 if (tIndex == 0) {

768 return 0;

769 }

770 if (tIndex > fTs.count()) {

771 return 1;

772 }

773 return fTs[tIndex - 1];

774 }

775

776 #if DEBUG_DUMP

777 void dump(const SkPoint* pts, SkPath::Verb verb) {

778 const char className[] = "Intercepts";

779 const int tab = 8;

780 for (int i = 0; i < fTs.count(); ++i) {

781 SkPoint out;

782 switch (verb) {

783 case SkPath::kLine_Verb:

784 LineXYAtT(pts, fTs[i], &out);

785 break;

786 case SkPath::kQuad_Verb:

787 QuadXYAtT(pts, fTs[i], &out);

788 break;

789 case SkPath::kCubic_Verb:

790 CubicXYAtT(pts, fTs[i], &out);

791 break;

792 default:

793 SkASSERT(0);

794 }

795 SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className ),

796 className, i, fTs[i], out.fX, out.fY);

797 }

798 SkDebugf("%*s.fTopIntercepts=%u\n", tab + sizeof(className),

799 className, fTopIntercepts);

800 SkDebugf("%*s.fBottomIntercepts=%u\n", tab + sizeof(className),

801 className, fBottomIntercepts);

802 SkDebugf("%*s.fExplicit=%d\n", tab + sizeof(className),

803 className, fExplicit);

804 }

805 #endif

806

807 SkTDArray<double> fTs;

808 unsigned char fTopIntercepts; // 0=init state 1=1 edge >1=multiple edges

809 unsigned char fBottomIntercepts;

810 bool fExplicit; // if set, suppress 0 and 1

811

812 };

813

814 struct HorizontalEdge {

815 bool operator<(const HorizontalEdge& rh) const {

816 return fY == rh.fY ? fLeft == rh.fLeft ? fRight < rh.fRight

817 : fLeft < rh.fLeft : fY < rh.fY;

818 }

819

820 #if DEBUG_DUMP

821 void dump() {

822 const char className[] = "HorizontalEdge";

823 const int tab = 4;

824 SkDebugf("%*s.fLeft=%1.9g\n", tab + sizeof(className), className, fLeft) ;

825 SkDebugf("%*s.fRight=%1.9g\n", tab + sizeof(className), className, fRigh t);

826 SkDebugf("%*s.fY=%1.9g\n", tab + sizeof(className), className, fY);

827 }

828 #endif

829

830 SkScalar fLeft;

831 SkScalar fRight;

832 SkScalar fY;

833 };

834

835 struct InEdge {

836 bool operator<(const InEdge& rh) const {

837 return fBounds.fTop == rh.fBounds.fTop

838 ? fBounds.fLeft < rh.fBounds.fLeft

839 : fBounds.fTop < rh.fBounds.fTop;

840 }

841

842 // Avoid collapsing t values that are close to the same since

843 // we walk ts to describe consecutive intersections. Since a pair of ts can

844 // be nearly equal, any problems caused by this should be taken care

845 // of later.

846 int add(double* ts, size_t count, ptrdiff_t verbIndex) {

847 // FIXME: in the pathological case where there is a ton of intercepts, b inary search?

848 bool foundIntercept = false;

849 int insertedAt = -1;

850 Intercepts& intercepts = fIntercepts[verbIndex];

851 for (size_t index = 0; index < count; ++index) {

852 double t = ts[index];

853 if (t <= 0) {

854 intercepts.fTopIntercepts <<= 1;

855 fContainsIntercepts \|= ++intercepts.fTopIntercepts > 1;

856 continue;

857 }

858 if (t >= 1) {

859 intercepts.fBottomIntercepts <<= 1;

860 fContainsIntercepts \|= ++intercepts.fBottomIntercepts > 1;

861 continue;

862 }

863 fIntersected = true;

864 foundIntercept = true;

865 size_t tCount = intercepts.fTs.count();

866 double delta;

867 for (size_t idx2 = 0; idx2 < tCount; ++idx2) {

868 if (t <= intercepts.fTs[idx2]) {

869 // FIXME: ? if (t < intercepts.fTs[idx2]) // failed

870 delta = intercepts.fTs[idx2] - t;

871 if (delta > 0) {

872 insertedAt = idx2;

873 *intercepts.fTs.insert(idx2) = t;

874 }

875 goto nextPt;

876 }

877 }

878 if (tCount == 0 \|\| (delta = t - intercepts.fTs[tCount - 1]) > 0) {

879 insertedAt = tCount;

880 *intercepts.fTs.append() = t;

881 }

882 nextPt:

883 ;

884 }

885 fContainsIntercepts \|= foundIntercept;

886 return insertedAt;

887 }

888

889 void addPartial(SkTArray<InEdge>& edges, int ptStart, int ptEnd,

890 int verbStart, int verbEnd) {

891 InEdge* edge = edges.push_back_n(1);

892 int verbCount = verbEnd - verbStart;

893 edge->fIntercepts.push_back_n(verbCount);

894 // uint8_t* verbs = &fVerbs[verbStart];

895 for (int ceptIdx = 0; ceptIdx < verbCount; ++ceptIdx) {

896 edge->fIntercepts[ceptIdx] = fIntercepts[verbStart + ceptIdx];

897 }

898 edge->fPts.append(ptEnd - ptStart, &fPts[ptStart]);

899 edge->fVerbs.append(verbCount, &fVerbs[verbStart]);

900 edge->setBounds();

901 edge->fWinding = fWinding;

902 edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be co rrect -- but do we need to know?

903 }

904

905 void addSplit(SkTArray<InEdge>& edges, SkPoint* pts, uint8_t verb,

906 Intercepts& intercepts, int firstT, int lastT, bool flipped) {

907 InEdge* edge = edges.push_back_n(1);

908 edge->fIntercepts.push_back_n(1);

909 if (firstT == 0) {

910 *edge->fIntercepts[0].fTs.append() = 0;

911 } else {

912 *edge->fIntercepts[0].fTs.append() = intercepts.fTs[firstT - 1];

913 }

914 bool add1 = lastT == intercepts.fTs.count();

915 edge->fIntercepts[0].fTs.append(lastT - firstT, &intercepts.fTs[firstT]) ;

916 if (add1) {

917 *edge->fIntercepts[0].fTs.append() = 1;

918 }

919 edge->fIntercepts[0].fExplicit = true;

920 edge->fPts.append(verb + 1, pts);

921 edge->fVerbs.append(1, &verb);

922 // FIXME: bounds could be better for partial Ts

923 edge->setSubBounds();

924 edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be co rrect -- but do we need to know?

925 if (flipped) {

926 edge->flipTs();

927 edge->fWinding = -fWinding;

928 } else {

929 edge->fWinding = fWinding;

930 }

931 }

932

933 bool cached(const InEdge* edge) {

934 // FIXME: in the pathological case where there is a ton of edges, binary search?

935 size_t count = fCached.count();

936 for (size_t index = 0; index < count; ++index) {

937 if (edge == fCached[index]) {

938 return true;

939 }

940 if (edge < fCached[index]) {

941 *fCached.insert(index) = edge;

942 return false;

943 }

944 }

945 *fCached.append() = edge;

946 return false;

947 }

948

949 void complete(signed char winding) {

950 setBounds();

951 fIntercepts.push_back_n(fVerbs.count());

952 if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top

953 flip();

954 }

955 fContainsIntercepts = fIntersected = false;

956 }

957

958 void flip() {

959 size_t index;

960 size_t last = fPts.count() - 1;

961 for (index = 0; index < last; ++index, --last) {

962 SkTSwap<SkPoint>(fPts[index], fPts[last]);

963 }

964 last = fVerbs.count() - 1;

965 for (index = 0; index < last; ++index, --last) {

966 SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]);

967 }

968 }

969

970 void flipTs() {

971 SkASSERT(fIntercepts.count() == 1);

972 Intercepts& intercepts = fIntercepts[0];

973 SkASSERT(intercepts.fExplicit);

974 SkTDArray<double>& ts = intercepts.fTs;

975 size_t index;

976 size_t last = ts.count() - 1;

977 for (index = 0; index < last; ++index, --last) {

978 SkTSwap<double>(ts[index], ts[last]);

979 }

980 }

981

982 void reset() {

983 fCached.reset();

984 fIntercepts.reset();

985 fPts.reset();

986 fVerbs.reset();

987 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);

988 fWinding = 0;

989 fContainsIntercepts = false;

990 fIntersected = false;

991 }

992

993 void setBounds() {

994 SkPoint* ptPtr = fPts.begin();

995 SkPoint* ptLast = fPts.end();

996 if (ptPtr == ptLast) {

997 SkDebugf("%s empty edge\n", __FUNCTION__);

998 SkASSERT(0);

999 // FIXME: delete empty edge?

1000 return;

1001 }

1002 fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY);

1003 ++ptPtr;

1004 while (ptPtr != ptLast) {

1005 fBounds.growToInclude(ptPtr->fX, ptPtr->fY);

1006 ++ptPtr;

1007 }

1008 }

1009

1010 // recompute bounds based on subrange of T values

1011 void setSubBounds() {

1012 SkASSERT(fIntercepts.count() == 1);

1013 Intercepts& intercepts = fIntercepts[0];

1014 SkASSERT(intercepts.fExplicit);

1015 SkASSERT(fVerbs.count() == 1);

1016 SkTDArray<double>& ts = intercepts.fTs;

1017 if (fVerbs[0] == SkPath::kQuad_Verb) {

1018 SkASSERT(fPts.count() == 3);

1019 QuadSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds);

1020 } else {

1021 SkASSERT(fVerbs[0] == SkPath::kCubic_Verb);

1022 SkASSERT(fPts.count() == 4);

1023 CubicSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds);

1024 }

1025 }

1026

1027 void splitInflectionPts(SkTArray<InEdge>& edges) {

1028 if (!fIntersected) {

1029 return;

1030 }

1031 uint8_t* verbs = fVerbs.begin();

1032 SkPoint* pts = fPts.begin();

1033 int lastVerb = 0;

1034 int lastPt = 0;

1035 uint8_t verb;

1036 bool edgeSplit = false;

1037 for (int ceptIdx = 0; ceptIdx < fIntercepts.count(); ++ceptIdx, pts += v erb) {

1038 Intercepts& intercepts = fIntercepts[ceptIdx];

1039 verb = *verbs++;

1040 if (verb <= SkPath::kLine_Verb) {

1041 continue;

1042 }

1043 size_t tCount = intercepts.fTs.count();

1044 if (!tCount) {

1045 continue;

1046 }

1047 size_t tIndex = (size_t) -1;

1048 SkScalar y = pts[0].fY;

1049 int lastSplit = 0;

1050 int firstSplit = -1;

1051 bool curveSplit = false;

1052 while (++tIndex < tCount) {

1053 double nextT = intercepts.fTs[tIndex];

1054 SkScalar nextY = verb == SkPath::kQuad_Verb

1055 ? QuadYAtT(pts, nextT) : CubicYAtT(pts, nextT);

1056 if (nextY < y) {

1057 edgeSplit = curveSplit = true;

1058 if (firstSplit < 0) {

1059 firstSplit = tIndex;

1060 int nextPt = pts - fPts.begin();

1061 int nextVerb = verbs - 1 - fVerbs.begin();

1062 if (lastVerb < nextVerb) {

1063 addPartial(edges, lastPt, nextPt, lastVerb, nextVerb );

1064 #if DEBUG_SPLIT

1065 SkDebugf("%s addPartial 1\n", __FUNCTION__);

1066 #endif

1067 }

1068 lastPt = nextPt;

1069 lastVerb = nextVerb;

1070 }

1071 } else {

1072 if (firstSplit >= 0) {

1073 if (lastSplit < firstSplit) {

1074 addSplit(edges, pts, verb, intercepts,

1075 lastSplit, firstSplit, false);

1076 #if DEBUG_SPLIT

1077 SkDebugf("%s addSplit 1 tIndex=%d,%d\n",

1078 __FUNCTION__, lastSplit, firstSplit);

1079 #endif

1080 }

1081 addSplit(edges, pts, verb, intercepts,

1082 firstSplit, tIndex, true);

1083 #if DEBUG_SPLIT

1084 SkDebugf("%s addSplit 2 tIndex=%d,%d flip\n",

1085 __FUNCTION__, firstSplit, tIndex);

1086 #endif

1087 lastSplit = tIndex;

1088 firstSplit = -1;

1089 }

1090 }

1091 y = nextY;

1092 }

1093 if (curveSplit) {

1094 if (firstSplit < 0) {

1095 firstSplit = lastSplit;

1096 } else {

1097 addSplit(edges, pts, verb, intercepts, lastSplit,

1098 firstSplit, false);

1099 #if DEBUG_SPLIT

1100 SkDebugf("%s addSplit 3 tIndex=%d,%d\n", __FUNCTION__,

1101 lastSplit, firstSplit);

1102 #endif

1103 }

1104 addSplit(edges, pts, verb, intercepts, firstSplit,

1105 tIndex, pts[verb].fY < y);

1106 #if DEBUG_SPLIT

1107 SkDebugf("%s addSplit 4 tIndex=%d,%d %s\n", __FUNCTION__,

1108 firstSplit, tIndex, pts[verb].fY < y ? "flip" : "");

1109 #endif

1110 }

1111 }

1112 // collapse remainder -- if there's nothing left, clear it somehow?

1113 if (edgeSplit) {

1114 int nextVerb = verbs - 1 - fVerbs.begin();

1115 if (lastVerb < nextVerb) {

1116 int nextPt = pts - fPts.begin();

1117 addPartial(edges, lastPt, nextPt, lastVerb, nextVerb);

1118 #if DEBUG_SPLIT

1119 SkDebugf("%s addPartial 2\n", __FUNCTION__);

1120 #endif

1121 }

1122 // OPTIMIZATION: reuse the edge instead of marking it empty

1123 reset();

1124 }

1125 }

1126

1127 #if DEBUG_DUMP

1128 void dump() {

1129 int i;

1130 const char className[] = "InEdge";

1131 const int tab = 4;

1132 SkDebugf("InEdge %p (edge=%d)\n", this, fID);

1133 for (i = 0; i < fCached.count(); ++i) {

1134 SkDebugf("%*s.fCached[%d]=0x%08x\n", tab + sizeof(className),

1135 className, i, fCached[i]);

1136 }

1137 uint8_t* verbs = fVerbs.begin();

1138 SkPoint* pts = fPts.begin();

1139 for (i = 0; i < fIntercepts.count(); ++i) {

1140 SkDebugf("%*s.fIntercepts[%d]:\n", tab + sizeof(className),

1141 className, i);

1142 fIntercepts[i].dump(pts, (SkPath::Verb) *verbs);

1143 pts += *verbs++;

1144 }

1145 for (i = 0; i < fPts.count(); ++i) {

1146 SkDebugf("%*s.fPts[%d]=(%1.9g,%1.9g)\n", tab + sizeof(className),

1147 className, i, fPts[i].fX, fPts[i].fY);

1148 }

1149 for (i = 0; i < fVerbs.count(); ++i) {

1150 SkDebugf("%*s.fVerbs[%d]=%d\n", tab + sizeof(className),

1151 className, i, fVerbs[i]);

1152 }

1153 SkDebugf("%*s.fBounds=(%1.9g, %1.9g, %1.9g, %1.9g)\n", tab + sizeof(clas sName),

1154 className, fBounds.fLeft, fBounds.fTop,

1155 fBounds.fRight, fBounds.fBottom);

1156 SkDebugf("%*s.fWinding=%d\n", tab + sizeof(className), className,

1157 fWinding);

1158 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),

1159 className, fContainsIntercepts);

1160 SkDebugf("%*s.fIntersected=%d\n", tab + sizeof(className),

1161 className, fIntersected);

1162 }

1163 #endif

1164

1165 // FIXME: temporary data : move this to a separate struct?

1166 SkTDArray<const InEdge*> fCached; // list of edges already intercepted

1167 SkTArray<Intercepts> fIntercepts; // one per verb

1168

1169 // persistent data

1170 SkTDArray<SkPoint> fPts;

1171 SkTDArray<uint8_t> fVerbs;

1172 Bounds fBounds;

1173 int fID;

1174 signed char fWinding;

1175 bool fContainsIntercepts;

1176 bool fIntersected;

1177 };

1178

1179 class InEdgeBuilder {

1180 public:

1181

1182 InEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges ,

1183 SkTDArray<HorizontalEdge>& horizontalEdges)

1184 : fPath(path)

1185 , fCurrentEdge(NULL)

1186 , fEdges(edges)

1187 , fHorizontalEdges(horizontalEdges)

1188 , fIgnoreHorizontal(ignoreHorizontal)

1189 , fContainsCurves(false)

1190 {

1191 walk();

1192 }

1193

1194 bool containsCurves() const {

1195 return fContainsCurves;

1196 }

1197

1198 protected:

1199

1200 void addEdge() {

1201 SkASSERT(fCurrentEdge);

1202 fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]);

1203 fPtOffset = 1;

1204 *fCurrentEdge->fVerbs.append() = fVerb;

1205 }

1206

1207 bool complete() {

1208 if (fCurrentEdge && fCurrentEdge->fVerbs.count()) {

1209 fCurrentEdge->complete(fWinding);

1210 fCurrentEdge = NULL;

1211 return true;

1212 }

1213 return false;

1214 }

1215

1216 int direction(SkPath::Verb verb) {

1217 fPtCount = verb + 1;

1218 if (fIgnoreHorizontal && isHorizontal()) {

1219 return 0;

1220 }

1221 return fPts[0].fY == fPts[verb].fY

1222 ? fPts[0].fX == fPts[verb].fX ? 0 : fPts[0].fX < fPts[verb].fX

1223 ? 1 : -1 : fPts[0].fY < fPts[verb].fY ? 1 : -1;

1224 }

1225

1226 bool isHorizontal() {

1227 SkScalar y = fPts[0].fY;

1228 for (int i = 1; i < fPtCount; ++i) {

1229 if (fPts[i].fY != y) {

1230 return false;

1231 }

1232 }

1233 return true;

1234 }

1235

1236 void startEdge() {

1237 if (!fCurrentEdge) {

1238 fCurrentEdge = fEdges.push_back_n(1);

1239 }

1240 fWinding = 0;

1241 fPtOffset = 0;

1242 }

1243

1244 void walk() {

1245 SkPath::Iter iter(fPath, true);

1246 int winding = 0;

1247 while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) {

1248 switch (fVerb) {

1249 case SkPath::kMove_Verb:

1250 startEdge();

1251 continue;

1252 case SkPath::kLine_Verb:

1253 winding = direction(SkPath::kLine_Verb);

1254 break;

1255 case SkPath::kQuad_Verb:

1256 fVerb = QuadReduceOrder(fPts);

1257 winding = direction(fVerb);

1258 fContainsCurves \|= fVerb == SkPath::kQuad_Verb;

1259 break;

1260 case SkPath::kCubic_Verb:

1261 fVerb = CubicReduceOrder(fPts);

1262 winding = direction(fVerb);

1263 fContainsCurves \|= fVerb >= SkPath::kQuad_Verb;

1264 break;

1265 case SkPath::kClose_Verb:

1266 SkASSERT(fCurrentEdge);

1267 complete();

1268 continue;

1269 default:

1270 SkDEBUGFAIL("bad verb");

1271 return;

1272 }

1273 if (winding == 0) {

1274 HorizontalEdge* horizontalEdge = fHorizontalEdges.append();

1275 // FIXME: for degenerate quads and cubics, compute x extremes

1276 horizontalEdge->fLeft = fPts[0].fX;

1277 horizontalEdge->fRight = fPts[fVerb].fX;

1278 horizontalEdge->fY = fPts[0].fY;

1279 if (horizontalEdge->fLeft > horizontalEdge->fRight) {

1280 SkTSwap<SkScalar>(horizontalEdge->fLeft, horizontalEdge->fRight) ;

1281 }

1282 if (complete()) {

1283 startEdge();

1284 }

1285 continue;

1286 }

1287 if (fWinding + winding == 0) {

1288 // FIXME: if prior verb or this verb is a horizontal line, reverse

1289 // it instead of starting a new edge

1290 SkASSERT(fCurrentEdge);

1291 if (complete()) {

1292 startEdge();

1293 }

1294 }

1295 fWinding = winding;

1296 addEdge();

1297 }

1298 if (!complete()) {

1299 if (fCurrentEdge) {

1300 fEdges.pop_back();

1301 }

1302 }

1303 }

1304

1305 private:

1306 const SkPath& fPath;

1307 InEdge* fCurrentEdge;

1308 SkTArray<InEdge>& fEdges;

1309 SkTDArray<HorizontalEdge>& fHorizontalEdges;

1310 SkPoint fPts[4];

1311 SkPath::Verb fVerb;

1312 int fPtCount;

1313 int fPtOffset;

1314 int8_t fWinding;

1315 bool fIgnoreHorizontal;

1316 bool fContainsCurves;

1317 };

1318

1319 struct WorkEdge {

1320 SkScalar bottom() const {

1321 return fPts[verb()].fY;

1322 }

1323

1324 void init(const InEdge* edge) {

1325 fEdge = edge;

1326 fPts = edge->fPts.begin();

1327 fVerb = edge->fVerbs.begin();

1328 }

1329

1330 bool advance() {

1331 SkASSERT(fVerb < fEdge->fVerbs.end());

1332 fPts += *fVerb++;

1333 return fVerb != fEdge->fVerbs.end();

1334 }

1335

1336 const SkPoint* lastPoints() const {

1337 SkASSERT(fPts >= fEdge->fPts.begin() + lastVerb());

1338 return &fPts[-lastVerb()];

1339 }

1340

1341 SkPath::Verb lastVerb() const {

1342 SkASSERT(fVerb > fEdge->fVerbs.begin());

1343 return (SkPath::Verb) fVerb[-1];

1344 }

1345

1346 const SkPoint* points() const {

1347 return fPts;

1348 }

1349

1350 SkPath::Verb verb() const {

1351 return (SkPath::Verb) *fVerb;

1352 }

1353

1354 ptrdiff_t verbIndex() const {

1355 return fVerb - fEdge->fVerbs.begin();

1356 }

1357

1358 int winding() const {

1359 return fEdge->fWinding;

1360 }

1361

1362 const InEdge* fEdge;

1363 const SkPoint* fPts;

1364 const uint8_t* fVerb;

1365 };

1366

1367 // always constructed with SkTDArray because new edges are inserted

1368 // this may be a inappropriate optimization, suggesting that a separate array of

1369 // ActiveEdge* may be faster to insert and search

1370

1371 // OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since

1372 // as active edges are introduced, only local sorting should be required

1373 class ActiveEdge {

1374 public:

1375 // this logic must be kept in sync with tooCloseToCall

1376 // callers expect this to only read fAbove, fTangent

1377 bool operator<(const ActiveEdge& rh) const {

1378 if (fVerb == rh.fVerb) {

1379 // FIXME: don't know what to do if verb is quad, cubic

1380 return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow);

1381 }

1382 // figure out which is quad, line

1383 // if cached data says line did not intersect quad, use top/bottom

1384 if (fVerb != SkPath::kLine_Verb ? noIntersect(rh) : rh.noIntersect(*this )) {

1385 return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow);

1386 }

1387 // use whichever of top/tangent tangent/bottom overlaps more

1388 // with line top/bot

1389 // assumes quad/cubic can already be upconverted to cubic/cubic

1390 const SkPoint* line[2];

1391 const SkPoint* curve[4];

1392 if (fVerb != SkPath::kLine_Verb) {

1393 line[0] = &rh.fAbove;

1394 line[1] = &rh.fBelow;

1395 curve[0] = &fAbove;

1396 curve[1] = &fTangent;

1397 curve[2] = &fBelow;

1398 } else {

1399 line[0] = &fAbove;

1400 line[1] = &fBelow;

1401 curve[0] = &rh.fAbove;

1402 curve[1] = &rh.fTangent;

1403 curve[2] = &rh.fBelow;

1404 }

1405 // FIXME: code has been abandoned, incomplete....

1406 return false;

1407 }

1408

1409 bool abCompare(const SkPoint& a1, const SkPoint& a2, const SkPoint& b1,

1410 const SkPoint& b2) const {

1411 double topD = a1.fX - b1.fX;

1412 if (b1.fY < a1.fY) {

1413 topD = (b2.fY - b1.fY) * topD - (a1.fY - b1.fY) * (b2.fX - b1.fX);

1414 } else if (b1.fY > a1.fY) {

1415 topD = (a2.fY - a1.fY) * topD + (b1.fY - a1.fY) * (a2.fX - a1.fX);

1416 }

1417 double botD = a2.fX - b2.fX;

1418 if (b2.fY > a2.fY) {

1419 botD = (b2.fY - b1.fY) * botD - (a2.fY - b2.fY) * (b2.fX - b1.fX);

1420 } else if (b2.fY < a2.fY) {

1421 botD = (a2.fY - a1.fY) * botD + (b2.fY - a2.fY) * (a2.fX - a1.fX);

1422 }

1423 // return sign of greater absolute value

1424 return (fabs(topD) > fabs(botD) ? topD : botD) < 0;

1425 }

1426

1427 // If a pair of edges are nearly coincident for some span, add a T in the

1428 // edge so it can be shortened to match the other edge. Note that another

1429 // approach is to trim the edge after it is added to the OutBuilder list --

1430 // FIXME: since this has no effect if the edge is already done (i.e.,

1431 // fYBottom >= y) maybe this can only be done by calling trimLine later.

1432 void addTatYBelow(SkScalar y) {

1433 if (fBelow.fY <= y \|\| fYBottom >= y) {

1434 return;

1435 }

1436 addTatYInner(y);

1437 fFixBelow = true;

1438 }

1439

1440 void addTatYAbove(SkScalar y) {

1441 if (fBelow.fY <= y) {

1442 return;

1443 }

1444 addTatYInner(y);

1445 }

1446

1447 void addTatYInner(SkScalar y) {

1448 if (fWorkEdge.fPts[0].fY > y) {

1449 backup(y);

1450 }

1451 SkScalar left = fWorkEdge.fPts[0].fX;

1452 SkScalar right = fWorkEdge.fPts[1].fX;

1453 if (left > right) {

1454 SkTSwap(left, right);

1455 }

1456 double ts[2];

1457 SkASSERT(fWorkEdge.fVerb[0] == SkPath::kLine_Verb);

1458 int pts = LineIntersect(fWorkEdge.fPts, left, right, y, ts);

1459 SkASSERT(pts == 1);

1460 // An ActiveEdge or WorkEdge has no need to modify the T values computed

1461 // in the InEdge, except in the following case. If a pair of edges are

1462 // nearly coincident, this may not be detected when the edges are

1463 // intersected. Later, when sorted, and this near-coincidence is found,

1464 // an additional t value must be added, requiring the cast below.

1465 InEdge* writable = const_cast<InEdge*>(fWorkEdge.fEdge);

1466 int insertedAt = writable->add(ts, pts, fWorkEdge.verbIndex());

1467 #if DEBUG_ADJUST_COINCIDENT

1468 SkDebugf("%s edge=%d y=%1.9g t=%1.9g\n", __FUNCTION__, ID(), y, ts[0]);

1469 #endif

1470 if (insertedAt >= 0) {

1471 if (insertedAt + 1 < fTIndex) {

1472 SkASSERT(insertedAt + 2 == fTIndex);

1473 --fTIndex;

1474 }

1475 }

1476 }

1477

1478 bool advanceT() {

1479 SkASSERT(fTIndex <= fTs->count() - fExplicitTs);

1480 return ++fTIndex <= fTs->count() - fExplicitTs;

1481 }

1482

1483 bool advance() {

1484 // FIXME: flip sense of next

1485 bool result = fWorkEdge.advance();

1486 fDone = !result;

1487 initT();

1488 return result;

1489 }

1490

1491 void backup(SkScalar y) {

1492 do {

1493 SkASSERT(fWorkEdge.fEdge->fVerbs.begin() < fWorkEdge.fVerb);

1494 fWorkEdge.fPts -= *--fWorkEdge.fVerb;

1495 SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts);

1496 } while (fWorkEdge.fPts[0].fY >= y);

1497 initT();

1498 SkASSERT(!fExplicitTs);

1499 fTIndex = fTs->count() + 1;

1500 }

1501

1502 void calcAboveBelow(double tAbove, double tBelow) {

1503 fVerb = fWorkEdge.verb();

1504 switch (fVerb) {

1505 case SkPath::kLine_Verb:

1506 LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove);

1507 LineXYAtT(fWorkEdge.fPts, tBelow, &fTangent);

1508 fBelow = fTangent;

1509 break;

1510 case SkPath::kQuad_Verb:

1511 // FIXME: put array in struct to avoid copy?

1512 SkPoint quad[3];

1513 QuadSubDivide(fWorkEdge.fPts, tAbove, tBelow, quad);

1514 fAbove = quad[0];

1515 fTangent = quad[0] != quad[1] ? quad[1] : quad[2];

1516 fBelow = quad[2];

1517 break;

1518 case SkPath::kCubic_Verb:

1519 SkPoint cubic[3];

1520 CubicSubDivide(fWorkEdge.fPts, tAbove, tBelow, cubic);

1521 fAbove = cubic[0];

1522 // FIXME: can't see how quad logic for how tangent is used

1523 // extends to cubic

1524 fTangent = cubic[0] != cubic[1] ? cubic[1]

1525 : cubic[0] != cubic[2] ? cubic[2] : cubic[3];

1526 fBelow = cubic[3];

1527 break;

1528 default:

1529 SkASSERT(0);

1530 }

1531 }

1532

1533 void calcLeft(SkScalar y) {

1534 // OPTIMIZE: put a kDone_Verb at the end of the verb list?

1535 if (fDone \|\| fBelow.fY > y) {

1536 return; // nothing to do; use last

1537 }

1538 calcLeft();

1539 if (fAbove.fY == fBelow.fY) {

1540 SkDebugf("%s edge=%d fAbove.fY != fBelow.fY %1.9g\n", __FUNCTION__,

1541 ID(), fAbove.fY);

1542 }

1543 }

1544

1545 void calcLeft() {

1546 int add = (fTIndex <= fTs->count() - fExplicitTs) - 1;

1547 double tAbove = t(fTIndex + add);

1548 double tBelow = t(fTIndex - ~add);

1549 // OPTIMIZATION: if fAbove, fBelow have already been computed

1550 // for the fTIndex, don't do it again

1551 calcAboveBelow(tAbove, tBelow);

1552 // For identical x, this lets us know which edge is first.

1553 // If both edges have T values < 1, check x at next T (fBelow).

1554 SkASSERT(tAbove != tBelow);

1555 // FIXME: this can loop forever

1556 // need a break if we hit the end

1557 // FIXME: in unit test, figure out how explicit Ts work as well

1558 while (fAbove.fY == fBelow.fY) {

1559 if (add < 0 \|\| fTIndex == fTs->count()) {

1560 add -= 1;

1561 SkASSERT(fTIndex + add >= 0);

1562 tAbove = t(fTIndex + add);

1563 } else {

1564 add += 1;

1565 SkASSERT(fTIndex - ~add <= fTs->count() + 1);

1566 tBelow = t(fTIndex - ~add);

1567 }

1568 calcAboveBelow(tAbove, tBelow);

1569 }

1570 fTAbove = tAbove;

1571 fTBelow = tBelow;

1572 }

1573

1574 bool done(SkScalar bottom) const {

1575 return fDone \|\| fYBottom >= bottom;

1576 }

1577

1578 void fixBelow() {

1579 if (fFixBelow) {

1580 fTBelow = nextT();

1581 calcAboveBelow(fTAbove, fTBelow);

1582 fFixBelow = false;

1583 }

1584 }

1585

1586 void init(const InEdge* edge) {

1587 fWorkEdge.init(edge);

1588 fDone = false;

1589 initT();

1590 fBelow.fY = SK_ScalarMin;

1591 fYBottom = SK_ScalarMin;

1592 }

1593

1594 void initT() {

1595 const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front();

1596 SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count());

1597 const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex();

1598 fTs = &interceptPtr->fTs;

1599 fExplicitTs = interceptPtr->fExplicit;

1600 // the above is conceptually the same as

1601 // fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs;

1602 // but templated arrays don't allow returning a pointer to the end() element

1603 fTIndex = 0;

1604 if (!fDone) {

1605 fVerb = fWorkEdge.verb();

1606 }

1607 SkASSERT(fVerb > SkPath::kMove_Verb);

1608 }

1609

1610 // OPTIMIZATION: record if two edges are coincident when the are intersected

1611 // It's unclear how to do this -- seems more complicated than recording the

1612 // t values, since the same t values could exist intersecting non-coincident

1613 // edges.

1614 bool isCoincidentWith(const ActiveEdge* edge) const {

1615 if (fAbove != edge->fAbove \|\| fBelow != edge->fBelow) {

1616 return false;

1617 }

1618 if (fVerb != edge->fVerb) {

1619 return false;

1620 }

1621 switch (fVerb) {

1622 case SkPath::kLine_Verb:

1623 return true;

1624 default:

1625 // FIXME: add support for quads, cubics

1626 SkASSERT(0);

1627 return false;

1628 }

1629 return false;

1630 }

1631

1632 bool isUnordered(const ActiveEdge* edge) const {

1633 return fAbove == edge->fAbove && fBelow == edge->fBelow;

1634 }

1635

1636 // SkPath::Verb lastVerb() const {

1637 // return fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb();

1638 // }

1639

1640 const SkPoint* lastPoints() const {

1641 return fDone ? fWorkEdge.lastPoints() : fWorkEdge.points();

1642 }

1643

1644 bool noIntersect(const ActiveEdge& ) const {

1645 // incomplete

1646 return false;

1647 }

1648

1649 // The shortest close call edge should be moved into a position where

1650 // it contributes if the winding is transitioning to or from zero.

1651 bool swapClose(const ActiveEdge* next, int prev, int wind, int mask) const {

1652 #if DEBUG_ADJUST_COINCIDENT

1653 SkDebugf("%s edge=%d (%g) next=%d (%g) prev=%d wind=%d nextWind=%d\n",

1654 __FUNCTION__, ID(), fBelow.fY, next->ID(), next->fBelow.fY,

1655 prev, wind, wind + next->fWorkEdge.winding());

1656 #endif

1657 if ((prev & mask) == 0 \|\| (wind & mask) == 0) {

1658 return next->fBelow.fY < fBelow.fY;

1659 }

1660 int nextWinding = wind + next->fWorkEdge.winding();

1661 if ((nextWinding & mask) == 0) {

1662 return fBelow.fY < next->fBelow.fY;

1663 }

1664 return false;

1665 }

1666

1667 bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const {

1668 if (fBelow.fY >= bottom \|\| fDone \|\| edge->fDone) {

1669 return false;

1670 }

1671 ActiveEdge thisWork = *this;

1672 ActiveEdge edgeWork = *edge;

1673 while ((thisWork.advanceT() \|\| thisWork.advance())

1674 && (edgeWork.advanceT() \|\| edgeWork.advance())) {

1675 thisWork.calcLeft();

1676 edgeWork.calcLeft();

1677 if (thisWork < edgeWork) {

1678 return false;

1679 }

1680 if (edgeWork < thisWork) {

1681 return true;

1682 }

1683 }

1684 return false;

1685 }

1686

1687 bool swapUnordered(const ActiveEdge* edge, SkScalar /* bottom */) const {

1688 SkASSERT(fVerb != SkPath::kLine_Verb

1689 \|\| edge->fVerb != SkPath::kLine_Verb);

1690 if (fDone \|\| edge->fDone) {

1691 return false;

1692 }

1693 ActiveEdge thisWork, edgeWork;

1694 extractAboveBelow(thisWork);

1695 edge->extractAboveBelow(edgeWork);

1696 return edgeWork < thisWork;

1697 }

1698

1699 bool tooCloseToCall(const ActiveEdge* edge) const {

1700 int ulps;

1701 double t1, t2, b1, b2;

1702 // This logic must be kept in sync with operator <

1703 if (edge->fAbove.fY < fAbove.fY) {

1704 t1 = (edge->fTangent.fY - edge->fAbove.fY) * (fAbove.fX - edge->fAbo ve.fX);

1705 t2 = (fAbove.fY - edge->fAbove.fY) * (edge->fTangent.fX - edge->fAbo ve.fX);

1706 } else if (edge->fAbove.fY > fAbove.fY) {

1707 t1 = (fTangent.fY - fAbove.fY) * (fAbove.fX - edge->fAbove.fX);

1708 t2 = (fAbove.fY - edge->fAbove.fY) * (fTangent.fX - fAbove.fX);

1709 } else {

1710 t1 = fAbove.fX;

1711 t2 = edge->fAbove.fX;

1712 }

1713 if (edge->fTangent.fY > fTangent.fY) {

1714 b1 = (edge->fTangent.fY - edge->fAbove.fY) * (fTangent.fX - edge->fT angent.fX);

1715 b2 = (fTangent.fY - edge->fTangent.fY) * (edge->fTangent.fX - edge-> fAbove.fX);

1716 } else if (edge->fTangent.fY < fTangent.fY) {

1717 b1 = (fTangent.fY - fAbove.fY) * (fTangent.fX - edge->fTangent.fX);

1718 b2 = (fTangent.fY - edge->fTangent.fY) * (fTangent.fX - fAbove.fX);

1719 } else {

1720 b1 = fTangent.fX;

1721 b2 = edge->fTangent.fX;

1722 }

1723 if (fabs(t1 - t2) > fabs(b1 - b2)) {

1724 ulps = UlpsDiff((float) t1, (float) t2);

1725 } else {

1726 ulps = UlpsDiff((float) b1, (float) b2);

1727 }

1728 #if DEBUG_ADJUST_COINCIDENT

1729 SkDebugf("%s this=%d edge=%d ulps=%d\n", __FUNCTION__, ID(), edge->ID(),

1730 ulps);

1731 #endif

1732 if (ulps < 0 \|\| ulps > 32) {

1733 return false;

1734 }

1735 if (fVerb == SkPath::kLine_Verb && edge->fVerb == SkPath::kLine_Verb) {

1736 return true;

1737 }

1738 if (fVerb != SkPath::kLine_Verb && edge->fVerb != SkPath::kLine_Verb) {

1739 return false;

1740 }

1741

1742 double ts[2];

1743 bool isLine = true;

1744 bool curveQuad = true;

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

1746 ts[0] = (fTAbove * 2 + fTBelow) / 3;

1747 ts[1] = (fTAbove + fTBelow * 2) / 3;

1748 curveQuad = isLine = false;

1749 } else if (edge->fVerb == SkPath::kCubic_Verb) {

1750 ts[0] = (edge->fTAbove * 2 + edge->fTBelow) / 3;

1751 ts[1] = (edge->fTAbove + edge->fTBelow * 2) / 3;

1752 curveQuad = false;

1753 } else if (fVerb == SkPath::kQuad_Verb) {

1754 ts[0] = fTAbove;

1755 ts[1] = (fTAbove + fTBelow) / 2;

1756 isLine = false;

1757 } else {

1758 SkASSERT(edge->fVerb == SkPath::kQuad_Verb);

1759 ts[0] = edge->fTAbove;

1760 ts[1] = (edge->fTAbove + edge->fTBelow) / 2;

1761 }

1762 const SkPoint* curvePts = isLine ? edge->lastPoints() : lastPoints();

1763 const ActiveEdge* lineEdge = isLine ? this : edge;

1764 SkPoint curveSample[2];

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

1766 if (curveQuad) {

1767 QuadXYAtT(curvePts, ts[index], &curveSample[index]);

1768 } else {

1769 CubicXYAtT(curvePts, ts[index], &curveSample[index]);

1770 }

1771 }

1772 return IsCoincident(curveSample, lineEdge->fAbove, lineEdge->fBelow);

1773 }

1774

1775 double nextT() const {

1776 SkASSERT(fTIndex <= fTs->count() - fExplicitTs);

1777 return t(fTIndex + 1);

1778 }

1779

1780 double t() const {

1781 return t(fTIndex);

1782 }

1783

1784 double t(int tIndex) const {

1785 if (fExplicitTs) {

1786 SkASSERT(tIndex < fTs->count());

1787 return (*fTs)[tIndex];

1788 }

1789 if (tIndex == 0) {

1790 return 0;

1791 }

1792 if (tIndex > fTs->count()) {

1793 return 1;

1794 }

1795 return (*fTs)[tIndex - 1];

1796 }

1797

1798 // FIXME: debugging only

1799 int ID() const {

1800 return fWorkEdge.fEdge->fID;

1801 }

1802

1803 private:

1804 // utility used only by swapUnordered

1805 void extractAboveBelow(ActiveEdge& extracted) const {

1806 SkPoint curve[4];

1807 switch (fVerb) {

1808 case SkPath::kLine_Verb:

1809 extracted.fAbove = fAbove;

1810 extracted.fTangent = fTangent;

1811 return;

1812 case SkPath::kQuad_Verb:

1813 QuadSubDivide(lastPoints(), fTAbove, fTBelow, curve);

1814 break;

1815 case SkPath::kCubic_Verb:

1816 CubicSubDivide(lastPoints(), fTAbove, fTBelow, curve);

1817 break;

1818 default:

1819 SkASSERT(0);

1820 }

1821 extracted.fAbove = curve[0];

1822 extracted.fTangent = curve[1];

1823 }

1824

1825 public:

1826 WorkEdge fWorkEdge;

1827 const SkTDArray<double>* fTs;

1828 SkPoint fAbove;

1829 SkPoint fTangent;

1830 SkPoint fBelow;

1831 double fTAbove; // OPTIMIZATION: only required if edge has quads or cubics

1832 double fTBelow;

1833 SkScalar fYBottom;

1834 int fCoincident;

1835 int fTIndex;

1836 SkPath::Verb fVerb;

1837 bool fSkip; // OPTIMIZATION: use bitfields?

1838 bool fCloseCall;

1839 bool fDone;

1840 bool fFixBelow;

1841 bool fExplicitTs;

1842 };

1843

1844 static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) {

1845 size_t count = activeEdges.count();

1846 for (size_t index = 0; index < count; ++index) {

1847 if (edge == activeEdges[index].fWorkEdge.fEdge) {

1848 return;

1849 }

1850 }

1851 ActiveEdge* active = activeEdges.append();

1852 active->init(edge);

1853 }

1854

1855 // Find any intersections in the range of active edges. A pair of edges, on

1856 // either side of another edge, may change the winding contribution for part of

1857 // the edge.

1858 // Keep horizontal edges just for

1859 // the purpose of computing when edges change their winding contribution, since

1860 // this is essentially computing the horizontal intersection.

1861 static void addBottomT(InEdge currentPtr, InEdge lastPtr,

1862 HorizontalEdge** horizontal) {

1863 InEdge** testPtr = currentPtr - 1;

1864 HorizontalEdge* horzEdge = *horizontal;

1865 SkScalar left = horzEdge->fLeft;

1866 SkScalar bottom = horzEdge->fY;

1867 while (++testPtr != lastPtr) {

1868 InEdge* test = *testPtr;

1869 if (test->fBounds.fBottom <= bottom \|\| test->fBounds.fRight <= left) {

1870 continue;

1871 }

1872 WorkEdge wt;

1873 wt.init(test);

1874 do {

1875 HorizontalEdge** sorted = horizontal;

1876 horzEdge = *sorted;

1877 do {

1878 double wtTs[4];

1879 int pts;

1880 uint8_t verb = wt.verb();

1881 switch (verb) {

1882 case SkPath::kLine_Verb:

1883 pts = LineIntersect(wt.fPts, horzEdge->fLeft,

1884 horzEdge->fRight, horzEdge->fY, wtTs);

1885 break;

1886 case SkPath::kQuad_Verb:

1887 pts = QuadIntersect(wt.fPts, horzEdge->fLeft,

1888 horzEdge->fRight, horzEdge->fY, wtTs);

1889 break;

1890 case SkPath::kCubic_Verb:

1891 pts = CubicIntersect(wt.fPts, horzEdge->fLeft,

1892 horzEdge->fRight, horzEdge->fY, wtTs);

1893 break;

1894 }

1895 if (pts) {

1896 #if DEBUG_ADD_BOTTOM_TS

1897 for (int x = 0; x < pts; ++x) {

1898 SkDebugf("%s y=%g wtTs[0]=%g (%g,%g", __FUNCTION__,

1899 horzEdge->fY, wtTs[x], wt.fPts[0].fX, wt.fPts[0] .fY);

1900 for (int y = 0; y < verb; ++y) {

1901 SkDebugf(" %g,%g", wt.fPts[y + 1].fX, wt.fPts[y + 1] .fY));

1902 }

1903 SkDebugf(")\n");

1904 }

1905 if (pts > verb) {

1906 SkASSERT(0); // FIXME ? should this work?

1907 SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);

1908 }

1909 #endif

1910 test->add(wtTs, pts, wt.verbIndex());

1911 }

1912 horzEdge = *++sorted;

1913 } while (horzEdge->fY == bottom

1914 && horzEdge->fLeft <= test->fBounds.fRight);

1915 } while (wt.advance());

1916 }

1917 }

1918

1919 #if DEBUG_ADD_INTERSECTING_TS

1920 static void debugShowLineIntersection(int pts, const WorkEdge& wt,

1921 const WorkEdge& wn, const double wtTs[2], const double wnTs[2]) {

1922 if (!pts) {

1923 return;

1924 }

1925 SkPoint wtOutPt, wnOutPt;

1926 LineXYAtT(wt.fPts, wtTs[0], &wtOutPt);

1927 LineXYAtT(wn.fPts, wnTs[0], &wnOutPt);

1928 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",

1929 __FUNCTION__,

1930 wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY,

1931 wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY);

1932 if (pts == 2) {

1933 SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);

1934 }

1935 SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",

1936 __FUNCTION__,

1937 wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY,

1938 wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY);

1939 if (pts == 2) {

1940 SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]);

1941 }

1942 }

1943 #else

1944 static void debugShowLineIntersection(int , const WorkEdge& ,

1945 const WorkEdge& , const double [2], const double [2]) {

1946 }

1947 #endif

1948

1949 static void addIntersectingTs(InEdge currentPtr, InEdge lastPtr) {

1950 InEdge** testPtr = currentPtr - 1;

1951 // FIXME: lastPtr should be past the point of interest, so

1952 // test below should be lastPtr - 2

1953 // that breaks testSimplifyTriangle22, so further investigation is needed

1954 while (++testPtr != lastPtr - 1) {

1955 InEdge* test = *testPtr;

1956 InEdge** nextPtr = testPtr;

1957 do {

1958 InEdge* next = *++nextPtr;

1959 // FIXME: this compares against the sentinel sometimes

1960 // OPTIMIZATION: this may never be needed since this gets called

1961 // in two passes now. Verify that double hits are appropriate.

1962 if (test->cached(next)) {

1963 continue;

1964 }

1965 if (!Bounds::Intersects(test->fBounds, next->fBounds)) {

1966 continue;

1967 }

1968 WorkEdge wt, wn;

1969 wt.init(test);

1970 wn.init(next);

1971 do {

1972 int pts;

1973 Intersections ts;

1974 bool swap = false;

1975 switch (wt.verb()) {

1976 case SkPath::kLine_Verb:

1977 switch (wn.verb()) {

1978 case SkPath::kLine_Verb: {

1979 pts = LineIntersect(wt.fPts, wn.fPts, ts);

1980 debugShowLineIntersection(pts, wt, wn,

1981 ts.fT[0], ts.fT[1]);

1982 break;

1983 }

1984 case SkPath::kQuad_Verb: {

1985 swap = true;

1986 pts = QuadLineIntersect(wn.fPts, wt.fPts, ts);

1987 break;

1988 }

1989 case SkPath::kCubic_Verb: {

1990 swap = true;

1991 pts = CubicLineIntersect(wn.fPts, wt.fPts, ts);

1992 break;

1993 }

1994 default:

1995 SkASSERT(0);

1996 }

1997 break;

1998 case SkPath::kQuad_Verb:

1999 switch (wn.verb()) {

2000 case SkPath::kLine_Verb: {

2001 pts = QuadLineIntersect(wt.fPts, wn.fPts, ts);

2002 break;

2003 }

2004 case SkPath::kQuad_Verb: {

2005 pts = QuadIntersect(wt.fPts, wn.fPts, ts);

2006 break;

2007 }

2008 case SkPath::kCubic_Verb: {

2009 // FIXME: promote quad to cubic

2010 pts = CubicIntersect(wt.fPts, wn.fPts, ts);

2011 break;

2012 }

2013 default:

2014 SkASSERT(0);

2015 }

2016 break;

2017 case SkPath::kCubic_Verb:

2018 switch (wn.verb()) {

2019 case SkPath::kLine_Verb: {

2020 pts = CubicLineIntersect(wt.fPts, wn.fPts, ts);

2021 break;

2022 }

2023 case SkPath::kQuad_Verb: {

2024 // FIXME: promote quad to cubic

2025 pts = CubicIntersect(wt.fPts, wn.fPts, ts);

2026 break;

2027 }

2028 case SkPath::kCubic_Verb: {

2029 pts = CubicIntersect(wt.fPts, wn.fPts, ts);

2030 break;

2031 }

2032 default:

2033 SkASSERT(0);

2034 }

2035 break;

2036 default:

2037 SkASSERT(0);

2038 }

2039 test->add(ts.fT[swap], pts, wt.verbIndex());

2040 next->add(ts.fT[!swap], pts, wn.verbIndex());

2041 } while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance());

2042 } while (nextPtr != lastPtr);

2043 }

2044 }

2045

2046 static InEdge** advanceEdges(SkTDArray<ActiveEdge>* activeEdges,

2047 InEdge currentPtr, InEdge lastPtr, SkScalar y) {

2048 InEdge** testPtr = currentPtr - 1;

2049 while (++testPtr != lastPtr) {

2050 if ((*testPtr)->fBounds.fBottom > y) {

2051 continue;

2052 }

2053 if (activeEdges) {

2054 InEdge* test = *testPtr;

2055 ActiveEdge* activePtr = activeEdges->begin() - 1;

2056 ActiveEdge* lastActive = activeEdges->end();

2057 while (++activePtr != lastActive) {

2058 if (activePtr->fWorkEdge.fEdge == test) {

2059 activeEdges->remove(activePtr - activeEdges->begin());

2060 break;

2061 }

2062 }

2063 }

2064 if (testPtr == currentPtr) {

2065 ++currentPtr;

2066 }

2067 }

2068 return currentPtr;

2069 }

2070

2071 // OPTIMIZE: inline?

2072 static HorizontalEdge advanceHorizontal(HorizontalEdge edge, SkScalar y) {

2073 while ((*edge)->fY < y) {

2074 ++edge;

2075 }

2076 return edge;

2077 }

2078

2079 // compute bottom taking into account any intersected edges

2080 static SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges,

2081 SkScalar y, SkScalar bottom) {

2082 ActiveEdge* activePtr = activeEdges.begin() - 1;

2083 ActiveEdge* lastActive = activeEdges.end();

2084 while (++activePtr != lastActive) {

2085 const InEdge* test = activePtr->fWorkEdge.fEdge;

2086 if (!test->fContainsIntercepts) {

2087 continue;

2088 }

2089 WorkEdge wt;

2090 wt.init(test);

2091 do {

2092 const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()];

2093 if (intercepts.fTopIntercepts > 1) {

2094 SkScalar yTop = wt.fPts[0].fY;

2095 if (yTop > y && bottom > yTop) {

2096 bottom = yTop;

2097 }

2098 }

2099 if (intercepts.fBottomIntercepts > 1) {

2100 SkScalar yBottom = wt.fPts[wt.verb()].fY;

2101 if (yBottom > y && bottom > yBottom) {

2102 bottom = yBottom;

2103 }

2104 }

2105 const SkTDArray<double>& fTs = intercepts.fTs;

2106 size_t count = fTs.count();

2107 for (size_t index = 0; index < count; ++index) {

2108 SkScalar yIntercept;

2109 switch (wt.verb()) {

2110 case SkPath::kLine_Verb: {

2111 yIntercept = LineYAtT(wt.fPts, fTs[index]);

2112 break;

2113 }

2114 case SkPath::kQuad_Verb: {

2115 yIntercept = QuadYAtT(wt.fPts, fTs[index]);

2116 break;

2117 }

2118 case SkPath::kCubic_Verb: {

2119 yIntercept = CubicYAtT(wt.fPts, fTs[index]);

2120 break;

2121 }

2122 default:

2123 SkASSERT(0); // should never get here

2124 }

2125 if (yIntercept > y && bottom > yIntercept) {

2126 bottom = yIntercept;

2127 }

2128 }

2129 } while (wt.advance());

2130 }

2131 #if DEBUG_BOTTOM

2132 SkDebugf("%s bottom=%1.9g\n", __FUNCTION__, bottom);

2133 #endif

2134 return bottom;

2135 }

2136

2137 static SkScalar findBottom(InEdge** currentPtr,

2138 InEdge** edgeListEnd, SkTDArray<ActiveEdge>* activeEdges, SkScalar y,

2139 bool /asFill/, InEdge**& testPtr) {

2140 InEdge* current = *currentPtr;

2141 SkScalar bottom = current->fBounds.fBottom;

2142

2143 // find the list of edges that cross y

2144 InEdge* test = *testPtr;

2145 while (testPtr != edgeListEnd) {

2146 SkScalar testTop = test->fBounds.fTop;

2147 if (bottom <= testTop) {

2148 break;

2149 }

2150 SkScalar testBottom = test->fBounds.fBottom;

2151 // OPTIMIZATION: Shortening the bottom is only interesting when filling

2152 // and when the edge is to the left of a longer edge. If it's a framing

2153 // edge, or part of the right, it won't effect the longer edges.

2154 if (testTop > y) {

2155 bottom = testTop;

2156 break;

2157 }

2158 if (y < testBottom) {

2159 if (bottom > testBottom) {

2160 bottom = testBottom;

2161 }

2162 if (activeEdges) {

2163 addToActive(*activeEdges, test);

2164 }

2165 }

2166 test = *++testPtr;

2167 }

2168 #if DEBUG_BOTTOM

2169 SkDebugf("%s %d bottom=%1.9g\n", __FUNCTION__, activeEdges ? 2 : 1, bottom);

2170 #endif

2171 return bottom;

2172 }

2173

2174 static void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel,

2175 SkTDArray<InEdge*>& edgeList) {

2176 size_t edgeCount = edges.count();

2177 if (edgeCount == 0) {

2178 return;

2179 }

2180 int id = 0;

2181 for (size_t index = 0; index < edgeCount; ++index) {

2182 InEdge& edge = edges[index];

2183 if (!edge.fWinding) {

2184 continue;

2185 }

2186 edge.fID = ++id;

2187 *edgeList.append() = &edge;

2188 }

2189 *edgeList.append() = &edgeSentinel;

2190 QSort<InEdge>(edgeList.begin(), edgeList.end() - 1);

2191 }

2192

2193 static void makeHorizontalList(SkTDArray<HorizontalEdge>& edges,

2194 HorizontalEdge& edgeSentinel, SkTDArray<HorizontalEdge*>& edgeList) {

2195 size_t edgeCount = edges.count();

2196 if (edgeCount == 0) {

2197 return;

2198 }

2199 for (size_t index = 0; index < edgeCount; ++index) {

2200 *edgeList.append() = &edges[index];

2201 }

2202 edgeSentinel.fLeft = edgeSentinel.fRight = edgeSentinel.fY = SK_ScalarMax;

2203 *edgeList.append() = &edgeSentinel;

2204 QSort<HorizontalEdge>(edgeList.begin(), edgeList.end() - 1);

2205 }

2206

2207 static void skipCoincidence(int lastWinding, int winding, int windingMask,

2208 ActiveEdge* activePtr, ActiveEdge* firstCoincident) {

2209 if (((lastWinding & windingMask) == 0) ^ ((winding & windingMask) != 0)) {

2210 return;

2211 }

2212 // FIXME: ? shouldn't this be if (lastWinding & windingMask) ?

2213 if (lastWinding) {

2214 #if DEBUG_ADJUST_COINCIDENT

2215 SkDebugf("%s edge=%d 1 set skip=false\n", __FUNCTION__, activePtr->ID()) ;

2216 #endif

2217 activePtr->fSkip = false;

2218 } else {

2219 #if DEBUG_ADJUST_COINCIDENT

2220 SkDebugf("%s edge=%d 2 set skip=false\n", __FUNCTION__, firstCoincident- >ID());

2221 #endif

2222 firstCoincident->fSkip = false;

2223 }

2224 }

2225

2226 static void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges,

2227 SkTDArray<ActiveEdge*>& edgeList, SkScalar y) {

2228 size_t edgeCount = activeEdges.count();

2229 if (edgeCount == 0) {

2230 return;

2231 }

2232 #if DEBUG_SORT_HORIZONTAL

2233 const int tab = 3; // FIXME: debugging only

2234 SkDebugf("%s y=%1.9g\n", __FUNCTION__, y);

2235 #endif

2236 size_t index;

2237 for (index = 0; index < edgeCount; ++index) {

2238 ActiveEdge& activeEdge = activeEdges[index];

2239 do {

2240 activeEdge.calcLeft(y);

2241 // skip segments that don't span y

2242 if (activeEdge.fAbove != activeEdge.fBelow) {

2243 break;

2244 }

2245 if (activeEdge.fDone) {

2246 #if DEBUG_SORT_HORIZONTAL

2247 SkDebugf("%*s edge=%d done\n", tab, "", activeEdge.ID());

2248 #endif

2249 goto nextEdge;

2250 }

2251 #if DEBUG_SORT_HORIZONTAL

2252 SkDebugf("%*s edge=%d above==below\n", tab, "", activeEdge.ID());

2253 #endif

2254 } while (activeEdge.advanceT() \|\| activeEdge.advance());

2255 #if DEBUG_SORT_HORIZONTAL

2256 SkDebugf("%*s edge=%d above=(%1.9g,%1.9g) (%1.9g) below=(%1.9g,%1.9g)"

2257 " (%1.9g)\n", tab, "", activeEdge.ID(),

2258 activeEdge.fAbove.fX, activeEdge.fAbove.fY, activeEdge.fTAbove,

2259 activeEdge.fBelow.fX, activeEdge.fBelow.fY, activeEdge.fTBelow);

2260 #endif

2261 activeEdge.fSkip = activeEdge.fCloseCall = activeEdge.fFixBelow = false;

2262 *edgeList.append() = &activeEdge;

2263 nextEdge:

2264 ;

2265 }

2266 QSort<ActiveEdge>(edgeList.begin(), edgeList.end() - 1);

2267 }

2268

2269 // remove coincident edges

2270 // OPTIMIZE: remove edges? This is tricky because the current logic expects

2271 // the winding count to be maintained while skipping coincident edges. In

2272 // addition to removing the coincident edges, the remaining edges would need

2273 // to have a different winding value, possibly different per intercept span.

2274 static SkScalar adjustCoincident(SkTDArray<ActiveEdge*>& edgeList,

2275 int windingMask, SkScalar y, SkScalar bottom, OutEdgeBuilder& outBuilder )

2276 {

2277 #if DEBUG_ADJUST_COINCIDENT

2278 SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom);

2279 #endif

2280 size_t edgeCount = edgeList.count();

2281 if (edgeCount == 0) {

2282 return bottom;

2283 }

2284 ActiveEdge* activePtr, * nextPtr = edgeList[0];

2285 size_t index;

2286 bool foundCoincident = false;

2287 size_t firstIndex = 0;

2288 for (index = 1; index < edgeCount; ++index) {

2289 activePtr = nextPtr;

2290 nextPtr = edgeList[index];

2291 if (firstIndex != index - 1 && activePtr->fVerb > SkPath::kLine_Verb

2292 && nextPtr->fVerb == SkPath::kLine_Verb

2293 && activePtr->isUnordered(nextPtr)) {

2294 // swap the line with the curve

2295 // back up to the previous edge and retest

2296 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]);

2297 SkASSERT(index > 1);

2298 index -= 2;

2299 nextPtr = edgeList[index];

2300 continue;

2301 }

2302 bool closeCall = false;

2303 activePtr->fCoincident = firstIndex;

2304 if (activePtr->isCoincidentWith(nextPtr)

2305 \|\| (closeCall = activePtr->tooCloseToCall(nextPtr))) {

2306 activePtr->fSkip = nextPtr->fSkip = foundCoincident = true;

2307 activePtr->fCloseCall = nextPtr->fCloseCall = closeCall;

2308 } else if (activePtr->isUnordered(nextPtr)) {

2309 foundCoincident = true;

2310 } else {

2311 firstIndex = index;

2312 }

2313 }

2314 nextPtr->fCoincident = firstIndex;

2315 if (!foundCoincident) {

2316 return bottom;

2317 }

2318 int winding = 0;

2319 nextPtr = edgeList[0];

2320 for (index = 1; index < edgeCount; ++index) {

2321 int priorWinding = winding;

2322 winding += activePtr->fWorkEdge.winding();

2323 activePtr = nextPtr;

2324 nextPtr = edgeList[index];

2325 SkASSERT(activePtr == edgeList[index - 1]);

2326 SkASSERT(nextPtr == edgeList[index]);

2327 if (activePtr->fCoincident != nextPtr->fCoincident) {

2328 continue;

2329 }

2330 // the coincident edges may not have been sorted above -- advance

2331 // the edges and resort if needed

2332 // OPTIMIZE: if sorting is done incrementally as new edges are added

2333 // and not all at once as is done here, fold this test into the

2334 // current less than test.

2335 while ((!activePtr->fSkip \|\| !nextPtr->fSkip)

2336 && activePtr->fCoincident == nextPtr->fCoincident) {

2337 if (activePtr->swapUnordered(nextPtr, bottom)) {

2338 winding -= activePtr->fWorkEdge.winding();

2339 SkASSERT(activePtr == edgeList[index - 1]);

2340 SkASSERT(nextPtr == edgeList[index]);

2341 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]);

2342 if (--index == 0) {

2343 winding += activePtr->fWorkEdge.winding();

2344 break;

2345 }

2346 // back up one

2347 activePtr = edgeList[index - 1];

2348 continue;

2349 }

2350 SkASSERT(activePtr == edgeList[index - 1]);

2351 SkASSERT(nextPtr == edgeList[index]);

2352 break;

2353 }

2354 if (activePtr->fSkip && nextPtr->fSkip) {

2355 if (activePtr->fCloseCall ? activePtr->swapClose(nextPtr,

2356 priorWinding, winding, windingMask)

2357 : activePtr->swapCoincident(nextPtr, bottom)) {

2358 winding -= activePtr->fWorkEdge.winding();

2359 SkASSERT(activePtr == edgeList[index - 1]);

2360 SkASSERT(nextPtr == edgeList[index]);

2361 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]);

2362 SkTSwap<ActiveEdge*>(activePtr, nextPtr);

2363 winding += activePtr->fWorkEdge.winding();

2364 SkASSERT(activePtr == edgeList[index - 1]);

2365 SkASSERT(nextPtr == edgeList[index]);

2366 }

2367 }

2368 }

2369 int firstCoincidentWinding = 0;

2370 ActiveEdge* firstCoincident = NULL;

2371 winding = 0;

2372 activePtr = edgeList[0];

2373 for (index = 1; index < edgeCount; ++index) {

2374 int priorWinding = winding;

2375 winding += activePtr->fWorkEdge.winding();

2376 nextPtr = edgeList[index];

2377 if (activePtr->fSkip && nextPtr->fSkip

2378 && activePtr->fCoincident == nextPtr->fCoincident) {

2379 if (!firstCoincident) {

2380 firstCoincident = activePtr;

2381 firstCoincidentWinding = priorWinding;

2382 }

2383 if (activePtr->fCloseCall) {

2384 // If one of the edges has already been added to out as a non

2385 // coincident edge, trim it back to the top of this span

2386 if (outBuilder.trimLine(y, activePtr->ID())) {

2387 activePtr->addTatYAbove(y);

2388 #if DEBUG_ADJUST_COINCIDENT

2389 SkDebugf("%s 1 edge=%d y=%1.9g (was fYBottom=%1.9g)\n",

2390 __FUNCTION__, activePtr->ID(), y, activePtr->fYBotto m);

2391 #endif

2392 activePtr->fYBottom = y;

2393 }

2394 if (outBuilder.trimLine(y, nextPtr->ID())) {

2395 nextPtr->addTatYAbove(y);

2396 #if DEBUG_ADJUST_COINCIDENT

2397 SkDebugf("%s 2 edge=%d y=%1.9g (was fYBottom=%1.9g)\n",

2398 __FUNCTION__, nextPtr->ID(), y, nextPtr->fYBottom);

2399 #endif

2400 nextPtr->fYBottom = y;

2401 }

2402 // add missing t values so edges can be the same length

2403 SkScalar testY = activePtr->fBelow.fY;

2404 nextPtr->addTatYBelow(testY);

2405 if (bottom > testY && testY > y) {

2406 #if DEBUG_ADJUST_COINCIDENT

2407 SkDebugf("%s 3 edge=%d bottom=%1.9g (was bottom=%1.9g)\n",

2408 __FUNCTION__, activePtr->ID(), testY, bottom);

2409 #endif

2410 bottom = testY;

2411 }

2412 testY = nextPtr->fBelow.fY;

2413 activePtr->addTatYBelow(testY);

2414 if (bottom > testY && testY > y) {

2415 #if DEBUG_ADJUST_COINCIDENT

2416 SkDebugf("%s 4 edge=%d bottom=%1.9g (was bottom=%1.9g)\n",

2417 __FUNCTION__, nextPtr->ID(), testY, bottom);

2418 #endif

2419 bottom = testY;

2420 }

2421 }

2422 } else if (firstCoincident) {

2423 skipCoincidence(firstCoincidentWinding, winding, windingMask,

2424 activePtr, firstCoincident);

2425 firstCoincident = NULL;

2426 }

2427 activePtr = nextPtr;

2428 }

2429 if (firstCoincident) {

2430 winding += activePtr->fWorkEdge.winding();

2431 skipCoincidence(firstCoincidentWinding, winding, windingMask, activePtr,

2432 firstCoincident);

2433 }

2434 // fix up the bottom for close call edges. OPTIMIZATION: maybe this could

2435 // be in the loop above, but moved here since loop above reads fBelow and

2436 // it felt unsafe to write it in that loop

2437 for (index = 0; index < edgeCount; ++index) {

2438 (edgeList[index])->fixBelow();

2439 }

2440 return bottom;

2441 }

2442

2443 // stitch edge and t range that satisfies operation

2444 static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar

2445 #if DEBUG_STITCH_EDGE

2446 y

2447 #endif

2448 ,

2449 SkScalar bottom, int windingMask, bool fill, OutEdgeBuilder& outBuilder) {

2450 int winding = 0;

2451 ActiveEdge** activeHandle = edgeList.begin() - 1;

2452 ActiveEdge** lastActive = edgeList.end();

2453 #if DEBUG_STITCH_EDGE

2454 const int tab = 7; // FIXME: debugging only

2455 SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom);

2456 #endif

2457 while (++activeHandle != lastActive) {

2458 ActiveEdge* activePtr = *activeHandle;

2459 const WorkEdge& wt = activePtr->fWorkEdge;

2460 int lastWinding = winding;

2461 winding += wt.winding();

2462 #if DEBUG_STITCH_EDGE

2463 SkDebugf("%*s edge=%d lastWinding=%d winding=%d skip=%d close=%d"

2464 " above=%1.9g below=%1.9g\n",

2465 tab-4, "", activePtr->ID(), lastWinding,

2466 winding, activePtr->fSkip, activePtr->fCloseCall,

2467 activePtr->fTAbove, activePtr->fTBelow);

2468 #endif

2469 if (activePtr->done(bottom)) {

2470 #if DEBUG_STITCH_EDGE

2471 SkDebugf("%*s fDone=%d \|\| fYBottom=%1.9g >= bottom\n", tab, "",

2472 activePtr->fDone, activePtr->fYBottom);

2473 #endif

2474 continue;

2475 }

2476 int opener = (lastWinding & windingMask) == 0;

2477 bool closer = (winding & windingMask) == 0;

2478 SkASSERT(!opener \| !closer);

2479 bool inWinding = opener \| closer;

2480 SkPoint clippedPts[4];

2481 const SkPoint* clipped = NULL;

2482 bool moreToDo, aboveBottom;

2483 do {

2484 double currentT = activePtr->t();

2485 const SkPoint* points = wt.fPts;

2486 double nextT;

2487 SkPath::Verb verb = activePtr->fVerb;

2488 do {

2489 nextT = activePtr->nextT();

2490 // FIXME: obtuse: want efficient way to say

2491 // !currentT && currentT != 1 \|\| !nextT && nextT != 1

2492 if (currentT * nextT != 0 \|\| currentT + nextT != 1) {

2493 // OPTIMIZATION: if !inWinding, we only need

2494 // clipped[1].fY

2495 switch (verb) {

2496 case SkPath::kLine_Verb:

2497 LineSubDivide(points, currentT, nextT, clippedPts);

2498 break;

2499 case SkPath::kQuad_Verb:

2500 QuadSubDivide(points, currentT, nextT, clippedPts);

2501 break;

2502 case SkPath::kCubic_Verb:

2503 CubicSubDivide(points, currentT, nextT, clippedPts);

2504 break;

2505 default:

2506 SkASSERT(0);

2507 break;

2508 }

2509 clipped = clippedPts;

2510 } else {

2511 clipped = points;

2512 }

2513 if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY

2514 != clipped[verb].fY : clipped[0] != clipped[verb])) {

2515 #if DEBUG_STITCH_EDGE

2516 SkDebugf("%*s add%s %1.9g,%1.9g %1.9g,%1.9g edge=%d"

2517 " v=%d t=(%1.9g,%1.9g)\n", tab, "",

2518 kUVerbStr[verb], clipped[0].fX, clipped[0].fY,

2519 clipped[verb].fX, clipped[verb].fY,

2520 activePtr->ID(),

2521 activePtr->fWorkEdge.fVerb

2522 - activePtr->fWorkEdge.fEdge->fVerbs.begin(),

2523 currentT, nextT);

2524 #endif

2525 outBuilder.addCurve(clipped, (SkPath::Verb) verb,

2526 activePtr->fWorkEdge.fEdge->fID,

2527 activePtr->fCloseCall);

2528 } else {

2529 #if DEBUG_STITCH_EDGE

2530 SkDebugf("%*s skip%s %1.9g,%1.9g %1.9g,%1.9g"

2531 " edge=%d v=%d t=(%1.9g,%1.9g)\n", tab, "",

2532 kUVerbStr[verb], clipped[0].fX, clipped[0].fY,

2533 clipped[verb].fX, clipped[verb].fY,

2534 activePtr->ID(),

2535 activePtr->fWorkEdge.fVerb

2536 - activePtr->fWorkEdge.fEdge->fVerbs.begin(),

2537 currentT, nextT);

2538 #endif

2539 }

2540 // by advancing fAbove/fBelow, the next call to sortHorizontal

2541 // will use these values if they're still valid instead of

2542 // recomputing

2543 if (clipped[verb].fY > activePtr->fBelow.fY

2544 && bottom >= activePtr->fBelow.fY

2545 && verb == SkPath::kLine_Verb) {

2546 activePtr->fAbove = activePtr->fBelow;

2547 activePtr->fBelow = activePtr->fTangent = clipped[verb];

2548 activePtr->fTAbove = activePtr->fTBelow < 1

2549 ? activePtr->fTBelow : 0;

2550 activePtr->fTBelow = nextT;

2551 }

2552 currentT = nextT;

2553 moreToDo = activePtr->advanceT();

2554 activePtr->fYBottom = clipped[verb].fY; // was activePtr->fClose Call ? bottom :

2555

2556 // clearing the fSkip/fCloseCall bit here means that trailing ed ges

2557 // fall out of sync, if one edge is long and another is a series of short pieces

2558 // if fSkip/fCloseCall is set, need to recompute coincidence/too -close-to-call

2559 // after advancing

2560 // another approach would be to restrict bottom to smaller part of close call

2561 // maybe this is already happening with coincidence when interse ction is computed,

2562 // and needs to be added to the close call computation as well

2563 // this is hard to do because that the bottom is important is no t known when

2564 // the lines are intersected; only when the computation for edge sorting is done

2565 // does the need for new bottoms become apparent.

2566 // maybe this is good incentive to scrap the current sort and do an insertion

2567 // sort that can take this into consideration when the x value i s computed

2568

2569 // FIXME: initialized in sortHorizontal, cleared here as well so

2570 // that next edge is not skipped -- but should skipped edges eve r

2571 // continue? (probably not)

2572 aboveBottom = clipped[verb].fY < bottom;

2573 if (clipped[0].fY != clipped[verb].fY) {

2574 activePtr->fSkip = false;

2575 activePtr->fCloseCall = false;

2576 aboveBottom &= !activePtr->fCloseCall;

2577 }

2578 #if DEBUG_STITCH_EDGE

2579 else {

2580 if (activePtr->fSkip \|\| activePtr->fCloseCall) {

2581 SkDebugf("%s skip or close == %1.9g\n", __FUNCTION__,

2582 clippedPts[0].fY);

2583 }

2584 }

2585 #endif

2586 } while (moreToDo & aboveBottom);

2587 } while ((moreToDo \|\| activePtr->advance()) & aboveBottom);

2588 }

2589 }

2590

2591 #if DEBUG_DUMP

2592 static void dumpEdgeList(const SkTDArray<InEdge*>& edgeList,

2593 const InEdge& edgeSentinel) {

2594 InEdge** debugPtr = edgeList.begin();

2595 do {

2596 (*debugPtr++)->dump();

2597 } while (*debugPtr != &edgeSentinel);

2598 }

2599 #else

2600 static void dumpEdgeList(const SkTDArray<InEdge*>& ,

2601 const InEdge& ) {

2602 }

2603 #endif

2604

2605 void simplify(const SkPath& path, bool asFill, SkPath& simple) {

2606 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness

2607 int windingMask = (path.getFillType() & 1) ? 1 : -1;

2608 simple.reset();

2609 simple.setFillType(SkPath::kEvenOdd_FillType);

2610 // turn path into list of edges increasing in y

2611 // if an edge is a quad or a cubic with a y extrema, note it, but leave it

2612 // unbroken. Once we have a list, sort it, then walk the list (walk edges

2613 // twice that have y extrema's on top) and detect crossings -- look for raw

2614 // bounds that cross over, then tight bounds that cross

2615 SkTArray<InEdge> edges;

2616 SkTDArray<HorizontalEdge> horizontalEdges;

2617 InEdgeBuilder builder(path, asFill, edges, horizontalEdges);

2618 SkTDArray<InEdge*> edgeList;

2619 InEdge edgeSentinel;

2620 edgeSentinel.reset();

2621 makeEdgeList(edges, edgeSentinel, edgeList);

2622 SkTDArray<HorizontalEdge*> horizontalList;

2623 HorizontalEdge horizontalSentinel;

2624 makeHorizontalList(horizontalEdges, horizontalSentinel, horizontalList);

2625 InEdge** currentPtr = edgeList.begin();

2626 if (!currentPtr) {

2627 return;

2628 }

2629 // find all intersections between edges

2630 // beyond looking for horizontal intercepts, we need to know if any active edges

2631 // intersect edges below 'bottom', but above the active edge segment.

2632 // maybe it makes more sense to compute all intercepts before doing anything

2633 // else, since the intercept list is long-lived, at least in the current design.

2634 SkScalar y = (*currentPtr)->fBounds.fTop;

2635 HorizontalEdge** currentHorizontal = horizontalList.begin();

2636 do {

2637 InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set

2638 SkScalar bottom = findBottom(currentPtr, edgeList.end(),

2639 NULL, y, asFill, lastPtr);

2640 if (lastPtr > currentPtr) {

2641 if (currentHorizontal) {

2642 if ((*currentHorizontal)->fY < SK_ScalarMax) {

2643 addBottomT(currentPtr, lastPtr, currentHorizontal);

2644 }

2645 currentHorizontal = advanceHorizontal(currentHorizontal, bottom) ;

2646 }

2647 addIntersectingTs(currentPtr, lastPtr);

2648 }

2649 y = bottom;

2650 currentPtr = advanceEdges(NULL, currentPtr, lastPtr, y);

2651 } while (*currentPtr != &edgeSentinel);

2652 // if a quadratic or cubic now has an intermediate T value, see if the Ts

2653 // on either side cause the Y values to monotonically increase. If not, spli t

2654 // the curve at the new T.

2655

2656 // try an alternate approach which does not split curves or stitch edges

2657 // (may still need adjustCoincident, though)

2658 // the idea is to output non-intersecting contours, then figure out their

2659 // respective winding contribution

2660 // each contour will need to know whether it is CW or CCW, and then whether

2661 // a ray from that contour hits any a contour that contains it. The ray can

2662 // move to the left and then arbitrarily move up or down (as long as it neve r

2663 // moves to the right) to find a reference sibling contour or containing

2664 // contour. If the contour is part of an intersection, the companion contour

2665 // that is part of the intersection can determine the containership.

2666 if (builder.containsCurves()) {

2667 currentPtr = edgeList.begin();

2668 SkTArray<InEdge> splits;

2669 do {

2670 (*currentPtr)->splitInflectionPts(splits);

2671 } while (*++currentPtr != &edgeSentinel);

2672 if (splits.count()) {

2673 for (int index = 0; index < splits.count(); ++index) {

2674 edges.push_back(splits[index]);

2675 }

2676 edgeList.reset();

2677 makeEdgeList(edges, edgeSentinel, edgeList);

2678 }

2679 }

2680 dumpEdgeList(edgeList, edgeSentinel);

2681 // walk the sorted edges from top to bottom, computing accumulated winding

2682 SkTDArray<ActiveEdge> activeEdges;

2683 OutEdgeBuilder outBuilder(asFill);

2684 currentPtr = edgeList.begin();

2685 y = (*currentPtr)->fBounds.fTop;

2686 do {

2687 InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set

2688 SkScalar bottom = findBottom(currentPtr, edgeList.end(),

2689 &activeEdges, y, asFill, lastPtr);

2690 if (lastPtr > currentPtr) {

2691 bottom = computeInterceptBottom(activeEdges, y, bottom);

2692 SkTDArray<ActiveEdge*> activeEdgeList;

2693 sortHorizontal(activeEdges, activeEdgeList, y);

2694 bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom,

2695 outBuilder);

2696 stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilde r);

2697 }

2698 y = bottom;

2699 // OPTIMIZATION: as edges expire, InEdge allocations could be released

2700 currentPtr = advanceEdges(&activeEdges, currentPtr, lastPtr, y);

2701 } while (*currentPtr != &edgeSentinel);

2702 // assemble output path from string of pts, verbs

2703 outBuilder.bridge();

2704 outBuilder.assemble(simple);

2705 }

OLD	NEW

« no previous file with comments | « experimental/Intersection/EdgeMain.cpp ('k') | experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp » ('j') | no next file with comments »