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

Side by Side Diff: experimental/Intersection/SkAntiEdge.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 2011 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 "SkAntiEdge.h"

8 #include "SkPoint.h"

9

10 /** Returns the signed fraction of a SkFixed

11 */

12 static inline SkFixed SkFixedFraction(SkFixed x)

13 {

14 SkFixed mask = x >> 31 << 16;

15 return (x & 0xFFFF) \| mask;

16 }

17

18 void SkAntiEdge::pointOnLine(SkFixed x, SkFixed y) {

19 float x0 = SkFixedToFloat(x);

20 float y0 = SkFixedToFloat(y);

21 float x1 = SkFixedToFloat(fFirstX);

22 float y1 = SkFixedToFloat(fFirstY);

23 float x2 = SkFixedToFloat(fLastX);

24 float y2 = SkFixedToFloat(fLastY);

25 float numer = (x2 - x1) * (y1 - y0) - (x1 - x0) * (y2 - y1);

26 float denom = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);

27 double dist = fabs(numer) / sqrt(denom);

28 SkAssertResult(dist < 0.01);

29 }

30

31 void SkAntiEdge::pointInLine(SkFixed x, SkFixed y) {

32 if (y == SK_MaxS32) {

33 return;

34 }

35 pointOnLine(x, y);

36 SkAssertResult(y >= fFirstY && y <= fLastY);

37 }

38

39 void SkAntiEdge::validate() {

40 pointOnLine(fWalkX, fY);

41 pointOnLine(fX, fWalkY);

42 }

43

44 bool SkAntiEdge::setLine(const SkPoint& p0, const SkPoint& p1) {

45 fFirstY = SkScalarToFixed(p0.fY);

46 fLastY = SkScalarToFixed(p1.fY);

47 if (fFirstY == fLastY) {

48 return false;

49 }

50 fFirstX = SkScalarToFixed(p0.fX);

51 fLastX = SkScalarToFixed(p1.fX);

52 if (fFirstY > fLastY) {

53 SkTSwap(fFirstX, fLastX);

54 SkTSwap(fFirstY, fLastY);

55 fWinding = -1;

56 } else {

57 fWinding = 1;

58 }

59 SkFixed dx = fLastX - fFirstX;

60 fDXFlipped = dx < 0;

61 SkFixed dy = fLastY - fFirstY;

62 fDX = SkFixedDiv(dx, dy);

63 fDY = dx == 0 ? SK_MaxS32 : SkFixedDiv(dy, SkFixedAbs(dx));

64 fLink = NULL;

65 fLinkSet = false;

66 return true;

67 }

68

69 void SkAntiEdge::calcLine() {

70 SkFixed yStartFrac = SkFixedFraction(fFirstY);

71 if (fDXFlipped) {

72 SkFixed vert = SK_Fixed1 - yStartFrac; // distance from y start to x-axi s

73 fX0 = fFirstX + SkFixedMul(fDX, vert);

74 SkFixed backupX = fFirstX + SkFixedMul(vert, fDX); // x cell to back up to

75 SkFixed cellX = SkIntToFixed(SkFixedFloor(backupX));

76 SkFixed endX = SkIntToFixed(SkFixedFloor(fLastX));

77 if (cellX < endX) {

78 cellX = endX;

79 }

80 SkFixed distX = fFirstX - cellX; // to y-axis

81 fY0 = fFirstY + SkFixedMul(fDY, distX);

82 SkFixed rowBottom = SkIntToFixed(SkFixedCeil(fFirstY + 1));

83 if (fLastY > rowBottom) {

84 fPartialY = 0;

85 fX = fX0;

86 fY = rowBottom;

87 } else {

88 fPartialY = SkFixedFraction(fLastY);

89 fX = fLastX;

90 fY = fLastY;

91 }

92 } else {

93 fPartialY = yStartFrac;

94 fX0 = fFirstX - SkFixedMul(fDX, yStartFrac);

95 fY0 = fFirstY;

96 if (fDY != SK_MaxS32) {

97 SkFixed xStartFrac = SkFixedFraction(fFirstX);

98 fY0 -= SkFixedMul(fDY, xStartFrac);

99 }

100 fX = fFirstX;

101 fY = fFirstY;

102 }

103 fWalkX = fX;

104 fWalkY = fY;

105 fFinished = false;

106 }

107

108 static SkFixed SkFixedAddPin(SkFixed a, SkFixed b) {

109 SkFixed result = a + b;

110 if (((a ^ ~b) & (a ^ result)) >= 0) { // one positive, one negative

111 return result; // or all three same sign

112 }

113 return a < 0 ? -SK_FixedMax : SK_FixedMax;

114 }

115

116 // edge is increasing in x and y

