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