robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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" |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 13 | #include "GrPathUtils.h" |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 14 | |
| 15 | // Next steps: |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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); |
Mike Reed | 8be952a | 2017-02-13 20:44:33 -0500 | [diff] [blame] | 22 | static const SkScalar kCloseSqd = kClose * kClose; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 23 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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 | |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 32 | // dot product above which we consider two adjacent curves to be part of the "same" curve |
ethannicholas | fc6cb73 | 2016-08-30 07:26:58 -0700 | [diff] [blame] | 33 | static const SkScalar kCurveConnectionThreshold = 0.8f; |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 34 | |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 35 | static bool intersect(const SkPoint& p0, const SkPoint& n0, |
| 36 | const SkPoint& p1, const SkPoint& n1, |
| 37 | SkScalar* t) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 38 | const SkPoint v = p1 - p0; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 39 | SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX; |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 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; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 46 | } |
| 47 | |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 48 | // This is a special case version of intersect where we have the vector |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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) { |
Cary Clark | df429f3 | 2017-11-08 11:44:31 -0500 | [diff] [blame] | 58 | SkScalar distSq = SkPointPriv::DistanceToSqd(p0, p1); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 59 | return distSq < kCloseSqd; |
| 60 | } |
| 61 | |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 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; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 70 | } |
| 71 | |
| 72 | int GrAAConvexTessellator::addPt(const SkPoint& pt, |
| 73 | SkScalar depth, |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 74 | SkScalar coverage, |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 75 | bool movable, |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 76 | CurveState curve) { |
Brian Salomon | efa6bcb | 2018-09-11 13:19:19 -0400 | [diff] [blame] | 77 | SkASSERT(pt.isFinite()); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 78 | this->validate(); |
| 79 | |
| 80 | int index = fPts.count(); |
| 81 | *fPts.push() = pt; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 82 | *fCoverages.push() = coverage; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 83 | *fMovable.push() = movable; |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 84 | *fCurveState.push() = curve; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 85 | |
| 86 | this->validate(); |
| 87 | return index; |
| 88 | } |
| 89 | |
| 90 | void GrAAConvexTessellator::popLastPt() { |
| 91 | this->validate(); |
| 92 | |
| 93 | fPts.pop(); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 94 | fCoverages.pop(); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 95 | fMovable.pop(); |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 96 | fCurveState.pop(); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 97 | |
| 98 | this->validate(); |
| 99 | } |
| 100 | |
| 101 | void GrAAConvexTessellator::popFirstPtShuffle() { |
| 102 | this->validate(); |
| 103 | |
| 104 | fPts.removeShuffle(0); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 105 | fCoverages.removeShuffle(0); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 106 | fMovable.removeShuffle(0); |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 107 | fCurveState.removeShuffle(0); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 108 | |
| 109 | this->validate(); |
| 110 | } |
| 111 | |
| 112 | void GrAAConvexTessellator::updatePt(int index, |
| 113 | const SkPoint& pt, |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 114 | SkScalar depth, |
| 115 | SkScalar coverage) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 116 | this->validate(); |
| 117 | SkASSERT(fMovable[index]); |
| 118 | |
| 119 | fPts[index] = pt; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 120 | fCoverages[index] = coverage; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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(); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 135 | fCoverages.rewind(); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 136 | fMovable.rewind(); |
| 137 | fIndices.rewind(); |
| 138 | fNorms.rewind(); |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 139 | fCurveState.rewind(); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 | |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 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 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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]; |
robertphillips | 364ad00 | 2015-05-20 11:49:55 -0700 | [diff] [blame] | 177 | if (!fBisectors[cur].normalize()) { |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 178 | fBisectors[cur] = SkPointPriv::MakeOrthog(fNorms[cur], (SkPointPriv::Side)-fSide) + |
| 179 | SkPointPriv::MakeOrthog(fNorms[prev], fSide); |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 180 | SkAssertResult(fBisectors[cur].normalize()); |
robertphillips | 364ad00 | 2015-05-20 11:49:55 -0700 | [diff] [blame] | 181 | } else { |
| 182 | fBisectors[cur].negate(); // make the bisector face in |
| 183 | } |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 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 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 197 | |
| 198 | SkASSERT(SkScalarNearlyEqual(1.0f, fBisectors[cur].length())); |
| 199 | } |
| 200 | } |
| 201 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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, |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 205 | SkScalar initialCoverage, SkScalar targetDepth, |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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 | |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 218 | bool done = this->createInsetRing(*currentRing, nextRing, initialDepth, initialCoverage, |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 247 | if (!this->extractFromPath(m, path)) { |
| 248 | return false; |
| 249 | } |
| 250 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 251 | SkScalar coverage = 1.0f; |
ethannicholas | fea7763 | 2015-08-19 12:09:12 -0700 | [diff] [blame] | 252 | SkScalar scaleFactor = 0.0f; |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 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); |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 292 | SkASSERT(m.isSimilarity()); |
ethannicholas | fea7763 | 2015-08-19 12:09:12 -0700 | [diff] [blame] | 293 | scaleFactor = m.getMaxScale(); // x and y scale are the same |
| 294 | SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 295 | Ring outerStrokeRing; |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 296 | this->createOuterRing(fInitialRing, effectiveStrokeWidth / 2 - kAntialiasingRadius, |
ethannicholas | fea7763 | 2015-08-19 12:09:12 -0700 | [diff] [blame] | 297 | coverage, &outerStrokeRing); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 305 | |
| 306 | // the bisectors are only needed for the computation of the outer ring |
| 307 | fBisectors.rewind(); |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 308 | if (SkStrokeRec::kStroke_Style == fStyle && fInitialRing.numPts() > 2) { |
| 309 | SkASSERT(fStrokeWidth >= 0.0f); |
ethannicholas | fea7763 | 2015-08-19 12:09:12 -0700 | [diff] [blame] | 310 | SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 311 | Ring* insetStrokeRing; |
ethannicholas | fea7763 | 2015-08-19 12:09:12 -0700 | [diff] [blame] | 312 | SkScalar strokeDepth = effectiveStrokeWidth / 2 - kAntialiasingRadius; |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 313 | if (this->createInsetRings(fInitialRing, 0.0f, coverage, strokeDepth, coverage, |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 314 | &insetStrokeRing)) { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 315 | Ring* insetAARing; |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 316 | this->createInsetRings(*insetStrokeRing, strokeDepth, coverage, strokeDepth + |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 317 | kAntialiasingRadius * 2, 0.0f, &insetAARing); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 318 | } |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 319 | } else { |
| 320 | Ring* insetAARing; |
| 321 | this->createInsetRings(fInitialRing, 0.0f, 0.5f, kAntialiasingRadius, 1.0f, &insetAARing); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 322 | } |
| 323 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 324 | SkDEBUGCODE(this->validate();) |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 347 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 351 | SkASSERT(startIdx < fPts.count()); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 352 | newP = fPts[startIdx]; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 353 | } else if (t < 0.0f) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 362 | SkScalar dot = bisector.dot(norm); |
| 363 | t = -desiredDepth / dot; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 364 | *result = bisector; |
| 365 | result->scale(t); |
| 366 | *result += newP; |
| 367 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 368 | return true; |
| 369 | } |
| 370 | |
| 371 | bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 372 | SkASSERT(SkPath::kConvex_Convexity == path.getConvexity()); |
| 373 | |
Brian Salomon | efa6bcb | 2018-09-11 13:19:19 -0400 | [diff] [blame] | 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 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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; |
Brian Salomon | 97042bf | 2017-02-28 11:21:28 -0500 | [diff] [blame] | 397 | while ((verb = iter.next(pts, true, true)) != SkPath::kDone_Verb) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 398 | switch (verb) { |
| 399 | case SkPath::kLine_Verb: |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 400 | this->lineTo(m, pts[1], kSharp_CurveState); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 401 | break; |
| 402 | case SkPath::kQuad_Verb: |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 403 | this->quadTo(m, pts); |
| 404 | break; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 405 | case SkPath::kCubic_Verb: |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 406 | this->cubicTo(m, pts); |
| 407 | break; |
| 408 | case SkPath::kConic_Verb: |
| 409 | this->conicTo(m, pts, iter.conicWeight()); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 410 | break; |
| 411 | case SkPath::kMove_Verb: |
| 412 | case SkPath::kClose_Verb: |
| 413 | case SkPath::kDone_Verb: |
| 414 | break; |
| 415 | } |
| 416 | } |
| 417 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 418 | if (this->numPts() < 2) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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(); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 425 | } |
| 426 | |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 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])) { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 431 | this->popLastPt(); |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 432 | } else if (points_are_colinear_and_b_is_middle(fPts.top(), fPts[0], fPts[1])) { |
| 433 | this->popFirstPtShuffle(); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 434 | } else { |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 435 | noRemovalsToDo = true; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 436 | } |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 437 | } |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 438 | |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 439 | // Compute the normals and bisectors. |
| 440 | SkASSERT(fNorms.empty()); |
| 441 | if (this->numPts() >= 3) { |
| 442 | this->computeNormals(); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 443 | this->computeBisectors(); |
| 444 | } else if (this->numPts() == 2) { |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 445 | // We've got two points, so we're degenerate. |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 446 | if (fStyle == SkStrokeRec::kFill_Style) { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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 |
Cary Clark | df429f3 | 2017-11-08 11:44:31 -0500 | [diff] [blame] | 451 | fSide = SkPointPriv::kLeft_Side; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 452 | |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 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())); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 458 | // we won't actually use the bisectors, so just push zeroes |
Mike Reed | 5edcd31 | 2018-08-08 11:23:41 -0400 | [diff] [blame] | 459 | fBisectors.push_back(SkPoint::Make(0.0, 0.0)); |
| 460 | fBisectors.push_back(SkPoint::Make(0.0, 0.0)); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 461 | } else { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 462 | return false; |
| 463 | } |
| 464 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 |
halcanary | 385fe4d | 2015-08-26 13:07:48 -0700 | [diff] [blame] | 478 | Ring* ring = *fRings.push() = new Ring; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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)); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 496 | } |
| 497 | } |
| 498 | |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 499 | void GrAAConvexTessellator::createOuterRing(const Ring& previousRing, SkScalar outset, |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 500 | SkScalar coverage, Ring* nextRing) { |
| 501 | const int numPts = previousRing.numPts(); |
| 502 | if (numPts == 0) { |
| 503 | return; |
| 504 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 505 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 506 | int prev = numPts - 1; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 507 | int lastPerpIdx = -1, firstPerpIdx = -1; |
| 508 | |
Mike Reed | 8be952a | 2017-02-13 20:44:33 -0500 | [diff] [blame] | 509 | const SkScalar outsetSq = outset * outset; |
| 510 | SkScalar miterLimitSq = outset * fMiterLimit; |
| 511 | miterLimitSq = miterLimitSq * miterLimitSq; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 512 | for (int cur = 0; cur < numPts; ++cur) { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 513 | int originalIdx = previousRing.index(cur); |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 514 | // For each vertex of the original polygon we add at least two points to the |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 515 | // outset polygon - one extending perpendicular to each impinging edge. Connecting these |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 516 | // two points yields a bevel join. We need one additional point for a mitered join, and |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 517 | // a round join requires one or more points depending upon curvature. |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 518 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 524 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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]; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 530 | |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 531 | CurveState curve = fCurveState[originalIdx]; |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 532 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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) |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 535 | int perp1Idx = this->addPt(perp1, -outset, coverage, false, curve); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 536 | nextRing->addIdx(perp1Idx, originalIdx); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 537 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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 { |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 543 | perp2Idx = this->addPt(perp2, -outset, coverage, false, curve); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 544 | } |
ethannicholas | 2436f19 | 2015-06-25 14:42:34 -0700 | [diff] [blame] | 545 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 546 | if (perp2Idx != perp1Idx) { |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 547 | if (curve == kCurve_CurveState) { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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]; |
reed | 9730f4a | 2015-06-26 05:06:43 -0700 | [diff] [blame] | 558 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 559 | // For very shallow angles all the corner points could fuse |
| 560 | if (!duplicate_pt(miter, this->point(perp1Idx))) { |
| 561 | int miterIdx; |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 562 | miterIdx = this->addPt(miter, -outset, coverage, false, kSharp_CurveState); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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 | } |
reed | 9730f4a | 2015-06-26 05:06:43 -0700 | [diff] [blame] | 571 | } else { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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); |
Brian Salomon | 776a411 | 2018-09-13 16:39:12 -0400 | [diff] [blame] | 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); |
Greg Daniel | ba31640 | 2018-04-03 11:27:50 -0400 | [diff] [blame] | 580 | SkScalar lengthSq = sk_ieee_float_divide(outsetSq, sinHalfAngleSq); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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; |
Ben Wagner | 63fd760 | 2017-10-09 15:45:33 -0400 | [diff] [blame] | 592 | miterIdx = this->addPt(miter, -outset, coverage, false, |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 593 | kSharp_CurveState); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 594 | nextRing->addIdx(miterIdx, originalIdx); |
| 595 | // The two triangles for the corner |
| 596 | this->addTri(originalIdx, perp1Idx, miterIdx); |
| 597 | this->addTri(originalIdx, miterIdx, perp2Idx); |
Brian Salomon | 20ea47a | 2018-09-04 11:38:28 -0400 | [diff] [blame] | 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); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 602 | } |
| 603 | break; |
| 604 | } |
| 605 | case SkPaint::Join::kBevel_Join: |
| 606 | this->addTri(originalIdx, perp1Idx, perp2Idx); |
| 607 | break; |
| 608 | default: |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 609 | // kRound_Join is unsupported for now. GrAALinearizingConvexPathRenderer is |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 610 | // only willing to draw mitered or beveled, so we should never get here. |
| 611 | SkASSERT(false); |
| 612 | } |
reed | 9730f4a | 2015-06-26 05:06:43 -0700 | [diff] [blame] | 613 | } |
| 614 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 615 | nextRing->addIdx(perp2Idx, originalIdx); |
ethannicholas | 2436f19 | 2015-06-25 14:42:34 -0700 | [diff] [blame] | 616 | } |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 633 | } |
| 634 | |
| 635 | // pick up the final edge rect |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 636 | int lastIdx = previousRing.index(numPts - 1); |
| 637 | this->addTri(lastIdx, firstPerpIdx, previousRing.index(0)); |
| 638 | this->addTri(lastIdx, lastPerpIdx, firstPerpIdx); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 639 | |
| 640 | this->validate(); |
| 641 | } |
| 642 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 643 | // Something went wrong in the creation of the next ring. If we're filling the shape, just go ahead |
| 644 | // and fan it. |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 645 | void GrAAConvexTessellator::terminate(const Ring& ring) { |
Adrienne Walker | 890a8cc | 2018-04-25 15:44:02 -0700 | [diff] [blame] | 646 | if (fStyle != SkStrokeRec::kStroke_Style && ring.numPts() > 0) { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 647 | this->fanRing(ring); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 648 | } |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 649 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 650 | |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 651 | static SkScalar compute_coverage(SkScalar depth, SkScalar initialDepth, SkScalar initialCoverage, |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 652 | SkScalar targetDepth, SkScalar targetCoverage) { |
| 653 | if (SkScalarNearlyEqual(initialDepth, targetDepth)) { |
| 654 | return targetCoverage; |
| 655 | } |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 656 | SkScalar result = (depth - initialDepth) / (targetDepth - initialDepth) * |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 657 | (targetCoverage - initialCoverage) + initialCoverage; |
| 658 | return SkScalarClampMax(result, 1.0f); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 659 | } |
| 660 | |
| 661 | // return true when processing is complete |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 662 | bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing, |
| 663 | SkScalar initialDepth, SkScalar initialCoverage, |
| 664 | SkScalar targetDepth, SkScalar targetCoverage, |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 665 | bool forceNew) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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(); |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 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); |
Brian Salomon | 8e449eb | 2018-09-05 15:08:49 -0400 | [diff] [blame] | 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) { |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 684 | continue; |
| 685 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 695 | if (minEdgeIdx == -1) { |
| 696 | return false; |
| 697 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 703 | if (depth >= targetDepth) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 704 | // None of the bisectors intersect before reaching the desired depth. |
| 705 | // Just step them all to the desired depth |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 706 | depth = targetDepth; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 { |
ethannicholas | 0dacc67 | 2015-07-07 12:41:52 -0700 | [diff] [blame] | 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 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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; |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 783 | if (fCandidateVerts.needsToBeNew(i) || forceNew) { |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 784 | // if the originating index is still valid then this point wasn't |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 785 | // fused (and is thus movable) |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 786 | SkScalar coverage = compute_coverage(depth, initialDepth, initialCoverage, |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 787 | targetDepth, targetCoverage); |
| 788 | newIdx = this->addPt(fCandidateVerts.point(i), depth, coverage, |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 789 | fCandidateVerts.originatingIdx(i) != -1, kSharp_CurveState); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 790 | } else { |
| 791 | SkASSERT(fCandidateVerts.originatingIdx(i) != -1); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 792 | this->updatePt(fCandidateVerts.originatingIdx(i), fCandidateVerts.point(i), depth, |
| 793 | targetCoverage); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 | |
robertphillips | 44c3128 | 2015-09-03 12:58:48 -0700 | [diff] [blame] | 806 | for (int i = 0; i < lastRing.numPts(); ++i) { |
| 807 | int next = (i + 1) % lastRing.numPts(); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 808 | |
robertphillips | 44c3128 | 2015-09-03 12:58:48 -0700 | [diff] [blame] | 809 | this->addTri(lastRing.index(i), lastRing.index(next), dst[next]); |
| 810 | this->addTri(lastRing.index(i), dst[next], dst[i]); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 811 | } |
| 812 | |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 813 | if (done && fStyle != SkStrokeRec::kStroke_Style) { |
| 814 | // fill or stroke-and-fill |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 815 | this->fanRing(*nextRing); |
| 816 | } |
| 817 | |
| 818 | if (nextRing->numPts() < 3) { |
| 819 | done = true; |
| 820 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 821 | return done; |
| 822 | } |
| 823 | |
| 824 | void GrAAConvexTessellator::validate() const { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 825 | SkASSERT(fPts.count() == fMovable.count()); |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 826 | SkASSERT(fPts.count() == fCoverages.count()); |
| 827 | SkASSERT(fPts.count() == fCurveState.count()); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 828 | SkASSERT(0 == (fIndices.count() % 3)); |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 829 | SkASSERT(!fBisectors.count() || fBisectors.count() == fNorms.count()); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 830 | } |
| 831 | |
| 832 | ////////////////////////////////////////////////////////////////////////////// |
| 833 | void GrAAConvexTessellator::Ring::init(const GrAAConvexTessellator& tess) { |
| 834 | this->computeNormals(tess); |
robertphillips | 364ad00 | 2015-05-20 11:49:55 -0700 | [diff] [blame] | 835 | this->computeBisectors(tess); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 852 | SkPoint::Normalize(&fPts[cur].fNorm); |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 853 | fPts[cur].fNorm = SkPointPriv::MakeOrthog(fPts[cur].fNorm, tess.side()); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 854 | } |
| 855 | } |
| 856 | |
robertphillips | 364ad00 | 2015-05-20 11:49:55 -0700 | [diff] [blame] | 857 | void GrAAConvexTessellator::Ring::computeBisectors(const GrAAConvexTessellator& tess) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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; |
robertphillips | 364ad00 | 2015-05-20 11:49:55 -0700 | [diff] [blame] | 861 | if (!fPts[cur].fBisector.normalize()) { |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 862 | fPts[cur].fBisector = |
| 863 | SkPointPriv::MakeOrthog(fPts[cur].fNorm, (SkPointPriv::Side)-tess.side()) + |
| 864 | SkPointPriv::MakeOrthog(fPts[prev].fNorm, tess.side()); |
robertphillips | 364ad00 | 2015-05-20 11:49:55 -0700 | [diff] [blame] | 865 | SkAssertResult(fPts[cur].fBisector.normalize()); |
| 866 | } else { |
| 867 | fPts[cur].fBisector.negate(); // make the bisector face in |
| 868 | } |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 869 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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) { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 877 | return true; |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 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); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 905 | } |
| 906 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 907 | #endif |
| 908 | |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 909 | void GrAAConvexTessellator::lineTo(const SkPoint& p, CurveState curve) { |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 910 | if (this->numPts() > 0 && duplicate_pt(p, this->lastPoint())) { |
| 911 | return; |
| 912 | } |
| 913 | |
Brian Salomon | 0235c64 | 2018-08-31 12:04:18 -0400 | [diff] [blame] | 914 | if (this->numPts() >= 2 && |
| 915 | points_are_colinear_and_b_is_middle(fPts[fPts.count() - 2], fPts.top(), p)) { |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 916 | // The old last point is on the line from the second to last to the new point |
| 917 | this->popLastPt(); |
ethannicholas | 1bcbc8f | 2016-01-08 14:09:18 -0800 | [diff] [blame] | 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 |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 920 | // floating point precision issues mean it can actually happen on paths that were |
| 921 | // determined to be convex. |
ethannicholas | 1bcbc8f | 2016-01-08 14:09:18 -0800 | [diff] [blame] | 922 | if (duplicate_pt(p, this->lastPoint())) { |
| 923 | return; |
| 924 | } |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 925 | } |
robertphillips | 8c17097 | 2016-09-22 12:42:30 -0700 | [diff] [blame] | 926 | SkScalar initialRingCoverage = (SkStrokeRec::kFill_Style == fStyle) ? 0.5f : 1.0f; |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 927 | this->addPt(p, 0.0f, initialRingCoverage, false, curve); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 928 | } |
| 929 | |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 930 | void GrAAConvexTessellator::lineTo(const SkMatrix& m, SkPoint p, CurveState curve) { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 931 | m.mapPoints(&p, 1); |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 932 | this->lineTo(p, curve); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 933 | } |
| 934 | |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 935 | void GrAAConvexTessellator::quadTo(const SkPoint pts[3]) { |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 936 | int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance); |
Mike Klein | cc9856c | 2018-04-19 09:18:33 -0400 | [diff] [blame] | 937 | fPointBuffer.setCount(maxCount); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 938 | SkPoint* target = fPointBuffer.begin(); |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 939 | int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2], |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 940 | kQuadTolerance, &target, maxCount); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 941 | fPointBuffer.setCount(count); |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 942 | for (int i = 0; i < count - 1; i++) { |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 943 | this->lineTo(fPointBuffer[i], kCurve_CurveState); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 944 | } |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 945 | this->lineTo(fPointBuffer[count - 1], kIndeterminate_CurveState); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 946 | } |
| 947 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 948 | void GrAAConvexTessellator::quadTo(const SkMatrix& m, SkPoint pts[3]) { |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 949 | m.mapPoints(pts, 3); |
| 950 | this->quadTo(pts); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 951 | } |
| 952 | |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 953 | void GrAAConvexTessellator::cubicTo(const SkMatrix& m, SkPoint pts[4]) { |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 954 | m.mapPoints(pts, 4); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 955 | int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance); |
Mike Klein | cc9856c | 2018-04-19 09:18:33 -0400 | [diff] [blame] | 956 | fPointBuffer.setCount(maxCount); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 957 | SkPoint* target = fPointBuffer.begin(); |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 958 | int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3], |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 959 | kCubicTolerance, &target, maxCount); |
| 960 | fPointBuffer.setCount(count); |
ethannicholas | fab4a9b | 2016-08-26 11:03:32 -0700 | [diff] [blame] | 961 | for (int i = 0; i < count - 1; i++) { |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 962 | this->lineTo(fPointBuffer[i], kCurve_CurveState); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 963 | } |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 964 | this->lineTo(fPointBuffer[count - 1], kIndeterminate_CurveState); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 965 | } |
| 966 | |
| 967 | // include down here to avoid compilation errors caused by "-" overload in SkGeometry.h |
| 968 | #include "SkGeometry.h" |
| 969 | |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 970 | void GrAAConvexTessellator::conicTo(const SkMatrix& m, SkPoint pts[3], SkScalar w) { |
| 971 | m.mapPoints(pts, 3); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 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]; |
Robert Phillips | 1d08998 | 2016-09-26 14:07:48 -0400 | [diff] [blame] | 981 | this->quadTo(quadPts); |
ethannicholas | 1a1b3ac | 2015-06-10 12:11:17 -0700 | [diff] [blame] | 982 | lastPoint = quadPts[2]; |
| 983 | quads += 2; |
| 984 | } |
| 985 | } |
| 986 | |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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); |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 1008 | canvas->drawCircle(p.fX, p.fY, kPointRadius, stroke); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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)); |
Cary Clark | 2a475ea | 2017-04-28 15:35:12 -0400 | [diff] [blame] | 1054 | canvas->drawString(num, mid.fX, mid.fY, paint); |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 1055 | |
| 1056 | if (fPts.count()) { |
| 1057 | draw_arrow(canvas, tess.point(fPts[cur].fIndex), fPts[cur].fBisector, |
| 1058 | kArrowLength, SK_ColorBLUE); |
| 1059 | } |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 1060 | } |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 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, |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 1087 | this->point(i), 0.5f + (this->depth(i)/(2 * kAntialiasingRadius)), |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 1088 | !this->movable(i)); |
| 1089 | |
| 1090 | SkPaint paint; |
| 1091 | paint.setTextSize(kPointTextSize); |
| 1092 | paint.setTextAlign(SkPaint::kCenter_Align); |
fmalita | bd5d7e7 | 2015-06-26 07:18:24 -0700 | [diff] [blame] | 1093 | if (this->depth(i) <= -kAntialiasingRadius) { |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 1094 | paint.setColor(SK_ColorWHITE); |
| 1095 | } |
| 1096 | |
| 1097 | SkString num; |
| 1098 | num.printf("%d", i); |
Cary Clark | 2a475ea | 2017-04-28 15:35:12 -0400 | [diff] [blame] | 1099 | canvas->drawString(num, |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 1100 | this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f), |
robertphillips | 84b0088 | 2015-05-06 05:15:57 -0700 | [diff] [blame] | 1101 | paint); |
| 1102 | } |
| 1103 | } |
| 1104 | |
| 1105 | #endif |