117 uint16_t SkAntiEdge::advanceX(SkFixed left) {

118 validate();

119 SkFixed x = SkFixedAddPin(fX0, fDX);

120 SkFixed wy = SkIntToFixed(SkFixedFloor(fWalkY + SK_Fixed1));

121 pointOnLine(x, wy);

122 SkFixed partial = SK_Fixed1 - fPartialY;

123 SkFixed bottomPartial = wy - fLastY;

124 if (bottomPartial > 0) {

125 partial -= bottomPartial;

126 }

127 if (x > fLastX) {

128 x = fLastX;

129 wy = fLastY;

130 }

131 uint16_t coverage;

132 if (left >= x) {

133 fFinished = true;

134 coverage = partial - 1; // walker is to the right of edge

135 } else {

136 SkFixed y = SkFixedAddPin(fY0, fDY);

137 SkFixed wx = SkIntToFixed(SkFixedFloor(fWalkX + SK_Fixed1));

138 if (fDY != SK_MaxS32) {

139 pointOnLine(wx, y);

140 }

141 if (y > fLastY) {

142 y = fLastY;

143 wx = fLastX;

144 }

145 bool topCorner = fWalkX <= fX;

146 bool bottomCorner = x <= wx;

147 bool halfPlane = !(topCorner ^ bottomCorner);

148 if (halfPlane) {

149 if (x - SkIntToFixed(SkFixedFloor(fX)) <= SK_Fixed1) {

150 coverage = ~((fX + x) >> 1); // avg of fx, fx+dx

151 fFinished = true;

152 if (x >= left + SK_Fixed1) {

153 fWalkX = wx;

154 fY = fY0 = y;

155 }

156 } else {

157 SkAssertResult(y - SkIntToFixed(SkFixedFloor(fY)) <= SK_Fixed1);

158 coverage = ((fY + y) >> 1);

159 fFinished = y == fLastY;

160 fWalkX = wx;

161 fY = fY0 = y;

162 }

163 coverage = coverage * partial >> 16;

164 } else if (topCorner) {

165 SkFixed xDiff = wx - fX;

166 SkAssertResult(xDiff >= 0);

167 SkAssertResult(xDiff <= SK_Fixed1);

168 SkFixed yDiff = y - fWalkY;

169 // This may be a very small negative number if error accumulates

170 // FIXME: for now, try setting it to zero in that case.

171 if (yDiff < 0) {

172 fX = fX0 = SkIntToFixed(SkFixedCeil(fX));

173 yDiff = 0;

174 }

175 SkAssertResult(yDiff >= 0);

176 SkAssertResult(yDiff <= SK_Fixed1);

177 int xCoverage = xDiff >> 1; // throw away 1 bit so multiply

178 int yCoverage = yDiff >> 1; // stays in range

179 int triangle = xCoverage * yCoverage; // 30 bits

180 SkFixed bottomPartial = y - fLastY;

181 fFinished = bottomPartial >= 0;

182 if (fFinished) {

183 yCoverage = bottomPartial >> 1;

184 xCoverage = (wx - fLastX) >> 1;

185 triangle -= xCoverage * yCoverage;

186 }

187 coverage = triangle >> 15;

188 fWalkX = wx;

189 fY = fY0 = y;

190 } else {

191 SkAssertResult(bottomCorner);

192 SkFixed xDiff = x - fWalkX;

193 SkAssertResult(xDiff >= 0);

194 SkAssertResult(xDiff <= SK_Fixed1);

195 SkFixed yDiff = wy - fY;

196 SkAssertResult(yDiff >= 0);

197 SkAssertResult(yDiff <= SK_Fixed1);

198 int xCoverage = xDiff >> 1; // throw away 1 bit so multiply

199 int yCoverage = yDiff >> 1; // stays in range

200 int triangle = xCoverage * yCoverage >> 15;

201 coverage = partial - 1 - triangle;

202 fFinished = true;

203 }

204 }

205 validate();

206 return coverage;

207 }

208

209 // edge is increasing in x, but decreasing in y

210 uint16_t SkAntiEdge::advanceFlippedX(SkFixed left) {

211 validate();

212 SkFixed x = SkFixedAddPin(fX0, -fDX);

213 SkFixed wy = SkIntToFixed(SkFixedFloor(fWalkY - 1));

214 pointOnLine(x, wy);

215 SkFixed partial = fPartialY ? fPartialY : SK_Fixed1;

216 SkFixed topPartial = fFirstY - wy;

217 if (topPartial > 0) {

218 partial -= topPartial;

219 }

220 if (x > fFirstX) {

221 x = fFirstX;

222 wy = fFirstY;

223 }

224 uint16_t coverage;

225 if (left >= x) {

226 fFinished = true;

227 coverage = partial - 1; // walker is to the right of edge

228 } else {

229 SkFixed y = SkFixedAddPin(fY0, -fDY);

230 SkFixed wx = SkIntToFixed(SkFixedFloor(fWalkX + SK_Fixed1));

231 pointOnLine(wx, y);

232 if (y < fFirstY) {

233 y = fFirstY;

234 wx = fFirstX;

235 }

236 bool bottomCorner = fWalkX <= fX;

237 bool topCorner = x <= wx;

238 bool halfPlane = !(topCorner ^ bottomCorner);

239 if (halfPlane) {

240 if (x - SkIntToFixed(SkFixedFloor(fX)) <= SK_Fixed1) {

241 coverage = ~((fX + x) >> 1); // avg of fx, fx+dx

242 fFinished = true;

243 } else {

244 SkAssertResult(y - SkIntToFixed(SkFixedFloor(fY)) <= SK_Fixed1);

245 coverage = ~((fY + y) >> 1);

246 fFinished = y == fY;

247 fWalkX = wx;

248 fY = fY0 = y;

249 }

250 coverage = coverage * partial >> 16;

251 } else if (bottomCorner) {

252 SkFixed xDiff = wx - fX;

253 SkAssertResult(xDiff >= 0);

254 SkAssertResult(xDiff <= SK_Fixed1);

255 SkFixed yDiff = fWalkY - y;

256 SkAssertResult(yDiff >= 0);

257 SkAssertResult(yDiff <= SK_Fixed1);

258 int xCoverage = xDiff >> 1; // throw away 1 bit so multiply

259 int yCoverage = yDiff >> 1; // stays in range

260 int triangle = xCoverage * yCoverage; // 30 bits

261 SkFixed bottomPartial = fFirstY - y;

262 fFinished = bottomPartial >= 0;

263 if (fFinished) {

264 yCoverage = bottomPartial >> 1;

265 xCoverage = (wx - fFirstX) >> 1;

266 triangle -= xCoverage * yCoverage;

267 }

268 coverage = triangle >> 15;

269 fWalkX = wx;

270 fY = fY0 = y;

271 } else {

272 SkAssertResult(topCorner);

273 SkFixed xDiff = x - fWalkX;

274 SkAssertResult(xDiff >= 0);

275 SkAssertResult(xDiff <= SK_Fixed1);

276 SkFixed yDiff = fY - wy;

277 SkAssertResult(yDiff >= 0);

278 SkAssertResult(yDiff <= SK_Fixed1);

279 int xCoverage = xDiff >> 1; // throw away 1 bit so multiply

280 int yCoverage = yDiff >> 1; // stays in range

281 int triangle = xCoverage * yCoverage >> 15;

282 coverage = partial - 1 - triangle;

283 fFinished = true;

284 }

285 }

286 validate();

287 return coverage;

288 }

