aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/SkScan_DAAPath.cpp
blob: d4860daf2241a65bd01df23b7969aaba62eb1ce9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
/*
 * Copyright 2016 The Android Open Source Project
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "SkAnalyticEdge.h"
#include "SkAntiRun.h"
#include "SkAutoMalloc.h"
#include "SkBlitter.h"
#include "SkCoverageDelta.h"
#include "SkEdge.h"
#include "SkEdgeBuilder.h"
#include "SkGeometry.h"
#include "SkMask.h"
#include "SkPath.h"
#include "SkQuadClipper.h"
#include "SkRasterClip.h"
#include "SkRegion.h"
#include "SkScan.h"
#include "SkScanPriv.h"
#include "SkTSort.h"
#include "SkTemplates.h"
#include "SkUtils.h"

///////////////////////////////////////////////////////////////////////////////

/*

DAA stands for Delta-based Anti-Aliasing.

This is an improved version of our analytic AA algorithm (in SkScan_AAAPath.cpp)
which first scan convert paths into coverage deltas (this step can happen out of order,
and we don't seem to be needed to worry about the intersection, clamping, etc.),
and then use a single blitter run to convert all those deltas into the final alphas.

Before we go to the final blitter run, we'll use SkFixed for all delta values so we
don't ever have to worry about under/overflow.

*/

///////////////////////////////////////////////////////////////////////////////

// The following helper functions are the same as those from SkScan_AAAPath.cpp
// except that we use SkFixed everywhere instead of SkAlpha.

static inline SkFixed SkFixedMul_lowprec(SkFixed a, SkFixed b) {
    return (a >> 8) * (b >> 8);
}

// Return the alpha of a trapezoid whose height is 1
static inline SkFixed trapezoidToAlpha(SkFixed l1, SkFixed l2) {
    SkASSERT(l1 >= 0 && l2 >= 0);
    return (l1 + l2) >> 1;
}

// The alpha of right-triangle (a, a*b)
static inline SkFixed partialTriangleToAlpha(SkFixed a, SkFixed b) {
    SkASSERT(a <= SK_Fixed1);
    // SkFixedMul(SkFixedMul(a, a), b) >> 1
    // return ((((a >> 8) * (a >> 8)) >> 8) * (b >> 8)) >> 1;
    return (a >> 11) * (a >> 11) * (b >> 11);
}

static inline SkFixed getPartialAlpha(SkFixed alpha, SkFixed partialMultiplier) {
    // DAA should not be so sensitive to the precision (compared to AAA).
    return SkFixedMul_lowprec(alpha, partialMultiplier);
}

///////////////////////////////////////////////////////////////////////////////

