SkEdgeBuilder.cpp revision c8d640b1788822a8697816b645c327383a1d1f20 
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], NULL, 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], NULL, 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], NULL, 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 edgePtr - fEdgeList;
154}
155
156int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip,
157                         int shiftUp) {
158    fAlloc.reset();
159    fList.reset();
160    fShiftUp = shiftUp;
161
162    if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
163        return this->buildPoly(path, iclip, shiftUp);
164    }
165
166    SkPath::Iter    iter(path, true);
167    SkPoint         pts[4];
168    SkPath::Verb    verb;
169
170    if (iclip) {
171        SkRect clip;
172        setShiftedClip(&clip, *iclip, shiftUp);
173        SkEdgeClipper clipper;
174
175        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
176            switch (verb) {
177                case SkPath::kMove_Verb:
178                case SkPath::kClose_Verb:
179                    // we ignore these, and just get the whole segment from
180                    // the corresponding line/quad/cubic verbs
181                    break;
182                case SkPath::kLine_Verb: {
183                    SkPoint lines[SkLineClipper::kMaxPoints];
184                    int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
185                    for (int i = 0; i < lineCount; i++) {
186                        this->addLine(&lines[i]);
187                    }
188                    break;
189                }
190                case SkPath::kQuad_Verb:
191                    if (clipper.clipQuad(pts, clip)) {
192                        this->addClipper(&clipper);
193                    }
194                    break;
195                case SkPath::kCubic_Verb:
196                    if (clipper.clipCubic(pts, clip)) {
197                        this->addClipper(&clipper);
198                    }
199                    break;
200                default:
201                    SkDEBUGFAIL("unexpected verb");
202                    break;
203            }
204        }
205    } else {
206        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
207            switch (verb) {
208                case SkPath::kMove_Verb:
209                case SkPath::kClose_Verb:
210                    // we ignore these, and just get the whole segment from
211                    // the corresponding line/quad/cubic verbs
212                    break;
213                case SkPath::kLine_Verb:
214                    this->addLine(pts);
215                    break;
216                case SkPath::kQuad_Verb: {
217                    SkPoint monoX[5];
218                    int n = SkChopQuadAtYExtrema(pts, monoX);
219                    for (int i = 0; i <= n; i++) {
220                        this->addQuad(&monoX[i * 2]);
221                    }
222                    break;
223                }
224                case SkPath::kCubic_Verb: {
225                    SkPoint monoY[10];
226                    int n = SkChopCubicAtYExtrema(pts, monoY);
227                    for (int i = 0; i <= n; i++) {
228                        this->addCubic(&monoY[i * 3]);
229                    }
230                    break;
231                }
232                default:
233                    SkDEBUGFAIL("unexpected verb");
234                    break;
235            }
236        }
237    }
238    fEdgeList = fList.begin();
239    return fList.count();
240}
241
242