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