SkEdgeBuilder.cpp revision d36baa7a4a5ae3cc94cc4a45379f55658f80c0a6 
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 "SkEdgeClipper.h"
11#include "SkLineClipper.h"
12#include "SkGeometry.h"
13
14template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) {
15    return static_cast<T*>(alloc.allocThrow(sizeof(T)));
16}
17
18///////////////////////////////////////////////////////////////////////////////
19
20SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {
21    fEdgeList = nullptr;
22}
23
24SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical(const SkEdge* edge, SkEdge* last) {
25    if (last->fCurveCount || last->fDX || edge->fX != last->fX) {
26        return kNo_Combine;
27    }
28    if (edge->fWinding == last->fWinding) {
29        if (edge->fLastY + 1 == last->fFirstY) {
30            last->fFirstY = edge->fFirstY;
31            return kPartial_Combine;
32        }
33        if (edge->fFirstY == last->fLastY + 1) {
34            last->fLastY = edge->fLastY;
35            return kPartial_Combine;
36        }
37        return kNo_Combine;
38    }
39    if (edge->fFirstY == last->fFirstY) {
40        if (edge->fLastY == last->fLastY) {
41            return kTotal_Combine;
42        }
43        if (edge->fLastY < last->fLastY) {
44            last->fFirstY = edge->fLastY + 1;
45            return kPartial_Combine;
46        }
47        last->fFirstY = last->fLastY + 1;
48        last->fLastY = edge->fLastY;
49        last->fWinding = edge->fWinding;
50        return kPartial_Combine;
51    }
52    if (edge->fLastY == last->fLastY) {
53        if (edge->fFirstY > last->fFirstY) {
54            last->fLastY = edge->fFirstY - 1;
55            return kPartial_Combine;
56        }
57        last->fLastY = last->fFirstY - 1;
58        last->fFirstY = edge->fFirstY;
59        last->fWinding = edge->fWinding;
60        return kPartial_Combine;
61    }
62    return kNo_Combine;
63}
64
65static bool vertical_line(const SkEdge* edge) {
66    return !edge->fDX && !edge->fCurveCount;
67}
68
69void SkEdgeBuilder::addLine(const SkPoint pts[]) {
70    SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
71    if (edge->setLine(pts[0], pts[1], fShiftUp)) {
72        if (vertical_line(edge) && fList.count()) {
73            Combine combine = CombineVertical(edge, *(fList.end() - 1));
74            if (kNo_Combine != combine) {
75                if (kTotal_Combine == combine) {
76                    fList.pop();
77                }
78                goto unallocate_edge;
79            }
80        }
81        fList.push(edge);
82    } else {
83unallocate_edge:
84        ;
85        // TODO: unallocate edge from storage...
86    }
87}
88
89void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
90    SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc);
91    if (edge->setQuadratic(pts, fShiftUp)) {
92        fList.push(edge);
93    } else {
94        // TODO: unallocate edge from storage...
95    }
96}
97
98void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
99    SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc);
100    if (edge->setCubic(pts, fShiftUp)) {
101        fList.push(edge);
102    } else {
103        // TODO: unallocate edge from storage...
104    }
105}
106
107void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
108    SkPoint      pts[4];
109    SkPath::Verb verb;
110
111    while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
112        switch (verb) {
113            case SkPath::kLine_Verb:
114                this->addLine(pts);
115                break;
116            case SkPath::kQuad_Verb:
117                this->addQuad(pts);
118                break;
119            case SkPath::kCubic_Verb:
120                this->addCubic(pts);
121                break;
122            default:
123                break;
124        }
125    }
126}
127
128///////////////////////////////////////////////////////////////////////////////
129
130static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
131    dst->set(SkIntToScalar(src.fLeft >> shift),
132             SkIntToScalar(src.fTop >> shift),
133             SkIntToScalar(src.fRight >> shift),
134             SkIntToScalar(src.fBottom >> shift));
135}
136
137SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge** edgePtr) {
138    return !vertical_line(edge) || edgePtr <= fEdgeList ? kNo_Combine :
139            CombineVertical(edge, edgePtr[-1]);
140}
141
142int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp,
143                             bool canCullToTheRight) {
144    SkPath::Iter    iter(path, true);
145    SkPoint         pts[4];
146    SkPath::Verb    verb;
147
148    int maxEdgeCount = path.countPoints();
149    if (iclip) {
150        // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
151        // we turn portions that are clipped out on the left/right into vertical
152        // segments.
153        maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
154    }
155    size_t maxEdgeSize = maxEdgeCount * sizeof(SkEdge);
156    size_t maxEdgePtrSize = maxEdgeCount * sizeof(SkEdge*);
157
158    // lets store the edges and their pointers in the same block
159    char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize);
160    SkEdge* edge = reinterpret_cast<SkEdge*>(storage);
161    SkEdge** edgePtr = reinterpret_cast<SkEdge**>(storage + maxEdgeSize);
162    // Record the beginning of our pointers, so we can return them to the caller
163    fEdgeList = edgePtr;
164
165    if (iclip) {
166        SkRect clip;
167        setShiftedClip(&clip, *iclip, shiftUp);
168
169        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
170            switch (verb) {
171                case SkPath::kMove_Verb:
172                case SkPath::kClose_Verb:
173                    // we ignore these, and just get the whole segment from
174                    // the corresponding line/quad/cubic verbs
175                    break;
176                case SkPath::kLine_Verb: {
177                    SkPoint lines[SkLineClipper::kMaxPoints];
178                    int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
179                    SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
180                    for (int i = 0; i < lineCount; i++) {
181                        if (edge->setLine(lines[i], lines[i + 1], shiftUp)) {
182                            Combine combine = checkVertical(edge, edgePtr);
183                            if (kNo_Combine == combine) {
184                                *edgePtr++ = edge++;
185                            } else if (kTotal_Combine == combine) {
186                                --edgePtr;
187                            }
188                        }
189                    }
190                    break;
191                }
192                default:
193                    SkDEBUGFAIL("unexpected verb");
194                    break;
195            }
196        }
197    } else {
198        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
199            switch (verb) {
200                case SkPath::kMove_Verb:
201                case SkPath::kClose_Verb:
202                    // we ignore these, and just get the whole segment from
203                    // the corresponding line/quad/cubic verbs
204                    break;
205                case SkPath::kLine_Verb:
206                    if (edge->setLine(pts[0], pts[1], shiftUp)) {
207                        Combine combine = checkVertical(edge, edgePtr);
208                        if (kNo_Combine == combine) {
209                            *edgePtr++ = edge++;
210                        } else if (kTotal_Combine == combine) {
211                            --edgePtr;
212                        }
213                    }
214                    break;
215                default:
216                    SkDEBUGFAIL("unexpected verb");
217                    break;
218            }
219        }
220    }
221    SkASSERT((char*)edge <= (char*)fEdgeList);
222    SkASSERT(edgePtr - fEdgeList <= maxEdgeCount);
223    return SkToInt(edgePtr - fEdgeList);
224}
225
226static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
227    SkPoint monoX[5];
228    int n = SkChopQuadAtYExtrema(pts, monoX);
229    for (int i = 0; i <= n; i++) {
230        builder->addQuad(&monoX[i * 2]);
231    }
232}
233
234int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp,
235                         bool canCullToTheRight) {
236    fAlloc.reset();
237    fList.reset();
238    fShiftUp = shiftUp;
239
240    if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
241        return this->buildPoly(path, iclip, shiftUp, canCullToTheRight);
242    }
243
244    SkAutoConicToQuads quadder;
245    const SkScalar conicTol = SK_Scalar1 / 4;
246
247    SkPath::Iter    iter(path, true);
248    SkPoint         pts[4];
249    SkPath::Verb    verb;
250
251    if (iclip) {
252        SkRect clip;
253        setShiftedClip(&clip, *iclip, shiftUp);
254        SkEdgeClipper clipper(canCullToTheRight);
255
256        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
257            switch (verb) {
258                case SkPath::kMove_Verb:
259                case SkPath::kClose_Verb:
260                    // we ignore these, and just get the whole segment from
261                    // the corresponding line/quad/cubic verbs
262                    break;
263                case SkPath::kLine_Verb: {
264                    SkPoint lines[SkLineClipper::kMaxPoints];
265                    int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
266                    for (int i = 0; i < lineCount; i++) {
267                        this->addLine(&lines[i]);
268                    }
269                    break;
270                }
271                case SkPath::kQuad_Verb:
272                    if (clipper.clipQuad(pts, clip)) {
273                        this->addClipper(&clipper);
274                    }
275                    break;
276                case SkPath::kConic_Verb: {
277                    const SkPoint* quadPts = quadder.computeQuads(
278                                          pts, iter.conicWeight(), conicTol);
279                    for (int i = 0; i < quadder.countQuads(); ++i) {
280                        if (clipper.clipQuad(quadPts, clip)) {
281                            this->addClipper(&clipper);
282                        }
283                        quadPts += 2;
284                    }
285                } break;
286                case SkPath::kCubic_Verb:
287                    if (clipper.clipCubic(pts, clip)) {
288                        this->addClipper(&clipper);
289                    }
290                    break;
291                default:
292                    SkDEBUGFAIL("unexpected verb");
293                    break;
294            }
295        }
296    } else {
297        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
298            switch (verb) {
299                case SkPath::kMove_Verb:
300                case SkPath::kClose_Verb:
301                    // we ignore these, and just get the whole segment from
302                    // the corresponding line/quad/cubic verbs
303                    break;
304                case SkPath::kLine_Verb:
305                    this->addLine(pts);
306                    break;
307                case SkPath::kQuad_Verb: {
308                    handle_quad(this, pts);
309                    break;
310                }
311                case SkPath::kConic_Verb: {
312                    const SkPoint* quadPts = quadder.computeQuads(
313                                          pts, iter.conicWeight(), conicTol);
314                    for (int i = 0; i < quadder.countQuads(); ++i) {
315                        handle_quad(this, quadPts);
316                        quadPts += 2;
317                    }
318                } break;
319                case SkPath::kCubic_Verb: {
320                    SkPoint monoY[10];
321                    int n = SkChopCubicAtYExtrema(pts, monoY);
322                    for (int i = 0; i <= n; i++) {
323                        this->addCubic(&monoY[i * 3]);
324                    }
325                    break;
326                }
327                default:
328                    SkDEBUGFAIL("unexpected verb");
329                    break;
330            }
331        }
332    }
333    fEdgeList = fList.begin();
334    return fList.count();
335}
336