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