289

290 void SkAntiEdge::advanceY(SkFixed top) {

291 validate();

292 fX0 = SkFixedAddPin(fX0, fDX);

293 fPartialY = 0;

294 if (fDXFlipped) {

295 if (fX0 < fLastX) {

296 fWalkX = fX = fLastX;

297 } else {

298 fWalkX = fX = fX0;

299 }

300 SkFixed bottom = top + SK_Fixed1;

301 if (bottom > fLastY) {

302 bottom = fLastY;

303 }

304 SkFixed vert = bottom - fFirstY; // distance from y start to x-axis

305 SkFixed backupX = fFirstX + SkFixedMul(vert, fDX); // x cell to back up to

306 SkFixed distX = fFirstX - SkIntToFixed(SkFixedFloor(backupX)); // to y-a xis

307 fY0 = fFirstY + SkFixedMul(fDY, distX);

308

309 fY = top + SK_Fixed1;

310 if (fY > fLastY) {

311 fY = fLastY;

312 }

313 if (fLastY < top + SK_Fixed1) {

314 fPartialY = SkFixedFraction(fLastY);

315 }

316 } else {

317 if (fX0 > fLastX) {

318 fX0 = fLastX;

319 }

320 fX = fX0;

321 }

322 fWalkY = SkIntToFixed(SkFixedFloor(fWalkY + SK_Fixed1));

323 if (fWalkY > fLastY) {

324 fWalkY = fLastY;

325 }

326 validate();

327 fFinished = false;

328 }

329

330 int SkAntiEdgeBuilder::build(const SkPoint pts[], int count) {

331 SkAntiEdge* edge = fEdges.append();

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

333 if (edge->setLine(pts[index], pts[(index + 1) % count])) {

334 edge = fEdges.append();

335 }

336 }

337 int result = fEdges.count();

338 fEdges.setCount(--result);

339 if (result > 0) {

340 sk_bzero(&fHeadEdge, sizeof(fHeadEdge));

341 sk_bzero(&fTailEdge, sizeof(fTailEdge));

342 for (int index = 0; index < result; ++index) {

343 *fList.append() = &fEdges[index];

344 }

345 }

346 return result;

347 }

348

349 void SkAntiEdgeBuilder::calc() {

350 for (SkAntiEdge* active = fEdges.begin(); active != fEdges.end(); ++active) {

351 active->calcLine();

352 }

353 // compute winding sum for edges

354 SkAntiEdge* first = fHeadEdge.fNext;

355 SkAntiEdge* active;

356 SkAntiEdge* listTop = first;

357 for (active = first; active != &fTailEdge; active = active->fNext) {

358 active->fWindingSum = active->fWinding;

359 while (listTop->fLastY < active->fFirstY) {

360 listTop = listTop->fNext;

361 }

362 for (SkAntiEdge* check = listTop; check->fFirstY <= active->fFirstY; che ck = check->fNext) {

363 if (check == active) {

364 continue;

365 }

366 if (check->fLastY <= active->fFirstY) {

367 continue;

368 }

369 if (check->fFirstX > active->fFirstX) {

370 continue;

371 }

372 if (check->fFirstX == active->fFirstX && check->fDX > active->fDX) {

373 continue;

374 }

375 active->fWindingSum += check->fWinding;

376 }

377 }

378 }

379

380 extern "C" {

381 static int edge_compare(const void* a, const void* b) {

382 const SkAntiEdge* edgea = (const SkAntiEdge*)a;

383 const SkAntiEdge* edgeb = (const SkAntiEdge*)b;

384

385 int valuea = edgea->fFirstY;

386 int valueb = edgeb->fFirstY;

387

388 if (valuea == valueb) {

389 valuea = edgea->fFirstX;

390 valueb = edgeb->fFirstX;

391 }

392

393 if (valuea == valueb) {

394 valuea = edgea->fDX;

395 valueb = edgeb->fDX;

396 }

397

398 return valuea - valueb;

399 }

400 }

401

402 void SkAntiEdgeBuilder::sort(SkTDArray<SkAntiEdge*>& listOfEdges) {

403 SkAntiEdge** list = listOfEdges.begin();

404 int count = listOfEdges.count();

405 qsort(list, count, sizeof(SkAntiEdge*), edge_compare);

406

407 // link the edges in sorted order

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

409 list[i - 1]->fNext = list[i];

410 list[i]->fPrev = list[i - 1];

411 }

412 }

413

414 #define kEDGE_HEAD_XY SK_MinS32

415 #define kEDGE_TAIL_XY SK_MaxS32

416

417 void SkAntiEdgeBuilder::sort() {

418 sort(fList);

419 SkAntiEdge* last = fList.end()[-1];

420 fHeadEdge.fNext = fList[0];

421 fHeadEdge.fFirstX = fHeadEdge.fFirstY = fHeadEdge.fWalkY = fHeadEdge.fLastY = kEDGE_HEAD_XY;

422 fList[0]->fPrev = &fHeadEdge;

423

424 fTailEdge.fPrev = last;

425 fTailEdge.fFirstX = fTailEdge.fFirstY = fTailEdge.fWalkY = fTailEdge.fLastY = kEDGE_TAIL_XY;

426 last->fNext = &fTailEdge;

427 }

428

429 static inline void remove_edge(SkAntiEdge* edge) {

430 edge->fPrev->fNext = edge->fNext;

431 edge->fNext->fPrev = edge->fPrev;

432 }

433

434 static inline void swap_edges(SkAntiEdge* prev, SkAntiEdge* next) {

435 SkASSERT(prev->fNext == next && next->fPrev == prev);

436

437 // remove prev from the list

438 prev->fPrev->fNext = next;

439 next->fPrev = prev->fPrev;

440

441 // insert prev after next

442 prev->fNext = next->fNext;

443 next->fNext->fPrev = prev;

444 next->fNext = prev;

445 prev->fPrev = next;

446 }