template<bool isPartial, class Deltas>
static inline void add_coverage_delta_segment(int y, SkFixed rowHeight, const SkAnalyticEdge* edge,
        SkFixed nextX, Deltas* deltas) { // rowHeight=fullAlpha
    SkASSERT(rowHeight <= SK_Fixed1 && rowHeight >= 0);

    // Let's see if multiplying sign is faster than multiplying edge->fWinding.
    // (Compiler should be able to optimize multiplication with 1/-1?)
    int sign = edge->fWinding == 1 ? 1 : -1;

    SkFixed l = SkTMin(edge->fX, nextX);
    SkFixed r = edge->fX + nextX - l;
    int     L = SkFixedFloorToInt(l);
    int     R = SkFixedCeilToInt(r);
    int     len = R - L;

    switch (len) {
        case 0: {
            deltas->addDelta(L, y, rowHeight * sign);
            return;
        }
        case 1: {
            SkFixed fixedR  = SkIntToFixed(R);
            SkFixed alpha   = trapezoidToAlpha(fixedR - l, fixedR - r);
            if (isPartial) {
                alpha = getPartialAlpha(alpha, rowHeight);
            }
            deltas->addDelta(L,     y,  alpha * sign);
            deltas->addDelta(L + 1, y,  (rowHeight - alpha) * sign);
            return;
        }
        case 2: {
            SkFixed middle  = SkIntToFixed(L + 1);
            SkFixed x1      = middle - l;
            SkFixed x2      = r - middle;
            SkFixed alpha1  = partialTriangleToAlpha(x1, edge->fDY);
            SkFixed alpha2  = rowHeight - partialTriangleToAlpha(x2, edge->fDY);
            deltas->addDelta(L,     y,  alpha1 * sign);
            deltas->addDelta(L + 1, y,  (alpha2 - alpha1) * sign);
            deltas->addDelta(L + 2, y,  (rowHeight - alpha2) * sign);
            return;
        }
    }

    // When len > 2, computations are similar to computeAlphaAboveLine in SkScan_AAAPath.cpp
    SkFixed dY      = edge->fDY;
    SkFixed fixedL  = SkIntToFixed(L);
    SkFixed fixedR  = SkIntToFixed(R);
    SkFixed first   = SK_Fixed1 + fixedL - l; // horizontal edge of the left-most triangle
    SkFixed last    = r - (fixedR - SK_Fixed1); // horizontal edge of the right-most triangle
    SkFixed firstH  = SkFixedMul_lowprec(first, dY); // vertical edge of the left-most triangle

    SkFixed alpha0  = SkFixedMul_lowprec(first, firstH) >> 1;   // triangle alpha
    SkFixed alpha1  = firstH + (dY >> 1);                       // rectangle plus triangle
    deltas->addDelta(L, y, alpha0 * sign);
    deltas->addDelta(L + 1, y, (alpha1 - alpha0) * sign);
    for(int i = 2; i < len - 1; ++i) {
        deltas->addDelta(L + i, y, dY * sign); // the increment is always a rect of height = dY
    }

    SkFixed alphaR2     = alpha1 + dY * (len - 3);                      // the alpha at R - 2
    SkFixed lastAlpha   = rowHeight - partialTriangleToAlpha(last, dY); // the alpha at R - 1
    deltas->addDelta(R - 1, y, (lastAlpha - alphaR2) * sign);
    deltas->addDelta(R,     y, (rowHeight - lastAlpha) * sign);
}

class XLessThan {
public:
    bool operator()(const SkBezier* a, const SkBezier* b) {
        return a->fP0.fX + a->fP1.fX < b->fP0.fX + b->fP1.fX;
    }
};

class YLessThan {
public:
    bool operator()(const SkBezier* a, const SkBezier* b) {
        return a->fP0.fY + a->fP1.fY < b->fP0.fY + b->fP1.fY;
    }
};

