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