1
2/*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8#include "SkEdgeBuilder.h"
9#include "SkPath.h"
10#include "SkEdge.h"
11#include "SkEdgeClipper.h"
12#include "SkLineClipper.h"
13#include "SkGeometry.h"
14
15template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) {
16    return static_cast<T*>(alloc.allocThrow(sizeof(T)));
17}
18
19///////////////////////////////////////////////////////////////////////////////
20
21SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {
22    fEdgeList = NULL;
23}
24
25void SkEdgeBuilder::addLine(const SkPoint pts[]) {
26    SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
27    if (edge->setLine(pts[0], pts[1], fShiftUp)) {
28        fList.push(edge);
29    } else {
30        // TODO: unallocate edge from storage...
31    }
32}
33
34void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
35    SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc);
36    if (edge->setQuadratic(pts, fShiftUp)) {
37        fList.push(edge);
38    } else {
39        // TODO: unallocate edge from storage...
40    }
41}
42
43void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
44    SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc);
45    if (edge->setCubic(pts, NULL, fShiftUp)) {
46        fList.push(edge);
47    } else {
48        // TODO: unallocate edge from storage...
49    }
50}
51
52void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
53    SkPoint      pts[4];
54    SkPath::Verb verb;
55
56    while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
57        switch (verb) {
58            case SkPath::kLine_Verb:
59                this->addLine(pts);
60                break;
61            case SkPath::kQuad_Verb:
62                this->addQuad(pts);
63                break;
64            case SkPath::kCubic_Verb:
65                this->addCubic(pts);
66                break;
67            default:
68                break;
69        }
70    }
71}
72
73///////////////////////////////////////////////////////////////////////////////
74
75static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
76    dst->set(SkIntToScalar(src.fLeft >> shift),
77             SkIntToScalar(src.fTop >> shift),
78             SkIntToScalar(src.fRight >> shift),
79             SkIntToScalar(src.fBottom >> shift));
80}
81
82int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip,
83                             int shiftUp) {
84    SkPath::Iter    iter(path, true);
85    SkPoint         pts[4];
86    SkPath::Verb    verb;
87
88    int maxEdgeCount = path.countPoints();
89    if (iclip) {
90        // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
91        // we turn portions that are clipped out on the left/right into vertical
92        // segments.
93        maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
94    }
95    size_t maxEdgeSize = maxEdgeCount * sizeof(SkEdge);
96    size_t maxEdgePtrSize = maxEdgeCount * sizeof(SkEdge*);
97
98    // lets store the edges and their pointers in the same block
99    char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize);
100    SkEdge* edge = reinterpret_cast<SkEdge*>(storage);
101    SkEdge** edgePtr = reinterpret_cast<SkEdge**>(storage + maxEdgeSize);
102    // Record the beginning of our pointers, so we can return them to the caller
103    fEdgeList = edgePtr;
104
105    if (iclip) {
106        SkRect clip;
107        setShiftedClip(&clip, *iclip, shiftUp);
108
109        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
110            switch (verb) {
111                case SkPath::kMove_Verb:
112                case SkPath::kClose_Verb:
113                    // we ignore these, and just get the whole segment from
114                    // the corresponding line/quad/cubic verbs
115                    break;
116                case SkPath::kLine_Verb: {
117                    SkPoint lines[SkLineClipper::kMaxPoints];
118                    int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
119                    SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
120                    for (int i = 0; i < lineCount; i++) {
121                        if (edge->setLine(lines[i], lines[i + 1], shiftUp)) {
122                            *edgePtr++ = edge++;
123                        }
124                    }
125                    break;
126                }
127                default:
128                    SkDEBUGFAIL("unexpected verb");
129                    break;
130            }
131        }
132    } else {
133        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
134            switch (verb) {
135                case SkPath::kMove_Verb:
136                case SkPath::kClose_Verb:
137                    // we ignore these, and just get the whole segment from
138                    // the corresponding line/quad/cubic verbs
139                    break;
140                case SkPath::kLine_Verb:
141                    if (edge->setLine(pts[0], pts[1], shiftUp)) {
142                        *edgePtr++ = edge++;
143                    }
144                    break;
145                default:
146                    SkDEBUGFAIL("unexpected verb");
147                    break;
148            }
149        }
150    }
151    SkASSERT((char*)edge <= (char*)fEdgeList);
152    SkASSERT(edgePtr - fEdgeList <= maxEdgeCount);
153    return SkToInt(edgePtr - fEdgeList);
154}
155
156static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
157    SkPoint monoX[5];
158    int n = SkChopQuadAtYExtrema(pts, monoX);
159    for (int i = 0; i <= n; i++) {
160        builder->addQuad(&monoX[i * 2]);
161    }
162}
163
164int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip,
165                         int shiftUp) {
166    fAlloc.reset();
167    fList.reset();
168    fShiftUp = shiftUp;
169
170    SkScalar conicTol = SK_ScalarHalf * (1 << shiftUp);
171
172    if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
173        return this->buildPoly(path, iclip, shiftUp);
174    }
175
176    SkPath::Iter    iter(path, true);
177    SkPoint         pts[4];
178    SkPath::Verb    verb;
179
180    if (iclip) {
181        SkRect clip;
182        setShiftedClip(&clip, *iclip, shiftUp);
183        SkEdgeClipper clipper;
184
185        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
186            switch (verb) {
187                case SkPath::kMove_Verb:
188                case SkPath::kClose_Verb:
189                    // we ignore these, and just get the whole segment from
190                    // the corresponding line/quad/cubic verbs
191                    break;
192                case SkPath::kLine_Verb: {
193                    SkPoint lines[SkLineClipper::kMaxPoints];
194                    int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
195                    for (int i = 0; i < lineCount; i++) {
196                        this->addLine(&lines[i]);
197                    }
198                    break;
199                }
200                case SkPath::kQuad_Verb:
201                    if (clipper.clipQuad(pts, clip)) {
202                        this->addClipper(&clipper);
203                    }
204                    break;
205                case SkPath::kConic_Verb: {
206                    const int MAX_POW2 = 4;
207                    const int MAX_QUADS = 1 << MAX_POW2;
208                    const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS;
209                    SkPoint storage[MAX_QUAD_PTS];
210
211                    SkConic conic;
212                    conic.set(pts, iter.conicWeight());
213                    int pow2 = conic.computeQuadPOW2(conicTol);
214                    pow2 = SkMin32(pow2, MAX_POW2);
215                    int quadCount = conic.chopIntoQuadsPOW2(storage, pow2);
216                    SkASSERT(quadCount <= MAX_QUADS);
217                    for (int i = 0; i < quadCount; ++i) {
218                        if (clipper.clipQuad(&storage[i * 2], clip)) {
219                            this->addClipper(&clipper);
220                        }
221                    }
222                } break;
223                case SkPath::kCubic_Verb:
224                    if (clipper.clipCubic(pts, clip)) {
225                        this->addClipper(&clipper);
226                    }
227                    break;
228                default:
229                    SkDEBUGFAIL("unexpected verb");
230                    break;
231            }
232        }
233    } else {
234        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
235            switch (verb) {
236                case SkPath::kMove_Verb:
237                case SkPath::kClose_Verb:
238                    // we ignore these, and just get the whole segment from
239                    // the corresponding line/quad/cubic verbs
240                    break;
241                case SkPath::kLine_Verb:
242                    this->addLine(pts);
243                    break;
244                case SkPath::kQuad_Verb: {
245                    handle_quad(this, pts);
246                    break;
247                }
248                case SkPath::kConic_Verb: {
249                    const int MAX_POW2 = 4;
250                    const int MAX_QUADS = 1 << MAX_POW2;
251                    const int MAX_QUAD_PTS = 1 + 2 * MAX_QUADS;
252                    SkPoint storage[MAX_QUAD_PTS];
253
254                    SkConic conic;
255                    conic.set(pts, iter.conicWeight());
256                    int pow2 = conic.computeQuadPOW2(conicTol);
257                    pow2 = SkMin32(pow2, MAX_POW2);
258                    int quadCount = conic.chopIntoQuadsPOW2(storage, pow2);
259                    SkASSERT(quadCount <= MAX_QUADS);
260                    for (int i = 0; i < quadCount; ++i) {
261                        handle_quad(this, &storage[i * 2]);
262                    }
263                } break;
264                case SkPath::kCubic_Verb: {
265                    SkPoint monoY[10];
266                    int n = SkChopCubicAtYExtrema(pts, monoY);
267                    for (int i = 0; i <= n; i++) {
268                        this->addCubic(&monoY[i * 3]);
269                    }
270                    break;
271                }
272                default:
273                    SkDEBUGFAIL("unexpected verb");
274                    break;
275            }
276        }
277    }
278    fEdgeList = fList.begin();
279    return fList.count();
280}
281