Line data Source code
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 0 : class GrAAConvexTessellator {
34 : public:
35 0 : 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 0 : : fSide(SkPoint::kOn_Side)
40 : , fStrokeWidth(strokeWidth)
41 : , fStyle(style)
42 : , fJoin(join)
43 0 : , fMiterLimit(miterLimit) {
44 0 : }
45 :
46 0 : 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 0 : int numPts() const { return fPts.count(); }
52 0 : int numIndices() const { return fIndices.count(); }
53 :
54 0 : const SkPoint& lastPoint() const { return fPts.top(); }
55 0 : const SkPoint& point(int index) const { return fPts[index]; }
56 0 : int index(int index) const { return fIndices[index]; }
57 0 : 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 0 : class CandidateVerts {
70 : public:
71 0 : void setReserve(int numPts) { fPts.setReserve(numPts); }
72 0 : void rewind() { fPts.rewind(); }
73 :
74 0 : int numPts() const { return fPts.count(); }
75 :
76 0 : const SkPoint& lastPoint() const { return fPts.top().fPt; }
77 0 : const SkPoint& firstPoint() const { return fPts[0].fPt; }
78 0 : const SkPoint& point(int index) const { return fPts[index].fPt; }
79 :
80 0 : int originatingIdx(int index) const { return fPts[index].fOriginatingIdx; }
81 0 : int origEdge(int index) const { return fPts[index].fOrigEdgeId; }
82 0 : bool needsToBeNew(int index) const { return fPts[index].fNeedsToBeNew; }
83 :
84 0 : int addNewPt(const SkPoint& newPt, int originatingIdx, int origEdge, bool needsToBeNew) {
85 0 : struct PointData* pt = fPts.push();
86 0 : pt->fPt = newPt;
87 0 : pt->fOrigEdgeId = origEdge;
88 0 : pt->fOriginatingIdx = originatingIdx;
89 0 : pt->fNeedsToBeNew = needsToBeNew;
90 0 : return fPts.count() - 1;
91 : }
92 :
93 0 : int fuseWithPrior(int origEdgeId) {
94 0 : fPts.top().fOrigEdgeId = origEdgeId;
95 0 : fPts.top().fOriginatingIdx = -1;
96 0 : fPts.top().fNeedsToBeNew = true;
97 0 : return fPts.count() - 1;
98 : }
99 :
100 0 : int fuseWithNext() {
101 0 : fPts[0].fOriginatingIdx = -1;
102 0 : fPts[0].fNeedsToBeNew = true;
103 0 : return 0;
104 : }
105 :
106 0 : int fuseWithBoth() {
107 0 : if (fPts.count() > 1) {
108 0 : fPts.pop();
109 : }
110 :
111 0 : fPts[0].fOriginatingIdx = -1;
112 0 : fPts[0].fNeedsToBeNew = true;
113 0 : 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 0 : class Ring {
130 : public:
131 0 : void setReserve(int numPts) { fPts.setReserve(numPts); }
132 0 : void rewind() { fPts.rewind(); }
133 :
134 0 : int numPts() const { return fPts.count(); }
135 :
136 0 : void addIdx(int index, int origEdgeId) {
137 0 : struct PointData* pt = fPts.push();
138 0 : pt->fIndex = index;
139 0 : pt->fOrigEdgeId = origEdgeId;
140 0 : }
141 :
142 : // Upgrade this ring so that it can behave like an originating ring
143 0 : void makeOriginalRing() {
144 0 : for (int i = 0; i < fPts.count(); ++i) {
145 0 : fPts[i].fOrigEdgeId = fPts[i].fIndex;
146 : }
147 0 : }
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 0 : const SkPoint& norm(int index) const { return fPts[index].fNorm; }
154 0 : const SkPoint& bisector(int index) const { return fPts[index].fBisector; }
155 0 : int index(int index) const { return fPts[index].fIndex; }
156 0 : 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 0 : 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 0 : void reservePts(int count) {
205 0 : fPts.setReserve(count);
206 0 : fCoverages.setReserve(count);
207 0 : fMovable.setReserve(count);
208 0 : }
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
|
