/* * Copyright 2017 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #include "SkShadowTessellator.h" #include "SkColorData.h" #include "SkDrawShadowInfo.h" #include "SkGeometry.h" #include "SkOffsetPolygon.h" #include "SkPath.h" #include "SkPoint3.h" #include "SkPointPriv.h" #include "SkVertices.h" #if SK_SUPPORT_GPU #include "GrPathUtils.h" #endif /** * Base class */ class SkBaseShadowTessellator { public: SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent); virtual ~SkBaseShadowTessellator() {} sk_sp releaseVertices() { if (!fSucceeded) { return nullptr; } return SkVertices::MakeCopy(SkVertices::kTriangles_VertexMode, this->vertexCount(), fPositions.begin(), nullptr, fColors.begin(), this->indexCount(), fIndices.begin()); } protected: static constexpr auto kMinHeight = 0.1f; int vertexCount() const { return fPositions.count(); } int indexCount() const { return fIndices.count(); } bool setZOffset(const SkRect& bounds, bool perspective); bool accumulateCentroid(const SkPoint& c, const SkPoint& n); bool checkConvexity(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2); void finishPathPolygon(); void stitchConcaveRings(const SkTDArray& umbraPolygon, SkTDArray* umbraIndices, const SkTDArray& penumbraPolygon, SkTDArray* penumbraIndices); void handleLine(const SkPoint& p); void handleLine(const SkMatrix& m, SkPoint* p); void handleQuad(const SkPoint pts[3]); void handleQuad(const SkMatrix& m, SkPoint pts[3]); void handleCubic(const SkMatrix& m, SkPoint pts[4]); void handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w); bool setTransformedHeightFunc(const SkMatrix& ctm); bool addArc(const SkVector& nextNormal, bool finishArc); void appendTriangle(uint16_t index0, uint16_t index1, uint16_t index2); void appendQuad(uint16_t index0, uint16_t index1, uint16_t index2, uint16_t index3); SkScalar heightFunc(SkScalar x, SkScalar y) { return fZPlaneParams.fX*x + fZPlaneParams.fY*y + fZPlaneParams.fZ; } SkPoint3 fZPlaneParams; std::function fTransformedHeightFunc; SkScalar fZOffset; // members for perspective height function SkPoint3 fTransformedZParams; SkScalar fPartialDeterminants[3]; // temporary buffer SkTDArray fPointBuffer; SkTDArray fPositions; SkTDArray fColors; SkTDArray fIndices; SkTDArray fPathPolygon; SkPoint fCentroid; SkScalar fArea; SkScalar fLastArea; int fAreaSignFlips; SkScalar fLastCross; int fFirstVertexIndex; SkVector fFirstOutset; SkPoint fFirstPoint; bool fSucceeded; bool fTransparent; bool fIsConvex; SkColor fUmbraColor; SkColor fPenumbraColor; SkScalar fRadius; SkScalar fDirection; int fPrevUmbraIndex; SkVector fPrevOutset; SkPoint fPrevPoint; }; static bool compute_normal(const SkPoint& p0, const SkPoint& p1, SkScalar dir, SkVector* newNormal) { SkVector normal; // compute perpendicular normal.fX = p0.fY - p1.fY; normal.fY = p1.fX - p0.fX; normal *= dir; if (!normal.normalize()) { return false; } *newNormal = normal; return true; } static void compute_radial_steps(const SkVector& v1, const SkVector& v2, SkScalar r, SkScalar* rotSin, SkScalar* rotCos, int* n) { const SkScalar kRecipPixelsPerArcSegment = 0.125f; SkScalar rCos = v1.dot(v2); SkScalar rSin = v1.cross(v2); SkScalar theta = SkScalarATan2(rSin, rCos); int steps = SkScalarRoundToInt(SkScalarAbs(r*theta*kRecipPixelsPerArcSegment)); SkScalar dTheta = theta / steps; *rotSin = SkScalarSinCos(dTheta, rotCos); *n = steps; } static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) { static constexpr SkScalar kClose = (SK_Scalar1 / 16); static constexpr SkScalar kCloseSqd = kClose * kClose; SkScalar distSq = SkPointPriv::DistanceToSqd(p0, p1); return distSq < kCloseSqd; } static SkScalar perp_dot(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { SkVector v0 = p1 - p0; SkVector v1 = p2 - p0; return v0.cross(v1); } SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent) : fZPlaneParams(zPlaneParams) , fZOffset(0) , fCentroid({0, 0}) , fArea(0) , fLastArea(0) , fAreaSignFlips(0) , fLastCross(0) , fFirstVertexIndex(-1) , fSucceeded(false) , fTransparent(transparent) , fIsConvex(true) , fDirection(1) , fPrevUmbraIndex(-1) { // child classes will set reserve for positions, colors and indices } bool SkBaseShadowTessellator::setZOffset(const SkRect& bounds, bool perspective) { SkScalar minZ = this->heightFunc(bounds.fLeft, bounds.fTop); if (perspective) { SkScalar z = this->heightFunc(bounds.fLeft, bounds.fBottom); if (z < minZ) { minZ = z; } z = this->heightFunc(bounds.fRight, bounds.fTop); if (z < minZ) { minZ = z; } z = this->heightFunc(bounds.fRight, bounds.fBottom); if (z < minZ) { minZ = z; } } if (minZ < kMinHeight) { fZOffset = -minZ + kMinHeight; return true; } return false; } bool SkBaseShadowTessellator::accumulateCentroid(const SkPoint& curr, const SkPoint& next) { if (duplicate_pt(curr, next)) { return false; } SkScalar quadArea = curr.cross(next); fCentroid.fX += (curr.fX + next.fX) * quadArea; fCentroid.fY += (curr.fY + next.fY) * quadArea; fArea += quadArea; // convexity check if (quadArea*fLastArea < 0) { ++fAreaSignFlips; } fLastArea = quadArea; return true; } bool SkBaseShadowTessellator::checkConvexity(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { SkScalar cross = perp_dot(p0, p1, p2); // skip collinear point if (SkScalarNearlyZero(cross)) { return false; } // check for convexity if (fLastCross*cross < 0) { fIsConvex = false; } fLastCross = cross; return true; } void SkBaseShadowTessellator::finishPathPolygon() { if (fPathPolygon.count() > 1) { if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], fPathPolygon[0])) { // remove coincident point fPathPolygon.pop(); } } if (fPathPolygon.count() > 2) { if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2], fPathPolygon[fPathPolygon.count() - 1], fPathPolygon[0])) { // remove collinear point fPathPolygon[0] = fPathPolygon[fPathPolygon.count() - 1]; fPathPolygon.pop(); } } fCentroid *= sk_ieee_float_divide(1, 3 * fArea); // It's possible to have a concave path that self-intersects but also passes the // cross-product check (e.g., a star). In that case, the signed area will change signs more // than twice, so we check for that here. if (fAreaSignFlips > 2) { fIsConvex = false; } // if area is positive, winding is ccw fDirection = fArea > 0 ? -1 : 1; } void SkBaseShadowTessellator::stitchConcaveRings(const SkTDArray& umbraPolygon, SkTDArray* umbraIndices, const SkTDArray& penumbraPolygon, SkTDArray* penumbraIndices) { // find minimum indices int minIndex = 0; int min = (*penumbraIndices)[0]; for (int i = 1; i < (*penumbraIndices).count(); ++i) { if ((*penumbraIndices)[i] < min) { min = (*penumbraIndices)[i]; minIndex = i; } } int currPenumbra = minIndex; minIndex = 0; min = (*umbraIndices)[0]; for (int i = 1; i < (*umbraIndices).count(); ++i) { if ((*umbraIndices)[i] < min) { min = (*umbraIndices)[i]; minIndex = i; } } int currUmbra = minIndex; // now find a case where the indices are equal (there should be at least one) int maxPenumbraIndex = fPathPolygon.count() - 1; int maxUmbraIndex = fPathPolygon.count() - 1; while ((*penumbraIndices)[currPenumbra] != (*umbraIndices)[currUmbra]) { if ((*penumbraIndices)[currPenumbra] < (*umbraIndices)[currUmbra]) { (*penumbraIndices)[currPenumbra] += fPathPolygon.count(); maxPenumbraIndex = (*penumbraIndices)[currPenumbra]; currPenumbra = (currPenumbra + 1) % penumbraPolygon.count(); } else { (*umbraIndices)[currUmbra] += fPathPolygon.count(); maxUmbraIndex = (*umbraIndices)[currUmbra]; currUmbra = (currUmbra + 1) % umbraPolygon.count(); } } *fPositions.push() = penumbraPolygon[currPenumbra]; *fColors.push() = fPenumbraColor; int prevPenumbraIndex = 0; *fPositions.push() = umbraPolygon[currUmbra]; *fColors.push() = fUmbraColor; fPrevUmbraIndex = 1; int nextPenumbra = (currPenumbra + 1) % penumbraPolygon.count(); int nextUmbra = (currUmbra + 1) % umbraPolygon.count(); while ((*penumbraIndices)[nextPenumbra] <= maxPenumbraIndex || (*umbraIndices)[nextUmbra] <= maxUmbraIndex) { if ((*umbraIndices)[nextUmbra] == (*penumbraIndices)[nextPenumbra]) { // advance both one step *fPositions.push() = penumbraPolygon[nextPenumbra]; *fColors.push() = fPenumbraColor; int currPenumbraIndex = fPositions.count() - 1; *fPositions.push() = umbraPolygon[nextUmbra]; *fColors.push() = fUmbraColor; int currUmbraIndex = fPositions.count() - 1; this->appendQuad(prevPenumbraIndex, currPenumbraIndex, fPrevUmbraIndex, currUmbraIndex); prevPenumbraIndex = currPenumbraIndex; (*penumbraIndices)[currPenumbra] += fPathPolygon.count(); currPenumbra = nextPenumbra; nextPenumbra = (currPenumbra + 1) % penumbraPolygon.count(); fPrevUmbraIndex = currUmbraIndex; (*umbraIndices)[currUmbra] += fPathPolygon.count(); currUmbra = nextUmbra; nextUmbra = (currUmbra + 1) % umbraPolygon.count(); } while ((*penumbraIndices)[nextPenumbra] < (*umbraIndices)[nextUmbra] && (*penumbraIndices)[nextPenumbra] <= maxPenumbraIndex) { // fill out penumbra arc *fPositions.push() = penumbraPolygon[nextPenumbra]; *fColors.push() = fPenumbraColor; int currPenumbraIndex = fPositions.count() - 1; this->appendTriangle(prevPenumbraIndex, currPenumbraIndex, fPrevUmbraIndex); prevPenumbraIndex = currPenumbraIndex; // this ensures the ordering when we wrap around (*penumbraIndices)[currPenumbra] += fPathPolygon.count(); currPenumbra = nextPenumbra; nextPenumbra = (currPenumbra + 1) % penumbraPolygon.count(); } while ((*umbraIndices)[nextUmbra] < (*penumbraIndices)[nextPenumbra] && (*umbraIndices)[nextUmbra] <= maxUmbraIndex) { // fill out umbra arc *fPositions.push() = umbraPolygon[nextUmbra]; *fColors.push() = fUmbraColor; int currUmbraIndex = fPositions.count() - 1; this->appendTriangle(fPrevUmbraIndex, prevPenumbraIndex, currUmbraIndex); fPrevUmbraIndex = currUmbraIndex; // this ensures the ordering when we wrap around (*umbraIndices)[currUmbra] += fPathPolygon.count(); currUmbra = nextUmbra; nextUmbra = (currUmbra + 1) % umbraPolygon.count(); } } // finish up by advancing both one step *fPositions.push() = penumbraPolygon[nextPenumbra]; *fColors.push() = fPenumbraColor; int currPenumbraIndex = fPositions.count() - 1; *fPositions.push() = umbraPolygon[nextUmbra]; *fColors.push() = fUmbraColor; int currUmbraIndex = fPositions.count() - 1; this->appendQuad(prevPenumbraIndex, currPenumbraIndex, fPrevUmbraIndex, currUmbraIndex); if (fTransparent) { // TODO: fill penumbra } } // tesselation tolerance values, in device space pixels #if SK_SUPPORT_GPU static const SkScalar kQuadTolerance = 0.2f; static const SkScalar kCubicTolerance = 0.2f; #endif static const SkScalar kConicTolerance = 0.5f; // clamps the point to the nearest 16th of a pixel static void sanitize_point(const SkPoint& in, SkPoint* out) { out->fX = SkScalarRoundToScalar(16.f*in.fX)*0.0625f; out->fY = SkScalarRoundToScalar(16.f*in.fY)*0.0625f; } void SkBaseShadowTessellator::handleLine(const SkPoint& p) { SkPoint pSanitized; sanitize_point(p, &pSanitized); if (fPathPolygon.count() > 0) { if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], pSanitized)) { // skip coincident point return; } } if (fPathPolygon.count() > 1) { if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2], fPathPolygon[fPathPolygon.count() - 1], pSanitized)) { // remove collinear point fPathPolygon.pop(); } } *fPathPolygon.push() = pSanitized; } void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) { m.mapPoints(p, 1); this->handleLine(*p); } void SkBaseShadowTessellator::handleQuad(const SkPoint pts[3]) { #if SK_SUPPORT_GPU // check for degeneracy SkVector v0 = pts[1] - pts[0]; SkVector v1 = pts[2] - pts[0]; if (SkScalarNearlyZero(v0.cross(v1))) { return; } // TODO: Pull PathUtils out of Ganesh? int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance); fPointBuffer.setCount(maxCount); SkPoint* target = fPointBuffer.begin(); int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2], kQuadTolerance, &target, maxCount); fPointBuffer.setCount(count); for (int i = 0; i < count; i++) { this->handleLine(fPointBuffer[i]); } #else // for now, just to draw something this->handleLine(pts[1]); this->handleLine(pts[2]); #endif } void SkBaseShadowTessellator::handleQuad(const SkMatrix& m, SkPoint pts[3]) { m.mapPoints(pts, 3); this->handleQuad(pts); } void SkBaseShadowTessellator::handleCubic(const SkMatrix& m, SkPoint pts[4]) { m.mapPoints(pts, 4); #if SK_SUPPORT_GPU // TODO: Pull PathUtils out of Ganesh? int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance); fPointBuffer.setCount(maxCount); SkPoint* target = fPointBuffer.begin(); int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3], kCubicTolerance, &target, maxCount); fPointBuffer.setCount(count); for (int i = 0; i < count; i++) { this->handleLine(fPointBuffer[i]); } #else // for now, just to draw something this->handleLine(pts[1]); this->handleLine(pts[2]); this->handleLine(pts[3]); #endif } void SkBaseShadowTessellator::handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w) { if (m.hasPerspective()) { w = SkConic::TransformW(pts, w, m); } m.mapPoints(pts, 3); SkAutoConicToQuads quadder; const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance); SkPoint lastPoint = *(quads++); int count = quadder.countQuads(); for (int i = 0; i < count; ++i) { SkPoint quadPts[3]; quadPts[0] = lastPoint; quadPts[1] = quads[0]; quadPts[2] = i == count - 1 ? pts[2] : quads[1]; this->handleQuad(quadPts); lastPoint = quadPts[2]; quads += 2; } } bool SkBaseShadowTessellator::addArc(const SkVector& nextNormal, bool finishArc) { // fill in fan from previous quad SkScalar rotSin, rotCos; int numSteps; compute_radial_steps(fPrevOutset, nextNormal, fRadius, &rotSin, &rotCos, &numSteps); SkVector prevNormal = fPrevOutset; for (int i = 0; i < numSteps-1; ++i) { SkVector currNormal; currNormal.fX = prevNormal.fX*rotCos - prevNormal.fY*rotSin; currNormal.fY = prevNormal.fY*rotCos + prevNormal.fX*rotSin; *fPositions.push() = fPrevPoint + currNormal; *fColors.push() = fPenumbraColor; this->appendTriangle(fPrevUmbraIndex, fPositions.count() - 1, fPositions.count() - 2); prevNormal = currNormal; } if (finishArc && numSteps) { *fPositions.push() = fPrevPoint + nextNormal; *fColors.push() = fPenumbraColor; this->appendTriangle(fPrevUmbraIndex, fPositions.count() - 1, fPositions.count() - 2); } fPrevOutset = nextNormal; return (numSteps > 0); } void SkBaseShadowTessellator::appendTriangle(uint16_t index0, uint16_t index1, uint16_t index2) { auto indices = fIndices.append(3); indices[0] = index0; indices[1] = index1; indices[2] = index2; } void SkBaseShadowTessellator::appendQuad(uint16_t index0, uint16_t index1, uint16_t index2, uint16_t index3) { auto indices = fIndices.append(6); indices[0] = index0; indices[1] = index1; indices[2] = index2; indices[3] = index2; indices[4] = index1; indices[5] = index3; } bool SkBaseShadowTessellator::setTransformedHeightFunc(const SkMatrix& ctm) { if (SkScalarNearlyZero(fZPlaneParams.fX) && SkScalarNearlyZero(fZPlaneParams.fY)) { fTransformedHeightFunc = [this](const SkPoint& p) { return fZPlaneParams.fZ; }; } else { SkMatrix ctmInverse; if (!ctm.invert(&ctmInverse) || !ctmInverse.isFinite()) { return false; } // multiply by transpose fTransformedZParams = SkPoint3::Make( ctmInverse[SkMatrix::kMScaleX] * fZPlaneParams.fX + ctmInverse[SkMatrix::kMSkewY] * fZPlaneParams.fY + ctmInverse[SkMatrix::kMPersp0] * fZPlaneParams.fZ, ctmInverse[SkMatrix::kMSkewX] * fZPlaneParams.fX + ctmInverse[SkMatrix::kMScaleY] * fZPlaneParams.fY + ctmInverse[SkMatrix::kMPersp1] * fZPlaneParams.fZ, ctmInverse[SkMatrix::kMTransX] * fZPlaneParams.fX + ctmInverse[SkMatrix::kMTransY] * fZPlaneParams.fY + ctmInverse[SkMatrix::kMPersp2] * fZPlaneParams.fZ ); if (ctm.hasPerspective()) { // We use Cramer's rule to solve for the W value for a given post-divide X and Y, // so pre-compute those values that are independent of X and Y. // W is det(ctmInverse)/(PD[0]*X + PD[1]*Y + PD[2]) fPartialDeterminants[0] = ctm[SkMatrix::kMSkewY] * ctm[SkMatrix::kMPersp1] - ctm[SkMatrix::kMScaleY] * ctm[SkMatrix::kMPersp0]; fPartialDeterminants[1] = ctm[SkMatrix::kMPersp0] * ctm[SkMatrix::kMSkewX] - ctm[SkMatrix::kMPersp1] * ctm[SkMatrix::kMScaleX]; fPartialDeterminants[2] = ctm[SkMatrix::kMScaleX] * ctm[SkMatrix::kMScaleY] - ctm[SkMatrix::kMSkewX] * ctm[SkMatrix::kMSkewY]; SkScalar ctmDeterminant = ctm[SkMatrix::kMTransX] * fPartialDeterminants[0] + ctm[SkMatrix::kMTransY] * fPartialDeterminants[1] + ctm[SkMatrix::kMPersp2] * fPartialDeterminants[2]; // Pre-bake the numerator of Cramer's rule into the zParams to avoid another multiply. // TODO: this may introduce numerical instability, but I haven't seen any issues yet. fTransformedZParams.fX *= ctmDeterminant; fTransformedZParams.fY *= ctmDeterminant; fTransformedZParams.fZ *= ctmDeterminant; fTransformedHeightFunc = [this](const SkPoint& p) { SkScalar denom = p.fX * fPartialDeterminants[0] + p.fY * fPartialDeterminants[1] + fPartialDeterminants[2]; SkScalar w = SkScalarFastInvert(denom); return fZOffset + w*(fTransformedZParams.fX * p.fX + fTransformedZParams.fY * p.fY + fTransformedZParams.fZ); }; } else { fTransformedHeightFunc = [this](const SkPoint& p) { return fZOffset + fTransformedZParams.fX * p.fX + fTransformedZParams.fY * p.fY + fTransformedZParams.fZ; }; } } return true; } ////////////////////////////////////////////////////////////////////////////////////////////////// class SkAmbientShadowTessellator : public SkBaseShadowTessellator { public: SkAmbientShadowTessellator(const SkPath& path, const SkMatrix& ctm, const SkPoint3& zPlaneParams, bool transparent); private: bool computePathPolygon(const SkPath& path, const SkMatrix& ctm); bool computeConvexShadow(); bool computeConcaveShadow(); void handlePolyPoint(const SkPoint& p, bool finalPoint); void addEdge(const SkPoint& nextPoint, const SkVector& nextNormal, bool finalEdge); void splitEdge(const SkPoint& nextPoint, const SkVector& insetNormal, const SkPoint& penumbraPoint, const SkPoint& umbraPoint, SkColor umbraColor); static constexpr auto kMaxEdgeLenSqr = 20 * 20; static constexpr auto kInsetFactor = -0.5f; SkScalar offset(SkScalar z) { return SkDrawShadowMetrics::AmbientBlurRadius(z); } SkColor umbraColor(SkScalar z) { SkScalar umbraAlpha = SkScalarInvert(SkDrawShadowMetrics::AmbientRecipAlpha(z)); return SkColorSetARGB(umbraAlpha * 255.9999f, 0, 0, 0); } bool fSplitFirstEdge; bool fSplitPreviousEdge; typedef SkBaseShadowTessellator INHERITED; }; SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path, const SkMatrix& ctm, const SkPoint3& zPlaneParams, bool transparent) : INHERITED(zPlaneParams, transparent) , fSplitFirstEdge(false) , fSplitPreviousEdge(false) { // Set base colors SkScalar umbraAlpha = SkScalarInvert(SkDrawShadowMetrics::AmbientRecipAlpha(heightFunc(0, 0))); // umbraColor is the interior value, penumbraColor the exterior value. // umbraAlpha is the factor that is linearly interpolated from outside to inside, and // then "blurred" by the GrBlurredEdgeFP. It is then multiplied by fAmbientAlpha to get // the final alpha. fUmbraColor = SkColorSetARGB(umbraAlpha * 255.9999f, 0, 0, 0); fPenumbraColor = SkColorSetARGB(0, 0, 0, 0); // make sure we're not below the canvas plane this->setZOffset(path.getBounds(), ctm.hasPerspective()); if (!this->setTransformedHeightFunc(ctm)) { return; } if (!this->computePathPolygon(path, ctm)) { return; } if (fPathPolygon.count() < 3 || !SkScalarIsFinite(fArea)) { fSucceeded = true; // We don't want to try to blur these cases, so we will // return an empty SkVertices instead. return; } // Outer ring: 3*numPts // Middle ring: numPts fPositions.setReserve(4 * path.countPoints()); fColors.setReserve(4 * path.countPoints()); // Outer ring: 12*numPts // Middle ring: 0 fIndices.setReserve(12 * path.countPoints()); if (fIsConvex) { fSucceeded = this->computeConvexShadow(); } else { fSucceeded = this->computeConcaveShadow(); } } bool SkAmbientShadowTessellator::computePathPolygon(const SkPath& path, const SkMatrix& ctm) { fPathPolygon.setReserve(path.countPoints()); // walk around the path, tessellate and generate outer ring // if original path is transparent, will accumulate sum of points for centroid SkPath::Iter iter(path, true); SkPoint pts[4]; SkPath::Verb verb; bool verbSeen = false; bool closeSeen = false; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { if (closeSeen) { return false; } switch (verb) { case SkPath::kLine_Verb: this->handleLine(ctm, &pts[1]); break; case SkPath::kQuad_Verb: this->handleQuad(ctm, pts); break; case SkPath::kCubic_Verb: this->handleCubic(ctm, pts); break; case SkPath::kConic_Verb: this->handleConic(ctm, pts, iter.conicWeight()); break; case SkPath::kMove_Verb: if (verbSeen) { return false; } break; case SkPath::kClose_Verb: case SkPath::kDone_Verb: closeSeen = true; break; } verbSeen = true; } this->finishPathPolygon(); return true; } bool SkAmbientShadowTessellator::computeConvexShadow() { int polyCount = fPathPolygon.count(); if (polyCount < 3) { return false; } // Add center point for fan if needed if (fTransparent) { *fPositions.push() = fCentroid; *fColors.push() = this->umbraColor(fTransformedHeightFunc(fCentroid)); } // Initialize SkVector normal; if (!compute_normal(fPathPolygon[polyCount-1], fPathPolygon[0], fDirection, &normal)) { // the polygon should be sanitized, so any issues at this point are unrecoverable return false; } fFirstPoint = fPathPolygon[polyCount - 1]; fFirstVertexIndex = fPositions.count(); SkScalar z = fTransformedHeightFunc(fFirstPoint); fFirstOutset = normal; fFirstOutset *= this->offset(z); fPrevOutset = fFirstOutset; fPrevPoint = fFirstPoint; fPrevUmbraIndex = fFirstVertexIndex; // Add the first quad *fPositions.push() = fFirstPoint; *fColors.push() = this->umbraColor(z); *fPositions.push() = fFirstPoint + fFirstOutset; *fColors.push() = fPenumbraColor; z = fTransformedHeightFunc(fPathPolygon[0]); fRadius = this->offset(z); fUmbraColor = this->umbraColor(z); this->addEdge(fPathPolygon[0], normal, false); // Process the remaining points for (int i = 1; i < fPathPolygon.count(); ++i) { this->handlePolyPoint(fPathPolygon[i], i == fPathPolygon.count()-1); } SkASSERT(this->indexCount()); // Final fan SkASSERT(fPositions.count() >= 3); if (this->addArc(fFirstOutset, false)) { this->appendTriangle(fFirstVertexIndex, fPositions.count() - 1, fFirstVertexIndex + 1); } else { // arc is too small, set the first penumbra point to be the same position // as the last one fPositions[fFirstVertexIndex + 1] = fPositions[fPositions.count() - 1]; } return true; } bool SkAmbientShadowTessellator::computeConcaveShadow() { // TODO: remove when we support filling the penumbra if (fTransparent) { return false; } // generate inner ring SkTDArray umbraPolygon; SkTDArray umbraIndices; umbraIndices.setReserve(fPathPolygon.count()); if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.count(), 0.5f, &umbraPolygon, &umbraIndices)) { // TODO: figure out how to handle this case return false; } // generate outer ring SkTDArray penumbraPolygon; SkTDArray penumbraIndices; penumbraPolygon.setReserve(umbraPolygon.count()); penumbraIndices.setReserve(umbraPolygon.count()); auto offsetFunc = [this](const SkPoint& p) { return -this->offset(fTransformedHeightFunc(p)); }; if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.count(), offsetFunc, &penumbraPolygon, &penumbraIndices)) { // TODO: figure out how to handle this case return false; } if (!umbraPolygon.count() || !penumbraPolygon.count()) { return false; } // attach the rings together this->stitchConcaveRings(umbraPolygon, &umbraIndices, penumbraPolygon, &penumbraIndices); return true; } void SkAmbientShadowTessellator::handlePolyPoint(const SkPoint& p, bool finalPoint) { SkVector normal; if (compute_normal(fPrevPoint, p, fDirection, &normal)) { SkVector scaledNormal = normal; scaledNormal *= fRadius; this->addArc(scaledNormal, true); SkScalar z = fTransformedHeightFunc(p); fRadius = this->offset(z); fUmbraColor = this->umbraColor(z); this->addEdge(p, normal, finalPoint); } } void SkAmbientShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal, bool finalEdge) { // We compute the inset in two stages: first we inset by half the current normal, // then on the next addEdge() we add half of the next normal to get an average of the two SkVector insetNormal = nextNormal; insetNormal *= 0.5f*kInsetFactor; // Adding the other half of the average for the previous edge fPositions[fPrevUmbraIndex] += insetNormal; SkPoint umbraPoint; if (finalEdge) { // Again, adding the other half of the average for the previous edge fPositions[fFirstVertexIndex] += insetNormal; // we multiply by another half because now we're adding to an average of an average if (fSplitFirstEdge) { fPositions[fFirstVertexIndex + 2] += insetNormal * 0.5f; } umbraPoint = fPositions[fFirstVertexIndex]; } else { umbraPoint = nextPoint + insetNormal; } SkVector outsetNormal = nextNormal; outsetNormal *= fRadius; SkPoint penumbraPoint = nextPoint + outsetNormal; // make sure we don't end up with a sharp alpha edge along the quad diagonal this->splitEdge(nextPoint, insetNormal, penumbraPoint, umbraPoint, fUmbraColor); // add next quad int prevPenumbraIndex; int currUmbraIndex; if (finalEdge) { prevPenumbraIndex = fPositions.count() - 1; currUmbraIndex = fFirstVertexIndex; } else { prevPenumbraIndex = fPositions.count() - 1; *fPositions.push() = umbraPoint; *fColors.push() = fUmbraColor; currUmbraIndex = fPositions.count() - 1; } *fPositions.push() = penumbraPoint; *fColors.push() = fPenumbraColor; // set triangularization to get best interpolation of color if (fColors[fPrevUmbraIndex] > fUmbraColor) { this->appendQuad(fPrevUmbraIndex, prevPenumbraIndex, currUmbraIndex, fPositions.count() - 1); } else { this->appendQuad(currUmbraIndex, fPositions.count() - 1, fPrevUmbraIndex, prevPenumbraIndex); } // if transparent, add to center fan if (fTransparent) { this->appendTriangle(0, fPrevUmbraIndex, currUmbraIndex); } fPrevUmbraIndex = currUmbraIndex; fPrevPoint = nextPoint; fPrevOutset = outsetNormal; } void SkAmbientShadowTessellator::splitEdge(const SkPoint& nextPoint, const SkVector& insetNormal, const SkPoint& penumbraPoint, const SkPoint& umbraPoint, SkColor umbraColor) { // For split edges, we're adding an average of two averages, so we multiply by another half if (fSplitPreviousEdge) { fPositions[fPrevUmbraIndex - 2] += insetNormal*SK_ScalarHalf; } // Split the edge to make sure we don't end up with a sharp alpha edge along the quad diagonal if (fColors[fPrevUmbraIndex] != umbraColor && SkPointPriv::DistanceToSqd(nextPoint, fPositions[fPrevUmbraIndex]) > kMaxEdgeLenSqr) { // This is lacking 1/4 of the next inset -- we'll add it the next time we call addEdge() SkPoint centerPoint = fPositions[fPrevUmbraIndex] + umbraPoint; centerPoint *= 0.5f; *fPositions.push() = centerPoint; *fColors.push() = SkPMLerp(umbraColor, fColors[fPrevUmbraIndex], 128); centerPoint = fPositions[fPositions.count() - 2] + penumbraPoint; centerPoint *= 0.5f; *fPositions.push() = centerPoint; *fColors.push() = fPenumbraColor; // set triangularization to get best interpolation of color if (fColors[fPrevUmbraIndex] > fColors[fPositions.count() - 2]) { this->appendQuad(fPrevUmbraIndex, fPositions.count() - 3, fPositions.count() - 2, fPositions.count() - 1); } else { this->appendQuad(fPositions.count() - 2, fPositions.count() - 1, fPrevUmbraIndex, fPositions.count() - 3); } // if transparent, add to center fan if (fTransparent) { this->appendTriangle(0, fPrevUmbraIndex, fPositions.count() - 2); } fSplitPreviousEdge = true; if (fPrevUmbraIndex == fFirstVertexIndex) { fSplitFirstEdge = true; } fPrevUmbraIndex = fPositions.count() - 2; } else { fSplitPreviousEdge = false; } } /////////////////////////////////////////////////////////////////////////////////////////////////// class SkSpotShadowTessellator : public SkBaseShadowTessellator { public: SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm, const SkPoint3& zPlaneParams, const SkPoint3& lightPos, SkScalar lightRadius, bool transparent); private: bool computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm, const SkMatrix& shadowTransform); void computeClipVectorsAndTestCentroid(); bool clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint); int getClosestUmbraPoint(const SkPoint& point); bool computeConvexShadow(SkScalar radius); bool computeConcaveShadow(SkScalar radius); bool handlePolyPoint(const SkPoint& p, bool lastPoint); void mapPoints(SkScalar scale, const SkVector& xlate, SkPoint* pts, int count); bool addInnerPoint(const SkPoint& pathPoint, int* currUmbraIndex); void addEdge(const SkVector& nextPoint, const SkVector& nextNormal, bool lastEdge); void addToClip(const SkVector& nextPoint); SkScalar offset(SkScalar z) { float zRatio = SkTPin(z / (fLightZ - z), 0.0f, 0.95f); return fLightRadius*zRatio; } SkScalar fLightZ; SkScalar fLightRadius; SkScalar fOffsetAdjust; SkTDArray fClipPolygon; SkTDArray fClipVectors; SkTDArray fUmbraPolygon; int fCurrClipPoint; int fCurrUmbraPoint; bool fPrevUmbraOutside; bool fFirstUmbraOutside; bool fValidUmbra; typedef SkBaseShadowTessellator INHERITED; }; SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm, const SkPoint3& zPlaneParams, const SkPoint3& lightPos, SkScalar lightRadius, bool transparent) : INHERITED(zPlaneParams, transparent) , fLightZ(lightPos.fZ) , fLightRadius(lightRadius) , fOffsetAdjust(0) , fCurrClipPoint(0) , fPrevUmbraOutside(false) , fFirstUmbraOutside(false) , fValidUmbra(true) { // make sure we're not below the canvas plane if (this->setZOffset(path.getBounds(), ctm.hasPerspective())) { // Adjust light height and radius fLightRadius *= (fLightZ + fZOffset) / fLightZ; fLightZ += fZOffset; } // Set radius and colors SkPoint center = SkPoint::Make(path.getBounds().centerX(), path.getBounds().centerY()); SkScalar occluderHeight = this->heightFunc(center.fX, center.fY) + fZOffset; fUmbraColor = SkColorSetARGB(255, 0, 0, 0); fPenumbraColor = SkColorSetARGB(0, 0, 0, 0); // Compute the blur radius, scale and translation for the spot shadow. SkScalar radius; SkMatrix shadowTransform; if (!ctm.hasPerspective()) { SkScalar scale; SkVector translate; SkDrawShadowMetrics::GetSpotParams(occluderHeight, lightPos.fX, lightPos.fY, fLightZ, lightRadius, &radius, &scale, &translate); shadowTransform.setScaleTranslate(scale, scale, translate.fX, translate.fY); } else { // For perspective, we have a scale, a z-shear, and another projective divide -- // this varies at each point so we can't use an affine transform. // We'll just apply this to each generated point in turn. shadowTransform.reset(); // Also can't cull the center (for now). fTransparent = true; radius = SkDrawShadowMetrics::SpotBlurRadius(occluderHeight, lightPos.fZ, lightRadius); } fRadius = radius; SkMatrix fullTransform = SkMatrix::Concat(shadowTransform, ctm); // Set up our reverse mapping if (!this->setTransformedHeightFunc(fullTransform)) { return; } // compute rough clip bounds for umbra, plus offset polygon, plus centroid if (!this->computeClipAndPathPolygons(path, ctm, shadowTransform)) { return; } if (fClipPolygon.count() < 3 || fPathPolygon.count() < 3 || !SkScalarIsFinite(fArea)) { fSucceeded = true; // We don't want to try to blur these cases, so we will // return an empty SkVertices instead. return; } // compute vectors for clip tests this->computeClipVectorsAndTestCentroid(); // check to see if umbra collapses if (fIsConvex) { SkScalar minDistSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid, fPathPolygon[0], fPathPolygon[1]); SkRect bounds; bounds.setBounds(&fPathPolygon[0], fPathPolygon.count()); for (int i = 1; i < fPathPolygon.count(); ++i) { int j = i + 1; if (i == fPathPolygon.count() - 1) { j = 0; } SkPoint currPoint = fPathPolygon[i]; SkPoint nextPoint = fPathPolygon[j]; SkScalar distSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid, currPoint, nextPoint); if (distSq < minDistSq) { minDistSq = distSq; } } static constexpr auto kTolerance = 1.0e-2f; if (minDistSq < (radius + kTolerance)*(radius + kTolerance)) { // if the umbra would collapse, we back off a bit on inner blur and adjust the alpha SkScalar newRadius = SkScalarSqrt(minDistSq) - kTolerance; fOffsetAdjust = newRadius - radius; SkScalar ratio = 128 * (newRadius + radius) / radius; // they aren't PMColors, but the interpolation algorithm is the same fUmbraColor = SkPMLerp(fUmbraColor, fPenumbraColor, (unsigned)ratio); radius = newRadius; } } // TODO: calculate these reserves better // Penumbra ring: 3*numPts // Umbra ring: numPts // Inner ring: numPts fPositions.setReserve(5 * path.countPoints()); fColors.setReserve(5 * path.countPoints()); // Penumbra ring: 12*numPts // Umbra ring: 3*numPts fIndices.setReserve(15 * path.countPoints()); if (fIsConvex) { fSucceeded = this->computeConvexShadow(radius); } else { fSucceeded = this->computeConcaveShadow(radius); } if (!fSucceeded) { return; } if (ctm.hasPerspective()) { for (int i = 0; i < fPositions.count(); ++i) { SkScalar pathZ = fTransformedHeightFunc(fPositions[i]); SkScalar factor = SkScalarInvert(fLightZ - pathZ); fPositions[i].fX = (fPositions[i].fX*fLightZ - lightPos.fX*pathZ)*factor; fPositions[i].fY = (fPositions[i].fY*fLightZ - lightPos.fY*pathZ)*factor; } #ifdef DRAW_CENTROID SkScalar pathZ = fTransformedHeightFunc(fCentroid); SkScalar factor = SkScalarInvert(fLightZ - pathZ); fCentroid.fX = (fCentroid.fX*fLightZ - lightPos.fX*pathZ)*factor; fCentroid.fY = (fCentroid.fY*fLightZ - lightPos.fY*pathZ)*factor; #endif } #ifdef DRAW_CENTROID *fPositions.push() = fCentroid + SkVector::Make(-2, -2); *fColors.push() = SkColorSetARGB(255, 0, 255, 255); *fPositions.push() = fCentroid + SkVector::Make(2, -2); *fColors.push() = SkColorSetARGB(255, 0, 255, 255); *fPositions.push() = fCentroid + SkVector::Make(-2, 2); *fColors.push() = SkColorSetARGB(255, 0, 255, 255); *fPositions.push() = fCentroid + SkVector::Make(2, 2); *fColors.push() = SkColorSetARGB(255, 0, 255, 255); this->appendQuad(fPositions.count() - 2, fPositions.count() - 1, fPositions.count() - 4, fPositions.count() - 3); #endif fSucceeded = true; } void SkSpotShadowTessellator::addToClip(const SkPoint& point) { if (fClipPolygon.isEmpty() || !duplicate_pt(point, fClipPolygon[fClipPolygon.count()-1])) { *fClipPolygon.push() = point; } } bool SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm, const SkMatrix& shadowTransform) { fPathPolygon.setReserve(path.countPoints()); fClipPolygon.setReserve(path.countPoints()); // Walk around the path and compute clip polygon and path polygon. // Will also accumulate sum of areas for centroid. // For Bezier curves, we compute additional interior points on curve. SkPath::Iter iter(path, true); SkPoint pts[4]; SkPath::Verb verb; // coefficients to compute cubic Bezier at t = 5/16 static constexpr SkScalar kA = 0.32495117187f; static constexpr SkScalar kB = 0.44311523437f; static constexpr SkScalar kC = 0.20141601562f; static constexpr SkScalar kD = 0.03051757812f; SkPoint curvePoint; SkScalar w; bool closeSeen = false; bool verbSeen = false; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { if (closeSeen) { return false; } switch (verb) { case SkPath::kLine_Verb: ctm.mapPoints(&pts[1], 1); this->addToClip(pts[1]); this->handleLine(shadowTransform, &pts[1]); break; case SkPath::kQuad_Verb: ctm.mapPoints(pts, 3); // point at t = 1/2 curvePoint.fX = 0.25f*pts[0].fX + 0.5f*pts[1].fX + 0.25f*pts[2].fX; curvePoint.fY = 0.25f*pts[0].fY + 0.5f*pts[1].fY + 0.25f*pts[2].fY; this->addToClip(curvePoint); this->addToClip(pts[2]); this->handleQuad(shadowTransform, pts); break; case SkPath::kConic_Verb: ctm.mapPoints(pts, 3); w = iter.conicWeight(); // point at t = 1/2 curvePoint.fX = 0.25f*pts[0].fX + w*0.5f*pts[1].fX + 0.25f*pts[2].fX; curvePoint.fY = 0.25f*pts[0].fY + w*0.5f*pts[1].fY + 0.25f*pts[2].fY; curvePoint *= SkScalarInvert(0.5f + 0.5f*w); this->addToClip(curvePoint); this->addToClip(pts[2]); this->handleConic(shadowTransform, pts, w); break; case SkPath::kCubic_Verb: ctm.mapPoints(pts, 4); // point at t = 5/16 curvePoint.fX = kA*pts[0].fX + kB*pts[1].fX + kC*pts[2].fX + kD*pts[3].fX; curvePoint.fY = kA*pts[0].fY + kB*pts[1].fY + kC*pts[2].fY + kD*pts[3].fY; this->addToClip(curvePoint); // point at t = 11/16 curvePoint.fX = kD*pts[0].fX + kC*pts[1].fX + kB*pts[2].fX + kA*pts[3].fX; curvePoint.fY = kD*pts[0].fY + kC*pts[1].fY + kB*pts[2].fY + kA*pts[3].fY; this->addToClip(curvePoint); this->addToClip(pts[3]); this->handleCubic(shadowTransform, pts); break; case SkPath::kMove_Verb: if (verbSeen) { return false; } break; case SkPath::kClose_Verb: case SkPath::kDone_Verb: closeSeen = true; break; default: SkDEBUGFAIL("unknown verb"); } verbSeen = true; } this->finishPathPolygon(); fCurrClipPoint = fClipPolygon.count() - 1; return true; } void SkSpotShadowTessellator::computeClipVectorsAndTestCentroid() { SkASSERT(fClipPolygon.count() >= 3); // init clip vectors SkVector v0 = fClipPolygon[1] - fClipPolygon[0]; SkVector v1 = fClipPolygon[2] - fClipPolygon[0]; *fClipVectors.push() = v0; // init centroid check bool hiddenCentroid = true; v1 = fCentroid - fClipPolygon[0]; SkScalar initCross = v0.cross(v1); for (int p = 1; p < fClipPolygon.count(); ++p) { // add to clip vectors v0 = fClipPolygon[(p + 1) % fClipPolygon.count()] - fClipPolygon[p]; *fClipVectors.push() = v0; // Determine if transformed centroid is inside clipPolygon. v1 = fCentroid - fClipPolygon[p]; if (initCross*v0.cross(v1) <= 0) { hiddenCentroid = false; } } SkASSERT(fClipVectors.count() == fClipPolygon.count()); fTransparent = fTransparent || !hiddenCentroid; } bool SkSpotShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint) { SkVector segmentVector = centroid - umbraPoint; int startClipPoint = fCurrClipPoint; do { SkVector dp = umbraPoint - fClipPolygon[fCurrClipPoint]; SkScalar denom = fClipVectors[fCurrClipPoint].cross(segmentVector); SkScalar t_num = dp.cross(segmentVector); // if line segments are nearly parallel if (SkScalarNearlyZero(denom)) { // and collinear if (SkScalarNearlyZero(t_num)) { return false; } // otherwise are separate, will try the next poly segment // else if crossing lies within poly segment } else if (t_num >= 0 && t_num <= denom) { SkScalar s_num = dp.cross(fClipVectors[fCurrClipPoint]); // if umbra point is inside the clip polygon if (s_num >= 0 && s_num <= denom) { segmentVector *= s_num/denom; *clipPoint = umbraPoint + segmentVector; return true; } } fCurrClipPoint = (fCurrClipPoint + 1) % fClipPolygon.count(); } while (fCurrClipPoint != startClipPoint); return false; } int SkSpotShadowTessellator::getClosestUmbraPoint(const SkPoint& p) { SkScalar minDistance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[fCurrUmbraPoint]); int index = fCurrUmbraPoint; int dir = 1; int next = (index + dir) % fUmbraPolygon.count(); // init travel direction SkScalar distance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[next]); if (distance < minDistance) { index = next; minDistance = distance; } else { dir = fUmbraPolygon.count()-1; } // iterate until we find a point that increases the distance next = (index + dir) % fUmbraPolygon.count(); distance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[next]); while (distance < minDistance) { index = next; minDistance = distance; next = (index + dir) % fUmbraPolygon.count(); distance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[next]); } fCurrUmbraPoint = index; return index; } bool SkSpotShadowTessellator::computeConvexShadow(SkScalar radius) { // generate inner ring if (!SkInsetConvexPolygon(&fPathPolygon[0], fPathPolygon.count(), radius, &fUmbraPolygon)) { // this shouldn't happen, but just in case we'll inset using the centroid fValidUmbra = false; } // walk around the path polygon, generate outer ring and connect to inner ring if (fTransparent) { *fPositions.push() = fCentroid; *fColors.push() = fUmbraColor; } fCurrUmbraPoint = 0; // initial setup // add first quad int polyCount = fPathPolygon.count(); if (!compute_normal(fPathPolygon[polyCount-1], fPathPolygon[0], fDirection, &fFirstOutset)) { // polygon should be sanitized by this point, so this is unrecoverable return false; } fFirstOutset *= fRadius; fFirstPoint = fPathPolygon[polyCount - 1]; fFirstVertexIndex = fPositions.count(); fPrevOutset = fFirstOutset; fPrevPoint = fFirstPoint; fPrevUmbraIndex = -1; this->addInnerPoint(fFirstPoint, &fPrevUmbraIndex); if (!fTransparent) { SkPoint clipPoint; bool isOutside = this->clipUmbraPoint(fPositions[fFirstVertexIndex], fCentroid, &clipPoint); if (isOutside) { *fPositions.push() = clipPoint; *fColors.push() = fUmbraColor; } fPrevUmbraOutside = isOutside; fFirstUmbraOutside = isOutside; } SkPoint newPoint = fFirstPoint + fFirstOutset; *fPositions.push() = newPoint; *fColors.push() = fPenumbraColor; this->addEdge(fPathPolygon[0], fFirstOutset, false); for (int i = 1; i < polyCount; ++i) { if (!this->handlePolyPoint(fPathPolygon[i], i == polyCount-1)) { return false; } } SkASSERT(this->indexCount()); // final fan SkASSERT(fPositions.count() >= 3); if (this->addArc(fFirstOutset, false)) { if (fFirstUmbraOutside) { this->appendTriangle(fFirstVertexIndex, fPositions.count() - 1, fFirstVertexIndex + 2); } else { this->appendTriangle(fFirstVertexIndex, fPositions.count() - 1, fFirstVertexIndex + 1); } } else { // no arc added, fix up by setting first penumbra point position to last one if (fFirstUmbraOutside) { fPositions[fFirstVertexIndex + 2] = fPositions[fPositions.count() - 1]; } else { fPositions[fFirstVertexIndex + 1] = fPositions[fPositions.count() - 1]; } } return true; } bool SkSpotShadowTessellator::computeConcaveShadow(SkScalar radius) { // TODO: remove when we support filling the penumbra if (fTransparent) { return false; } // generate inner ring SkTDArray umbraIndices; umbraIndices.setReserve(fPathPolygon.count()); if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.count(), radius, &fUmbraPolygon, &umbraIndices)) { // TODO: figure out how to handle this case return false; } // generate outer ring SkTDArray penumbraPolygon; SkTDArray penumbraIndices; penumbraPolygon.setReserve(fUmbraPolygon.count()); penumbraIndices.setReserve(fUmbraPolygon.count()); if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.count(), -radius, &penumbraPolygon, &penumbraIndices)) { // TODO: figure out how to handle this case return false; } if (!fUmbraPolygon.count() || !penumbraPolygon.count()) { return false; } // attach the rings together this->stitchConcaveRings(fUmbraPolygon, &umbraIndices, penumbraPolygon, &penumbraIndices); return true; } void SkSpotShadowTessellator::mapPoints(SkScalar scale, const SkVector& xlate, SkPoint* pts, int count) { // TODO: vectorize for (int i = 0; i < count; ++i) { pts[i] *= scale; pts[i] += xlate; } } bool SkSpotShadowTessellator::handlePolyPoint(const SkPoint& p, bool lastPoint) { SkVector normal; if (compute_normal(fPrevPoint, p, fDirection, &normal)) { normal *= fRadius; this->addArc(normal, true); this->addEdge(p, normal, lastPoint); } return true; } bool SkSpotShadowTessellator::addInnerPoint(const SkPoint& pathPoint, int* currUmbraIndex) { SkPoint umbraPoint; if (!fValidUmbra) { SkVector v = fCentroid - pathPoint; v *= 0.95f; umbraPoint = pathPoint + v; } else { umbraPoint = fUmbraPolygon[this->getClosestUmbraPoint(pathPoint)]; } fPrevPoint = pathPoint; // merge "close" points if (fPrevUmbraIndex == -1 || !duplicate_pt(umbraPoint, fPositions[fPrevUmbraIndex])) { // if we've wrapped around, don't add a new point if (fPrevUmbraIndex >= 0 && duplicate_pt(umbraPoint, fPositions[fFirstVertexIndex])) { *currUmbraIndex = fFirstVertexIndex; } else { *currUmbraIndex = fPositions.count(); *fPositions.push() = umbraPoint; *fColors.push() = fUmbraColor; } return false; } else { *currUmbraIndex = fPrevUmbraIndex; return true; } } void SkSpotShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal, bool lastEdge) { // add next umbra point int currUmbraIndex; bool duplicate; if (lastEdge) { duplicate = false; currUmbraIndex = fFirstVertexIndex; fPrevPoint = nextPoint; } else { duplicate = this->addInnerPoint(nextPoint, &currUmbraIndex); } int prevPenumbraIndex = duplicate || (currUmbraIndex == fFirstVertexIndex) ? fPositions.count()-1 : fPositions.count()-2; if (!duplicate) { // add to center fan if transparent or centroid showing if (fTransparent) { this->appendTriangle(0, fPrevUmbraIndex, currUmbraIndex); // otherwise add to clip ring } else { SkPoint clipPoint; bool isOutside = lastEdge ? fFirstUmbraOutside : this->clipUmbraPoint(fPositions[currUmbraIndex], fCentroid, &clipPoint); if (isOutside) { if (!lastEdge) { *fPositions.push() = clipPoint; *fColors.push() = fUmbraColor; } this->appendTriangle(fPrevUmbraIndex, currUmbraIndex, currUmbraIndex + 1); if (fPrevUmbraOutside) { // fill out quad this->appendTriangle(fPrevUmbraIndex, currUmbraIndex + 1, fPrevUmbraIndex + 1); } } else if (fPrevUmbraOutside) { // add tri this->appendTriangle(fPrevUmbraIndex, currUmbraIndex, fPrevUmbraIndex + 1); } fPrevUmbraOutside = isOutside; } } // add next penumbra point and quad SkPoint newPoint = nextPoint + nextNormal; *fPositions.push() = newPoint; *fColors.push() = fPenumbraColor; if (!duplicate) { this->appendTriangle(fPrevUmbraIndex, prevPenumbraIndex, currUmbraIndex); } this->appendTriangle(prevPenumbraIndex, fPositions.count() - 1, currUmbraIndex); fPrevUmbraIndex = currUmbraIndex; fPrevOutset = nextNormal; } /////////////////////////////////////////////////////////////////////////////////////////////////// sk_sp SkShadowTessellator::MakeAmbient(const SkPath& path, const SkMatrix& ctm, const SkPoint3& zPlane, bool transparent) { if (!ctm.mapRect(path.getBounds()).isFinite() || !zPlane.isFinite()) { return nullptr; } SkAmbientShadowTessellator ambientTess(path, ctm, zPlane, transparent); return ambientTess.releaseVertices(); } sk_sp SkShadowTessellator::MakeSpot(const SkPath& path, const SkMatrix& ctm, const SkPoint3& zPlane, const SkPoint3& lightPos, SkScalar lightRadius, bool transparent) { if (!ctm.mapRect(path.getBounds()).isFinite() || !zPlane.isFinite() || !lightPos.isFinite() || !(lightPos.fZ >= SK_ScalarNearlyZero) || !SkScalarIsFinite(lightRadius) || !(lightRadius >= SK_ScalarNearlyZero)) { return nullptr; } SkSpotShadowTessellator spotTess(path, ctm, zPlane, lightPos, lightRadius, transparent); return spotTess.releaseVertices(); }