Move triangulators and tessellators into gpu/geometry
This is the other half of making everything in gpu/ops be v1-only.
Bug: skia:11837
Change-Id: I5d77a499ef02eba69208d5bd634650433d02f6fb
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/440216
Reviewed-by: Michael Ludwig <michaelludwig@google.com>
Commit-Queue: Robert Phillips <robertphillips@google.com>
diff --git a/src/gpu/ops/GrAAConvexTessellator.cpp b/src/gpu/ops/GrAAConvexTessellator.cpp
deleted file mode 100644
index f2ed77a..0000000
--- a/src/gpu/ops/GrAAConvexTessellator.cpp
+++ /dev/null
@@ -1,1125 +0,0 @@
-/*
- * Copyright 2015 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/SkCanvas.h"
-#include "include/core/SkPath.h"
-#include "include/core/SkPoint.h"
-#include "include/core/SkString.h"
-#include "include/private/SkTPin.h"
-#include "src/gpu/geometry/GrPathUtils.h"
-#include "src/gpu/ops/GrAAConvexTessellator.h"
-
-// Next steps:
-// add an interactive sample app slide
-// add debug check that all points are suitably far apart
-// test more degenerate cases
-
-// The tolerance for fusing vertices and eliminating colinear lines (It is in device space).
-static const SkScalar kClose = (SK_Scalar1 / 16);
-static const SkScalar kCloseSqd = kClose * kClose;
-
-// tesselation tolerance values, in device space pixels
-static const SkScalar kQuadTolerance = 0.2f;
-static const SkScalar kCubicTolerance = 0.2f;
-static const SkScalar kConicTolerance = 0.25f;
-
-// dot product below which we use a round cap between curve segments
-static const SkScalar kRoundCapThreshold = 0.8f;
-
-// dot product above which we consider two adjacent curves to be part of the "same" curve
-static const SkScalar kCurveConnectionThreshold = 0.8f;
-
-static bool intersect(const SkPoint& p0, const SkPoint& n0,
- const SkPoint& p1, const SkPoint& n1,
- SkScalar* t) {
- const SkPoint v = p1 - p0;
- SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX;
- if (SkScalarNearlyZero(perpDot)) {
- return false;
- }
- *t = (v.fX * n1.fY - v.fY * n1.fX) / perpDot;
- return SkScalarIsFinite(*t);
-}
-
-// This is a special case version of intersect where we have the vector
-// perpendicular to the second line rather than the vector parallel to it.
-static SkScalar perp_intersect(const SkPoint& p0, const SkPoint& n0,
- const SkPoint& p1, const SkPoint& perp) {
- const SkPoint v = p1 - p0;
- SkScalar perpDot = n0.dot(perp);
- return v.dot(perp) / perpDot;
-}
-
-static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) {
- SkScalar distSq = SkPointPriv::DistanceToSqd(p0, p1);
- return distSq < kCloseSqd;
-}
-
-static bool points_are_colinear_and_b_is_middle(const SkPoint& a, const SkPoint& b,
- const SkPoint& c, float* accumError) {
- // First check distance from b to the infinite line through a, c
- SkVector aToC = c - a;
- SkVector n = {aToC.fY, -aToC.fX};
- n.normalize();
-
- SkScalar distBToLineAC = SkScalarAbs(n.dot(b) - n.dot(a));
- if (*accumError + distBToLineAC >= kClose || aToC.dot(b - a) <= 0.f || aToC.dot(c - b) <= 0.f) {
- // Too far from the line or not between the line segment from a to c
- return false;
- } else {
- // Accumulate the distance from b to |ac| that goes "away" when this near-colinear point
- // is removed to simplify the path.
- *accumError += distBToLineAC;
- return true;
- }
-}
-
-int GrAAConvexTessellator::addPt(const SkPoint& pt,
- SkScalar depth,
- SkScalar coverage,
- bool movable,
- CurveState curve) {
- SkASSERT(pt.isFinite());
- this->validate();
-
- int index = fPts.count();
- *fPts.push() = pt;
- *fCoverages.push() = coverage;
- *fMovable.push() = movable;
- *fCurveState.push() = curve;
-
- this->validate();
- return index;
-}
-
-void GrAAConvexTessellator::popLastPt() {
- this->validate();
-
- fPts.pop();
- fCoverages.pop();
- fMovable.pop();
- fCurveState.pop();
-
- this->validate();
-}
-
-void GrAAConvexTessellator::popFirstPtShuffle() {
- this->validate();
-
- fPts.removeShuffle(0);
- fCoverages.removeShuffle(0);
- fMovable.removeShuffle(0);
- fCurveState.removeShuffle(0);
-
- this->validate();
-}
-
-void GrAAConvexTessellator::updatePt(int index,
- const SkPoint& pt,
- SkScalar depth,
- SkScalar coverage) {
- this->validate();
- SkASSERT(fMovable[index]);
-
- fPts[index] = pt;
- fCoverages[index] = coverage;
-}
-
-void GrAAConvexTessellator::addTri(int i0, int i1, int i2) {
- if (i0 == i1 || i1 == i2 || i2 == i0) {
- return;
- }
-
- *fIndices.push() = i0;
- *fIndices.push() = i1;
- *fIndices.push() = i2;
-}
-
-void GrAAConvexTessellator::rewind() {
- fPts.rewind();
- fCoverages.rewind();
- fMovable.rewind();
- fIndices.rewind();
- fNorms.rewind();
- fCurveState.rewind();
- fInitialRing.rewind();
- fCandidateVerts.rewind();
-#if GR_AA_CONVEX_TESSELLATOR_VIZ
- fRings.rewind(); // TODO: leak in this case!
-#else
- fRings[0].rewind();
- fRings[1].rewind();
-#endif
-}
-
-void GrAAConvexTessellator::computeNormals() {
- auto normalToVector = [this](SkVector v) {
- SkVector n = SkPointPriv::MakeOrthog(v, fSide);
- SkAssertResult(n.normalize());
- SkASSERT(SkScalarNearlyEqual(1.0f, n.length()));
- return n;
- };
-
- // Check the cross product of the final trio
- fNorms.append(fPts.count());
- fNorms[0] = fPts[1] - fPts[0];
- fNorms.top() = fPts[0] - fPts.top();
- SkScalar cross = SkPoint::CrossProduct(fNorms[0], fNorms.top());
- fSide = (cross > 0.0f) ? SkPointPriv::kRight_Side : SkPointPriv::kLeft_Side;
- fNorms[0] = normalToVector(fNorms[0]);
- for (int cur = 1; cur < fNorms.count() - 1; ++cur) {
- fNorms[cur] = normalToVector(fPts[cur + 1] - fPts[cur]);
- }
- fNorms.top() = normalToVector(fNorms.top());
-}
-
-void GrAAConvexTessellator::computeBisectors() {
- fBisectors.setCount(fNorms.count());
-
- int prev = fBisectors.count() - 1;
- for (int cur = 0; cur < fBisectors.count(); prev = cur, ++cur) {
- fBisectors[cur] = fNorms[cur] + fNorms[prev];
- if (!fBisectors[cur].normalize()) {
- fBisectors[cur] = SkPointPriv::MakeOrthog(fNorms[cur], (SkPointPriv::Side)-fSide) +
- SkPointPriv::MakeOrthog(fNorms[prev], fSide);
- SkAssertResult(fBisectors[cur].normalize());
- } else {
- fBisectors[cur].negate(); // make the bisector face in
- }
- if (fCurveState[prev] == kIndeterminate_CurveState) {
- if (fCurveState[cur] == kSharp_CurveState) {
- fCurveState[prev] = kSharp_CurveState;
- } else {
- if (SkScalarAbs(fNorms[cur].dot(fNorms[prev])) > kCurveConnectionThreshold) {
- fCurveState[prev] = kCurve_CurveState;
- fCurveState[cur] = kCurve_CurveState;
- } else {
- fCurveState[prev] = kSharp_CurveState;
- fCurveState[cur] = kSharp_CurveState;
- }
- }
- }
-
- SkASSERT(SkScalarNearlyEqual(1.0f, fBisectors[cur].length()));
- }
-}
-
-// Create as many rings as we need to (up to a predefined limit) to reach the specified target
-// depth. If we are in fill mode, the final ring will automatically be fanned.
-bool GrAAConvexTessellator::createInsetRings(Ring& previousRing, SkScalar initialDepth,
- SkScalar initialCoverage, SkScalar targetDepth,
- SkScalar targetCoverage, Ring** finalRing) {
- static const int kMaxNumRings = 8;
-
- if (previousRing.numPts() < 3) {
- return false;
- }
- Ring* currentRing = &previousRing;
- int i;
- for (i = 0; i < kMaxNumRings; ++i) {
- Ring* nextRing = this->getNextRing(currentRing);
- SkASSERT(nextRing != currentRing);
-
- bool done = this->createInsetRing(*currentRing, nextRing, initialDepth, initialCoverage,
- targetDepth, targetCoverage, i == 0);
- currentRing = nextRing;
- if (done) {
- break;
- }
- currentRing->init(*this);
- }
-
- if (kMaxNumRings == i) {
- // Bail if we've exceeded the amount of time we want to throw at this.
- this->terminate(*currentRing);
- return false;
- }
- bool done = currentRing->numPts() >= 3;
- if (done) {
- currentRing->init(*this);
- }
- *finalRing = currentRing;
- return done;
-}
-
-// The general idea here is to, conceptually, start with the original polygon and slide
-// the vertices along the bisectors until the first intersection. At that
-// point two of the edges collapse and the process repeats on the new polygon.
-// The polygon state is captured in the Ring class while the GrAAConvexTessellator
-// controls the iteration. The CandidateVerts holds the formative points for the
-// next ring.
-bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) {
- if (!this->extractFromPath(m, path)) {
- return false;
- }
-
- SkScalar coverage = 1.0f;
- SkScalar scaleFactor = 0.0f;
-
- if (SkStrokeRec::kStrokeAndFill_Style == fStyle) {
- SkASSERT(m.isSimilarity());
- scaleFactor = m.getMaxScale(); // x and y scale are the same
- SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth;
- Ring outerStrokeAndAARing;
- this->createOuterRing(fInitialRing,
- effectiveStrokeWidth / 2 + kAntialiasingRadius, 0.0,
- &outerStrokeAndAARing);
-
- // discard all the triangles added between the originating ring and the new outer ring
- fIndices.rewind();
-
- outerStrokeAndAARing.init(*this);
-
- outerStrokeAndAARing.makeOriginalRing();
-
- // Add the outer stroke ring's normals to the originating ring's normals
- // so it can also act as an originating ring
- fNorms.setCount(fNorms.count() + outerStrokeAndAARing.numPts());
- for (int i = 0; i < outerStrokeAndAARing.numPts(); ++i) {
- SkASSERT(outerStrokeAndAARing.index(i) < fNorms.count());
- fNorms[outerStrokeAndAARing.index(i)] = outerStrokeAndAARing.norm(i);
- }
-
- // the bisectors are only needed for the computation of the outer ring
- fBisectors.rewind();
-
- Ring* insetAARing;
- this->createInsetRings(outerStrokeAndAARing,
- 0.0f, 0.0f, 2*kAntialiasingRadius, 1.0f,
- &insetAARing);
-
- SkDEBUGCODE(this->validate();)
- return true;
- }
-
- if (SkStrokeRec::kStroke_Style == fStyle) {
- SkASSERT(fStrokeWidth >= 0.0f);
- SkASSERT(m.isSimilarity());
- scaleFactor = m.getMaxScale(); // x and y scale are the same
- SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth;
- Ring outerStrokeRing;
- this->createOuterRing(fInitialRing, effectiveStrokeWidth / 2 - kAntialiasingRadius,
- coverage, &outerStrokeRing);
- outerStrokeRing.init(*this);
- Ring outerAARing;
- this->createOuterRing(outerStrokeRing, kAntialiasingRadius * 2, 0.0f, &outerAARing);
- } else {
- Ring outerAARing;
- this->createOuterRing(fInitialRing, kAntialiasingRadius, 0.0f, &outerAARing);
- }
-
- // the bisectors are only needed for the computation of the outer ring
- fBisectors.rewind();
- if (SkStrokeRec::kStroke_Style == fStyle && fInitialRing.numPts() > 2) {
- SkASSERT(fStrokeWidth >= 0.0f);
- SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth;
- Ring* insetStrokeRing;
- SkScalar strokeDepth = effectiveStrokeWidth / 2 - kAntialiasingRadius;
- if (this->createInsetRings(fInitialRing, 0.0f, coverage, strokeDepth, coverage,
- &insetStrokeRing)) {
- Ring* insetAARing;
- this->createInsetRings(*insetStrokeRing, strokeDepth, coverage, strokeDepth +
- kAntialiasingRadius * 2, 0.0f, &insetAARing);
- }
- } else {
- Ring* insetAARing;
- this->createInsetRings(fInitialRing, 0.0f, 0.5f, kAntialiasingRadius, 1.0f, &insetAARing);
- }
-
- SkDEBUGCODE(this->validate();)
- return true;
-}
-
-SkScalar GrAAConvexTessellator::computeDepthFromEdge(int edgeIdx, const SkPoint& p) const {
- SkASSERT(edgeIdx < fNorms.count());
-
- SkPoint v = p - fPts[edgeIdx];
- SkScalar depth = -fNorms[edgeIdx].dot(v);
- return depth;
-}
-
-// Find a point that is 'desiredDepth' away from the 'edgeIdx'-th edge and lies
-// along the 'bisector' from the 'startIdx'-th point.
-bool GrAAConvexTessellator::computePtAlongBisector(int startIdx,
- const SkVector& bisector,
- int edgeIdx,
- SkScalar desiredDepth,
- SkPoint* result) const {
- const SkPoint& norm = fNorms[edgeIdx];
-
- // First find the point where the edge and the bisector intersect
- SkPoint newP;
-
- SkScalar t = perp_intersect(fPts[startIdx], bisector, fPts[edgeIdx], norm);
- if (SkScalarNearlyEqual(t, 0.0f)) {
- // the start point was one of the original ring points
- SkASSERT(startIdx < fPts.count());
- newP = fPts[startIdx];
- } else if (t < 0.0f) {
- newP = bisector;
- newP.scale(t);
- newP += fPts[startIdx];
- } else {
- return false;
- }
-
- // Then offset along the bisector from that point the correct distance
- SkScalar dot = bisector.dot(norm);
- t = -desiredDepth / dot;
- *result = bisector;
- result->scale(t);
- *result += newP;
-
- return true;
-}
-
-bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) {
- SkASSERT(path.isConvex());
-
- SkRect bounds = path.getBounds();
- m.mapRect(&bounds);
- if (!bounds.isFinite()) {
- // We could do something smarter here like clip the path based on the bounds of the dst.
- // We'd have to be careful about strokes to ensure we don't draw something wrong.
- return false;
- }
-
- // Outer ring: 3*numPts
- // Middle ring: numPts
- // Presumptive inner ring: numPts
- this->reservePts(5*path.countPoints());
- // Outer ring: 12*numPts
- // Middle ring: 0
- // Presumptive inner ring: 6*numPts + 6
- fIndices.setReserve(18*path.countPoints() + 6);
-
- // Reset the accumulated error for all the future lineTo() calls when iterating over the path.
- fAccumLinearError = 0.f;
- // TODO: is there a faster way to extract the points from the path? Perhaps
- // get all the points via a new entry point, transform them all in bulk
- // and then walk them to find duplicates?
- SkPathEdgeIter iter(path);
- while (auto e = iter.next()) {
- switch (e.fEdge) {
- case SkPathEdgeIter::Edge::kLine:
- if (!SkPathPriv::AllPointsEq(e.fPts, 2)) {
- this->lineTo(m, e.fPts[1], kSharp_CurveState);
- }
- break;
- case SkPathEdgeIter::Edge::kQuad:
- if (!SkPathPriv::AllPointsEq(e.fPts, 3)) {
- this->quadTo(m, e.fPts);
- }
- break;
- case SkPathEdgeIter::Edge::kCubic:
- if (!SkPathPriv::AllPointsEq(e.fPts, 4)) {
- this->cubicTo(m, e.fPts);
- }
- break;
- case SkPathEdgeIter::Edge::kConic:
- if (!SkPathPriv::AllPointsEq(e.fPts, 3)) {
- this->conicTo(m, e.fPts, iter.conicWeight());
- }
- break;
- }
- }
-
- if (this->numPts() < 2) {
- return false;
- }
-
- // check if last point is a duplicate of the first point. If so, remove it.
- if (duplicate_pt(fPts[this->numPts()-1], fPts[0])) {
- this->popLastPt();
- }
-
- // Remove any lingering colinear points where the path wraps around
- fAccumLinearError = 0.f;
- bool noRemovalsToDo = false;
- while (!noRemovalsToDo && this->numPts() >= 3) {
- if (points_are_colinear_and_b_is_middle(fPts[fPts.count() - 2], fPts.top(), fPts[0],
- &fAccumLinearError)) {
- this->popLastPt();
- } else if (points_are_colinear_and_b_is_middle(fPts.top(), fPts[0], fPts[1],
- &fAccumLinearError)) {
- this->popFirstPtShuffle();
- } else {
- noRemovalsToDo = true;
- }
- }
-
- // Compute the normals and bisectors.
- SkASSERT(fNorms.empty());
- if (this->numPts() >= 3) {
- this->computeNormals();
- this->computeBisectors();
- } else if (this->numPts() == 2) {
- // We've got two points, so we're degenerate.
- if (fStyle == SkStrokeRec::kFill_Style) {
- // it's a fill, so we don't need to worry about degenerate paths
- return false;
- }
- // For stroking, we still need to process the degenerate path, so fix it up
- fSide = SkPointPriv::kLeft_Side;
-
- fNorms.append(2);
- fNorms[0] = SkPointPriv::MakeOrthog(fPts[1] - fPts[0], fSide);
- fNorms[0].normalize();
- fNorms[1] = -fNorms[0];
- SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[0].length()));
- // we won't actually use the bisectors, so just push zeroes
- fBisectors.push_back(SkPoint::Make(0.0, 0.0));
- fBisectors.push_back(SkPoint::Make(0.0, 0.0));
- } else {
- return false;
- }
-
- fCandidateVerts.setReserve(this->numPts());
- fInitialRing.setReserve(this->numPts());
- for (int i = 0; i < this->numPts(); ++i) {
- fInitialRing.addIdx(i, i);
- }
- fInitialRing.init(fNorms, fBisectors);
-
- this->validate();
- return true;
-}
-
-GrAAConvexTessellator::Ring* GrAAConvexTessellator::getNextRing(Ring* lastRing) {
-#if GR_AA_CONVEX_TESSELLATOR_VIZ
- Ring* ring = *fRings.push() = new Ring;
- ring->setReserve(fInitialRing.numPts());
- ring->rewind();
- return ring;
-#else
- // Flip flop back and forth between fRings[0] & fRings[1]
- int nextRing = (lastRing == &fRings[0]) ? 1 : 0;
- fRings[nextRing].setReserve(fInitialRing.numPts());
- fRings[nextRing].rewind();
- return &fRings[nextRing];
-#endif
-}
-
-void GrAAConvexTessellator::fanRing(const Ring& ring) {
- // fan out from point 0
- int startIdx = ring.index(0);
- for (int cur = ring.numPts() - 2; cur >= 0; --cur) {
- this->addTri(startIdx, ring.index(cur), ring.index(cur + 1));
- }
-}
-
-void GrAAConvexTessellator::createOuterRing(const Ring& previousRing, SkScalar outset,
- SkScalar coverage, Ring* nextRing) {
- const int numPts = previousRing.numPts();
- if (numPts == 0) {
- return;
- }
-
- int prev = numPts - 1;
- int lastPerpIdx = -1, firstPerpIdx = -1;
-
- const SkScalar outsetSq = outset * outset;
- SkScalar miterLimitSq = outset * fMiterLimit;
- miterLimitSq = miterLimitSq * miterLimitSq;
- for (int cur = 0; cur < numPts; ++cur) {
- int originalIdx = previousRing.index(cur);
- // For each vertex of the original polygon we add at least two points to the
- // outset polygon - one extending perpendicular to each impinging edge. Connecting these
- // two points yields a bevel join. We need one additional point for a mitered join, and
- // a round join requires one or more points depending upon curvature.
-
- // The perpendicular point for the last edge
- SkPoint normal1 = previousRing.norm(prev);
- SkPoint perp1 = normal1;
- perp1.scale(outset);
- perp1 += this->point(originalIdx);
-
- // The perpendicular point for the next edge.
- SkPoint normal2 = previousRing.norm(cur);
- SkPoint perp2 = normal2;
- perp2.scale(outset);
- perp2 += fPts[originalIdx];
-
- CurveState curve = fCurveState[originalIdx];
-
- // We know it isn't a duplicate of the prior point (since it and this
- // one are just perpendicular offsets from the non-merged polygon points)
- int perp1Idx = this->addPt(perp1, -outset, coverage, false, curve);
- nextRing->addIdx(perp1Idx, originalIdx);
-
- int perp2Idx;
- // For very shallow angles all the corner points could fuse.
- if (duplicate_pt(perp2, this->point(perp1Idx))) {
- perp2Idx = perp1Idx;
- } else {
- perp2Idx = this->addPt(perp2, -outset, coverage, false, curve);
- }
-
- if (perp2Idx != perp1Idx) {
- if (curve == kCurve_CurveState) {
- // bevel or round depending upon curvature
- SkScalar dotProd = normal1.dot(normal2);
- if (dotProd < kRoundCapThreshold) {
- // Currently we "round" by creating a single extra point, which produces
- // good results for common cases. For thick strokes with high curvature, we will
- // need to add more points; for the time being we simply fall back to software
- // rendering for thick strokes.
- SkPoint miter = previousRing.bisector(cur);
- miter.setLength(-outset);
- miter += fPts[originalIdx];
-
- // For very shallow angles all the corner points could fuse
- if (!duplicate_pt(miter, this->point(perp1Idx))) {
- int miterIdx;
- miterIdx = this->addPt(miter, -outset, coverage, false, kSharp_CurveState);
- nextRing->addIdx(miterIdx, originalIdx);
- // The two triangles for the corner
- this->addTri(originalIdx, perp1Idx, miterIdx);
- this->addTri(originalIdx, miterIdx, perp2Idx);
- }
- } else {
- this->addTri(originalIdx, perp1Idx, perp2Idx);
- }
- } else {
- switch (fJoin) {
- case SkPaint::Join::kMiter_Join: {
- // The bisector outset point
- SkPoint miter = previousRing.bisector(cur);
- SkScalar dotProd = normal1.dot(normal2);
- // The max is because this could go slightly negative if precision causes
- // us to become slightly concave.
- SkScalar sinHalfAngleSq = std::max(SkScalarHalf(SK_Scalar1 + dotProd), 0.f);
- SkScalar lengthSq = sk_ieee_float_divide(outsetSq, sinHalfAngleSq);
- if (lengthSq > miterLimitSq) {
- // just bevel it
- this->addTri(originalIdx, perp1Idx, perp2Idx);
- break;
- }
- miter.setLength(-SkScalarSqrt(lengthSq));
- miter += fPts[originalIdx];
-
- // For very shallow angles all the corner points could fuse
- if (!duplicate_pt(miter, this->point(perp1Idx))) {
- int miterIdx;
- miterIdx = this->addPt(miter, -outset, coverage, false,
- kSharp_CurveState);
- nextRing->addIdx(miterIdx, originalIdx);
- // The two triangles for the corner
- this->addTri(originalIdx, perp1Idx, miterIdx);
- this->addTri(originalIdx, miterIdx, perp2Idx);
- } else {
- // ignore the miter point as it's so close to perp1/perp2 and simply
- // bevel.
- this->addTri(originalIdx, perp1Idx, perp2Idx);
- }
- break;
- }
- case SkPaint::Join::kBevel_Join:
- this->addTri(originalIdx, perp1Idx, perp2Idx);
- break;
- default:
- // kRound_Join is unsupported for now. GrAALinearizingConvexPathRenderer is
- // only willing to draw mitered or beveled, so we should never get here.
- SkASSERT(false);
- }
- }
-
- nextRing->addIdx(perp2Idx, originalIdx);
- }
-
- if (0 == cur) {
- // Store the index of the first perpendicular point to finish up
- firstPerpIdx = perp1Idx;
- SkASSERT(-1 == lastPerpIdx);
- } else {
- // The triangles for the previous edge
- int prevIdx = previousRing.index(prev);
- this->addTri(prevIdx, perp1Idx, originalIdx);
- this->addTri(prevIdx, lastPerpIdx, perp1Idx);
- }
-
- // Track the last perpendicular outset point so we can construct the
- // trailing edge triangles.
- lastPerpIdx = perp2Idx;
- prev = cur;
- }
-
- // pick up the final edge rect
- int lastIdx = previousRing.index(numPts - 1);
- this->addTri(lastIdx, firstPerpIdx, previousRing.index(0));
- this->addTri(lastIdx, lastPerpIdx, firstPerpIdx);
-
- this->validate();
-}
-
-// Something went wrong in the creation of the next ring. If we're filling the shape, just go ahead
-// and fan it.
-void GrAAConvexTessellator::terminate(const Ring& ring) {
- if (fStyle != SkStrokeRec::kStroke_Style && ring.numPts() > 0) {
- this->fanRing(ring);
- }
-}
-
-static SkScalar compute_coverage(SkScalar depth, SkScalar initialDepth, SkScalar initialCoverage,
- SkScalar targetDepth, SkScalar targetCoverage) {
- if (SkScalarNearlyEqual(initialDepth, targetDepth)) {
- return targetCoverage;
- }
- SkScalar result = (depth - initialDepth) / (targetDepth - initialDepth) *
- (targetCoverage - initialCoverage) + initialCoverage;
- return SkTPin(result, 0.0f, 1.0f);
-}
-
-// return true when processing is complete
-bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing,
- SkScalar initialDepth, SkScalar initialCoverage,
- SkScalar targetDepth, SkScalar targetCoverage,
- bool forceNew) {
- bool done = false;
-
- fCandidateVerts.rewind();
-
- // Loop through all the points in the ring and find the intersection with the smallest depth
- SkScalar minDist = SK_ScalarMax, minT = 0.0f;
- int minEdgeIdx = -1;
-
- for (int cur = 0; cur < lastRing.numPts(); ++cur) {
- int next = (cur + 1) % lastRing.numPts();
-
- SkScalar t;
- bool result = intersect(this->point(lastRing.index(cur)), lastRing.bisector(cur),
- this->point(lastRing.index(next)), lastRing.bisector(next),
- &t);
- // The bisectors may be parallel (!result) or the previous ring may have become slightly
- // concave due to accumulated error (t <= 0).
- if (!result || t <= 0) {
- continue;
- }
- SkScalar dist = -t * lastRing.norm(cur).dot(lastRing.bisector(cur));
-
- if (minDist > dist) {
- minDist = dist;
- minT = t;
- minEdgeIdx = cur;
- }
- }
-
- if (minEdgeIdx == -1) {
- return false;
- }
- SkPoint newPt = lastRing.bisector(minEdgeIdx);
- newPt.scale(minT);
- newPt += this->point(lastRing.index(minEdgeIdx));
-
- SkScalar depth = this->computeDepthFromEdge(lastRing.origEdgeID(minEdgeIdx), newPt);
- if (depth >= targetDepth) {
- // None of the bisectors intersect before reaching the desired depth.
- // Just step them all to the desired depth
- depth = targetDepth;
- done = true;
- }
-
- // 'dst' stores where each point in the last ring maps to/transforms into
- // in the next ring.
- SkTDArray<int> dst;
- dst.setCount(lastRing.numPts());
-
- // Create the first point (who compares with no one)
- if (!this->computePtAlongBisector(lastRing.index(0),
- lastRing.bisector(0),
- lastRing.origEdgeID(0),
- depth, &newPt)) {
- this->terminate(lastRing);
- return true;
- }
- dst[0] = fCandidateVerts.addNewPt(newPt,
- lastRing.index(0), lastRing.origEdgeID(0),
- !this->movable(lastRing.index(0)));
-
- // Handle the middle points (who only compare with the prior point)
- for (int cur = 1; cur < lastRing.numPts()-1; ++cur) {
- if (!this->computePtAlongBisector(lastRing.index(cur),
- lastRing.bisector(cur),
- lastRing.origEdgeID(cur),
- depth, &newPt)) {
- this->terminate(lastRing);
- return true;
- }
- if (!duplicate_pt(newPt, fCandidateVerts.lastPoint())) {
- dst[cur] = fCandidateVerts.addNewPt(newPt,
- lastRing.index(cur), lastRing.origEdgeID(cur),
- !this->movable(lastRing.index(cur)));
- } else {
- dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur));
- }
- }
-
- // Check on the last point (handling the wrap around)
- int cur = lastRing.numPts()-1;
- if (!this->computePtAlongBisector(lastRing.index(cur),
- lastRing.bisector(cur),
- lastRing.origEdgeID(cur),
- depth, &newPt)) {
- this->terminate(lastRing);
- return true;
- }
- bool dupPrev = duplicate_pt(newPt, fCandidateVerts.lastPoint());
- bool dupNext = duplicate_pt(newPt, fCandidateVerts.firstPoint());
-
- if (!dupPrev && !dupNext) {
- dst[cur] = fCandidateVerts.addNewPt(newPt,
- lastRing.index(cur), lastRing.origEdgeID(cur),
- !this->movable(lastRing.index(cur)));
- } else if (dupPrev && !dupNext) {
- dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur));
- } else if (!dupPrev && dupNext) {
- dst[cur] = fCandidateVerts.fuseWithNext();
- } else {
- bool dupPrevVsNext = duplicate_pt(fCandidateVerts.firstPoint(), fCandidateVerts.lastPoint());
-
- if (!dupPrevVsNext) {
- dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur));
- } else {
- const int fused = fCandidateVerts.fuseWithBoth();
- dst[cur] = fused;
- const int targetIdx = dst[cur - 1];
- for (int i = cur - 1; i >= 0 && dst[i] == targetIdx; i--) {
- dst[i] = fused;
- }
- }
- }
-
- // Fold the new ring's points into the global pool
- for (int i = 0; i < fCandidateVerts.numPts(); ++i) {
- int newIdx;
- if (fCandidateVerts.needsToBeNew(i) || forceNew) {
- // if the originating index is still valid then this point wasn't
- // fused (and is thus movable)
- SkScalar coverage = compute_coverage(depth, initialDepth, initialCoverage,
- targetDepth, targetCoverage);
- newIdx = this->addPt(fCandidateVerts.point(i), depth, coverage,
- fCandidateVerts.originatingIdx(i) != -1, kSharp_CurveState);
- } else {
- SkASSERT(fCandidateVerts.originatingIdx(i) != -1);
- this->updatePt(fCandidateVerts.originatingIdx(i), fCandidateVerts.point(i), depth,
- targetCoverage);
- newIdx = fCandidateVerts.originatingIdx(i);
- }
-
- nextRing->addIdx(newIdx, fCandidateVerts.origEdge(i));
- }
-
- // 'dst' currently has indices into the ring. Remap these to be indices
- // into the global pool since the triangulation operates in that space.
- for (int i = 0; i < dst.count(); ++i) {
- dst[i] = nextRing->index(dst[i]);
- }
-
- for (int i = 0; i < lastRing.numPts(); ++i) {
- int next = (i + 1) % lastRing.numPts();
-
- this->addTri(lastRing.index(i), lastRing.index(next), dst[next]);
- this->addTri(lastRing.index(i), dst[next], dst[i]);
- }
-
- if (done && fStyle != SkStrokeRec::kStroke_Style) {
- // fill or stroke-and-fill
- this->fanRing(*nextRing);
- }
-
- if (nextRing->numPts() < 3) {
- done = true;
- }
- return done;
-}
-
-void GrAAConvexTessellator::validate() const {
- SkASSERT(fPts.count() == fMovable.count());
- SkASSERT(fPts.count() == fCoverages.count());
- SkASSERT(fPts.count() == fCurveState.count());
- SkASSERT(0 == (fIndices.count() % 3));
- SkASSERT(!fBisectors.count() || fBisectors.count() == fNorms.count());
-}
-
-//////////////////////////////////////////////////////////////////////////////
-void GrAAConvexTessellator::Ring::init(const GrAAConvexTessellator& tess) {
- this->computeNormals(tess);
- this->computeBisectors(tess);
-}
-
-void GrAAConvexTessellator::Ring::init(const SkTDArray<SkVector>& norms,
- const SkTDArray<SkVector>& bisectors) {
- for (int i = 0; i < fPts.count(); ++i) {
- fPts[i].fNorm = norms[i];
- fPts[i].fBisector = bisectors[i];
- }
-}
-
-// Compute the outward facing normal at each vertex.
-void GrAAConvexTessellator::Ring::computeNormals(const GrAAConvexTessellator& tess) {
- for (int cur = 0; cur < fPts.count(); ++cur) {
- int next = (cur + 1) % fPts.count();
-
- fPts[cur].fNorm = tess.point(fPts[next].fIndex) - tess.point(fPts[cur].fIndex);
- SkPoint::Normalize(&fPts[cur].fNorm);
- fPts[cur].fNorm = SkPointPriv::MakeOrthog(fPts[cur].fNorm, tess.side());
- }
-}
-
-void GrAAConvexTessellator::Ring::computeBisectors(const GrAAConvexTessellator& tess) {
- int prev = fPts.count() - 1;
- for (int cur = 0; cur < fPts.count(); prev = cur, ++cur) {
- fPts[cur].fBisector = fPts[cur].fNorm + fPts[prev].fNorm;
- if (!fPts[cur].fBisector.normalize()) {
- fPts[cur].fBisector =
- SkPointPriv::MakeOrthog(fPts[cur].fNorm, (SkPointPriv::Side)-tess.side()) +
- SkPointPriv::MakeOrthog(fPts[prev].fNorm, tess.side());
- SkAssertResult(fPts[cur].fBisector.normalize());
- } else {
- fPts[cur].fBisector.negate(); // make the bisector face in
- }
- }
-}
-
-//////////////////////////////////////////////////////////////////////////////
-#ifdef SK_DEBUG
-// Is this ring convex?
-bool GrAAConvexTessellator::Ring::isConvex(const GrAAConvexTessellator& tess) const {
- if (fPts.count() < 3) {
- return true;
- }
-
- SkPoint prev = tess.point(fPts[0].fIndex) - tess.point(fPts.top().fIndex);
- SkPoint cur = tess.point(fPts[1].fIndex) - tess.point(fPts[0].fIndex);
- SkScalar minDot = prev.fX * cur.fY - prev.fY * cur.fX;
- SkScalar maxDot = minDot;
-
- prev = cur;
- for (int i = 1; i < fPts.count(); ++i) {
- int next = (i + 1) % fPts.count();
-
- cur = tess.point(fPts[next].fIndex) - tess.point(fPts[i].fIndex);
- SkScalar dot = prev.fX * cur.fY - prev.fY * cur.fX;
-
- minDot = std::min(minDot, dot);
- maxDot = std::max(maxDot, dot);
-
- prev = cur;
- }
-
- if (SkScalarNearlyEqual(maxDot, 0.0f, 0.005f)) {
- maxDot = 0;
- }
- if (SkScalarNearlyEqual(minDot, 0.0f, 0.005f)) {
- minDot = 0;
- }
- return (maxDot >= 0.0f) == (minDot >= 0.0f);
-}
-
-#endif
-
-void GrAAConvexTessellator::lineTo(const SkPoint& p, CurveState curve) {
- if (this->numPts() > 0 && duplicate_pt(p, this->lastPoint())) {
- return;
- }
-
- if (this->numPts() >= 2 &&
- points_are_colinear_and_b_is_middle(fPts[fPts.count() - 2], fPts.top(), p,
- &fAccumLinearError)) {
- // The old last point is on the line from the second to last to the new point
- this->popLastPt();
- // double-check that the new last point is not a duplicate of the new point. In an ideal
- // world this wouldn't be necessary (since it's only possible for non-convex paths), but
- // floating point precision issues mean it can actually happen on paths that were
- // determined to be convex.
- if (duplicate_pt(p, this->lastPoint())) {
- return;
- }
- } else {
- fAccumLinearError = 0.f;
- }
- SkScalar initialRingCoverage = (SkStrokeRec::kFill_Style == fStyle) ? 0.5f : 1.0f;
- this->addPt(p, 0.0f, initialRingCoverage, false, curve);
-}
-
-void GrAAConvexTessellator::lineTo(const SkMatrix& m, const SkPoint& p, CurveState curve) {
- this->lineTo(m.mapXY(p.fX, p.fY), curve);
-}
-
-void GrAAConvexTessellator::quadTo(const SkPoint pts[3]) {
- 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 - 1; i++) {
- this->lineTo(fPointBuffer[i], kCurve_CurveState);
- }
- this->lineTo(fPointBuffer[count - 1], kIndeterminate_CurveState);
-}
-
-void GrAAConvexTessellator::quadTo(const SkMatrix& m, const SkPoint srcPts[3]) {
- SkPoint pts[3];
- m.mapPoints(pts, srcPts, 3);
- this->quadTo(pts);
-}
-
-void GrAAConvexTessellator::cubicTo(const SkMatrix& m, const SkPoint srcPts[4]) {
- SkPoint pts[4];
- m.mapPoints(pts, srcPts, 4);
- 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 - 1; i++) {
- this->lineTo(fPointBuffer[i], kCurve_CurveState);
- }
- this->lineTo(fPointBuffer[count - 1], kIndeterminate_CurveState);
-}
-
-// include down here to avoid compilation errors caused by "-" overload in SkGeometry.h
-#include "src/core/SkGeometry.h"
-
-void GrAAConvexTessellator::conicTo(const SkMatrix& m, const SkPoint srcPts[3], SkScalar w) {
- SkPoint pts[3];
- m.mapPoints(pts, srcPts, 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->quadTo(quadPts);
- lastPoint = quadPts[2];
- quads += 2;
- }
-}
-
-//////////////////////////////////////////////////////////////////////////////
-#if GR_AA_CONVEX_TESSELLATOR_VIZ
-static const SkScalar kPointRadius = 0.02f;
-static const SkScalar kArrowStrokeWidth = 0.0f;
-static const SkScalar kArrowLength = 0.2f;
-static const SkScalar kEdgeTextSize = 0.1f;
-static const SkScalar kPointTextSize = 0.02f;
-
-static void draw_point(SkCanvas* canvas, const SkPoint& p, SkScalar paramValue, bool stroke) {
- SkPaint paint;
- SkASSERT(paramValue <= 1.0f);
- int gs = int(255*paramValue);
- paint.setARGB(255, gs, gs, gs);
-
- canvas->drawCircle(p.fX, p.fY, kPointRadius, paint);
-
- if (stroke) {
- SkPaint stroke;
- stroke.setColor(SK_ColorYELLOW);
- stroke.setStyle(SkPaint::kStroke_Style);
- stroke.setStrokeWidth(kPointRadius/3.0f);
- canvas->drawCircle(p.fX, p.fY, kPointRadius, stroke);
- }
-}
-
-static void draw_line(SkCanvas* canvas, const SkPoint& p0, const SkPoint& p1, SkColor color) {
- SkPaint p;
- p.setColor(color);
-
- canvas->drawLine(p0.fX, p0.fY, p1.fX, p1.fY, p);
-}
-
-static void draw_arrow(SkCanvas*canvas, const SkPoint& p, const SkPoint &n,
- SkScalar len, SkColor color) {
- SkPaint paint;
- paint.setColor(color);
- paint.setStrokeWidth(kArrowStrokeWidth);
- paint.setStyle(SkPaint::kStroke_Style);
-
- canvas->drawLine(p.fX, p.fY,
- p.fX + len * n.fX, p.fY + len * n.fY,
- paint);
-}
-
-void GrAAConvexTessellator::Ring::draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const {
- SkPaint paint;
- paint.setTextSize(kEdgeTextSize);
-
- for (int cur = 0; cur < fPts.count(); ++cur) {
- int next = (cur + 1) % fPts.count();
-
- draw_line(canvas,
- tess.point(fPts[cur].fIndex),
- tess.point(fPts[next].fIndex),
- SK_ColorGREEN);
-
- SkPoint mid = tess.point(fPts[cur].fIndex) + tess.point(fPts[next].fIndex);
- mid.scale(0.5f);
-
- if (fPts.count()) {
- draw_arrow(canvas, mid, fPts[cur].fNorm, kArrowLength, SK_ColorRED);
- mid.fX += (kArrowLength/2) * fPts[cur].fNorm.fX;
- mid.fY += (kArrowLength/2) * fPts[cur].fNorm.fY;
- }
-
- SkString num;
- num.printf("%d", this->origEdgeID(cur));
- canvas->drawString(num, mid.fX, mid.fY, paint);
-
- if (fPts.count()) {
- draw_arrow(canvas, tess.point(fPts[cur].fIndex), fPts[cur].fBisector,
- kArrowLength, SK_ColorBLUE);
- }
- }
-}
-
-void GrAAConvexTessellator::draw(SkCanvas* canvas) const {
- for (int i = 0; i < fIndices.count(); i += 3) {
- SkASSERT(fIndices[i] < this->numPts()) ;
- SkASSERT(fIndices[i+1] < this->numPts()) ;
- SkASSERT(fIndices[i+2] < this->numPts()) ;
-
- draw_line(canvas,
- this->point(this->fIndices[i]), this->point(this->fIndices[i+1]),
- SK_ColorBLACK);
- draw_line(canvas,
- this->point(this->fIndices[i+1]), this->point(this->fIndices[i+2]),
- SK_ColorBLACK);
- draw_line(canvas,
- this->point(this->fIndices[i+2]), this->point(this->fIndices[i]),
- SK_ColorBLACK);
- }
-
- fInitialRing.draw(canvas, *this);
- for (int i = 0; i < fRings.count(); ++i) {
- fRings[i]->draw(canvas, *this);
- }
-
- for (int i = 0; i < this->numPts(); ++i) {
- draw_point(canvas,
- this->point(i), 0.5f + (this->depth(i)/(2 * kAntialiasingRadius)),
- !this->movable(i));
-
- SkPaint paint;
- paint.setTextSize(kPointTextSize);
- if (this->depth(i) <= -kAntialiasingRadius) {
- paint.setColor(SK_ColorWHITE);
- }
-
- SkString num;
- num.printf("%d", i);
- canvas->drawString(num,
- this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f),
- paint);
- }
-}
-
-#endif
diff --git a/src/gpu/ops/GrAAConvexTessellator.h b/src/gpu/ops/GrAAConvexTessellator.h
deleted file mode 100644
index 5cf113d..0000000
--- a/src/gpu/ops/GrAAConvexTessellator.h
+++ /dev/null
@@ -1,296 +0,0 @@
-/*
- * Copyright 2015 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#ifndef GrAAConvexTessellator_DEFINED
-#define GrAAConvexTessellator_DEFINED
-
-#include "include/core/SkColor.h"
-#include "include/core/SkPaint.h"
-#include "include/core/SkScalar.h"
-#include "include/core/SkStrokeRec.h"
-#include "include/private/SkTDArray.h"
-#include "src/core/SkPointPriv.h"
-
-class SkCanvas;
-class SkMatrix;
-class SkPath;
-
-//#define GR_AA_CONVEX_TESSELLATOR_VIZ 1
-
-// device space distance which we inset / outset points in order to create the soft antialiased edge
-static const SkScalar kAntialiasingRadius = 0.5f;
-
-class GrAAConvexTessellator;
-
-// The AAConvexTessellator holds the global pool of points and the triangulation
-// that connects them. It also drives the tessellation process.
-// The outward facing normals of the original polygon are stored (in 'fNorms') to service
-// computeDepthFromEdge requests.
-class GrAAConvexTessellator {
-public:
- GrAAConvexTessellator(SkStrokeRec::Style style = SkStrokeRec::kFill_Style,
- SkScalar strokeWidth = -1.0f,
- SkPaint::Join join = SkPaint::Join::kBevel_Join,
- SkScalar miterLimit = 0.0f)
- : fSide(SkPointPriv::kOn_Side)
- , fStrokeWidth(strokeWidth)
- , fStyle(style)
- , fJoin(join)
- , fMiterLimit(miterLimit) {
- }
-
- SkPointPriv::Side side() const { return fSide; }
-
- bool tessellate(const SkMatrix& m, const SkPath& path);
-
- // The next five should only be called after tessellate to extract the result
- int numPts() const { return fPts.count(); }
- int numIndices() const { return fIndices.count(); }
-
- const SkPoint& lastPoint() const { return fPts.top(); }
- const SkPoint& point(int index) const { return fPts[index]; }
- int index(int index) const { return fIndices[index]; }
- SkScalar coverage(int index) const { return fCoverages[index]; }
-
-#if GR_AA_CONVEX_TESSELLATOR_VIZ
- void draw(SkCanvas* canvas) const;
-#endif
-
- // The tessellator can be reused for multiple paths by rewinding in between
- void rewind();
-
-private:
- // CandidateVerts holds the vertices for the next ring while they are
- // being generated. Its main function is to de-dup the points.
- class CandidateVerts {
- public:
- void setReserve(int numPts) { fPts.setReserve(numPts); }
- void rewind() { fPts.rewind(); }
-
- int numPts() const { return fPts.count(); }
-
- const SkPoint& lastPoint() const { return fPts.top().fPt; }
- const SkPoint& firstPoint() const { return fPts[0].fPt; }
- const SkPoint& point(int index) const { return fPts[index].fPt; }
-
- int originatingIdx(int index) const { return fPts[index].fOriginatingIdx; }
- int origEdge(int index) const { return fPts[index].fOrigEdgeId; }
- bool needsToBeNew(int index) const { return fPts[index].fNeedsToBeNew; }
-
- int addNewPt(const SkPoint& newPt, int originatingIdx, int origEdge, bool needsToBeNew) {
- struct PointData* pt = fPts.push();
- pt->fPt = newPt;
- pt->fOrigEdgeId = origEdge;
- pt->fOriginatingIdx = originatingIdx;
- pt->fNeedsToBeNew = needsToBeNew;
- return fPts.count() - 1;
- }
-
- int fuseWithPrior(int origEdgeId) {
- fPts.top().fOrigEdgeId = origEdgeId;
- fPts.top().fOriginatingIdx = -1;
- fPts.top().fNeedsToBeNew = true;
- return fPts.count() - 1;
- }
-
- int fuseWithNext() {
- fPts[0].fOriginatingIdx = -1;
- fPts[0].fNeedsToBeNew = true;
- return 0;
- }
-
- int fuseWithBoth() {
- if (fPts.count() > 1) {
- fPts.pop();
- }
-
- fPts[0].fOriginatingIdx = -1;
- fPts[0].fNeedsToBeNew = true;
- return 0;
- }
-
- private:
- struct PointData {
- SkPoint fPt;
- int fOriginatingIdx;
- int fOrigEdgeId;
- bool fNeedsToBeNew;
- };
-
- SkTDArray<struct PointData> fPts;
- };
-
- // The Ring holds a set of indices into the global pool that together define
- // a single polygon inset.
- class Ring {
- public:
- void setReserve(int numPts) { fPts.setReserve(numPts); }
- void rewind() { fPts.rewind(); }
-
- int numPts() const { return fPts.count(); }
-
- void addIdx(int index, int origEdgeId) {
- struct PointData* pt = fPts.push();
- pt->fIndex = index;
- pt->fOrigEdgeId = origEdgeId;
- }
-
- // Upgrade this ring so that it can behave like an originating ring
- void makeOriginalRing() {
- for (int i = 0; i < fPts.count(); ++i) {
- fPts[i].fOrigEdgeId = fPts[i].fIndex;
- }
- }
-
- // init should be called after all the indices have been added (via addIdx)
- void init(const GrAAConvexTessellator& tess);
- void init(const SkTDArray<SkVector>& norms, const SkTDArray<SkVector>& bisectors);
-
- const SkPoint& norm(int index) const { return fPts[index].fNorm; }
- const SkPoint& bisector(int index) const { return fPts[index].fBisector; }
- int index(int index) const { return fPts[index].fIndex; }
- int origEdgeID(int index) const { return fPts[index].fOrigEdgeId; }
- void setOrigEdgeId(int index, int id) { fPts[index].fOrigEdgeId = id; }
-
- #if GR_AA_CONVEX_TESSELLATOR_VIZ
- void draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const;
- #endif
-
- private:
- void computeNormals(const GrAAConvexTessellator& result);
- void computeBisectors(const GrAAConvexTessellator& tess);
-
- SkDEBUGCODE(bool isConvex(const GrAAConvexTessellator& tess) const;)
-
- struct PointData {
- SkPoint fNorm;
- SkPoint fBisector;
- int fIndex;
- int fOrigEdgeId;
- };
-
- SkTDArray<PointData> fPts;
- };
-
- // Represents whether a given point is within a curve. A point is inside a curve only if it is
- // an interior point within a quad, cubic, or conic, or if it is the endpoint of a quad, cubic,
- // or conic with another curve meeting it at (more or less) the same angle.
- enum CurveState {
- // point is a sharp vertex
- kSharp_CurveState,
- // endpoint of a curve with the other side's curvature not yet determined
- kIndeterminate_CurveState,
- // point is in the interior of a curve
- kCurve_CurveState
- };
-
- bool movable(int index) const { return fMovable[index]; }
-
- // Movable points are those that can be slid along their bisector.
- // Basically, a point is immovable if it is part of the original
- // polygon or it results from the fusing of two bisectors.
- int addPt(const SkPoint& pt, SkScalar depth, SkScalar coverage, bool movable, CurveState curve);
- void popLastPt();
- void popFirstPtShuffle();
-
- void updatePt(int index, const SkPoint& pt, SkScalar depth, SkScalar coverage);
-
- void addTri(int i0, int i1, int i2);
-
- void reservePts(int count) {
- fPts.setReserve(count);
- fCoverages.setReserve(count);
- fMovable.setReserve(count);
- }
-
- SkScalar computeDepthFromEdge(int edgeIdx, const SkPoint& p) const;
-
- bool computePtAlongBisector(int startIdx, const SkPoint& bisector,
- int edgeIdx, SkScalar desiredDepth,
- SkPoint* result) const;
-
- void lineTo(const SkPoint& p, CurveState curve);
-
- void lineTo(const SkMatrix& m, const SkPoint& p, CurveState curve);
-
- void quadTo(const SkPoint pts[3]);
-
- void quadTo(const SkMatrix& m, const SkPoint pts[3]);
-
- void cubicTo(const SkMatrix& m, const SkPoint pts[4]);
-
- void conicTo(const SkMatrix& m, const SkPoint pts[3], SkScalar w);
-
- void terminate(const Ring& lastRing);
-
- // return false on failure/degenerate path
- bool extractFromPath(const SkMatrix& m, const SkPath& path);
- void computeBisectors();
- void computeNormals();
-
- void fanRing(const Ring& ring);
-
- Ring* getNextRing(Ring* lastRing);
-
- void createOuterRing(const Ring& previousRing, SkScalar outset, SkScalar coverage,
- Ring* nextRing);
-
- bool createInsetRings(Ring& previousRing, SkScalar initialDepth, SkScalar initialCoverage,
- SkScalar targetDepth, SkScalar targetCoverage, Ring** finalRing);
-
- bool createInsetRing(const Ring& lastRing, Ring* nextRing,
- SkScalar initialDepth, SkScalar initialCoverage, SkScalar targetDepth,
- SkScalar targetCoverage, bool forceNew);
-
- void validate() const;
-
- // fPts, fCoverages, fMovable & fCurveState should always have the same # of elements
- SkTDArray<SkPoint> fPts;
- SkTDArray<SkScalar> fCoverages;
- // movable points are those that can be slid further along their bisector
- SkTDArray<bool> fMovable;
- // Tracks whether a given point is interior to a curve. Such points are
- // assumed to have shallow curvature.
- SkTDArray<CurveState> fCurveState;
-
- // The outward facing normals for the original polygon
- SkTDArray<SkVector> fNorms;
- // The inward facing bisector at each point in the original polygon. Only
- // needed for exterior ring creation and then handed off to the initial ring.
- SkTDArray<SkVector> fBisectors;
-
- SkPointPriv::Side fSide; // winding of the original polygon
-
- // The triangulation of the points
- SkTDArray<int> fIndices;
-
- Ring fInitialRing;
-#if GR_AA_CONVEX_TESSELLATOR_VIZ
- // When visualizing save all the rings
- SkTDArray<Ring*> fRings;
-#else
- Ring fRings[2];
-#endif
- CandidateVerts fCandidateVerts;
-
- // the stroke width is only used for stroke or stroke-and-fill styles
- SkScalar fStrokeWidth;
- SkStrokeRec::Style fStyle;
-
- SkPaint::Join fJoin;
-
- SkScalar fMiterLimit;
-
- // accumulated error when removing near colinear points to prevent an
- // overly greedy simplification
- SkScalar fAccumLinearError;
-
- SkTDArray<SkPoint> fPointBuffer;
-};
-
-
-#endif
diff --git a/src/gpu/ops/GrAALinearizingConvexPathRenderer.cpp b/src/gpu/ops/GrAALinearizingConvexPathRenderer.cpp
index e8b46e3..2c51330 100644
--- a/src/gpu/ops/GrAALinearizingConvexPathRenderer.cpp
+++ b/src/gpu/ops/GrAALinearizingConvexPathRenderer.cpp
@@ -21,9 +21,9 @@
#include "src/gpu/GrProgramInfo.h"
#include "src/gpu/GrStyle.h"
#include "src/gpu/GrVertexWriter.h"
+#include "src/gpu/geometry/GrAAConvexTessellator.h"
#include "src/gpu/geometry/GrPathUtils.h"
#include "src/gpu/geometry/GrStyledShape.h"
-#include "src/gpu/ops/GrAAConvexTessellator.h"
#include "src/gpu/ops/GrMeshDrawOp.h"
#include "src/gpu/ops/GrSimpleMeshDrawOpHelperWithStencil.h"
#include "src/gpu/v1/SurfaceDrawContext_v1.h"
diff --git a/src/gpu/ops/GrTriangulatingPathRenderer.cpp b/src/gpu/ops/GrTriangulatingPathRenderer.cpp
index 17d6967..4003f29 100644
--- a/src/gpu/ops/GrTriangulatingPathRenderer.cpp
+++ b/src/gpu/ops/GrTriangulatingPathRenderer.cpp
@@ -9,7 +9,6 @@
#include "include/private/SkIDChangeListener.h"
#include "src/core/SkGeometry.h"
-#include "src/gpu/GrAATriangulator.h"
#include "src/gpu/GrAuditTrail.h"
#include "src/gpu/GrCaps.h"
#include "src/gpu/GrDefaultGeoProcFactory.h"
@@ -23,9 +22,10 @@
#include "src/gpu/GrSimpleMesh.h"
#include "src/gpu/GrStyle.h"
#include "src/gpu/GrThreadSafeCache.h"
-#include "src/gpu/GrTriangulator.h"
+#include "src/gpu/geometry/GrAATriangulator.h"
#include "src/gpu/geometry/GrPathUtils.h"
#include "src/gpu/geometry/GrStyledShape.h"
+#include "src/gpu/geometry/GrTriangulator.h"
#include "src/gpu/ops/GrMeshDrawOp.h"
#include "src/gpu/ops/GrSimpleMeshDrawOpHelperWithStencil.h"
#include "src/gpu/v1/SurfaceDrawContext_v1.h"