1 /*
2 * Copyright 2017 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 "SkShadowTessellator.h"
9 #include "SkColorPriv.h"
10 #include "SkGeometry.h"
11 #include "SkInsetConvexPolygon.h"
12 #include "SkPath.h"
13 #include "SkVertices.h"
14
15 #if SK_SUPPORT_GPU
16 #include "GrPathUtils.h"
17 #endif
18
19
20 /**
21 * Base class
22 */
23 class SkBaseShadowTessellator {
24 public:
25 SkBaseShadowTessellator(SkShadowTessellator::HeightFunc, bool transparent);
~SkBaseShadowTessellator()26 virtual ~SkBaseShadowTessellator() {}
27
releaseVertices()28 sk_sp<SkVertices> releaseVertices() {
29 if (!fSucceeded) {
30 return nullptr;
31 }
32 return SkVertices::MakeCopy(SkCanvas::kTriangles_VertexMode, this->vertexCount(),
33 fPositions.begin(), nullptr, fColors.begin(),
34 this->indexCount(), fIndices.begin());
35 }
36
37 protected:
38 static constexpr auto kMinHeight = 0.1f;
39
vertexCount() const40 int vertexCount() const { return fPositions.count(); }
indexCount() const41 int indexCount() const { return fIndices.count(); }
42
43 bool setZOffset(const SkRect& bounds, bool perspective);
44
45 virtual void handleLine(const SkPoint& p) = 0;
46 void handleLine(const SkMatrix& m, SkPoint* p);
47
48 void handleQuad(const SkPoint pts[3]);
49 void handleQuad(const SkMatrix& m, SkPoint pts[3]);
50
51 void handleCubic(const SkMatrix& m, SkPoint pts[4]);
52
53 void handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w);
54
55 bool setTransformedHeightFunc(const SkMatrix& ctm);
56
57 void addArc(const SkVector& nextNormal, bool finishArc);
58
59 SkShadowTessellator::HeightFunc fHeightFunc;
60 std::function<SkScalar(const SkPoint&)> fTransformedHeightFunc;
61 SkScalar fZOffset;
62 // members for perspective height function
63 SkScalar fZParams[3];
64 SkScalar fPartialDeterminants[3];
65
66 // first two points
67 SkTDArray<SkPoint> fInitPoints;
68 // temporary buffer
69 SkTDArray<SkPoint> fPointBuffer;
70
71 SkTDArray<SkPoint> fPositions;
72 SkTDArray<SkColor> fColors;
73 SkTDArray<uint16_t> fIndices;
74
75 int fFirstVertex;
76 SkVector fFirstNormal;
77 SkPoint fFirstPoint;
78
79 bool fSucceeded;
80 bool fTransparent;
81
82 SkColor fUmbraColor;
83 SkColor fPenumbraColor;
84
85 SkScalar fRadius;
86 SkScalar fDirection;
87 int fPrevUmbraIndex;
88 SkVector fPrevNormal;
89 SkPoint fPrevPoint;
90 };
91
compute_normal(const SkPoint & p0,const SkPoint & p1,SkScalar dir,SkVector * newNormal)92 static bool compute_normal(const SkPoint& p0, const SkPoint& p1, SkScalar dir,
93 SkVector* newNormal) {
94 SkVector normal;
95 // compute perpendicular
96 normal.fX = p0.fY - p1.fY;
97 normal.fY = p1.fX - p0.fX;
98 normal *= dir;
99 if (!normal.normalize()) {
100 return false;
101 }
102 *newNormal = normal;
103 return true;
104 }
105
compute_radial_steps(const SkVector & v1,const SkVector & v2,SkScalar r,SkScalar * rotSin,SkScalar * rotCos,int * n)106 static void compute_radial_steps(const SkVector& v1, const SkVector& v2, SkScalar r,
107 SkScalar* rotSin, SkScalar* rotCos, int* n) {
108 const SkScalar kRecipPixelsPerArcSegment = 0.25f;
109
110 SkScalar rCos = v1.dot(v2);
111 SkScalar rSin = v1.cross(v2);
112 SkScalar theta = SkScalarATan2(rSin, rCos);
113
114 SkScalar steps = r*theta*kRecipPixelsPerArcSegment;
115
116 SkScalar dTheta = theta / steps;
117 *rotSin = SkScalarSinCos(dTheta, rotCos);
118 *n = SkScalarFloorToInt(steps);
119 }
120
SkBaseShadowTessellator(SkShadowTessellator::HeightFunc heightFunc,bool transparent)121 SkBaseShadowTessellator::SkBaseShadowTessellator(SkShadowTessellator::HeightFunc heightFunc,
122 bool transparent)
123 : fHeightFunc(heightFunc)
124 , fZOffset(0)
125 , fFirstVertex(-1)
126 , fSucceeded(false)
127 , fTransparent(transparent)
128 , fDirection(1)
129 , fPrevUmbraIndex(-1) {
130 fInitPoints.setReserve(3);
131
132 // child classes will set reserve for positions, colors and indices
133 }
134
setZOffset(const SkRect & bounds,bool perspective)135 bool SkBaseShadowTessellator::setZOffset(const SkRect& bounds, bool perspective) {
136 SkScalar minZ = fHeightFunc(bounds.fLeft, bounds.fTop);
137 if (perspective) {
138 SkScalar z = fHeightFunc(bounds.fLeft, bounds.fBottom);
139 if (z < minZ) {
140 minZ = z;
141 }
142 z = fHeightFunc(bounds.fRight, bounds.fTop);
143 if (z < minZ) {
144 minZ = z;
145 }
146 z = fHeightFunc(bounds.fRight, bounds.fBottom);
147 if (z < minZ) {
148 minZ = z;
149 }
150 }
151
152 if (minZ < kMinHeight) {
153 fZOffset = -minZ + kMinHeight;
154 return true;
155 }
156
157 return false;
158 }
159
160 // tesselation tolerance values, in device space pixels
161 #if SK_SUPPORT_GPU
162 static const SkScalar kQuadTolerance = 0.2f;
163 static const SkScalar kCubicTolerance = 0.2f;
164 #endif
165 static const SkScalar kConicTolerance = 0.5f;
166
handleLine(const SkMatrix & m,SkPoint * p)167 void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) {
168 m.mapPoints(p, 1);
169 this->handleLine(*p);
170 }
171
handleQuad(const SkPoint pts[3])172 void SkBaseShadowTessellator::handleQuad(const SkPoint pts[3]) {
173 #if SK_SUPPORT_GPU
174 // TODO: Pull PathUtils out of Ganesh?
175 int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
176 fPointBuffer.setReserve(maxCount);
177 SkPoint* target = fPointBuffer.begin();
178 int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
179 kQuadTolerance, &target, maxCount);
180 fPointBuffer.setCount(count);
181 for (int i = 0; i < count; i++) {
182 this->handleLine(fPointBuffer[i]);
183 }
184 #else
185 // for now, just to draw something
186 this->handleLine(pts[1]);
187 this->handleLine(pts[2]);
188 #endif
189 }
190
handleQuad(const SkMatrix & m,SkPoint pts[3])191 void SkBaseShadowTessellator::handleQuad(const SkMatrix& m, SkPoint pts[3]) {
192 m.mapPoints(pts, 3);
193 this->handleQuad(pts);
194 }
195
handleCubic(const SkMatrix & m,SkPoint pts[4])196 void SkBaseShadowTessellator::handleCubic(const SkMatrix& m, SkPoint pts[4]) {
197 m.mapPoints(pts, 4);
198 #if SK_SUPPORT_GPU
199 // TODO: Pull PathUtils out of Ganesh?
200 int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
201 fPointBuffer.setReserve(maxCount);
202 SkPoint* target = fPointBuffer.begin();
203 int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
204 kCubicTolerance, &target, maxCount);
205 fPointBuffer.setCount(count);
206 for (int i = 0; i < count; i++) {
207 this->handleLine(fPointBuffer[i]);
208 }
209 #else
210 // for now, just to draw something
211 this->handleLine(pts[1]);
212 this->handleLine(pts[2]);
213 this->handleLine(pts[3]);
214 #endif
215 }
216
handleConic(const SkMatrix & m,SkPoint pts[3],SkScalar w)217 void SkBaseShadowTessellator::handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w) {
218 if (m.hasPerspective()) {
219 w = SkConic::TransformW(pts, w, m);
220 }
221 m.mapPoints(pts, 3);
222 SkAutoConicToQuads quadder;
223 const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance);
224 SkPoint lastPoint = *(quads++);
225 int count = quadder.countQuads();
226 for (int i = 0; i < count; ++i) {
227 SkPoint quadPts[3];
228 quadPts[0] = lastPoint;
229 quadPts[1] = quads[0];
230 quadPts[2] = i == count - 1 ? pts[2] : quads[1];
231 this->handleQuad(quadPts);
232 lastPoint = quadPts[2];
233 quads += 2;
234 }
235 }
236
addArc(const SkVector & nextNormal,bool finishArc)237 void SkBaseShadowTessellator::addArc(const SkVector& nextNormal, bool finishArc) {
238 // fill in fan from previous quad
239 SkScalar rotSin, rotCos;
240 int numSteps;
241 compute_radial_steps(fPrevNormal, nextNormal, fRadius, &rotSin, &rotCos, &numSteps);
242 SkVector prevNormal = fPrevNormal;
243 for (int i = 0; i < numSteps; ++i) {
244 SkVector currNormal;
245 currNormal.fX = prevNormal.fX*rotCos - prevNormal.fY*rotSin;
246 currNormal.fY = prevNormal.fY*rotCos + prevNormal.fX*rotSin;
247 *fPositions.push() = fPrevPoint + currNormal;
248 *fColors.push() = fPenumbraColor;
249 *fIndices.push() = fPrevUmbraIndex;
250 *fIndices.push() = fPositions.count() - 2;
251 *fIndices.push() = fPositions.count() - 1;
252
253 prevNormal = currNormal;
254 }
255 if (finishArc) {
256 *fPositions.push() = fPrevPoint + nextNormal;
257 *fColors.push() = fPenumbraColor;
258 *fIndices.push() = fPrevUmbraIndex;
259 *fIndices.push() = fPositions.count() - 2;
260 *fIndices.push() = fPositions.count() - 1;
261 }
262 fPrevNormal = nextNormal;
263 }
264
setTransformedHeightFunc(const SkMatrix & ctm)265 bool SkBaseShadowTessellator::setTransformedHeightFunc(const SkMatrix& ctm) {
266 if (!ctm.hasPerspective()) {
267 fTransformedHeightFunc = [this](const SkPoint& p) {
268 return this->fHeightFunc(0, 0);
269 };
270 } else {
271 SkMatrix ctmInverse;
272 if (!ctm.invert(&ctmInverse)) {
273 return false;
274 }
275 SkScalar C = fHeightFunc(0, 0);
276 SkScalar A = fHeightFunc(1, 0) - C;
277 SkScalar B = fHeightFunc(0, 1) - C;
278
279 // multiply by transpose
280 fZParams[0] = ctmInverse[SkMatrix::kMScaleX] * A +
281 ctmInverse[SkMatrix::kMSkewY] * B +
282 ctmInverse[SkMatrix::kMPersp0] * C;
283 fZParams[1] = ctmInverse[SkMatrix::kMSkewX] * A +
284 ctmInverse[SkMatrix::kMScaleY] * B +
285 ctmInverse[SkMatrix::kMPersp1] * C;
286 fZParams[2] = ctmInverse[SkMatrix::kMTransX] * A +
287 ctmInverse[SkMatrix::kMTransY] * B +
288 ctmInverse[SkMatrix::kMPersp2] * C;
289
290 // We use Cramer's rule to solve for the W value for a given post-divide X and Y,
291 // so pre-compute those values that are independent of X and Y.
292 // W is det(ctmInverse)/(PD[0]*X + PD[1]*Y + PD[2])
293 fPartialDeterminants[0] = ctm[SkMatrix::kMSkewY] * ctm[SkMatrix::kMPersp1] -
294 ctm[SkMatrix::kMScaleY] * ctm[SkMatrix::kMPersp0];
295 fPartialDeterminants[1] = ctm[SkMatrix::kMPersp0] * ctm[SkMatrix::kMSkewX] -
296 ctm[SkMatrix::kMPersp1] * ctm[SkMatrix::kMScaleX];
297 fPartialDeterminants[2] = ctm[SkMatrix::kMScaleX] * ctm[SkMatrix::kMScaleY] -
298 ctm[SkMatrix::kMSkewX] * ctm[SkMatrix::kMSkewY];
299 SkScalar ctmDeterminant = ctm[SkMatrix::kMTransX] * fPartialDeterminants[0] +
300 ctm[SkMatrix::kMTransY] * fPartialDeterminants[1] +
301 ctm[SkMatrix::kMPersp2] * fPartialDeterminants[2];
302
303 // Pre-bake the numerator of Cramer's rule into the zParams to avoid another multiply.
304 // TODO: this may introduce numerical instability, but I haven't seen any issues yet.
305 fZParams[0] *= ctmDeterminant;
306 fZParams[1] *= ctmDeterminant;
307 fZParams[2] *= ctmDeterminant;
308
309 fTransformedHeightFunc = [this](const SkPoint& p) {
310 SkScalar denom = p.fX * this->fPartialDeterminants[0] +
311 p.fY * this->fPartialDeterminants[1] +
312 this->fPartialDeterminants[2];
313 SkScalar w = SkScalarFastInvert(denom);
314 return (this->fZParams[0] * p.fX + this->fZParams[1] * p.fY + this->fZParams[2])*w +
315 this->fZOffset;
316 };
317 }
318
319 return true;
320 }
321
322
323 //////////////////////////////////////////////////////////////////////////////////////////////////
324
325 class SkAmbientShadowTessellator : public SkBaseShadowTessellator {
326 public:
327 SkAmbientShadowTessellator(const SkPath& path, const SkMatrix& ctm,
328 SkShadowTessellator::HeightFunc heightFunc,
329 SkScalar ambientAlpha, bool transparent);
330
331 private:
332 void handleLine(const SkPoint& p) override;
333 void addEdge(const SkVector& nextPoint, const SkVector& nextNormal);
334
335 static constexpr auto kHeightFactor = 1.0f / 128.0f;
336 static constexpr auto kGeomFactor = 64.0f;
337 static constexpr auto kMaxEdgeLenSqr = 20 * 20;
338
offset(SkScalar z)339 SkScalar offset(SkScalar z) {
340 return z * kHeightFactor * kGeomFactor;
341 }
umbraColor(SkScalar z)342 SkColor umbraColor(SkScalar z) {
343 SkScalar umbraAlpha = SkScalarInvert((1.0f + SkTMax(z*kHeightFactor, 0.0f)));
344 return SkColorSetARGB(255, 0, fAmbientAlpha * 255.9999f, umbraAlpha * 255.9999f);
345 }
346
347 SkScalar fAmbientAlpha;
348 int fCentroidCount;
349
350 typedef SkBaseShadowTessellator INHERITED;
351 };
352
SkAmbientShadowTessellator(const SkPath & path,const SkMatrix & ctm,SkShadowTessellator::HeightFunc heightFunc,SkScalar ambientAlpha,bool transparent)353 SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
354 const SkMatrix& ctm,
355 SkShadowTessellator::HeightFunc heightFunc,
356 SkScalar ambientAlpha,
357 bool transparent)
358 : INHERITED(heightFunc, transparent)
359 , fAmbientAlpha(ambientAlpha) {
360 // Set base colors
361 SkScalar occluderHeight = heightFunc(0, 0);
362 SkScalar umbraAlpha = SkScalarInvert((1.0f + SkTMax(occluderHeight*kHeightFactor, 0.0f)));
363 // umbraColor is the interior value, penumbraColor the exterior value.
364 // umbraAlpha is the factor that is linearly interpolated from outside to inside, and
365 // then "blurred" by the GrBlurredEdgeFP. It is then multiplied by fAmbientAlpha to get
366 // the final alpha.
367 fUmbraColor = SkColorSetARGB(255, 0, ambientAlpha * 255.9999f, umbraAlpha * 255.9999f);
368 fPenumbraColor = SkColorSetARGB(255, 0, ambientAlpha * 255.9999f, 0);
369
370 // make sure we're not below the canvas plane
371 this->setZOffset(path.getBounds(), ctm.hasPerspective());
372
373 this->setTransformedHeightFunc(ctm);
374
375 // Outer ring: 3*numPts
376 // Middle ring: numPts
377 fPositions.setReserve(4 * path.countPoints());
378 fColors.setReserve(4 * path.countPoints());
379 // Outer ring: 12*numPts
380 // Middle ring: 0
381 fIndices.setReserve(12 * path.countPoints());
382
383 // walk around the path, tessellate and generate outer ring
384 // if original path is transparent, will accumulate sum of points for centroid
385 SkPath::Iter iter(path, true);
386 SkPoint pts[4];
387 SkPath::Verb verb;
388 if (fTransparent) {
389 *fPositions.push() = SkPoint::Make(0, 0);
390 *fColors.push() = fUmbraColor;
391 fCentroidCount = 0;
392 }
393 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
394 switch (verb) {
395 case SkPath::kLine_Verb:
396 this->INHERITED::handleLine(ctm, &pts[1]);
397 break;
398 case SkPath::kQuad_Verb:
399 this->handleQuad(ctm, pts);
400 break;
401 case SkPath::kCubic_Verb:
402 this->handleCubic(ctm, pts);
403 break;
404 case SkPath::kConic_Verb:
405 this->handleConic(ctm, pts, iter.conicWeight());
406 break;
407 case SkPath::kMove_Verb:
408 case SkPath::kClose_Verb:
409 case SkPath::kDone_Verb:
410 break;
411 }
412 }
413
414 if (!this->indexCount()) {
415 return;
416 }
417
418 SkVector normal;
419 if (compute_normal(fPrevPoint, fFirstPoint, fDirection, &normal)) {
420 SkScalar z = fTransformedHeightFunc(fPrevPoint);
421 fRadius = this->offset(z);
422 SkVector scaledNormal(normal);
423 scaledNormal *= fRadius;
424 this->addArc(scaledNormal, true);
425
426 // set up for final edge
427 z = fTransformedHeightFunc(fFirstPoint);
428 normal *= this->offset(z);
429
430 // make sure we don't end up with a sharp alpha edge along the quad diagonal
431 if (fColors[fPrevUmbraIndex] != fColors[fFirstVertex] &&
432 fFirstPoint.distanceToSqd(fPositions[fPrevUmbraIndex]) > kMaxEdgeLenSqr) {
433 SkPoint centerPoint = fPositions[fPrevUmbraIndex] + fFirstPoint;
434 centerPoint *= 0.5f;
435 *fPositions.push() = centerPoint;
436 *fColors.push() = SkPMLerp(fColors[fFirstVertex], fColors[fPrevUmbraIndex], 128);
437 SkVector midNormal = fPrevNormal + normal;
438 midNormal *= 0.5f;
439 *fPositions.push() = centerPoint + midNormal;
440 *fColors.push() = fPenumbraColor;
441
442 *fIndices.push() = fPrevUmbraIndex;
443 *fIndices.push() = fPositions.count() - 3;
444 *fIndices.push() = fPositions.count() - 2;
445
446 *fIndices.push() = fPositions.count() - 3;
447 *fIndices.push() = fPositions.count() - 1;
448 *fIndices.push() = fPositions.count() - 2;
449
450 fPrevUmbraIndex = fPositions.count() - 2;
451 }
452
453 // final edge
454 *fPositions.push() = fFirstPoint + normal;
455 *fColors.push() = fPenumbraColor;
456
457 if (fColors[fPrevUmbraIndex] > fColors[fFirstVertex]) {
458 *fIndices.push() = fPrevUmbraIndex;
459 *fIndices.push() = fPositions.count() - 2;
460 *fIndices.push() = fFirstVertex;
461
462 *fIndices.push() = fPositions.count() - 2;
463 *fIndices.push() = fPositions.count() - 1;
464 *fIndices.push() = fFirstVertex;
465 } else {
466 *fIndices.push() = fPrevUmbraIndex;
467 *fIndices.push() = fPositions.count() - 2;
468 *fIndices.push() = fPositions.count() - 1;
469
470 *fIndices.push() = fPrevUmbraIndex;
471 *fIndices.push() = fPositions.count() - 1;
472 *fIndices.push() = fFirstVertex;
473 }
474 fPrevNormal = normal;
475 }
476
477 // finalize centroid
478 if (fTransparent) {
479 fPositions[0] *= SkScalarFastInvert(fCentroidCount);
480
481 *fIndices.push() = 0;
482 *fIndices.push() = fPrevUmbraIndex;
483 *fIndices.push() = fFirstVertex;
484 }
485
486 // final fan
487 if (fPositions.count() >= 3) {
488 fPrevUmbraIndex = fFirstVertex;
489 fPrevPoint = fFirstPoint;
490 fRadius = this->offset(fTransformedHeightFunc(fPrevPoint));
491 this->addArc(fFirstNormal, false);
492
493 *fIndices.push() = fFirstVertex;
494 *fIndices.push() = fPositions.count() - 1;
495 *fIndices.push() = fFirstVertex + 1;
496 }
497 fSucceeded = true;
498 }
499
handleLine(const SkPoint & p)500 void SkAmbientShadowTessellator::handleLine(const SkPoint& p) {
501 if (fInitPoints.count() < 2) {
502 *fInitPoints.push() = p;
503 return;
504 }
505
506 if (fInitPoints.count() == 2) {
507 // determine if cw or ccw
508 SkVector v0 = fInitPoints[1] - fInitPoints[0];
509 SkVector v1 = p - fInitPoints[0];
510 SkScalar perpDot = v0.fX*v1.fY - v0.fY*v1.fX;
511 if (SkScalarNearlyZero(perpDot)) {
512 // nearly parallel, just treat as straight line and continue
513 fInitPoints[1] = p;
514 return;
515 }
516
517 // if perpDot > 0, winding is ccw
518 fDirection = (perpDot > 0) ? -1 : 1;
519
520 // add first quad
521 SkVector normal;
522 if (!compute_normal(fInitPoints[0], fInitPoints[1], fDirection, &normal)) {
523 // first two points are incident, make the third point the second and continue
524 fInitPoints[1] = p;
525 return;
526 }
527
528 fFirstPoint = fInitPoints[0];
529 fFirstVertex = fPositions.count();
530 SkScalar z = fTransformedHeightFunc(fFirstPoint);
531 fFirstNormal = normal;
532 fFirstNormal *= this->offset(z);
533
534 fPrevNormal = fFirstNormal;
535 fPrevPoint = fFirstPoint;
536 fPrevUmbraIndex = fFirstVertex;
537
538 *fPositions.push() = fFirstPoint;
539 *fColors.push() = this->umbraColor(z);
540 *fPositions.push() = fFirstPoint + fFirstNormal;
541 *fColors.push() = fPenumbraColor;
542 if (fTransparent) {
543 fPositions[0] += fFirstPoint;
544 fCentroidCount = 1;
545 }
546
547 // add the first quad
548 z = fTransformedHeightFunc(fInitPoints[1]);
549 fRadius = this->offset(z);
550 fUmbraColor = this->umbraColor(z);
551 normal *= fRadius;
552 this->addEdge(fInitPoints[1], normal);
553
554 // to ensure we skip this block next time
555 *fInitPoints.push() = p;
556 }
557
558 SkVector normal;
559 if (compute_normal(fPositions[fPrevUmbraIndex], p, fDirection, &normal)) {
560 SkVector scaledNormal = normal;
561 scaledNormal *= fRadius;
562 this->addArc(scaledNormal, true);
563 SkScalar z = fTransformedHeightFunc(p);
564 fRadius = this->offset(z);
565 fUmbraColor = this->umbraColor(z);
566 normal *= fRadius;
567 this->addEdge(p, normal);
568 }
569 }
570
addEdge(const SkPoint & nextPoint,const SkVector & nextNormal)571 void SkAmbientShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal) {
572 // make sure we don't end up with a sharp alpha edge along the quad diagonal
573 if (fColors[fPrevUmbraIndex] != fUmbraColor &&
574 nextPoint.distanceToSqd(fPositions[fPrevUmbraIndex]) > kMaxEdgeLenSqr) {
575 SkPoint centerPoint = fPositions[fPrevUmbraIndex] + nextPoint;
576 centerPoint *= 0.5f;
577 *fPositions.push() = centerPoint;
578 *fColors.push() = SkPMLerp(fUmbraColor, fColors[fPrevUmbraIndex], 128);
579 SkVector midNormal = fPrevNormal + nextNormal;
580 midNormal *= 0.5f;
581 *fPositions.push() = centerPoint + midNormal;
582 *fColors.push() = fPenumbraColor;
583
584 // set triangularization to get best interpolation of color
585 if (fColors[fPrevUmbraIndex] > fColors[fPositions.count() - 2]) {
586 *fIndices.push() = fPrevUmbraIndex;
587 *fIndices.push() = fPositions.count() - 3;
588 *fIndices.push() = fPositions.count() - 2;
589
590 *fIndices.push() = fPositions.count() - 3;
591 *fIndices.push() = fPositions.count() - 1;
592 *fIndices.push() = fPositions.count() - 2;
593 } else {
594 *fIndices.push() = fPrevUmbraIndex;
595 *fIndices.push() = fPositions.count() - 2;
596 *fIndices.push() = fPositions.count() - 1;
597
598 *fIndices.push() = fPrevUmbraIndex;
599 *fIndices.push() = fPositions.count() - 1;
600 *fIndices.push() = fPositions.count() - 3;
601 }
602
603 fPrevUmbraIndex = fPositions.count() - 2;
604 }
605
606 // add next quad
607 *fPositions.push() = nextPoint;
608 *fColors.push() = fUmbraColor;
609 *fPositions.push() = nextPoint + nextNormal;
610 *fColors.push() = fPenumbraColor;
611
612 // set triangularization to get best interpolation of color
613 if (fColors[fPrevUmbraIndex] > fColors[fPositions.count() - 2]) {
614 *fIndices.push() = fPrevUmbraIndex;
615 *fIndices.push() = fPositions.count() - 3;
616 *fIndices.push() = fPositions.count() - 2;
617
618 *fIndices.push() = fPositions.count() - 3;
619 *fIndices.push() = fPositions.count() - 1;
620 *fIndices.push() = fPositions.count() - 2;
621 } else {
622 *fIndices.push() = fPrevUmbraIndex;
623 *fIndices.push() = fPositions.count() - 2;
624 *fIndices.push() = fPositions.count() - 1;
625
626 *fIndices.push() = fPrevUmbraIndex;
627 *fIndices.push() = fPositions.count() - 1;
628 *fIndices.push() = fPositions.count() - 3;
629 }
630
631 // if transparent, add point to first one in array and add to center fan
632 if (fTransparent) {
633 fPositions[0] += nextPoint;
634 ++fCentroidCount;
635
636 *fIndices.push() = 0;
637 *fIndices.push() = fPrevUmbraIndex;
638 *fIndices.push() = fPositions.count() - 2;
639 }
640
641 fPrevUmbraIndex = fPositions.count() - 2;
642 fPrevNormal = nextNormal;
643 fPrevPoint = nextPoint;
644 }
645
646 ///////////////////////////////////////////////////////////////////////////////////////////////////
647
648 class SkSpotShadowTessellator : public SkBaseShadowTessellator {
649 public:
650 SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm,
651 SkShadowTessellator::HeightFunc heightFunc,
652 const SkPoint3& lightPos, SkScalar lightRadius,
653 SkScalar spotAlpha, bool transparent);
654
655 private:
656 void computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
657 const SkMatrix& shadowTransform);
658 void computeClipVectorsAndTestCentroid();
659 bool clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint);
660 int getClosestUmbraPoint(const SkPoint& point);
661
662 void handleLine(const SkPoint& p) override;
663 void handlePolyPoint(const SkPoint& p);
664
665 void mapPoints(SkScalar scale, const SkVector& xlate, SkPoint* pts, int count);
666 bool addInnerPoint(const SkPoint& pathPoint);
667 void addEdge(const SkVector& nextPoint, const SkVector& nextNormal);
668
offset(SkScalar z)669 SkScalar offset(SkScalar z) {
670 float zRatio = SkTPin(z / (fLightZ - z), 0.0f, 0.95f);
671 return fLightRadius*zRatio;
672 }
673
674 SkScalar fLightZ;
675 SkScalar fLightRadius;
676 SkScalar fOffsetAdjust;
677
678 SkTDArray<SkPoint> fClipPolygon;
679 SkTDArray<SkVector> fClipVectors;
680 SkPoint fCentroid;
681 SkScalar fArea;
682
683 SkTDArray<SkPoint> fPathPolygon;
684 SkTDArray<SkPoint> fUmbraPolygon;
685 int fCurrClipPoint;
686 int fCurrUmbraPoint;
687 bool fPrevUmbraOutside;
688 bool fFirstUmbraOutside;
689 bool fValidUmbra;
690
691 typedef SkBaseShadowTessellator INHERITED;
692 };
693
SkSpotShadowTessellator(const SkPath & path,const SkMatrix & ctm,SkShadowTessellator::HeightFunc heightFunc,const SkPoint3 & lightPos,SkScalar lightRadius,SkScalar spotAlpha,bool transparent)694 SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm,
695 SkShadowTessellator::HeightFunc heightFunc,
696 const SkPoint3& lightPos, SkScalar lightRadius,
697 SkScalar spotAlpha, bool transparent)
698 : INHERITED(heightFunc, transparent)
699 , fLightZ(lightPos.fZ)
700 , fLightRadius(lightRadius)
701 , fOffsetAdjust(0)
702 , fCurrClipPoint(0)
703 , fPrevUmbraOutside(false)
704 , fFirstUmbraOutside(false)
705 , fValidUmbra(true) {
706
707 // make sure we're not below the canvas plane
708 if (this->setZOffset(path.getBounds(), ctm.hasPerspective())) {
709 // Adjust light height and radius
710 fLightRadius *= (fLightZ + fZOffset) / fLightZ;
711 fLightZ += fZOffset;
712 }
713
714 // Set radius and colors
715 SkPoint center = SkPoint::Make(path.getBounds().centerX(), path.getBounds().centerY());
716 SkScalar occluderHeight = heightFunc(center.fX, center.fY) + fZOffset;
717 float zRatio = SkTPin(occluderHeight / (fLightZ - occluderHeight), 0.0f, 0.95f);
718 SkScalar radius = lightRadius * zRatio;
719 fRadius = radius;
720 fUmbraColor = SkColorSetARGB(255, 0, spotAlpha * 255.9999f, 255);
721 fPenumbraColor = SkColorSetARGB(255, 0, spotAlpha * 255.9999f, 0);
722
723 // Compute the scale and translation for the spot shadow.
724 SkMatrix shadowTransform;
725 if (!ctm.hasPerspective()) {
726 SkScalar scale = fLightZ / (fLightZ - occluderHeight);
727 SkVector translate = SkVector::Make(-zRatio * lightPos.fX, -zRatio * lightPos.fY);
728 shadowTransform.setScaleTranslate(scale, scale, translate.fX, translate.fY);
729 } else {
730 // For perspective, we have a scale, a z-shear, and another projective divide --
731 // this varies at each point so we can't use an affine transform.
732 // We'll just apply this to each generated point in turn.
733 shadowTransform.reset();
734 // Also can't cull the center (for now).
735 fTransparent = true;
736 }
737 SkMatrix fullTransform = SkMatrix::Concat(shadowTransform, ctm);
738
739 // Set up our reverse mapping
740 this->setTransformedHeightFunc(fullTransform);
741
742 // TODO: calculate these reserves better
743 // Penumbra ring: 3*numPts
744 // Umbra ring: numPts
745 // Inner ring: numPts
746 fPositions.setReserve(5 * path.countPoints());
747 fColors.setReserve(5 * path.countPoints());
748 // Penumbra ring: 12*numPts
749 // Umbra ring: 3*numPts
750 fIndices.setReserve(15 * path.countPoints());
751 fClipPolygon.setReserve(path.countPoints());
752
753 // compute rough clip bounds for umbra, plus offset polygon, plus centroid
754 this->computeClipAndPathPolygons(path, ctm, shadowTransform);
755 if (fClipPolygon.count() < 3 || fPathPolygon.count() < 3) {
756 return;
757 }
758
759 // check to see if umbra collapses
760 SkScalar minDistSq = fCentroid.distanceToLineSegmentBetweenSqd(fPathPolygon[0],
761 fPathPolygon[1]);
762 SkRect bounds;
763 bounds.setBounds(&fPathPolygon[0], fPathPolygon.count());
764 for (int i = 1; i < fPathPolygon.count(); ++i) {
765 int j = i + 1;
766 if (i == fPathPolygon.count() - 1) {
767 j = 0;
768 }
769 SkPoint currPoint = fPathPolygon[i];
770 SkPoint nextPoint = fPathPolygon[j];
771 SkScalar distSq = fCentroid.distanceToLineSegmentBetweenSqd(currPoint, nextPoint);
772 if (distSq < minDistSq) {
773 minDistSq = distSq;
774 }
775 }
776 static constexpr auto kTolerance = 1.0e-2f;
777 if (minDistSq < (radius + kTolerance)*(radius + kTolerance)) {
778 // if the umbra would collapse, we back off a bit on inner blur and adjust the alpha
779 SkScalar newRadius = SkScalarSqrt(minDistSq) - kTolerance;
780 fOffsetAdjust = newRadius - radius;
781 SkScalar ratio = 256 * newRadius / radius;
782 // they aren't PMColors, but the interpolation algorithm is the same
783 fUmbraColor = SkPMLerp(fUmbraColor, fPenumbraColor, (unsigned)ratio);
784 radius = newRadius;
785 }
786
787 // compute vectors for clip tests
788 this->computeClipVectorsAndTestCentroid();
789
790 // generate inner ring
791 if (!SkInsetConvexPolygon(&fPathPolygon[0], fPathPolygon.count(), radius,
792 &fUmbraPolygon)) {
793 // this shouldn't happen, but just in case we'll inset using the centroid
794 fValidUmbra = false;
795 }
796
797 // walk around the path polygon, generate outer ring and connect to inner ring
798 if (fTransparent) {
799 *fPositions.push() = fCentroid;
800 *fColors.push() = fUmbraColor;
801 }
802 fCurrUmbraPoint = 0;
803 for (int i = 0; i < fPathPolygon.count(); ++i) {
804 this->handlePolyPoint(fPathPolygon[i]);
805 }
806
807 if (!this->indexCount()) {
808 return;
809 }
810
811 // finish up the final verts
812 SkVector normal;
813 if (compute_normal(fPrevPoint, fFirstPoint, fDirection, &normal)) {
814 normal *= fRadius;
815 this->addArc(normal, true);
816
817 // add to center fan
818 if (fTransparent) {
819 *fIndices.push() = 0;
820 *fIndices.push() = fPrevUmbraIndex;
821 *fIndices.push() = fFirstVertex;
822 // or to clip ring
823 } else {
824 if (fFirstUmbraOutside) {
825 *fIndices.push() = fPrevUmbraIndex;
826 *fIndices.push() = fFirstVertex;
827 *fIndices.push() = fFirstVertex + 1;
828 if (fPrevUmbraOutside) {
829 // fill out quad
830 *fIndices.push() = fPrevUmbraIndex;
831 *fIndices.push() = fFirstVertex + 1;
832 *fIndices.push() = fPrevUmbraIndex + 1;
833 }
834 } else if (fPrevUmbraOutside) {
835 // add tri
836 *fIndices.push() = fPrevUmbraIndex;
837 *fIndices.push() = fFirstVertex;
838 *fIndices.push() = fPrevUmbraIndex + 1;
839 }
840 }
841
842 // add final edge
843 *fPositions.push() = fFirstPoint + normal;
844 *fColors.push() = fPenumbraColor;
845
846 *fIndices.push() = fPrevUmbraIndex;
847 *fIndices.push() = fPositions.count() - 2;
848 *fIndices.push() = fFirstVertex;
849
850 *fIndices.push() = fPositions.count() - 2;
851 *fIndices.push() = fPositions.count() - 1;
852 *fIndices.push() = fFirstVertex;
853
854 fPrevNormal = normal;
855 }
856
857 // final fan
858 if (fPositions.count() >= 3) {
859 fPrevUmbraIndex = fFirstVertex;
860 fPrevPoint = fFirstPoint;
861 this->addArc(fFirstNormal, false);
862
863 *fIndices.push() = fFirstVertex;
864 *fIndices.push() = fPositions.count() - 1;
865 if (fFirstUmbraOutside) {
866 *fIndices.push() = fFirstVertex + 2;
867 } else {
868 *fIndices.push() = fFirstVertex + 1;
869 }
870 }
871
872 if (ctm.hasPerspective()) {
873 for (int i = 0; i < fPositions.count(); ++i) {
874 SkScalar pathZ = fTransformedHeightFunc(fPositions[i]);
875 SkScalar factor = SkScalarInvert(fLightZ - pathZ);
876 fPositions[i].fX = (fPositions[i].fX*fLightZ - lightPos.fX*pathZ)*factor;
877 fPositions[i].fY = (fPositions[i].fY*fLightZ - lightPos.fY*pathZ)*factor;
878 }
879 #ifdef DRAW_CENTROID
880 SkScalar pathZ = fTransformedHeightFunc(fCentroid);
881 SkScalar factor = SkScalarInvert(fLightZ - pathZ);
882 fCentroid.fX = (fCentroid.fX*fLightZ - lightPos.fX*pathZ)*factor;
883 fCentroid.fY = (fCentroid.fY*fLightZ - lightPos.fY*pathZ)*factor;
884 #endif
885 }
886 #ifdef DRAW_CENTROID
887 *fPositions.push() = fCentroid + SkVector::Make(-2, -2);
888 *fColors.push() = SkColorSetARGB(255, 0, 255, 255);
889 *fPositions.push() = fCentroid + SkVector::Make(2, -2);
890 *fColors.push() = SkColorSetARGB(255, 0, 255, 255);
891 *fPositions.push() = fCentroid + SkVector::Make(-2, 2);
892 *fColors.push() = SkColorSetARGB(255, 0, 255, 255);
893 *fPositions.push() = fCentroid + SkVector::Make(2, 2);
894 *fColors.push() = SkColorSetARGB(255, 0, 255, 255);
895
896 *fIndices.push() = fPositions.count() - 4;
897 *fIndices.push() = fPositions.count() - 2;
898 *fIndices.push() = fPositions.count() - 1;
899
900 *fIndices.push() = fPositions.count() - 4;
901 *fIndices.push() = fPositions.count() - 1;
902 *fIndices.push() = fPositions.count() - 3;
903 #endif
904
905 fSucceeded = true;
906 }
907
computeClipAndPathPolygons(const SkPath & path,const SkMatrix & ctm,const SkMatrix & shadowTransform)908 void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
909 const SkMatrix& shadowTransform) {
910
911 fPathPolygon.setReserve(path.countPoints());
912
913 // Walk around the path and compute clip polygon and path polygon.
914 // Will also accumulate sum of areas for centroid.
915 // For Bezier curves, we compute additional interior points on curve.
916 SkPath::Iter iter(path, true);
917 SkPoint pts[4];
918 SkPath::Verb verb;
919
920 fClipPolygon.reset();
921
922 // init centroid
923 fCentroid = SkPoint::Make(0, 0);
924 fArea = 0;
925
926 // coefficients to compute cubic Bezier at t = 5/16
927 static constexpr SkScalar kA = 0.32495117187f;
928 static constexpr SkScalar kB = 0.44311523437f;
929 static constexpr SkScalar kC = 0.20141601562f;
930 static constexpr SkScalar kD = 0.03051757812f;
931
932 SkPoint curvePoint;
933 SkScalar w;
934 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
935 switch (verb) {
936 case SkPath::kLine_Verb:
937 ctm.mapPoints(&pts[1], 1);
938 *fClipPolygon.push() = pts[1];
939 this->INHERITED::handleLine(shadowTransform, &pts[1]);
940 break;
941 case SkPath::kQuad_Verb:
942 ctm.mapPoints(pts, 3);
943 // point at t = 1/2
944 curvePoint.fX = 0.25f*pts[0].fX + 0.5f*pts[1].fX + 0.25f*pts[2].fX;
945 curvePoint.fY = 0.25f*pts[0].fY + 0.5f*pts[1].fY + 0.25f*pts[2].fY;
946 *fClipPolygon.push() = curvePoint;
947 *fClipPolygon.push() = pts[2];
948 this->handleQuad(shadowTransform, pts);
949 break;
950 case SkPath::kConic_Verb:
951 ctm.mapPoints(pts, 3);
952 w = iter.conicWeight();
953 // point at t = 1/2
954 curvePoint.fX = 0.25f*pts[0].fX + w*0.5f*pts[1].fX + 0.25f*pts[2].fX;
955 curvePoint.fY = 0.25f*pts[0].fY + w*0.5f*pts[1].fY + 0.25f*pts[2].fY;
956 curvePoint *= SkScalarInvert(0.5f + 0.5f*w);
957 *fClipPolygon.push() = curvePoint;
958 *fClipPolygon.push() = pts[2];
959 this->handleConic(shadowTransform, pts, w);
960 break;
961 case SkPath::kCubic_Verb:
962 ctm.mapPoints(pts, 4);
963 // point at t = 5/16
964 curvePoint.fX = kA*pts[0].fX + kB*pts[1].fX + kC*pts[2].fX + kD*pts[3].fX;
965 curvePoint.fY = kA*pts[0].fY + kB*pts[1].fY + kC*pts[2].fY + kD*pts[3].fY;
966 *fClipPolygon.push() = curvePoint;
967 // point at t = 11/16
968 curvePoint.fX = kD*pts[0].fX + kC*pts[1].fX + kB*pts[2].fX + kA*pts[3].fX;
969 curvePoint.fY = kD*pts[0].fY + kC*pts[1].fY + kB*pts[2].fY + kA*pts[3].fY;
970 *fClipPolygon.push() = curvePoint;
971 *fClipPolygon.push() = pts[3];
972 this->handleCubic(shadowTransform, pts);
973 break;
974 case SkPath::kMove_Verb:
975 case SkPath::kClose_Verb:
976 case SkPath::kDone_Verb:
977 break;
978 default:
979 SkDEBUGFAIL("unknown verb");
980 }
981 }
982
983 // finish centroid
984 if (fPathPolygon.count() > 0) {
985 SkPoint currPoint = fPathPolygon[fPathPolygon.count() - 1];
986 SkPoint nextPoint = fPathPolygon[0];
987 SkScalar quadArea = currPoint.cross(nextPoint);
988 fCentroid.fX += (currPoint.fX + nextPoint.fX) * quadArea;
989 fCentroid.fY += (currPoint.fY + nextPoint.fY) * quadArea;
990 fArea += quadArea;
991 fCentroid *= SK_Scalar1 / (3 * fArea);
992 }
993
994 fCurrClipPoint = fClipPolygon.count() - 1;
995 }
996
computeClipVectorsAndTestCentroid()997 void SkSpotShadowTessellator::computeClipVectorsAndTestCentroid() {
998 SkASSERT(fClipPolygon.count() >= 3);
999
1000 // init clip vectors
1001 SkVector v0 = fClipPolygon[1] - fClipPolygon[0];
1002 *fClipVectors.push() = v0;
1003
1004 // init centroid check
1005 bool hiddenCentroid = true;
1006 SkVector v1 = fCentroid - fClipPolygon[0];
1007 SkScalar initCross = v0.cross(v1);
1008
1009 for (int p = 1; p < fClipPolygon.count(); ++p) {
1010 // add to clip vectors
1011 v0 = fClipPolygon[(p + 1) % fClipPolygon.count()] - fClipPolygon[p];
1012 *fClipVectors.push() = v0;
1013 // Determine if transformed centroid is inside clipPolygon.
1014 v1 = fCentroid - fClipPolygon[p];
1015 if (initCross*v0.cross(v1) <= 0) {
1016 hiddenCentroid = false;
1017 }
1018 }
1019 SkASSERT(fClipVectors.count() == fClipPolygon.count());
1020
1021 fTransparent = fTransparent || !hiddenCentroid;
1022 }
1023
clipUmbraPoint(const SkPoint & umbraPoint,const SkPoint & centroid,SkPoint * clipPoint)1024 bool SkSpotShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid,
1025 SkPoint* clipPoint) {
1026 SkVector segmentVector = centroid - umbraPoint;
1027
1028 int startClipPoint = fCurrClipPoint;
1029 do {
1030 SkVector dp = umbraPoint - fClipPolygon[fCurrClipPoint];
1031 SkScalar denom = fClipVectors[fCurrClipPoint].cross(segmentVector);
1032 SkScalar t_num = dp.cross(segmentVector);
1033 // if line segments are nearly parallel
1034 if (SkScalarNearlyZero(denom)) {
1035 // and collinear
1036 if (SkScalarNearlyZero(t_num)) {
1037 return false;
1038 }
1039 // otherwise are separate, will try the next poly segment
1040 // else if crossing lies within poly segment
1041 } else if (t_num >= 0 && t_num <= denom) {
1042 SkScalar s_num = dp.cross(fClipVectors[fCurrClipPoint]);
1043 // if umbra point is inside the clip polygon
1044 if (s_num >= 0 && s_num <= denom) {
1045 segmentVector *= s_num/denom;
1046 *clipPoint = umbraPoint + segmentVector;
1047 return true;
1048 }
1049 }
1050 fCurrClipPoint = (fCurrClipPoint + 1) % fClipPolygon.count();
1051 } while (fCurrClipPoint != startClipPoint);
1052
1053 return false;
1054 }
1055
getClosestUmbraPoint(const SkPoint & p)1056 int SkSpotShadowTessellator::getClosestUmbraPoint(const SkPoint& p) {
1057 SkScalar minDistance = p.distanceToSqd(fUmbraPolygon[fCurrUmbraPoint]);
1058 int index = fCurrUmbraPoint;
1059 int dir = 1;
1060 int next = (index + dir) % fUmbraPolygon.count();
1061
1062 // init travel direction
1063 SkScalar distance = p.distanceToSqd(fUmbraPolygon[next]);
1064 if (distance < minDistance) {
1065 index = next;
1066 minDistance = distance;
1067 } else {
1068 dir = fUmbraPolygon.count()-1;
1069 }
1070
1071 // iterate until we find a point that increases the distance
1072 next = (index + dir) % fUmbraPolygon.count();
1073 distance = p.distanceToSqd(fUmbraPolygon[next]);
1074 while (distance < minDistance) {
1075 index = next;
1076 minDistance = distance;
1077 next = (index + dir) % fUmbraPolygon.count();
1078 distance = p.distanceToSqd(fUmbraPolygon[next]);
1079 }
1080
1081 fCurrUmbraPoint = index;
1082 return index;
1083 }
1084
mapPoints(SkScalar scale,const SkVector & xlate,SkPoint * pts,int count)1085 void SkSpotShadowTessellator::mapPoints(SkScalar scale, const SkVector& xlate,
1086 SkPoint* pts, int count) {
1087 // TODO: vectorize
1088 for (int i = 0; i < count; ++i) {
1089 pts[i] *= scale;
1090 pts[i] += xlate;
1091 }
1092 }
1093
duplicate_pt(const SkPoint & p0,const SkPoint & p1)1094 static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) {
1095 static constexpr SkScalar kClose = (SK_Scalar1 / 16);
1096 static constexpr SkScalar kCloseSqd = kClose*kClose;
1097
1098 SkScalar distSq = p0.distanceToSqd(p1);
1099 return distSq < kCloseSqd;
1100 }
1101
is_collinear(const SkPoint & p0,const SkPoint & p1,const SkPoint & p2)1102 static bool is_collinear(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
1103 SkVector v0 = p1 - p0;
1104 SkVector v1 = p2 - p0;
1105 return (SkScalarNearlyZero(v0.cross(v1)));
1106 }
1107
handleLine(const SkPoint & p)1108 void SkSpotShadowTessellator::handleLine(const SkPoint& p) {
1109 // remove coincident points and add to centroid
1110 if (fPathPolygon.count() > 0) {
1111 const SkPoint& lastPoint = fPathPolygon[fPathPolygon.count() - 1];
1112 if (duplicate_pt(p, lastPoint)) {
1113 return;
1114 }
1115 SkScalar quadArea = lastPoint.cross(p);
1116 fCentroid.fX += (p.fX + lastPoint.fX) * quadArea;
1117 fCentroid.fY += (p.fY + lastPoint.fY) * quadArea;
1118 fArea += quadArea;
1119 }
1120
1121 // try to remove collinear points
1122 if (fPathPolygon.count() > 1 && is_collinear(fPathPolygon[fPathPolygon.count()-2],
1123 fPathPolygon[fPathPolygon.count()-1],
1124 p)) {
1125 fPathPolygon[fPathPolygon.count() - 1] = p;
1126 } else {
1127 *fPathPolygon.push() = p;
1128 }
1129 }
1130
handlePolyPoint(const SkPoint & p)1131 void SkSpotShadowTessellator::handlePolyPoint(const SkPoint& p) {
1132 if (fInitPoints.count() < 2) {
1133 *fInitPoints.push() = p;
1134 return;
1135 }
1136
1137 if (fInitPoints.count() == 2) {
1138 // determine if cw or ccw
1139 SkVector v0 = fInitPoints[1] - fInitPoints[0];
1140 SkVector v1 = p - fInitPoints[0];
1141 SkScalar perpDot = v0.cross(v1);
1142 if (SkScalarNearlyZero(perpDot)) {
1143 // nearly parallel, just treat as straight line and continue
1144 fInitPoints[1] = p;
1145 return;
1146 }
1147
1148 // if perpDot > 0, winding is ccw
1149 fDirection = (perpDot > 0) ? -1 : 1;
1150
1151 // add first quad
1152 if (!compute_normal(fInitPoints[0], fInitPoints[1], fDirection, &fFirstNormal)) {
1153 // first two points are incident, make the third point the second and continue
1154 fInitPoints[1] = p;
1155 return;
1156 }
1157
1158 fFirstNormal *= fRadius;
1159 fFirstPoint = fInitPoints[0];
1160 fFirstVertex = fPositions.count();
1161 fPrevNormal = fFirstNormal;
1162 fPrevPoint = fFirstPoint;
1163 fPrevUmbraIndex = fFirstVertex;
1164
1165 this->addInnerPoint(fFirstPoint);
1166
1167 if (!fTransparent) {
1168 SkPoint clipPoint;
1169 bool isOutside = this->clipUmbraPoint(fPositions[fFirstVertex], fCentroid, &clipPoint);
1170 if (isOutside) {
1171 *fPositions.push() = clipPoint;
1172 *fColors.push() = fUmbraColor;
1173 }
1174 fPrevUmbraOutside = isOutside;
1175 fFirstUmbraOutside = isOutside;
1176 }
1177
1178 SkPoint newPoint = fFirstPoint + fFirstNormal;
1179 *fPositions.push() = newPoint;
1180 *fColors.push() = fPenumbraColor;
1181 this->addEdge(fInitPoints[1], fFirstNormal);
1182
1183 // to ensure we skip this block next time
1184 *fInitPoints.push() = p;
1185 }
1186
1187 SkVector normal;
1188 if (compute_normal(fPrevPoint, p, fDirection, &normal)) {
1189 normal *= fRadius;
1190 this->addArc(normal, true);
1191 this->addEdge(p, normal);
1192 }
1193 }
1194
addInnerPoint(const SkPoint & pathPoint)1195 bool SkSpotShadowTessellator::addInnerPoint(const SkPoint& pathPoint) {
1196 SkPoint umbraPoint;
1197 if (!fValidUmbra) {
1198 SkVector v = fCentroid - pathPoint;
1199 v *= 0.95f;
1200 umbraPoint = pathPoint + v;
1201 } else {
1202 umbraPoint = fUmbraPolygon[this->getClosestUmbraPoint(pathPoint)];
1203 }
1204
1205 fPrevPoint = pathPoint;
1206
1207 // merge "close" points
1208 if (fPrevUmbraIndex == fFirstVertex ||
1209 !duplicate_pt(umbraPoint, fPositions[fPrevUmbraIndex])) {
1210 *fPositions.push() = umbraPoint;
1211 *fColors.push() = fUmbraColor;
1212
1213 return false;
1214 } else {
1215 return true;
1216 }
1217 }
1218
addEdge(const SkPoint & nextPoint,const SkVector & nextNormal)1219 void SkSpotShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal) {
1220 // add next umbra point
1221 bool duplicate = this->addInnerPoint(nextPoint);
1222 int prevPenumbraIndex = duplicate ? fPositions.count()-1 : fPositions.count()-2;
1223 int currUmbraIndex = duplicate ? fPrevUmbraIndex : fPositions.count()-1;
1224
1225 if (!duplicate) {
1226 // add to center fan if transparent or centroid showing
1227 if (fTransparent) {
1228 *fIndices.push() = 0;
1229 *fIndices.push() = fPrevUmbraIndex;
1230 *fIndices.push() = currUmbraIndex;
1231 // otherwise add to clip ring
1232 } else {
1233 SkPoint clipPoint;
1234 bool isOutside = this->clipUmbraPoint(fPositions[currUmbraIndex], fCentroid,
1235 &clipPoint);
1236 if (isOutside) {
1237 *fPositions.push() = clipPoint;
1238 *fColors.push() = fUmbraColor;
1239
1240 *fIndices.push() = fPrevUmbraIndex;
1241 *fIndices.push() = currUmbraIndex;
1242 *fIndices.push() = currUmbraIndex + 1;
1243 if (fPrevUmbraOutside) {
1244 // fill out quad
1245 *fIndices.push() = fPrevUmbraIndex;
1246 *fIndices.push() = currUmbraIndex + 1;
1247 *fIndices.push() = fPrevUmbraIndex + 1;
1248 }
1249 } else if (fPrevUmbraOutside) {
1250 // add tri
1251 *fIndices.push() = fPrevUmbraIndex;
1252 *fIndices.push() = currUmbraIndex;
1253 *fIndices.push() = fPrevUmbraIndex + 1;
1254 }
1255 fPrevUmbraOutside = isOutside;
1256 }
1257 }
1258
1259 // add next penumbra point and quad
1260 SkPoint newPoint = nextPoint + nextNormal;
1261 *fPositions.push() = newPoint;
1262 *fColors.push() = fPenumbraColor;
1263
1264 if (!duplicate) {
1265 *fIndices.push() = fPrevUmbraIndex;
1266 *fIndices.push() = prevPenumbraIndex;
1267 *fIndices.push() = currUmbraIndex;
1268 }
1269
1270 *fIndices.push() = prevPenumbraIndex;
1271 *fIndices.push() = fPositions.count() - 1;
1272 *fIndices.push() = currUmbraIndex;
1273
1274 fPrevUmbraIndex = currUmbraIndex;
1275 fPrevNormal = nextNormal;
1276 }
1277
1278 ///////////////////////////////////////////////////////////////////////////////////////////////////
1279
MakeAmbient(const SkPath & path,const SkMatrix & ctm,HeightFunc heightFunc,SkScalar ambientAlpha,bool transparent)1280 sk_sp<SkVertices> SkShadowTessellator::MakeAmbient(const SkPath& path, const SkMatrix& ctm,
1281 HeightFunc heightFunc, SkScalar ambientAlpha,
1282 bool transparent) {
1283 SkAmbientShadowTessellator ambientTess(path, ctm, heightFunc, ambientAlpha, transparent);
1284 return ambientTess.releaseVertices();
1285 }
1286
MakeSpot(const SkPath & path,const SkMatrix & ctm,HeightFunc heightFunc,const SkPoint3 & lightPos,SkScalar lightRadius,SkScalar spotAlpha,bool transparent)1287 sk_sp<SkVertices> SkShadowTessellator::MakeSpot(const SkPath& path, const SkMatrix& ctm,
1288 HeightFunc heightFunc,
1289 const SkPoint3& lightPos, SkScalar lightRadius,
1290 SkScalar spotAlpha, bool transparent) {
1291 SkSpotShadowTessellator spotTess(path, ctm, heightFunc, lightPos, lightRadius,
1292 spotAlpha, transparent);
1293 return spotTess.releaseVertices();
1294 }
1295