From 84b008873b5bdf35eba9185038fb3b5580a8b9a8 Mon Sep 17 00:00:00 2001 From: robertphillips Date: Wed, 6 May 2015 05:15:57 -0700 Subject: [PATCH] Add GrAAConvexTessellator class This CL adds a GrAAConvexTessellator class. It does not connect it to the GrAAConvexPathRenderer. Review URL: https://codereview.chromium.org/1084943003 --- gyp/gpu.gypi | 2 + src/gpu/GrAAConvexTessellator.cpp | 874 ++++++++++++++++++++++++++++++++++++++ src/gpu/GrAAConvexTessellator.h | 244 +++++++++++ 3 files changed, 1120 insertions(+) create mode 100644 src/gpu/GrAAConvexTessellator.cpp create mode 100644 src/gpu/GrAAConvexTessellator.h diff --git a/gyp/gpu.gypi b/gyp/gpu.gypi index 12ae979..9415f30 100644 --- a/gyp/gpu.gypi +++ b/gyp/gpu.gypi @@ -55,6 +55,8 @@ '<(skia_src_path)/gpu/GrAAHairLinePathRenderer.h', '<(skia_src_path)/gpu/GrAAConvexPathRenderer.cpp', '<(skia_src_path)/gpu/GrAAConvexPathRenderer.h', + '<(skia_src_path)/gpu/GrAAConvexTessellator.cpp', + '<(skia_src_path)/gpu/GrAAConvexTessellator.h', '<(skia_src_path)/gpu/GrAADistanceFieldPathRenderer.cpp', '<(skia_src_path)/gpu/GrAADistanceFieldPathRenderer.h', '<(skia_src_path)/gpu/GrAARectRenderer.cpp', diff --git a/src/gpu/GrAAConvexTessellator.cpp b/src/gpu/GrAAConvexTessellator.cpp new file mode 100644 index 0000000..b2269c5 --- /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 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& norms, + const SkTDArray& 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 + diff --git a/src/gpu/GrAAConvexTessellator.h b/src/gpu/GrAAConvexTessellator.h new file mode 100644 index 0000000..c2b751e --- /dev/null +++ b/src/gpu/GrAAConvexTessellator.h @@ -0,0 +1,244 @@ +/* + * 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 "SkColor.h" +#include "SkPoint.h" +#include "SkScalar.h" +#include "SkTDArray.h" + +class SkCanvas; +class SkMatrix; +class SkPath; + +//#define GR_AA_CONVEX_TESSELLATOR_VIZ 1 + +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(SkScalar targetDepth = 0.5f) + : fSide(SkPoint::kOn_Side) + , fTargetDepth(targetDepth) { + } + + void setTargetDepth(SkScalar targetDepth) { fTargetDepth = targetDepth; } + SkScalar targetDepth() const { return fTargetDepth; } + + SkPoint::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 depth(int index) const {return fDepths[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 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; + } + + // init should be called after all the indices have been added (via addIdx) + void init(const GrAAConvexTessellator& tess); + void init(const SkTDArray& norms, const SkTDArray& 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; } + + #if GR_AA_CONVEX_TESSELLATOR_VIZ + void draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const; + #endif + + private: + void computeNormals(const GrAAConvexTessellator& result); + void computeBisectors(); + + SkDEBUGCODE(bool isConvex(const GrAAConvexTessellator& tess) const;) + + struct PointData { + SkPoint fNorm; + SkPoint fBisector; + int fIndex; + int fOrigEdgeId; + }; + + SkTDArray fPts; + }; + + 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, bool movable); + void popLastPt(); + void popFirstPtShuffle(); + + void updatePt(int index, const SkPoint& pt, SkScalar depth); + + void addTri(int i0, int i1, int i2); + + void reservePts(int count) { + fPts.setReserve(count); + fDepths.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 terminate(const Ring& lastRing); + + // return false on failure/degenerate path + bool extractFromPath(const SkMatrix& m, const SkPath& path); + void computeBisectors(); + + void fanRing(const Ring& ring); + void createOuterRing(); + + Ring* getNextRing(Ring* lastRing); + + bool createInsetRing(const Ring& lastRing, Ring* nextRing); + + void validate() const; + + +#ifdef SK_DEBUG + SkScalar computeRealDepth(const SkPoint& p) const; + void checkAllDepths() const; +#endif + + // fPts, fWeights & fMovable should always have the same # of elements + SkTDArray fPts; + SkTDArray fDepths; + // movable points are those that can be slid further along their bisector + SkTDArray fMovable; + + // The outward facing normals for the original polygon + SkTDArray 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 fBisectors; + SkPoint::Side fSide; // winding of the original polygon + + // The triangulation of the points + SkTDArray fIndices; + + Ring fInitialRing; +#if GR_AA_CONVEX_TESSELLATOR_VIZ + // When visualizing save all the rings + SkTDArray fRings; +#else + Ring fRings[2]; +#endif + CandidateVerts fCandidateVerts; + + SkScalar fTargetDepth; + + // If some goes wrong with the inset computation the tessellator will + // truncate the creation of the inset polygon. In this case the depth + // check will complain. + SkDEBUGCODE(bool fShouldCheckDepths;) +}; + + +#endif + -- 2.7.4