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
17SkEdgeBuilder::SkEdgeBuilder() {
18    fEdgeList = nullptr;
19}
20
21SkEdgeBuilder::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
62static inline bool approximatelyEqual(SkFixed a, SkFixed b) {
63    return SkAbs32(a - b) < 0x100;
64}
65
66SkEdgeBuilder::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
113bool SkEdgeBuilder::vertical_line(const SkEdge* edge) {
114    return !edge->fDX && !edge->fCurveCount;
115}
116
117bool SkEdgeBuilder::vertical_line(const SkAnalyticEdge* edge) {
118    SkASSERT(fEdgeType == kAnalyticEdge);
119    return !edge->fDX && !edge->fCurveCount;
120}
121
122void 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 {
142unallocate_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 {
160unallocate_edge:
161            ;
162            // TODO: unallocate edge from storage...
163        }
164    }
165}
166
167void 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
190void 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
213void 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
236static 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
243SkEdgeBuilder::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
248SkEdgeBuilder::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
255int 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
338static 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
346int 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
451int 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