447

448 static void backward_insert_edge_based_on_x(SkAntiEdge* edge SkDECLAREPARAM(int, y)) {

449 SkFixed x = edge->fFirstX;

450

451 for (;;) {

452 SkAntiEdge* prev = edge->fPrev;

453

454 // add 1 to curr_y since we may have added new edges (built from curves)

455 // that start on the next scanline

456 SkASSERT(prev && SkFixedFloor(prev->fWalkY - prev->fDXFlipped) <= y + 1) ;

457

458 if (prev->fFirstX <= x) {

459 break;

460 }

461 swap_edges(prev, edge);

462 }

463 }

464

465 static void insert_new_edges(SkAntiEdge* newEdge, SkFixed curr_y) {

466 int y = SkFixedFloor(curr_y);

467 if (SkFixedFloor(newEdge->fWalkY - newEdge->fDXFlipped) < y) {

468 return;

469 }

470 while (SkFixedFloor(newEdge->fWalkY - newEdge->fDXFlipped) == y) {

471 SkAntiEdge* next = newEdge->fNext;

472 backward_insert_edge_based_on_x(newEdge SkPARAM(y));

473 newEdge = next;

474 }

475 }

476

477 static int find_active_edges(int y, SkAntiEdge** activeLeft,

478 SkAntiEdge** activeLast) {

479 SkAntiEdge* first = *activeLeft;

480 SkFixed bottom = first->fLastY;

481 SkAntiEdge* active = first->fNext;

482 first->fLinkSet = false;

483 SkFixed yLimit = SkIntToFixed(y + 1); // limiting pixel edge

484 for ( ; active->fWalkY != kEDGE_TAIL_XY; active = active->fNext) {

485 active->fLinkSet = false;

486 if (yLimit <= active->fWalkY - active->fDXFlipped) {

487 break;

488 }

489 if ((*activeLeft)->fWalkX > active->fWalkX) {

490 *activeLeft = active;

491 }

492 if (bottom > active->fLastY) {

493 bottom = active->fLastY;

494 }

495 }

496 *activeLast = active;

497 return SkFixedCeil(bottom);

498 }

499

500 // All edges are oriented to increase in y. Link edges with common tops and

501 // bottoms so the links can share their winding sum.

502 void SkAntiEdgeBuilder::link() {

503 SkAntiEdge* tail = fEdges.end();

504 // look for links forwards and backwards

505 SkAntiEdge* prev = fEdges.begin();

506 SkAntiEdge* active;

507 for (active = prev + 1; active != tail; ++active) {

508 if (prev->fWinding == active->fWinding) {

509 if (prev->fLastX == active->fFirstX && prev->fLastY == active->fFirs tY) {

510 prev->fLink = active;

511 active->fLinkSet = true;

512 } else if (active->fLastX == prev->fFirstX && active->fLastY == prev ->fFirstY) {

513 active->fLink = prev;

514 prev->fLinkSet = true;

515 }

516 }

517 prev = active;

518 }

519 // look for stragglers

520 prev = fEdges.begin() - 1;

521 do {

522 do {

523 if (++prev == tail) {

524 return;

525 }

526 } while (prev->fLinkSet \|\| NULL != prev->fLink);

527 for (active = prev + 1; active != tail; ++active) {

528 if (active->fLinkSet \|\| NULL != active->fLink) {

529 continue;

530 }

531 if (prev->fWinding != active->fWinding) {

532 continue;

533 }

534 if (prev->fLastX == active->fFirstX && prev->fLastY == active->fFirs tY) {

535 prev->fLink = active;

536 active->fLinkSet = true;

537 break;

538 }

539 if (active->fLastX == prev->fFirstX && active->fLastY == prev->fFirs tY) {

540 active->fLink = prev;

541 prev->fLinkSet = true;

542 break;

543 }

544 }

545 } while (true);

546 }

547

548 void SkAntiEdgeBuilder::split(SkAntiEdge* edge, SkFixed y) {

549 SkPoint upperPoint = {edge->fFirstX, edge->fFirstY};

550 SkPoint midPoint = {edge->fFirstX + SkMulDiv(y - edge->fFirstY,

551 edge->fLastX - edge->fFirstX, edge->fLastY - edge->fFirstY), y};

552 SkPoint lowerPoint = {edge->fLastX, edge->fLastY};

553 int8_t winding = edge->fWinding;

554 edge->setLine(upperPoint, midPoint);

555 edge->fWinding = winding;

556 SkAntiEdge* lower = fEdges.append();

557 lower->setLine(midPoint, lowerPoint);

558 lower->fWinding = winding;

559 insert_new_edges(lower, y);

560 }

561

562 // An edge computes pixel coverage by considering the integral winding value

563 // to its left. If an edge is enclosed by fractional winding, split it.

564 // FIXME: This is also a good time to find crossing edges and split them, too.

