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 "include/core/SkColor.h"
12#include "include/core/SkPaint.h"
13#include "include/core/SkScalar.h"
14#include "include/core/SkStrokeRec.h"
15#include "include/private/SkTDArray.h"
16#include "src/core/SkPointPriv.h"
17
18class SkCanvas;
19class SkMatrix;
20class 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
25static const SkScalar kAntialiasingRadius = 0.5f;
26
27class 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.
33class GrAAConvexTessellator {
34public:
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(SkPointPriv::kOn_Side)
40 , fStrokeWidth(strokeWidth)
41 , fStyle(style)
42 , fJoin(join)
43 , fMiterLimit(miterLimit) {
44 }
45
46 SkPointPriv::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
66private:
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, const SkPoint& p, CurveState curve);
219
220 void quadTo(const SkPoint pts[3]);
221
222 void quadTo(const SkMatrix& m, const SkPoint pts[3]);
223
224 void cubicTo(const SkMatrix& m, const SkPoint pts[4]);
225
226 void conicTo(const SkMatrix& m, const 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 void computeNormals();
234
235 void fanRing(const Ring& ring);
236
237 Ring* getNextRing(Ring* lastRing);
238
239 void createOuterRing(const Ring& previousRing, SkScalar outset, SkScalar coverage,
240 Ring* nextRing);
241
242 bool createInsetRings(Ring& previousRing, SkScalar initialDepth, SkScalar initialCoverage,
243 SkScalar targetDepth, SkScalar targetCoverage, Ring** finalRing);
244
245 bool createInsetRing(const Ring& lastRing, Ring* nextRing,
246 SkScalar initialDepth, SkScalar initialCoverage, SkScalar targetDepth,
247 SkScalar targetCoverage, bool forceNew);
248
249 void validate() const;
250
251 // fPts, fCoverages, fMovable & fCurveState should always have the same # of elements
252 SkTDArray<SkPoint> fPts;
253 SkTDArray<SkScalar> fCoverages;
254 // movable points are those that can be slid further along their bisector
255 SkTDArray<bool> fMovable;
256 // Tracks whether a given point is interior to a curve. Such points are
257 // assumed to have shallow curvature.
258 SkTDArray<CurveState> fCurveState;
259
260 // The outward facing normals for the original polygon
261 SkTDArray<SkVector> fNorms;
262 // The inward facing bisector at each point in the original polygon. Only
263 // needed for exterior ring creation and then handed off to the initial ring.
264 SkTDArray<SkVector> fBisectors;
265
266 SkPointPriv::Side fSide; // winding of the original polygon
267
268 // The triangulation of the points
269 SkTDArray<int> fIndices;
270
271 Ring fInitialRing;
272#if GR_AA_CONVEX_TESSELLATOR_VIZ
273 // When visualizing save all the rings
274 SkTDArray<Ring*> fRings;
275#else
276 Ring fRings[2];
277#endif
278 CandidateVerts fCandidateVerts;
279
280 // the stroke width is only used for stroke or stroke-and-fill styles
281 SkScalar fStrokeWidth;
282 SkStrokeRec::Style fStyle;
283
284 SkPaint::Join fJoin;
285
286 SkScalar fMiterLimit;
287
288 // accumulated error when removing near colinear points to prevent an
289 // overly greedy simplification
290 SkScalar fAccumLinearError;
291
292 SkTDArray<SkPoint> fPointBuffer;
293};
294
295
296#endif
297