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