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
9 #include "src/utils/SkShadowTessellator.h"
10
11 #include "include/core/SkColor.h"
12 #include "include/core/SkMatrix.h"
13 #include "include/core/SkPath.h"
14 #include "include/core/SkPoint.h"
15 #include "include/core/SkPoint3.h"
16 #include "include/core/SkRect.h"
17 #include "include/core/SkTypes.h"
18 #include "include/core/SkVertices.h"
19 #include "include/private/SkColorData.h"
20 #include "include/private/base/SkFloatingPoint.h"
21 #include "include/private/base/SkTDArray.h"
22 #include "include/private/base/SkTemplates.h"
23 #include "src/core/SkDrawShadowInfo.h"
24 #include "src/core/SkGeometry.h"
25 #include "src/core/SkPointPriv.h"
26 #include "src/core/SkRectPriv.h"
27 #include "src/utils/SkPolyUtils.h"
28
29 #include <algorithm>
30 #include <cstdint>
31
32
33 #if defined(SK_GANESH)
34 #include "src/gpu/ganesh/geometry/GrPathUtils.h"
35 #endif
36
37 using namespace skia_private;
38
39 #if !defined(SK_ENABLE_OPTIMIZE_SIZE)
40
41 /**
42 * Base class
43 */
44 class SkBaseShadowTessellator {
45 public:
46 SkBaseShadowTessellator(const SkPoint3& zPlaneParams, const SkRect& bounds, bool transparent);
~SkBaseShadowTessellator()47 virtual ~SkBaseShadowTessellator() {}
48
releaseVertices()49 sk_sp<SkVertices> releaseVertices() {
50 if (!fSucceeded) {
51 return nullptr;
52 }
53 return SkVertices::MakeCopy(SkVertices::kTriangles_VertexMode, this->vertexCount(),
54 fPositions.begin(), nullptr, fColors.begin(),
55 this->indexCount(), fIndices.begin());
56 }
57
58 protected:
59 inline static constexpr auto kMinHeight = 0.1f;
60 inline static constexpr auto kPenumbraColor = SK_ColorTRANSPARENT;
61 inline static constexpr auto kUmbraColor = SK_ColorBLACK;
62
vertexCount() const63 int vertexCount() const { return fPositions.size(); }
indexCount() const64 int indexCount() const { return fIndices.size(); }
65
66 // initialization methods
67 bool accumulateCentroid(const SkPoint& c, const SkPoint& n);
68 bool checkConvexity(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2);
69 void finishPathPolygon();
70
71 // convex shadow methods
72 bool computeConvexShadow(SkScalar inset, SkScalar outset, bool doClip);
73 void computeClipVectorsAndTestCentroid();
74 bool clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint);
75 void addEdge(const SkVector& nextPoint, const SkVector& nextNormal, SkColor umbraColor,
76 const SkTDArray<SkPoint>& umbraPolygon, bool lastEdge, bool doClip);
77 bool addInnerPoint(const SkPoint& pathPoint, SkColor umbraColor,
78 const SkTDArray<SkPoint>& umbraPolygon, int* currUmbraIndex);
79 int getClosestUmbraIndex(const SkPoint& point, const SkTDArray<SkPoint>& umbraPolygon);
80
81 // concave shadow methods
82 bool computeConcaveShadow(SkScalar inset, SkScalar outset);
83 void stitchConcaveRings(const SkTDArray<SkPoint>& umbraPolygon,
84 SkTDArray<int>* umbraIndices,
85 const SkTDArray<SkPoint>& penumbraPolygon,
86 SkTDArray<int>* penumbraIndices);
87
88 void handleLine(const SkPoint& p);
89 void handleLine(const SkMatrix& m, SkPoint* p);
90
91 void handleQuad(const SkPoint pts[3]);
92 void handleQuad(const SkMatrix& m, SkPoint pts[3]);
93
94 void handleCubic(const SkMatrix& m, SkPoint pts[4]);
95
96 void handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w);
97
98 bool addArc(const SkVector& nextNormal, SkScalar offset, bool finishArc);
99
100 void appendTriangle(uint16_t index0, uint16_t index1, uint16_t index2);
101 void appendQuad(uint16_t index0, uint16_t index1, uint16_t index2, uint16_t index3);
102
heightFunc(SkScalar x,SkScalar y)103 SkScalar heightFunc(SkScalar x, SkScalar y) {
104 return fZPlaneParams.fX*x + fZPlaneParams.fY*y + fZPlaneParams.fZ;
105 }
106
107 SkPoint3 fZPlaneParams;
108
109 // temporary buffer
110 SkTDArray<SkPoint> fPointBuffer;
111
112 SkTDArray<SkPoint> fPositions;
113 SkTDArray<SkColor> fColors;
114 SkTDArray<uint16_t> fIndices;
115
116 SkTDArray<SkPoint> fPathPolygon;
117 SkTDArray<SkPoint> fClipPolygon;
118 SkTDArray<SkVector> fClipVectors;
119
120 SkRect fPathBounds;
121 SkPoint fCentroid;
122 SkScalar fArea;
123 SkScalar fLastArea;
124 SkScalar fLastCross;
125
126 int fFirstVertexIndex;
127 SkVector fFirstOutset;
128 SkPoint fFirstPoint;
129
130 bool fSucceeded;
131 bool fTransparent;
132 bool fIsConvex;
133 bool fValidUmbra;
134
135 SkScalar fDirection;
136 int fPrevUmbraIndex;
137 int fCurrUmbraIndex;
138 int fCurrClipIndex;
139 bool fPrevUmbraOutside;
140 bool fFirstUmbraOutside;
141 SkVector fPrevOutset;
142 SkPoint fPrevPoint;
143 };
144
compute_normal(const SkPoint & p0,const SkPoint & p1,SkScalar dir,SkVector * newNormal)145 static bool compute_normal(const SkPoint& p0, const SkPoint& p1, SkScalar dir,
146 SkVector* newNormal) {
147 SkVector normal;
148 // compute perpendicular
149 normal.fX = p0.fY - p1.fY;
150 normal.fY = p1.fX - p0.fX;
151 normal *= dir;
152 if (!normal.normalize()) {
153 return false;
154 }
155 *newNormal = normal;
156 return true;
157 }
158
duplicate_pt(const SkPoint & p0,const SkPoint & p1)159 static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) {
160 static constexpr SkScalar kClose = (SK_Scalar1 / 16);
161 static constexpr SkScalar kCloseSqd = kClose * kClose;
162
163 SkScalar distSq = SkPointPriv::DistanceToSqd(p0, p1);
164 return distSq < kCloseSqd;
165 }
166
perp_dot(const SkPoint & p0,const SkPoint & p1,const SkPoint & p2)167 static SkScalar perp_dot(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
168 SkVector v0 = p1 - p0;
169 SkVector v1 = p2 - p1;
170 return v0.cross(v1);
171 }
172
SkBaseShadowTessellator(const SkPoint3 & zPlaneParams,const SkRect & bounds,bool transparent)173 SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, const SkRect& bounds,
174 bool transparent)
175 : fZPlaneParams(zPlaneParams)
176 , fPathBounds(bounds)
177 , fCentroid({0, 0})
178 , fArea(0)
179 , fLastArea(0)
180 , fLastCross(0)
181 , fFirstVertexIndex(-1)
182 , fSucceeded(false)
183 , fTransparent(transparent)
184 , fIsConvex(true)
185 , fValidUmbra(true)
186 , fDirection(1)
187 , fPrevUmbraIndex(-1)
188 , fCurrUmbraIndex(0)
189 , fCurrClipIndex(0)
190 , fPrevUmbraOutside(false)
191 , fFirstUmbraOutside(false) {
192 // child classes will set reserve for positions, colors and indices
193 }
194
accumulateCentroid(const SkPoint & curr,const SkPoint & next)195 bool SkBaseShadowTessellator::accumulateCentroid(const SkPoint& curr, const SkPoint& next) {
196 if (duplicate_pt(curr, next)) {
197 return false;
198 }
199
200 SkASSERT(!fPathPolygon.empty());
201 SkVector v0 = curr - fPathPolygon[0];
202 SkVector v1 = next - fPathPolygon[0];
203 SkScalar quadArea = v0.cross(v1);
204 fCentroid.fX += (v0.fX + v1.fX) * quadArea;
205 fCentroid.fY += (v0.fY + v1.fY) * quadArea;
206 fArea += quadArea;
207 // convexity check
208 if (quadArea*fLastArea < 0) {
209 fIsConvex = false;
210 }
211 if (0 != quadArea) {
212 fLastArea = quadArea;
213 }
214
215 return true;
216 }
217
checkConvexity(const SkPoint & p0,const SkPoint & p1,const SkPoint & p2)218 bool SkBaseShadowTessellator::checkConvexity(const SkPoint& p0,
219 const SkPoint& p1,
220 const SkPoint& p2) {
221 SkScalar cross = perp_dot(p0, p1, p2);
222 // skip collinear point
223 if (SkScalarNearlyZero(cross)) {
224 return false;
225 }
226
227 // check for convexity
228 if (fLastCross*cross < 0) {
229 fIsConvex = false;
230 }
231 if (0 != cross) {
232 fLastCross = cross;
233 }
234
235 return true;
236 }
237
finishPathPolygon()238 void SkBaseShadowTessellator::finishPathPolygon() {
239 if (fPathPolygon.size() > 1) {
240 if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.size() - 1], fPathPolygon[0])) {
241 // remove coincident point
242 fPathPolygon.pop_back();
243 }
244 }
245
246 if (fPathPolygon.size() > 2) {
247 // do this before the final convexity check, so we use the correct fPathPolygon[0]
248 fCentroid *= sk_ieee_float_divide(1, 3 * fArea);
249 fCentroid += fPathPolygon[0];
250 if (!checkConvexity(fPathPolygon[fPathPolygon.size() - 2],
251 fPathPolygon[fPathPolygon.size() - 1],
252 fPathPolygon[0])) {
253 // remove collinear point
254 fPathPolygon[0] = fPathPolygon[fPathPolygon.size() - 1];
255 fPathPolygon.pop_back();
256 }
257 }
258
259 // if area is positive, winding is ccw
260 fDirection = fArea > 0 ? -1 : 1;
261 }
262
computeConvexShadow(SkScalar inset,SkScalar outset,bool doClip)263 bool SkBaseShadowTessellator::computeConvexShadow(SkScalar inset, SkScalar outset, bool doClip) {
264 if (doClip) {
265 this->computeClipVectorsAndTestCentroid();
266 }
267
268 // adjust inset distance and umbra color if necessary
269 auto umbraColor = kUmbraColor;
270 SkScalar minDistSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid,
271 fPathPolygon[0],
272 fPathPolygon[1]);
273 SkRect bounds;
274 bounds.setBounds(&fPathPolygon[0], fPathPolygon.size());
275 for (int i = 1; i < fPathPolygon.size(); ++i) {
276 int j = i + 1;
277 if (i == fPathPolygon.size() - 1) {
278 j = 0;
279 }
280 SkPoint currPoint = fPathPolygon[i];
281 SkPoint nextPoint = fPathPolygon[j];
282 SkScalar distSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid, currPoint,
283 nextPoint);
284 if (distSq < minDistSq) {
285 minDistSq = distSq;
286 }
287 }
288
289 SkTDArray<SkPoint> insetPolygon;
290 if (inset > SK_ScalarNearlyZero) {
291 static constexpr auto kTolerance = 1.0e-2f;
292 if (minDistSq < (inset + kTolerance)*(inset + kTolerance)) {
293 // if the umbra would collapse, we back off a bit on inner blur and adjust the alpha
294 auto newInset = SkScalarSqrt(minDistSq) - kTolerance;
295 auto ratio = 128 * (newInset / inset + 1);
296 SkASSERT(SkIsFinite(ratio));
297 // they aren't PMColors, but the interpolation algorithm is the same
298 umbraColor = SkPMLerp(kUmbraColor, kPenumbraColor, (unsigned)ratio);
299 inset = newInset;
300 }
301
302 // generate inner ring
303 if (!SkInsetConvexPolygon(&fPathPolygon[0], fPathPolygon.size(), inset,
304 &insetPolygon)) {
305 // not ideal, but in this case we'll inset using the centroid
306 fValidUmbra = false;
307 }
308 }
309 const SkTDArray<SkPoint>& umbraPolygon = (inset > SK_ScalarNearlyZero) ? insetPolygon
310 : fPathPolygon;
311
312 // walk around the path polygon, generate outer ring and connect to inner ring
313 if (fTransparent) {
314 fPositions.push_back(fCentroid);
315 fColors.push_back(umbraColor);
316 }
317 fCurrUmbraIndex = 0;
318
319 // initial setup
320 // add first quad
321 int polyCount = fPathPolygon.size();
322 if (!compute_normal(fPathPolygon[polyCount - 1], fPathPolygon[0], fDirection, &fFirstOutset)) {
323 // polygon should be sanitized by this point, so this is unrecoverable
324 return false;
325 }
326
327 fFirstOutset *= outset;
328 fFirstPoint = fPathPolygon[polyCount - 1];
329 fFirstVertexIndex = fPositions.size();
330 fPrevOutset = fFirstOutset;
331 fPrevPoint = fFirstPoint;
332 fPrevUmbraIndex = -1;
333
334 this->addInnerPoint(fFirstPoint, umbraColor, umbraPolygon, &fPrevUmbraIndex);
335
336 if (!fTransparent && doClip) {
337 SkPoint clipPoint;
338 bool isOutside = this->clipUmbraPoint(fPositions[fFirstVertexIndex],
339 fCentroid, &clipPoint);
340 if (isOutside) {
341 fPositions.push_back(clipPoint);
342 fColors.push_back(umbraColor);
343 }
344 fPrevUmbraOutside = isOutside;
345 fFirstUmbraOutside = isOutside;
346 }
347
348 SkPoint newPoint = fFirstPoint + fFirstOutset;
349 fPositions.push_back(newPoint);
350 fColors.push_back(kPenumbraColor);
351 this->addEdge(fPathPolygon[0], fFirstOutset, umbraColor, umbraPolygon, false, doClip);
352
353 for (int i = 1; i < polyCount; ++i) {
354 SkVector normal;
355 if (!compute_normal(fPrevPoint, fPathPolygon[i], fDirection, &normal)) {
356 return false;
357 }
358 normal *= outset;
359 this->addArc(normal, outset, true);
360 this->addEdge(fPathPolygon[i], normal, umbraColor, umbraPolygon,
361 i == polyCount - 1, doClip);
362 }
363 SkASSERT(this->indexCount());
364
365 // final fan
366 SkASSERT(fPositions.size() >= 3);
367 if (this->addArc(fFirstOutset, outset, false)) {
368 if (fFirstUmbraOutside) {
369 this->appendTriangle(fFirstVertexIndex, fPositions.size() - 1,
370 fFirstVertexIndex + 2);
371 } else {
372 this->appendTriangle(fFirstVertexIndex, fPositions.size() - 1,
373 fFirstVertexIndex + 1);
374 }
375 } else {
376 // no arc added, fix up by setting first penumbra point position to last one
377 if (fFirstUmbraOutside) {
378 fPositions[fFirstVertexIndex + 2] = fPositions[fPositions.size() - 1];
379 } else {
380 fPositions[fFirstVertexIndex + 1] = fPositions[fPositions.size() - 1];
381 }
382 }
383
384 return true;
385 }
386
computeClipVectorsAndTestCentroid()387 void SkBaseShadowTessellator::computeClipVectorsAndTestCentroid() {
388 SkASSERT(fClipPolygon.size() >= 3);
389 fCurrClipIndex = fClipPolygon.size() - 1;
390
391 // init clip vectors
392 SkVector v0 = fClipPolygon[1] - fClipPolygon[0];
393 SkVector v1 = fClipPolygon[2] - fClipPolygon[0];
394 fClipVectors.push_back(v0);
395
396 // init centroid check
397 bool hiddenCentroid = true;
398 v1 = fCentroid - fClipPolygon[0];
399 SkScalar initCross = v0.cross(v1);
400
401 for (int p = 1; p < fClipPolygon.size(); ++p) {
402 // add to clip vectors
403 v0 = fClipPolygon[(p + 1) % fClipPolygon.size()] - fClipPolygon[p];
404 fClipVectors.push_back(v0);
405 // Determine if transformed centroid is inside clipPolygon.
406 v1 = fCentroid - fClipPolygon[p];
407 if (initCross*v0.cross(v1) <= 0) {
408 hiddenCentroid = false;
409 }
410 }
411 SkASSERT(fClipVectors.size() == fClipPolygon.size());
412
413 fTransparent = fTransparent || !hiddenCentroid;
414 }
415
addEdge(const SkPoint & nextPoint,const SkVector & nextNormal,SkColor umbraColor,const SkTDArray<SkPoint> & umbraPolygon,bool lastEdge,bool doClip)416 void SkBaseShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal,
417 SkColor umbraColor, const SkTDArray<SkPoint>& umbraPolygon,
418 bool lastEdge, bool doClip) {
419 // add next umbra point
420 int currUmbraIndex;
421 bool duplicate;
422 if (lastEdge) {
423 duplicate = false;
424 currUmbraIndex = fFirstVertexIndex;
425 fPrevPoint = nextPoint;
426 } else {
427 duplicate = this->addInnerPoint(nextPoint, umbraColor, umbraPolygon, &currUmbraIndex);
428 }
429 int prevPenumbraIndex = duplicate || (currUmbraIndex == fFirstVertexIndex)
430 ? fPositions.size() - 1
431 : fPositions.size() - 2;
432 if (!duplicate) {
433 // add to center fan if transparent or centroid showing
434 if (fTransparent) {
435 this->appendTriangle(0, fPrevUmbraIndex, currUmbraIndex);
436 // otherwise add to clip ring
437 } else if (doClip) {
438 SkPoint clipPoint;
439 bool isOutside = lastEdge ? fFirstUmbraOutside
440 : this->clipUmbraPoint(fPositions[currUmbraIndex], fCentroid,
441 &clipPoint);
442 if (isOutside) {
443 if (!lastEdge) {
444 fPositions.push_back(clipPoint);
445 fColors.push_back(umbraColor);
446 }
447 this->appendTriangle(fPrevUmbraIndex, currUmbraIndex, currUmbraIndex + 1);
448 if (fPrevUmbraOutside) {
449 // fill out quad
450 this->appendTriangle(fPrevUmbraIndex, currUmbraIndex + 1,
451 fPrevUmbraIndex + 1);
452 }
453 } else if (fPrevUmbraOutside) {
454 // add tri
455 this->appendTriangle(fPrevUmbraIndex, currUmbraIndex, fPrevUmbraIndex + 1);
456 }
457
458 fPrevUmbraOutside = isOutside;
459 }
460 }
461
462 // add next penumbra point and quad
463 SkPoint newPoint = nextPoint + nextNormal;
464 fPositions.push_back(newPoint);
465 fColors.push_back(kPenumbraColor);
466
467 if (!duplicate) {
468 this->appendTriangle(fPrevUmbraIndex, prevPenumbraIndex, currUmbraIndex);
469 }
470 this->appendTriangle(prevPenumbraIndex, fPositions.size() - 1, currUmbraIndex);
471
472 fPrevUmbraIndex = currUmbraIndex;
473 fPrevOutset = nextNormal;
474 }
475
clipUmbraPoint(const SkPoint & umbraPoint,const SkPoint & centroid,SkPoint * clipPoint)476 bool SkBaseShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid,
477 SkPoint* clipPoint) {
478 SkVector segmentVector = centroid - umbraPoint;
479
480 int startClipPoint = fCurrClipIndex;
481 do {
482 SkVector dp = umbraPoint - fClipPolygon[fCurrClipIndex];
483 SkScalar denom = fClipVectors[fCurrClipIndex].cross(segmentVector);
484 SkScalar t_num = dp.cross(segmentVector);
485 // if line segments are nearly parallel
486 if (SkScalarNearlyZero(denom)) {
487 // and collinear
488 if (SkScalarNearlyZero(t_num)) {
489 return false;
490 }
491 // otherwise are separate, will try the next poly segment
492 // else if crossing lies within poly segment
493 } else if (t_num >= 0 && t_num <= denom) {
494 SkScalar s_num = dp.cross(fClipVectors[fCurrClipIndex]);
495 // if umbra point is inside the clip polygon
496 if (s_num >= 0 && s_num <= denom) {
497 segmentVector *= s_num / denom;
498 *clipPoint = umbraPoint + segmentVector;
499 return true;
500 }
501 }
502 fCurrClipIndex = (fCurrClipIndex + 1) % fClipPolygon.size();
503 } while (fCurrClipIndex != startClipPoint);
504
505 return false;
506 }
507
addInnerPoint(const SkPoint & pathPoint,SkColor umbraColor,const SkTDArray<SkPoint> & umbraPolygon,int * currUmbraIndex)508 bool SkBaseShadowTessellator::addInnerPoint(const SkPoint& pathPoint, SkColor umbraColor,
509 const SkTDArray<SkPoint>& umbraPolygon,
510 int* currUmbraIndex) {
511 SkPoint umbraPoint;
512 if (!fValidUmbra) {
513 SkVector v = fCentroid - pathPoint;
514 v *= 0.95f;
515 umbraPoint = pathPoint + v;
516 } else {
517 umbraPoint = umbraPolygon[this->getClosestUmbraIndex(pathPoint, umbraPolygon)];
518 }
519
520 fPrevPoint = pathPoint;
521
522 // merge "close" points
523 if (fPrevUmbraIndex == -1 ||
524 !duplicate_pt(umbraPoint, fPositions[fPrevUmbraIndex])) {
525 // if we've wrapped around, don't add a new point
526 if (fPrevUmbraIndex >= 0 && duplicate_pt(umbraPoint, fPositions[fFirstVertexIndex])) {
527 *currUmbraIndex = fFirstVertexIndex;
528 } else {
529 *currUmbraIndex = fPositions.size();
530 fPositions.push_back(umbraPoint);
531 fColors.push_back(umbraColor);
532 }
533 return false;
534 } else {
535 *currUmbraIndex = fPrevUmbraIndex;
536 return true;
537 }
538 }
539
getClosestUmbraIndex(const SkPoint & p,const SkTDArray<SkPoint> & umbraPolygon)540 int SkBaseShadowTessellator::getClosestUmbraIndex(const SkPoint& p,
541 const SkTDArray<SkPoint>& umbraPolygon) {
542 SkScalar minDistance = SkPointPriv::DistanceToSqd(p, umbraPolygon[fCurrUmbraIndex]);
543 int index = fCurrUmbraIndex;
544 int dir = 1;
545 int next = (index + dir) % umbraPolygon.size();
546
547 // init travel direction
548 SkScalar distance = SkPointPriv::DistanceToSqd(p, umbraPolygon[next]);
549 if (distance < minDistance) {
550 index = next;
551 minDistance = distance;
552 } else {
553 dir = umbraPolygon.size() - 1;
554 }
555
556 // iterate until we find a point that increases the distance
557 next = (index + dir) % umbraPolygon.size();
558 distance = SkPointPriv::DistanceToSqd(p, umbraPolygon[next]);
559 while (distance < minDistance) {
560 index = next;
561 minDistance = distance;
562 next = (index + dir) % umbraPolygon.size();
563 distance = SkPointPriv::DistanceToSqd(p, umbraPolygon[next]);
564 }
565
566 fCurrUmbraIndex = index;
567 return index;
568 }
569
computeConcaveShadow(SkScalar inset,SkScalar outset)570 bool SkBaseShadowTessellator::computeConcaveShadow(SkScalar inset, SkScalar outset) {
571 if (!SkIsSimplePolygon(&fPathPolygon[0], fPathPolygon.size())) {
572 return false;
573 }
574
575 // shouldn't inset more than the half bounds of the polygon
576 inset = std::min(inset, std::min(SkTAbs(SkRectPriv::HalfWidth(fPathBounds)),
577 SkTAbs(SkRectPriv::HalfHeight(fPathBounds))));
578 // generate inner ring
579 SkTDArray<SkPoint> umbraPolygon;
580 SkTDArray<int> umbraIndices;
581 umbraIndices.reserve(fPathPolygon.size());
582 if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.size(), fPathBounds, inset,
583 &umbraPolygon, &umbraIndices)) {
584 // TODO: figure out how to handle this case
585 return false;
586 }
587
588 // generate outer ring
589 SkTDArray<SkPoint> penumbraPolygon;
590 SkTDArray<int> penumbraIndices;
591 penumbraPolygon.reserve(umbraPolygon.size());
592 penumbraIndices.reserve(umbraPolygon.size());
593 if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.size(), fPathBounds, -outset,
594 &penumbraPolygon, &penumbraIndices)) {
595 // TODO: figure out how to handle this case
596 return false;
597 }
598
599 if (umbraPolygon.empty() || penumbraPolygon.empty()) {
600 return false;
601 }
602
603 // attach the rings together
604 this->stitchConcaveRings(umbraPolygon, &umbraIndices, penumbraPolygon, &penumbraIndices);
605
606 return true;
607 }
608
stitchConcaveRings(const SkTDArray<SkPoint> & umbraPolygon,SkTDArray<int> * umbraIndices,const SkTDArray<SkPoint> & penumbraPolygon,SkTDArray<int> * penumbraIndices)609 void SkBaseShadowTessellator::stitchConcaveRings(const SkTDArray<SkPoint>& umbraPolygon,
610 SkTDArray<int>* umbraIndices,
611 const SkTDArray<SkPoint>& penumbraPolygon,
612 SkTDArray<int>* penumbraIndices) {
613 // TODO: only create and fill indexMap when fTransparent is true?
614 AutoSTMalloc<64, uint16_t> indexMap(umbraPolygon.size());
615
616 // find minimum indices
617 int minIndex = 0;
618 int min = (*penumbraIndices)[0];
619 for (int i = 1; i < (*penumbraIndices).size(); ++i) {
620 if ((*penumbraIndices)[i] < min) {
621 min = (*penumbraIndices)[i];
622 minIndex = i;
623 }
624 }
625 int currPenumbra = minIndex;
626
627 minIndex = 0;
628 min = (*umbraIndices)[0];
629 for (int i = 1; i < (*umbraIndices).size(); ++i) {
630 if ((*umbraIndices)[i] < min) {
631 min = (*umbraIndices)[i];
632 minIndex = i;
633 }
634 }
635 int currUmbra = minIndex;
636
637 // now find a case where the indices are equal (there should be at least one)
638 int maxPenumbraIndex = fPathPolygon.size() - 1;
639 int maxUmbraIndex = fPathPolygon.size() - 1;
640 while ((*penumbraIndices)[currPenumbra] != (*umbraIndices)[currUmbra]) {
641 if ((*penumbraIndices)[currPenumbra] < (*umbraIndices)[currUmbra]) {
642 (*penumbraIndices)[currPenumbra] += fPathPolygon.size();
643 maxPenumbraIndex = (*penumbraIndices)[currPenumbra];
644 currPenumbra = (currPenumbra + 1) % penumbraPolygon.size();
645 } else {
646 (*umbraIndices)[currUmbra] += fPathPolygon.size();
647 maxUmbraIndex = (*umbraIndices)[currUmbra];
648 currUmbra = (currUmbra + 1) % umbraPolygon.size();
649 }
650 }
651
652 fPositions.push_back(penumbraPolygon[currPenumbra]);
653 fColors.push_back(kPenumbraColor);
654 int prevPenumbraIndex = 0;
655 fPositions.push_back(umbraPolygon[currUmbra]);
656 fColors.push_back(kUmbraColor);
657 fPrevUmbraIndex = 1;
658 indexMap[currUmbra] = 1;
659
660 int nextPenumbra = (currPenumbra + 1) % penumbraPolygon.size();
661 int nextUmbra = (currUmbra + 1) % umbraPolygon.size();
662 while ((*penumbraIndices)[nextPenumbra] <= maxPenumbraIndex ||
663 (*umbraIndices)[nextUmbra] <= maxUmbraIndex) {
664
665 if ((*umbraIndices)[nextUmbra] == (*penumbraIndices)[nextPenumbra]) {
666 // advance both one step
667 fPositions.push_back(penumbraPolygon[nextPenumbra]);
668 fColors.push_back(kPenumbraColor);
669 int currPenumbraIndex = fPositions.size() - 1;
670
671 fPositions.push_back(umbraPolygon[nextUmbra]);
672 fColors.push_back(kUmbraColor);
673 int currUmbraIndex = fPositions.size() - 1;
674 indexMap[nextUmbra] = currUmbraIndex;
675
676 this->appendQuad(prevPenumbraIndex, currPenumbraIndex,
677 fPrevUmbraIndex, currUmbraIndex);
678
679 prevPenumbraIndex = currPenumbraIndex;
680 (*penumbraIndices)[currPenumbra] += fPathPolygon.size();
681 currPenumbra = nextPenumbra;
682 nextPenumbra = (currPenumbra + 1) % penumbraPolygon.size();
683
684 fPrevUmbraIndex = currUmbraIndex;
685 (*umbraIndices)[currUmbra] += fPathPolygon.size();
686 currUmbra = nextUmbra;
687 nextUmbra = (currUmbra + 1) % umbraPolygon.size();
688 }
689
690 while ((*penumbraIndices)[nextPenumbra] < (*umbraIndices)[nextUmbra] &&
691 (*penumbraIndices)[nextPenumbra] <= maxPenumbraIndex) {
692 // fill out penumbra arc
693 fPositions.push_back(penumbraPolygon[nextPenumbra]);
694 fColors.push_back(kPenumbraColor);
695 int currPenumbraIndex = fPositions.size() - 1;
696
697 this->appendTriangle(prevPenumbraIndex, currPenumbraIndex, fPrevUmbraIndex);
698
699 prevPenumbraIndex = currPenumbraIndex;
700 // this ensures the ordering when we wrap around
701 (*penumbraIndices)[currPenumbra] += fPathPolygon.size();
702 currPenumbra = nextPenumbra;
703 nextPenumbra = (currPenumbra + 1) % penumbraPolygon.size();
704 }
705
706 while ((*umbraIndices)[nextUmbra] < (*penumbraIndices)[nextPenumbra] &&
707 (*umbraIndices)[nextUmbra] <= maxUmbraIndex) {
708 // fill out umbra arc
709 fPositions.push_back(umbraPolygon[nextUmbra]);
710 fColors.push_back(kUmbraColor);
711 int currUmbraIndex = fPositions.size() - 1;
712 indexMap[nextUmbra] = currUmbraIndex;
713
714 this->appendTriangle(fPrevUmbraIndex, prevPenumbraIndex, currUmbraIndex);
715
716 fPrevUmbraIndex = currUmbraIndex;
717 // this ensures the ordering when we wrap around
718 (*umbraIndices)[currUmbra] += fPathPolygon.size();
719 currUmbra = nextUmbra;
720 nextUmbra = (currUmbra + 1) % umbraPolygon.size();
721 }
722 }
723 // finish up by advancing both one step
724 fPositions.push_back(penumbraPolygon[nextPenumbra]);
725 fColors.push_back(kPenumbraColor);
726 int currPenumbraIndex = fPositions.size() - 1;
727
728 fPositions.push_back(umbraPolygon[nextUmbra]);
729 fColors.push_back(kUmbraColor);
730 int currUmbraIndex = fPositions.size() - 1;
731 indexMap[nextUmbra] = currUmbraIndex;
732
733 this->appendQuad(prevPenumbraIndex, currPenumbraIndex,
734 fPrevUmbraIndex, currUmbraIndex);
735
736 if (fTransparent) {
737 SkTriangulateSimplePolygon(umbraPolygon.begin(), indexMap, umbraPolygon.size(),
738 &fIndices);
739 }
740 }
741
742
743 // tesselation tolerance values, in device space pixels
744 #if defined(SK_GANESH)
745 static constexpr SkScalar kQuadTolerance = 0.2f;
746 static constexpr SkScalar kCubicTolerance = 0.2f;
747 static constexpr SkScalar kQuadToleranceSqd = kQuadTolerance * kQuadTolerance;
748 static constexpr SkScalar kCubicToleranceSqd = kCubicTolerance * kCubicTolerance;
749 #endif
750 static constexpr SkScalar kConicTolerance = 0.25f;
751
752 // clamps the point to the nearest 16th of a pixel
sanitize_point(const SkPoint & in,SkPoint * out)753 static void sanitize_point(const SkPoint& in, SkPoint* out) {
754 out->fX = SkScalarRoundToScalar(16.f*in.fX)*0.0625f;
755 out->fY = SkScalarRoundToScalar(16.f*in.fY)*0.0625f;
756 }
757
handleLine(const SkPoint & p)758 void SkBaseShadowTessellator::handleLine(const SkPoint& p) {
759 SkPoint pSanitized;
760 sanitize_point(p, &pSanitized);
761
762 if (!fPathPolygon.empty()) {
763 if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.size() - 1], pSanitized)) {
764 // skip coincident point
765 return;
766 }
767 }
768
769 if (fPathPolygon.size() > 1) {
770 if (!checkConvexity(fPathPolygon[fPathPolygon.size() - 2],
771 fPathPolygon[fPathPolygon.size() - 1],
772 pSanitized)) {
773 // remove collinear point
774 fPathPolygon.pop_back();
775 // it's possible that the previous point is coincident with the new one now
776 if (duplicate_pt(fPathPolygon[fPathPolygon.size() - 1], pSanitized)) {
777 fPathPolygon.pop_back();
778 }
779 }
780 }
781
782 fPathPolygon.push_back(pSanitized);
783 }
784
handleLine(const SkMatrix & m,SkPoint * p)785 void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) {
786 m.mapPoints(p, 1);
787
788 this->handleLine(*p);
789 }
790
handleQuad(const SkPoint pts[3])791 void SkBaseShadowTessellator::handleQuad(const SkPoint pts[3]) {
792 #if defined(SK_GANESH)
793 // check for degeneracy
794 SkVector v0 = pts[1] - pts[0];
795 SkVector v1 = pts[2] - pts[0];
796 if (SkScalarNearlyZero(v0.cross(v1))) {
797 return;
798 }
799 // TODO: Pull PathUtils out of Ganesh?
800 int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
801 fPointBuffer.resize(maxCount);
802 SkPoint* target = fPointBuffer.begin();
803 int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
804 kQuadToleranceSqd, &target, maxCount);
805 fPointBuffer.resize(count);
806 for (int i = 0; i < count; i++) {
807 this->handleLine(fPointBuffer[i]);
808 }
809 #else
810 // for now, just to draw something
811 this->handleLine(pts[1]);
812 this->handleLine(pts[2]);
813 #endif
814 }
815
handleQuad(const SkMatrix & m,SkPoint pts[3])816 void SkBaseShadowTessellator::handleQuad(const SkMatrix& m, SkPoint pts[3]) {
817 m.mapPoints(pts, 3);
818 this->handleQuad(pts);
819 }
820
handleCubic(const SkMatrix & m,SkPoint pts[4])821 void SkBaseShadowTessellator::handleCubic(const SkMatrix& m, SkPoint pts[4]) {
822 m.mapPoints(pts, 4);
823 #if defined(SK_GANESH)
824 // TODO: Pull PathUtils out of Ganesh?
825 int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
826 fPointBuffer.resize(maxCount);
827 SkPoint* target = fPointBuffer.begin();
828 int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
829 kCubicToleranceSqd, &target, maxCount);
830 fPointBuffer.resize(count);
831 for (int i = 0; i < count; i++) {
832 this->handleLine(fPointBuffer[i]);
833 }
834 #else
835 // for now, just to draw something
836 this->handleLine(pts[1]);
837 this->handleLine(pts[2]);
838 this->handleLine(pts[3]);
839 #endif
840 }
841
handleConic(const SkMatrix & m,SkPoint pts[3],SkScalar w)842 void SkBaseShadowTessellator::handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w) {
843 if (m.hasPerspective()) {
844 w = SkConic::TransformW(pts, w, m);
845 }
846 m.mapPoints(pts, 3);
847 SkAutoConicToQuads quadder;
848 const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance);
849 SkPoint lastPoint = *(quads++);
850 int count = quadder.countQuads();
851 for (int i = 0; i < count; ++i) {
852 SkPoint quadPts[3];
853 quadPts[0] = lastPoint;
854 quadPts[1] = quads[0];
855 quadPts[2] = i == count - 1 ? pts[2] : quads[1];
856 this->handleQuad(quadPts);
857 lastPoint = quadPts[2];
858 quads += 2;
859 }
860 }
861
addArc(const SkVector & nextNormal,SkScalar offset,bool finishArc)862 bool SkBaseShadowTessellator::addArc(const SkVector& nextNormal, SkScalar offset, bool finishArc) {
863 // fill in fan from previous quad
864 SkScalar rotSin, rotCos;
865 int numSteps;
866 if (!SkComputeRadialSteps(fPrevOutset, nextNormal, offset, &rotSin, &rotCos, &numSteps)) {
867 // recover as best we can
868 numSteps = 0;
869 }
870 SkVector prevNormal = fPrevOutset;
871 for (int i = 0; i < numSteps-1; ++i) {
872 SkVector currNormal;
873 currNormal.fX = prevNormal.fX*rotCos - prevNormal.fY*rotSin;
874 currNormal.fY = prevNormal.fY*rotCos + prevNormal.fX*rotSin;
875 fPositions.push_back(fPrevPoint + currNormal);
876 fColors.push_back(kPenumbraColor);
877 this->appendTriangle(fPrevUmbraIndex, fPositions.size() - 1, fPositions.size() - 2);
878
879 prevNormal = currNormal;
880 }
881 if (finishArc && numSteps) {
882 fPositions.push_back(fPrevPoint + nextNormal);
883 fColors.push_back(kPenumbraColor);
884 this->appendTriangle(fPrevUmbraIndex, fPositions.size() - 1, fPositions.size() - 2);
885 }
886 fPrevOutset = nextNormal;
887
888 return (numSteps > 0);
889 }
890
appendTriangle(uint16_t index0,uint16_t index1,uint16_t index2)891 void SkBaseShadowTessellator::appendTriangle(uint16_t index0, uint16_t index1, uint16_t index2) {
892 auto indices = fIndices.append(3);
893
894 indices[0] = index0;
895 indices[1] = index1;
896 indices[2] = index2;
897 }
898
appendQuad(uint16_t index0,uint16_t index1,uint16_t index2,uint16_t index3)899 void SkBaseShadowTessellator::appendQuad(uint16_t index0, uint16_t index1,
900 uint16_t index2, uint16_t index3) {
901 auto indices = fIndices.append(6);
902
903 indices[0] = index0;
904 indices[1] = index1;
905 indices[2] = index2;
906
907 indices[3] = index2;
908 indices[4] = index1;
909 indices[5] = index3;
910 }
911
912 //////////////////////////////////////////////////////////////////////////////////////////////////
913
914 class SkAmbientShadowTessellator : public SkBaseShadowTessellator {
915 public:
916 SkAmbientShadowTessellator(const SkPath& path, const SkMatrix& ctm,
917 const SkPoint3& zPlaneParams, bool transparent);
918
919 private:
920 bool computePathPolygon(const SkPath& path, const SkMatrix& ctm);
921
922 using INHERITED = SkBaseShadowTessellator;
923 };
924
SkAmbientShadowTessellator(const SkPath & path,const SkMatrix & ctm,const SkPoint3 & zPlaneParams,bool transparent)925 SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
926 const SkMatrix& ctm,
927 const SkPoint3& zPlaneParams,
928 bool transparent)
929 : INHERITED(zPlaneParams, path.getBounds(), transparent) {
930 // Set base colors
931 auto baseZ = heightFunc(fPathBounds.centerX(), fPathBounds.centerY());
932 // umbraColor is the interior value, penumbraColor the exterior value.
933 auto outset = SkDrawShadowMetrics::AmbientBlurRadius(baseZ);
934 auto inset = outset * SkDrawShadowMetrics::AmbientRecipAlpha(baseZ) - outset;
935
936 if (!this->computePathPolygon(path, ctm)) {
937 return;
938 }
939 if (fPathPolygon.size() < 3 || !SkIsFinite(fArea)) {
940 fSucceeded = true; // We don't want to try to blur these cases, so we will
941 // return an empty SkVertices instead.
942 return;
943 }
944
945 // Outer ring: 3*numPts
946 // Middle ring: numPts
947 fPositions.reserve(4 * path.countPoints());
948 fColors.reserve(4 * path.countPoints());
949 // Outer ring: 12*numPts
950 // Middle ring: 0
951 fIndices.reserve(12 * path.countPoints());
952
953 if (fIsConvex) {
954 fSucceeded = this->computeConvexShadow(inset, outset, false);
955 } else {
956 fSucceeded = this->computeConcaveShadow(inset, outset);
957 }
958 }
959
computePathPolygon(const SkPath & path,const SkMatrix & ctm)960 bool SkAmbientShadowTessellator::computePathPolygon(const SkPath& path, const SkMatrix& ctm) {
961 fPathPolygon.reserve(path.countPoints());
962
963 // walk around the path, tessellate and generate outer ring
964 // if original path is transparent, will accumulate sum of points for centroid
965 SkPath::Iter iter(path, true);
966 SkPoint pts[4];
967 SkPath::Verb verb;
968 bool verbSeen = false;
969 bool closeSeen = false;
970 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
971 if (closeSeen) {
972 return false;
973 }
974 switch (verb) {
975 case SkPath::kLine_Verb:
976 this->handleLine(ctm, &pts[1]);
977 break;
978 case SkPath::kQuad_Verb:
979 this->handleQuad(ctm, pts);
980 break;
981 case SkPath::kCubic_Verb:
982 this->handleCubic(ctm, pts);
983 break;
984 case SkPath::kConic_Verb:
985 this->handleConic(ctm, pts, iter.conicWeight());
986 break;
987 case SkPath::kMove_Verb:
988 if (verbSeen) {
989 return false;
990 }
991 break;
992 case SkPath::kClose_Verb:
993 case SkPath::kDone_Verb:
994 closeSeen = true;
995 break;
996 }
997 verbSeen = true;
998 }
999
1000 this->finishPathPolygon();
1001 return true;
1002 }
1003
1004 ///////////////////////////////////////////////////////////////////////////////////////////////////
1005
1006 class SkSpotShadowTessellator : public SkBaseShadowTessellator {
1007 public:
1008 SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm,
1009 const SkPoint3& zPlaneParams, const SkPoint3& lightPos,
1010 SkScalar lightRadius, bool transparent, bool directional);
1011
1012 private:
1013 bool computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
1014 const SkMatrix& shadowTransform);
1015 void addToClip(const SkVector& nextPoint);
1016
1017 using INHERITED = SkBaseShadowTessellator;
1018 };
1019
SkSpotShadowTessellator(const SkPath & path,const SkMatrix & ctm,const SkPoint3 & zPlaneParams,const SkPoint3 & lightPos,SkScalar lightRadius,bool transparent,bool directional)1020 SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm,
1021 const SkPoint3& zPlaneParams,
1022 const SkPoint3& lightPos, SkScalar lightRadius,
1023 bool transparent, bool directional)
1024 : INHERITED(zPlaneParams, path.getBounds(), transparent) {
1025
1026 // Compute the blur radius, scale and translation for the spot shadow.
1027 SkMatrix shadowTransform;
1028 SkScalar outset;
1029 if (!SkDrawShadowMetrics::GetSpotShadowTransform(lightPos, lightRadius, ctm, zPlaneParams,
1030 path.getBounds(), directional,
1031 &shadowTransform, &outset)) {
1032 return;
1033 }
1034 SkScalar inset = outset;
1035
1036 // compute rough clip bounds for umbra, plus offset polygon, plus centroid
1037 if (!this->computeClipAndPathPolygons(path, ctm, shadowTransform)) {
1038 return;
1039 }
1040 if (fClipPolygon.size() < 3 || fPathPolygon.size() < 3 || !SkIsFinite(fArea)) {
1041 fSucceeded = true; // We don't want to try to blur these cases, so we will
1042 // return an empty SkVertices instead.
1043 return;
1044 }
1045
1046 // TODO: calculate these reserves better
1047 // Penumbra ring: 3*numPts
1048 // Umbra ring: numPts
1049 // Inner ring: numPts
1050 fPositions.reserve(5 * path.countPoints());
1051 fColors.reserve(5 * path.countPoints());
1052 // Penumbra ring: 12*numPts
1053 // Umbra ring: 3*numPts
1054 fIndices.reserve(15 * path.countPoints());
1055
1056 if (fIsConvex) {
1057 fSucceeded = this->computeConvexShadow(inset, outset, true);
1058 } else {
1059 fSucceeded = this->computeConcaveShadow(inset, outset);
1060 }
1061
1062 if (!fSucceeded) {
1063 return;
1064 }
1065
1066 fSucceeded = true;
1067 }
1068
computeClipAndPathPolygons(const SkPath & path,const SkMatrix & ctm,const SkMatrix & shadowTransform)1069 bool SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
1070 const SkMatrix& shadowTransform) {
1071
1072 fPathPolygon.reserve(path.countPoints());
1073 fClipPolygon.reserve(path.countPoints());
1074
1075 // Walk around the path and compute clip polygon and path polygon.
1076 // Will also accumulate sum of areas for centroid.
1077 // For Bezier curves, we compute additional interior points on curve.
1078 SkPath::Iter iter(path, true);
1079 SkPoint pts[4];
1080 SkPoint clipPts[4];
1081 SkPath::Verb verb;
1082
1083 // coefficients to compute cubic Bezier at t = 5/16
1084 static constexpr SkScalar kA = 0.32495117187f;
1085 static constexpr SkScalar kB = 0.44311523437f;
1086 static constexpr SkScalar kC = 0.20141601562f;
1087 static constexpr SkScalar kD = 0.03051757812f;
1088
1089 SkPoint curvePoint;
1090 SkScalar w;
1091 bool closeSeen = false;
1092 bool verbSeen = false;
1093 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1094 if (closeSeen) {
1095 return false;
1096 }
1097 switch (verb) {
1098 case SkPath::kLine_Verb:
1099 ctm.mapPoints(clipPts, &pts[1], 1);
1100 this->addToClip(clipPts[0]);
1101 this->handleLine(shadowTransform, &pts[1]);
1102 break;
1103 case SkPath::kQuad_Verb:
1104 ctm.mapPoints(clipPts, pts, 3);
1105 // point at t = 1/2
1106 curvePoint.fX = 0.25f*clipPts[0].fX + 0.5f*clipPts[1].fX + 0.25f*clipPts[2].fX;
1107 curvePoint.fY = 0.25f*clipPts[0].fY + 0.5f*clipPts[1].fY + 0.25f*clipPts[2].fY;
1108 this->addToClip(curvePoint);
1109 this->addToClip(clipPts[2]);
1110 this->handleQuad(shadowTransform, pts);
1111 break;
1112 case SkPath::kConic_Verb:
1113 ctm.mapPoints(clipPts, pts, 3);
1114 w = iter.conicWeight();
1115 // point at t = 1/2
1116 curvePoint.fX = 0.25f*clipPts[0].fX + w*0.5f*clipPts[1].fX + 0.25f*clipPts[2].fX;
1117 curvePoint.fY = 0.25f*clipPts[0].fY + w*0.5f*clipPts[1].fY + 0.25f*clipPts[2].fY;
1118 curvePoint *= SkScalarInvert(0.5f + 0.5f*w);
1119 this->addToClip(curvePoint);
1120 this->addToClip(clipPts[2]);
1121 this->handleConic(shadowTransform, pts, w);
1122 break;
1123 case SkPath::kCubic_Verb:
1124 ctm.mapPoints(clipPts, pts, 4);
1125 // point at t = 5/16
1126 curvePoint.fX = kA*clipPts[0].fX + kB*clipPts[1].fX
1127 + kC*clipPts[2].fX + kD*clipPts[3].fX;
1128 curvePoint.fY = kA*clipPts[0].fY + kB*clipPts[1].fY
1129 + kC*clipPts[2].fY + kD*clipPts[3].fY;
1130 this->addToClip(curvePoint);
1131 // point at t = 11/16
1132 curvePoint.fX = kD*clipPts[0].fX + kC*clipPts[1].fX
1133 + kB*clipPts[2].fX + kA*clipPts[3].fX;
1134 curvePoint.fY = kD*clipPts[0].fY + kC*clipPts[1].fY
1135 + kB*clipPts[2].fY + kA*clipPts[3].fY;
1136 this->addToClip(curvePoint);
1137 this->addToClip(clipPts[3]);
1138 this->handleCubic(shadowTransform, pts);
1139 break;
1140 case SkPath::kMove_Verb:
1141 if (verbSeen) {
1142 return false;
1143 }
1144 break;
1145 case SkPath::kClose_Verb:
1146 case SkPath::kDone_Verb:
1147 closeSeen = true;
1148 break;
1149 default:
1150 SkDEBUGFAIL("unknown verb");
1151 }
1152 verbSeen = true;
1153 }
1154
1155 this->finishPathPolygon();
1156 return true;
1157 }
1158
addToClip(const SkPoint & point)1159 void SkSpotShadowTessellator::addToClip(const SkPoint& point) {
1160 if (fClipPolygon.empty() || !duplicate_pt(point, fClipPolygon[fClipPolygon.size() - 1])) {
1161 fClipPolygon.push_back(point);
1162 }
1163 }
1164
1165 ///////////////////////////////////////////////////////////////////////////////////////////////////
1166
MakeAmbient(const SkPath & path,const SkMatrix & ctm,const SkPoint3 & zPlane,bool transparent)1167 sk_sp<SkVertices> SkShadowTessellator::MakeAmbient(const SkPath& path, const SkMatrix& ctm,
1168 const SkPoint3& zPlane, bool transparent) {
1169 if (!ctm.mapRect(path.getBounds()).isFinite() || !zPlane.isFinite()) {
1170 return nullptr;
1171 }
1172 SkAmbientShadowTessellator ambientTess(path, ctm, zPlane, transparent);
1173 return ambientTess.releaseVertices();
1174 }
1175
MakeSpot(const SkPath & path,const SkMatrix & ctm,const SkPoint3 & zPlane,const SkPoint3 & lightPos,SkScalar lightRadius,bool transparent,bool directional)1176 sk_sp<SkVertices> SkShadowTessellator::MakeSpot(const SkPath& path, const SkMatrix& ctm,
1177 const SkPoint3& zPlane, const SkPoint3& lightPos,
1178 SkScalar lightRadius, bool transparent,
1179 bool directional) {
1180 if (!ctm.mapRect(path.getBounds()).isFinite() || !zPlane.isFinite() ||
1181 !lightPos.isFinite() || !(lightPos.fZ >= SK_ScalarNearlyZero) ||
1182 !SkIsFinite(lightRadius) || !(lightRadius >= SK_ScalarNearlyZero)) {
1183 return nullptr;
1184 }
1185 SkSpotShadowTessellator spotTess(path, ctm, zPlane, lightPos, lightRadius, transparent,
1186 directional);
1187 return spotTess.releaseVertices();
1188 }
1189
1190 #endif // !defined(SK_ENABLE_OPTIMIZE_SIZE)
1191
1192