565 void SkAntiEdgeBuilder::split() {

566 // create a new set of edges that describe the whole link

567 SkTDArray<SkAntiEdge> links;

568 SkAntiEdge* first = fHeadEdge.fNext;

569 SkAntiEdge* active;

570 for (active = first; active != &fTailEdge; active = active->fNext) {

571 if (active->fLinkSet \|\| NULL == active->fLink) {

572 continue;

573 }

574 SkAntiEdge* link = links.append();

575 link->fFirstX = active->fFirstX;

576 link->fFirstY = active->fFirstY;

577 SkAntiEdge* linkEnd;

578 SkAntiEdge* next = active;

579 do {

580 linkEnd = next;

581 next = next->fLink;

582 } while (NULL != next);

583 link->fLastX = linkEnd->fLastX;

584 link->fLastY = linkEnd->fLastY;

585 }

586 // create a list of all edges, links and singletons

587 SkTDArray<SkAntiEdge*> list;

588 for (active = links.begin(); active != links.end(); ++active) {

589 *list.append() = active;

590 }

591 for (active = first; active != &fTailEdge; active = active->fNext) {

592 if (!active->fLinkSet && NULL == active->fLink) {

593 SkAntiEdge* link = links.append();

594 link->fFirstX = active->fFirstX;

595 link->fFirstY = active->fFirstY;

596 link->fLastX = active->fLastX;

597 link->fLastY = active->fLastY;

598 *list.append() = link;

599 }

600 }

601 SkAntiEdge tail;

602 tail.fFirstY = tail.fLastY = kEDGE_TAIL_XY;

603 *list.append() = &tail;

604 sort(list);

605 // walk the list, splitting edges partially occluded on the left

606 SkAntiEdge* listTop = list[0];

607 for (active = first; active != &fTailEdge; active = active->fNext) {

608 while (listTop->fLastY < active->fFirstY) {

609 listTop = listTop->fNext;

610 }

611 for (SkAntiEdge* check = listTop; check->fFirstY < active->fLastY; check = check->fNext) {

612 if (check->fFirstX > active->fFirstX) {

613 continue;

614 }

615 if (check->fFirstX == active->fFirstX && check->fDX > active->fDX) {

616 continue;

617 }

618 if (check->fFirstY > active->fFirstY) {

619 split(active, check->fFirstY);

620 }

621 if (check->fLastY < active->fLastY) {

622 split(active, check->fLastY);

623 }

624 }

625 }

626 }

627

628 static inline uint8_t coverage_to_8(int coverage) {

629 uint16_t x = coverage < 0 ? 0 : coverage > 0xFFFF ? 0xFFFF : coverage;

630 // for values 0x7FFF and smaller, add (0x7F - high byte) and trunc

631 // for values 0x8000 and larger, subtract (high byte - 0x80) and trunc

632 return (x + 0x7f + (x >> 15) - (x >> 8)) >> 8;

633 }

634

635 void SkAntiEdgeBuilder::walk(uint8_t* result, int rowBytes, int height) {

636 SkAntiEdge* first = fHeadEdge.fNext;

637 SkFixed top = first->fWalkY - first->fDXFlipped;

638 int y = SkFixedFloor(top);

639 do {

640 SkAntiEdge* activeLeft = first;

641 SkAntiEdge* activeLast, * active;

642 int yLast = find_active_edges(y, &activeLeft, &activeLast);

643 while (y < yLast) {

644 SkAssertResult(y >= 0);

645 SkAssertResult(y < height);

646 SkFixed left = activeLeft->fWalkX;

647 int x = SkFixedFloor(left);

648 uint8_t* resultPtr = &result[y * rowBytes + x];

649 bool finished;

650 do {

651 left = SkIntToFixed(x);

652 SkAssertResult(x >= 0);

653 // SkAssertResult(x < pixelCol);

654 if (x >= rowBytes) { // FIXME: cumulative error in fX += fDX

655 break; // fails to set fFinished early enough

656 } // see test 6 (dy<dx)

657 finished = true;

658 int coverage = 0;

659 for (active = first; active != activeLast; active = active->fNex t) {

660 if (left + SK_Fixed1 <= active->fX) {

661 finished = false;

662 continue; // walker is to the left of edge

663 }

664 int cover = active->fDXFlipped ?

665 active->advanceFlippedX(left) : active->advanceX(left);

666 if (0 == active->fWindingSum) {

667 cover = -cover;

668 }

669 coverage += cover;

670 finished &= active->fFinished;

671 }

672 uint8_t old = *resultPtr;

673 uint8_t pix = coverage_to_8(coverage);

674 uint8_t blend = old > pix ? old : pix;

675 *resultPtr++ = blend;

676 ++x;

677 } while (!finished);

678 ++y;

679 top = SkIntToFixed(y);

680 SkFixed topLimit = top + SK_Fixed1;

681 SkFixed xSort = -SK_FixedMax;

682 for (active = first; active != activeLast; active = active->fNext) {

683 if (xSort > active->fX \|\| topLimit > active->fLastY) {

684 yLast = y; // recompute bottom after all Ys are advanced

685 }

686 xSort = active->fX;

687 if (active->fWalkY < active->fLastY) {

688 active->advanceY(top);

689 }

690 }

691 for (active = first; active != activeLast; ) {

692 SkAntiEdge* next = active->fNext;

693 if (top >= active->fLastY) {

694 remove_edge(active);

695 }

696 active = next;

697 }

698 first = fHeadEdge.fNext;

699 }

700 SkAntiEdge* prev = activeLast->fPrev;

701 if (prev != &fHeadEdge) {

702 insert_new_edges(prev, top);

703 first = fHeadEdge.fNext;

704 }

705 } while (first->fWalkY < kEDGE_TAIL_XY);

706 }

707

708 void SkAntiEdgeBuilder::process(const SkPoint* points, int ptCount,

709 uint8_t* result, int pixelCol, int pixelRow) {

710 if (ptCount < 3) {

711 return;

712 }

713 int count = build(points, ptCount);

714 if (count == 0) {

715 return;

716 }

717 SkAssertResult(count > 1);

718 link();

719 sort();

720 split();

721 calc();

722 walk(result, pixelCol, pixelRow);

723 }

724

725 ////////////////////////////////////////////////////////////////////////////////

726

727 int test3by3_test;

728

729 // input is a rectangle

