Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1314)

Unified Diff: src/gpu/GrAAConvexTessellator.cpp

Issue 1084943003: Add GrAAConvexTessellator class (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Fix more warnings as errors Created 5 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/gpu/GrAAConvexTessellator.h ('k') | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/gpu/GrAAConvexTessellator.cpp
diff --git a/src/gpu/GrAAConvexTessellator.cpp b/src/gpu/GrAAConvexTessellator.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..b2269c5afe17f6aac39c7da7026fc1b23ab1913a
--- /dev/null
+++ b/src/gpu/GrAAConvexTessellator.cpp
@@ -0,0 +1,874 @@
+/*
+ * 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 "GrAAConvexTessellator.h"
+#include "SkCanvas.h"
+#include "SkPath.h"
+#include "SkPoint.h"
+#include "SkString.h"
+
+// Next steps:
+// use in AAConvexPathRenderer
+// 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 = SkScalarMul(kClose, kClose);
+
+static SkScalar intersect(const SkPoint& p0, const SkPoint& n0,
+ const SkPoint& p1, const SkPoint& n1) {
+ const SkPoint v = p1 - p0;
+
+ SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX;
+ return (v.fX * n1.fY - v.fY * n1.fX) / perpDot;
+}
+
+// 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 = p0.distanceToSqd(p1);
+ return distSq < kCloseSqd;
+}
+
+static SkScalar abs_dist_from_line(const SkPoint& p0, const SkVector& v, const SkPoint& test) {
+ SkPoint testV = test - p0;
+ SkScalar dist = testV.fX * v.fY - testV.fY * v.fX;
+ return SkScalarAbs(dist);
+}
+
+int GrAAConvexTessellator::addPt(const SkPoint& pt,
+ SkScalar depth,
+ bool movable) {
+ this->validate();
+
+ int index = fPts.count();
+ *fPts.push() = pt;
+ *fDepths.push() = depth;
+ *fMovable.push() = movable;
+
+ this->validate();
+ return index;
+}
+
+void GrAAConvexTessellator::popLastPt() {
+ this->validate();
+
+ fPts.pop();
+ fDepths.pop();
+ fMovable.pop();
+
+ this->validate();
+}
+
+void GrAAConvexTessellator::popFirstPtShuffle() {
+ this->validate();
+
+ fPts.removeShuffle(0);
+ fDepths.removeShuffle(0);
+ fMovable.removeShuffle(0);
+
+ this->validate();
+}
+
+void GrAAConvexTessellator::updatePt(int index,
+ const SkPoint& pt,
+ SkScalar depth) {
+ this->validate();
+ SkASSERT(fMovable[index]);
+
+ fPts[index] = pt;
+ fDepths[index] = depth;
+}
+
+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();
+ fDepths.rewind();
+ fMovable.rewind();
+ fIndices.rewind();
+ fNorms.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::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];
+ fBisectors[cur].normalize();
+ fBisectors[cur].negate(); // make the bisector face in
+
+ SkASSERT(SkScalarNearlyEqual(1.0f, fBisectors[cur].length()));
+ }
+}
+
+// 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) {
+ static const int kMaxNumRings = 8;
+
+ SkDEBUGCODE(fShouldCheckDepths = true;)
+
+ if (!this->extractFromPath(m, path)) {
+ return false;
+ }
+
+ this->createOuterRing();
+
+ // the bisectors are only needed for the computation of the outer ring
+ fBisectors.rewind();
+
+ Ring* lastRing = &fInitialRing;
+ int i;
+ for (i = 0; i < kMaxNumRings; ++i) {
+ Ring* nextRing = this->getNextRing(lastRing);
+
+ if (this->createInsetRing(*lastRing, nextRing)) {
+ break;
+ }
+
+ nextRing->init(*this);
+ lastRing = nextRing;
+ }
+
+ if (kMaxNumRings == i) {
+ // If we've exceeded the amount of time we want to throw at this, set
+ // the depth of all points in the final ring to 'fTargetDepth' and
+ // create a fan.
+ this->terminate(*lastRing);
+ SkDEBUGCODE(fShouldCheckDepths = false;)
+ }
+
+#ifdef SK_DEBUG
+ this->validate();
+ if (fShouldCheckDepths) {
+ SkDEBUGCODE(this->checkAllDepths();)
+ }
+#endif
+ 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);
+ SkASSERT(depth >= 0.0f);
+ 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 < fNorms.count());
+ newP = fPts[startIdx];
+ } else if (t > 0.0f) {
+ SkASSERT(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
+ t = -desiredDepth / bisector.dot(norm);
+ SkASSERT(t > 0.0f);
+ *result = bisector;
+ result->scale(t);
+ *result += newP;
+
+
+ return true;
+}
+
+bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) {
+ SkASSERT(SkPath::kLine_SegmentMask == path.getSegmentMasks());
+ SkASSERT(SkPath::kConvex_Convexity == path.getConvexity());
+
+ // 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);
+
+ fNorms.setReserve(path.countPoints());
+
+ SkScalar minCross = SK_ScalarMax, maxCross = -SK_ScalarMax;
+
+ // 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?
+ 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:
+ m.mapPoints(&pts[1], 1);
+ if (this->numPts() > 0 && duplicate_pt(pts[1], this->lastPoint())) {
+ continue;
+ }
+
+ SkASSERT(fPts.count() <= 1 || fPts.count() == fNorms.count()+1);
+ if (this->numPts() >= 2 &&
+ abs_dist_from_line(fPts.top(), fNorms.top(), pts[1]) < kClose) {
+ // The old last point is on the line from the second to last to the new point
+ this->popLastPt();
+ fNorms.pop();
+ }
+
+ this->addPt(pts[1], 0.0f, false);
+ if (this->numPts() > 1) {
+ *fNorms.push() = fPts.top() - fPts[fPts.count()-2];
+ SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top());
+ SkASSERT(len > 0.0f);
+ SkASSERT(SkScalarNearlyEqual(1.0f, fNorms.top().length()));
+ }
+
+ if (this->numPts() >= 3) {
+ int cur = this->numPts()-1;
+ SkScalar cross = SkPoint::CrossProduct(fNorms[cur-1], fNorms[cur-2]);
+ maxCross = SkTMax(maxCross, cross);
+ minCross = SkTMin(minCross, cross);
+ }
+ break;
+ case SkPath::kQuad_Verb:
+ case SkPath::kConic_Verb:
+ case SkPath::kCubic_Verb:
+ SkASSERT(false);
+ break;
+ case SkPath::kMove_Verb:
+ case SkPath::kClose_Verb:
+ case SkPath::kDone_Verb:
+ break;
+ }
+ }
+
+ if (this->numPts() < 3) {
+ 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();
+ fNorms.pop();
+ }
+
+ SkASSERT(fPts.count() == fNorms.count()+1);
+ if (this->numPts() >= 3 &&
+ abs_dist_from_line(fPts.top(), fNorms.top(), fPts[0]) < kClose) {
+ // The last point is on the line from the second to last to the first point.
+ this->popLastPt();
+ fNorms.pop();
+ }
+
+ if (this->numPts() < 3) {
+ return false;
+ }
+
+ *fNorms.push() = fPts[0] - fPts.top();
+ SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top());
+ SkASSERT(len > 0.0f);
+ SkASSERT(fPts.count() == fNorms.count());
+
+ if (abs_dist_from_line(fPts[0], fNorms.top(), fPts[1]) < kClose) {
+ // The first point is on the line from the last to the second.
+ this->popFirstPtShuffle();
+ fNorms.removeShuffle(0);
+ fNorms[0] = fPts[1] - fPts[0];
+ SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms[0]);
+ SkASSERT(len > 0.0f);
+ SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[0].length()));
+ }
+
+ if (this->numPts() < 3) {
+ return false;
+ }
+
+ // Check the cross produce of the final trio
+ SkScalar cross = SkPoint::CrossProduct(fNorms[0], fNorms.top());
+ maxCross = SkTMax(maxCross, cross);
+ minCross = SkTMin(minCross, cross);
+
+ if (maxCross > 0.0f) {
+ SkASSERT(minCross >= 0.0f);
+ fSide = SkPoint::kRight_Side;
+ } else {
+ SkASSERT(minCross <= 0.0f);
+ fSide = SkPoint::kLeft_Side;
+ }
+
+ // Make all the normals face outwards rather than along the edge
+ for (int cur = 0; cur < fNorms.count(); ++cur) {
+ fNorms[cur].setOrthog(fNorms[cur], fSide);
+ SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length()));
+ }
+
+ this->computeBisectors();
+
+ 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() = SkNEW(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
+ for (int cur = 1; cur < ring.numPts()-1; ++cur) {
+ this->addTri(ring.index(0), ring.index(cur), ring.index(cur+1));
+ }
+}
+
+void GrAAConvexTessellator::createOuterRing() {
+ // For now, we're only generating one outer ring (at the start). This
+ // could be relaxed for stroking use cases.
+ SkASSERT(0 == fIndices.count());
+ SkASSERT(fPts.count() == fNorms.count());
+
+ const int numPts = fPts.count();
+
+ // For each vertex of the original polygon we add three points to the
+ // outset polygon - one extending perpendicular to each impinging edge
+ // and one along the bisector. Two triangles are added for each corner
+ // and two are added along each edge.
+ int prev = numPts - 1;
+ int lastPerpIdx = -1, firstPerpIdx = -1, newIdx0, newIdx1, newIdx2;
+ for (int cur = 0; cur < numPts; ++cur) {
+ // The perpendicular point for the last edge
+ SkPoint temp = fNorms[prev];
+ temp.scale(fTargetDepth);
+ temp += fPts[cur];
+
+ // 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)
+ newIdx0 = this->addPt(temp, -fTargetDepth, false);
+
+ // The bisector outset point
+ temp = fBisectors[cur];
+ temp.scale(-fTargetDepth); // the bisectors point in
+ temp += fPts[cur];
+
+ // For very shallow angles all the corner points could fuse
+ if (duplicate_pt(temp, this->point(newIdx0))) {
+ newIdx1 = newIdx0;
+ } else {
+ newIdx1 = this->addPt(temp, -fTargetDepth, false);
+ }
+
+ // The perpendicular point for the next edge.
+ temp = fNorms[cur];
+ temp.scale(fTargetDepth);
+ temp += fPts[cur];
+
+ // For very shallow angles all the corner points could fuse.
+ if (duplicate_pt(temp, this->point(newIdx1))) {
+ newIdx2 = newIdx1;
+ } else {
+ newIdx2 = this->addPt(temp, -fTargetDepth, false);
+ }
+
+ if (0 == cur) {
+ // Store the index of the first perpendicular point to finish up
+ firstPerpIdx = newIdx0;
+ SkASSERT(-1 == lastPerpIdx);
+ } else {
+ // The triangles for the previous edge
+ this->addTri(prev, newIdx0, cur);
+ this->addTri(prev, lastPerpIdx, newIdx0);
+ }
+
+ // The two triangles for the corner
+ this->addTri(cur, newIdx0, newIdx1);
+ this->addTri(cur, newIdx1, newIdx2);
+
+ prev = cur;
+ // Track the last perpendicular outset point so we can construct the
+ // trailing edge triangles.
+ lastPerpIdx = newIdx2;
+ }
+
+ // pick up the final edge rect
+ this->addTri(numPts-1, firstPerpIdx, 0);
+ this->addTri(numPts-1, lastPerpIdx, firstPerpIdx);
+
+ this->validate();
+}
+
+// Something went wrong in the creation of the next ring. Mark the last good
+// ring as being at the desired depth and fan it.
+void GrAAConvexTessellator::terminate(const Ring& ring) {
+ for (int i = 0; i < ring.numPts(); ++i) {
+ fDepths[ring.index(i)] = fTargetDepth;
+ }
+
+ this->fanRing(ring);
+}
+
+// return true when processing is complete
+bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing) {
+ 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 = intersect(this->point(lastRing.index(cur)), lastRing.bisector(cur),
+ this->point(lastRing.index(next)), lastRing.bisector(next));
+ SkScalar dist = -t * lastRing.norm(cur).dot(lastRing.bisector(cur));
+
+ if (minDist > dist) {
+ minDist = dist;
+ minT = t;
+ minEdgeIdx = cur;
+ }
+ }
+
+ SkPoint newPt = lastRing.bisector(minEdgeIdx);
+ newPt.scale(minT);
+ newPt += this->point(lastRing.index(minEdgeIdx));
+
+ SkScalar depth = this->computeDepthFromEdge(lastRing.origEdgeID(minEdgeIdx), newPt);
+ if (depth >= fTargetDepth) {
+ // None of the bisectors intersect before reaching the desired depth.
+ // Just step them all to the desired depth
+ depth = fTargetDepth;
+ 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);
+ SkDEBUGCODE(fShouldCheckDepths = false;)
+ 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);
+ SkDEBUGCODE(fShouldCheckDepths = false;)
+ 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);
+ SkDEBUGCODE(fShouldCheckDepths = false;)
+ 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 {
+ dst[cur] = dst[cur-1] = fCandidateVerts.fuseWithBoth();
+ }
+ }
+
+ // Fold the new ring's points into the global pool
+ for (int i = 0; i < fCandidateVerts.numPts(); ++i) {
+ int newIdx;
+ if (fCandidateVerts.needsToBeNew(i)) {
+ // if the originating index is still valid then this point wasn't
+ // fused (and is thus movable)
+ newIdx = this->addPt(fCandidateVerts.point(i), depth,
+ fCandidateVerts.originatingIdx(i) != -1);
+ } else {
+ SkASSERT(fCandidateVerts.originatingIdx(i) != -1);
+ this->updatePt(fCandidateVerts.originatingIdx(i), fCandidateVerts.point(i), depth);
+ 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 cur = 0; cur < lastRing.numPts(); ++cur) {
+ int next = (cur + 1) % lastRing.numPts();
+
+ this->addTri(lastRing.index(cur), lastRing.index(next), dst[next]);
+ this->addTri(lastRing.index(cur), dst[next], dst[cur]);
+ }
+
+ if (done) {
+ this->fanRing(*nextRing);
+ }
+
+ if (nextRing->numPts() < 3) {
+ done = true;
+ }
+
+ return done;
+}
+
+void GrAAConvexTessellator::validate() const {
+ SkASSERT(fPts.count() == fDepths.count());
+ SkASSERT(fPts.count() == fMovable.count());
+ SkASSERT(0 == (fIndices.count() % 3));
+}
+
+//////////////////////////////////////////////////////////////////////////////
+void GrAAConvexTessellator::Ring::init(const GrAAConvexTessellator& tess) {
+ this->computeNormals(tess);
+ this->computeBisectors();
+ SkASSERT(this->isConvex(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);
+ SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fPts[cur].fNorm);
+ SkASSERT(len > 0.0f);
+ fPts[cur].fNorm.setOrthog(fPts[cur].fNorm, tess.side());
+
+ SkASSERT(SkScalarNearlyEqual(1.0f, fPts[cur].fNorm.length()));
+ }
+}
+
+void GrAAConvexTessellator::Ring::computeBisectors() {
+ int prev = fPts.count() - 1;
+ for (int cur = 0; cur < fPts.count(); prev = cur, ++cur) {
+ fPts[cur].fBisector = fPts[cur].fNorm + fPts[prev].fNorm;
+ fPts[cur].fBisector.normalize();
+ fPts[cur].fBisector.negate(); // make the bisector face in
+
+ SkASSERT(SkScalarNearlyEqual(1.0f, fPts[cur].fBisector.length()));
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////////
+#ifdef SK_DEBUG
+// Is this ring convex?
+bool GrAAConvexTessellator::Ring::isConvex(const GrAAConvexTessellator& tess) const {
+ if (fPts.count() < 3) {
+ return false;
+ }
+
+ 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 = SkMinScalar(minDot, dot);
+ maxDot = SkMaxScalar(maxDot, dot);
+
+ prev = cur;
+ }
+
+ return (maxDot > 0.0f) == (minDot >= 0.0f);
+}
+
+static SkScalar capsule_depth(const SkPoint& p0, const SkPoint& p1,
+ const SkPoint& test, SkPoint::Side side,
+ int* sign) {
+ *sign = -1;
+ SkPoint edge = p1 - p0;
+ SkScalar len = SkPoint::Normalize(&edge);
+
+ SkPoint testVec = test - p0;
+
+ SkScalar d0 = edge.dot(testVec);
+ if (d0 < 0.0f) {
+ return SkPoint::Distance(p0, test);
+ }
+ if (d0 > len) {
+ return SkPoint::Distance(p1, test);
+ }
+
+ SkScalar perpDist = testVec.fY * edge.fX - testVec.fX * edge.fY;
+ if (SkPoint::kRight_Side == side) {
+ perpDist = -perpDist;
+ }
+
+ if (perpDist < 0.0f) {
+ perpDist = -perpDist;
+ } else {
+ *sign = 1;
+ }
+ return perpDist;
+}
+
+SkScalar GrAAConvexTessellator::computeRealDepth(const SkPoint& p) const {
+ SkScalar minDist = SK_ScalarMax;
+ int closestSign, sign;
+
+ for (int edge = 0; edge < fNorms.count(); ++edge) {
+ SkScalar dist = capsule_depth(this->point(edge),
+ this->point((edge+1) % fNorms.count()),
+ p, fSide, &sign);
+ SkASSERT(dist >= 0.0f);
+
+ if (minDist > dist) {
+ minDist = dist;
+ closestSign = sign;
+ }
+ }
+
+ return closestSign * minDist;
+}
+
+// Verify that the incrementally computed depths are close to the actual depths.
+void GrAAConvexTessellator::checkAllDepths() const {
+ for (int cur = 0; cur < this->numPts(); ++cur) {
+ SkScalar realDepth = this->computeRealDepth(this->point(cur));
+ SkScalar computedDepth = this->depth(cur);
+ SkASSERT(SkScalarNearlyEqual(realDepth, computedDepth, 0.01f));
+ }
+}
+#endif
+
+//////////////////////////////////////////////////////////////////////////////
+#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->drawText(num.c_str(), num.size(), 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*fTargetDepth)),
+ !this->movable(i));
+
+ SkPaint paint;
+ paint.setTextSize(kPointTextSize);
+ paint.setTextAlign(SkPaint::kCenter_Align);
+ if (this->depth(i) <= -fTargetDepth) {
+ paint.setColor(SK_ColorWHITE);
+ }
+
+ SkString num;
+ num.printf("%d", i);
+ canvas->drawText(num.c_str(), num.size(),
+ this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f),
+ paint);
+ }
+}
+
+#endif
+
« no previous file with comments | « src/gpu/GrAAConvexTessellator.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698