1 /* 2 * Copyright 2015 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef GrAAConvexTessellator_DEFINED 9 #define GrAAConvexTessellator_DEFINED 10 11 #include "SkColor.h" 12 #include "SkPaint.h" 13 #include "SkPoint.h" 14 #include "SkScalar.h" 15 #include "SkStrokeRec.h" 16 #include "SkTDArray.h" 17 18 class SkCanvas; 19 class SkMatrix; 20 class SkPath; 21 22 //#define GR_AA_CONVEX_TESSELLATOR_VIZ 1 23 24 // device space distance which we inset / outset points in order to create the soft antialiased edge 25 static const SkScalar kAntialiasingRadius = 0.5f; 26 27 class GrAAConvexTessellator; 28 29 // The AAConvexTessellator holds the global pool of points and the triangulation 30 // that connects them. It also drives the tessellation process. 31 // The outward facing normals of the original polygon are stored (in 'fNorms') to service 32 // computeDepthFromEdge requests. 33 class GrAAConvexTessellator { 34 public: 35 GrAAConvexTessellator(SkStrokeRec::Style style = SkStrokeRec::kFill_Style, 36 SkScalar strokeWidth = -1.0f, 37 SkPaint::Join join = SkPaint::Join::kBevel_Join, 38 SkScalar miterLimit = 0.0f) 39 : fSide(SkPoint::kOn_Side) 40 , fStrokeWidth(strokeWidth) 41 , fStyle(style) 42 , fJoin(join) 43 , fMiterLimit(miterLimit) { 44 } 45 46 SkPoint::Side side() const { return fSide; } 47 48 bool tessellate(const SkMatrix& m, const SkPath& path); 49 50 // The next five should only be called after tessellate to extract the result 51 int numPts() const { return fPts.count(); } 52 int numIndices() const { return fIndices.count(); } 53 54 const SkPoint& lastPoint() const { return fPts.top(); } 55 const SkPoint& point(int index) const { return fPts[index]; } 56 int index(int index) const { return fIndices[index]; } 57 SkScalar coverage(int index) const { return fCoverages[index]; } 58 59 #if GR_AA_CONVEX_TESSELLATOR_VIZ 60 void draw(SkCanvas* canvas) const; 61 #endif 62 63 // The tessellator can be reused for multiple paths by rewinding in between 64 void rewind(); 65 66 private: 67 // CandidateVerts holds the vertices for the next ring while they are 68 // being generated. Its main function is to de-dup the points. 69 class CandidateVerts { 70 public: 71 void setReserve(int numPts) { fPts.setReserve(numPts); } 72 void rewind() { fPts.rewind(); } 73 74 int numPts() const { return fPts.count(); } 75 76 const SkPoint& lastPoint() const { return fPts.top().fPt; } 77 const SkPoint& firstPoint() const { return fPts[0].fPt; } 78 const SkPoint& point(int index) const { return fPts[index].fPt; } 79 80 int originatingIdx(int index) const { return fPts[index].fOriginatingIdx; } 81 int origEdge(int index) const { return fPts[index].fOrigEdgeId; } 82 bool needsToBeNew(int index) const { return fPts[index].fNeedsToBeNew; } 83 84 int addNewPt(const SkPoint& newPt, int originatingIdx, int origEdge, bool needsToBeNew) { 85 struct PointData* pt = fPts.push(); 86 pt->fPt = newPt; 87 pt->fOrigEdgeId = origEdge; 88 pt->fOriginatingIdx = originatingIdx; 89 pt->fNeedsToBeNew = needsToBeNew; 90 return fPts.count() - 1; 91 } 92 93 int fuseWithPrior(int origEdgeId) { 94 fPts.top().fOrigEdgeId = origEdgeId; 95 fPts.top().fOriginatingIdx = -1; 96 fPts.top().fNeedsToBeNew = true; 97 return fPts.count() - 1; 98 } 99 100 int fuseWithNext() { 101 fPts[0].fOriginatingIdx = -1; 102 fPts[0].fNeedsToBeNew = true; 103 return 0; 104 } 105 106 int fuseWithBoth() { 107 if (fPts.count() > 1) { 108 fPts.pop(); 109 } 110 111 fPts[0].fOriginatingIdx = -1; 112 fPts[0].fNeedsToBeNew = true; 113 return 0; 114 } 115 116 private: 117 struct PointData { 118 SkPoint fPt; 119 int fOriginatingIdx; 120 int fOrigEdgeId; 121 bool fNeedsToBeNew; 122 }; 123 124 SkTDArray<struct PointData> fPts; 125 }; 126 127 // The Ring holds a set of indices into the global pool that together define 128 // a single polygon inset. 129 class Ring { 130 public: 131 void setReserve(int numPts) { fPts.setReserve(numPts); } 132 void rewind() { fPts.rewind(); } 133 134 int numPts() const { return fPts.count(); } 135 136 void addIdx(int index, int origEdgeId) { 137 struct PointData* pt = fPts.push(); 138 pt->fIndex = index; 139 pt->fOrigEdgeId = origEdgeId; 140 } 141 142 // Upgrade this ring so that it can behave like an originating ring 143 void makeOriginalRing() { 144 for (int i = 0; i < fPts.count(); ++i) { 145 fPts[i].fOrigEdgeId = fPts[i].fIndex; 146 } 147 } 148 149 // init should be called after all the indices have been added (via addIdx) 150 void init(const GrAAConvexTessellator& tess); 151 void init(const SkTDArray<SkVector>& norms, const SkTDArray<SkVector>& bisectors); 152 153 const SkPoint& norm(int index) const { return fPts[index].fNorm; } 154 const SkPoint& bisector(int index) const { return fPts[index].fBisector; } 155 int index(int index) const { return fPts[index].fIndex; } 156 int origEdgeID(int index) const { return fPts[index].fOrigEdgeId; } 157 void setOrigEdgeId(int index, int id) { fPts[index].fOrigEdgeId = id; } 158 159 #if GR_AA_CONVEX_TESSELLATOR_VIZ 160 void draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const; 161 #endif 162 163 private: 164 void computeNormals(const GrAAConvexTessellator& result); 165 void computeBisectors(const GrAAConvexTessellator& tess); 166 167 SkDEBUGCODE(bool isConvex(const GrAAConvexTessellator& tess) const;) 168 169 struct PointData { 170 SkPoint fNorm; 171 SkPoint fBisector; 172 int fIndex; 173 int fOrigEdgeId; 174 }; 175 176 SkTDArray<PointData> fPts; 177 }; 178 179 // Represents whether a given point is within a curve. A point is inside a curve only if it is 180 // an interior point within a quad, cubic, or conic, or if it is the endpoint of a quad, cubic, 181 // or conic with another curve meeting it at (more or less) the same angle. 182 enum CurveState { 183 // point is a sharp vertex 184 kSharp_CurveState, 185 // endpoint of a curve with the other side's curvature not yet determined 186 kIndeterminate_CurveState, 187 // point is in the interior of a curve 188 kCurve_CurveState 189 }; 190 191 bool movable(int index) const { return fMovable[index]; } 192 193 // Movable points are those that can be slid along their bisector. 194 // Basically, a point is immovable if it is part of the original 195 // polygon or it results from the fusing of two bisectors. 196 int addPt(const SkPoint& pt, SkScalar depth, SkScalar coverage, bool movable, CurveState curve); 197 void popLastPt(); 198 void popFirstPtShuffle(); 199 200 void updatePt(int index, const SkPoint& pt, SkScalar depth, SkScalar coverage); 201 202 void addTri(int i0, int i1, int i2); 203 204 void reservePts(int count) { 205 fPts.setReserve(count); 206 fCoverages.setReserve(count); 207 fMovable.setReserve(count); 208 } 209 210 SkScalar computeDepthFromEdge(int edgeIdx, const SkPoint& p) const; 211 212 bool computePtAlongBisector(int startIdx, const SkPoint& bisector, 213 int edgeIdx, SkScalar desiredDepth, 214 SkPoint* result) const; 215 216 void lineTo(const SkPoint& p, CurveState curve); 217 218 void lineTo(const SkMatrix& m, SkPoint p, CurveState curve); 219 220 void quadTo(const SkPoint pts[3]); 221 222 void quadTo(const SkMatrix& m, SkPoint pts[3]); 223 224 void cubicTo(const SkMatrix& m, SkPoint pts[4]); 225 226 void conicTo(const SkMatrix& m, SkPoint pts[3], SkScalar w); 227 228 void terminate(const Ring& lastRing); 229 230 // return false on failure/degenerate path 231 bool extractFromPath(const SkMatrix& m, const SkPath& path); 232 void computeBisectors(); 233 234 void fanRing(const Ring& ring); 235 236 Ring* getNextRing(Ring* lastRing); 237 238 void createOuterRing(const Ring& previousRing, SkScalar outset, SkScalar coverage, 239 Ring* nextRing); 240 241 bool createInsetRings(Ring& previousRing, SkScalar initialDepth, SkScalar initialCoverage, 242 SkScalar targetDepth, SkScalar targetCoverage, Ring** finalRing); 243 244 bool createInsetRing(const Ring& lastRing, Ring* nextRing, 245 SkScalar initialDepth, SkScalar initialCoverage, SkScalar targetDepth, 246 SkScalar targetCoverage, bool forceNew); 247 248 void validate() const; 249 250 // fPts, fCoverages, fMovable & fCurveState should always have the same # of elements 251 SkTDArray<SkPoint> fPts; 252 SkTDArray<SkScalar> fCoverages; 253 // movable points are those that can be slid further along their bisector 254 SkTDArray<bool> fMovable; 255 // Tracks whether a given point is interior to a curve. Such points are 256 // assumed to have shallow curvature. 257 SkTDArray<CurveState> fCurveState; 258 259 // The outward facing normals for the original polygon 260 SkTDArray<SkVector> fNorms; 261 // The inward facing bisector at each point in the original polygon. Only 262 // needed for exterior ring creation and then handed off to the initial ring. 263 SkTDArray<SkVector> fBisectors; 264 265 SkPoint::Side fSide; // winding of the original polygon 266 267 // The triangulation of the points 268 SkTDArray<int> fIndices; 269 270 Ring fInitialRing; 271 #if GR_AA_CONVEX_TESSELLATOR_VIZ 272 // When visualizing save all the rings 273 SkTDArray<Ring*> fRings; 274 #else 275 Ring fRings[2]; 276 #endif 277 CandidateVerts fCandidateVerts; 278 279 // the stroke width is only used for stroke or stroke-and-fill styles 280 SkScalar fStrokeWidth; 281 SkStrokeRec::Style fStyle; 282 283 SkPaint::Join fJoin; 284 285 SkScalar fMiterLimit; 286 287 SkTDArray<SkPoint> fPointBuffer; 288 }; 289 290 291 #endif 292