blob: b485f3f68cf76d7a3d70ab26f702511fed191b26 [file] [log] [blame]
/*
* 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 "SkPolyUtils.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<SkVertices> 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<SkPoint>& umbraPolygon,
SkTDArray<int>* umbraIndices,
const SkTDArray<SkPoint>& penumbraPolygon,
SkTDArray<int>* 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<SkScalar(const SkPoint&)> fTransformedHeightFunc;
SkScalar fZOffset;
// members for perspective height function
SkPoint3 fTransformedZParams;
SkScalar fPartialDeterminants[3];
// temporary buffer
SkTDArray<SkPoint> fPointBuffer;
SkTDArray<SkPoint> fPositions;
SkTDArray<SkColor> fColors;
SkTDArray<uint16_t> fIndices;
SkTDArray<SkPoint> fPathPolygon;
SkPoint fCentroid;
SkScalar fArea;
SkScalar fLastArea;
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 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 - p1;
return v0.cross(v1);
}
SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent)
: fZPlaneParams(zPlaneParams)
, fZOffset(0)
, fCentroid({0, 0})
, fArea(0)
, fLastArea(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;
}
SkASSERT(fPathPolygon.count() > 0);
SkVector v0 = curr - fPathPolygon[0];
SkVector v1 = next - fPathPolygon[0];
SkScalar quadArea = v0.cross(v1);
fCentroid.fX += (v0.fX + v1.fX) * quadArea;
fCentroid.fY += (v0.fY + v1.fY) * quadArea;
fArea += quadArea;
// convexity check
if (quadArea*fLastArea < 0) {
fIsConvex = false;
}
if (0 != quadArea) {
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;
}
if (0 != cross) {
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) {
// do this before the final convexity check, so we use the correct fPathPolygon[0]
fCentroid *= sk_ieee_float_divide(1, 3 * fArea);
fCentroid += fPathPolygon[0];
if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2],
fPathPolygon[fPathPolygon.count() - 1],
fPathPolygon[0])) {
// remove collinear point
fPathPolygon[0] = fPathPolygon[fPathPolygon.count() - 1];
fPathPolygon.pop();
}
}
// if area is positive, winding is ccw
fDirection = fArea > 0 ? -1 : 1;
}
void SkBaseShadowTessellator::stitchConcaveRings(const SkTDArray<SkPoint>& umbraPolygon,
SkTDArray<int>* umbraIndices,
const SkTDArray<SkPoint>& penumbraPolygon,
SkTDArray<int>* penumbraIndices) {
// TODO: only create and fill indexMap when fTransparent is true?
SkAutoSTMalloc<64, uint16_t> indexMap(umbraPolygon.count());
// 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;
indexMap[currUmbra] = 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;
indexMap[nextUmbra] = currUmbraIndex;
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;
indexMap[nextUmbra] = currUmbraIndex;
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;
indexMap[nextUmbra] = currUmbraIndex;
this->appendQuad(prevPenumbraIndex, currPenumbraIndex,
fPrevUmbraIndex, currUmbraIndex);
if (fTransparent) {
SkTriangulateSimplePolygon(umbraPolygon.begin(), indexMap, umbraPolygon.count(),
&fIndices);
}
}
// 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;
if (!SkComputeRadialSteps(fPrevOutset, nextNormal, fRadius, &rotSin, &rotCos, &numSteps)) {
// recover as best we can
numSteps = 0;
}
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() {
if (!SkIsSimplePolygon(&fPathPolygon[0], fPathPolygon.count())) {
return false;
}
// generate inner ring
SkTDArray<SkPoint> umbraPolygon;
SkTDArray<int> 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<SkPoint> penumbraPolygon;
SkTDArray<int> 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<SkPoint> fClipPolygon;
SkTDArray<SkVector> fClipVectors;
SkTDArray<SkPoint> 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) {
if (!SkIsSimplePolygon(&fPathPolygon[0], fPathPolygon.count())) {
return false;
}
// generate inner ring
SkTDArray<int> 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<SkPoint> penumbraPolygon;
SkTDArray<int> 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<SkVertices> 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<SkVertices> 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();
}