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