blob: 9e1606f3f0c4fbd52ecffd821ac03ace8d1d8370 [file] [log] [blame]
/*
* Copyright 2020 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#ifndef skgpu_tessellate_StrokeIterator_DEFINED
#define skgpu_tessellate_StrokeIterator_DEFINED
#include "include/core/SkMatrix.h"
#include "include/core/SkPaint.h"
#include "include/core/SkPathTypes.h"
#include "include/core/SkPoint.h"
#include "include/core/SkStrokeRec.h"
#include "include/private/base/SkAssert.h"
#include "src/core/SkPathPriv.h"
#include <array>
class SkPath;
namespace skgpu::tess {
// This class iterates over the stroke geometry defined by a path and stroke. It automatically
// converts closes and square caps to lines, and round caps to circles so the user doesn't have to
// worry about it. At each location it provides a verb and "prevVerb" so there is context about the
// preceding join. Usage:
//
// StrokeIterator iter(path, stroke);
// while (iter.next()) { // Call next() first.
// iter.verb();
// iter.pts();
// iter.w();
// iter.prevVerb();
// iter.prevPts();
// }
//
class StrokeIterator {
public:
StrokeIterator(const SkPath& path, const SkStrokeRec* stroke, const SkMatrix* viewMatrix)
: fViewMatrix(viewMatrix), fStroke(stroke) {
SkPathPriv::Iterate it(path);
fIter = it.begin();
fEnd = it.end();
}
enum class Verb {
// Verbs that describe stroke geometry.
kLine = (int)SkPathVerb::kLine,
kQuad = (int)SkPathVerb::kQuad,
kConic = (int)SkPathVerb::kConic,
kCubic = (int)SkPathVerb::kCubic,
kCircle, // A stroke-width circle drawn as a 180-degree point stroke.
// Helper verbs that notify callers to update their own iteration state.
kMoveWithinContour,
kContourFinished
};
constexpr static bool IsVerbGeometric(Verb verb) { return verb < Verb::kMoveWithinContour; }
// Must be called first. Loads the next pair of "prev" and "current" stroke. Returns false if
// iteration is complete.
bool next() {
if (fQueueCount) {
SkASSERT(fQueueCount >= 2);
this->popFront();
if (fQueueCount >= 2) {
return true;
}
SkASSERT(fQueueCount == 1);
if (this->atVerb(0) == Verb::kContourFinished) {
// Don't let "kContourFinished" be prevVerb at the start of the next contour.
fQueueCount = 0;
}
}
for (; fIter != fEnd; ++fIter) {
SkASSERT(fQueueCount == 0 || fQueueCount == 1);
auto [verb, pts, w] = *fIter;
switch (verb) {
case SkPathVerb::kMove:
if (!this->finishOpenContour()) {
continue;
}
break;
case SkPathVerb::kCubic:
if (pts[3] == pts[2]) {
[[fallthrough]]; // i.e., "if (p3 == p2 && p2 == p1 && p1 == p0)"
case SkPathVerb::kConic:
case SkPathVerb::kQuad:
if (pts[2] == pts[1]) {
[[fallthrough]]; // i.e., "if (p2 == p1 && p1 == p0)"
case SkPathVerb::kLine:
if (pts[1] == pts[0]) {
fLastDegenerateStrokePt = pts;
continue;
}}}
this->enqueue((Verb)verb, pts, w);
if (fQueueCount == 1) {
// Defer the first verb until the end when we know what it's joined to.
fFirstVerbInContour = (Verb)verb;
fFirstPtsInContour = pts;
fFirstWInContour = w;
continue;
}
break;
case SkPathVerb::kClose:
if (!fQueueCount) {
fLastDegenerateStrokePt = pts;
continue;
}
if (pts[0] != fFirstPtsInContour[0]) {
// Draw a line back to the contour's starting point.
fClosePts = {pts[0], fFirstPtsInContour[0]};
this->enqueue(Verb::kLine, fClosePts.data(), nullptr);
}
// Repeat the first verb, this time as the "current" stroke instead of the prev.
this->enqueue(fFirstVerbInContour, fFirstPtsInContour, fFirstWInContour);
this->enqueue(Verb::kContourFinished, nullptr, nullptr);
fLastDegenerateStrokePt = nullptr;
break;
}
SkASSERT(fQueueCount >= 2);
++fIter;
return true;
}
return this->finishOpenContour();
}
Verb prevVerb() const { return this->atVerb(0); }
const SkPoint* prevPts() const { return this->atPts(0); }
Verb verb() const { return this->atVerb(1); }
const SkPoint* pts() const { return this->atPts(1); }
float w() const { return this->atW(1); }
Verb firstVerbInContour() const { SkASSERT(fQueueCount > 0); return fFirstVerbInContour; }
const SkPoint* firstPtsInContour() const {
SkASSERT(fQueueCount > 0);
return fFirstPtsInContour;
}
private:
constexpr static int kQueueBufferCount = 8;
Verb atVerb(int i) const {
SkASSERT(0 <= i && i < fQueueCount);
return fVerbs[(fQueueFrontIdx + i) & (kQueueBufferCount - 1)];
}
Verb backVerb() const {
return this->atVerb(fQueueCount - 1);
}
const SkPoint* atPts(int i) const {
SkASSERT(0 <= i && i < fQueueCount);
return fPts[(fQueueFrontIdx + i) & (kQueueBufferCount - 1)];
}
const SkPoint* backPts() const {
return this->atPts(fQueueCount - 1);
}
float atW(int i) const {
SkASSERT(0 <= i && i < fQueueCount);
const float* w = fW[(fQueueFrontIdx + i) & (kQueueBufferCount - 1)];
SkASSERT(w);
return *w;
}
void enqueue(Verb verb, const SkPoint* pts, const float* w) {
SkASSERT(fQueueCount < kQueueBufferCount);
int i = (fQueueFrontIdx + fQueueCount) & (kQueueBufferCount - 1);
fVerbs[i] = verb;
fPts[i] = pts;
fW[i] = w;
++fQueueCount;
}
void popFront() {
SkASSERT(fQueueCount > 0);
++fQueueFrontIdx;
--fQueueCount;
}
// Finishes the current contour without closing it. Enqueues any necessary caps as well as the
// contour's first stroke that we deferred at the beginning.
// Returns false and makes no changes if the current contour was already finished.
bool finishOpenContour() {
if (fQueueCount) {
SkASSERT(this->backVerb() == Verb::kLine || this->backVerb() == Verb::kQuad ||
this->backVerb() == Verb::kConic || this->backVerb() == Verb::kCubic);
switch (fStroke->getCap()) {
case SkPaint::kButt_Cap:
// There are no caps, but inject a "move" so the first stroke doesn't get joined
// with the end of the contour when it's processed.
this->enqueue(Verb::kMoveWithinContour, fFirstPtsInContour, fFirstWInContour);
break;
case SkPaint::kRound_Cap: {
// The "kCircle" verb serves as our barrier to prevent the first stroke from
// getting joined with the end of the contour. We just need to make sure that
// the first point of the contour goes last.
int backIdx = SkPathPriv::PtsInIter((unsigned)this->backVerb()) - 1;
this->enqueue(Verb::kCircle, this->backPts() + backIdx, nullptr);
this->enqueue(Verb::kCircle, fFirstPtsInContour, fFirstWInContour);
break;
}
case SkPaint::kSquare_Cap:
this->fillSquareCapPoints(); // Fills in fEndingCapPts and fBeginningCapPts.
// Append the ending cap onto the current contour.
this->enqueue(Verb::kLine, fEndingCapPts.data(), nullptr);
// Move to the beginning cap and append it right before (and joined to) the
// first stroke (that we will add below).
this->enqueue(Verb::kMoveWithinContour, fBeginningCapPts.data(), nullptr);
this->enqueue(Verb::kLine, fBeginningCapPts.data(), nullptr);
break;
}
} else if (fLastDegenerateStrokePt) {
// fQueueCount=0 means this subpath is zero length. Generates caps on its location.
//
// "Any zero length subpath ... shall be stroked if the 'stroke-linecap' property has
// a value of round or square producing respectively a circle or a square."
//
// (https://www.w3.org/TR/SVG11/painting.html#StrokeProperties)
//
switch (fStroke->getCap()) {
case SkPaint::kButt_Cap:
// Zero-length contour with butt caps. There are no caps and no first stroke to
// generate.
return false;
case SkPaint::kRound_Cap:
this->enqueue(Verb::kCircle, fLastDegenerateStrokePt, nullptr);
// Setting the "first" stroke as the circle causes it to be added again below,
// this time as the "current" stroke.
fFirstVerbInContour = Verb::kCircle;
fFirstPtsInContour = fLastDegenerateStrokePt;
fFirstWInContour = nullptr;
break;
case SkPaint::kSquare_Cap: {
SkPoint outset;
if (!fStroke->isHairlineStyle()) {
// Implement degenerate square caps as a stroke-width square in path space.
outset = {fStroke->getWidth() * .5f, 0};
} else {
// If the stroke is hairline, draw a 1x1 device-space square instead. This
// is equivalent to using:
//
// outset = inverse(fViewMatrix).mapVector(.5, 0)
//
// And since the matrix cannot have perspective, we only need to invert the
// upper 2x2 of the viewMatrix to achieve this.
SkASSERT(!fViewMatrix->hasPerspective());
float a=fViewMatrix->getScaleX(), b=fViewMatrix->getSkewX(),
c=fViewMatrix->getSkewY(), d=fViewMatrix->getScaleY();
float det = a*d - b*c;
if (det > 0) {
// outset = inverse(|a b|) * |.5|
// |c d| | 0|
//
// == 1/det * | d -b| * |.5|
// |-c a| | 0|
//
// == | d| * .5/det
// |-c|
outset = SkVector{d, -c} * (.5f / det);
} else {
outset = {1, 0};
}
}
fEndingCapPts = {*fLastDegenerateStrokePt - outset,
*fLastDegenerateStrokePt + outset};
// Add the square first as the "prev" join.
this->enqueue(Verb::kLine, fEndingCapPts.data(), nullptr);
this->enqueue(Verb::kMoveWithinContour, fEndingCapPts.data(), nullptr);
// Setting the "first" stroke as the square causes it to be added again below,
// this time as the "current" stroke.
fFirstVerbInContour = Verb::kLine;
fFirstPtsInContour = fEndingCapPts.data();
fFirstWInContour = nullptr;
break;
}
}
} else {
// This contour had no lines, beziers, or "close" verbs. There are no caps and no first
// stroke to generate.
return false;
}
// Repeat the first verb, this time as the "current" stroke instead of the prev.
this->enqueue(fFirstVerbInContour, fFirstPtsInContour, fFirstWInContour);
this->enqueue(Verb::kContourFinished, nullptr, nullptr);
fLastDegenerateStrokePt = nullptr;
return true;
}
// We implement square caps as two extra "kLine" verbs. This method finds the endpoints for
// those lines.
void fillSquareCapPoints() {
// Find the endpoints of the cap at the end of the contour.
SkVector lastTangent;
const SkPoint* lastPts = this->backPts();
Verb lastVerb = this->backVerb();
switch (lastVerb) {
case Verb::kCubic:
lastTangent = lastPts[3] - lastPts[2];
if (!lastTangent.isZero()) {
break;
}
[[fallthrough]];
case Verb::kConic:
case Verb::kQuad:
lastTangent = lastPts[2] - lastPts[1];
if (!lastTangent.isZero()) {
break;
}
[[fallthrough]];
case Verb::kLine:
lastTangent = lastPts[1] - lastPts[0];
SkASSERT(!lastTangent.isZero());
break;
default:
SkUNREACHABLE;
}
if (!fStroke->isHairlineStyle()) {
// Extend the cap by 1/2 stroke width.
lastTangent *= (.5f * fStroke->getWidth()) / lastTangent.length();
} else {
// Extend the cap by what will be 1/2 pixel after transformation.
lastTangent *= .5f / fViewMatrix->mapVector(lastTangent.fX, lastTangent.fY).length();
}
SkPoint lastPoint = lastPts[SkPathPriv::PtsInIter((unsigned)lastVerb) - 1];
fEndingCapPts = {lastPoint, lastPoint + lastTangent};
// Find the endpoints of the cap at the beginning of the contour.
SkVector firstTangent = fFirstPtsInContour[1] - fFirstPtsInContour[0];
if (firstTangent.isZero()) {
SkASSERT(fFirstVerbInContour == Verb::kQuad || fFirstVerbInContour == Verb::kConic ||
fFirstVerbInContour == Verb::kCubic);
firstTangent = fFirstPtsInContour[2] - fFirstPtsInContour[0];
if (firstTangent.isZero()) {
SkASSERT(fFirstVerbInContour == Verb::kCubic);
firstTangent = fFirstPtsInContour[3] - fFirstPtsInContour[0];
SkASSERT(!firstTangent.isZero());
}
}
if (!fStroke->isHairlineStyle()) {
// Set the the cap back by 1/2 stroke width.
firstTangent *= (-.5f * fStroke->getWidth()) / firstTangent.length();
} else {
// Set the cap back by what will be 1/2 pixel after transformation.
firstTangent *=
-.5f / fViewMatrix->mapVector(firstTangent.fX, firstTangent.fY).length();
}
fBeginningCapPts = {fFirstPtsInContour[0] + firstTangent, fFirstPtsInContour[0]};
}
// Info and iterators from the original path.
const SkMatrix* const fViewMatrix; // For hairlines.
const SkStrokeRec* const fStroke;
SkPathPriv::RangeIter fIter;
SkPathPriv::RangeIter fEnd;
// Info for the current contour we are iterating.
Verb fFirstVerbInContour;
const SkPoint* fFirstPtsInContour;
const float* fFirstWInContour;
const SkPoint* fLastDegenerateStrokePt = nullptr;
// The queue is implemented as a roll-over array with a floating front index.
Verb fVerbs[kQueueBufferCount];
const SkPoint* fPts[kQueueBufferCount];
const float* fW[kQueueBufferCount];
int fQueueFrontIdx = 0;
int fQueueCount = 0;
// Storage space for geometry that gets defined implicitly by the path, but does not have
// actual points in memory to reference.
std::array<SkPoint, 2> fClosePts;
std::array<SkPoint, 2> fEndingCapPts;
std::array<SkPoint, 2> fBeginningCapPts;
};
} // namespace skgpu::tess
#endif // skgpu_tessellate_StrokeIterator_DEFINED