730 static void test_3_by_3() {

731 const int pixelRow = 3;

732 const int pixelCol = 3;

733 const int ptCount = 4;

734 const int pixelCount = pixelRow * pixelCol;

735 const SkPoint tests[][ptCount] = {

736 {{2.0f, 1.0f}, {1.0f, 1.0f}, {1.0f, 2.0f}, {2.0f, 2.0f}}, // 0: full rec t

737 {{2.5f, 1.0f}, {1.5f, 1.0f}, {1.5f, 2.0f}, {2.5f, 2.0f}}, // 1: y edge

738 {{2.0f, 1.5f}, {1.0f, 1.5f}, {1.0f, 2.5f}, {2.0f, 2.5f}}, // 2: x edge

739 {{2.5f, 1.5f}, {1.5f, 1.5f}, {1.5f, 2.5f}, {2.5f, 2.5f}}, // 3: x/y edge

740 {{2.8f, 0.2f}, {0.2f, 0.2f}, {0.2f, 2.8f}, {2.8f, 2.8f}}, // 4: large

741 {{1.8f, 1.2f}, {1.2f, 1.2f}, {1.2f, 1.8f}, {1.8f, 1.8f}}, // 5: small

742 {{0.0f, 0.0f}, {0.0f, 1.0f}, {3.0f, 2.0f}, {3.0f, 1.0f}}, // 6: dy<dx

743 {{3.0f, 0.0f}, {0.0f, 1.0f}, {0.0f, 2.0f}, {3.0f, 1.0f}}, // 7: dy<-dx

744 {{1.0f, 0.0f}, {0.0f, 0.0f}, {1.0f, 3.0f}, {2.0f, 3.0f}}, // 8: dy>dx

745 {{2.0f, 0.0f}, {1.0f, 0.0f}, {0.0f, 3.0f}, {1.0f, 3.0f}}, // 9: dy>-dx

746 {{0.5f, 0.5f}, {0.5f, 1.5f}, {2.5f, 2.5f}, {2.5f, 1.5f}}, // 10: dy<dx 2

747 {{2.5f, 0.5f}, {0.5f, 1.5f}, {0.5f, 2.5f}, {2.5f, 1.5f}}, // 11: dy<-dx 2

748 {{0.0f, 0.0f}, {2.0f, 0.0f}, {2.0f, 2.0f}, {0.0f, 2.0f}}, // 12: 2x2

749 {{0.0f, 0.0f}, {3.0f, 0.0f}, {3.0f, 3.0f}, {0.0f, 3.0f}}, // 13: 3x3

750 {{1.75f, 0.25f}, {2.75f, 1.25f}, {1.25f, 2.75f}, {0.25f, 1.75f}}, // 14

751 {{2.25f, 0.25f}, {2.75f, 0.75f}, {0.75f, 2.75f}, {0.25f, 2.25f}}, // 15

752 {{0.25f, 0.75f}, {0.75f, 0.25f}, {2.75f, 2.25f}, {2.25f, 2.75f}}, // 16

753 {{1.25f, 0.50f}, {1.75f, 0.25f}, {2.75f, 2.25f}, {2.25f, 2.50f}}, // 17

754 {{1.00f, 0.75f}, {2.00f, 0.50f}, {2.00f, 1.50f}, {1.00f, 1.75f}}, // 18

755 {{1.00f, 0.50f}, {2.00f, 0.75f}, {2.00f, 1.75f}, {1.00f, 1.50f}}, // 19

756 {{1.00f, 0.75f}, {1.00f, 1.75f}, {2.00f, 1.50f}, {2.00f, 0.50f}}, // 20

757 {{1.00f, 0.50f}, {1.00f, 1.50f}, {2.00f, 1.75f}, {2.00f, 0.75f}}, // 21

758 };

759 const uint8_t results[][pixelCount] = {

760 {0x00, 0x00, 0x00, // 0: 1 pixel rect

761 0x00, 0xFF, 0x00,

762 0x00, 0x00, 0x00},

763 {0x00, 0x00, 0x00, // 1: y edge

764 0x00, 0x7F, 0x80,

765 0x00, 0x00, 0x00},

766 {0x00, 0x00, 0x00, // 2: x edge

767 0x00, 0x7F, 0x00,

768 0x00, 0x7F, 0x00},

769 {0x00, 0x00, 0x00, // 3: x/y edge

770 0x00, 0x40, 0x40,

771 0x00, 0x40, 0x40},

772 {0xA3, 0xCC, 0xA3, // 4: large

773 0xCC, 0xFF, 0xCC,

774 0xA3, 0xCC, 0xA3},

775 {0x00, 0x00, 0x00, // 5: small

776 0x00, 0x5C, 0x00,

777 0x00, 0x00, 0x00},

778 {0xD5, 0x80, 0x2B, // 6: dy<dx

779 0x2A, 0x7F, 0xD4,

780 0x00, 0x00, 0x00},

781 {0x2B, 0x80, 0xD5, // 7: dy<-dx

782 0xD4, 0x7F, 0x2A,

783 0x00, 0x00, 0x00},

784 {0xD5, 0x2A, 0x00, // 8: dy>dx

785 0x80, 0x7F, 0x00,

786 0x2B, 0xD4, 0x00},

787 {0x2A, 0xD5, 0x00, // 9: dy>-dx

788 0x7F, 0x80, 0x00,

789 0xD4, 0x2B, 0x00},

790 {0x30, 0x10, 0x00, // 10: dy<dx 2

791 0x50, 0xDF, 0x50,

792 0x00, 0x10, 0x30},

793 {0x00, 0x10, 0x30, // 11: dy<-dx 2

794 0x50, 0xDF, 0x50,

795 0x30, 0x10, 0x00},

796 {0xFF, 0xFF, 0x00, // 12: 2x2

797 0xFF, 0xFF, 0x00,

798 0x00, 0x00, 0x00},

799 {0xFF, 0xFF, 0xFF, // 13: 3x3

800 0xFF, 0xFF, 0xFF,

801 0xFF, 0xFF, 0xFF},

802 {0x00, 0x70, 0x20, // 14

803 0x70, 0xFF, 0x70,

804 0x20, 0x70, 0x00},

805 {0x00, 0x20, 0x60, // 15

806 0x20, 0xBF, 0x20,

807 0x60, 0x20, 0x00},

808 {0x60, 0x20, 0x00, // 16

809 0x20, 0xBF, 0x20,

810 0x00, 0x20, 0x60},

811 {0x00, 0x60, 0x04, // 17

812 0x00, 0x40, 0x60,

813 0x00, 0x00, 0x3C},

814 {0x00, 0x60, 0x00, // 18

815 0x00, 0x9F, 0x00,

816 0x00, 0x00, 0x00},

817 {0x00, 0x60, 0x00, // 19

818 0x00, 0x9F, 0x00,

819 0x00, 0x00, 0x00},

820 {0x00, 0x60, 0x00, // 20

821 0x00, 0x9F, 0x00,

822 0x00, 0x00, 0x00},

823 {0x00, 0x60, 0x00, // 21

824 0x00, 0x9F, 0x00,

825 0x00, 0x00, 0x00},

826 };

827 const int testCount = sizeof(tests) / sizeof(tests[0]);

828 SkAssertResult(testCount == sizeof(results) / sizeof(results[0]));

829 int testFirst = test3by3_test < 0 ? 0 : test3by3_test;

830 int testLast = test3by3_test < 0 ? testCount : test3by3_test + 1;

831 for (int testIndex = testFirst; testIndex < testLast; ++testIndex) {

832 uint8_t result[pixelRow][pixelCol];

833 sk_bzero(result, sizeof(result));

834 const SkPoint* rect = tests[testIndex];

835 SkAntiEdgeBuilder builder;

836 builder.process(rect, ptCount, result[0], pixelCol, pixelRow);

837 SkAssertResult(memcmp(results[testIndex], result[0], pixelCount) == 0);

838 }

839 }

