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