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, 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, int shiftUp,
83                             bool canCullToTheRight) {
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, canCullToTheRight);
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, int shiftUp,
165                         bool canCullToTheRight) {
166    fAlloc.reset();
167    fList.reset();
168    fShiftUp = shiftUp;
169
170    if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
171        return this->buildPoly(path, iclip, shiftUp, canCullToTheRight);
172    }
173
174    SkAutoConicToQuads quadder;
175    const SkScalar conicTol = SK_Scalar1 / 4;
176
177    SkPath::Iter    iter(path, true);
178    SkPoint         pts[4];
179    SkPath::Verb    verb;
180
181    if (iclip) {
182        SkRect clip;
183        setShiftedClip(&clip, *iclip, shiftUp);
184        SkEdgeClipper clipper(canCullToTheRight);
185
186        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
187            switch (verb) {
188                case SkPath::kMove_Verb:
189                case SkPath::kClose_Verb:
190                    // we ignore these, and just get the whole segment from
191                    // the corresponding line/quad/cubic verbs
192                    break;
193                case SkPath::kLine_Verb: {
194                    SkPoint lines[SkLineClipper::kMaxPoints];
195                    int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
196                    for (int i = 0; i < lineCount; i++) {
197                        this->addLine(&lines[i]);
198                    }
199                    break;
200                }
201                case SkPath::kQuad_Verb:
202                    if (clipper.clipQuad(pts, clip)) {
203                        this->addClipper(&clipper);
204                    }
205                    break;
206                case SkPath::kConic_Verb: {
207                    const SkPoint* quadPts = quadder.computeQuads(
208                                          pts, iter.conicWeight(), conicTol);
209                    for (int i = 0; i < quadder.countQuads(); ++i) {
210                        if (clipper.clipQuad(quadPts, clip)) {
211                            this->addClipper(&clipper);
212                        }
213                        quadPts += 2;
214                    }
215                } break;
216                case SkPath::kCubic_Verb:
217                    if (clipper.clipCubic(pts, clip)) {
218                        this->addClipper(&clipper);
219                    }
220                    break;
221                default:
222                    SkDEBUGFAIL("unexpected verb");
223                    break;
224            }
225        }
226    } else {
227        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
228            switch (verb) {
229                case SkPath::kMove_Verb:
230                case SkPath::kClose_Verb:
231                    // we ignore these, and just get the whole segment from
232                    // the corresponding line/quad/cubic verbs
233                    break;
234                case SkPath::kLine_Verb:
235                    this->addLine(pts);
236                    break;
237                case SkPath::kQuad_Verb: {
238                    handle_quad(this, pts);
239                    break;
240                }
241                case SkPath::kConic_Verb: {
242                    const SkPoint* quadPts = quadder.computeQuads(
243                                          pts, iter.conicWeight(), conicTol);
244                    for (int i = 0; i < quadder.countQuads(); ++i) {
245                        handle_quad(this, quadPts);
246                        quadPts += 2;
247                    }
248                } break;
249                case SkPath::kCubic_Verb: {
250                    SkPoint monoY[10];
251                    int n = SkChopCubicAtYExtrema(pts, monoY);
252                    for (int i = 0; i <= n; i++) {
253                        this->addCubic(&monoY[i * 3]);
254                    }
255                    break;
256                }
257                default:
258                    SkDEBUGFAIL("unexpected verb");
259                    break;
260            }
261        }
262    }
263    fEdgeList = fList.begin();
264    return fList.count();
265}
266