template<class Deltas> static SK_ALWAYS_INLINE
void gen_alpha_deltas(const SkPath& path, const SkIRect& clipBounds, Deltas& result,
        SkBlitter* blitter, bool skipRect, bool pathContainedInClip) {
    // 1. Build edges
    SkEdgeBuilder builder;
    SkIRect ir               = path.getBounds().roundOut();
    int  count               = builder.build_edges(path, &clipBounds, 0, pathContainedInClip,
                                                   SkEdgeBuilder::kBezier);
    if (count == 0) {
        return;
    }
    SkBezier** list = builder.bezierList();

    // 2. Try to find the rect part because blitAntiRect is so much faster than blitCoverageDeltas
    int rectTop = ir.fBottom;   // the rect is initialized to be empty as top = bot
    int rectBot = ir.fBottom;
    if (skipRect) {             // only find that rect is skipRect == true
        YLessThan lessThan;     // sort edges in YX order
        SkTQSort(list, list + count - 1, lessThan);
        for(int i = 0; i < count - 1; ++i) {
            SkBezier* lb = list[i];
            SkBezier* rb = list[i + 1];

            // fCount == 2 ensures that lb and rb are lines instead of quads or cubics.
            bool lDX0 = lb->fP0.fX == lb->fP1.fX && lb->fCount == 2;
            bool rDX0 = rb->fP0.fX == rb->fP1.fX && rb->fCount == 2;
            if (!lDX0 || !rDX0) { // make sure that the edges are vertical
                continue;
            }

            SkAnalyticEdge l, r;
            l.setLine(lb->fP0, lb->fP1);
            r.setLine(rb->fP0, rb->fP1);

            SkFixed xorUpperY = l.fUpperY ^ r.fUpperY;
            SkFixed xorLowerY = l.fLowerY ^ r.fLowerY;
            if ((xorUpperY | xorLowerY) == 0) { // equal upperY and lowerY
                rectTop = SkFixedCeilToInt(l.fUpperY);
                rectBot = SkFixedFloorToInt(l.fLowerY);
                if (rectBot > rectTop) { // if bot == top, the rect is too short for blitAntiRect
                    int L = SkFixedCeilToInt(l.fUpperX);
                    int R = SkFixedFloorToInt(r.fUpperX);
                    if (L <= R) {
                        SkAlpha la = (SkIntToFixed(L) - l.fUpperX) >> 8;
                        SkAlpha ra = (r.fUpperX - SkIntToFixed(R)) >> 8;
                        result.setAntiRect(L - 1, rectTop, R - L, rectBot - rectTop, la, ra);
                    } else { // too thin to use blitAntiRect; reset the rect region to be emtpy
                        rectTop = rectBot = ir.fBottom;
                    }
                }
                break;
            }

        }
    }

    // 3. Sort edges in x so we may need less sorting for delta based on x. This only helps
    //    SkCoverageDeltaList. And we don't want to sort more than SORT_THRESHOLD edges where
    //    the log(count) factor of the quick sort may become a bottleneck; when there are so
    //    many edges, we're unlikely to make deltas sorted anyway.
    constexpr int SORT_THRESHOLD = 256;
    if (std::is_same<Deltas, SkCoverageDeltaList>::value && count < SORT_THRESHOLD) {
        XLessThan lessThan;
        SkTQSort(list, list + count - 1, lessThan);
    }

    // Future todo: parallize and SIMD the following code.
    // 4. iterate through edges and generate deltas
    for(int index = 0; index < count; ++index) {
        SkAnalyticCubicEdge storage;
        SkASSERT(sizeof(SkAnalyticQuadraticEdge) >= sizeof(SkAnalyticEdge));
        SkASSERT(sizeof(SkAnalyticCubicEdge) >= sizeof(SkAnalyticQuadraticEdge));

        SkBezier* bezier        = list[index];
        SkAnalyticEdge* currE   = &storage;
        bool edgeSet            = false;

        int originalWinding = 1;
        bool sortY = true;
        switch (bezier->fCount) {
            case 2: {
                edgeSet = currE->setLine(bezier->fP0, bezier->fP1);
                originalWinding = currE->fWinding;
                break;
            }
            case 3: {
                SkQuad* quad = static_cast<SkQuad*>(bezier);
                SkPoint pts[3] = {quad->fP0, quad->fP1, quad->fP2};
                edgeSet = static_cast<SkAnalyticQuadraticEdge*>(currE)->setQuadratic(pts);
                originalWinding = static_cast<SkAnalyticQuadraticEdge*>(currE)->fQEdge.fWinding;
                break;
            }
            case 4: {
                sortY = false;
                SkCubic* cubic = static_cast<SkCubic*>(bezier);
                SkPoint pts[4] = {cubic->fP0, cubic->fP1, cubic->fP2, cubic->fP3};
                edgeSet = static_cast<SkAnalyticCubicEdge*>(currE)->setCubic(pts, sortY);
                originalWinding = static_cast<SkAnalyticCubicEdge*>(currE)->fCEdge.fWinding;
                break;
            }
        }

        if (!edgeSet) {
            continue;
        }

        do {
            currE->fX =  currE->fUpperX;

            SkFixed upperFloor  = SkFixedFloorToFixed(currE->fUpperY);
            SkFixed lowerCeil   = SkFixedCeilToFixed(currE->fLowerY);
            int     iy          = SkFixedFloorToInt(upperFloor);

            if (lowerCeil <= upperFloor + SK_Fixed1) { // only one row is affected by the currE
                SkFixed rowHeight = currE->fLowerY - currE->fUpperY;
                SkFixed nextX = currE->fX + SkFixedMul(currE->fDX, rowHeight);
                if (iy >= clipBounds.fTop && iy < clipBounds.fBottom) {
                    add_coverage_delta_segment<true>(iy, rowHeight, currE, nextX, &result);
                }
                continue;
            }

            // check first row
            SkFixed rowHeight = upperFloor + SK_Fixed1 - currE->fUpperY;
            SkFixed nextX;
            if (rowHeight != SK_Fixed1) {   // it's a partial row
                nextX = currE->fX + SkFixedMul(currE->fDX, rowHeight);
                add_coverage_delta_segment<true>(iy, rowHeight, currE, nextX, &result);
            } else {                        // it's a full row so we can leave it to the while loop
                iy--;                       // compensate the iy++ in the while loop
                nextX = currE->fX;
            }

            while (true) { // process the full rows in the middle
                iy++;
                SkFixed y = SkIntToFixed(iy);
                currE->fX = nextX;
                nextX += currE->fDX;

                if (y + SK_Fixed1 > currE->fLowerY) {
                    break; // no full rows left, break
                }

                // Check whether we're in the rect part that will be covered by blitAntiRect
                if (iy >= rectTop && iy < rectBot) {
                    SkASSERT(currE->fDX == 0);  // If yes, we must be on an edge with fDX = 0.
                    iy = rectBot - 1;           // Skip the rect part by advancing iy to the bottom.
                    continue;
                }

                // Add current edge's coverage deltas on this full row
                add_coverage_delta_segment<false>(iy, SK_Fixed1, currE, nextX, &result);
            }

            // last partial row
            if (SkIntToFixed(iy) < currE->fLowerY &&
                    iy >= clipBounds.fTop && iy < clipBounds.fBottom) {
                rowHeight = currE->fLowerY - SkIntToFixed(iy);
                nextX = currE->fX + SkFixedMul(currE->fDX, rowHeight);
                add_coverage_delta_segment<true>(iy, rowHeight, currE, nextX, &result);
            }
        // Intended assignment to fWinding to restore the maybe-negated winding (during updateLine)
        } while ((currE->fWinding = originalWinding) && currE->update(currE->fLowerY, sortY));
    }
}

