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 #include "GrPathUtils.h" 14 15 // Next steps: 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 = kClose * kClose; 23 24 // tesselation tolerance values, in device space pixels 25 static const SkScalar kQuadTolerance = 0.2f; 26 static const SkScalar kCubicTolerance = 0.2f; 27 static const SkScalar kConicTolerance = 0.5f; 28 29 // dot product below which we use a round cap between curve segments 30 static const SkScalar kRoundCapThreshold = 0.8f; 31 32 // dot product above which we consider two adjacent curves to be part of the "same" curve 33 static const SkScalar kCurveConnectionThreshold = 0.8f; 34 35 static bool intersect(const SkPoint& p0, const SkPoint& n0, 36 const SkPoint& p1, const SkPoint& n1, 37 SkScalar* t) { 38 const SkPoint v = p1 - p0; 39 SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX; 40 if (SkScalarNearlyZero(perpDot)) { 41 return false; 42 } 43 *t = (v.fX * n1.fY - v.fY * n1.fX) / perpDot; 44 SkASSERT(SkScalarIsFinite(*t)); 45 return true; 46 } 47 48 // This is a special case version of intersect where we have the vector 49 // perpendicular to the second line rather than the vector parallel to it. 50 static SkScalar perp_intersect(const SkPoint& p0, const SkPoint& n0, 51 const SkPoint& p1, const SkPoint& perp) { 52 const SkPoint v = p1 - p0; 53 SkScalar perpDot = n0.dot(perp); 54 return v.dot(perp) / perpDot; 55 } 56 57 static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) { 58 SkScalar distSq = SkPointPriv::DistanceToSqd(p0, p1); 59 return distSq < kCloseSqd; 60 } 61 62 static SkScalar abs_dist_from_line(const SkPoint& p0, const SkVector& v, const SkPoint& test) { 63 SkPoint testV = test - p0; 64 SkScalar dist = testV.fX * v.fY - testV.fY * v.fX; 65 return SkScalarAbs(dist); 66 } 67 68 int GrAAConvexTessellator::addPt(const SkPoint& pt, 69 SkScalar depth, 70 SkScalar coverage, 71 bool movable, 72 CurveState curve) { 73 this->validate(); 74 75 int index = fPts.count(); 76 *fPts.push() = pt; 77 *fCoverages.push() = coverage; 78 *fMovable.push() = movable; 79 *fCurveState.push() = curve; 80 81 this->validate(); 82 return index; 83 } 84 85 void GrAAConvexTessellator::popLastPt() { 86 this->validate(); 87 88 fPts.pop(); 89 fCoverages.pop(); 90 fMovable.pop(); 91 fCurveState.pop(); 92 93 this->validate(); 94 } 95 96 void GrAAConvexTessellator::popFirstPtShuffle() { 97 this->validate(); 98 99 fPts.removeShuffle(0); 100 fCoverages.removeShuffle(0); 101 fMovable.removeShuffle(0); 102 fCurveState.removeShuffle(0); 103 104 this->validate(); 105 } 106 107 void GrAAConvexTessellator::updatePt(int index, 108 const SkPoint& pt, 109 SkScalar depth, 110 SkScalar coverage) { 111 this->validate(); 112 SkASSERT(fMovable[index]); 113 114 fPts[index] = pt; 115 fCoverages[index] = coverage; 116 } 117 118 void GrAAConvexTessellator::addTri(int i0, int i1, int i2) { 119 if (i0 == i1 || i1 == i2 || i2 == i0) { 120 return; 121 } 122 123 *fIndices.push() = i0; 124 *fIndices.push() = i1; 125 *fIndices.push() = i2; 126 } 127 128 void GrAAConvexTessellator::rewind() { 129 fPts.rewind(); 130 fCoverages.rewind(); 131 fMovable.rewind(); 132 fIndices.rewind(); 133 fNorms.rewind(); 134 fCurveState.rewind(); 135 fInitialRing.rewind(); 136 fCandidateVerts.rewind(); 137 #if GR_AA_CONVEX_TESSELLATOR_VIZ 138 fRings.rewind(); // TODO: leak in this case! 139 #else 140 fRings[0].rewind(); 141 fRings[1].rewind(); 142 #endif 143 } 144 145 void GrAAConvexTessellator::computeBisectors() { 146 fBisectors.setCount(fNorms.count()); 147 148 int prev = fBisectors.count() - 1; 149 for (int cur = 0; cur < fBisectors.count(); prev = cur, ++cur) { 150 fBisectors[cur] = fNorms[cur] + fNorms[prev]; 151 if (!fBisectors[cur].normalize()) { 152 SkASSERT(SkPointPriv::kLeft_Side == fSide || SkPointPriv::kRight_Side == fSide); 153 SkPointPriv::SetOrthog(&fBisectors[cur], fNorms[cur], (SkPointPriv::Side)-fSide); 154 SkVector other; 155 SkPointPriv::SetOrthog(&other, fNorms[prev], fSide); 156 fBisectors[cur] += other; 157 SkAssertResult(fBisectors[cur].normalize()); 158 } else { 159 fBisectors[cur].negate(); // make the bisector face in 160 } 161 if (fCurveState[prev] == kIndeterminate_CurveState) { 162 if (fCurveState[cur] == kSharp_CurveState) { 163 fCurveState[prev] = kSharp_CurveState; 164 } else { 165 if (SkScalarAbs(fNorms[cur].dot(fNorms[prev])) > kCurveConnectionThreshold) { 166 fCurveState[prev] = kCurve_CurveState; 167 fCurveState[cur] = kCurve_CurveState; 168 } else { 169 fCurveState[prev] = kSharp_CurveState; 170 fCurveState[cur] = kSharp_CurveState; 171 } 172 } 173 } 174 175 SkASSERT(SkScalarNearlyEqual(1.0f, fBisectors[cur].length())); 176 } 177 } 178 179 // Create as many rings as we need to (up to a predefined limit) to reach the specified target 180 // depth. If we are in fill mode, the final ring will automatically be fanned. 181 bool GrAAConvexTessellator::createInsetRings(Ring& previousRing, SkScalar initialDepth, 182 SkScalar initialCoverage, SkScalar targetDepth, 183 SkScalar targetCoverage, Ring** finalRing) { 184 static const int kMaxNumRings = 8; 185 186 if (previousRing.numPts() < 3) { 187 return false; 188 } 189 Ring* currentRing = &previousRing; 190 int i; 191 for (i = 0; i < kMaxNumRings; ++i) { 192 Ring* nextRing = this->getNextRing(currentRing); 193 SkASSERT(nextRing != currentRing); 194 195 bool done = this->createInsetRing(*currentRing, nextRing, initialDepth, initialCoverage, 196 targetDepth, targetCoverage, i == 0); 197 currentRing = nextRing; 198 if (done) { 199 break; 200 } 201 currentRing->init(*this); 202 } 203 204 if (kMaxNumRings == i) { 205 // Bail if we've exceeded the amount of time we want to throw at this. 206 this->terminate(*currentRing); 207 return false; 208 } 209 bool done = currentRing->numPts() >= 3; 210 if (done) { 211 currentRing->init(*this); 212 } 213 *finalRing = currentRing; 214 return done; 215 } 216 217 // The general idea here is to, conceptually, start with the original polygon and slide 218 // the vertices along the bisectors until the first intersection. At that 219 // point two of the edges collapse and the process repeats on the new polygon. 220 // The polygon state is captured in the Ring class while the GrAAConvexTessellator 221 // controls the iteration. The CandidateVerts holds the formative points for the 222 // next ring. 223 bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) { 224 if (!this->extractFromPath(m, path)) { 225 return false; 226 } 227 228 SkScalar coverage = 1.0f; 229 SkScalar scaleFactor = 0.0f; 230 231 if (SkStrokeRec::kStrokeAndFill_Style == fStyle) { 232 SkASSERT(m.isSimilarity()); 233 scaleFactor = m.getMaxScale(); // x and y scale are the same 234 SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; 235 Ring outerStrokeAndAARing; 236 this->createOuterRing(fInitialRing, 237 effectiveStrokeWidth / 2 + kAntialiasingRadius, 0.0, 238 &outerStrokeAndAARing); 239 240 // discard all the triangles added between the originating ring and the new outer ring 241 fIndices.rewind(); 242 243 outerStrokeAndAARing.init(*this); 244 245 outerStrokeAndAARing.makeOriginalRing(); 246 247 // Add the outer stroke ring's normals to the originating ring's normals 248 // so it can also act as an originating ring 249 fNorms.setCount(fNorms.count() + outerStrokeAndAARing.numPts()); 250 for (int i = 0; i < outerStrokeAndAARing.numPts(); ++i) { 251 SkASSERT(outerStrokeAndAARing.index(i) < fNorms.count()); 252 fNorms[outerStrokeAndAARing.index(i)] = outerStrokeAndAARing.norm(i); 253 } 254 255 // the bisectors are only needed for the computation of the outer ring 256 fBisectors.rewind(); 257 258 Ring* insetAARing; 259 this->createInsetRings(outerStrokeAndAARing, 260 0.0f, 0.0f, 2*kAntialiasingRadius, 1.0f, 261 &insetAARing); 262 263 SkDEBUGCODE(this->validate();) 264 return true; 265 } 266 267 if (SkStrokeRec::kStroke_Style == fStyle) { 268 SkASSERT(fStrokeWidth >= 0.0f); 269 SkASSERT(m.isSimilarity()); 270 scaleFactor = m.getMaxScale(); // x and y scale are the same 271 SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; 272 Ring outerStrokeRing; 273 this->createOuterRing(fInitialRing, effectiveStrokeWidth / 2 - kAntialiasingRadius, 274 coverage, &outerStrokeRing); 275 outerStrokeRing.init(*this); 276 Ring outerAARing; 277 this->createOuterRing(outerStrokeRing, kAntialiasingRadius * 2, 0.0f, &outerAARing); 278 } else { 279 Ring outerAARing; 280 this->createOuterRing(fInitialRing, kAntialiasingRadius, 0.0f, &outerAARing); 281 } 282 283 // the bisectors are only needed for the computation of the outer ring 284 fBisectors.rewind(); 285 if (SkStrokeRec::kStroke_Style == fStyle && fInitialRing.numPts() > 2) { 286 SkASSERT(fStrokeWidth >= 0.0f); 287 SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; 288 Ring* insetStrokeRing; 289 SkScalar strokeDepth = effectiveStrokeWidth / 2 - kAntialiasingRadius; 290 if (this->createInsetRings(fInitialRing, 0.0f, coverage, strokeDepth, coverage, 291 &insetStrokeRing)) { 292 Ring* insetAARing; 293 this->createInsetRings(*insetStrokeRing, strokeDepth, coverage, strokeDepth + 294 kAntialiasingRadius * 2, 0.0f, &insetAARing); 295 } 296 } else { 297 Ring* insetAARing; 298 this->createInsetRings(fInitialRing, 0.0f, 0.5f, kAntialiasingRadius, 1.0f, &insetAARing); 299 } 300 301 SkDEBUGCODE(this->validate();) 302 return true; 303 } 304 305 SkScalar GrAAConvexTessellator::computeDepthFromEdge(int edgeIdx, const SkPoint& p) const { 306 SkASSERT(edgeIdx < fNorms.count()); 307 308 SkPoint v = p - fPts[edgeIdx]; 309 SkScalar depth = -fNorms[edgeIdx].dot(v); 310 return depth; 311 } 312 313 // Find a point that is 'desiredDepth' away from the 'edgeIdx'-th edge and lies 314 // along the 'bisector' from the 'startIdx'-th point. 315 bool GrAAConvexTessellator::computePtAlongBisector(int startIdx, 316 const SkVector& bisector, 317 int edgeIdx, 318 SkScalar desiredDepth, 319 SkPoint* result) const { 320 const SkPoint& norm = fNorms[edgeIdx]; 321 322 // First find the point where the edge and the bisector intersect 323 SkPoint newP; 324 325 SkScalar t = perp_intersect(fPts[startIdx], bisector, fPts[edgeIdx], norm); 326 if (SkScalarNearlyEqual(t, 0.0f)) { 327 // the start point was one of the original ring points 328 SkASSERT(startIdx < fPts.count()); 329 newP = fPts[startIdx]; 330 } else if (t < 0.0f) { 331 newP = bisector; 332 newP.scale(t); 333 newP += fPts[startIdx]; 334 } else { 335 return false; 336 } 337 338 // Then offset along the bisector from that point the correct distance 339 SkScalar dot = bisector.dot(norm); 340 t = -desiredDepth / dot; 341 *result = bisector; 342 result->scale(t); 343 *result += newP; 344 345 return true; 346 } 347 348 bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) { 349 SkASSERT(SkPath::kConvex_Convexity == path.getConvexity()); 350 351 // Outer ring: 3*numPts 352 // Middle ring: numPts 353 // Presumptive inner ring: numPts 354 this->reservePts(5*path.countPoints()); 355 // Outer ring: 12*numPts 356 // Middle ring: 0 357 // Presumptive inner ring: 6*numPts + 6 358 fIndices.setReserve(18*path.countPoints() + 6); 359 360 fNorms.setReserve(path.countPoints()); 361 362 // TODO: is there a faster way to extract the points from the path? Perhaps 363 // get all the points via a new entry point, transform them all in bulk 364 // and then walk them to find duplicates? 365 SkPath::Iter iter(path, true); 366 SkPoint pts[4]; 367 SkPath::Verb verb; 368 while ((verb = iter.next(pts, true, true)) != SkPath::kDone_Verb) { 369 switch (verb) { 370 case SkPath::kLine_Verb: 371 this->lineTo(m, pts[1], kSharp_CurveState); 372 break; 373 case SkPath::kQuad_Verb: 374 this->quadTo(m, pts); 375 break; 376 case SkPath::kCubic_Verb: 377 this->cubicTo(m, pts); 378 break; 379 case SkPath::kConic_Verb: 380 this->conicTo(m, pts, iter.conicWeight()); 381 break; 382 case SkPath::kMove_Verb: 383 case SkPath::kClose_Verb: 384 case SkPath::kDone_Verb: 385 break; 386 } 387 } 388 389 if (this->numPts() < 2) { 390 return false; 391 } 392 393 // check if last point is a duplicate of the first point. If so, remove it. 394 if (duplicate_pt(fPts[this->numPts()-1], fPts[0])) { 395 this->popLastPt(); 396 fNorms.pop(); 397 } 398 399 SkASSERT(fPts.count() == fNorms.count()+1); 400 if (this->numPts() >= 3) { 401 if (abs_dist_from_line(fPts.top(), fNorms.top(), fPts[0]) < kClose) { 402 // The last point is on the line from the second to last to the first point. 403 this->popLastPt(); 404 fNorms.pop(); 405 } 406 407 *fNorms.push() = fPts[0] - fPts.top(); 408 SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top()); 409 SkASSERT(len > 0.0f); 410 SkASSERT(fPts.count() == fNorms.count()); 411 } 412 413 if (this->numPts() >= 3 && abs_dist_from_line(fPts[0], fNorms.top(), fPts[1]) < kClose) { 414 // The first point is on the line from the last to the second. 415 this->popFirstPtShuffle(); 416 fNorms.removeShuffle(0); 417 fNorms[0] = fPts[1] - fPts[0]; 418 SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms[0]); 419 SkASSERT(len > 0.0f); 420 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[0].length())); 421 } 422 423 if (this->numPts() >= 3) { 424 // Check the cross product of the final trio 425 SkScalar cross = SkPoint::CrossProduct(fNorms[0], fNorms.top()); 426 if (cross > 0.0f) { 427 fSide = SkPointPriv::kRight_Side; 428 } else { 429 fSide = SkPointPriv::kLeft_Side; 430 } 431 432 // Make all the normals face outwards rather than along the edge 433 for (int cur = 0; cur < fNorms.count(); ++cur) { 434 SkPointPriv::SetOrthog(&fNorms[cur], fNorms[cur], fSide); 435 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length())); 436 } 437 438 this->computeBisectors(); 439 } else if (this->numPts() == 2) { 440 // We've got two points, so we're degenerate. 441 if (fStyle == SkStrokeRec::kFill_Style) { 442 // it's a fill, so we don't need to worry about degenerate paths 443 return false; 444 } 445 // For stroking, we still need to process the degenerate path, so fix it up 446 fSide = SkPointPriv::kLeft_Side; 447 448 // Make all the normals face outwards rather than along the edge 449 for (int cur = 0; cur < fNorms.count(); ++cur) { 450 SkPointPriv::SetOrthog(&fNorms[cur], fNorms[cur], fSide); 451 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length())); 452 } 453 454 fNorms.push(SkPoint::Make(-fNorms[0].fX, -fNorms[0].fY)); 455 // we won't actually use the bisectors, so just push zeroes 456 fBisectors.push(SkPoint::Make(0.0, 0.0)); 457 fBisectors.push(SkPoint::Make(0.0, 0.0)); 458 } else { 459 return false; 460 } 461 462 fCandidateVerts.setReserve(this->numPts()); 463 fInitialRing.setReserve(this->numPts()); 464 for (int i = 0; i < this->numPts(); ++i) { 465 fInitialRing.addIdx(i, i); 466 } 467 fInitialRing.init(fNorms, fBisectors); 468 469 this->validate(); 470 return true; 471 } 472 473 GrAAConvexTessellator::Ring* GrAAConvexTessellator::getNextRing(Ring* lastRing) { 474 #if GR_AA_CONVEX_TESSELLATOR_VIZ 475 Ring* ring = *fRings.push() = new Ring; 476 ring->setReserve(fInitialRing.numPts()); 477 ring->rewind(); 478 return ring; 479 #else 480 // Flip flop back and forth between fRings[0] & fRings[1] 481 int nextRing = (lastRing == &fRings[0]) ? 1 : 0; 482 fRings[nextRing].setReserve(fInitialRing.numPts()); 483 fRings[nextRing].rewind(); 484 return &fRings[nextRing]; 485 #endif 486 } 487 488 void GrAAConvexTessellator::fanRing(const Ring& ring) { 489 // fan out from point 0 490 int startIdx = ring.index(0); 491 for (int cur = ring.numPts() - 2; cur >= 0; --cur) { 492 this->addTri(startIdx, ring.index(cur), ring.index(cur + 1)); 493 } 494 } 495 496 void GrAAConvexTessellator::createOuterRing(const Ring& previousRing, SkScalar outset, 497 SkScalar coverage, Ring* nextRing) { 498 const int numPts = previousRing.numPts(); 499 if (numPts == 0) { 500 return; 501 } 502 503 int prev = numPts - 1; 504 int lastPerpIdx = -1, firstPerpIdx = -1; 505 506 const SkScalar outsetSq = outset * outset; 507 SkScalar miterLimitSq = outset * fMiterLimit; 508 miterLimitSq = miterLimitSq * miterLimitSq; 509 for (int cur = 0; cur < numPts; ++cur) { 510 int originalIdx = previousRing.index(cur); 511 // For each vertex of the original polygon we add at least two points to the 512 // outset polygon - one extending perpendicular to each impinging edge. Connecting these 513 // two points yields a bevel join. We need one additional point for a mitered join, and 514 // a round join requires one or more points depending upon curvature. 515 516 // The perpendicular point for the last edge 517 SkPoint normal1 = previousRing.norm(prev); 518 SkPoint perp1 = normal1; 519 perp1.scale(outset); 520 perp1 += this->point(originalIdx); 521 522 // The perpendicular point for the next edge. 523 SkPoint normal2 = previousRing.norm(cur); 524 SkPoint perp2 = normal2; 525 perp2.scale(outset); 526 perp2 += fPts[originalIdx]; 527 528 CurveState curve = fCurveState[originalIdx]; 529 530 // We know it isn't a duplicate of the prior point (since it and this 531 // one are just perpendicular offsets from the non-merged polygon points) 532 int perp1Idx = this->addPt(perp1, -outset, coverage, false, curve); 533 nextRing->addIdx(perp1Idx, originalIdx); 534 535 int perp2Idx; 536 // For very shallow angles all the corner points could fuse. 537 if (duplicate_pt(perp2, this->point(perp1Idx))) { 538 perp2Idx = perp1Idx; 539 } else { 540 perp2Idx = this->addPt(perp2, -outset, coverage, false, curve); 541 } 542 543 if (perp2Idx != perp1Idx) { 544 if (curve == kCurve_CurveState) { 545 // bevel or round depending upon curvature 546 SkScalar dotProd = normal1.dot(normal2); 547 if (dotProd < kRoundCapThreshold) { 548 // Currently we "round" by creating a single extra point, which produces 549 // good results for common cases. For thick strokes with high curvature, we will 550 // need to add more points; for the time being we simply fall back to software 551 // rendering for thick strokes. 552 SkPoint miter = previousRing.bisector(cur); 553 miter.setLength(-outset); 554 miter += fPts[originalIdx]; 555 556 // For very shallow angles all the corner points could fuse 557 if (!duplicate_pt(miter, this->point(perp1Idx))) { 558 int miterIdx; 559 miterIdx = this->addPt(miter, -outset, coverage, false, kSharp_CurveState); 560 nextRing->addIdx(miterIdx, originalIdx); 561 // The two triangles for the corner 562 this->addTri(originalIdx, perp1Idx, miterIdx); 563 this->addTri(originalIdx, miterIdx, perp2Idx); 564 } 565 } else { 566 this->addTri(originalIdx, perp1Idx, perp2Idx); 567 } 568 } else { 569 switch (fJoin) { 570 case SkPaint::Join::kMiter_Join: { 571 // The bisector outset point 572 SkPoint miter = previousRing.bisector(cur); 573 SkScalar dotProd = normal1.dot(normal2); 574 SkScalar sinHalfAngleSq = SkScalarHalf(SK_Scalar1 + dotProd); 575 SkScalar lengthSq = outsetSq / sinHalfAngleSq; 576 if (lengthSq > miterLimitSq) { 577 // just bevel it 578 this->addTri(originalIdx, perp1Idx, perp2Idx); 579 break; 580 } 581 miter.setLength(-SkScalarSqrt(lengthSq)); 582 miter += fPts[originalIdx]; 583 584 // For very shallow angles all the corner points could fuse 585 if (!duplicate_pt(miter, this->point(perp1Idx))) { 586 int miterIdx; 587 miterIdx = this->addPt(miter, -outset, coverage, false, 588 kSharp_CurveState); 589 nextRing->addIdx(miterIdx, originalIdx); 590 // The two triangles for the corner 591 this->addTri(originalIdx, perp1Idx, miterIdx); 592 this->addTri(originalIdx, miterIdx, perp2Idx); 593 } 594 break; 595 } 596 case SkPaint::Join::kBevel_Join: 597 this->addTri(originalIdx, perp1Idx, perp2Idx); 598 break; 599 default: 600 // kRound_Join is unsupported for now. GrAALinearizingConvexPathRenderer is 601 // only willing to draw mitered or beveled, so we should never get here. 602 SkASSERT(false); 603 } 604 } 605 606 nextRing->addIdx(perp2Idx, originalIdx); 607 } 608 609 if (0 == cur) { 610 // Store the index of the first perpendicular point to finish up 611 firstPerpIdx = perp1Idx; 612 SkASSERT(-1 == lastPerpIdx); 613 } else { 614 // The triangles for the previous edge 615 int prevIdx = previousRing.index(prev); 616 this->addTri(prevIdx, perp1Idx, originalIdx); 617 this->addTri(prevIdx, lastPerpIdx, perp1Idx); 618 } 619 620 // Track the last perpendicular outset point so we can construct the 621 // trailing edge triangles. 622 lastPerpIdx = perp2Idx; 623 prev = cur; 624 } 625 626 // pick up the final edge rect 627 int lastIdx = previousRing.index(numPts - 1); 628 this->addTri(lastIdx, firstPerpIdx, previousRing.index(0)); 629 this->addTri(lastIdx, lastPerpIdx, firstPerpIdx); 630 631 this->validate(); 632 } 633 634 // Something went wrong in the creation of the next ring. If we're filling the shape, just go ahead 635 // and fan it. 636 void GrAAConvexTessellator::terminate(const Ring& ring) { 637 if (fStyle != SkStrokeRec::kStroke_Style) { 638 this->fanRing(ring); 639 } 640 } 641 642 static SkScalar compute_coverage(SkScalar depth, SkScalar initialDepth, SkScalar initialCoverage, 643 SkScalar targetDepth, SkScalar targetCoverage) { 644 if (SkScalarNearlyEqual(initialDepth, targetDepth)) { 645 return targetCoverage; 646 } 647 SkScalar result = (depth - initialDepth) / (targetDepth - initialDepth) * 648 (targetCoverage - initialCoverage) + initialCoverage; 649 return SkScalarClampMax(result, 1.0f); 650 } 651 652 // return true when processing is complete 653 bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing, 654 SkScalar initialDepth, SkScalar initialCoverage, 655 SkScalar targetDepth, SkScalar targetCoverage, 656 bool forceNew) { 657 bool done = false; 658 659 fCandidateVerts.rewind(); 660 661 // Loop through all the points in the ring and find the intersection with the smallest depth 662 SkScalar minDist = SK_ScalarMax, minT = 0.0f; 663 int minEdgeIdx = -1; 664 665 for (int cur = 0; cur < lastRing.numPts(); ++cur) { 666 int next = (cur + 1) % lastRing.numPts(); 667 668 SkScalar t; 669 bool result = intersect(this->point(lastRing.index(cur)), lastRing.bisector(cur), 670 this->point(lastRing.index(next)), lastRing.bisector(next), 671 &t); 672 if (!result) { 673 continue; 674 } 675 SkScalar dist = -t * lastRing.norm(cur).dot(lastRing.bisector(cur)); 676 677 if (minDist > dist) { 678 minDist = dist; 679 minT = t; 680 minEdgeIdx = cur; 681 } 682 } 683 684 if (minEdgeIdx == -1) { 685 return false; 686 } 687 SkPoint newPt = lastRing.bisector(minEdgeIdx); 688 newPt.scale(minT); 689 newPt += this->point(lastRing.index(minEdgeIdx)); 690 691 SkScalar depth = this->computeDepthFromEdge(lastRing.origEdgeID(minEdgeIdx), newPt); 692 if (depth >= targetDepth) { 693 // None of the bisectors intersect before reaching the desired depth. 694 // Just step them all to the desired depth 695 depth = targetDepth; 696 done = true; 697 } 698 699 // 'dst' stores where each point in the last ring maps to/transforms into 700 // in the next ring. 701 SkTDArray<int> dst; 702 dst.setCount(lastRing.numPts()); 703 704 // Create the first point (who compares with no one) 705 if (!this->computePtAlongBisector(lastRing.index(0), 706 lastRing.bisector(0), 707 lastRing.origEdgeID(0), 708 depth, &newPt)) { 709 this->terminate(lastRing); 710 return true; 711 } 712 dst[0] = fCandidateVerts.addNewPt(newPt, 713 lastRing.index(0), lastRing.origEdgeID(0), 714 !this->movable(lastRing.index(0))); 715 716 // Handle the middle points (who only compare with the prior point) 717 for (int cur = 1; cur < lastRing.numPts()-1; ++cur) { 718 if (!this->computePtAlongBisector(lastRing.index(cur), 719 lastRing.bisector(cur), 720 lastRing.origEdgeID(cur), 721 depth, &newPt)) { 722 this->terminate(lastRing); 723 return true; 724 } 725 if (!duplicate_pt(newPt, fCandidateVerts.lastPoint())) { 726 dst[cur] = fCandidateVerts.addNewPt(newPt, 727 lastRing.index(cur), lastRing.origEdgeID(cur), 728 !this->movable(lastRing.index(cur))); 729 } else { 730 dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur)); 731 } 732 } 733 734 // Check on the last point (handling the wrap around) 735 int cur = lastRing.numPts()-1; 736 if (!this->computePtAlongBisector(lastRing.index(cur), 737 lastRing.bisector(cur), 738 lastRing.origEdgeID(cur), 739 depth, &newPt)) { 740 this->terminate(lastRing); 741 return true; 742 } 743 bool dupPrev = duplicate_pt(newPt, fCandidateVerts.lastPoint()); 744 bool dupNext = duplicate_pt(newPt, fCandidateVerts.firstPoint()); 745 746 if (!dupPrev && !dupNext) { 747 dst[cur] = fCandidateVerts.addNewPt(newPt, 748 lastRing.index(cur), lastRing.origEdgeID(cur), 749 !this->movable(lastRing.index(cur))); 750 } else if (dupPrev && !dupNext) { 751 dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur)); 752 } else if (!dupPrev && dupNext) { 753 dst[cur] = fCandidateVerts.fuseWithNext(); 754 } else { 755 bool dupPrevVsNext = duplicate_pt(fCandidateVerts.firstPoint(), fCandidateVerts.lastPoint()); 756 757 if (!dupPrevVsNext) { 758 dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur)); 759 } else { 760 const int fused = fCandidateVerts.fuseWithBoth(); 761 dst[cur] = fused; 762 const int targetIdx = dst[cur - 1]; 763 for (int i = cur - 1; i >= 0 && dst[i] == targetIdx; i--) { 764 dst[i] = fused; 765 } 766 } 767 } 768 769 // Fold the new ring's points into the global pool 770 for (int i = 0; i < fCandidateVerts.numPts(); ++i) { 771 int newIdx; 772 if (fCandidateVerts.needsToBeNew(i) || forceNew) { 773 // if the originating index is still valid then this point wasn't 774 // fused (and is thus movable) 775 SkScalar coverage = compute_coverage(depth, initialDepth, initialCoverage, 776 targetDepth, targetCoverage); 777 newIdx = this->addPt(fCandidateVerts.point(i), depth, coverage, 778 fCandidateVerts.originatingIdx(i) != -1, kSharp_CurveState); 779 } else { 780 SkASSERT(fCandidateVerts.originatingIdx(i) != -1); 781 this->updatePt(fCandidateVerts.originatingIdx(i), fCandidateVerts.point(i), depth, 782 targetCoverage); 783 newIdx = fCandidateVerts.originatingIdx(i); 784 } 785 786 nextRing->addIdx(newIdx, fCandidateVerts.origEdge(i)); 787 } 788 789 // 'dst' currently has indices into the ring. Remap these to be indices 790 // into the global pool since the triangulation operates in that space. 791 for (int i = 0; i < dst.count(); ++i) { 792 dst[i] = nextRing->index(dst[i]); 793 } 794 795 for (int i = 0; i < lastRing.numPts(); ++i) { 796 int next = (i + 1) % lastRing.numPts(); 797 798 this->addTri(lastRing.index(i), lastRing.index(next), dst[next]); 799 this->addTri(lastRing.index(i), dst[next], dst[i]); 800 } 801 802 if (done && fStyle != SkStrokeRec::kStroke_Style) { 803 // fill or stroke-and-fill 804 this->fanRing(*nextRing); 805 } 806 807 if (nextRing->numPts() < 3) { 808 done = true; 809 } 810 return done; 811 } 812 813 void GrAAConvexTessellator::validate() const { 814 SkASSERT(fPts.count() == fMovable.count()); 815 SkASSERT(fPts.count() == fCoverages.count()); 816 SkASSERT(fPts.count() == fCurveState.count()); 817 SkASSERT(0 == (fIndices.count() % 3)); 818 SkASSERT(!fBisectors.count() || fBisectors.count() == fNorms.count()); 819 } 820 821 ////////////////////////////////////////////////////////////////////////////// 822 void GrAAConvexTessellator::Ring::init(const GrAAConvexTessellator& tess) { 823 this->computeNormals(tess); 824 this->computeBisectors(tess); 825 } 826 827 void GrAAConvexTessellator::Ring::init(const SkTDArray<SkVector>& norms, 828 const SkTDArray<SkVector>& bisectors) { 829 for (int i = 0; i < fPts.count(); ++i) { 830 fPts[i].fNorm = norms[i]; 831 fPts[i].fBisector = bisectors[i]; 832 } 833 } 834 835 // Compute the outward facing normal at each vertex. 836 void GrAAConvexTessellator::Ring::computeNormals(const GrAAConvexTessellator& tess) { 837 for (int cur = 0; cur < fPts.count(); ++cur) { 838 int next = (cur + 1) % fPts.count(); 839 840 fPts[cur].fNorm = tess.point(fPts[next].fIndex) - tess.point(fPts[cur].fIndex); 841 SkPoint::Normalize(&fPts[cur].fNorm); 842 SkPointPriv::SetOrthog(&fPts[cur].fNorm, fPts[cur].fNorm, tess.side()); 843 } 844 } 845 846 void GrAAConvexTessellator::Ring::computeBisectors(const GrAAConvexTessellator& tess) { 847 int prev = fPts.count() - 1; 848 for (int cur = 0; cur < fPts.count(); prev = cur, ++cur) { 849 fPts[cur].fBisector = fPts[cur].fNorm + fPts[prev].fNorm; 850 if (!fPts[cur].fBisector.normalize()) { 851 SkASSERT(SkPointPriv::kLeft_Side == tess.side() || 852 SkPointPriv::kRight_Side == tess.side()); 853 SkPointPriv::SetOrthog(&fPts[cur].fBisector, fPts[cur].fNorm, 854 (SkPointPriv::Side)-tess.side()); 855 SkVector other; 856 SkPointPriv::SetOrthog(&other, fPts[prev].fNorm, tess.side()); 857 fPts[cur].fBisector += other; 858 SkAssertResult(fPts[cur].fBisector.normalize()); 859 } else { 860 fPts[cur].fBisector.negate(); // make the bisector face in 861 } 862 } 863 } 864 865 ////////////////////////////////////////////////////////////////////////////// 866 #ifdef SK_DEBUG 867 // Is this ring convex? 868 bool GrAAConvexTessellator::Ring::isConvex(const GrAAConvexTessellator& tess) const { 869 if (fPts.count() < 3) { 870 return true; 871 } 872 873 SkPoint prev = tess.point(fPts[0].fIndex) - tess.point(fPts.top().fIndex); 874 SkPoint cur = tess.point(fPts[1].fIndex) - tess.point(fPts[0].fIndex); 875 SkScalar minDot = prev.fX * cur.fY - prev.fY * cur.fX; 876 SkScalar maxDot = minDot; 877 878 prev = cur; 879 for (int i = 1; i < fPts.count(); ++i) { 880 int next = (i + 1) % fPts.count(); 881 882 cur = tess.point(fPts[next].fIndex) - tess.point(fPts[i].fIndex); 883 SkScalar dot = prev.fX * cur.fY - prev.fY * cur.fX; 884 885 minDot = SkMinScalar(minDot, dot); 886 maxDot = SkMaxScalar(maxDot, dot); 887 888 prev = cur; 889 } 890 891 if (SkScalarNearlyEqual(maxDot, 0.0f, 0.005f)) { 892 maxDot = 0; 893 } 894 if (SkScalarNearlyEqual(minDot, 0.0f, 0.005f)) { 895 minDot = 0; 896 } 897 return (maxDot >= 0.0f) == (minDot >= 0.0f); 898 } 899 900 #endif 901 902 void GrAAConvexTessellator::lineTo(const SkPoint& p, CurveState curve) { 903 if (this->numPts() > 0 && duplicate_pt(p, this->lastPoint())) { 904 return; 905 } 906 907 SkASSERT(fPts.count() <= 1 || fPts.count() == fNorms.count()+1); 908 if (this->numPts() >= 2 && abs_dist_from_line(fPts.top(), fNorms.top(), p) < kClose) { 909 // The old last point is on the line from the second to last to the new point 910 this->popLastPt(); 911 fNorms.pop(); 912 // double-check that the new last point is not a duplicate of the new point. In an ideal 913 // world this wouldn't be necessary (since it's only possible for non-convex paths), but 914 // floating point precision issues mean it can actually happen on paths that were 915 // determined to be convex. 916 if (duplicate_pt(p, this->lastPoint())) { 917 return; 918 } 919 } 920 SkScalar initialRingCoverage = (SkStrokeRec::kFill_Style == fStyle) ? 0.5f : 1.0f; 921 this->addPt(p, 0.0f, initialRingCoverage, false, curve); 922 if (this->numPts() > 1) { 923 *fNorms.push() = fPts.top() - fPts[fPts.count()-2]; 924 SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top()); 925 SkASSERT(len > 0.0f); 926 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms.top().length())); 927 } 928 } 929 930 void GrAAConvexTessellator::lineTo(const SkMatrix& m, SkPoint p, CurveState curve) { 931 m.mapPoints(&p, 1); 932 this->lineTo(p, curve); 933 } 934 935 void GrAAConvexTessellator::quadTo(const SkPoint pts[3]) { 936 int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance); 937 fPointBuffer.setReserve(maxCount); 938 SkPoint* target = fPointBuffer.begin(); 939 int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2], 940 kQuadTolerance, &target, maxCount); 941 fPointBuffer.setCount(count); 942 for (int i = 0; i < count - 1; i++) { 943 this->lineTo(fPointBuffer[i], kCurve_CurveState); 944 } 945 this->lineTo(fPointBuffer[count - 1], kIndeterminate_CurveState); 946 } 947 948 void GrAAConvexTessellator::quadTo(const SkMatrix& m, SkPoint pts[3]) { 949 m.mapPoints(pts, 3); 950 this->quadTo(pts); 951 } 952 953 void GrAAConvexTessellator::cubicTo(const SkMatrix& m, SkPoint pts[4]) { 954 m.mapPoints(pts, 4); 955 int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance); 956 fPointBuffer.setReserve(maxCount); 957 SkPoint* target = fPointBuffer.begin(); 958 int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3], 959 kCubicTolerance, &target, maxCount); 960 fPointBuffer.setCount(count); 961 for (int i = 0; i < count - 1; i++) { 962 this->lineTo(fPointBuffer[i], kCurve_CurveState); 963 } 964 this->lineTo(fPointBuffer[count - 1], kIndeterminate_CurveState); 965 } 966 967 // include down here to avoid compilation errors caused by "-" overload in SkGeometry.h 968 #include "SkGeometry.h" 969 970 void GrAAConvexTessellator::conicTo(const SkMatrix& m, SkPoint pts[3], SkScalar w) { 971 m.mapPoints(pts, 3); 972 SkAutoConicToQuads quadder; 973 const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance); 974 SkPoint lastPoint = *(quads++); 975 int count = quadder.countQuads(); 976 for (int i = 0; i < count; ++i) { 977 SkPoint quadPts[3]; 978 quadPts[0] = lastPoint; 979 quadPts[1] = quads[0]; 980 quadPts[2] = i == count - 1 ? pts[2] : quads[1]; 981 this->quadTo(quadPts); 982 lastPoint = quadPts[2]; 983 quads += 2; 984 } 985 } 986 987 ////////////////////////////////////////////////////////////////////////////// 988 #if GR_AA_CONVEX_TESSELLATOR_VIZ 989 static const SkScalar kPointRadius = 0.02f; 990 static const SkScalar kArrowStrokeWidth = 0.0f; 991 static const SkScalar kArrowLength = 0.2f; 992 static const SkScalar kEdgeTextSize = 0.1f; 993 static const SkScalar kPointTextSize = 0.02f; 994 995 static void draw_point(SkCanvas* canvas, const SkPoint& p, SkScalar paramValue, bool stroke) { 996 SkPaint paint; 997 SkASSERT(paramValue <= 1.0f); 998 int gs = int(255*paramValue); 999 paint.setARGB(255, gs, gs, gs); 1000 1001 canvas->drawCircle(p.fX, p.fY, kPointRadius, paint); 1002 1003 if (stroke) { 1004 SkPaint stroke; 1005 stroke.setColor(SK_ColorYELLOW); 1006 stroke.setStyle(SkPaint::kStroke_Style); 1007 stroke.setStrokeWidth(kPointRadius/3.0f); 1008 canvas->drawCircle(p.fX, p.fY, kPointRadius, stroke); 1009 } 1010 } 1011 1012 static void draw_line(SkCanvas* canvas, const SkPoint& p0, const SkPoint& p1, SkColor color) { 1013 SkPaint p; 1014 p.setColor(color); 1015 1016 canvas->drawLine(p0.fX, p0.fY, p1.fX, p1.fY, p); 1017 } 1018 1019 static void draw_arrow(SkCanvas*canvas, const SkPoint& p, const SkPoint &n, 1020 SkScalar len, SkColor color) { 1021 SkPaint paint; 1022 paint.setColor(color); 1023 paint.setStrokeWidth(kArrowStrokeWidth); 1024 paint.setStyle(SkPaint::kStroke_Style); 1025 1026 canvas->drawLine(p.fX, p.fY, 1027 p.fX + len * n.fX, p.fY + len * n.fY, 1028 paint); 1029 } 1030 1031 void GrAAConvexTessellator::Ring::draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const { 1032 SkPaint paint; 1033 paint.setTextSize(kEdgeTextSize); 1034 1035 for (int cur = 0; cur < fPts.count(); ++cur) { 1036 int next = (cur + 1) % fPts.count(); 1037 1038 draw_line(canvas, 1039 tess.point(fPts[cur].fIndex), 1040 tess.point(fPts[next].fIndex), 1041 SK_ColorGREEN); 1042 1043 SkPoint mid = tess.point(fPts[cur].fIndex) + tess.point(fPts[next].fIndex); 1044 mid.scale(0.5f); 1045 1046 if (fPts.count()) { 1047 draw_arrow(canvas, mid, fPts[cur].fNorm, kArrowLength, SK_ColorRED); 1048 mid.fX += (kArrowLength/2) * fPts[cur].fNorm.fX; 1049 mid.fY += (kArrowLength/2) * fPts[cur].fNorm.fY; 1050 } 1051 1052 SkString num; 1053 num.printf("%d", this->origEdgeID(cur)); 1054 canvas->drawString(num, mid.fX, mid.fY, paint); 1055 1056 if (fPts.count()) { 1057 draw_arrow(canvas, tess.point(fPts[cur].fIndex), fPts[cur].fBisector, 1058 kArrowLength, SK_ColorBLUE); 1059 } 1060 } 1061 } 1062 1063 void GrAAConvexTessellator::draw(SkCanvas* canvas) const { 1064 for (int i = 0; i < fIndices.count(); i += 3) { 1065 SkASSERT(fIndices[i] < this->numPts()) ; 1066 SkASSERT(fIndices[i+1] < this->numPts()) ; 1067 SkASSERT(fIndices[i+2] < this->numPts()) ; 1068 1069 draw_line(canvas, 1070 this->point(this->fIndices[i]), this->point(this->fIndices[i+1]), 1071 SK_ColorBLACK); 1072 draw_line(canvas, 1073 this->point(this->fIndices[i+1]), this->point(this->fIndices[i+2]), 1074 SK_ColorBLACK); 1075 draw_line(canvas, 1076 this->point(this->fIndices[i+2]), this->point(this->fIndices[i]), 1077 SK_ColorBLACK); 1078 } 1079 1080 fInitialRing.draw(canvas, *this); 1081 for (int i = 0; i < fRings.count(); ++i) { 1082 fRings[i]->draw(canvas, *this); 1083 } 1084 1085 for (int i = 0; i < this->numPts(); ++i) { 1086 draw_point(canvas, 1087 this->point(i), 0.5f + (this->depth(i)/(2 * kAntialiasingRadius)), 1088 !this->movable(i)); 1089 1090 SkPaint paint; 1091 paint.setTextSize(kPointTextSize); 1092 paint.setTextAlign(SkPaint::kCenter_Align); 1093 if (this->depth(i) <= -kAntialiasingRadius) { 1094 paint.setColor(SK_ColorWHITE); 1095 } 1096 1097 SkString num; 1098 num.printf("%d", i); 1099 canvas->drawString(num, 1100 this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f), 1101 paint); 1102 } 1103 } 1104 1105 #endif 1106