Consolidate ambient and spot code setup.
Uses shared code to create a polygon version of the path, as well as
computing the centroid and determining convexity. This makes things
more consistent and sets up for creating concave ambient shadows.
Bug: skia:7971
Change-Id: I3f36a423431361177ad9f53218b3ff0fdaa179e1
Reviewed-on: https://skia-review.googlesource.com/131585
Commit-Queue: Jim Van Verth <jvanverth@google.com>
Reviewed-by: Brian Salomon <bsalomon@google.com>
diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp
index c07311c..61b1e97 100755
--- a/src/utils/SkShadowTessellator.cpp
+++ b/src/utils/SkShadowTessellator.cpp
@@ -45,7 +45,11 @@
bool setZOffset(const SkRect& bounds, bool perspective);
- virtual void handleLine(const SkPoint& p) = 0;
+ bool accumulateCentroid(const SkPoint& c, const SkPoint& n);
+ bool checkConvexity(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2);
+ void finishPathPolygon();
+
+ void handleLine(const SkPoint& p);
void handleLine(const SkMatrix& m, SkPoint* p);
void handleQuad(const SkPoint pts[3]);
@@ -82,6 +86,13 @@
SkTDArray<SkColor> fColors;
SkTDArray<uint16_t> fIndices;
+ SkTDArray<SkPoint> fPathPolygon;
+ SkPoint fCentroid;
+ SkScalar fArea;
+ SkScalar fLastArea;
+ int fAreaSignFlips;
+ SkScalar fLastCross;
+
int fFirstVertexIndex;
SkVector fFirstOutset;
SkPoint fFirstPoint;
@@ -143,9 +154,15 @@
return v0.cross(v1);
}
+
SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent)
: fZPlaneParams(zPlaneParams)
, fZOffset(0)
+ , fCentroid({0, 0})
+ , fArea(0)
+ , fLastArea(0)
+ , fAreaSignFlips(0)
+ , fLastCross(0)
, fFirstVertexIndex(-1)
, fSucceeded(false)
, fTransparent(transparent)
@@ -182,6 +199,71 @@
return false;
}
+bool SkBaseShadowTessellator::accumulateCentroid(const SkPoint& curr, const SkPoint& next) {
+ if (duplicate_pt(curr, next)) {
+ return false;
+ }
+
+ SkScalar quadArea = curr.cross(next);
+ fCentroid.fX += (curr.fX + next.fX) * quadArea;
+ fCentroid.fY += (curr.fY + next.fY) * quadArea;
+ fArea += quadArea;
+ // convexity check
+ if (!SkScalarNearlyZero(quadArea)) {
+ if (quadArea*fLastArea < 0) {
+ ++fAreaSignFlips;
+ }
+ fLastArea = quadArea;
+ }
+
+ return true;
+}
+
+bool SkBaseShadowTessellator::checkConvexity(const SkPoint& p0,
+ const SkPoint& p1,
+ const SkPoint& p2) {
+ SkScalar cross = perp_dot(p0, p1, p2);
+ // skip collinear point
+ if (SkScalarNearlyZero(cross)) {
+ return false;
+ }
+
+ // check for convexity
+ if (fLastCross*cross < 0) {
+ fIsConvex = false;
+ }
+ fLastCross = cross;
+
+ return true;
+}
+
+void SkBaseShadowTessellator::finishPathPolygon() {
+ if (fPathPolygon.count() > 1) {
+ if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], fPathPolygon[0])) {
+ // remove coincident point
+ fPathPolygon.pop();
+ }
+ }
+
+ if (fPathPolygon.count() > 2) {
+ if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2],
+ fPathPolygon[fPathPolygon.count() - 1],
+ fPathPolygon[0])) {
+ // remove collinear point
+ fPathPolygon[0] = fPathPolygon[fPathPolygon.count() - 1];
+ fPathPolygon.pop();
+ }
+ }
+
+ fCentroid *= sk_ieee_float_divide(1, 3 * fArea);
+ // It's possible to have a concave path that self-intersects but also passes the
+ // cross-product check (e.g., a star). In that case, the signed area will change signs more
+ // than twice, so we check for that here.
+ if (fAreaSignFlips > 2) {
+ fIsConvex = false;
+ }
+}
+
// tesselation tolerance values, in device space pixels
#if SK_SUPPORT_GPU
static const SkScalar kQuadTolerance = 0.2f;
@@ -189,8 +271,29 @@
#endif
static const SkScalar kConicTolerance = 0.5f;
+void SkBaseShadowTessellator::handleLine(const SkPoint& p) {
+ if (fPathPolygon.count() > 0) {
+ if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], p)) {
+ // skip coincident point
+ return;
+ }
+ }
+
+ if (fPathPolygon.count() > 1) {
+ if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2],
+ fPathPolygon[fPathPolygon.count() - 1],
+ p)) {
+ // remove collinear point
+ fPathPolygon.pop();
+ }
+ }
+
+ *fPathPolygon.push() = p;
+}
+
void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) {
m.mapPoints(p, 1);
+
this->handleLine(*p);
}
@@ -386,7 +489,8 @@
const SkPoint3& zPlaneParams, bool transparent);
private:
- void handleLine(const SkPoint& p) override;
+ void computePathPolygon(const SkPath& path, const SkMatrix& ctm);
+ void handlePolyPoint(const SkPoint& p);
void addEdge(const SkVector& nextPoint, const SkVector& nextNormal);
static constexpr auto kMaxEdgeLenSqr = 20 * 20;
@@ -400,7 +504,6 @@
return SkColorSetARGB(umbraAlpha * 255.9999f, 0, 0, 0);
}
- int fCentroidCount;
bool fSplitFirstEdge;
bool fSplitPreviousEdge;
@@ -438,48 +541,26 @@
// Middle ring: 0
fIndices.setReserve(12 * 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;
- if (fTransparent) {
- *fPositions.push() = SkPoint::Make(0, 0);
- *fColors.push() = fUmbraColor;
- fCentroidCount = 0;
+ this->computePathPolygon(path, ctm);
+ if (fPathPolygon.count() < 3) {
+ return;
}
- while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
- switch (verb) {
- case SkPath::kLine_Verb:
- this->INHERITED::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;
- }
- // TODO: add support for concave paths
- if (!fIsConvex) {
- return;
- }
- }
-
- if (!this->indexCount()) {
+ // TODO: add support for concave paths
+ if (!fIsConvex) {
return;
}
- // final convexity check
- // TODO: add support for concave paths
- if (fDirection*perp_dot(fInitPoints[1], fInitPoints[2], fFirstPoint) > 0) {
+ // Add center point for fan if needed
+ if (fTransparent) {
+ *fPositions.push() = fCentroid;
+ *fColors.push() = this->umbraColor(fTransformedHeightFunc(fCentroid));
+ }
+
+ for (int i = 0; i < fPathPolygon.count(); ++i) {
+ this->handlePolyPoint(fPathPolygon[i]);
+ }
+
+ if (!this->indexCount()) {
return;
}
@@ -531,11 +612,8 @@
fPrevUmbraIndex, fPositions.count() - 3);
}
- // if transparent, add point to first one in array and add to center fan
+ // if transparent, add to center fan
if (fTransparent) {
- fPositions[0] += centerPoint;
- ++fCentroidCount;
-
*fIndices.push() = 0;
*fIndices.push() = fPrevUmbraIndex;
*fIndices.push() = fPositions.count() - 2;
@@ -558,11 +636,8 @@
fPrevOutset = normal;
}
- // finalize centroid
+ // finalize center fan
if (fTransparent) {
- fPositions[0] *= SkScalarFastInvert(fCentroidCount);
- fColors[0] = this->umbraColor(fTransformedHeightFunc(fPositions[0]));
-
this->appendTriangle(0, fPrevUmbraIndex, fFirstVertexIndex);
}
@@ -582,12 +657,42 @@
fSucceeded = true;
}
-void SkAmbientShadowTessellator::handleLine(const SkPoint& p) {
- // skip duplicate points
- if (!fInitPoints.isEmpty() && duplicate_pt(p, fInitPoints[fInitPoints.count() - 1])) {
- return;
+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();
+}
+
+void SkAmbientShadowTessellator::handlePolyPoint(const SkPoint& p) {
+ // should have no coincident points
+ SkASSERT(fInitPoints.isEmpty() || !duplicate_pt(p, fInitPoints[fInitPoints.count() - 1]));
+
if (fInitPoints.count() < 2) {
*fInitPoints.push() = p;
return;
@@ -596,11 +701,8 @@
if (fInitPoints.count() == 2) {
// determine if cw or ccw
SkScalar perpDot = perp_dot(fInitPoints[0], fInitPoints[1], p);
- if (SkScalarNearlyZero(perpDot)) {
- // nearly parallel, just treat as straight line and continue
- fInitPoints[1] = p;
- return;
- }
+ // should not be collinear
+ SkASSERT(!SkScalarNearlyZero(perpDot));
// if perpDot > 0, winding is ccw
fDirection = (perpDot > 0) ? -1 : 1;
@@ -627,10 +729,6 @@
*fColors.push() = this->umbraColor(z);
*fPositions.push() = fFirstPoint + fFirstOutset;
*fColors.push() = fPenumbraColor;
- if (fTransparent) {
- fPositions[0] += fFirstPoint;
- fCentroidCount = 1;
- }
// add the first quad
z = fTransformedHeightFunc(fInitPoints[1]);
@@ -640,15 +738,6 @@
// to ensure we skip this block next time
*fInitPoints.push() = p;
- } else {
- // reuse fInitPoints to track last three points
- fInitPoints[0] = fInitPoints[1];
- fInitPoints[1] = fInitPoints[2];
- fInitPoints[2] = p;
- // convexity check
- if (fDirection*perp_dot(fInitPoints[0], fInitPoints[1], p) > 0) {
- fIsConvex = false;
- }
}
SkVector normal;
@@ -706,11 +795,8 @@
fPrevUmbraIndex, fPositions.count() - 3);
}
- // if transparent, add point to first one in array and add to center fan
+ // if transparent, add to center fan
if (fTransparent) {
- fPositions[0] += centerPoint;
- ++fCentroidCount;
-
this->appendTriangle(0, fPrevUmbraIndex, fPositions.count() - 2);
}
@@ -738,11 +824,8 @@
fPrevUmbraIndex, fPositions.count() - 3);
}
- // if transparent, add point to first one in array and add to center fan
+ // if transparent, add to center fan
if (fTransparent) {
- fPositions[0] += nextPoint;
- ++fCentroidCount;
-
this->appendTriangle(0, fPrevUmbraIndex, fPositions.count() - 2);
}
@@ -769,7 +852,6 @@
bool computeConvexShadow(SkScalar radius);
bool computeConcaveShadow(SkScalar radius);
- void handleLine(const SkPoint& p) override;
bool handlePolyPoint(const SkPoint& p);
void mapPoints(SkScalar scale, const SkVector& xlate, SkPoint* pts, int count);
@@ -788,10 +870,7 @@
SkTDArray<SkPoint> fClipPolygon;
SkTDArray<SkVector> fClipVectors;
- SkPoint fCentroid;
- SkScalar fArea;
- SkTDArray<SkPoint> fPathPolygon;
SkTDArray<SkPoint> fUmbraPolygon;
int fCurrClipPoint;
int fCurrUmbraPoint;
@@ -906,14 +985,6 @@
}
}
- 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;
- }
- }
-
if (fIsConvex) {
if (!this->computeConvexShadow(radius)) {
return;
@@ -977,10 +1048,6 @@
fClipPolygon.reset();
- // init centroid
- fCentroid = SkPoint::Make(0, 0);
- fArea = 0;
-
// coefficients to compute cubic Bezier at t = 5/16
static constexpr SkScalar kA = 0.32495117187f;
static constexpr SkScalar kB = 0.44311523437f;
@@ -994,7 +1061,7 @@
case SkPath::kLine_Verb:
ctm.mapPoints(&pts[1], 1);
this->addToClip(pts[1]);
- this->INHERITED::handleLine(shadowTransform, &pts[1]);
+ this->handleLine(shadowTransform, &pts[1]);
break;
case SkPath::kQuad_Verb:
ctm.mapPoints(pts, 3);
@@ -1038,17 +1105,7 @@
}
}
- // finish centroid
- if (fPathPolygon.count() > 0) {
- SkPoint currPoint = fPathPolygon[fPathPolygon.count() - 1];
- SkPoint nextPoint = fPathPolygon[0];
- SkScalar quadArea = currPoint.cross(nextPoint);
- fCentroid.fX += (currPoint.fX + nextPoint.fX) * quadArea;
- fCentroid.fY += (currPoint.fY + nextPoint.fY) * quadArea;
- fArea += quadArea;
- fCentroid *= sk_ieee_float_divide(1, 3 * fArea);
- }
-
+ this->finishPathPolygon();
fCurrClipPoint = fClipPolygon.count() - 1;
}
@@ -1058,7 +1115,6 @@
// init clip vectors
SkVector v0 = fClipPolygon[1] - fClipPolygon[0];
SkVector v1 = fClipPolygon[2] - fClipPolygon[0];
- SkScalar winding = v0.cross(v1);
*fClipVectors.push() = v0;
// init centroid check
@@ -1070,10 +1126,6 @@
// add to clip vectors
v0 = fClipPolygon[(p + 1) % fClipPolygon.count()] - fClipPolygon[p];
*fClipVectors.push() = v0;
- v1 = fClipPolygon[(p + 2) % fClipPolygon.count()] - fClipPolygon[p];
- if (winding*v0.cross(v1) < 0) {
- fIsConvex = false;
- }
// Determine if transformed centroid is inside clipPolygon.
v1 = fCentroid - fClipPolygon[p];
if (initCross*v0.cross(v1) <= 0) {
@@ -1393,33 +1445,6 @@
}
}
-static bool is_collinear(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
- return (SkScalarNearlyZero(perp_dot(p0, p1, p2)));
-}
-
-void SkSpotShadowTessellator::handleLine(const SkPoint& p) {
- // remove coincident points and add to centroid
- if (fPathPolygon.count() > 0) {
- const SkPoint& lastPoint = fPathPolygon[fPathPolygon.count() - 1];
- if (duplicate_pt(p, lastPoint)) {
- return;
- }
- SkScalar quadArea = lastPoint.cross(p);
- fCentroid.fX += (p.fX + lastPoint.fX) * quadArea;
- fCentroid.fY += (p.fY + lastPoint.fY) * quadArea;
- fArea += quadArea;
- }
-
- // try to remove collinear points
- if (fPathPolygon.count() > 1 && is_collinear(fPathPolygon[fPathPolygon.count()-2],
- fPathPolygon[fPathPolygon.count()-1],
- p)) {
- fPathPolygon[fPathPolygon.count() - 1] = p;
- } else {
- *fPathPolygon.push() = p;
- }
-}
-
bool SkSpotShadowTessellator::handlePolyPoint(const SkPoint& p) {
if (fInitPoints.count() < 2) {
*fInitPoints.push() = p;
@@ -1429,11 +1454,8 @@
if (fInitPoints.count() == 2) {
// determine if cw or ccw
SkScalar perpDot = perp_dot(fInitPoints[0], fInitPoints[1], p);
- if (SkScalarNearlyZero(perpDot)) {
- // nearly parallel, just treat as straight line and continue
- fInitPoints[1] = p;
- return true;
- }
+ // shouldn't be any collinear points
+ SkASSERT(!SkScalarNearlyZero(perpDot));
// if perpDot > 0, winding is ccw
fDirection = (perpDot > 0) ? -1 : 1;