| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 | 7 |
| 8 #include "GrAAConvexTessellator.h" | 8 #include "GrAAConvexTessellator.h" |
| 9 #include "SkCanvas.h" | 9 #include "SkCanvas.h" |
| 10 #include "SkPath.h" | 10 #include "SkPath.h" |
| (...skipping 14 matching lines...) Expand all Loading... |
| 25 static const SkScalar kQuadTolerance = 0.2f; | 25 static const SkScalar kQuadTolerance = 0.2f; |
| 26 static const SkScalar kCubicTolerance = 0.2f; | 26 static const SkScalar kCubicTolerance = 0.2f; |
| 27 static const SkScalar kConicTolerance = 0.5f; | 27 static const SkScalar kConicTolerance = 0.5f; |
| 28 | 28 |
| 29 // dot product below which we use a round cap between curve segments | 29 // dot product below which we use a round cap between curve segments |
| 30 static const SkScalar kRoundCapThreshold = 0.8f; | 30 static const SkScalar kRoundCapThreshold = 0.8f; |
| 31 | 31 |
| 32 // dot product above which we consider two adjacent curves to be part of the "sa
me" curve | 32 // dot product above which we consider two adjacent curves to be part of the "sa
me" curve |
| 33 static const SkScalar kCurveConnectionThreshold = 0.8f; | 33 static const SkScalar kCurveConnectionThreshold = 0.8f; |
| 34 | 34 |
| 35 static bool intersect(const SkPoint& p0, const SkPoint& n0, | 35 static SkScalar intersect(const SkPoint& p0, const SkPoint& n0, |
| 36 const SkPoint& p1, const SkPoint& n1, | 36 const SkPoint& p1, const SkPoint& n1) { |
| 37 SkScalar* t) { | |
| 38 const SkPoint v = p1 - p0; | 37 const SkPoint v = p1 - p0; |
| 39 SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX; | 38 SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX; |
| 40 if (SkScalarNearlyZero(perpDot)) { | 39 return (v.fX * n1.fY - v.fY * n1.fX) / perpDot; |
| 41 return false; | |
| 42 } | |
| 43 *t = (v.fX * n1.fY - v.fY * n1.fX) / perpDot; | |
| 44 SkASSERT(SkScalarIsFinite(*t)); | |
| 45 return true; | |
| 46 } | 40 } |
| 47 | 41 |
| 48 // This is a special case version of intersect where we have the vector | 42 // 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. | 43 // perpendicular to the second line rather than the vector parallel to it. |
| 50 static SkScalar perp_intersect(const SkPoint& p0, const SkPoint& n0, | 44 static SkScalar perp_intersect(const SkPoint& p0, const SkPoint& n0, |
| 51 const SkPoint& p1, const SkPoint& perp) { | 45 const SkPoint& p1, const SkPoint& perp) { |
| 52 const SkPoint v = p1 - p0; | 46 const SkPoint v = p1 - p0; |
| 53 SkScalar perpDot = n0.dot(perp); | 47 SkScalar perpDot = n0.dot(perp); |
| 54 return v.dot(perp) / perpDot; | 48 return v.dot(perp) / perpDot; |
| 55 } | 49 } |
| (...skipping 161 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 217 // The polygon state is captured in the Ring class while the GrAAConvexTessellat
or | 211 // The polygon state is captured in the Ring class while the GrAAConvexTessellat
or |
| 218 // controls the iteration. The CandidateVerts holds the formative points for the | 212 // controls the iteration. The CandidateVerts holds the formative points for the |
| 219 // next ring. | 213 // next ring. |
| 220 bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) { | 214 bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) { |
| 221 if (!this->extractFromPath(m, path)) { | 215 if (!this->extractFromPath(m, path)) { |
| 222 return false; | 216 return false; |
| 223 } | 217 } |
| 224 | 218 |
| 225 SkScalar coverage = 1.0f; | 219 SkScalar coverage = 1.0f; |
| 226 SkScalar scaleFactor = 0.0f; | 220 SkScalar scaleFactor = 0.0f; |
| 227 | 221 if (fStrokeWidth >= 0.0f) { |
| 228 if (SkStrokeRec::kStrokeAndFill_Style == fStyle) { | |
| 229 SkASSERT(m.isSimilarity()); | 222 SkASSERT(m.isSimilarity()); |
| 230 scaleFactor = m.getMaxScale(); // x and y scale are the same | 223 scaleFactor = m.getMaxScale(); // x and y scale are the same |
| 231 SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; | 224 SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; |
| 232 Ring outerStrokeAndAARing; | |
| 233 this->createOuterRing(fInitialRing, | |
| 234 effectiveStrokeWidth / 2 + kAntialiasingRadius, 0.
0, | |
| 235 &outerStrokeAndAARing); | |
| 236 | |
| 237 // discard all the triangles added between the originating ring and the
new outer ring | |
| 238 fIndices.rewind(); | |
| 239 | |
| 240 outerStrokeAndAARing.init(*this); | |
| 241 | |
| 242 outerStrokeAndAARing.makeOriginalRing(); | |
| 243 | |
| 244 // Add the outer stroke ring's normals to the originating ring's normals | |
| 245 // so it can also act as an originating ring | |
| 246 fNorms.setReserve(fNorms.count() + outerStrokeAndAARing.numPts()); | |
| 247 for (int i = 0; i < outerStrokeAndAARing.numPts(); ++i) { | |
| 248 fNorms.push(outerStrokeAndAARing.norm(i)); | |
| 249 } | |
| 250 | |
| 251 // the bisectors are only needed for the computation of the outer ring | |
| 252 fBisectors.rewind(); | |
| 253 | |
| 254 Ring* insetAARing; | |
| 255 this->createInsetRings(outerStrokeAndAARing, | |
| 256 0.0f, 0.0f, 2*kAntialiasingRadius, 1.0f, | |
| 257 &insetAARing); | |
| 258 | |
| 259 SkDEBUGCODE(this->validate();) | |
| 260 return true; | |
| 261 } | |
| 262 | |
| 263 if (SkStrokeRec::kStroke_Style == fStyle) { | |
| 264 SkASSERT(fStrokeWidth >= 0.0f); | |
| 265 SkASSERT(m.isSimilarity()); | |
| 266 scaleFactor = m.getMaxScale(); // x and y scale are the same | |
| 267 SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; | |
| 268 Ring outerStrokeRing; | 225 Ring outerStrokeRing; |
| 269 this->createOuterRing(fInitialRing, effectiveStrokeWidth / 2 - kAntialia
singRadius, | 226 this->createOuterRing(fInitialRing, effectiveStrokeWidth / 2 - kAntialia
singRadius, |
| 270 coverage, &outerStrokeRing); | 227 coverage, &outerStrokeRing); |
| 271 outerStrokeRing.init(*this); | 228 outerStrokeRing.init(*this); |
| 272 Ring outerAARing; | 229 Ring outerAARing; |
| 273 this->createOuterRing(outerStrokeRing, kAntialiasingRadius * 2, 0.0f, &o
uterAARing); | 230 this->createOuterRing(outerStrokeRing, kAntialiasingRadius * 2, 0.0f, &o
uterAARing); |
| 274 } else { | 231 } else { |
| 275 Ring outerAARing; | 232 Ring outerAARing; |
| 276 this->createOuterRing(fInitialRing, kAntialiasingRadius, 0.0f, &outerAAR
ing); | 233 this->createOuterRing(fInitialRing, kAntialiasingRadius, 0.0f, &outerAAR
ing); |
| 277 } | 234 } |
| 278 | 235 |
| 279 // the bisectors are only needed for the computation of the outer ring | 236 // the bisectors are only needed for the computation of the outer ring |
| 280 fBisectors.rewind(); | 237 fBisectors.rewind(); |
| 281 if (SkStrokeRec::kStroke_Style == fStyle && fInitialRing.numPts() > 2) { | 238 if (fStrokeWidth >= 0.0f && fInitialRing.numPts() > 2) { |
| 282 SkASSERT(fStrokeWidth >= 0.0f); | |
| 283 SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; | 239 SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; |
| 284 Ring* insetStrokeRing; | 240 Ring* insetStrokeRing; |
| 285 SkScalar strokeDepth = effectiveStrokeWidth / 2 - kAntialiasingRadius; | 241 SkScalar strokeDepth = effectiveStrokeWidth / 2 - kAntialiasingRadius; |
| 286 if (this->createInsetRings(fInitialRing, 0.0f, coverage, strokeDepth, co
verage, | 242 if (this->createInsetRings(fInitialRing, 0.0f, coverage, strokeDepth, co
verage, |
| 287 &insetStrokeRing)) { | 243 &insetStrokeRing)) { |
| 288 Ring* insetAARing; | 244 Ring* insetAARing; |
| 289 this->createInsetRings(*insetStrokeRing, strokeDepth, coverage, stro
keDepth + | 245 this->createInsetRings(*insetStrokeRing, strokeDepth, coverage, stro
keDepth + |
| 290 kAntialiasingRadius * 2, 0.0f, &insetAARing); | 246 kAntialiasingRadius * 2, 0.0f, &insetAARing); |
| 291 } | 247 } |
| 292 } else { | 248 } else { |
| 293 Ring* insetAARing; | 249 Ring* insetAARing; |
| 294 this->createInsetRings(fInitialRing, 0.0f, 0.5f, kAntialiasingRadius, 1.
0f, &insetAARing); | 250 this->createInsetRings(fInitialRing, 0.0f, 0.5f, kAntialiasingRadius, 1.
0f, &insetAARing); |
| 295 } | 251 } |
| 296 | 252 |
| 297 SkDEBUGCODE(this->validate();) | 253 SkDEBUGCODE(this->validate();) |
| 298 return true; | 254 return true; |
| 299 } | 255 } |
| 300 | 256 |
| (...skipping 126 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 427 | 383 |
| 428 // Make all the normals face outwards rather than along the edge | 384 // Make all the normals face outwards rather than along the edge |
| 429 for (int cur = 0; cur < fNorms.count(); ++cur) { | 385 for (int cur = 0; cur < fNorms.count(); ++cur) { |
| 430 fNorms[cur].setOrthog(fNorms[cur], fSide); | 386 fNorms[cur].setOrthog(fNorms[cur], fSide); |
| 431 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length())); | 387 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length())); |
| 432 } | 388 } |
| 433 | 389 |
| 434 this->computeBisectors(); | 390 this->computeBisectors(); |
| 435 } else if (this->numPts() == 2) { | 391 } else if (this->numPts() == 2) { |
| 436 // We've got two points, so we're degenerate. | 392 // We've got two points, so we're degenerate. |
| 437 if (fStyle == SkStrokeRec::kFill_Style) { | 393 if (fStrokeWidth < 0.0f) { |
| 438 // it's a fill, so we don't need to worry about degenerate paths | 394 // it's a fill, so we don't need to worry about degenerate paths |
| 439 return false; | 395 return false; |
| 440 } | 396 } |
| 441 // For stroking, we still need to process the degenerate path, so fix it
up | 397 // For stroking, we still need to process the degenerate path, so fix it
up |
| 442 fSide = SkPoint::kLeft_Side; | 398 fSide = SkPoint::kLeft_Side; |
| 443 | 399 |
| 444 // Make all the normals face outwards rather than along the edge | 400 // Make all the normals face outwards rather than along the edge |
| 445 for (int cur = 0; cur < fNorms.count(); ++cur) { | 401 for (int cur = 0; cur < fNorms.count(); ++cur) { |
| 446 fNorms[cur].setOrthog(fNorms[cur], fSide); | 402 fNorms[cur].setOrthog(fNorms[cur], fSide); |
| 447 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length())); | 403 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length())); |
| (...skipping 175 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 623 int lastIdx = previousRing.index(numPts - 1); | 579 int lastIdx = previousRing.index(numPts - 1); |
| 624 this->addTri(lastIdx, firstPerpIdx, previousRing.index(0)); | 580 this->addTri(lastIdx, firstPerpIdx, previousRing.index(0)); |
| 625 this->addTri(lastIdx, lastPerpIdx, firstPerpIdx); | 581 this->addTri(lastIdx, lastPerpIdx, firstPerpIdx); |
| 626 | 582 |
| 627 this->validate(); | 583 this->validate(); |
| 628 } | 584 } |
| 629 | 585 |
| 630 // Something went wrong in the creation of the next ring. If we're filling the s
hape, just go ahead | 586 // Something went wrong in the creation of the next ring. If we're filling the s
hape, just go ahead |
| 631 // and fan it. | 587 // and fan it. |
| 632 void GrAAConvexTessellator::terminate(const Ring& ring) { | 588 void GrAAConvexTessellator::terminate(const Ring& ring) { |
| 633 if (fStyle != SkStrokeRec::kStroke_Style) { | 589 if (fStrokeWidth < 0.0f) { |
| 634 this->fanRing(ring); | 590 this->fanRing(ring); |
| 635 } | 591 } |
| 636 } | 592 } |
| 637 | 593 |
| 638 static SkScalar compute_coverage(SkScalar depth, SkScalar initialDepth, SkScalar
initialCoverage, | 594 static SkScalar compute_coverage(SkScalar depth, SkScalar initialDepth, SkScalar
initialCoverage, |
| 639 SkScalar targetDepth, SkScalar targetCoverage) { | 595 SkScalar targetDepth, SkScalar targetCoverage) { |
| 640 if (SkScalarNearlyEqual(initialDepth, targetDepth)) { | 596 if (SkScalarNearlyEqual(initialDepth, targetDepth)) { |
| 641 return targetCoverage; | 597 return targetCoverage; |
| 642 } | 598 } |
| 643 SkScalar result = (depth - initialDepth) / (targetDepth - initialDepth) * | 599 SkScalar result = (depth - initialDepth) / (targetDepth - initialDepth) * |
| 644 (targetCoverage - initialCoverage) + initialCoverage; | 600 (targetCoverage - initialCoverage) + initialCoverage; |
| 645 return SkScalarClampMax(result, 1.0f); | 601 return SkScalarClampMax(result, 1.0f); |
| 646 } | 602 } |
| 647 | 603 |
| 648 // return true when processing is complete | 604 // return true when processing is complete |
| 649 bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing
, | 605 bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing
, |
| 650 SkScalar initialDepth, SkScalar init
ialCoverage, | 606 SkScalar initialDepth, SkScalar init
ialCoverage, |
| 651 SkScalar targetDepth, SkScalar targe
tCoverage, | 607 SkScalar targetDepth, SkScalar targe
tCoverage, |
| 652 bool forceNew) { | 608 bool forceNew) { |
| 653 bool done = false; | 609 bool done = false; |
| 654 | 610 |
| 655 fCandidateVerts.rewind(); | 611 fCandidateVerts.rewind(); |
| 656 | 612 |
| 657 // Loop through all the points in the ring and find the intersection with th
e smallest depth | 613 // Loop through all the points in the ring and find the intersection with th
e smallest depth |
| 658 SkScalar minDist = SK_ScalarMax, minT = 0.0f; | 614 SkScalar minDist = SK_ScalarMax, minT = 0.0f; |
| 659 int minEdgeIdx = -1; | 615 int minEdgeIdx = -1; |
| 660 | 616 |
| 661 for (int cur = 0; cur < lastRing.numPts(); ++cur) { | 617 for (int cur = 0; cur < lastRing.numPts(); ++cur) { |
| 662 int next = (cur + 1) % lastRing.numPts(); | 618 int next = (cur + 1) % lastRing.numPts(); |
| 663 | 619 SkScalar t = intersect(this->point(lastRing.index(cur)), lastRing.bisec
tor(cur), |
| 664 SkScalar t; | 620 this->point(lastRing.index(next)), lastRing.bisec
tor(next)); |
| 665 bool result = intersect(this->point(lastRing.index(cur)), lastRing.bise
ctor(cur), | |
| 666 this->point(lastRing.index(next)), lastRing.bise
ctor(next), | |
| 667 &t); | |
| 668 if (!result) { | |
| 669 continue; | |
| 670 } | |
| 671 SkScalar dist = -t * lastRing.norm(cur).dot(lastRing.bisector(cur)); | 621 SkScalar dist = -t * lastRing.norm(cur).dot(lastRing.bisector(cur)); |
| 672 | 622 |
| 673 if (minDist > dist) { | 623 if (minDist > dist) { |
| 674 minDist = dist; | 624 minDist = dist; |
| 675 minT = t; | 625 minT = t; |
| 676 minEdgeIdx = cur; | 626 minEdgeIdx = cur; |
| 677 } | 627 } |
| 678 } | 628 } |
| 679 | 629 |
| 680 if (minEdgeIdx == -1) { | 630 if (minEdgeIdx == -1) { |
| (...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 788 dst[i] = nextRing->index(dst[i]); | 738 dst[i] = nextRing->index(dst[i]); |
| 789 } | 739 } |
| 790 | 740 |
| 791 for (int i = 0; i < lastRing.numPts(); ++i) { | 741 for (int i = 0; i < lastRing.numPts(); ++i) { |
| 792 int next = (i + 1) % lastRing.numPts(); | 742 int next = (i + 1) % lastRing.numPts(); |
| 793 | 743 |
| 794 this->addTri(lastRing.index(i), lastRing.index(next), dst[next]); | 744 this->addTri(lastRing.index(i), lastRing.index(next), dst[next]); |
| 795 this->addTri(lastRing.index(i), dst[next], dst[i]); | 745 this->addTri(lastRing.index(i), dst[next], dst[i]); |
| 796 } | 746 } |
| 797 | 747 |
| 798 if (done && fStyle != SkStrokeRec::kStroke_Style) { | 748 if (done && fStrokeWidth < 0.0f) { |
| 799 // fill or stroke-and-fill | 749 // fill |
| 800 this->fanRing(*nextRing); | 750 this->fanRing(*nextRing); |
| 801 } | 751 } |
| 802 | 752 |
| 803 if (nextRing->numPts() < 3) { | 753 if (nextRing->numPts() < 3) { |
| 804 done = true; | 754 done = true; |
| 805 } | 755 } |
| 806 return done; | 756 return done; |
| 807 } | 757 } |
| 808 | 758 |
| 809 void GrAAConvexTessellator::validate() const { | 759 void GrAAConvexTessellator::validate() const { |
| (...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 903 fNorms.pop(); | 853 fNorms.pop(); |
| 904 fCurveState.pop(); | 854 fCurveState.pop(); |
| 905 // double-check that the new last point is not a duplicate of the new po
int. In an ideal | 855 // double-check that the new last point is not a duplicate of the new po
int. In an ideal |
| 906 // world this wouldn't be necessary (since it's only possible for non-co
nvex paths), but | 856 // world this wouldn't be necessary (since it's only possible for non-co
nvex paths), but |
| 907 // floating point precision issues mean it can actually happen on paths
that were determined | 857 // floating point precision issues mean it can actually happen on paths
that were determined |
| 908 // to be convex. | 858 // to be convex. |
| 909 if (duplicate_pt(p, this->lastPoint())) { | 859 if (duplicate_pt(p, this->lastPoint())) { |
| 910 return; | 860 return; |
| 911 } | 861 } |
| 912 } | 862 } |
| 913 SkScalar initialRingCoverage = (SkStrokeRec::kFill_Style == fStyle) ? 0.5f :
1.0f; | 863 SkScalar initialRingCoverage = fStrokeWidth < 0.0f ? 0.5f : 1.0f; |
| 914 this->addPt(p, 0.0f, initialRingCoverage, false, curve); | 864 this->addPt(p, 0.0f, initialRingCoverage, false, curve); |
| 915 if (this->numPts() > 1) { | 865 if (this->numPts() > 1) { |
| 916 *fNorms.push() = fPts.top() - fPts[fPts.count()-2]; | 866 *fNorms.push() = fPts.top() - fPts[fPts.count()-2]; |
| 917 SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top()); | 867 SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top()); |
| 918 SkASSERT(len > 0.0f); | 868 SkASSERT(len > 0.0f); |
| 919 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms.top().length())); | 869 SkASSERT(SkScalarNearlyEqual(1.0f, fNorms.top().length())); |
| 920 } | 870 } |
| 921 } | 871 } |
| 922 | 872 |
| 923 void GrAAConvexTessellator::lineTo(const SkMatrix& m, SkPoint p, CurveState curv
e) { | 873 void GrAAConvexTessellator::lineTo(const SkMatrix& m, SkPoint p, CurveState curv
e) { |
| (...skipping 169 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1093 | 1043 |
| 1094 SkString num; | 1044 SkString num; |
| 1095 num.printf("%d", i); | 1045 num.printf("%d", i); |
| 1096 canvas->drawText(num.c_str(), num.size(), | 1046 canvas->drawText(num.c_str(), num.size(), |
| 1097 this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f
), | 1047 this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f
), |
| 1098 paint); | 1048 paint); |
| 1099 } | 1049 } |
| 1100 } | 1050 } |
| 1101 | 1051 |
| 1102 #endif | 1052 #endif |
| OLD | NEW |