1 /* 2 * Copyright 2015 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 "GrAAConvexTessellator.h" 9 #include "SkCanvas.h" 10 #include "SkPath.h" 11 #include "SkPoint.h" 12 #include "SkString.h" 13 14 // Next steps: 15 // use in AAConvexPathRenderer 16 // add an interactive sample app slide 17 // add debug check that all points are suitably far apart 18 // test more degenerate cases 19 20 // The tolerance for fusing vertices and eliminating colinear lines (It is in device space). 21 static const SkScalar kClose = (SK_Scalar1 / 16); 22 static const SkScalar kCloseSqd = SkScalarMul(kClose, kClose); 23 24 static SkScalar intersect(const SkPoint& p0, const SkPoint& n0, 25 const SkPoint& p1, const SkPoint& n1) { 26 const SkPoint v = p1 - p0; 27 28 SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX; 29 return (v.fX * n1.fY - v.fY * n1.fX) / perpDot; 30 } 31 32 // This is a special case version of intersect where we have the vector 33 // perpendicular to the second line rather than the vector parallel to it. 34 static SkScalar perp_intersect(const SkPoint& p0, const SkPoint& n0, 35 const SkPoint& p1, const SkPoint& perp) { 36 const SkPoint v = p1 - p0; 37 SkScalar perpDot = n0.dot(perp); 38 return v.dot(perp) / perpDot; 39 } 40 41 static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) { 42 SkScalar distSq = p0.distanceToSqd(p1); 43 return distSq < kCloseSqd; 44 } 45 46 static SkScalar abs_dist_from_line(const SkPoint& p0, const SkVector& v, const SkPoint& test) { 47 SkPoint testV = test - p0; 48 SkScalar dist = testV.fX * v.fY - testV.fY * v.fX; 49 return SkScalarAbs(dist); 50 } 51 52 int GrAAConvexTessellator::addPt(const SkPoint& pt, 53 SkScalar depth, 54 bool movable) { 55 this->validate(); 56 57 int index = fPts.count(); 58 *fPts.push() = pt; 59 *fDepths.push() = depth; 60 *fMovable.push() = movable; 61 62 this->validate(); 63 return index; 64 } 65 66 void GrAAConvexTessellator::popLastPt() { 67 this->validate(); 68 69 fPts.pop(); 70 fDepths.pop(); 71 fMovable.pop(); 72 73 this->validate(); 74 } 75 76 void GrAAConvexTessellator::popFirstPtShuffle() { 77 this->validate(); 78 79 fPts.removeShuffle(0); 80 fDepths.removeShuffle(0); 81 fMovable.removeShuffle(0); 82 83 this->validate(); 84 } 85 86 void GrAAConvexTessellator::updatePt(int index, 87 const SkPoint& pt, 88 SkScalar depth) { 89 this->validate(); 90 SkASSERT(fMovable[index]); 91 92 fPts[index] = pt; 93 fDepths[index] = depth; 94 } 95 96 void GrAAConvexTessellator::addTri(int i0, int i1, int i2) { 97 if (i0 == i1 || i1 == i2 || i2 == i0) { 98 return; 99 } 100 101 *fIndices.push() = i0; 102 *fIndices.push() = i1; 103 *fIndices.push() = i2; 104 } 105 106 void GrAAConvexTessellator::rewind() { 107 fPts.rewind(); 108 fDepths.rewind(); 109 fMovable.rewind(); 110 fIndices.rewind(); 111 fNorms.rewind(); 112 fInitialRing.rewind(); 113 fCandidateVerts.rewind(); 114 #if GR_AA_CONVEX_TESSELLATOR_VIZ 115 fRings.rewind(); // TODO: leak in this case! 116 #else 117 fRings[0].rewind(); 118 fRings[1].rewind(); 119 #endif 120 } 121 122 void GrAAConvexTessellator::computeBisectors() { 123 fBisectors.setCount(fNorms.count()); 124 125 int prev = fBisectors.count() - 1; 126 for (int cur = 0; cur < fBisectors.count(); prev = cur, ++cur) { 127 fBisectors[cur] = fNorms[cur] + fNorms[prev]; 128 fBisectors[cur].normalize(); 129 fBisectors[cur].negate(); // make the bisector face in 130 131 SkASSERT(SkScalarNearlyEqual(1.0f, fBisectors[cur].length())); 132 } 133 } 134 135 // The general idea here is to, conceptually, start with the original polygon and slide 136 // the vertices along the bisectors until the first intersection. At that 137 // point two of the edges collapse and the process repeats on the new polygon. 138 // The polygon state is captured in the Ring class while the GrAAConvexTessellator 139 // controls the iteration. The CandidateVerts holds the formative points for the 140 // next ring. 141 bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) { 142 static const int kMaxNumRings = 8; 143 144 SkDEBUGCODE(fShouldCheckDepths = true;) 145 146 if (!this->extractFromPath(m, path)) { 147 return false; 148 } 149 150 this->createOuterRing(); 151 152 // the bisectors are only needed for the computation of the outer ring 153 fBisectors.rewind(); 154 155 Ring* lastRing = &fInitialRing; 156 int i; 157 for (i = 0; i < kMaxNumRings; ++i) { 158 Ring* nextRing = this->getNextRing(lastRing); 159 160 if (this->createInsetRing(*lastRing, nextRing)) { 161 break; 162 } 163 164 nextRing->init(*this); 165 lastRing = nextRing; 166 } 167 168 if (kMaxNumRings == i) { 169 // If we've exceeded the amount of time we want to throw at this, set 170 // the depth of all points in the final ring to 'fTargetDepth' and 171 // create a fan. 172 this->terminate(*lastRing); 173 SkDEBUGCODE(fShouldCheckDepths = false;) 174 } 175 176 #ifdef SK_DEBUG 177 this->validate(); 178 if (fShouldCheckDepths) { 179 SkDEBUGCODE(this->checkAllDepths();) 180 } 181 #endif 182 return true; 183 } 184 185 SkScalar GrAAConvexTessellator::computeDepthFromEdge(int edgeIdx, const SkPoint& p) const { 186 SkASSERT(edgeIdx < fNorms.count()); 187 188 SkPoint v = p - fPts[edgeIdx]; 189 SkScalar depth = -fNorms[edgeIdx].dot(v); 190 SkASSERT(depth >= 0.0f); 191 return depth; 192 } 193 194 // Find a point that is 'desiredDepth' away from the 'edgeIdx'-th edge and lies 195 // along the 'bisector' from the 'startIdx'-th point. 196 bool GrAAConvexTessellator::computePtAlongBisector(int startIdx, 197 const SkVector& bisector, 198 int edgeIdx, 199 SkScalar desiredDepth, 200 SkPoint* result) const { 201 const SkPoint& norm = fNorms[edgeIdx]; 202 203 // First find the point where the edge and the bisector intersect 204 SkPoint newP; 205 SkScalar t = perp_intersect(fPts[startIdx], bisector, fPts[edgeIdx], norm); 206 if (SkScalarNearlyEqual(t, 0.0f)) { 207 // the start point was one of the original ring points 208 SkASSERT(startIdx < fNorms.count()); 209 newP = fPts[startIdx]; 210 } else if (t > 0.0f) { 211 SkASSERT(t < 0.0f); 212 newP = bisector; 213 newP.scale(t); 214 newP += fPts[startIdx]; 215 } else { 216 return false; 217 } 218 219 // Then offset along the bisector from that point the correct distance 220 t = -desiredDepth / bisector.dot(norm); 221 SkASSERT(t > 0.0f); 222 *result = bisector; 223 result->scale(t); 224 *result += newP; 225 226 227 return true; 228 } 229 230 bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) { 231 SkASSERT(SkPath::kLine_SegmentMask == path.getSegmentMasks()); 232 SkASSERT(SkPath::kConvex_Convexity == path.getConvexity()); 233 234 // Outer ring: 3*numPts 235 // Middle ring: numPts 236 // Presumptive inner ring: numPts 237 this->reservePts(5*path.countPoints()); 238 // Outer ring: 12*numPts 239 // Middle ring: 0 240 // Presumptive inner ring: 6*numPts + 6 241 fIndices.setReserve(18*path.countPoints() + 6); 242 243 fNorms.setReserve(path.countPoints()); 244 245 SkScalar minCross = SK_ScalarMax, maxCross = -SK_ScalarMax; 246 247 // TODO: is there a faster way to extract the points from the path? Perhaps 248 // get all the points via a new entry point, transform them all in bulk 249 // and then walk them to find duplicates? 250 SkPath::Iter iter(path, true); 251 SkPoint pts[4]; 252 SkPath::Verb verb; 253 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 254 switch (verb) { 255 case SkPath::kLine_Verb: 256 m.mapPoints(&pts[1], 1); 257 if (this->numPts() > 0 && duplicate_pt(pts[1], this->lastPoint())) { 258 continue; 259 } 260 261 SkASSERT(fPts.count() <= 1 || fPts.count() == fNorms.count()+1); 262 if (this->numPts() >= 2 && 263 abs_dist_from_line(fPts.top(), fNorms.top(), pts[1]) < kClose) { 264 // The old last point is on the line from the second to last to the new point 265 this->popLastPt(); 266 fNorms.pop(); 267 } 268 269 this->addPt(pts[1], 0.0f, false); 270 if (this->numPts() > 1) { 271 *fNorms.push() = fPts.top() - fPts[fPts.count()-2]; 272 SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top()); 273 SkASSERT(len > 0.0f); 274 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms.top().length())); 275 } 276 277 if (this->numPts() >= 3) { 278 int cur = this->numPts()-1; 279 SkScalar cross = SkPoint::CrossProduct(fNorms[cur-1], fNorms[cur-2]); 280 maxCross = SkTMax(maxCross, cross); 281 minCross = SkTMin(minCross, cross); 282 } 283 break; 284 case SkPath::kQuad_Verb: 285 case SkPath::kConic_Verb: 286 case SkPath::kCubic_Verb: 287 SkASSERT(false); 288 break; 289 case SkPath::kMove_Verb: 290 case SkPath::kClose_Verb: 291 case SkPath::kDone_Verb: 292 break; 293 } 294 } 295 296 if (this->numPts() < 3) { 297 return false; 298 } 299 300 // check if last point is a duplicate of the first point. If so, remove it. 301 if (duplicate_pt(fPts[this->numPts()-1], fPts[0])) { 302 this->popLastPt(); 303 fNorms.pop(); 304 } 305 306 SkASSERT(fPts.count() == fNorms.count()+1); 307 if (this->numPts() >= 3 && 308 abs_dist_from_line(fPts.top(), fNorms.top(), fPts[0]) < kClose) { 309 // The last point is on the line from the second to last to the first point. 310 this->popLastPt(); 311 fNorms.pop(); 312 } 313 314 if (this->numPts() < 3) { 315 return false; 316 } 317 318 *fNorms.push() = fPts[0] - fPts.top(); 319 SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top()); 320 SkASSERT(len > 0.0f); 321 SkASSERT(fPts.count() == fNorms.count()); 322 323 if (abs_dist_from_line(fPts[0], fNorms.top(), fPts[1]) < kClose) { 324 // The first point is on the line from the last to the second. 325 this->popFirstPtShuffle(); 326 fNorms.removeShuffle(0); 327 fNorms[0] = fPts[1] - fPts[0]; 328 SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms[0]); 329 SkASSERT(len > 0.0f); 330 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[0].length())); 331 } 332 333 if (this->numPts() < 3) { 334 return false; 335 } 336 337 // Check the cross produce of the final trio 338 SkScalar cross = SkPoint::CrossProduct(fNorms[0], fNorms.top()); 339 maxCross = SkTMax(maxCross, cross); 340 minCross = SkTMin(minCross, cross); 341 342 if (maxCross > 0.0f) { 343 SkASSERT(minCross >= 0.0f); 344 fSide = SkPoint::kRight_Side; 345 } else { 346 SkASSERT(minCross <= 0.0f); 347 fSide = SkPoint::kLeft_Side; 348 } 349 350 // Make all the normals face outwards rather than along the edge 351 for (int cur = 0; cur < fNorms.count(); ++cur) { 352 fNorms[cur].setOrthog(fNorms[cur], fSide); 353 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length())); 354 } 355 356 this->computeBisectors(); 357 358 fCandidateVerts.setReserve(this->numPts()); 359 fInitialRing.setReserve(this->numPts()); 360 for (int i = 0; i < this->numPts(); ++i) { 361 fInitialRing.addIdx(i, i); 362 } 363 fInitialRing.init(fNorms, fBisectors); 364 365 this->validate(); 366 return true; 367 } 368 369 GrAAConvexTessellator::Ring* GrAAConvexTessellator::getNextRing(Ring* lastRing) { 370 #if GR_AA_CONVEX_TESSELLATOR_VIZ 371 Ring* ring = *fRings.push() = SkNEW(Ring); 372 ring->setReserve(fInitialRing.numPts()); 373 ring->rewind(); 374 return ring; 375 #else 376 // Flip flop back and forth between fRings[0] & fRings[1] 377 int nextRing = (lastRing == &fRings[0]) ? 1 : 0; 378 fRings[nextRing].setReserve(fInitialRing.numPts()); 379 fRings[nextRing].rewind(); 380 return &fRings[nextRing]; 381 #endif 382 } 383 384 void GrAAConvexTessellator::fanRing(const Ring& ring) { 385 // fan out from point 0 386 for (int cur = 1; cur < ring.numPts()-1; ++cur) { 387 this->addTri(ring.index(0), ring.index(cur), ring.index(cur+1)); 388 } 389 } 390 391 void GrAAConvexTessellator::createOuterRing() { 392 // For now, we're only generating one outer ring (at the start). This 393 // could be relaxed for stroking use cases. 394 SkASSERT(0 == fIndices.count()); 395 SkASSERT(fPts.count() == fNorms.count()); 396 397 const int numPts = fPts.count(); 398 399 // For each vertex of the original polygon we add three points to the 400 // outset polygon - one extending perpendicular to each impinging edge 401 // and one along the bisector. Two triangles are added for each corner 402 // and two are added along each edge. 403 int prev = numPts - 1; 404 int lastPerpIdx = -1, firstPerpIdx = -1, newIdx0, newIdx1, newIdx2; 405 for (int cur = 0; cur < numPts; ++cur) { 406 // The perpendicular point for the last edge 407 SkPoint temp = fNorms[prev]; 408 temp.scale(fTargetDepth); 409 temp += fPts[cur]; 410 411 // We know it isn't a duplicate of the prior point (since it and this 412 // one are just perpendicular offsets from the non-merged polygon points) 413 newIdx0 = this->addPt(temp, -fTargetDepth, false); 414 415 // The bisector outset point 416 temp = fBisectors[cur]; 417 temp.scale(-fTargetDepth); // the bisectors point in 418 temp += fPts[cur]; 419 420 // For very shallow angles all the corner points could fuse 421 if (duplicate_pt(temp, this->point(newIdx0))) { 422 newIdx1 = newIdx0; 423 } else { 424 newIdx1 = this->addPt(temp, -fTargetDepth, false); 425 } 426 427 // The perpendicular point for the next edge. 428 temp = fNorms[cur]; 429 temp.scale(fTargetDepth); 430 temp += fPts[cur]; 431 432 // For very shallow angles all the corner points could fuse. 433 if (duplicate_pt(temp, this->point(newIdx1))) { 434 newIdx2 = newIdx1; 435 } else { 436 newIdx2 = this->addPt(temp, -fTargetDepth, false); 437 } 438 439 if (0 == cur) { 440 // Store the index of the first perpendicular point to finish up 441 firstPerpIdx = newIdx0; 442 SkASSERT(-1 == lastPerpIdx); 443 } else { 444 // The triangles for the previous edge 445 this->addTri(prev, newIdx0, cur); 446 this->addTri(prev, lastPerpIdx, newIdx0); 447 } 448 449 // The two triangles for the corner 450 this->addTri(cur, newIdx0, newIdx1); 451 this->addTri(cur, newIdx1, newIdx2); 452 453 prev = cur; 454 // Track the last perpendicular outset point so we can construct the 455 // trailing edge triangles. 456 lastPerpIdx = newIdx2; 457 } 458 459 // pick up the final edge rect 460 this->addTri(numPts-1, firstPerpIdx, 0); 461 this->addTri(numPts-1, lastPerpIdx, firstPerpIdx); 462 463 this->validate(); 464 } 465 466 // Something went wrong in the creation of the next ring. Mark the last good 467 // ring as being at the desired depth and fan it. 468 void GrAAConvexTessellator::terminate(const Ring& ring) { 469 for (int i = 0; i < ring.numPts(); ++i) { 470 fDepths[ring.index(i)] = fTargetDepth; 471 } 472 473 this->fanRing(ring); 474 } 475 476 // return true when processing is complete 477 bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing) { 478 bool done = false; 479 480 fCandidateVerts.rewind(); 481 482 // Loop through all the points in the ring and find the intersection with the smallest depth 483 SkScalar minDist = SK_ScalarMax, minT = 0.0f; 484 int minEdgeIdx = -1; 485 486 for (int cur = 0; cur < lastRing.numPts(); ++cur) { 487 int next = (cur + 1) % lastRing.numPts(); 488 489 SkScalar t = intersect(this->point(lastRing.index(cur)), lastRing.bisector(cur), 490 this->point(lastRing.index(next)), lastRing.bisector(next)); 491 SkScalar dist = -t * lastRing.norm(cur).dot(lastRing.bisector(cur)); 492 493 if (minDist > dist) { 494 minDist = dist; 495 minT = t; 496 minEdgeIdx = cur; 497 } 498 } 499 500 SkPoint newPt = lastRing.bisector(minEdgeIdx); 501 newPt.scale(minT); 502 newPt += this->point(lastRing.index(minEdgeIdx)); 503 504 SkScalar depth = this->computeDepthFromEdge(lastRing.origEdgeID(minEdgeIdx), newPt); 505 if (depth >= fTargetDepth) { 506 // None of the bisectors intersect before reaching the desired depth. 507 // Just step them all to the desired depth 508 depth = fTargetDepth; 509 done = true; 510 } 511 512 // 'dst' stores where each point in the last ring maps to/transforms into 513 // in the next ring. 514 SkTDArray<int> dst; 515 dst.setCount(lastRing.numPts()); 516 517 // Create the first point (who compares with no one) 518 if (!this->computePtAlongBisector(lastRing.index(0), 519 lastRing.bisector(0), 520 lastRing.origEdgeID(0), 521 depth, &newPt)) { 522 this->terminate(lastRing); 523 SkDEBUGCODE(fShouldCheckDepths = false;) 524 return true; 525 } 526 dst[0] = fCandidateVerts.addNewPt(newPt, 527 lastRing.index(0), lastRing.origEdgeID(0), 528 !this->movable(lastRing.index(0))); 529 530 // Handle the middle points (who only compare with the prior point) 531 for (int cur = 1; cur < lastRing.numPts()-1; ++cur) { 532 if (!this->computePtAlongBisector(lastRing.index(cur), 533 lastRing.bisector(cur), 534 lastRing.origEdgeID(cur), 535 depth, &newPt)) { 536 this->terminate(lastRing); 537 SkDEBUGCODE(fShouldCheckDepths = false;) 538 return true; 539 } 540 if (!duplicate_pt(newPt, fCandidateVerts.lastPoint())) { 541 dst[cur] = fCandidateVerts.addNewPt(newPt, 542 lastRing.index(cur), lastRing.origEdgeID(cur), 543 !this->movable(lastRing.index(cur))); 544 } else { 545 dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur)); 546 } 547 } 548 549 // Check on the last point (handling the wrap around) 550 int cur = lastRing.numPts()-1; 551 if (!this->computePtAlongBisector(lastRing.index(cur), 552 lastRing.bisector(cur), 553 lastRing.origEdgeID(cur), 554 depth, &newPt)) { 555 this->terminate(lastRing); 556 SkDEBUGCODE(fShouldCheckDepths = false;) 557 return true; 558 } 559 bool dupPrev = duplicate_pt(newPt, fCandidateVerts.lastPoint()); 560 bool dupNext = duplicate_pt(newPt, fCandidateVerts.firstPoint()); 561 562 if (!dupPrev && !dupNext) { 563 dst[cur] = fCandidateVerts.addNewPt(newPt, 564 lastRing.index(cur), lastRing.origEdgeID(cur), 565 !this->movable(lastRing.index(cur))); 566 } else if (dupPrev && !dupNext) { 567 dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur)); 568 } else if (!dupPrev && dupNext) { 569 dst[cur] = fCandidateVerts.fuseWithNext(); 570 } else { 571 bool dupPrevVsNext = duplicate_pt(fCandidateVerts.firstPoint(), fCandidateVerts.lastPoint()); 572 573 if (!dupPrevVsNext) { 574 dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur)); 575 } else { 576 dst[cur] = dst[cur-1] = fCandidateVerts.fuseWithBoth(); 577 } 578 } 579 580 // Fold the new ring's points into the global pool 581 for (int i = 0; i < fCandidateVerts.numPts(); ++i) { 582 int newIdx; 583 if (fCandidateVerts.needsToBeNew(i)) { 584 // if the originating index is still valid then this point wasn't 585 // fused (and is thus movable) 586 newIdx = this->addPt(fCandidateVerts.point(i), depth, 587 fCandidateVerts.originatingIdx(i) != -1); 588 } else { 589 SkASSERT(fCandidateVerts.originatingIdx(i) != -1); 590 this->updatePt(fCandidateVerts.originatingIdx(i), fCandidateVerts.point(i), depth); 591 newIdx = fCandidateVerts.originatingIdx(i); 592 } 593 594 nextRing->addIdx(newIdx, fCandidateVerts.origEdge(i)); 595 } 596 597 // 'dst' currently has indices into the ring. Remap these to be indices 598 // into the global pool since the triangulation operates in that space. 599 for (int i = 0; i < dst.count(); ++i) { 600 dst[i] = nextRing->index(dst[i]); 601 } 602 603 for (int cur = 0; cur < lastRing.numPts(); ++cur) { 604 int next = (cur + 1) % lastRing.numPts(); 605 606 this->addTri(lastRing.index(cur), lastRing.index(next), dst[next]); 607 this->addTri(lastRing.index(cur), dst[next], dst[cur]); 608 } 609 610 if (done) { 611 this->fanRing(*nextRing); 612 } 613 614 if (nextRing->numPts() < 3) { 615 done = true; 616 } 617 618 return done; 619 } 620 621 void GrAAConvexTessellator::validate() const { 622 SkASSERT(fPts.count() == fDepths.count()); 623 SkASSERT(fPts.count() == fMovable.count()); 624 SkASSERT(0 == (fIndices.count() % 3)); 625 } 626 627 ////////////////////////////////////////////////////////////////////////////// 628 void GrAAConvexTessellator::Ring::init(const GrAAConvexTessellator& tess) { 629 this->computeNormals(tess); 630 this->computeBisectors(); 631 SkASSERT(this->isConvex(tess)); 632 } 633 634 void GrAAConvexTessellator::Ring::init(const SkTDArray<SkVector>& norms, 635 const SkTDArray<SkVector>& bisectors) { 636 for (int i = 0; i < fPts.count(); ++i) { 637 fPts[i].fNorm = norms[i]; 638 fPts[i].fBisector = bisectors[i]; 639 } 640 } 641 642 // Compute the outward facing normal at each vertex. 643 void GrAAConvexTessellator::Ring::computeNormals(const GrAAConvexTessellator& tess) { 644 for (int cur = 0; cur < fPts.count(); ++cur) { 645 int next = (cur + 1) % fPts.count(); 646 647 fPts[cur].fNorm = tess.point(fPts[next].fIndex) - tess.point(fPts[cur].fIndex); 648 SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fPts[cur].fNorm); 649 SkASSERT(len > 0.0f); 650 fPts[cur].fNorm.setOrthog(fPts[cur].fNorm, tess.side()); 651 652 SkASSERT(SkScalarNearlyEqual(1.0f, fPts[cur].fNorm.length())); 653 } 654 } 655 656 void GrAAConvexTessellator::Ring::computeBisectors() { 657 int prev = fPts.count() - 1; 658 for (int cur = 0; cur < fPts.count(); prev = cur, ++cur) { 659 fPts[cur].fBisector = fPts[cur].fNorm + fPts[prev].fNorm; 660 fPts[cur].fBisector.normalize(); 661 fPts[cur].fBisector.negate(); // make the bisector face in 662 663 SkASSERT(SkScalarNearlyEqual(1.0f, fPts[cur].fBisector.length())); 664 } 665 } 666 667 ////////////////////////////////////////////////////////////////////////////// 668 #ifdef SK_DEBUG 669 // Is this ring convex? 670 bool GrAAConvexTessellator::Ring::isConvex(const GrAAConvexTessellator& tess) const { 671 if (fPts.count() < 3) { 672 return false; 673 } 674 675 SkPoint prev = tess.point(fPts[0].fIndex) - tess.point(fPts.top().fIndex); 676 SkPoint cur = tess.point(fPts[1].fIndex) - tess.point(fPts[0].fIndex); 677 SkScalar minDot = prev.fX * cur.fY - prev.fY * cur.fX; 678 SkScalar maxDot = minDot; 679 680 prev = cur; 681 for (int i = 1; i < fPts.count(); ++i) { 682 int next = (i + 1) % fPts.count(); 683 684 cur = tess.point(fPts[next].fIndex) - tess.point(fPts[i].fIndex); 685 SkScalar dot = prev.fX * cur.fY - prev.fY * cur.fX; 686 687 minDot = SkMinScalar(minDot, dot); 688 maxDot = SkMaxScalar(maxDot, dot); 689 690 prev = cur; 691 } 692 693 return (maxDot > 0.0f) == (minDot >= 0.0f); 694 } 695 696 static SkScalar capsule_depth(const SkPoint& p0, const SkPoint& p1, 697 const SkPoint& test, SkPoint::Side side, 698 int* sign) { 699 *sign = -1; 700 SkPoint edge = p1 - p0; 701 SkScalar len = SkPoint::Normalize(&edge); 702 703 SkPoint testVec = test - p0; 704 705 SkScalar d0 = edge.dot(testVec); 706 if (d0 < 0.0f) { 707 return SkPoint::Distance(p0, test); 708 } 709 if (d0 > len) { 710 return SkPoint::Distance(p1, test); 711 } 712 713 SkScalar perpDist = testVec.fY * edge.fX - testVec.fX * edge.fY; 714 if (SkPoint::kRight_Side == side) { 715 perpDist = -perpDist; 716 } 717 718 if (perpDist < 0.0f) { 719 perpDist = -perpDist; 720 } else { 721 *sign = 1; 722 } 723 return perpDist; 724 } 725 726 SkScalar GrAAConvexTessellator::computeRealDepth(const SkPoint& p) const { 727 SkScalar minDist = SK_ScalarMax; 728 int closestSign, sign; 729 730 for (int edge = 0; edge < fNorms.count(); ++edge) { 731 SkScalar dist = capsule_depth(this->point(edge), 732 this->point((edge+1) % fNorms.count()), 733 p, fSide, &sign); 734 SkASSERT(dist >= 0.0f); 735 736 if (minDist > dist) { 737 minDist = dist; 738 closestSign = sign; 739 } 740 } 741 742 return closestSign * minDist; 743 } 744 745 // Verify that the incrementally computed depths are close to the actual depths. 746 void GrAAConvexTessellator::checkAllDepths() const { 747 for (int cur = 0; cur < this->numPts(); ++cur) { 748 SkScalar realDepth = this->computeRealDepth(this->point(cur)); 749 SkScalar computedDepth = this->depth(cur); 750 SkASSERT(SkScalarNearlyEqual(realDepth, computedDepth, 0.01f)); 751 } 752 } 753 #endif 754 755 ////////////////////////////////////////////////////////////////////////////// 756 #if GR_AA_CONVEX_TESSELLATOR_VIZ 757 static const SkScalar kPointRadius = 0.02f; 758 static const SkScalar kArrowStrokeWidth = 0.0f; 759 static const SkScalar kArrowLength = 0.2f; 760 static const SkScalar kEdgeTextSize = 0.1f; 761 static const SkScalar kPointTextSize = 0.02f; 762 763 static void draw_point(SkCanvas* canvas, const SkPoint& p, SkScalar paramValue, bool stroke) { 764 SkPaint paint; 765 SkASSERT(paramValue <= 1.0f); 766 int gs = int(255*paramValue); 767 paint.setARGB(255, gs, gs, gs); 768 769 canvas->drawCircle(p.fX, p.fY, kPointRadius, paint); 770 771 if (stroke) { 772 SkPaint stroke; 773 stroke.setColor(SK_ColorYELLOW); 774 stroke.setStyle(SkPaint::kStroke_Style); 775 stroke.setStrokeWidth(kPointRadius/3.0f); 776 canvas->drawCircle(p.fX, p.fY, kPointRadius, stroke); 777 } 778 } 779 780 static void draw_line(SkCanvas* canvas, const SkPoint& p0, const SkPoint& p1, SkColor color) { 781 SkPaint p; 782 p.setColor(color); 783 784 canvas->drawLine(p0.fX, p0.fY, p1.fX, p1.fY, p); 785 } 786 787 static void draw_arrow(SkCanvas*canvas, const SkPoint& p, const SkPoint &n, 788 SkScalar len, SkColor color) { 789 SkPaint paint; 790 paint.setColor(color); 791 paint.setStrokeWidth(kArrowStrokeWidth); 792 paint.setStyle(SkPaint::kStroke_Style); 793 794 canvas->drawLine(p.fX, p.fY, 795 p.fX + len * n.fX, p.fY + len * n.fY, 796 paint); 797 } 798 799 void GrAAConvexTessellator::Ring::draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const { 800 SkPaint paint; 801 paint.setTextSize(kEdgeTextSize); 802 803 for (int cur = 0; cur < fPts.count(); ++cur) { 804 int next = (cur + 1) % fPts.count(); 805 806 draw_line(canvas, 807 tess.point(fPts[cur].fIndex), 808 tess.point(fPts[next].fIndex), 809 SK_ColorGREEN); 810 811 SkPoint mid = tess.point(fPts[cur].fIndex) + tess.point(fPts[next].fIndex); 812 mid.scale(0.5f); 813 814 if (fPts.count()) { 815 draw_arrow(canvas, mid, fPts[cur].fNorm, kArrowLength, SK_ColorRED); 816 mid.fX += (kArrowLength/2) * fPts[cur].fNorm.fX; 817 mid.fY += (kArrowLength/2) * fPts[cur].fNorm.fY; 818 } 819 820 SkString num; 821 num.printf("%d", this->origEdgeID(cur)); 822 canvas->drawText(num.c_str(), num.size(), mid.fX, mid.fY, paint); 823 824 if (fPts.count()) { 825 draw_arrow(canvas, tess.point(fPts[cur].fIndex), fPts[cur].fBisector, 826 kArrowLength, SK_ColorBLUE); 827 } 828 } 829 } 830 831 void GrAAConvexTessellator::draw(SkCanvas* canvas) const { 832 for (int i = 0; i < fIndices.count(); i += 3) { 833 SkASSERT(fIndices[i] < this->numPts()) ; 834 SkASSERT(fIndices[i+1] < this->numPts()) ; 835 SkASSERT(fIndices[i+2] < this->numPts()) ; 836 837 draw_line(canvas, 838 this->point(this->fIndices[i]), this->point(this->fIndices[i+1]), 839 SK_ColorBLACK); 840 draw_line(canvas, 841 this->point(this->fIndices[i+1]), this->point(this->fIndices[i+2]), 842 SK_ColorBLACK); 843 draw_line(canvas, 844 this->point(this->fIndices[i+2]), this->point(this->fIndices[i]), 845 SK_ColorBLACK); 846 } 847 848 fInitialRing.draw(canvas, *this); 849 for (int i = 0; i < fRings.count(); ++i) { 850 fRings[i]->draw(canvas, *this); 851 } 852 853 for (int i = 0; i < this->numPts(); ++i) { 854 draw_point(canvas, 855 this->point(i), 0.5f + (this->depth(i)/(2*fTargetDepth)), 856 !this->movable(i)); 857 858 SkPaint paint; 859 paint.setTextSize(kPointTextSize); 860 paint.setTextAlign(SkPaint::kCenter_Align); 861 if (this->depth(i) <= -fTargetDepth) { 862 paint.setColor(SK_ColorWHITE); 863 } 864 865 SkString num; 866 num.printf("%d", i); 867 canvas->drawText(num.c_str(), num.size(), 868 this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f), 869 paint); 870 } 871 } 872 873 #endif 874 875