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