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 "SkColorData.h"
10 #include "SkDrawShadowInfo.h"
11 #include "SkGeometry.h"
12 #include "SkInsetConvexPolygon.h"
13 #include "SkPath.h"
14 #include "SkPoint3.h"
15 #include "SkPointPriv.h"
16 #include "SkVertices.h"
17
18 #if SK_SUPPORT_GPU
19 #include "GrPathUtils.h"
20 #endif
21
22
23 /**
24 * Base class
25 */
26 class SkBaseShadowTessellator {
27 public:
28 SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent);
~SkBaseShadowTessellator()29 virtual ~SkBaseShadowTessellator() {}
30
releaseVertices()31 sk_sp<SkVertices> releaseVertices() {
32 if (!fSucceeded) {
33 return nullptr;
34 }
35 return SkVertices::MakeCopy(SkVertices::kTriangles_VertexMode, this->vertexCount(),
36 fPositions.begin(), nullptr, fColors.begin(),
37 this->indexCount(), fIndices.begin());
38 }
39
40 protected:
41 static constexpr auto kMinHeight = 0.1f;
42
vertexCount() const43 int vertexCount() const { return fPositions.count(); }
indexCount() const44 int indexCount() const { return fIndices.count(); }
45
46 bool setZOffset(const SkRect& bounds, bool perspective);
47
48 virtual void handleLine(const SkPoint& p) = 0;
49 void handleLine(const SkMatrix& m, SkPoint* p);
50
51 void handleQuad(const SkPoint pts[3]);
52 void handleQuad(const SkMatrix& m, SkPoint pts[3]);
53
54 void handleCubic(const SkMatrix& m, SkPoint pts[4]);
55
56 void handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w);
57
58 bool setTransformedHeightFunc(const SkMatrix& ctm);
59
60 bool addArc(const SkVector& nextNormal, bool finishArc);
61
heightFunc(SkScalar x,SkScalar y)62 SkScalar heightFunc(SkScalar x, SkScalar y) {
63 return fZPlaneParams.fX*x + fZPlaneParams.fY*y + fZPlaneParams.fZ;
64 }
65
66 SkPoint3 fZPlaneParams;
67 std::function<SkScalar(const SkPoint&)> fTransformedHeightFunc;
68 SkScalar fZOffset;
69 // members for perspective height function
70 SkPoint3 fTransformedZParams;
71 SkScalar fPartialDeterminants[3];
72
73 // first two points
74 SkTDArray<SkPoint> fInitPoints;
75 // temporary buffer
76 SkTDArray<SkPoint> fPointBuffer;
77
78 SkTDArray<SkPoint> fPositions;
79 SkTDArray<SkColor> fColors;
80 SkTDArray<uint16_t> fIndices;
81
82 int fFirstVertexIndex;
83 SkVector fFirstOutset;
84 SkPoint fFirstPoint;
85
86 bool fSucceeded;
87 bool fTransparent;
88
89 SkColor fUmbraColor;
90 SkColor fPenumbraColor;
91
92 SkScalar fRadius;
93 SkScalar fDirection;
94 int fPrevUmbraIndex;
95 SkVector fPrevOutset;
96 SkPoint fPrevPoint;
97 };
98
compute_normal(const SkPoint & p0,const SkPoint & p1,SkScalar dir,SkVector * newNormal)99 static bool compute_normal(const SkPoint& p0, const SkPoint& p1, SkScalar dir,
100 SkVector* newNormal) {
101 SkVector normal;
102 // compute perpendicular
103 normal.fX = p0.fY - p1.fY;
104 normal.fY = p1.fX - p0.fX;
105 normal *= dir;
106 if (!normal.normalize()) {
107 return false;
108 }
109 *newNormal = normal;
110 return true;
111 }
112
compute_radial_steps(const SkVector & v1,const SkVector & v2,SkScalar r,SkScalar * rotSin,SkScalar * rotCos,int * n)113 static void compute_radial_steps(const SkVector& v1, const SkVector& v2, SkScalar r,
114 SkScalar* rotSin, SkScalar* rotCos, int* n) {
115 const SkScalar kRecipPixelsPerArcSegment = 0.125f;
116
117 SkScalar rCos = v1.dot(v2);
118 SkScalar rSin = v1.cross(v2);
119 SkScalar theta = SkScalarATan2(rSin, rCos);
120
121 int steps = SkScalarFloorToInt(r*theta*kRecipPixelsPerArcSegment);
122
123 SkScalar dTheta = theta / steps;
124 *rotSin = SkScalarSinCos(dTheta, rotCos);
125 *n = steps;
126 }
127
SkBaseShadowTessellator(const SkPoint3 & zPlaneParams,bool transparent)128 SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent)
129 : fZPlaneParams(zPlaneParams)
130 , fZOffset(0)
131 , fFirstVertexIndex(-1)
132 , fSucceeded(false)
133 , fTransparent(transparent)
134 , fDirection(1)
135 , fPrevUmbraIndex(-1) {
136 fInitPoints.setReserve(3);
137
138 // child classes will set reserve for positions, colors and indices
139 }
140
setZOffset(const SkRect & bounds,bool perspective)141 bool SkBaseShadowTessellator::setZOffset(const SkRect& bounds, bool perspective) {
142 SkScalar minZ = this->heightFunc(bounds.fLeft, bounds.fTop);
143 if (perspective) {
144 SkScalar z = this->heightFunc(bounds.fLeft, bounds.fBottom);
145 if (z < minZ) {
146 minZ = z;
147 }
148 z = this->heightFunc(bounds.fRight, bounds.fTop);
149 if (z < minZ) {
150 minZ = z;
151 }
152 z = this->heightFunc(bounds.fRight, bounds.fBottom);
153 if (z < minZ) {
154 minZ = z;
155 }
156 }
157
158 if (minZ < kMinHeight) {
159 fZOffset = -minZ + kMinHeight;
160 return true;
161 }
162
163 return false;
164 }
165
166 // tesselation tolerance values, in device space pixels
167 #if SK_SUPPORT_GPU
168 static const SkScalar kQuadTolerance = 0.2f;
169 static const SkScalar kCubicTolerance = 0.2f;
170 #endif
171 static const SkScalar kConicTolerance = 0.5f;
172
handleLine(const SkMatrix & m,SkPoint * p)173 void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) {
174 m.mapPoints(p, 1);
175 this->handleLine(*p);
176 }
177
handleQuad(const SkPoint pts[3])178 void SkBaseShadowTessellator::handleQuad(const SkPoint pts[3]) {
179 #if SK_SUPPORT_GPU
180 // TODO: Pull PathUtils out of Ganesh?
181 int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
182 fPointBuffer.setReserve(maxCount);
183 SkPoint* target = fPointBuffer.begin();
184 int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
185 kQuadTolerance, &target, maxCount);
186 fPointBuffer.setCount(count);
187 for (int i = 0; i < count; i++) {
188 this->handleLine(fPointBuffer[i]);
189 }
190 #else
191 // for now, just to draw something
192 this->handleLine(pts[1]);
193 this->handleLine(pts[2]);
194 #endif
195 }
196
handleQuad(const SkMatrix & m,SkPoint pts[3])197 void SkBaseShadowTessellator::handleQuad(const SkMatrix& m, SkPoint pts[3]) {
198 m.mapPoints(pts, 3);
199 this->handleQuad(pts);
200 }
201
handleCubic(const SkMatrix & m,SkPoint pts[4])202 void SkBaseShadowTessellator::handleCubic(const SkMatrix& m, SkPoint pts[4]) {
203 m.mapPoints(pts, 4);
204 #if SK_SUPPORT_GPU
205 // TODO: Pull PathUtils out of Ganesh?
206 int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
207 fPointBuffer.setReserve(maxCount);
208 SkPoint* target = fPointBuffer.begin();
209 int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
210 kCubicTolerance, &target, maxCount);
211 fPointBuffer.setCount(count);
212 for (int i = 0; i < count; i++) {
213 this->handleLine(fPointBuffer[i]);
214 }
215 #else
216 // for now, just to draw something
217 this->handleLine(pts[1]);
218 this->handleLine(pts[2]);
219 this->handleLine(pts[3]);
220 #endif
221 }
222
handleConic(const SkMatrix & m,SkPoint pts[3],SkScalar w)223 void SkBaseShadowTessellator::handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w) {
224 if (m.hasPerspective()) {
225 w = SkConic::TransformW(pts, w, m);
226 }
227 m.mapPoints(pts, 3);
228 SkAutoConicToQuads quadder;
229 const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance);
230 SkPoint lastPoint = *(quads++);
231 int count = quadder.countQuads();
232 for (int i = 0; i < count; ++i) {
233 SkPoint quadPts[3];
234 quadPts[0] = lastPoint;
235 quadPts[1] = quads[0];
236 quadPts[2] = i == count - 1 ? pts[2] : quads[1];
237 this->handleQuad(quadPts);
238 lastPoint = quadPts[2];
239 quads += 2;
240 }
241 }
242
addArc(const SkVector & nextNormal,bool finishArc)243 bool SkBaseShadowTessellator::addArc(const SkVector& nextNormal, bool finishArc) {
244 // fill in fan from previous quad
245 SkScalar rotSin, rotCos;
246 int numSteps;
247 compute_radial_steps(fPrevOutset, nextNormal, fRadius, &rotSin, &rotCos, &numSteps);
248 SkVector prevNormal = fPrevOutset;
249 for (int i = 0; i < numSteps-1; ++i) {
250 SkVector currNormal;
251 currNormal.fX = prevNormal.fX*rotCos - prevNormal.fY*rotSin;
252 currNormal.fY = prevNormal.fY*rotCos + prevNormal.fX*rotSin;
253 *fPositions.push() = fPrevPoint + currNormal;
254 *fColors.push() = fPenumbraColor;
255 *fIndices.push() = fPrevUmbraIndex;
256 *fIndices.push() = fPositions.count() - 1;
257 *fIndices.push() = fPositions.count() - 2;
258
259 prevNormal = currNormal;
260 }
261 if (finishArc && numSteps) {
262 *fPositions.push() = fPrevPoint + nextNormal;
263 *fColors.push() = fPenumbraColor;
264 *fIndices.push() = fPrevUmbraIndex;
265 *fIndices.push() = fPositions.count() - 1;
266 *fIndices.push() = fPositions.count() - 2;
267 }
268 fPrevOutset = nextNormal;
269
270 return (numSteps > 0);
271 }
272
setTransformedHeightFunc(const SkMatrix & ctm)273 bool SkBaseShadowTessellator::setTransformedHeightFunc(const SkMatrix& ctm) {
274 if (SkScalarNearlyZero(fZPlaneParams.fX) && SkScalarNearlyZero(fZPlaneParams.fY)) {
275 fTransformedHeightFunc = [this](const SkPoint& p) {
276 return fZPlaneParams.fZ;
277 };
278 } else {
279 SkMatrix ctmInverse;
280 if (!ctm.invert(&ctmInverse)) {
281 return false;
282 }
283 // multiply by transpose
284 fTransformedZParams = SkPoint3::Make(
285 ctmInverse[SkMatrix::kMScaleX] * fZPlaneParams.fX +
286 ctmInverse[SkMatrix::kMSkewY] * fZPlaneParams.fY +
287 ctmInverse[SkMatrix::kMPersp0] * fZPlaneParams.fZ,
288
289 ctmInverse[SkMatrix::kMSkewX] * fZPlaneParams.fX +
290 ctmInverse[SkMatrix::kMScaleY] * fZPlaneParams.fY +
291 ctmInverse[SkMatrix::kMPersp1] * fZPlaneParams.fZ,
292
293 ctmInverse[SkMatrix::kMTransX] * fZPlaneParams.fX +
294 ctmInverse[SkMatrix::kMTransY] * fZPlaneParams.fY +
295 ctmInverse[SkMatrix::kMPersp2] * fZPlaneParams.fZ
296 );
297
298 if (ctm.hasPerspective()) {
299 // We use Cramer's rule to solve for the W value for a given post-divide X and Y,
300 // so pre-compute those values that are independent of X and Y.
301 // W is det(ctmInverse)/(PD[0]*X + PD[1]*Y + PD[2])
302 fPartialDeterminants[0] = ctm[SkMatrix::kMSkewY] * ctm[SkMatrix::kMPersp1] -
303 ctm[SkMatrix::kMScaleY] * ctm[SkMatrix::kMPersp0];
304 fPartialDeterminants[1] = ctm[SkMatrix::kMPersp0] * ctm[SkMatrix::kMSkewX] -
305 ctm[SkMatrix::kMPersp1] * ctm[SkMatrix::kMScaleX];
306 fPartialDeterminants[2] = ctm[SkMatrix::kMScaleX] * ctm[SkMatrix::kMScaleY] -
307 ctm[SkMatrix::kMSkewX] * ctm[SkMatrix::kMSkewY];
308 SkScalar ctmDeterminant = ctm[SkMatrix::kMTransX] * fPartialDeterminants[0] +
309 ctm[SkMatrix::kMTransY] * fPartialDeterminants[1] +
310 ctm[SkMatrix::kMPersp2] * fPartialDeterminants[2];
311
312 // Pre-bake the numerator of Cramer's rule into the zParams to avoid another multiply.
313 // TODO: this may introduce numerical instability, but I haven't seen any issues yet.
314 fTransformedZParams.fX *= ctmDeterminant;
315 fTransformedZParams.fY *= ctmDeterminant;
316 fTransformedZParams.fZ *= ctmDeterminant;
317
318 fTransformedHeightFunc = [this](const SkPoint& p) {
319 SkScalar denom = p.fX * fPartialDeterminants[0] +
320 p.fY * fPartialDeterminants[1] +
321 fPartialDeterminants[2];
322 SkScalar w = SkScalarFastInvert(denom);
323 return fZOffset + w*(fTransformedZParams.fX * p.fX +
324 fTransformedZParams.fY * p.fY +
325 fTransformedZParams.fZ);
326 };
327 } else {
328 fTransformedHeightFunc = [this](const SkPoint& p) {
329 return fZOffset + fTransformedZParams.fX * p.fX +
330 fTransformedZParams.fY * p.fY + fTransformedZParams.fZ;
331 };
332 }
333 }
334
335 return true;
336 }
337
338
339 //////////////////////////////////////////////////////////////////////////////////////////////////
340
341 class SkAmbientShadowTessellator : public SkBaseShadowTessellator {
342 public:
343 SkAmbientShadowTessellator(const SkPath& path, const SkMatrix& ctm,
344 const SkPoint3& zPlaneParams, bool transparent);
345
346 private:
347 void handleLine(const SkPoint& p) override;
348 void addEdge(const SkVector& nextPoint, const SkVector& nextNormal);
349
350 static constexpr auto kMaxEdgeLenSqr = 20 * 20;
351 static constexpr auto kInsetFactor = -0.5f;
352
offset(SkScalar z)353 SkScalar offset(SkScalar z) {
354 return SkDrawShadowMetrics::AmbientBlurRadius(z);
355 }
umbraColor(SkScalar z)356 SkColor umbraColor(SkScalar z) {
357 SkScalar umbraAlpha = SkScalarInvert(SkDrawShadowMetrics::AmbientRecipAlpha(z));
358 return SkColorSetARGB(umbraAlpha * 255.9999f, 0, 0, 0);
359 }
360
361 int fCentroidCount;
362 bool fSplitFirstEdge;
363 bool fSplitPreviousEdge;
364
365 typedef SkBaseShadowTessellator INHERITED;
366 };
367
SkAmbientShadowTessellator(const SkPath & path,const SkMatrix & ctm,const SkPoint3 & zPlaneParams,bool transparent)368 SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
369 const SkMatrix& ctm,
370 const SkPoint3& zPlaneParams,
371 bool transparent)
372 : INHERITED(zPlaneParams, transparent)
373 , fSplitFirstEdge(false)
374 , fSplitPreviousEdge(false) {
375 // Set base colors
376 SkScalar umbraAlpha = SkScalarInvert(SkDrawShadowMetrics::AmbientRecipAlpha(heightFunc(0, 0)));
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 SkPointPriv::DistanceToSqd(fFirstPoint, 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 SkPointPriv::DistanceToSqd(nextPoint, 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 fUmbraColor = SkColorSetARGB(255, 0, 0, 0);
807 fPenumbraColor = SkColorSetARGB(0, 0, 0, 0);
808
809 // Compute the blur radius, scale and translation for the spot shadow.
810 SkScalar radius;
811 SkMatrix shadowTransform;
812 if (!ctm.hasPerspective()) {
813 SkScalar scale;
814 SkVector translate;
815 SkDrawShadowMetrics::GetSpotParams(occluderHeight, lightPos.fX, lightPos.fY, fLightZ,
816 lightRadius, &radius, &scale, &translate);
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 radius = SkDrawShadowMetrics::SpotBlurRadius(occluderHeight, lightPos.fZ, lightRadius);
826 }
827 fRadius = radius;
828 SkMatrix fullTransform = SkMatrix::Concat(shadowTransform, ctm);
829
830 // Set up our reverse mapping
831 this->setTransformedHeightFunc(fullTransform);
832
833 // TODO: calculate these reserves better
834 // Penumbra ring: 3*numPts
835 // Umbra ring: numPts
836 // Inner ring: numPts
837 fPositions.setReserve(5 * path.countPoints());
838 fColors.setReserve(5 * path.countPoints());
839 // Penumbra ring: 12*numPts
840 // Umbra ring: 3*numPts
841 fIndices.setReserve(15 * path.countPoints());
842 fClipPolygon.setReserve(path.countPoints());
843
844 // compute rough clip bounds for umbra, plus offset polygon, plus centroid
845 this->computeClipAndPathPolygons(path, ctm, shadowTransform);
846 if (fClipPolygon.count() < 3 || fPathPolygon.count() < 3) {
847 return;
848 }
849
850 // check to see if umbra collapses
851 SkScalar minDistSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid, fPathPolygon[0],
852 fPathPolygon[1]);
853 SkRect bounds;
854 bounds.setBounds(&fPathPolygon[0], fPathPolygon.count());
855 for (int i = 1; i < fPathPolygon.count(); ++i) {
856 int j = i + 1;
857 if (i == fPathPolygon.count() - 1) {
858 j = 0;
859 }
860 SkPoint currPoint = fPathPolygon[i];
861 SkPoint nextPoint = fPathPolygon[j];
862 SkScalar distSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid, currPoint,
863 nextPoint);
864 if (distSq < minDistSq) {
865 minDistSq = distSq;
866 }
867 }
868 static constexpr auto kTolerance = 1.0e-2f;
869 if (minDistSq < (radius + kTolerance)*(radius + kTolerance)) {
870 // if the umbra would collapse, we back off a bit on inner blur and adjust the alpha
871 SkScalar newRadius = SkScalarSqrt(minDistSq) - kTolerance;
872 fOffsetAdjust = newRadius - radius;
873 SkScalar ratio = 128 * (newRadius + radius) / radius;
874 // they aren't PMColors, but the interpolation algorithm is the same
875 fUmbraColor = SkPMLerp(fUmbraColor, fPenumbraColor, (unsigned)ratio);
876 radius = newRadius;
877 }
878
879 // compute vectors for clip tests
880 this->computeClipVectorsAndTestCentroid();
881
882 // generate inner ring
883 if (!SkInsetConvexPolygon(&fPathPolygon[0], fPathPolygon.count(), radius,
884 &fUmbraPolygon)) {
885 // this shouldn't happen, but just in case we'll inset using the centroid
886 fValidUmbra = false;
887 }
888
889 // walk around the path polygon, generate outer ring and connect to inner ring
890 if (fTransparent) {
891 *fPositions.push() = fCentroid;
892 *fColors.push() = fUmbraColor;
893 }
894 fCurrUmbraPoint = 0;
895 for (int i = 0; i < fPathPolygon.count(); ++i) {
896 if (!this->handlePolyPoint(fPathPolygon[i])) {
897 return;
898 }
899 }
900
901 if (!this->indexCount()) {
902 return;
903 }
904
905 // finish up the final verts
906 SkVector normal;
907 if (compute_normal(fPrevPoint, fFirstPoint, fDirection, &normal)) {
908 normal *= fRadius;
909 this->addArc(normal, true);
910
911 // add to center fan
912 if (fTransparent) {
913 *fIndices.push() = 0;
914 *fIndices.push() = fPrevUmbraIndex;
915 *fIndices.push() = fFirstVertexIndex;
916 // or to clip ring
917 } else {
918 if (fFirstUmbraOutside) {
919 *fIndices.push() = fPrevUmbraIndex;
920 *fIndices.push() = fFirstVertexIndex;
921 *fIndices.push() = fFirstVertexIndex + 1;
922 if (fPrevUmbraOutside) {
923 // fill out quad
924 *fIndices.push() = fPrevUmbraIndex;
925 *fIndices.push() = fFirstVertexIndex + 1;
926 *fIndices.push() = fPrevUmbraIndex + 1;
927 }
928 } else if (fPrevUmbraOutside) {
929 // add tri
930 *fIndices.push() = fPrevUmbraIndex;
931 *fIndices.push() = fFirstVertexIndex;
932 *fIndices.push() = fPrevUmbraIndex + 1;
933 }
934 }
935
936 // add final edge
937 *fPositions.push() = fFirstPoint + normal;
938 *fColors.push() = fPenumbraColor;
939
940 *fIndices.push() = fPrevUmbraIndex;
941 *fIndices.push() = fPositions.count() - 2;
942 *fIndices.push() = fFirstVertexIndex;
943
944 *fIndices.push() = fPositions.count() - 2;
945 *fIndices.push() = fPositions.count() - 1;
946 *fIndices.push() = fFirstVertexIndex;
947
948 fPrevOutset = normal;
949 }
950
951 // final fan
952 if (fPositions.count() >= 3) {
953 fPrevUmbraIndex = fFirstVertexIndex;
954 fPrevPoint = fFirstPoint;
955 if (this->addArc(fFirstOutset, false)) {
956 *fIndices.push() = fFirstVertexIndex;
957 *fIndices.push() = fPositions.count() - 1;
958 if (fFirstUmbraOutside) {
959 *fIndices.push() = fFirstVertexIndex + 2;
960 } else {
961 *fIndices.push() = fFirstVertexIndex + 1;
962 }
963 } else {
964 // no arc added, fix up by setting first penumbra point position to last one
965 if (fFirstUmbraOutside) {
966 fPositions[fFirstVertexIndex + 2] = fPositions[fPositions.count() - 1];
967 } else {
968 fPositions[fFirstVertexIndex + 1] = fPositions[fPositions.count() - 1];
969 }
970 }
971 }
972
973 if (ctm.hasPerspective()) {
974 for (int i = 0; i < fPositions.count(); ++i) {
975 SkScalar pathZ = fTransformedHeightFunc(fPositions[i]);
976 SkScalar factor = SkScalarInvert(fLightZ - pathZ);
977 fPositions[i].fX = (fPositions[i].fX*fLightZ - lightPos.fX*pathZ)*factor;
978 fPositions[i].fY = (fPositions[i].fY*fLightZ - lightPos.fY*pathZ)*factor;
979 }
980 #ifdef DRAW_CENTROID
981 SkScalar pathZ = fTransformedHeightFunc(fCentroid);
982 SkScalar factor = SkScalarInvert(fLightZ - pathZ);
983 fCentroid.fX = (fCentroid.fX*fLightZ - lightPos.fX*pathZ)*factor;
984 fCentroid.fY = (fCentroid.fY*fLightZ - lightPos.fY*pathZ)*factor;
985 #endif
986 }
987 #ifdef DRAW_CENTROID
988 *fPositions.push() = fCentroid + SkVector::Make(-2, -2);
989 *fColors.push() = SkColorSetARGB(255, 0, 255, 255);
990 *fPositions.push() = fCentroid + SkVector::Make(2, -2);
991 *fColors.push() = SkColorSetARGB(255, 0, 255, 255);
992 *fPositions.push() = fCentroid + SkVector::Make(-2, 2);
993 *fColors.push() = SkColorSetARGB(255, 0, 255, 255);
994 *fPositions.push() = fCentroid + SkVector::Make(2, 2);
995 *fColors.push() = SkColorSetARGB(255, 0, 255, 255);
996
997 *fIndices.push() = fPositions.count() - 4;
998 *fIndices.push() = fPositions.count() - 2;
999 *fIndices.push() = fPositions.count() - 1;
1000
1001 *fIndices.push() = fPositions.count() - 4;
1002 *fIndices.push() = fPositions.count() - 1;
1003 *fIndices.push() = fPositions.count() - 3;
1004 #endif
1005
1006 fSucceeded = true;
1007 }
1008
computeClipAndPathPolygons(const SkPath & path,const SkMatrix & ctm,const SkMatrix & shadowTransform)1009 void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
1010 const SkMatrix& shadowTransform) {
1011
1012 fPathPolygon.setReserve(path.countPoints());
1013
1014 // Walk around the path and compute clip polygon and path polygon.
1015 // Will also accumulate sum of areas for centroid.
1016 // For Bezier curves, we compute additional interior points on curve.
1017 SkPath::Iter iter(path, true);
1018 SkPoint pts[4];
1019 SkPath::Verb verb;
1020
1021 fClipPolygon.reset();
1022
1023 // init centroid
1024 fCentroid = SkPoint::Make(0, 0);
1025 fArea = 0;
1026
1027 // coefficients to compute cubic Bezier at t = 5/16
1028 static constexpr SkScalar kA = 0.32495117187f;
1029 static constexpr SkScalar kB = 0.44311523437f;
1030 static constexpr SkScalar kC = 0.20141601562f;
1031 static constexpr SkScalar kD = 0.03051757812f;
1032
1033 SkPoint curvePoint;
1034 SkScalar w;
1035 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1036 switch (verb) {
1037 case SkPath::kLine_Verb:
1038 ctm.mapPoints(&pts[1], 1);
1039 *fClipPolygon.push() = pts[1];
1040 this->INHERITED::handleLine(shadowTransform, &pts[1]);
1041 break;
1042 case SkPath::kQuad_Verb:
1043 ctm.mapPoints(pts, 3);
1044 // point at t = 1/2
1045 curvePoint.fX = 0.25f*pts[0].fX + 0.5f*pts[1].fX + 0.25f*pts[2].fX;
1046 curvePoint.fY = 0.25f*pts[0].fY + 0.5f*pts[1].fY + 0.25f*pts[2].fY;
1047 *fClipPolygon.push() = curvePoint;
1048 *fClipPolygon.push() = pts[2];
1049 this->handleQuad(shadowTransform, pts);
1050 break;
1051 case SkPath::kConic_Verb:
1052 ctm.mapPoints(pts, 3);
1053 w = iter.conicWeight();
1054 // point at t = 1/2
1055 curvePoint.fX = 0.25f*pts[0].fX + w*0.5f*pts[1].fX + 0.25f*pts[2].fX;
1056 curvePoint.fY = 0.25f*pts[0].fY + w*0.5f*pts[1].fY + 0.25f*pts[2].fY;
1057 curvePoint *= SkScalarInvert(0.5f + 0.5f*w);
1058 *fClipPolygon.push() = curvePoint;
1059 *fClipPolygon.push() = pts[2];
1060 this->handleConic(shadowTransform, pts, w);
1061 break;
1062 case SkPath::kCubic_Verb:
1063 ctm.mapPoints(pts, 4);
1064 // point at t = 5/16
1065 curvePoint.fX = kA*pts[0].fX + kB*pts[1].fX + kC*pts[2].fX + kD*pts[3].fX;
1066 curvePoint.fY = kA*pts[0].fY + kB*pts[1].fY + kC*pts[2].fY + kD*pts[3].fY;
1067 *fClipPolygon.push() = curvePoint;
1068 // point at t = 11/16
1069 curvePoint.fX = kD*pts[0].fX + kC*pts[1].fX + kB*pts[2].fX + kA*pts[3].fX;
1070 curvePoint.fY = kD*pts[0].fY + kC*pts[1].fY + kB*pts[2].fY + kA*pts[3].fY;
1071 *fClipPolygon.push() = curvePoint;
1072 *fClipPolygon.push() = pts[3];
1073 this->handleCubic(shadowTransform, pts);
1074 break;
1075 case SkPath::kMove_Verb:
1076 case SkPath::kClose_Verb:
1077 case SkPath::kDone_Verb:
1078 break;
1079 default:
1080 SkDEBUGFAIL("unknown verb");
1081 }
1082 }
1083
1084 // finish centroid
1085 if (fPathPolygon.count() > 0) {
1086 SkPoint currPoint = fPathPolygon[fPathPolygon.count() - 1];
1087 SkPoint nextPoint = fPathPolygon[0];
1088 SkScalar quadArea = currPoint.cross(nextPoint);
1089 fCentroid.fX += (currPoint.fX + nextPoint.fX) * quadArea;
1090 fCentroid.fY += (currPoint.fY + nextPoint.fY) * quadArea;
1091 fArea += quadArea;
1092 fCentroid *= SK_Scalar1 / (3 * fArea);
1093 }
1094
1095 fCurrClipPoint = fClipPolygon.count() - 1;
1096 }
1097
computeClipVectorsAndTestCentroid()1098 void SkSpotShadowTessellator::computeClipVectorsAndTestCentroid() {
1099 SkASSERT(fClipPolygon.count() >= 3);
1100
1101 // init clip vectors
1102 SkVector v0 = fClipPolygon[1] - fClipPolygon[0];
1103 *fClipVectors.push() = v0;
1104
1105 // init centroid check
1106 bool hiddenCentroid = true;
1107 SkVector v1 = fCentroid - fClipPolygon[0];
1108 SkScalar initCross = v0.cross(v1);
1109
1110 for (int p = 1; p < fClipPolygon.count(); ++p) {
1111 // add to clip vectors
1112 v0 = fClipPolygon[(p + 1) % fClipPolygon.count()] - fClipPolygon[p];
1113 *fClipVectors.push() = v0;
1114 // Determine if transformed centroid is inside clipPolygon.
1115 v1 = fCentroid - fClipPolygon[p];
1116 if (initCross*v0.cross(v1) <= 0) {
1117 hiddenCentroid = false;
1118 }
1119 }
1120 SkASSERT(fClipVectors.count() == fClipPolygon.count());
1121
1122 fTransparent = fTransparent || !hiddenCentroid;
1123 }
1124
clipUmbraPoint(const SkPoint & umbraPoint,const SkPoint & centroid,SkPoint * clipPoint)1125 bool SkSpotShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid,
1126 SkPoint* clipPoint) {
1127 SkVector segmentVector = centroid - umbraPoint;
1128
1129 int startClipPoint = fCurrClipPoint;
1130 do {
1131 SkVector dp = umbraPoint - fClipPolygon[fCurrClipPoint];
1132 SkScalar denom = fClipVectors[fCurrClipPoint].cross(segmentVector);
1133 SkScalar t_num = dp.cross(segmentVector);
1134 // if line segments are nearly parallel
1135 if (SkScalarNearlyZero(denom)) {
1136 // and collinear
1137 if (SkScalarNearlyZero(t_num)) {
1138 return false;
1139 }
1140 // otherwise are separate, will try the next poly segment
1141 // else if crossing lies within poly segment
1142 } else if (t_num >= 0 && t_num <= denom) {
1143 SkScalar s_num = dp.cross(fClipVectors[fCurrClipPoint]);
1144 // if umbra point is inside the clip polygon
1145 if (s_num >= 0 && s_num <= denom) {
1146 segmentVector *= s_num/denom;
1147 *clipPoint = umbraPoint + segmentVector;
1148 return true;
1149 }
1150 }
1151 fCurrClipPoint = (fCurrClipPoint + 1) % fClipPolygon.count();
1152 } while (fCurrClipPoint != startClipPoint);
1153
1154 return false;
1155 }
1156
getClosestUmbraPoint(const SkPoint & p)1157 int SkSpotShadowTessellator::getClosestUmbraPoint(const SkPoint& p) {
1158 SkScalar minDistance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[fCurrUmbraPoint]);
1159 int index = fCurrUmbraPoint;
1160 int dir = 1;
1161 int next = (index + dir) % fUmbraPolygon.count();
1162
1163 // init travel direction
1164 SkScalar distance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[next]);
1165 if (distance < minDistance) {
1166 index = next;
1167 minDistance = distance;
1168 } else {
1169 dir = fUmbraPolygon.count()-1;
1170 }
1171
1172 // iterate until we find a point that increases the distance
1173 next = (index + dir) % fUmbraPolygon.count();
1174 distance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[next]);
1175 while (distance < minDistance) {
1176 index = next;
1177 minDistance = distance;
1178 next = (index + dir) % fUmbraPolygon.count();
1179 distance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[next]);
1180 }
1181
1182 fCurrUmbraPoint = index;
1183 return index;
1184 }
1185
mapPoints(SkScalar scale,const SkVector & xlate,SkPoint * pts,int count)1186 void SkSpotShadowTessellator::mapPoints(SkScalar scale, const SkVector& xlate,
1187 SkPoint* pts, int count) {
1188 // TODO: vectorize
1189 for (int i = 0; i < count; ++i) {
1190 pts[i] *= scale;
1191 pts[i] += xlate;
1192 }
1193 }
1194
duplicate_pt(const SkPoint & p0,const SkPoint & p1)1195 static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) {
1196 static constexpr SkScalar kClose = (SK_Scalar1 / 16);
1197 static constexpr SkScalar kCloseSqd = kClose*kClose;
1198
1199 SkScalar distSq = SkPointPriv::DistanceToSqd(p0, p1);
1200 return distSq < kCloseSqd;
1201 }
1202
perp_dot(const SkPoint & p0,const SkPoint & p1,const SkPoint & p2)1203 static SkScalar perp_dot(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
1204 SkVector v0 = p1 - p0;
1205 SkVector v1 = p2 - p0;
1206 return v0.cross(v1);
1207 }
1208
is_collinear(const SkPoint & p0,const SkPoint & p1,const SkPoint & p2)1209 static bool is_collinear(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
1210 return (SkScalarNearlyZero(perp_dot(p0, p1, p2)));
1211 }
1212
handleLine(const SkPoint & p)1213 void SkSpotShadowTessellator::handleLine(const SkPoint& p) {
1214 // remove coincident points and add to centroid
1215 if (fPathPolygon.count() > 0) {
1216 const SkPoint& lastPoint = fPathPolygon[fPathPolygon.count() - 1];
1217 if (duplicate_pt(p, lastPoint)) {
1218 return;
1219 }
1220 SkScalar quadArea = lastPoint.cross(p);
1221 fCentroid.fX += (p.fX + lastPoint.fX) * quadArea;
1222 fCentroid.fY += (p.fY + lastPoint.fY) * quadArea;
1223 fArea += quadArea;
1224 }
1225
1226 // try to remove collinear points
1227 if (fPathPolygon.count() > 1 && is_collinear(fPathPolygon[fPathPolygon.count()-2],
1228 fPathPolygon[fPathPolygon.count()-1],
1229 p)) {
1230 fPathPolygon[fPathPolygon.count() - 1] = p;
1231 } else {
1232 *fPathPolygon.push() = p;
1233 }
1234 }
1235
handlePolyPoint(const SkPoint & p)1236 bool SkSpotShadowTessellator::handlePolyPoint(const SkPoint& p) {
1237 if (fInitPoints.count() < 2) {
1238 *fInitPoints.push() = p;
1239 return true;
1240 }
1241
1242 if (fInitPoints.count() == 2) {
1243 // determine if cw or ccw
1244 SkScalar perpDot = perp_dot(fInitPoints[0], fInitPoints[1], p);
1245 if (SkScalarNearlyZero(perpDot)) {
1246 // nearly parallel, just treat as straight line and continue
1247 fInitPoints[1] = p;
1248 return true;
1249 }
1250
1251 // if perpDot > 0, winding is ccw
1252 fDirection = (perpDot > 0) ? -1 : 1;
1253
1254 // add first quad
1255 if (!compute_normal(fInitPoints[0], fInitPoints[1], fDirection, &fFirstOutset)) {
1256 // first two points are incident, make the third point the second and continue
1257 fInitPoints[1] = p;
1258 return true;
1259 }
1260
1261 fFirstOutset *= fRadius;
1262 fFirstPoint = fInitPoints[0];
1263 fFirstVertexIndex = fPositions.count();
1264 fPrevOutset = fFirstOutset;
1265 fPrevPoint = fFirstPoint;
1266 fPrevUmbraIndex = -1;
1267
1268 this->addInnerPoint(fFirstPoint);
1269 fPrevUmbraIndex = fFirstVertexIndex;
1270
1271 if (!fTransparent) {
1272 SkPoint clipPoint;
1273 bool isOutside = this->clipUmbraPoint(fPositions[fFirstVertexIndex],
1274 fCentroid, &clipPoint);
1275 if (isOutside) {
1276 *fPositions.push() = clipPoint;
1277 *fColors.push() = fUmbraColor;
1278 }
1279 fPrevUmbraOutside = isOutside;
1280 fFirstUmbraOutside = isOutside;
1281 }
1282
1283 SkPoint newPoint = fFirstPoint + fFirstOutset;
1284 *fPositions.push() = newPoint;
1285 *fColors.push() = fPenumbraColor;
1286 this->addEdge(fInitPoints[1], fFirstOutset);
1287
1288 // to ensure we skip this block next time
1289 *fInitPoints.push() = p;
1290 }
1291
1292 // if concave, abort
1293 SkScalar perpDot = perp_dot(fInitPoints[1], fInitPoints[2], p);
1294 if (fDirection*perpDot > 0) {
1295 return false;
1296 }
1297
1298 SkVector normal;
1299 if (compute_normal(fPrevPoint, p, fDirection, &normal)) {
1300 normal *= fRadius;
1301 this->addArc(normal, true);
1302 this->addEdge(p, normal);
1303 fInitPoints[1] = fInitPoints[2];
1304 fInitPoints[2] = p;
1305 }
1306
1307 return true;
1308 }
1309
addInnerPoint(const SkPoint & pathPoint)1310 bool SkSpotShadowTessellator::addInnerPoint(const SkPoint& pathPoint) {
1311 SkPoint umbraPoint;
1312 if (!fValidUmbra) {
1313 SkVector v = fCentroid - pathPoint;
1314 v *= 0.95f;
1315 umbraPoint = pathPoint + v;
1316 } else {
1317 umbraPoint = fUmbraPolygon[this->getClosestUmbraPoint(pathPoint)];
1318 }
1319
1320 fPrevPoint = pathPoint;
1321
1322 // merge "close" points
1323 if (fPrevUmbraIndex == -1 ||
1324 !duplicate_pt(umbraPoint, fPositions[fPrevUmbraIndex])) {
1325 *fPositions.push() = umbraPoint;
1326 *fColors.push() = fUmbraColor;
1327
1328 return false;
1329 } else {
1330 return true;
1331 }
1332 }
1333
addEdge(const SkPoint & nextPoint,const SkVector & nextNormal)1334 void SkSpotShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal) {
1335 // add next umbra point
1336 bool duplicate = this->addInnerPoint(nextPoint);
1337 int prevPenumbraIndex = duplicate ? fPositions.count()-1 : fPositions.count()-2;
1338 int currUmbraIndex = duplicate ? fPrevUmbraIndex : fPositions.count()-1;
1339
1340 if (!duplicate) {
1341 // add to center fan if transparent or centroid showing
1342 if (fTransparent) {
1343 *fIndices.push() = 0;
1344 *fIndices.push() = fPrevUmbraIndex;
1345 *fIndices.push() = currUmbraIndex;
1346 // otherwise add to clip ring
1347 } else {
1348 SkPoint clipPoint;
1349 bool isOutside = this->clipUmbraPoint(fPositions[currUmbraIndex], fCentroid,
1350 &clipPoint);
1351 if (isOutside) {
1352 *fPositions.push() = clipPoint;
1353 *fColors.push() = fUmbraColor;
1354
1355 *fIndices.push() = fPrevUmbraIndex;
1356 *fIndices.push() = currUmbraIndex;
1357 *fIndices.push() = currUmbraIndex + 1;
1358 if (fPrevUmbraOutside) {
1359 // fill out quad
1360 *fIndices.push() = fPrevUmbraIndex;
1361 *fIndices.push() = currUmbraIndex + 1;
1362 *fIndices.push() = fPrevUmbraIndex + 1;
1363 }
1364 } else if (fPrevUmbraOutside) {
1365 // add tri
1366 *fIndices.push() = fPrevUmbraIndex;
1367 *fIndices.push() = currUmbraIndex;
1368 *fIndices.push() = fPrevUmbraIndex + 1;
1369 }
1370 fPrevUmbraOutside = isOutside;
1371 }
1372 }
1373
1374 // add next penumbra point and quad
1375 SkPoint newPoint = nextPoint + nextNormal;
1376 *fPositions.push() = newPoint;
1377 *fColors.push() = fPenumbraColor;
1378
1379 if (!duplicate) {
1380 *fIndices.push() = fPrevUmbraIndex;
1381 *fIndices.push() = prevPenumbraIndex;
1382 *fIndices.push() = currUmbraIndex;
1383 }
1384
1385 *fIndices.push() = prevPenumbraIndex;
1386 *fIndices.push() = fPositions.count() - 1;
1387 *fIndices.push() = currUmbraIndex;
1388
1389 fPrevUmbraIndex = currUmbraIndex;
1390 fPrevOutset = nextNormal;
1391 }
1392
1393 ///////////////////////////////////////////////////////////////////////////////////////////////////
1394
MakeAmbient(const SkPath & path,const SkMatrix & ctm,const SkPoint3 & zPlane,bool transparent)1395 sk_sp<SkVertices> SkShadowTessellator::MakeAmbient(const SkPath& path, const SkMatrix& ctm,
1396 const SkPoint3& zPlane, bool transparent) {
1397 SkAmbientShadowTessellator ambientTess(path, ctm, zPlane, transparent);
1398 return ambientTess.releaseVertices();
1399 }
1400
MakeSpot(const SkPath & path,const SkMatrix & ctm,const SkPoint3 & zPlane,const SkPoint3 & lightPos,SkScalar lightRadius,bool transparent)1401 sk_sp<SkVertices> SkShadowTessellator::MakeSpot(const SkPath& path, const SkMatrix& ctm,
1402 const SkPoint3& zPlane, const SkPoint3& lightPos,
1403 SkScalar lightRadius, bool transparent) {
1404 SkSpotShadowTessellator spotTess(path, ctm, zPlane, lightPos, lightRadius, transparent);
1405 return spotTess.releaseVertices();
1406 }
1407