From 8760e2f42857b3a59c203212ffdc2b5a6cdcb72c Mon Sep 17 00:00:00 2001 From: Jim Van Verth Date: Tue, 12 Jun 2018 14:21:38 -0400 Subject: Add outline concave shadow support Bug: skia:7971 Change-Id: I97370b9c942c5e5f1e53ec15524bd2d20794d68c Reviewed-on: https://skia-review.googlesource.com/134328 Reviewed-by: Brian Salomon Commit-Queue: Jim Van Verth --- src/utils/SkShadowTessellator.cpp | 377 ++++++++++++++++++++++---------------- src/utils/SkShadowUtils.cpp | 4 +- 2 files changed, 219 insertions(+), 162 deletions(-) (limited to 'src/utils') diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp index 08af4b78bb..c50265fd42 100755 --- a/src/utils/SkShadowTessellator.cpp +++ b/src/utils/SkShadowTessellator.cpp @@ -48,6 +48,10 @@ protected: 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); @@ -263,6 +267,132 @@ void SkBaseShadowTessellator::finishPathPolygon() { 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; @@ -489,6 +619,9 @@ public: private: void 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, @@ -543,13 +676,49 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path, fIndices.setReserve(12 * path.countPoints()); this->computePathPolygon(path, ctm); + if (fIsConvex) { + fSucceeded = this->computeConvexShadow(); + } else { + fSucceeded = this->computeConcaveShadow(); + } +} + +void 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; + while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { + 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: + case SkPath::kClose_Verb: + case SkPath::kDone_Verb: + break; + } + } + + this->finishPathPolygon(); +} + +bool SkAmbientShadowTessellator::computeConvexShadow() { int polyCount = fPathPolygon.count(); if (polyCount < 3) { - return; - } - // TODO: add support for concave paths - if (!fIsConvex) { - return; + return false; } // Add center point for fan if needed @@ -562,7 +731,7 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path, 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; + return false; } fFirstPoint = fPathPolygon[polyCount - 1]; fFirstVertexIndex = fPositions.count(); @@ -601,39 +770,46 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path, fPositions[fFirstVertexIndex + 1] = fPositions[fPositions.count() - 1]; } - fSucceeded = true; + return true; } -void SkAmbientShadowTessellator::computePathPolygon(const SkPath& path, const SkMatrix& ctm) { - fPathPolygon.setReserve(path.countPoints()); +bool SkAmbientShadowTessellator::computeConcaveShadow() { + // TODO: remove when we support filling the penumbra + if (fTransparent) { + return false; + } - // 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; - while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { - 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: - case SkPath::kClose_Verb: - case SkPath::kDone_Verb: - break; - } + // 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; } - this->finishPathPolygon(); + // generate outer ring + SkTDArray penumbraPolygon; + SkTDArray penumbraIndices; + penumbraPolygon.setReserve(umbraPolygon.count()); + penumbraIndices.setReserve(umbraPolygon.count()); + // TODO: handle tilt + SkScalar radius = this->offset(fTransformedHeightFunc(fPathPolygon[0])); + if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.count(), -radius, + &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) { @@ -912,15 +1088,13 @@ SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMat } if (fIsConvex) { - if (!this->computeConvexShadow(radius)) { - return; - } + fSucceeded = this->computeConvexShadow(radius); } else { - // For now + fSucceeded = this->computeConcaveShadow(radius); + } + + if (!fSucceeded) { return; - //if (!this->computeConcaveShadow(radius)) { - // return; - //} } if (ctm.hasPerspective()) { @@ -1233,126 +1407,7 @@ bool SkSpotShadowTessellator::computeConcaveShadow(SkScalar radius) { } // attach the rings together - - // 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) % fUmbraPolygon.count(); - } - } - - *fPositions.push() = penumbraPolygon[currPenumbra]; - *fColors.push() = fPenumbraColor; - int prevPenumbraIndex = 0; - *fPositions.push() = fUmbraPolygon[currUmbra]; - *fColors.push() = fUmbraColor; - fPrevUmbraIndex = 1; - - int nextPenumbra = (currPenumbra + 1) % penumbraPolygon.count(); - int nextUmbra = (currUmbra + 1) % fUmbraPolygon.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() = fUmbraPolygon[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) % fUmbraPolygon.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() = fUmbraPolygon[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) % fUmbraPolygon.count(); - } - } - // finish up by advancing both one step - *fPositions.push() = penumbraPolygon[nextPenumbra]; - *fColors.push() = fPenumbraColor; - int currPenumbraIndex = fPositions.count() - 1; - - *fPositions.push() = fUmbraPolygon[nextUmbra]; - *fColors.push() = fUmbraColor; - int currUmbraIndex = fPositions.count() - 1; - - this->appendQuad(prevPenumbraIndex, currPenumbraIndex, - fPrevUmbraIndex, currUmbraIndex); - - if (fTransparent) { - // TODO: fill penumbra - } + this->stitchConcaveRings(fUmbraPolygon, &umbraIndices, penumbraPolygon, &penumbraIndices); return true; } diff --git a/src/utils/SkShadowUtils.cpp b/src/utils/SkShadowUtils.cpp index 2578a686d1..b4fba5fcc1 100644 --- a/src/utils/SkShadowUtils.cpp +++ b/src/utils/SkShadowUtils.cpp @@ -688,8 +688,10 @@ void SkBaseDevice::drawShadow(const SkPath& path, const SkDrawShadowRec& rec) { } else if (factory.fOffset.length()*scale + scale < radius) { // if we don't translate more than the blur distance, can assume umbra is covered factory.fOccluderType = SpotVerticesFactory::OccluderType::kOpaqueNoUmbra; - } else { + } else if (path.isConvex()) { factory.fOccluderType = SpotVerticesFactory::OccluderType::kOpaquePartialUmbra; + } else { + factory.fOccluderType = SpotVerticesFactory::OccluderType::kTransparent; } // need to add this after we classify the shadow factory.fOffset.fX += viewMatrix.getTranslateX(); -- cgit v1.2.3