// For threaded backend with out-of-order init-once, we probably have to take care of the
// blitRegion, sk_blit_above, sk_blit_below in SkScan::AntiFillPath to maintain the draw order. If
// we do that, be caureful that blitRect may throw exception if the rect is empty.
void SkScan::DAAFillPath(const SkPath& path, SkBlitter* blitter, const SkIRect& ir,
                         const SkIRect& clipBounds, bool containedInClip, bool forceRLE) {
#if !defined(SK_SUPPORT_LEGACY_AA_BEHAVIOR)
    containedInClip = clipBounds.contains(ir);
#endif
    bool isEvenOdd  = path.getFillType() & 1;
    bool isConvex   = path.isConvex();
    bool isInverse  = path.isInverseFillType();
    bool skipRect   = isConvex && !isInverse;

    SkIRect clippedIR = ir;
    clippedIR.intersect(clipBounds);

    // The overhead of even constructing SkCoverageDeltaList/Mask is too big.
    // So TryBlitFatAntiRect and return if it's successful.
    if (!isInverse && TryBlitFatAntiRect(blitter, path, clipBounds)) {
        return;
    }

#ifdef GOOGLE3
    constexpr int STACK_SIZE = 12 << 10; // 12K stack size alloc; Google3 has 16K limit.
#else
    constexpr int STACK_SIZE = 64 << 10; // 64k stack size to avoid heap allocation
#endif
    SkSTArenaAlloc<STACK_SIZE> alloc; // avoid heap allocation with SkSTArenaAlloc

    // Only blitter->blitXXX needs to be done in order in the threaded backend.
    // Everything before can be done out of order in the threaded backend.
    if (!forceRLE && !isInverse && SkCoverageDeltaMask::Suitable(clippedIR)) {
        SkCoverageDeltaMask deltaMask(&alloc, clippedIR);
        gen_alpha_deltas(path, clipBounds, deltaMask, blitter, skipRect, containedInClip);
        deltaMask.convertCoverageToAlpha(isEvenOdd, isInverse, isConvex);
        blitter->blitMask(deltaMask.prepareSkMask(), clippedIR);
    } else {
        SkCoverageDeltaList deltaList(&alloc, clippedIR.fTop, clippedIR.fBottom, forceRLE);
        gen_alpha_deltas(path, clipBounds, deltaList, blitter, skipRect, containedInClip);
        blitter->blitCoverageDeltas(&deltaList, clipBounds, isEvenOdd, isInverse, isConvex);
    }
}