12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169 |
- /*
- * 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 "include/core/SkPath.h"
- #include "include/core/SkPoint3.h"
- #include "include/core/SkVertices.h"
- #include "include/private/SkColorData.h"
- #include "src/core/SkDrawShadowInfo.h"
- #include "src/core/SkGeometry.h"
- #include "src/core/SkPointPriv.h"
- #include "src/utils/SkPolyUtils.h"
- #include "src/utils/SkShadowTessellator.h"
- #if SK_SUPPORT_GPU
- #include "src/gpu/geometry/GrPathUtils.h"
- #endif
- /**
- * Base class
- */
- class SkBaseShadowTessellator {
- public:
- SkBaseShadowTessellator(const SkPoint3& zPlaneParams, const SkRect& bounds, 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;
- static constexpr auto kPenumbraColor = SK_ColorTRANSPARENT;
- static constexpr auto kUmbraColor = SK_ColorBLACK;
- int vertexCount() const { return fPositions.count(); }
- int indexCount() const { return fIndices.count(); }
- // initialization methods
- bool accumulateCentroid(const SkPoint& c, const SkPoint& n);
- bool checkConvexity(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2);
- void finishPathPolygon();
- // convex shadow methods
- bool computeConvexShadow(SkScalar inset, SkScalar outset, bool doClip);
- void computeClipVectorsAndTestCentroid();
- bool clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint);
- void addEdge(const SkVector& nextPoint, const SkVector& nextNormal, SkColor umbraColor,
- const SkTDArray<SkPoint>& umbraPolygon, bool lastEdge, bool doClip);
- bool addInnerPoint(const SkPoint& pathPoint, SkColor umbraColor,
- const SkTDArray<SkPoint>& umbraPolygon, int* currUmbraIndex);
- int getClosestUmbraIndex(const SkPoint& point, const SkTDArray<SkPoint>& umbraPolygon);
- // concave shadow methods
- bool computeConcaveShadow(SkScalar inset, SkScalar outset);
- 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 addArc(const SkVector& nextNormal, SkScalar offset, 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;
- // temporary buffer
- SkTDArray<SkPoint> fPointBuffer;
- SkTDArray<SkPoint> fPositions;
- SkTDArray<SkColor> fColors;
- SkTDArray<uint16_t> fIndices;
- SkTDArray<SkPoint> fPathPolygon;
- SkTDArray<SkPoint> fClipPolygon;
- SkTDArray<SkVector> fClipVectors;
- SkRect fPathBounds;
- SkPoint fCentroid;
- SkScalar fArea;
- SkScalar fLastArea;
- SkScalar fLastCross;
- int fFirstVertexIndex;
- SkVector fFirstOutset;
- SkPoint fFirstPoint;
- bool fSucceeded;
- bool fTransparent;
- bool fIsConvex;
- bool fValidUmbra;
- SkScalar fDirection;
- int fPrevUmbraIndex;
- int fCurrUmbraIndex;
- int fCurrClipIndex;
- bool fPrevUmbraOutside;
- bool fFirstUmbraOutside;
- SkVector fPrevOutset;
- SkPoint fPrevPoint;
- };
- // make external linkage happy
- constexpr SkColor SkBaseShadowTessellator::kUmbraColor;
- constexpr SkColor SkBaseShadowTessellator::kPenumbraColor;
- 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, const SkRect& bounds,
- bool transparent)
- : fZPlaneParams(zPlaneParams)
- , fPathBounds(bounds)
- , fCentroid({0, 0})
- , fArea(0)
- , fLastArea(0)
- , fLastCross(0)
- , fFirstVertexIndex(-1)
- , fSucceeded(false)
- , fTransparent(transparent)
- , fIsConvex(true)
- , fValidUmbra(true)
- , fDirection(1)
- , fPrevUmbraIndex(-1)
- , fCurrUmbraIndex(0)
- , fCurrClipIndex(0)
- , fPrevUmbraOutside(false)
- , fFirstUmbraOutside(false) {
- // child classes will set reserve for positions, colors and indices
- }
- 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;
- }
- bool SkBaseShadowTessellator::computeConvexShadow(SkScalar inset, SkScalar outset, bool doClip) {
- if (doClip) {
- this->computeClipVectorsAndTestCentroid();
- }
- // adjust inset distance and umbra color if necessary
- auto umbraColor = kUmbraColor;
- 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;
- }
- }
- SkTDArray<SkPoint> insetPolygon;
- if (inset > SK_ScalarNearlyZero) {
- static constexpr auto kTolerance = 1.0e-2f;
- if (minDistSq < (inset + kTolerance)*(inset + kTolerance)) {
- // if the umbra would collapse, we back off a bit on inner blur and adjust the alpha
- auto newInset = SkScalarSqrt(minDistSq) - kTolerance;
- auto ratio = 128 * (newInset / inset + 1);
- SkASSERT(SkScalarIsFinite(ratio));
- // they aren't PMColors, but the interpolation algorithm is the same
- umbraColor = SkPMLerp(kUmbraColor, kPenumbraColor, (unsigned)ratio);
- inset = newInset;
- }
- // generate inner ring
- if (!SkInsetConvexPolygon(&fPathPolygon[0], fPathPolygon.count(), inset,
- &insetPolygon)) {
- // not ideal, but in this case we'll inset using the centroid
- fValidUmbra = false;
- }
- }
- const SkTDArray<SkPoint>& umbraPolygon = (inset > SK_ScalarNearlyZero) ? insetPolygon
- : fPathPolygon;
- // walk around the path polygon, generate outer ring and connect to inner ring
- if (fTransparent) {
- fPositions.push_back(fCentroid);
- fColors.push_back(umbraColor);
- }
- fCurrUmbraIndex = 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 *= outset;
- fFirstPoint = fPathPolygon[polyCount - 1];
- fFirstVertexIndex = fPositions.count();
- fPrevOutset = fFirstOutset;
- fPrevPoint = fFirstPoint;
- fPrevUmbraIndex = -1;
- this->addInnerPoint(fFirstPoint, umbraColor, umbraPolygon, &fPrevUmbraIndex);
- if (!fTransparent && doClip) {
- SkPoint clipPoint;
- bool isOutside = this->clipUmbraPoint(fPositions[fFirstVertexIndex],
- fCentroid, &clipPoint);
- if (isOutside) {
- fPositions.push_back(clipPoint);
- fColors.push_back(umbraColor);
- }
- fPrevUmbraOutside = isOutside;
- fFirstUmbraOutside = isOutside;
- }
- SkPoint newPoint = fFirstPoint + fFirstOutset;
- fPositions.push_back(newPoint);
- fColors.push_back(kPenumbraColor);
- this->addEdge(fPathPolygon[0], fFirstOutset, umbraColor, umbraPolygon, false, doClip);
- for (int i = 1; i < polyCount; ++i) {
- SkVector normal;
- if (!compute_normal(fPrevPoint, fPathPolygon[i], fDirection, &normal)) {
- return false;
- }
- normal *= outset;
- this->addArc(normal, outset, true);
- this->addEdge(fPathPolygon[i], normal, umbraColor, umbraPolygon,
- i == polyCount - 1, doClip);
- }
- SkASSERT(this->indexCount());
- // final fan
- SkASSERT(fPositions.count() >= 3);
- if (this->addArc(fFirstOutset, outset, 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;
- }
- void SkBaseShadowTessellator::computeClipVectorsAndTestCentroid() {
- SkASSERT(fClipPolygon.count() >= 3);
- fCurrClipIndex = fClipPolygon.count() - 1;
- // init clip vectors
- SkVector v0 = fClipPolygon[1] - fClipPolygon[0];
- SkVector v1 = fClipPolygon[2] - fClipPolygon[0];
- fClipVectors.push_back(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_back(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;
- }
- void SkBaseShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal,
- SkColor umbraColor, const SkTDArray<SkPoint>& umbraPolygon,
- bool lastEdge, bool doClip) {
- // add next umbra point
- int currUmbraIndex;
- bool duplicate;
- if (lastEdge) {
- duplicate = false;
- currUmbraIndex = fFirstVertexIndex;
- fPrevPoint = nextPoint;
- } else {
- duplicate = this->addInnerPoint(nextPoint, umbraColor, umbraPolygon, &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 if (doClip) {
- SkPoint clipPoint;
- bool isOutside = lastEdge ? fFirstUmbraOutside
- : this->clipUmbraPoint(fPositions[currUmbraIndex], fCentroid,
- &clipPoint);
- if (isOutside) {
- if (!lastEdge) {
- fPositions.push_back(clipPoint);
- fColors.push_back(umbraColor);
- }
- 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_back(newPoint);
- fColors.push_back(kPenumbraColor);
- if (!duplicate) {
- this->appendTriangle(fPrevUmbraIndex, prevPenumbraIndex, currUmbraIndex);
- }
- this->appendTriangle(prevPenumbraIndex, fPositions.count() - 1, currUmbraIndex);
- fPrevUmbraIndex = currUmbraIndex;
- fPrevOutset = nextNormal;
- }
- bool SkBaseShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid,
- SkPoint* clipPoint) {
- SkVector segmentVector = centroid - umbraPoint;
- int startClipPoint = fCurrClipIndex;
- do {
- SkVector dp = umbraPoint - fClipPolygon[fCurrClipIndex];
- SkScalar denom = fClipVectors[fCurrClipIndex].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[fCurrClipIndex]);
- // if umbra point is inside the clip polygon
- if (s_num >= 0 && s_num <= denom) {
- segmentVector *= s_num / denom;
- *clipPoint = umbraPoint + segmentVector;
- return true;
- }
- }
- fCurrClipIndex = (fCurrClipIndex + 1) % fClipPolygon.count();
- } while (fCurrClipIndex != startClipPoint);
- return false;
- }
- bool SkBaseShadowTessellator::addInnerPoint(const SkPoint& pathPoint, SkColor umbraColor,
- const SkTDArray<SkPoint>& umbraPolygon,
- int* currUmbraIndex) {
- SkPoint umbraPoint;
- if (!fValidUmbra) {
- SkVector v = fCentroid - pathPoint;
- v *= 0.95f;
- umbraPoint = pathPoint + v;
- } else {
- umbraPoint = umbraPolygon[this->getClosestUmbraIndex(pathPoint, umbraPolygon)];
- }
- 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_back(umbraPoint);
- fColors.push_back(umbraColor);
- }
- return false;
- } else {
- *currUmbraIndex = fPrevUmbraIndex;
- return true;
- }
- }
- int SkBaseShadowTessellator::getClosestUmbraIndex(const SkPoint& p,
- const SkTDArray<SkPoint>& umbraPolygon) {
- SkScalar minDistance = SkPointPriv::DistanceToSqd(p, umbraPolygon[fCurrUmbraIndex]);
- int index = fCurrUmbraIndex;
- int dir = 1;
- int next = (index + dir) % umbraPolygon.count();
- // init travel direction
- SkScalar distance = SkPointPriv::DistanceToSqd(p, umbraPolygon[next]);
- if (distance < minDistance) {
- index = next;
- minDistance = distance;
- } else {
- dir = umbraPolygon.count() - 1;
- }
- // iterate until we find a point that increases the distance
- next = (index + dir) % umbraPolygon.count();
- distance = SkPointPriv::DistanceToSqd(p, umbraPolygon[next]);
- while (distance < minDistance) {
- index = next;
- minDistance = distance;
- next = (index + dir) % umbraPolygon.count();
- distance = SkPointPriv::DistanceToSqd(p, umbraPolygon[next]);
- }
- fCurrUmbraIndex = index;
- return index;
- }
- bool SkBaseShadowTessellator::computeConcaveShadow(SkScalar inset, SkScalar outset) {
- 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(), fPathBounds, inset,
- &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());
- if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.count(), fPathBounds, -outset,
- &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 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_back(penumbraPolygon[currPenumbra]);
- fColors.push_back(kPenumbraColor);
- int prevPenumbraIndex = 0;
- fPositions.push_back(umbraPolygon[currUmbra]);
- fColors.push_back(kUmbraColor);
- 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_back(penumbraPolygon[nextPenumbra]);
- fColors.push_back(kPenumbraColor);
- int currPenumbraIndex = fPositions.count() - 1;
- fPositions.push_back(umbraPolygon[nextUmbra]);
- fColors.push_back(kUmbraColor);
- 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_back(penumbraPolygon[nextPenumbra]);
- fColors.push_back(kPenumbraColor);
- 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_back(umbraPolygon[nextUmbra]);
- fColors.push_back(kUmbraColor);
- 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_back(penumbraPolygon[nextPenumbra]);
- fColors.push_back(kPenumbraColor);
- int currPenumbraIndex = fPositions.count() - 1;
- fPositions.push_back(umbraPolygon[nextUmbra]);
- fColors.push_back(kUmbraColor);
- 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.25f;
- // 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();
- // it's possible that the previous point is coincident with the new one now
- if (duplicate_pt(fPathPolygon[fPathPolygon.count() - 1], pSanitized)) {
- fPathPolygon.pop();
- }
- }
- }
- fPathPolygon.push_back(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, SkScalar offset, bool finishArc) {
- // fill in fan from previous quad
- SkScalar rotSin, rotCos;
- int numSteps;
- if (!SkComputeRadialSteps(fPrevOutset, nextNormal, offset, &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_back(fPrevPoint + currNormal);
- fColors.push_back(kPenumbraColor);
- this->appendTriangle(fPrevUmbraIndex, fPositions.count() - 1, fPositions.count() - 2);
- prevNormal = currNormal;
- }
- if (finishArc && numSteps) {
- fPositions.push_back(fPrevPoint + nextNormal);
- fColors.push_back(kPenumbraColor);
- 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;
- }
- //////////////////////////////////////////////////////////////////////////////////////////////////
- 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);
- typedef SkBaseShadowTessellator INHERITED;
- };
- SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
- const SkMatrix& ctm,
- const SkPoint3& zPlaneParams,
- bool transparent)
- : INHERITED(zPlaneParams, path.getBounds(), transparent) {
- // Set base colors
- auto baseZ = heightFunc(fPathBounds.centerX(), fPathBounds.centerY());
- // umbraColor is the interior value, penumbraColor the exterior value.
- auto outset = SkDrawShadowMetrics::AmbientBlurRadius(baseZ);
- auto inset = outset * SkDrawShadowMetrics::AmbientRecipAlpha(baseZ) - outset;
- inset = SkScalarPin(inset, 0, SkTMin(path.getBounds().width(),
- path.getBounds().height()));
- 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(inset, outset, false);
- } else {
- fSucceeded = this->computeConcaveShadow(inset, outset);
- }
- }
- 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;
- }
- ///////////////////////////////////////////////////////////////////////////////////////////////////
- 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 addToClip(const SkVector& nextPoint);
- typedef SkBaseShadowTessellator INHERITED;
- };
- SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm,
- const SkPoint3& zPlaneParams,
- const SkPoint3& lightPos, SkScalar lightRadius,
- bool transparent)
- : INHERITED(zPlaneParams, path.getBounds(), transparent) {
- // Compute the blur radius, scale and translation for the spot shadow.
- SkMatrix shadowTransform;
- SkScalar outset;
- if (!SkDrawShadowMetrics::GetSpotShadowTransform(lightPos, lightRadius,
- ctm, zPlaneParams, path.getBounds(),
- &shadowTransform, &outset)) {
- return;
- }
- SkScalar inset = outset;
- // 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;
- }
- // 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(inset, outset, true);
- } else {
- fSucceeded = this->computeConcaveShadow(inset, outset);
- }
- if (!fSucceeded) {
- return;
- }
- fSucceeded = true;
- }
- 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];
- SkPoint clipPts[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(clipPts, &pts[1], 1);
- this->addToClip(clipPts[0]);
- this->handleLine(shadowTransform, &pts[1]);
- break;
- case SkPath::kQuad_Verb:
- ctm.mapPoints(clipPts, pts, 3);
- // point at t = 1/2
- curvePoint.fX = 0.25f*clipPts[0].fX + 0.5f*clipPts[1].fX + 0.25f*clipPts[2].fX;
- curvePoint.fY = 0.25f*clipPts[0].fY + 0.5f*clipPts[1].fY + 0.25f*clipPts[2].fY;
- this->addToClip(curvePoint);
- this->addToClip(clipPts[2]);
- this->handleQuad(shadowTransform, pts);
- break;
- case SkPath::kConic_Verb:
- ctm.mapPoints(clipPts, pts, 3);
- w = iter.conicWeight();
- // point at t = 1/2
- curvePoint.fX = 0.25f*clipPts[0].fX + w*0.5f*clipPts[1].fX + 0.25f*clipPts[2].fX;
- curvePoint.fY = 0.25f*clipPts[0].fY + w*0.5f*clipPts[1].fY + 0.25f*clipPts[2].fY;
- curvePoint *= SkScalarInvert(0.5f + 0.5f*w);
- this->addToClip(curvePoint);
- this->addToClip(clipPts[2]);
- this->handleConic(shadowTransform, pts, w);
- break;
- case SkPath::kCubic_Verb:
- ctm.mapPoints(clipPts, pts, 4);
- // point at t = 5/16
- curvePoint.fX = kA*clipPts[0].fX + kB*clipPts[1].fX
- + kC*clipPts[2].fX + kD*clipPts[3].fX;
- curvePoint.fY = kA*clipPts[0].fY + kB*clipPts[1].fY
- + kC*clipPts[2].fY + kD*clipPts[3].fY;
- this->addToClip(curvePoint);
- // point at t = 11/16
- curvePoint.fX = kD*clipPts[0].fX + kC*clipPts[1].fX
- + kB*clipPts[2].fX + kA*clipPts[3].fX;
- curvePoint.fY = kD*clipPts[0].fY + kC*clipPts[1].fY
- + kB*clipPts[2].fY + kA*clipPts[3].fY;
- this->addToClip(curvePoint);
- this->addToClip(clipPts[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();
- return true;
- }
- void SkSpotShadowTessellator::addToClip(const SkPoint& point) {
- if (fClipPolygon.isEmpty() || !duplicate_pt(point, fClipPolygon[fClipPolygon.count() - 1])) {
- fClipPolygon.push_back(point);
- }
- }
- ///////////////////////////////////////////////////////////////////////////////////////////////////
- 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();
- }
|