1
2 /*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8 #include "SkEdgeBuilder.h"
9 #include "SkPath.h"
10 #include "SkEdge.h"
11 #include "SkEdgeClipper.h"
12 #include "SkLineClipper.h"
13 #include "SkGeometry.h"
14
typedAllocThrow(SkChunkAlloc & alloc)15 template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) {
16 return static_cast<T*>(alloc.allocThrow(sizeof(T)));
17 }
18
19 ///////////////////////////////////////////////////////////////////////////////
20
SkEdgeBuilder()21 SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {
22 fEdgeList = NULL;
23 }
24
addLine(const SkPoint pts[])25 void SkEdgeBuilder::addLine(const SkPoint pts[]) {
26 SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
27 if (edge->setLine(pts[0], pts[1], fShiftUp)) {
28 fList.push(edge);
29 } else {
30 // TODO: unallocate edge from storage...
31 }
32 }
33
addQuad(const SkPoint pts[])34 void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
35 SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc);
36 if (edge->setQuadratic(pts, fShiftUp)) {
37 fList.push(edge);
38 } else {
39 // TODO: unallocate edge from storage...
40 }
41 }
42
addCubic(const SkPoint pts[])43 void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
44 SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc);
45 if (edge->setCubic(pts, NULL, fShiftUp)) {
46 fList.push(edge);
47 } else {
48 // TODO: unallocate edge from storage...
49 }
50 }
51
addClipper(SkEdgeClipper * clipper)52 void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
53 SkPoint pts[4];
54 SkPath::Verb verb;
55
56 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
57 switch (verb) {
58 case SkPath::kLine_Verb:
59 this->addLine(pts);
60 break;
61 case SkPath::kQuad_Verb:
62 this->addQuad(pts);
63 break;
64 case SkPath::kCubic_Verb:
65 this->addCubic(pts);
66 break;
67 default:
68 break;
69 }
70 }
71 }
72
73 ///////////////////////////////////////////////////////////////////////////////
74
setShiftedClip(SkRect * dst,const SkIRect & src,int shift)75 static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
76 dst->set(SkIntToScalar(src.fLeft >> shift),
77 SkIntToScalar(src.fTop >> shift),
78 SkIntToScalar(src.fRight >> shift),
79 SkIntToScalar(src.fBottom >> shift));
80 }
81
buildPoly(const SkPath & path,const SkIRect * iclip,int shiftUp)82 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip,
83 int shiftUp) {
84 SkPath::Iter iter(path, true);
85 SkPoint pts[4];
86 SkPath::Verb verb;
87
88 int maxEdgeCount = path.countPoints();
89 if (iclip) {
90 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
91 // we turn portions that are clipped out on the left/right into vertical
92 // segments.
93 maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
94 }
95 size_t maxEdgeSize = maxEdgeCount * sizeof(SkEdge);
96 size_t maxEdgePtrSize = maxEdgeCount * sizeof(SkEdge*);
97
98 // lets store the edges and their pointers in the same block
99 char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize);
100 SkEdge* edge = reinterpret_cast<SkEdge*>(storage);
101 SkEdge** edgePtr = reinterpret_cast<SkEdge**>(storage + maxEdgeSize);
102 // Record the beginning of our pointers, so we can return them to the caller
103 fEdgeList = edgePtr;
104
105 if (iclip) {
106 SkRect clip;
107 setShiftedClip(&clip, *iclip, shiftUp);
108
109 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
110 switch (verb) {
111 case SkPath::kMove_Verb:
112 case SkPath::kClose_Verb:
113 // we ignore these, and just get the whole segment from
114 // the corresponding line/quad/cubic verbs
115 break;
116 case SkPath::kLine_Verb: {
117 SkPoint lines[SkLineClipper::kMaxPoints];
118 int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
119 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
120 for (int i = 0; i < lineCount; i++) {
121 if (edge->setLine(lines[i], lines[i + 1], shiftUp)) {
122 *edgePtr++ = edge++;
123 }
124 }
125 break;
126 }
127 default:
128 SkDEBUGFAIL("unexpected verb");
129 break;
130 }
131 }
132 } else {
133 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
134 switch (verb) {
135 case SkPath::kMove_Verb:
136 case SkPath::kClose_Verb:
137 // we ignore these, and just get the whole segment from
138 // the corresponding line/quad/cubic verbs
139 break;
140 case SkPath::kLine_Verb:
141 if (edge->setLine(pts[0], pts[1], shiftUp)) {
142 *edgePtr++ = edge++;
143 }
144 break;
145 default:
146 SkDEBUGFAIL("unexpected verb");
147 break;
148 }
149 }
150 }
151 SkASSERT((char*)edge <= (char*)fEdgeList);
152 SkASSERT(edgePtr - fEdgeList <= maxEdgeCount);
153 return SkToInt(edgePtr - fEdgeList);
154 }
155
handle_quad(SkEdgeBuilder * builder,const SkPoint pts[3])156 static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
157 SkPoint monoX[5];
158 int n = SkChopQuadAtYExtrema(pts, monoX);
159 for (int i = 0; i <= n; i++) {
160 builder->addQuad(&monoX[i * 2]);
161 }
162 }
163
build(const SkPath & path,const SkIRect * iclip,int shiftUp)164 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip,
165 int shiftUp) {
166 fAlloc.reset();
167 fList.reset();
168 fShiftUp = shiftUp;
169
170 SkScalar conicTol = SK_ScalarHalf * (1 << shiftUp);
171
172 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
173 return this->buildPoly(path, iclip, shiftUp);
174 }
175
176 SkPath::Iter iter(path, true);
177 SkPoint pts[4];
178 SkPath::Verb verb;
179
180 if (iclip) {
181 SkRect clip;
182 setShiftedClip(&clip, *iclip, shiftUp);
183 SkEdgeClipper clipper;
184
185 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
186 switch (verb) {
187 case SkPath::kMove_Verb:
188 case SkPath::kClose_Verb:
189 // we ignore these, and just get the whole segment from
190 // the corresponding line/quad/cubic verbs
191 break;
192 case SkPath::kLine_Verb: {
193 SkPoint lines[SkLineClipper::kMaxPoints];
194 int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
195 for (int i = 0; i < lineCount; i++) {
196 this->addLine(&lines[i]);
197 }
198 break;
199 }
200 case SkPath::kQuad_Verb:
201 if (clipper.clipQuad(pts, clip)) {
202 this->addClipper(&clipper);
203 }
204 break;
205 case SkPath::kConic_Verb: {
206 const int MAX_POW2 = 4;
207 const int MAX_QUADS = 1 << MAX_POW2;
208 const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS;
209 SkPoint storage[MAX_QUAD_PTS];
210
211 SkConic conic;
212 conic.set(pts, iter.conicWeight());
213 int pow2 = conic.computeQuadPOW2(conicTol);
214 pow2 = SkMin32(pow2, MAX_POW2);
215 int quadCount = conic.chopIntoQuadsPOW2(storage, pow2);
216 SkASSERT(quadCount <= MAX_QUADS);
217 for (int i = 0; i < quadCount; ++i) {
218 if (clipper.clipQuad(&storage[i * 2], clip)) {
219 this->addClipper(&clipper);
220 }
221 }
222 } break;
223 case SkPath::kCubic_Verb:
224 if (clipper.clipCubic(pts, clip)) {
225 this->addClipper(&clipper);
226 }
227 break;
228 default:
229 SkDEBUGFAIL("unexpected verb");
230 break;
231 }
232 }
233 } else {
234 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
235 switch (verb) {
236 case SkPath::kMove_Verb:
237 case SkPath::kClose_Verb:
238 // we ignore these, and just get the whole segment from
239 // the corresponding line/quad/cubic verbs
240 break;
241 case SkPath::kLine_Verb:
242 this->addLine(pts);
243 break;
244 case SkPath::kQuad_Verb: {
245 handle_quad(this, pts);
246 break;
247 }
248 case SkPath::kConic_Verb: {
249 const int MAX_POW2 = 4;
250 const int MAX_QUADS = 1 << MAX_POW2;
251 const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS;
252 SkPoint storage[MAX_QUAD_PTS];
253
254 SkConic conic;
255 conic.set(pts, iter.conicWeight());
256 int pow2 = conic.computeQuadPOW2(conicTol);
257 pow2 = SkMin32(pow2, MAX_POW2);
258 int quadCount = conic.chopIntoQuadsPOW2(storage, pow2);
259 SkASSERT(quadCount <= MAX_QUADS);
260 for (int i = 0; i < quadCount; ++i) {
261 handle_quad(this, &storage[i * 2]);
262 }
263 } break;
264 case SkPath::kCubic_Verb: {
265 SkPoint monoY[10];
266 int n = SkChopCubicAtYExtrema(pts, monoY);
267 for (int i = 0; i <= n; i++) {
268 this->addCubic(&monoY[i * 3]);
269 }
270 break;
271 }
272 default:
273 SkDEBUGFAIL("unexpected verb");
274 break;
275 }
276 }
277 }
278 fEdgeList = fList.begin();
279 return fList.count();
280 }
281