SkScan_AAAPath.cpp - Android社区 - https://www.androidos.net.cn/

/*
 * 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 "SkEdge.h"
#include "SkEdgeBuilder.h"
#include "SkGeometry.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 "SkTo.h"
#include "SkUTF.h"

#include <utility>

#if defined(SK_DISABLE_AAA)
void SkScan::AAAFillPath(const SkPath& path, SkBlitter* blitter, const SkIRect& ir,
                         const SkIRect& clipBounds, bool forceRLE) {
    SkDEBUGFAIL("AAA Disabled");
    return;
}
#else
///////////////////////////////////////////////////////////////////////////////

The following is a high-level overview of our analytic anti-aliasing
algorithm. We consider a path as a collection of line segments, as
quadratic/cubic curves are converted to small line segments. Without loss of
generality, let's assume that the draw region is [0, W] x [0, H].

Our algorithm is based on horizontal scan lines (y = c_i) as the previous
sampling-based algorithm did. However, our algorithm uses non-equal-spaced
scan lines, while the previous method always uses equal-spaced scan lines,
such as (y = 1/2 + 0, 1/2 + 1, 1/2 + 2, ...) in the previous non-AA algorithm,
and (y = 1/8 + 1/4, 1/8 + 2/4, 1/8 + 3/4, ...) in the previous
16-supersampling AA algorithm.

Our algorithm contains scan lines y = c_i for c_i that is either:

1. an integer between [0, H]

2. the y value of a line segment endpoint

3. the y value of an intersection of two line segments

For two consecutive scan lines y = c_i, y = c_{i+1}, we analytically computes
the coverage of this horizontal strip of our path on each pixel. This can be
done very efficiently because the strip of our path now only consists of
trapezoids whose top and bottom edges are y = c_i, y = c_{i+1} (this includes
rectangles and triangles as special cases).

We now describe how the coverage of single pixel is computed against such a
trapezoid. That coverage is essentially the intersection area of a rectangle
(e.g., [0, 1] x [c_i, c_{i+1}]) and our trapezoid. However, that intersection
could be complicated, as shown in the example region A below:

+-----------\----+
|            \  C|
|             \  |
\              \ |
|\      A       \|
| \              \
|  \             |
| B \            |
+----\-----------+

However, we don't have to compute the area of A directly. Instead, we can
compute the excluded area, which are B and C, quite easily, because they're
just triangles. In fact, we can prove that an excluded region (take B as an
example) is either itself a simple trapezoid (including rectangles, triangles,
and empty regions), or its opposite (the opposite of B is A + C) is a simple
trapezoid. In any case, we can compute its area efficiently.

In summary, our algorithm has a higher quality because it generates ground-
truth coverages analytically. It is also faster because it has much fewer
unnessasary horizontal scan lines. For example, given a triangle path, the
number of scan lines in our algorithm is only about 3 + H while the
16-supersampling algorithm has about 4H scan lines.

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

static inline void addAlpha(SkAlpha* alpha, SkAlpha delta) {
    SkASSERT(*alpha + (int)delta <= 256);
    *alpha = SkAlphaRuns::CatchOverflow(*alpha + (int)delta);
}

static inline void safelyAddAlpha(SkAlpha* alpha, SkAlpha delta) {
    *alpha = SkTMin(0xFF, *alpha + (int)delta);
}

class AdditiveBlitter : public SkBlitter {
public:
    ~AdditiveBlitter() override {}

virtual SkBlitter* getRealBlitter(bool forceRealBlitter = false) = 0;

virtual void blitAntiH(int x, int y, const SkAlpha antialias[], int len) = 0;
    virtual void blitAntiH(int x, int y, const SkAlpha alpha) = 0;
    virtual void blitAntiH(int x, int y, int width, const SkAlpha alpha) = 0;

void blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) override {
        SkDEBUGFAIL("Please call real blitter's blitAntiH instead.");
    }

void blitV(int x, int y, int height, SkAlpha alpha) override {
        SkDEBUGFAIL("Please call real blitter's blitV instead.");
    }

void blitH(int x, int y, int width) override {
        SkDEBUGFAIL("Please call real blitter's blitH instead.");
    }

void blitRect(int x, int y, int width, int height) override {
        SkDEBUGFAIL("Please call real blitter's blitRect instead.");
    }

void blitAntiRect(int x, int y, int width, int height,
                      SkAlpha leftAlpha, SkAlpha rightAlpha) override {
        SkDEBUGFAIL("Please call real blitter's blitAntiRect instead.");
    }

virtual int getWidth() = 0;

// Flush the additive alpha cache if floor(y) and floor(nextY) is different
    // (i.e., we'll start working on a new pixel row).
    virtual void flush_if_y_changed(SkFixed y, SkFixed nextY) = 0;
};

// We need this mask blitter because it significantly accelerates small path filling.
class MaskAdditiveBlitter : public AdditiveBlitter {
public:
    MaskAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkIRect& clipBounds,
            bool isInverse);
    ~MaskAdditiveBlitter() override {
        fRealBlitter->blitMask(fMask, fClipRect);
    }

// Most of the time, we still consider this mask blitter as the real blitter
    // so we can accelerate blitRect and others. But sometimes we want to return
    // the absolute real blitter (e.g., when we fall back to the old code path).
    SkBlitter* getRealBlitter(bool forceRealBlitter) override {
        return forceRealBlitter ? fRealBlitter : this;
    }

// Virtual function is slow. So don't use this. Directly add alpha to the mask instead.
    void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override;

// Allowing following methods are used to blit rectangles during aaa_walk_convex_edges
    // Since there aren't many rectangles, we can still bear the slow speed of virtual functions.
    void blitAntiH(int x, int y, const SkAlpha alpha) override;
    void blitAntiH(int x, int y, int width, const SkAlpha alpha) override;
    void blitV(int x, int y, int height, SkAlpha alpha) override;
    void blitRect(int x, int y, int width, int height) override;
    void blitAntiRect(int x, int y, int width, int height,
                      SkAlpha leftAlpha, SkAlpha rightAlpha) override;

// The flush is only needed for RLE (RunBasedAdditiveBlitter)
    void flush_if_y_changed(SkFixed y, SkFixed nextY) override {}

int getWidth() override { return fClipRect.width(); }

static bool canHandleRect(const SkIRect& bounds) {
        int width = bounds.width();
        if (width > MaskAdditiveBlitter::kMAX_WIDTH) {
            return false;
        }
        int64_t rb = SkAlign4(width);
        // use 64bits to detect overflow
        int64_t storage = rb * bounds.height();

return (width <= MaskAdditiveBlitter::kMAX_WIDTH) &&
               (storage <= MaskAdditiveBlitter::kMAX_STORAGE);
    }

// Return a pointer where pointer[x] corresonds to the alpha of (x, y)
    inline uint8_t* getRow(int y) {
        if (y != fY) {
            fY = y;
            fRow = fMask.fImage + (y - fMask.fBounds.fTop) * fMask.fRowBytes - fMask.fBounds.fLeft;
        }
        return fRow;
    }

private:
    // so we don't try to do very wide things, where the RLE blitter would be faster
    static const int kMAX_WIDTH = 32;
    static const int kMAX_STORAGE = 1024;

SkBlitter*  fRealBlitter;
    SkMask      fMask;
    SkIRect     fClipRect;
    // we add 2 because we can write 1 extra byte at either end due to precision error
    uint32_t    fStorage[(kMAX_STORAGE >> 2) + 2];

uint8_t*    fRow;
    int         fY;
};

MaskAdditiveBlitter::MaskAdditiveBlitter(
        SkBlitter* realBlitter, const SkIRect& ir, const SkIRect& clipBounds, bool isInverse) {
    SkASSERT(canHandleRect(ir));
    SkASSERT(!isInverse);

fRealBlitter = realBlitter;

fMask.fImage    = (uint8_t*)fStorage + 1; // There's 1 extra byte at either end of fStorage
    fMask.fBounds   = ir;
    fMask.fRowBytes = ir.width();
    fMask.fFormat   = SkMask::kA8_Format;

fY = ir.fTop - 1;
    fRow = nullptr;

fClipRect = ir;
    if (!fClipRect.intersect(clipBounds)) {
        SkASSERT(0);
        fClipRect.setEmpty();
    }

memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 2);
}

void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) {
    SK_ABORT("Don't use this; directly add alphas to the mask.");
}

void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) {
    SkASSERT(x >= fMask.fBounds.fLeft -1);
    addAlpha(&this->getRow(y)[x], alpha);
}

void MaskAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) {
    SkASSERT(x >= fMask.fBounds.fLeft -1);
    uint8_t* row = this->getRow(y);
    for (int i = 0; i < width; ++i) {
        addAlpha(&row[x + i], alpha);
    }
}

void MaskAdditiveBlitter::blitV(int x, int y, int height, SkAlpha alpha) {
    if (alpha == 0) {
        return;
    }
    SkASSERT(x >= fMask.fBounds.fLeft -1);
    // This must be called as if this is a real blitter.
    // So we directly set alpha rather than adding it.
    uint8_t* row = this->getRow(y);
    for (int i = 0; i < height; ++i) {
        row[x] = alpha;
        row += fMask.fRowBytes;
    }
}

void MaskAdditiveBlitter::blitRect(int x, int y, int width, int height) {
    SkASSERT(x >= fMask.fBounds.fLeft -1);
    // This must be called as if this is a real blitter.
    // So we directly set alpha rather than adding it.
    uint8_t* row = this->getRow(y);
    for (int i = 0; i < height; ++i) {
        memset(row + x, 0xFF, width);
        row += fMask.fRowBytes;
    }
}

void MaskAdditiveBlitter::blitAntiRect(int x, int y, int width, int height,
        SkAlpha leftAlpha, SkAlpha rightAlpha) {
    blitV(x, y, height, leftAlpha);
    blitV(x + 1 + width, y, height, rightAlpha);
    blitRect(x + 1, y, width, height);
}

class RunBasedAdditiveBlitter : public AdditiveBlitter {
public:
    RunBasedAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkIRect& clipBounds,
            bool isInverse);
    ~RunBasedAdditiveBlitter() override;

SkBlitter* getRealBlitter(bool forceRealBlitter) override;

void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override;
    void blitAntiH(int x, int y, const SkAlpha alpha) override;
    void blitAntiH(int x, int y, int width, const SkAlpha alpha) override;

int getWidth() override;

void flush_if_y_changed(SkFixed y, SkFixed nextY) override {
        if (SkFixedFloorToInt(y) != SkFixedFloorToInt(nextY)) {
            this->flush();
        }
    }

protected:
    SkBlitter* fRealBlitter;

/// Current y coordinate
    int         fCurrY;
    /// Widest row of region to be blitted
    int         fWidth;
    /// Leftmost x coordinate in any row
    int         fLeft;
    /// Initial y coordinate (top of bounds).
    int         fTop;

// The next three variables are used to track a circular buffer that
    // contains the values used in SkAlphaRuns. These variables should only
    // ever be updated in advanceRuns(), and fRuns should always point to
    // a valid SkAlphaRuns...
    int         fRunsToBuffer;
    void*       fRunsBuffer;
    int         fCurrentRun;
    SkAlphaRuns fRuns;

int         fOffsetX;

inline bool check(int x, int width) const {
        #ifdef SK_DEBUG
        if (x < 0 || x + width > fWidth) {
            // SkDebugf("Ignore x = %d, width = %d\n", x, width);
        }
        #endif
        return (x >= 0 && x + width <= fWidth);
    }

// extra one to store the zero at the end
    inline int getRunsSz() const { return (fWidth + 1 + (fWidth + 2)/2) * sizeof(int16_t); }

// This function updates the fRuns variable to point to the next buffer space
    // with adequate storage for a SkAlphaRuns. It mostly just advances fCurrentRun
    // and resets fRuns to point to an empty scanline.
    inline void advanceRuns() {
        const size_t kRunsSz = this->getRunsSz();
        fCurrentRun = (fCurrentRun + 1) % fRunsToBuffer;
        fRuns.fRuns = reinterpret_cast<int16_t*>(
            reinterpret_cast<uint8_t*>(fRunsBuffer) + fCurrentRun * kRunsSz);
        fRuns.fAlpha = reinterpret_cast<SkAlpha*>(fRuns.fRuns + fWidth + 1);
        fRuns.reset(fWidth);
    }

// Blitting 0xFF and 0 is much faster so we snap alphas close to them
    inline SkAlpha snapAlpha(SkAlpha alpha) {
        return alpha > 247 ? 0xFF : alpha < 8 ? 0 : alpha;
    }

inline void flush() {
        if (fCurrY >= fTop) {
            SkASSERT(fCurrentRun < fRunsToBuffer);
            for (int x = 0; fRuns.fRuns[x]; x += fRuns.fRuns[x]) {
                // It seems that blitting 255 or 0 is much faster than blitting 254 or 1
                fRuns.fAlpha[x] = snapAlpha(fRuns.fAlpha[x]);
            }
            if (!fRuns.empty()) {
                // SkDEBUGCODE(fRuns.dump();)
                fRealBlitter->blitAntiH(fLeft, fCurrY, fRuns.fAlpha, fRuns.fRuns);
                this->advanceRuns();
                fOffsetX = 0;
            }
            fCurrY = fTop - 1;
        }
    }

inline void checkY(int y) {
        if (y != fCurrY) {
            this->flush();
            fCurrY = y;
        }
    }
};

RunBasedAdditiveBlitter::RunBasedAdditiveBlitter(
        SkBlitter* realBlitter, const SkIRect& ir, const SkIRect& clipBounds, bool isInverse) {
    fRealBlitter = realBlitter;

SkIRect sectBounds;
    if (isInverse) {
        // We use the clip bounds instead of the ir, since we may be asked to
        //draw outside of the rect when we're a inverse filltype
        sectBounds = clipBounds;
    } else {
        if (!sectBounds.intersect(ir, clipBounds)) {
            sectBounds.setEmpty();
        }
    }

const int left = sectBounds.left();
    const int right = sectBounds.right();

fLeft = left;
    fWidth = right - left;
    fTop = sectBounds.top();
    fCurrY = fTop - 1;

fRunsToBuffer = realBlitter->requestRowsPreserved();
    fRunsBuffer = realBlitter->allocBlitMemory(fRunsToBuffer * this->getRunsSz());
    fCurrentRun = -1;

this->advanceRuns();

fOffsetX = 0;
}

RunBasedAdditiveBlitter::~RunBasedAdditiveBlitter() {
    this->flush();
}

SkBlitter* RunBasedAdditiveBlitter::getRealBlitter(bool forceRealBlitter) {
    return fRealBlitter;
}

void RunBasedAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) {
    checkY(y);
    x -= fLeft;

if (x < 0) {
        len += x;
        antialias -= x;
        x = 0;
    }
    len = SkTMin(len, fWidth - x);
    SkASSERT(check(x, len));