840

841 // input has arbitrary number of points

842 static void test_arbitrary_3_by_3() {

843 const int pixelRow = 3;

844 const int pixelCol = 3;

845 const int pixelCount = pixelRow * pixelCol;

846 const SkPoint t1[] = { {1,1}, {2,1}, {2,1.5f}, {1,1.5f}, {1,2}, {2,2},

847 {2,1.5f}, {1,1.5f}, {1,1} };

848 const SkPoint* tests[] = { t1 };

849 size_t testPts[] = { sizeof(t1) / sizeof(t1[0]) };

850 const uint8_t results[][pixelCount] = {

851 {0x00, 0x00, 0x00, // 0: 1 pixel rect

852 0x00, 0xFF, 0x00,

853 0x00, 0x00, 0x00},

854 };

855 const int testCount = sizeof(tests) / sizeof(tests[0]);

856 SkAssertResult(testCount == sizeof(results) / sizeof(results[0]));

857 int testFirst = test3by3_test < 0 ? 0 : test3by3_test;

858 int testLast = test3by3_test < 0 ? testCount : test3by3_test + 1;

859 for (int testIndex = testFirst; testIndex < testLast; ++testIndex) {

860 uint8_t result[pixelRow][pixelCol];

861 sk_bzero(result, sizeof(result));

862 const SkPoint* pts = tests[testIndex];

863 size_t ptCount = testPts[testIndex];

864 SkAntiEdgeBuilder builder;

865 builder.process(pts, ptCount, result[0], pixelCol, pixelRow);

866 SkAssertResult(memcmp(results[testIndex], result[0], pixelCount) == 0);

867 }

868 }

869

870 #include "SkRect.h"

871 #include "SkPath.h"

872

873 int testsweep_test;

874

875 static void create_sweep(uint8_t* result, int pixelRow, int pixelCol, SkScalar r ectWidth) {

876 const int ptCount = 4;

877 SkRect refRect = {pixelCol / 2 - rectWidth / 2, 5,

878 pixelCol / 2 + rectWidth / 2, pixelRow / 2 - 5};

879 SkPath refPath;

880 refPath.addRect(refRect);

881 SkScalar angleFirst = testsweep_test < 0 ? 0 : testsweep_test;

882 SkScalar angleLast = testsweep_test < 0 ? 360 : testsweep_test + 1;

883 for (SkScalar angle = angleFirst; angle < angleLast; angle += 12) {

884 SkPath rotPath;

885 SkMatrix matrix;

886 matrix.setRotate(angle, SkIntToScalar(pixelCol) / 2,

887 SkIntToScalar(pixelRow) / 2);

888 refPath.transform(matrix, &rotPath);

889 SkPoint rect[ptCount], temp[2];

890 SkPath::Iter iter(rotPath, false);

891 int index = 0;

892 for (;;) {

893 SkPath::Verb verb = iter.next(temp);

894 if (verb == SkPath::kMove_Verb) {

895 continue;

896 }

897 if (verb == SkPath::kClose_Verb) {

898 break;

899 }

900 SkAssertResult(SkPath::kLine_Verb == verb);

901 rect[index++] = temp[0];

902 }

903 SkAntiEdgeBuilder builder;

904 builder.process(rect, ptCount, result, pixelCol, pixelRow);

905 }

906 }

907

908 static void create_horz(uint8_t* result, int pixelRow, int pixelCol) {

909 const int ptCount = 4;

910 for (SkScalar x = 0; x < 100; x += 5) {

911 SkPoint rect[ptCount];

912 rect[0].fX = 0; rect[0].fY = x;

913 rect[1].fX = 100; rect[1].fY = x;

914 rect[2].fX = 100; rect[2].fY = x + x / 50;

915 rect[3].fX = 0; rect[3].fY = x + x / 50;

916 SkAntiEdgeBuilder builder;

917 builder.process(rect, ptCount, result, pixelCol, pixelRow);

918 }

919 }

920

921 static void create_vert(uint8_t* result, int pixelRow, int pixelCol) {

922 const int ptCount = 4;

923 for (SkScalar x = 0; x < 100; x += 5) {

924 SkPoint rect[ptCount];

925 rect[0].fY = 0; rect[0].fX = x;

926 rect[1].fY = 100; rect[1].fX = x;

927 rect[2].fY = 100; rect[2].fX = x + x / 50;

928 rect[3].fY = 0; rect[3].fX = x + x / 50;

929 SkAntiEdgeBuilder builder;

930 builder.process(rect, ptCount, result, pixelCol, pixelRow);

931 }

932 }

