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() : fAlloc(16*1024) {
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(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
113bool SkEdgeBuilder::vertical_line(const SkEdge* edge) {
114    return !edge->fDX && !edge->fCurveCount;
115}
116
117bool SkEdgeBuilder::vertical_line(const SkAnalyticEdge* edge) {
118    SkASSERT(fAnalyticAA);
119    return !edge->fDX && !edge->fCurveCount;
120}
121
122void 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 {
137unallocate_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 {
155unallocate_edge:
156            ;
157            // TODO: unallocate edge from storage...
158        }
159    }
160}
161
162void 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
180void 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
198void 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
221static 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
228SkEdgeBuilder::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
233SkEdgeBuilder::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
240int 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
336static 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
344int 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