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() {
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(fEdgeType == kAnalyticEdge);
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(fEdgeType == kAnalyticEdge);
119 return !edge->fDX && !edge->fCurveCount;
120 }
121
addLine(const SkPoint pts[])122 void SkEdgeBuilder::addLine(const SkPoint pts[]) {
123 if (fEdgeType == kBezier) {
124 SkLine* line = fAlloc.make<SkLine>();
125 if (line->set(pts)) {
126 fList.push(line);
127 }
128 } else if (fEdgeType == kAnalyticEdge) {
129 SkAnalyticEdge* edge = fAlloc.make<SkAnalyticEdge>();
130 if (edge->setLine(pts[0], pts[1])) {
131 if (vertical_line(edge) && fList.count()) {
132 Combine combine = CombineVertical(edge, (SkAnalyticEdge*)*(fList.end() - 1));
133 if (kNo_Combine != combine) {
134 if (kTotal_Combine == combine) {
135 fList.pop();
136 }
137 goto unallocate_analytic_edge;
138 }
139 }
140 fList.push(edge);
141 } else {
142 unallocate_analytic_edge:
143 ;
144 // TODO: unallocate edge from storage...
145 }
146 } else {
147 SkEdge* edge = fAlloc.make<SkEdge>();
148 if (edge->setLine(pts[0], pts[1], fShiftUp)) {
149 if (vertical_line(edge) && fList.count()) {
150 Combine combine = CombineVertical(edge, (SkEdge*)*(fList.end() - 1));
151 if (kNo_Combine != combine) {
152 if (kTotal_Combine == combine) {
153 fList.pop();
154 }
155 goto unallocate_edge;
156 }
157 }
158 fList.push(edge);
159 } else {
160 unallocate_edge:
161 ;
162 // TODO: unallocate edge from storage...
163 }
164 }
165 }
166
addQuad(const SkPoint pts[])167 void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
168 if (fEdgeType == kBezier) {
169 SkQuad* quad = fAlloc.make<SkQuad>();
170 if (quad->set(pts)) {
171 fList.push(quad);
172 }
173 } else if (fEdgeType == kAnalyticEdge) {
174 SkAnalyticQuadraticEdge* edge = fAlloc.make<SkAnalyticQuadraticEdge>();
175 if (edge->setQuadratic(pts)) {
176 fList.push(edge);
177 } else {
178 // TODO: unallocate edge from storage...
179 }
180 } else {
181 SkQuadraticEdge* edge = fAlloc.make<SkQuadraticEdge>();
182 if (edge->setQuadratic(pts, fShiftUp)) {
183 fList.push(edge);
184 } else {
185 // TODO: unallocate edge from storage...
186 }
187 }
188 }
189
addCubic(const SkPoint pts[])190 void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
191 if (fEdgeType == kBezier) {
192 SkCubic* cubic = fAlloc.make<SkCubic>();
193 if (cubic->set(pts)) {
194 fList.push(cubic);
195 }
196 } else if (fEdgeType == kAnalyticEdge) {
197 SkAnalyticCubicEdge* edge = fAlloc.make<SkAnalyticCubicEdge>();
198 if (edge->setCubic(pts)) {
199 fList.push(edge);
200 } else {
201 // TODO: unallocate edge from storage...
202 }
203 } else {
204 SkCubicEdge* edge = fAlloc.make<SkCubicEdge>();
205 if (edge->setCubic(pts, fShiftUp)) {
206 fList.push(edge);
207 } else {
208 // TODO: unallocate edge from storage...
209 }
210 }
211 }
212
addClipper(SkEdgeClipper * clipper)213 void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
214 SkPoint pts[4];
215 SkPath::Verb verb;
216
217 while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
218 switch (verb) {
219 case SkPath::kLine_Verb:
220 this->addLine(pts);
221 break;
222 case SkPath::kQuad_Verb:
223 this->addQuad(pts);
224 break;
225 case SkPath::kCubic_Verb:
226 this->addCubic(pts);
227 break;
228 default:
229 break;
230 }
231 }
232 }
233
234 ///////////////////////////////////////////////////////////////////////////////
235
setShiftedClip(SkRect * dst,const SkIRect & src,int shift)236 static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
237 dst->set(SkIntToScalar(src.fLeft >> shift),
238 SkIntToScalar(src.fTop >> shift),
239 SkIntToScalar(src.fRight >> shift),
240 SkIntToScalar(src.fBottom >> shift));
241 }
242
checkVertical(const SkEdge * edge,SkEdge ** edgePtr)243 SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge** edgePtr) {
244 return !vertical_line(edge) || edgePtr <= (SkEdge**)fEdgeList ? kNo_Combine :
245 CombineVertical(edge, edgePtr[-1]);
246 }
247
checkVertical(const SkAnalyticEdge * edge,SkAnalyticEdge ** edgePtr)248 SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkAnalyticEdge* edge,
249 SkAnalyticEdge** edgePtr) {
250 SkASSERT(fEdgeType == kAnalyticEdge);
251 return !vertical_line(edge) || edgePtr <= (SkAnalyticEdge**)fEdgeList ? kNo_Combine :
252 CombineVertical(edge, edgePtr[-1]);
253 }
254
buildPoly(const SkPath & path,const SkIRect * iclip,int shiftUp,bool canCullToTheRight)255 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp,
256 bool canCullToTheRight) {
257 SkPath::Iter iter(path, true);
258 SkPoint pts[4];
259 SkPath::Verb verb;
260
261 size_t maxEdgeCount = path.countPoints();
262 if (iclip) {
263 // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
264 // we turn portions that are clipped out on the left/right into vertical
265 // segments.
266 maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
267 }
268
269 size_t edgeSize;
270 char* edge;
271 switch (fEdgeType) {
272 case kEdge:
273 edgeSize = sizeof(SkEdge);
274 edge = (char*)fAlloc.makeArrayDefault<SkEdge>(maxEdgeCount);
275 break;
276 case kAnalyticEdge:
277 edgeSize = sizeof(SkAnalyticEdge);
278 edge = (char*)fAlloc.makeArrayDefault<SkAnalyticEdge>(maxEdgeCount);
279 break;
280 case kBezier:
281 edgeSize = sizeof(SkLine);
282 edge = (char*)fAlloc.makeArrayDefault<SkLine>(maxEdgeCount);
283 break;
284 }
285
286 SkDEBUGCODE(char* edgeStart = edge);
287 char** edgePtr = fAlloc.makeArrayDefault<char*>(maxEdgeCount);
288 fEdgeList = (void**)edgePtr;
289
290 if (iclip) {
291 SkRect clip;
292 setShiftedClip(&clip, *iclip, shiftUp);
293
294 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
295 switch (verb) {
296 case SkPath::kMove_Verb:
297 case SkPath::kClose_Verb:
298 // we ignore these, and just get the whole segment from
299 // the corresponding line/quad/cubic verbs
300 break;
301 case SkPath::kLine_Verb: {
302 SkPoint lines[SkLineClipper::kMaxPoints];
303 int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
304 SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
305 for (int i = 0; i < lineCount; i++) {
306 this->addPolyLine(lines + i, edge, edgeSize, edgePtr, shiftUp);
307 }
308 break;
309 }
310 default:
311 SkDEBUGFAIL("unexpected verb");
312 break;
313 }
314 }
315 } else {
316 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
317 switch (verb) {
318 case SkPath::kMove_Verb:
319 case SkPath::kClose_Verb:
320 // we ignore these, and just get the whole segment from
321 // the corresponding line/quad/cubic verbs
322 break;
323 case SkPath::kLine_Verb: {
324 this->addPolyLine(pts, edge, edgeSize, edgePtr, shiftUp);
325 break;
326 }
327 default:
328 SkDEBUGFAIL("unexpected verb");
329 break;
330 }
331 }
332 }
333 SkASSERT((size_t)(edge - edgeStart) <= maxEdgeCount * edgeSize);
334 SkASSERT((size_t)(edgePtr - (char**)fEdgeList) <= maxEdgeCount);
335 return SkToInt(edgePtr - (char**)fEdgeList);
336 }
337
handle_quad(SkEdgeBuilder * builder,const SkPoint pts[3])338 static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
339 SkPoint monoX[5];
340 int n = SkChopQuadAtYExtrema(pts, monoX);
341 for (int i = 0; i <= n; i++) {
342 builder->addQuad(&monoX[i * 2]);
343 }
344 }
345
build(const SkPath & path,const SkIRect * iclip,int shiftUp,bool canCullToTheRight,EdgeType edgeType)346 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp,
347 bool canCullToTheRight, EdgeType edgeType) {
348 fAlloc.reset();
349 fList.reset();
350 fShiftUp = shiftUp;
351 fEdgeType = edgeType;
352
353 if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
354 return this->buildPoly(path, iclip, shiftUp, canCullToTheRight);
355 }
356
357 SkAutoConicToQuads quadder;
358 const SkScalar conicTol = SK_Scalar1 / 4;
359
360 SkPath::Iter iter(path, true);
361 SkPoint pts[4];
362 SkPath::Verb verb;
363
364 if (iclip) {
365 SkRect clip;
366 setShiftedClip(&clip, *iclip, shiftUp);
367 SkEdgeClipper clipper(canCullToTheRight);
368
369 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
370 switch (verb) {
371 case SkPath::kMove_Verb:
372 case SkPath::kClose_Verb:
373 // we ignore these, and just get the whole segment from
374 // the corresponding line/quad/cubic verbs
375 break;
376 case SkPath::kLine_Verb:
377 if (clipper.clipLine(pts[0], pts[1], clip)) {
378 this->addClipper(&clipper);
379 }
380 break;
381 case SkPath::kQuad_Verb:
382 if (clipper.clipQuad(pts, clip)) {
383 this->addClipper(&clipper);
384 }
385 break;
386 case SkPath::kConic_Verb: {
387 const SkPoint* quadPts = quadder.computeQuads(
388 pts, iter.conicWeight(), conicTol);
389 for (int i = 0; i < quadder.countQuads(); ++i) {
390 if (clipper.clipQuad(quadPts, clip)) {
391 this->addClipper(&clipper);
392 }
393 quadPts += 2;
394 }
395 } break;
396 case SkPath::kCubic_Verb:
397 if (clipper.clipCubic(pts, clip)) {
398 this->addClipper(&clipper);
399 }
400 break;
401 default:
402 SkDEBUGFAIL("unexpected verb");
403 break;
404 }
405 }
406 } else {
407 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
408 switch (verb) {
409 case SkPath::kMove_Verb:
410 case SkPath::kClose_Verb:
411 // we ignore these, and just get the whole segment from
412 // the corresponding line/quad/cubic verbs
413 break;
414 case SkPath::kLine_Verb:
415 this->addLine(pts);
416 break;
417 case SkPath::kQuad_Verb: {
418 handle_quad(this, pts);
419 break;
420 }
421 case SkPath::kConic_Verb: {
422 const SkPoint* quadPts = quadder.computeQuads(
423 pts, iter.conicWeight(), conicTol);
424 for (int i = 0; i < quadder.countQuads(); ++i) {
425 handle_quad(this, quadPts);
426 quadPts += 2;
427 }
428 } break;
429 case SkPath::kCubic_Verb: {
430 if (fEdgeType == kBezier) {
431 this->addCubic(pts);
432 break;
433 }
434 SkPoint monoY[10];
435 int n = SkChopCubicAtYExtrema(pts, monoY);
436 for (int i = 0; i <= n; i++) {
437 this->addCubic(&monoY[i * 3]);
438 }
439 break;
440 }
441 default:
442 SkDEBUGFAIL("unexpected verb");
443 break;
444 }
445 }
446 }
447 fEdgeList = fList.begin();
448 return fList.count();
449 }
450
build_edges(const SkPath & path,const SkIRect * shiftedClip,int shiftEdgesUp,bool pathContainedInClip,EdgeType edgeType)451 int SkEdgeBuilder::build_edges(const SkPath& path, const SkIRect* shiftedClip,
452 int shiftEdgesUp, bool pathContainedInClip, EdgeType edgeType) {
453 // If we're convex, then we need both edges, even the right edge is past the clip
454 const bool canCullToTheRight = !path.isConvex();
455
456 const SkIRect* builderClip = pathContainedInClip ? nullptr : shiftedClip;
457 int count = this->build(path, builderClip, shiftEdgesUp, canCullToTheRight, edgeType);
458 SkASSERT(count >= 0);
459
460 // canCullToRight == false should imply count != 1 if edgeType != kBezier.
461 // If edgeType == kBezier (DAA), we don't chop edges at y extrema so count == 1 is valid.
462 // For example, a single cubic edge with a valley shape \_/ is fine for DAA.
463 SkASSERT(edgeType == kBezier || canCullToTheRight || count != 1);
464
465 return count;
466 }
467