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