blob: 0b355beeba886738eebc4580add4921c1d47615e [file] [log] [blame]
* 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 "SkPaint.h"
#include "SkPointPriv.h"
#include "SkScalar.h"
#include "SkStrokeRec.h"
#include "SkTDArray.h"
class SkCanvas;
class SkMatrix;
class SkPath;
// 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 {
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; }
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]; }
void draw(SkCanvas* canvas) const;
// The tessellator can be reused for multiple paths by rewinding in between
void rewind();
// CandidateVerts holds the vertices for the next ring while they are
// being generated. Its main function is to de-dup the points.
class CandidateVerts {
void setReserve(int numPts) { fPts.setReserve(numPts); }
void rewind() { fPts.rewind(); }
int numPts() const { return fPts.count(); }
const SkPoint& lastPoint() const { return; }
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) { = origEdgeId; = -1; = true;
return fPts.count() - 1;
int fuseWithNext() {
fPts[0].fOriginatingIdx = -1;
fPts[0].fNeedsToBeNew = true;
return 0;
int fuseWithBoth() {
if (fPts.count() > 1) {
fPts[0].fOriginatingIdx = -1;
fPts[0].fNeedsToBeNew = true;
return 0;
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 {
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; }
void draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const;
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
// endpoint of a curve with the other side's curvature not yet determined
// point is in the interior of a curve
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) {
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, SkPoint p, CurveState curve);
void quadTo(const SkPoint pts[3]);
void quadTo(const SkMatrix& m, SkPoint pts[3]);
void cubicTo(const SkMatrix& m, SkPoint pts[4]);
void conicTo(const SkMatrix& m, 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;
// When visualizing save all the rings
SkTDArray<Ring*> fRings;
Ring fRings[2];
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;
SkTDArray<SkPoint> fPointBuffer;