933

934 static void create_angle(uint8_t* result, int pixelRow, int pixelCol, SkScalar a ngle) {

935 const int ptCount = 4;

936 SkRect refRect = {25, 25, 125, 125};

937 SkPath refPath;

938 for (SkScalar x = 30; x < 125; x += 5) {

939 refRect.fTop = x;

940 refRect.fBottom = x + (x - 25) / 50;

941 refPath.addRect(refRect);

942 }

943 SkPath rotPath;

944 SkMatrix matrix;

945 matrix.setRotate(angle, 75, 75);

946 refPath.transform(matrix, &rotPath);

947 SkPath::Iter iter(rotPath, false);

948 for (SkScalar x = 30; x < 125; x += 5) {

949 SkPoint rect[ptCount], temp[2];

950 int index = 0;

951 for (;;) {

952 SkPath::Verb verb = iter.next(temp);

953 if (verb == SkPath::kMove_Verb) {

954 continue;

955 }

956 if (verb == SkPath::kClose_Verb) {

957 break;

958 }

959 SkAssertResult(SkPath::kLine_Verb == verb);

960 rect[index++] = temp[0];

961 }

962 // if ((x == 30 \|\| x == 75) && angle == 12) continue;

963 SkAntiEdgeBuilder builder;

964 builder.process(rect, ptCount, result, pixelCol, pixelRow);

965 }

966 }

967

968 static void test_sweep() {

969 const int pixelRow = 100;

970 const int pixelCol = 100;

971 uint8_t result[pixelRow][pixelCol];

972 sk_bzero(result, sizeof(result));

973 create_sweep(result[0], pixelRow, pixelCol, 1);

974 }

975

976 static void test_horz() {

977 const int pixelRow = 100;

978 const int pixelCol = 100;

979 uint8_t result[pixelRow][pixelCol];

980 sk_bzero(result, sizeof(result));

981 create_horz(result[0], pixelRow, pixelCol);

982 }

983

984 static void test_vert() {

985 const int pixelRow = 100;

986 const int pixelCol = 100;

987 uint8_t result[pixelRow][pixelCol];

988 sk_bzero(result, sizeof(result));

989 create_vert(result[0], pixelRow, pixelCol);

990 }

991

992 static void test_angle(SkScalar angle) {

993 const int pixelRow = 150;

994 const int pixelCol = 150;

995 uint8_t result[pixelRow][pixelCol];

996 sk_bzero(result, sizeof(result));

997 create_angle(result[0], pixelRow, pixelCol, angle);

998 }

999

1000 #include "SkBitmap.h"

1001

1002 void CreateSweep(SkBitmap* sweep, SkScalar rectWidth) {

1003 const int pixelRow = 100;

1004 const int pixelCol = 100;

1005 sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow);

1006 sweep->allocPixels();

1007 sweep->eraseColor(SK_ColorTRANSPARENT);

1008 sweep->lockPixels();

1009 void* pixels = sweep->getPixels();

1010 create_sweep((uint8_t*) pixels, pixelRow, pixelCol, rectWidth);

1011 sweep->unlockPixels();

1012 }

1013

1014 void CreateHorz(SkBitmap* sweep) {

1015 const int pixelRow = 100;

1016 const int pixelCol = 100;

1017 sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow);

1018 sweep->allocPixels();

1019 sweep->eraseColor(SK_ColorTRANSPARENT);

1020 sweep->lockPixels();

1021 void* pixels = sweep->getPixels();

1022 create_horz((uint8_t*) pixels, pixelRow, pixelCol);

1023 sweep->unlockPixels();

1024 }

1025

1026 void CreateVert(SkBitmap* sweep) {

1027 const int pixelRow = 100;

1028 const int pixelCol = 100;

1029 sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow);

1030 sweep->allocPixels();

1031 sweep->eraseColor(SK_ColorTRANSPARENT);

1032 sweep->lockPixels();

1033 void* pixels = sweep->getPixels();

1034 create_vert((uint8_t*) pixels, pixelRow, pixelCol);

1035 sweep->unlockPixels();

1036 }

1037

1038 void CreateAngle(SkBitmap* sweep, SkScalar angle) {

1039 const int pixelRow = 150;

1040 const int pixelCol = 150;

1041 sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow);

1042 sweep->allocPixels();

1043 sweep->eraseColor(SK_ColorTRANSPARENT);

1044 sweep->lockPixels();

1045 void* pixels = sweep->getPixels();

1046 create_angle((uint8_t*) pixels, pixelRow, pixelCol, angle);

1047 sweep->unlockPixels();

1048 }

1049

1050 #include "SkCanvas.h"

1051

1052 static void testPng() {

1053 SkBitmap device;

1054 device.setConfig(SkBitmap::kARGB_8888_Config, 4, 4);

1055 device.allocPixels();

1056 device.eraseColor(0xFFFFFFFF);

1057

1058 SkCanvas canvas(device);

1059 canvas.drawARGB(167, 0, 0, 0);

1060

1061 device.lockPixels();

1062 unsigned char* pixels = (unsigned char*) device.getPixels();

1063 SkDebugf("%02x%02x%02x%02x", pixels[3], pixels[2], pixels[1], pixels[0]);

1064 }

1065

1066 void SkAntiEdge_Test() {

1067 testPng();

1068 test_arbitrary_3_by_3();

1069 test_angle(12);

1070 #if 0

1071 test3by3_test = 18;

1072 #else

1073 test3by3_test = -1;

1074 #endif

1075 #if 0

1076 testsweep_test = 7 * 12;

1077 #else

1078 testsweep_test = -1;

1079 #endif

1080 if (testsweep_test == -1) {

1081 test_3_by_3();

1082 }

1083 test_sweep();

1084 test_horz();

1085 test_vert();

1086 }

OLD	NEW

« no previous file with comments | « experimental/Intersection/SkAntiEdge.h ('k') | experimental/Intersection/TSearch.h » ('j') | no next file with comments »