SkEdgeBuilder.cpp revision 451ceba3544fa1ff810378f1e9a47c7d20f48a9f 
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
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 = nullptr;
23}
24
25SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical(const SkEdge* edge, SkEdge* last) {
26    if (last->fCurveCount || last->fDX || edge->fX != last->fX) {
27        return kNo_Combine;
28    }
29    if (edge->fWinding == last->fWinding) {
30        if (edge->fLastY + 1 == last->fFirstY) {
31            last->fFirstY = edge->fFirstY;
32            return kPartial_Combine;
33        }
34        if (edge->fFirstY == last->fLastY + 1) {
35            last->fLastY = edge->fLastY;
36            return kPartial_Combine;
37        }
38        return kNo_Combine;
39    }
40    if (edge->fFirstY == last->fFirstY) {
41        if (edge->fLastY == last->fLastY) {
42            return kTotal_Combine;
43        }
44        if (edge->fLastY < last->fLastY) {
45            last->fFirstY = edge->fLastY + 1;
46            return kPartial_Combine;
47        }
48        last->fFirstY = last->fLastY + 1;
49        last->fLastY = edge->fLastY;
50        last->fWinding = edge->fWinding;
51        return kPartial_Combine;
52    }
53    if (edge->fLastY == last->fLastY) {
54        if (edge->fFirstY > last->fFirstY) {
55            last->fLastY = edge->fFirstY - 1;
56            return kPartial_Combine;
57        }
58        last->fLastY = last->fFirstY - 1;
59        last->fFirstY = edge->fFirstY;
60        last->fWinding = edge->fWinding;
61        return kPartial_Combine;
62    }
63    return kNo_Combine;
64}
65
66static inline bool approximatelyEqual(SkFixed a, SkFixed b) {
67    return SkAbs32(a - b) < 0x100;
68}
69
70SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical(
71        const SkAnalyticEdge* edge, SkAnalyticEdge* last) {
72    SkASSERT(fAnalyticAA);
73    if (last->fCurveCount || last->fDX || edge->fX != last->fX) {
74        return kNo_Combine;
75    }
76    if (edge->fWinding == last->fWinding) {
77        if (edge->fLowerY == last->fUpperY) {
78            last->fUpperY = edge->fUpperY;
79            last->fY = last->fUpperY;
80            return kPartial_Combine;
81        }
82        if (approximatelyEqual(edge->fUpperY, last->fLowerY)) {
83            last->fLowerY = edge->fLowerY;
84            return kPartial_Combine;
85        }
86        return kNo_Combine;
87    }
88    if (approximatelyEqual(edge->fUpperY, last->fUpperY)) {
89        if (approximatelyEqual(edge->fLowerY, last->fLowerY)) {
90            return kTotal_Combine;
91        }
92        if (edge->fLowerY < last->fLowerY) {
93            last->fUpperY = edge->fLowerY;
94            last->fY = last->fUpperY;
95            return kPartial_Combine;
96        }
97        last->fUpperY = last->fLowerY;
98        last->fY = last->fUpperY;
99        last->fLowerY = edge->fLowerY;
100        last->fWinding = edge->fWinding;
101        return kPartial_Combine;
102    }
103    if (approximatelyEqual(edge->fLowerY, last->fLowerY)) {
104        if (edge->fUpperY > last->fUpperY) {
105            last->fLowerY = edge->fUpperY;
106            return kPartial_Combine;
107        }
108        last->fLowerY = last->fUpperY;
109        last->fUpperY = edge->fUpperY;
110        last->fY = last->fUpperY;
111        last->fWinding = edge->fWinding;
112        return kPartial_Combine;
113    }
114    return kNo_Combine;
115}
116
117bool SkEdgeBuilder::vertical_line(const SkEdge* edge) {
118    return !edge->fDX && !edge->fCurveCount;
119}
120
121bool SkEdgeBuilder::vertical_line(const SkAnalyticEdge* edge) {
122    SkASSERT(fAnalyticAA);
123    return !edge->fDX && !edge->fCurveCount;
124}
125
126void SkEdgeBuilder::addLine(const SkPoint pts[]) {
127    if (fAnalyticAA) {
128        SkAnalyticEdge* edge = typedAllocThrow<SkAnalyticEdge>(fAlloc);
129        if (edge->setLine(pts[0], pts[1])) {
130            if (vertical_line(edge) && fList.count()) {
131                Combine combine = CombineVertical(edge, (SkAnalyticEdge*)*(fList.end() - 1));
132                if (kNo_Combine != combine) {
133                    if (kTotal_Combine == combine) {
134                        fList.pop();
135                    }
136                    goto unallocate_analytic_edge;
137                }
138            }
139            fList.push(edge);
140        } else {
141unallocate_analytic_edge:
142            ;
143            // TODO: unallocate edge from storage...
144        }
145    } else {
146        SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
147        if (edge->setLine(pts[0], pts[1], fShiftUp)) {
148            if (vertical_line(edge) && fList.count()) {
149                Combine combine = CombineVertical(edge, (SkEdge*)*(fList.end() - 1));
150                if (kNo_Combine != combine) {
151                    if (kTotal_Combine == combine) {
152                        fList.pop();
153                    }
154                    goto unallocate_edge;
155                }
156            }
157            fList.push(edge);
158        } else {
159unallocate_edge:
160            ;
161            // TODO: unallocate edge from storage...
162        }
163    }
164}
165
166void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
167    if (fAnalyticAA) {
168        SkAnalyticQuadraticEdge* edge = typedAllocThrow<SkAnalyticQuadraticEdge>(fAlloc);
169        if (edge->setQuadratic(pts)) {
170            fList.push(edge);
171        } else {
172            // TODO: unallocate edge from storage...
173        }
174    } else {
175        SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc);
176        if (edge->setQuadratic(pts, fShiftUp)) {
177            fList.push(edge);
178        } else {
179            // TODO: unallocate edge from storage...
180        }
181    }
182}
183
184void SkEdgeBuilder::addCubic(const SkPoint pts[]) {
185    if (fAnalyticAA) {
186        SkAnalyticCubicEdge* edge = typedAllocThrow<SkAnalyticCubicEdge>(fAlloc);
187        if (edge->setCubic(pts)) {
188            fList.push(edge);
189        } else {
190            // TODO: unallocate edge from storage...
191        }
192    } else {
193        SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc);
194        if (edge->setCubic(pts, fShiftUp)) {
195            fList.push(edge);
196        } else {
197            // TODO: unallocate edge from storage...
198        }
199    }
200}
201
202void SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) {
203    SkPoint      pts[4];
204    SkPath::Verb verb;
205
206    while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) {
207        switch (verb) {
208            case SkPath::kLine_Verb:
209                this->addLine(pts);
210                break;
211            case SkPath::kQuad_Verb:
212                this->addQuad(pts);
213                break;
214            case SkPath::kCubic_Verb:
215                this->addCubic(pts);
216                break;
217            default:
218                break;
219        }
220    }
221}
222
223///////////////////////////////////////////////////////////////////////////////
224
225static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
226    dst->set(SkIntToScalar(src.fLeft >> shift),
227             SkIntToScalar(src.fTop >> shift),
228             SkIntToScalar(src.fRight >> shift),
229             SkIntToScalar(src.fBottom >> shift));
230}
231
232SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge** edgePtr) {
233    return !vertical_line(edge) || edgePtr <= (SkEdge**)fEdgeList ? kNo_Combine :
234            CombineVertical(edge, edgePtr[-1]);
235}
236
237SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkAnalyticEdge* edge,
238        SkAnalyticEdge** edgePtr) {
239    SkASSERT(fAnalyticAA);
240    return !vertical_line(edge) || edgePtr <= (SkAnalyticEdge**)fEdgeList ? kNo_Combine :
241            CombineVertical(edge, edgePtr[-1]);
242}
243
244int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp,
245                             bool canCullToTheRight) {
246    SkPath::Iter    iter(path, true);
247    SkPoint         pts[4];
248    SkPath::Verb    verb;
249
250    int maxEdgeCount = path.countPoints();
251    if (iclip) {
252        // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
253        // we turn portions that are clipped out on the left/right into vertical
254        // segments.
255        maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
256    }
257    size_t edgeSize = fAnalyticAA ? sizeof(SkAnalyticEdge) : sizeof(SkEdge);
258    size_t maxEdgeSize = maxEdgeCount * edgeSize;
259    size_t maxEdgePtrSize = maxEdgeCount * sizeof(char*);
260
261    // lets store the edges and their pointers in the same block
262    char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize);
263    char* edge = (char*)storage;
264    char** edgePtr = (char**)(storage + maxEdgeSize);
265    // Record the beginning of our pointers, so we can return them to the caller
266    fEdgeList = (void**)edgePtr;
267
268    if (iclip) {
269        SkRect clip;
270        setShiftedClip(&clip, *iclip, shiftUp);
271
272        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
273            switch (verb) {
274                case SkPath::kMove_Verb:
275                case SkPath::kClose_Verb:
276                    // we ignore these, and just get the whole segment from
277                    // the corresponding line/quad/cubic verbs
278                    break;
279                case SkPath::kLine_Verb: {
280                    SkPoint lines[SkLineClipper::kMaxPoints];
281                    int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
282                    SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
283                    for (int i = 0; i < lineCount; i++) {
284                        bool setLineResult = fAnalyticAA ?
285                                ((SkAnalyticEdge*)edge)->setLine(lines[i], lines[i + 1]) :
286                                ((SkEdge*)edge)->setLine(lines[i], lines[i + 1], shiftUp);
287                        if (setLineResult) {
288                            Combine combine = fAnalyticAA ?
289                                    checkVertical((SkAnalyticEdge*)edge, (SkAnalyticEdge**)edgePtr) :
290                                    checkVertical((SkEdge*)edge, (SkEdge**)edgePtr);
291                            if (kNo_Combine == combine) {
292                                *edgePtr++ = edge;
293                                edge += edgeSize;
294                            } else if (kTotal_Combine == combine) {
295                                --edgePtr;
296                            }
297                        }
298                    }
299                    break;
300                }
301                default:
302                    SkDEBUGFAIL("unexpected verb");
303                    break;
304            }
305        }
306    } else {
307        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
308            switch (verb) {
309                case SkPath::kMove_Verb:
310                case SkPath::kClose_Verb:
311                    // we ignore these, and just get the whole segment from
312                    // the corresponding line/quad/cubic verbs
313                    break;
314                case SkPath::kLine_Verb: {
315                    bool setLineResult = fAnalyticAA ?
316                            ((SkAnalyticEdge*)edge)->setLine(pts[0], pts[1]) :
317                            ((SkEdge*)edge)->setLine(pts[0], pts[1], shiftUp);
318                    if (setLineResult) {
319                        Combine combine = fAnalyticAA ?
320                                checkVertical((SkAnalyticEdge*)edge, (SkAnalyticEdge**)edgePtr) :
321                                checkVertical((SkEdge*)edge, (SkEdge**)edgePtr);
322                        if (kNo_Combine == combine) {
323                            *edgePtr++ = edge;
324                            edge += edgeSize;
325                        } else if (kTotal_Combine == combine) {
326                            --edgePtr;
327                        }
328                    }
329                    break;
330                }
331                default:
332                    SkDEBUGFAIL("unexpected verb");
333                    break;
334            }
335        }
336    }
337    SkASSERT((char*)edge <= (char*)fEdgeList);
338    SkASSERT(edgePtr - (char**)fEdgeList <= maxEdgeCount);
339    return SkToInt(edgePtr - (char**)fEdgeList);
340}
341
342static void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) {
343    SkPoint monoX[5];
344    int n = SkChopQuadAtYExtrema(pts, monoX);
345    for (int i = 0; i <= n; i++) {
346        builder->addQuad(&monoX[i * 2]);
347    }
348}
349
350int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp,
351                         bool canCullToTheRight, bool analyticAA) {
352    fAlloc.reset();
353    fList.reset();
354    fShiftUp = shiftUp;
355    fAnalyticAA = analyticAA;
356
357    if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
358        return this->buildPoly(path, iclip, shiftUp, canCullToTheRight);
359    }
360
361    SkAutoConicToQuads quadder;
362    const SkScalar conicTol = SK_Scalar1 / 4;
363
364    SkPath::Iter    iter(path, true);
365    SkPoint         pts[4];
366    SkPath::Verb    verb;
367
368    if (iclip) {
369        SkRect clip;
370        setShiftedClip(&clip, *iclip, shiftUp);
371        SkEdgeClipper clipper(canCullToTheRight);
372
373        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
374            switch (verb) {
375                case SkPath::kMove_Verb:
376                case SkPath::kClose_Verb:
377                    // we ignore these, and just get the whole segment from
378                    // the corresponding line/quad/cubic verbs
379                    break;
380                case SkPath::kLine_Verb: {
381                    SkPoint lines[SkLineClipper::kMaxPoints];
382                    int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
383                    for (int i = 0; i < lineCount; i++) {
384                        this->addLine(&lines[i]);
385                    }
386                    break;
387                }
388                case SkPath::kQuad_Verb:
389                    if (clipper.clipQuad(pts, clip)) {
390                        this->addClipper(&clipper);
391                    }
392                    break;
393                case SkPath::kConic_Verb: {
394                    const SkPoint* quadPts = quadder.computeQuads(
395                                          pts, iter.conicWeight(), conicTol);
396                    for (int i = 0; i < quadder.countQuads(); ++i) {
397                        if (clipper.clipQuad(quadPts, clip)) {
398                            this->addClipper(&clipper);
399                        }
400                        quadPts += 2;
401                    }
402                } break;
403                case SkPath::kCubic_Verb:
404                    if (clipper.clipCubic(pts, clip)) {
405                        this->addClipper(&clipper);
406                    }
407                    break;
408                default:
409                    SkDEBUGFAIL("unexpected verb");
410                    break;
411            }
412        }
413    } else {
414        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
415            switch (verb) {
416                case SkPath::kMove_Verb:
417                case SkPath::kClose_Verb:
418                    // we ignore these, and just get the whole segment from
419                    // the corresponding line/quad/cubic verbs
420                    break;
421                case SkPath::kLine_Verb:
422                    this->addLine(pts);
423                    break;
424                case SkPath::kQuad_Verb: {
425                    handle_quad(this, pts);
426                    break;
427                }
428                case SkPath::kConic_Verb: {
429                    const SkPoint* quadPts = quadder.computeQuads(
430                                          pts, iter.conicWeight(), conicTol);
431                    for (int i = 0; i < quadder.countQuads(); ++i) {
432                        handle_quad(this, quadPts);
433                        quadPts += 2;
434                    }
435                } break;
436                case SkPath::kCubic_Verb: {
437                    SkPoint monoY[10];
438                    int n = SkChopCubicAtYExtrema(pts, monoY);
439                    for (int i = 0; i <= n; i++) {
440                        this->addCubic(&monoY[i * 3]);
441                    }
442                    break;
443                }
444                default:
445                    SkDEBUGFAIL("unexpected verb");
446                    break;
447            }
448        }
449    }
450    fEdgeList = fList.begin();
451    return fList.count();
452}
453