/* * 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 "include/core/SkColor.h" #include "include/core/SkPath.h" #include "include/core/SkPathTypes.h" #include "include/core/SkRect.h" #include "include/private/base/SkAlign.h" #include "include/private/base/SkAssert.h" #include "include/private/base/SkDebug.h" #include "include/private/base/SkFixed.h" #include "include/private/base/SkMath.h" #include "include/private/base/SkSafe32.h" #include "include/private/base/SkTo.h" #include "src/base/SkTSort.h" #include "src/core/SkAlphaRuns.h" #include "src/core/SkAnalyticEdge.h" #include "src/core/SkBlitter.h" #include "src/core/SkEdge.h" #include "src/core/SkEdgeBuilder.h" #include "src/core/SkMask.h" #include "src/core/SkScan.h" #include "src/core/SkScanPriv.h" #include <algorithm> #include <cstdint> #include <cstring> /* 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 void add_alpha(SkAlpha* alpha, SkAlpha delta) { … } static void safely_add_alpha(SkAlpha* alpha, SkAlpha delta) { … } class AdditiveBlitter : public SkBlitter { … }; // We need this mask blitter because it significantly accelerates small path filling. class MaskAdditiveBlitter : public AdditiveBlitter { … }; MaskAdditiveBlitter::MaskAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkIRect& clipBounds, bool isInverse) : … { … } void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) { … } void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) { … } void MaskAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) { … } void MaskAdditiveBlitter::blitV(int x, int y, int height, SkAlpha alpha) { … } void MaskAdditiveBlitter::blitRect(int x, int y, int width, int height) { … } void MaskAdditiveBlitter::blitAntiRect(int x, int y, int width, int height, SkAlpha leftAlpha, SkAlpha rightAlpha) { … } class RunBasedAdditiveBlitter : public AdditiveBlitter { … }; RunBasedAdditiveBlitter::RunBasedAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkIRect& clipBounds, bool isInverse) { … } void RunBasedAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) { … } void RunBasedAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) { … } void RunBasedAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) { … } // This exists specifically for concave path filling. // In those cases, we can easily accumulate alpha greater than 0xFF. class SafeRLEAdditiveBlitter : public RunBasedAdditiveBlitter { … }; void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) { … } void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) { … } void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) { … } // Return the alpha of a trapezoid whose height is 1 static SkAlpha trapezoid_to_alpha(SkFixed l1, SkFixed l2) { … } // The alpha of right-triangle (a, a*b) static SkAlpha partial_triangle_to_alpha(SkFixed a, SkFixed b) { … } static SkAlpha get_partial_alpha(SkAlpha alpha, SkFixed partialHeight) { … } static SkAlpha get_partial_alpha(SkAlpha alpha, SkAlpha fullAlpha) { … } // For SkFixed that's close to SK_Fixed1, we can't convert it to alpha by just shifting right. // For example, when f = SK_Fixed1, right shifting 8 will get 256, but we need 255. // This is rarely the problem so we'll only use this for blitting rectangles. static SkAlpha fixed_to_alpha(SkFixed f) { … } // Suppose that line (l1, y)-(r1, y+1) intersects with (l2, y)-(r2, y+1), // approximate (very coarsely) the x coordinate of the intersection. static SkFixed approximate_intersection(SkFixed l1, SkFixed r1, SkFixed l2, SkFixed r2) { … } // Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0] static void compute_alpha_above_line(SkAlpha* alphas, SkFixed l, SkFixed r, SkFixed dY, SkAlpha fullAlpha) { … } // Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0] static void compute_alpha_below_line(SkAlpha* alphas, SkFixed l, SkFixed r, SkFixed dY, SkAlpha fullAlpha) { … } // Note that if fullAlpha != 0xFF, we'll multiply alpha by fullAlpha static void blit_single_alpha(AdditiveBlitter* blitter, int y, int x, SkAlpha alpha, SkAlpha fullAlpha, SkAlpha* maskRow, bool noRealBlitter) { … } static void blit_two_alphas(AdditiveBlitter* blitter, int y, int x, SkAlpha a1, SkAlpha a2, SkAlpha fullAlpha, SkAlpha* maskRow, bool noRealBlitter) { … } static void blit_full_alpha(AdditiveBlitter* blitter, int y, int x, int len, SkAlpha fullAlpha, SkAlpha* maskRow, bool noRealBlitter) { … } static void blit_aaa_trapezoid_row(AdditiveBlitter* blitter, int y, SkFixed ul, SkFixed ur, SkFixed ll, SkFixed lr, SkFixed lDY, SkFixed rDY, SkAlpha fullAlpha, SkAlpha* maskRow, bool noRealBlitter) { … } static void blit_trapezoid_row(AdditiveBlitter* blitter, int y, SkFixed ul, SkFixed ur, SkFixed ll, SkFixed lr, SkFixed lDY, SkFixed rDY, SkAlpha fullAlpha, SkAlpha* maskRow, bool noRealBlitter) { … } static bool operator<(const SkAnalyticEdge& a, const SkAnalyticEdge& b) { … } static SkAnalyticEdge* sort_edges(SkAnalyticEdge* list[], int count, SkAnalyticEdge** last) { … } static void validate_sort(const SkAnalyticEdge* edge) { … } // For an edge, we consider it smooth if the Dx doesn't change much, and Dy is large enough // For curves that are updating, the Dx is not changing much if fQDx/fCDx and fQDy/fCDy are // relatively large compared to fQDDx/QCDDx and fQDDy/fCDDy static bool is_smooth_enough(SkAnalyticEdge* thisEdge, SkAnalyticEdge* nextEdge, int stop_y) { … } // Check if the leftE and riteE are changing smoothly in terms of fDX. // If yes, we can later skip the fractional y and directly jump to integer y. static bool is_smooth_enough(SkAnalyticEdge* leftE, SkAnalyticEdge* riteE, SkAnalyticEdge* currE, int stop_y) { … } static void aaa_walk_convex_edges(SkAnalyticEdge* prevHead, AdditiveBlitter* blitter, int start_y, int stop_y, SkFixed leftBound, SkFixed riteBound, bool isUsingMask) { … } static void update_next_next_y(SkFixed y, SkFixed nextY, SkFixed* nextNextY) { … } static void check_intersection(const SkAnalyticEdge* edge, SkFixed nextY, SkFixed* nextNextY) { … } static void check_intersection_fwd(const SkAnalyticEdge* edge, SkFixed nextY, SkFixed* nextNextY) { … } static void insert_new_edges(SkAnalyticEdge* newEdge, SkFixed y, SkFixed* nextNextY) { … } static void validate_edges_for_y(const SkAnalyticEdge* edge, SkFixed y) { … } // Return true if prev->fX, next->fX are too close in the current pixel row. static bool edges_too_close(SkAnalyticEdge* prev, SkAnalyticEdge* next, SkFixed lowerY) { … } // This function exists for the case where the previous rite edge is removed because // its fLowerY <= nextY static bool edges_too_close(int prevRite, SkFixed ul, SkFixed ll) { … } static void aaa_walk_edges(SkAnalyticEdge* prevHead, SkAnalyticEdge* nextTail, SkPathFillType fillType, AdditiveBlitter* blitter, int start_y, int stop_y, SkFixed leftClip, SkFixed rightClip, bool isUsingMask, bool forceRLE, bool skipIntersect) { … } static void aaa_fill_path(const SkPath& path, const SkIRect& clipRect, AdditiveBlitter* blitter, int start_y, int stop_y, bool pathContainedInClip, bool isUsingMask, bool forceRLE) { … } // Check if the path is a rect and fat enough after clipping; if so, blit it. static inline bool try_blit_fat_anti_rect(SkBlitter* blitter, const SkPath& path, const SkIRect& clip) { … } void SkScan::AAAFillPath(const SkPath& path, SkBlitter* blitter, const SkIRect& ir, const SkIRect& clipBounds, bool forceRLE) { … }
Codebase Browser
chromium