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 = nullptr;
23 }
24
CombineVertical(const SkEdge * edge,SkEdge * last)25 SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical(const SkEdge* edge, SkEdge* last) {
26 if (last->fCurveCount || last->fDX || edge->fX != last->fX) {
27 return kNo_Combine;
28 }
29 if (edge->fWinding == last->fWinding) {
30 if (edge->fLastY + 1 == last->fFirstY) {
31 last->fFirstY = edge->fFirstY;
32 return kPartial_Combine;
33 }
34 if (edge->fFirstY == last->fLastY + 1) {
35 last->fLastY = edge->fLastY;
36 return kPartial_Combine;
37 }
38 return kNo_Combine;
39 }
40 if (edge->fFirstY == last->fFirstY) {
41 if (edge->fLastY == last->fLastY) {
42 return kTotal_Combine;
43 }
44 if (edge->fLastY < last->fLastY) {
45 last->fFirstY = edge->fLastY + 1;
46 return kPartial_Combine;
47 }
48 last->fFirstY = last->fLastY + 1;
49 last->fLastY = edge->fLastY;
50 last->fWinding = edge->fWinding;
51 return kPartial_Combine;
52 }
53 if (edge->fLastY == last->fLastY) {
54 if (edge->fFirstY > last->fFirstY) {
55 last->fLastY = edge->fFirstY - 1;
56 return kPartial_Combine;
57 }
58 last->fLastY = last->fFirstY - 1;
59 last->fFirstY = edge->fFirstY;
60 last->fWinding = edge->fWinding;
61 return kPartial_Combine;
62 }
63 return kNo_Combine;
64 }
65
vertical_line(const SkEdge * edge)66 static bool vertical_line(const SkEdge* edge) {
67 return !edge->fDX && !edge->fCurveCount;
68 }
69
addLine(const SkPoint pts[])70 void SkEdgeBuilder::addLine(const SkPoint pts[]) {
71 SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
72 if (edge->setLine(pts[0], pts[1], fShiftUp)) {
73 if (vertical_line(edge) && fList.count()) {
74 Combine combine = CombineVertical(edge, *(fList.end() - 1));
75 if (kNo_Combine != combine) {
76 if (kTotal_Combine == combine) {
77 fList.pop();
78 }
79 goto unallocate_edge;
80 }
81 }
82 fList.push(edge);
83 } else {
84 unallocate_edge:
85 ;
86 // TODO: unallocate edge from storage...
87 }
88 }
89
addQuad(const SkPoint pts[])90 void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
91 SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc);
92 if (edge->setQuadratic(pts, fShiftUp)) {
93 fList.push(edge);
94 } else {
95 // TODO: unallocate edge from storage...
96 }
97 }
98
addCubic(const SkPoint pts[])99 void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
100 SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc);
101 if (edge->setCubic(pts, fShiftUp)) {
102 fList.push(edge);
103 } else {
104 // TODO: unallocate edge from storage...
105 }
106 }
107
addClipper(SkEdgeClipper * clipper)108 void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
109 SkPoint pts[4];
110 SkPath::Verb verb;
111
112 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
113 switch (verb) {
114 case SkPath::kLine_Verb:
115 this->addLine(pts);
116 break;
117 case SkPath::kQuad_Verb:
118 this->addQuad(pts);
119 break;
120 case SkPath::kCubic_Verb:
121 this->addCubic(pts);
122 break;
123 default:
124 break;
125 }
126 }
127 }
128
129 ///////////////////////////////////////////////////////////////////////////////
130
setShiftedClip(SkRect * dst,const SkIRect & src,int shift)131 static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
132 dst->set(SkIntToScalar(src.fLeft >> shift),
133 SkIntToScalar(src.fTop >> shift),
134 SkIntToScalar(src.fRight >> shift),
135 SkIntToScalar(src.fBottom >> shift));
136 }
137
checkVertical(const SkEdge * edge,SkEdge ** edgePtr)138 SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge** edgePtr) {
139 return !vertical_line(edge) || edgePtr <= fEdgeList ? kNo_Combine :
140 CombineVertical(edge, edgePtr[-1]);
141 }
142
buildPoly(const SkPath & path,const SkIRect * iclip,int shiftUp,bool canCullToTheRight)143 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp,
144 bool canCullToTheRight) {
145 SkPath::Iter iter(path, true);
146 SkPoint pts[4];
147 SkPath::Verb verb;
148
149 int maxEdgeCount = path.countPoints();
150 if (iclip) {
151 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
152 // we turn portions that are clipped out on the left/right into vertical
153 // segments.
154 maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
155 }
156 size_t maxEdgeSize = maxEdgeCount * sizeof(SkEdge);
157 size_t maxEdgePtrSize = maxEdgeCount * sizeof(SkEdge*);
158
159 // lets store the edges and their pointers in the same block
160 char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize);
161 SkEdge* edge = reinterpret_cast<SkEdge*>(storage);
162 SkEdge** edgePtr = reinterpret_cast<SkEdge**>(storage + maxEdgeSize);
163 // Record the beginning of our pointers, so we can return them to the caller
164 fEdgeList = edgePtr;
165
166 if (iclip) {
167 SkRect clip;
168 setShiftedClip(&clip, *iclip, shiftUp);
169
170 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
171 switch (verb) {
172 case SkPath::kMove_Verb:
173 case SkPath::kClose_Verb:
174 // we ignore these, and just get the whole segment from
175 // the corresponding line/quad/cubic verbs
176 break;
177 case SkPath::kLine_Verb: {
178 SkPoint lines[SkLineClipper::kMaxPoints];
179 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
180 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
181 for (int i = 0; i < lineCount; i++) {
182 if (edge->setLine(lines[i], lines[i + 1], shiftUp)) {
183 Combine combine = checkVertical(edge, edgePtr);
184 if (kNo_Combine == combine) {
185 *edgePtr++ = edge++;
186 } else if (kTotal_Combine == combine) {
187 --edgePtr;
188 }
189 }
190 }
191 break;
192 }
193 default:
194 SkDEBUGFAIL("unexpected verb");
195 break;
196 }
197 }
198 } else {
199 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
200 switch (verb) {
201 case SkPath::kMove_Verb:
202 case SkPath::kClose_Verb:
203 // we ignore these, and just get the whole segment from
204 // the corresponding line/quad/cubic verbs
205 break;
206 case SkPath::kLine_Verb:
207 if (edge->setLine(pts[0], pts[1], shiftUp)) {
208 Combine combine = checkVertical(edge, edgePtr);
209 if (kNo_Combine == combine) {
210 *edgePtr++ = edge++;
211 } else if (kTotal_Combine == combine) {
212 --edgePtr;
213 }
214 }
215 break;
216 default:
217 SkDEBUGFAIL("unexpected verb");
218 break;
219 }
220 }
221 }
222 SkASSERT((char*)edge <= (char*)fEdgeList);
223 SkASSERT(edgePtr - fEdgeList <= maxEdgeCount);
224 return SkToInt(edgePtr - fEdgeList);
225 }
226
handle_quad(SkEdgeBuilder * builder,const SkPoint pts[3])227 static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
228 SkPoint monoX[5];
229 int n = SkChopQuadAtYExtrema(pts, monoX);
230 for (int i = 0; i <= n; i++) {
231 builder->addQuad(&monoX[i * 2]);
232 }
233 }
234
build(const SkPath & path,const SkIRect * iclip,int shiftUp,bool canCullToTheRight)235 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp,
236 bool canCullToTheRight) {
237 fAlloc.reset();
238 fList.reset();
239 fShiftUp = shiftUp;
240
241 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
242 return this->buildPoly(path, iclip, shiftUp, canCullToTheRight);
243 }
244
245 SkAutoConicToQuads quadder;
246 const SkScalar conicTol = SK_Scalar1 / 4;
247
248 SkPath::Iter iter(path, true);
249 SkPoint pts[4];
250 SkPath::Verb verb;
251
252 if (iclip) {
253 SkRect clip;
254 setShiftedClip(&clip, *iclip, shiftUp);
255 SkEdgeClipper clipper(canCullToTheRight);
256
257 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
258 switch (verb) {
259 case SkPath::kMove_Verb:
260 case SkPath::kClose_Verb:
261 // we ignore these, and just get the whole segment from
262 // the corresponding line/quad/cubic verbs
263 break;
264 case SkPath::kLine_Verb: {
265 SkPoint lines[SkLineClipper::kMaxPoints];
266 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
267 for (int i = 0; i < lineCount; i++) {
268 this->addLine(&lines[i]);
269 }
270 break;
271 }
272 case SkPath::kQuad_Verb:
273 if (clipper.clipQuad(pts, clip)) {
274 this->addClipper(&clipper);
275 }
276 break;
277 case SkPath::kConic_Verb: {
278 const SkPoint* quadPts = quadder.computeQuads(
279 pts, iter.conicWeight(), conicTol);
280 for (int i = 0; i < quadder.countQuads(); ++i) {
281 if (clipper.clipQuad(quadPts, clip)) {
282 this->addClipper(&clipper);
283 }
284 quadPts += 2;
285 }
286 } break;
287 case SkPath::kCubic_Verb:
288 if (clipper.clipCubic(pts, clip)) {
289 this->addClipper(&clipper);
290 }
291 break;
292 default:
293 SkDEBUGFAIL("unexpected verb");
294 break;
295 }
296 }
297 } else {
298 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
299 switch (verb) {
300 case SkPath::kMove_Verb:
301 case SkPath::kClose_Verb:
302 // we ignore these, and just get the whole segment from
303 // the corresponding line/quad/cubic verbs
304 break;
305 case SkPath::kLine_Verb:
306 this->addLine(pts);
307 break;
308 case SkPath::kQuad_Verb: {
309 handle_quad(this, pts);
310 break;
311 }
312 case SkPath::kConic_Verb: {
313 const SkPoint* quadPts = quadder.computeQuads(
314 pts, iter.conicWeight(), conicTol);
315 for (int i = 0; i < quadder.countQuads(); ++i) {
316 handle_quad(this, quadPts);
317 quadPts += 2;
318 }
319 } break;
320 case SkPath::kCubic_Verb: {
321 SkPoint monoY[10];
322 int n = SkChopCubicAtYExtrema(pts, monoY);
323 for (int i = 0; i <= n; i++) {
324 this->addCubic(&monoY[i * 3]);
325 }
326 break;
327 }
328 default:
329 SkDEBUGFAIL("unexpected verb");
330 break;
331 }
332 }
333 }
334 fEdgeList = fList.begin();
335 return fList.count();
336 }
337