1 /*
2 * Copyright 2011 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 #include "SkEdgeBuilder.h"
8 #include "SkPath.h"
9 #include "SkEdge.h"
10 #include "SkAnalyticEdge.h"
11 #include "SkEdgeClipper.h"
12 #include "SkLineClipper.h"
13 #include "SkGeometry.h"
14
15 ///////////////////////////////////////////////////////////////////////////////
16
SkEdgeBuilder()17 SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {
18 fEdgeList = nullptr;
19 }
20
CombineVertical(const SkEdge * edge,SkEdge * last)21 SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical(const SkEdge* edge, SkEdge* last) {
22 if (last->fCurveCount || last->fDX || edge->fX != last->fX) {
23 return kNo_Combine;
24 }
25 if (edge->fWinding == last->fWinding) {
26 if (edge->fLastY + 1 == last->fFirstY) {
27 last->fFirstY = edge->fFirstY;
28 return kPartial_Combine;
29 }
30 if (edge->fFirstY == last->fLastY + 1) {
31 last->fLastY = edge->fLastY;
32 return kPartial_Combine;
33 }
34 return kNo_Combine;
35 }
36 if (edge->fFirstY == last->fFirstY) {
37 if (edge->fLastY == last->fLastY) {
38 return kTotal_Combine;
39 }
40 if (edge->fLastY < last->fLastY) {
41 last->fFirstY = edge->fLastY + 1;
42 return kPartial_Combine;
43 }
44 last->fFirstY = last->fLastY + 1;
45 last->fLastY = edge->fLastY;
46 last->fWinding = edge->fWinding;
47 return kPartial_Combine;
48 }
49 if (edge->fLastY == last->fLastY) {
50 if (edge->fFirstY > last->fFirstY) {
51 last->fLastY = edge->fFirstY - 1;
52 return kPartial_Combine;
53 }
54 last->fLastY = last->fFirstY - 1;
55 last->fFirstY = edge->fFirstY;
56 last->fWinding = edge->fWinding;
57 return kPartial_Combine;
58 }
59 return kNo_Combine;
60 }
61
approximatelyEqual(SkFixed a,SkFixed b)62 static inline bool approximatelyEqual(SkFixed a, SkFixed b) {
63 return SkAbs32(a - b) < 0x100;
64 }
65
CombineVertical(const SkAnalyticEdge * edge,SkAnalyticEdge * last)66 SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical(
67 const SkAnalyticEdge* edge, SkAnalyticEdge* last) {
68 SkASSERT(fAnalyticAA);
69 if (last->fCurveCount || last->fDX || edge->fX != last->fX) {
70 return kNo_Combine;
71 }
72 if (edge->fWinding == last->fWinding) {
73 if (edge->fLowerY == last->fUpperY) {
74 last->fUpperY = edge->fUpperY;
75 last->fY = last->fUpperY;
76 return kPartial_Combine;
77 }
78 if (approximatelyEqual(edge->fUpperY, last->fLowerY)) {
79 last->fLowerY = edge->fLowerY;
80 return kPartial_Combine;
81 }
82 return kNo_Combine;
83 }
84 if (approximatelyEqual(edge->fUpperY, last->fUpperY)) {
85 if (approximatelyEqual(edge->fLowerY, last->fLowerY)) {
86 return kTotal_Combine;
87 }
88 if (edge->fLowerY < last->fLowerY) {
89 last->fUpperY = edge->fLowerY;
90 last->fY = last->fUpperY;
91 return kPartial_Combine;
92 }
93 last->fUpperY = last->fLowerY;
94 last->fY = last->fUpperY;
95 last->fLowerY = edge->fLowerY;
96 last->fWinding = edge->fWinding;
97 return kPartial_Combine;
98 }
99 if (approximatelyEqual(edge->fLowerY, last->fLowerY)) {
100 if (edge->fUpperY > last->fUpperY) {
101 last->fLowerY = edge->fUpperY;
102 return kPartial_Combine;
103 }
104 last->fLowerY = last->fUpperY;
105 last->fUpperY = edge->fUpperY;
106 last->fY = last->fUpperY;
107 last->fWinding = edge->fWinding;
108 return kPartial_Combine;
109 }
110 return kNo_Combine;
111 }
112
vertical_line(const SkEdge * edge)113 bool SkEdgeBuilder::vertical_line(const SkEdge* edge) {
114 return !edge->fDX && !edge->fCurveCount;
115 }
116
vertical_line(const SkAnalyticEdge * edge)117 bool SkEdgeBuilder::vertical_line(const SkAnalyticEdge* edge) {
118 SkASSERT(fAnalyticAA);
119 return !edge->fDX && !edge->fCurveCount;
120 }
121
addLine(const SkPoint pts[])122 void SkEdgeBuilder::addLine(const SkPoint pts[]) {
123 if (fAnalyticAA) {
124 SkAnalyticEdge* edge = fAlloc.make<SkAnalyticEdge>();
125 if (edge->setLine(pts[0], pts[1])) {
126 if (vertical_line(edge) && fList.count()) {
127 Combine combine = CombineVertical(edge, (SkAnalyticEdge*)*(fList.end() - 1));
128 if (kNo_Combine != combine) {
129 if (kTotal_Combine == combine) {
130 fList.pop();
131 }
132 goto unallocate_analytic_edge;
133 }
134 }
135 fList.push(edge);
136 } else {
137 unallocate_analytic_edge:
138 ;
139 // TODO: unallocate edge from storage...
140 }
141 } else {
142 SkEdge* edge = fAlloc.make<SkEdge>();
143 if (edge->setLine(pts[0], pts[1], fShiftUp)) {
144 if (vertical_line(edge) && fList.count()) {
145 Combine combine = CombineVertical(edge, (SkEdge*)*(fList.end() - 1));
146 if (kNo_Combine != combine) {
147 if (kTotal_Combine == combine) {
148 fList.pop();
149 }
150 goto unallocate_edge;
151 }
152 }
153 fList.push(edge);
154 } else {
155 unallocate_edge:
156 ;
157 // TODO: unallocate edge from storage...
158 }
159 }
160 }
161
addQuad(const SkPoint pts[])162 void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
163 if (fAnalyticAA) {
164 SkAnalyticQuadraticEdge* edge = fAlloc.make<SkAnalyticQuadraticEdge>();
165 if (edge->setQuadratic(pts)) {
166 fList.push(edge);
167 } else {
168 // TODO: unallocate edge from storage...
169 }
170 } else {
171 SkQuadraticEdge* edge = fAlloc.make<SkQuadraticEdge>();
172 if (edge->setQuadratic(pts, fShiftUp)) {
173 fList.push(edge);
174 } else {
175 // TODO: unallocate edge from storage...
176 }
177 }
178 }
179
addCubic(const SkPoint pts[])180 void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
181 if (fAnalyticAA) {
182 SkAnalyticCubicEdge* edge = fAlloc.make<SkAnalyticCubicEdge>();
183 if (edge->setCubic(pts)) {
184 fList.push(edge);
185 } else {
186 // TODO: unallocate edge from storage...
187 }
188 } else {
189 SkCubicEdge* edge = fAlloc.make<SkCubicEdge>();
190 if (edge->setCubic(pts, fShiftUp)) {
191 fList.push(edge);
192 } else {
193 // TODO: unallocate edge from storage...
194 }
195 }
196 }
197
addClipper(SkEdgeClipper * clipper)198 void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
199 SkPoint pts[4];
200 SkPath::Verb verb;
201
202 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
203 switch (verb) {
204 case SkPath::kLine_Verb:
205 this->addLine(pts);
206 break;
207 case SkPath::kQuad_Verb:
208 this->addQuad(pts);
209 break;
210 case SkPath::kCubic_Verb:
211 this->addCubic(pts);
212 break;
213 default:
214 break;
215 }
216 }
217 }
218
219 ///////////////////////////////////////////////////////////////////////////////
220
setShiftedClip(SkRect * dst,const SkIRect & src,int shift)221 static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
222 dst->set(SkIntToScalar(src.fLeft >> shift),
223 SkIntToScalar(src.fTop >> shift),
224 SkIntToScalar(src.fRight >> shift),
225 SkIntToScalar(src.fBottom >> shift));
226 }
227
checkVertical(const SkEdge * edge,SkEdge ** edgePtr)228 SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge** edgePtr) {
229 return !vertical_line(edge) || edgePtr <= (SkEdge**)fEdgeList ? kNo_Combine :
230 CombineVertical(edge, edgePtr[-1]);
231 }
232
checkVertical(const SkAnalyticEdge * edge,SkAnalyticEdge ** edgePtr)233 SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkAnalyticEdge* edge,
234 SkAnalyticEdge** edgePtr) {
235 SkASSERT(fAnalyticAA);
236 return !vertical_line(edge) || edgePtr <= (SkAnalyticEdge**)fEdgeList ? kNo_Combine :
237 CombineVertical(edge, edgePtr[-1]);
238 }
239
buildPoly(const SkPath & path,const SkIRect * iclip,int shiftUp,bool canCullToTheRight)240 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp,
241 bool canCullToTheRight) {
242 SkPath::Iter iter(path, true);
243 SkPoint pts[4];
244 SkPath::Verb verb;
245
246 int maxEdgeCount = path.countPoints();
247 if (iclip) {
248 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
249 // we turn portions that are clipped out on the left/right into vertical
250 // segments.
251 maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
252 }
253
254 size_t edgeSize = fAnalyticAA ? sizeof(SkAnalyticEdge) : sizeof(SkEdge);
255 char* edge = fAnalyticAA ? (char*)fAlloc.makeArrayDefault<SkAnalyticEdge>(maxEdgeCount)
256 : (char*)fAlloc.makeArrayDefault<SkEdge>(maxEdgeCount);
257
258 SkDEBUGCODE(char* edgeStart = edge);
259 char** edgePtr = fAlloc.makeArrayDefault<char*>(maxEdgeCount);
260 fEdgeList = (void**)edgePtr;
261
262 if (iclip) {
263 SkRect clip;
264 setShiftedClip(&clip, *iclip, shiftUp);
265
266 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
267 switch (verb) {
268 case SkPath::kMove_Verb:
269 case SkPath::kClose_Verb:
270 // we ignore these, and just get the whole segment from
271 // the corresponding line/quad/cubic verbs
272 break;
273 case SkPath::kLine_Verb: {
274 SkPoint lines[SkLineClipper::kMaxPoints];
275 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
276 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
277 for (int i = 0; i < lineCount; i++) {
278 bool setLineResult = fAnalyticAA ?
279 ((SkAnalyticEdge*)edge)->setLine(lines[i], lines[i + 1]) :
280 ((SkEdge*)edge)->setLine(lines[i], lines[i + 1], shiftUp);
281 if (setLineResult) {
282 Combine combine = fAnalyticAA ?
283 checkVertical((SkAnalyticEdge*)edge, (SkAnalyticEdge**)edgePtr) :
284 checkVertical((SkEdge*)edge, (SkEdge**)edgePtr);
285 if (kNo_Combine == combine) {
286 *edgePtr++ = edge;
287 edge += edgeSize;
288 } else if (kTotal_Combine == combine) {
289 --edgePtr;
290 }
291 }
292 }
293 break;
294 }
295 default:
296 SkDEBUGFAIL("unexpected verb");
297 break;
298 }
299 }
300 } else {
301 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
302 switch (verb) {
303 case SkPath::kMove_Verb:
304 case SkPath::kClose_Verb:
305 // we ignore these, and just get the whole segment from
306 // the corresponding line/quad/cubic verbs
307 break;
308 case SkPath::kLine_Verb: {
309 bool setLineResult = fAnalyticAA ?
310 ((SkAnalyticEdge*)edge)->setLine(pts[0], pts[1]) :
311 ((SkEdge*)edge)->setLine(pts[0], pts[1], shiftUp);
312 if (setLineResult) {
313 Combine combine = fAnalyticAA ?
314 checkVertical((SkAnalyticEdge*)edge, (SkAnalyticEdge**)edgePtr) :
315 checkVertical((SkEdge*)edge, (SkEdge**)edgePtr);
316 if (kNo_Combine == combine) {
317 *edgePtr++ = edge;
318 edge += edgeSize;
319 } else if (kTotal_Combine == combine) {
320 --edgePtr;
321 }
322 }
323 break;
324 }
325 default:
326 SkDEBUGFAIL("unexpected verb");
327 break;
328 }
329 }
330 }
331 SkASSERT((size_t)(edge - edgeStart) <= maxEdgeCount * edgeSize);
332 SkASSERT(edgePtr - (char**)fEdgeList <= maxEdgeCount);
333 return SkToInt(edgePtr - (char**)fEdgeList);
334 }
335
handle_quad(SkEdgeBuilder * builder,const SkPoint pts[3])336 static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
337 SkPoint monoX[5];
338 int n = SkChopQuadAtYExtrema(pts, monoX);
339 for (int i = 0; i <= n; i++) {
340 builder->addQuad(&monoX[i * 2]);
341 }
342 }
343
build(const SkPath & path,const SkIRect * iclip,int shiftUp,bool canCullToTheRight,bool analyticAA)344 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp,
345 bool canCullToTheRight, bool analyticAA) {
346 fAlloc.reset();
347 fList.reset();
348 fShiftUp = shiftUp;
349 fAnalyticAA = analyticAA;
350
351 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
352 return this->buildPoly(path, iclip, shiftUp, canCullToTheRight);
353 }
354
355 SkAutoConicToQuads quadder;
356 const SkScalar conicTol = SK_Scalar1 / 4;
357
358 SkPath::Iter iter(path, true);
359 SkPoint pts[4];
360 SkPath::Verb verb;
361
362 if (iclip) {
363 SkRect clip;
364 setShiftedClip(&clip, *iclip, shiftUp);
365 SkEdgeClipper clipper(canCullToTheRight);
366
367 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
368 switch (verb) {
369 case SkPath::kMove_Verb:
370 case SkPath::kClose_Verb:
371 // we ignore these, and just get the whole segment from
372 // the corresponding line/quad/cubic verbs
373 break;
374 case SkPath::kLine_Verb:
375 if (clipper.clipLine(pts[0], pts[1], clip)) {
376 this->addClipper(&clipper);
377 }
378 break;
379 case SkPath::kQuad_Verb:
380 if (clipper.clipQuad(pts, clip)) {
381 this->addClipper(&clipper);
382 }
383 break;
384 case SkPath::kConic_Verb: {
385 const SkPoint* quadPts = quadder.computeQuads(
386 pts, iter.conicWeight(), conicTol);
387 for (int i = 0; i < quadder.countQuads(); ++i) {
388 if (clipper.clipQuad(quadPts, clip)) {
389 this->addClipper(&clipper);
390 }
391 quadPts += 2;
392 }
393 } break;
394 case SkPath::kCubic_Verb:
395 if (clipper.clipCubic(pts, clip)) {
396 this->addClipper(&clipper);
397 }
398 break;
399 default:
400 SkDEBUGFAIL("unexpected verb");
401 break;
402 }
403 }
404 } else {
405 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
406 switch (verb) {
407 case SkPath::kMove_Verb:
408 case SkPath::kClose_Verb:
409 // we ignore these, and just get the whole segment from
410 // the corresponding line/quad/cubic verbs
411 break;
412 case SkPath::kLine_Verb:
413 this->addLine(pts);
414 break;
415 case SkPath::kQuad_Verb: {
416 handle_quad(this, pts);
417 break;
418 }
419 case SkPath::kConic_Verb: {
420 const SkPoint* quadPts = quadder.computeQuads(
421 pts, iter.conicWeight(), conicTol);
422 for (int i = 0; i < quadder.countQuads(); ++i) {
423 handle_quad(this, quadPts);
424 quadPts += 2;
425 }
426 } break;
427 case SkPath::kCubic_Verb: {
428 SkPoint monoY[10];
429 int n = SkChopCubicAtYExtrema(pts, monoY);
430 for (int i = 0; i <= n; i++) {
431 this->addCubic(&monoY[i * 3]);
432 }
433 break;
434 }
435 default:
436 SkDEBUGFAIL("unexpected verb");
437 break;
438 }
439 }
440 }
441 fEdgeList = fList.begin();
442 return fList.count();
443 }
444