|
FastLED 3.10.10
|
A-buffer 8x4 antialiased polygon fill (fast, low-stack backend)
Alternate fill backend for drawPolygon (see fl::gfx::PolyFill::ABuffer).
Based on the A-buffer scanline approach described at https://aykevl.nl/2024/02/tinygl-polygon/ (TinyGL, aykevl), which in turn follows the A-buffer algorithm (Grossetete, 1991). Each pixel carries a 32-bit mask — an 8 x 4 grid of subpixels — and the alpha channel is the popcount of the mask (32 distinct levels, br = min(255, popcount * 8)).
Every non-horizontal polygon edge is treated as a trapezoid: the edge itself plus the horizontal region to its right. XOR-ing the trapezoid masks of all edges reproduces the polygon under the even-odd rule (the same rule the exact backend, drawPolygonCore, uses). Scanlines are rendered left to right; when an edge crosses a pixel its per-sub-row mask is XOR-ed into the running mask, and between pixels the mask is "extended" with mask = (mask & 0x01010101) * 255 — two operations that turn a set rightmost subpixel of each row into a full row for the next pixel (the trapezoid continues to the right).
Integer-only (repository convention): coordinates in Q16.16, sub-rows in .2 (4 per pixel). A sub-row is active for an edge when its TOP grid line lies within the edge's [ytop_q, ybot_q) span — the edge's segment reaches the sub-row's top. On the grid, a vertex shared by two edges belongs to exactly one of them; mid-sub-row, the vertex's sub-row belongs to the edge that ends there (its partner starts at the next sub-row), so no sub-row is claimed twice and the per-sub-row even-odd crossing set stays consistent. The edge's crossing of a sub-row is its line's x at the sub-row's top grid line, measured exactly from the top vertex in Q16 (never snapped to the sub-row grid), so a vertex mid-sub-row introduces no quantization shift. Per edge, once at setup: xinc = floor(65536 * B / dy) (one i64 division, i64 result) Per scanline, per active edge: x0 += xinc (i64 add, no libgcc). Per sub-row: X_r = X_0 + r * q + corr[r] (shifts/adds + a 2-bit table, no per-sub-row multiply). The per-pixel work is shifts, XORs and a popcount — no division anywhere in the scan loops, which is what keeps the kernel off the deep 64-bit libgcc chain the exact backend needs for its per-pixel area integration.
sublineY * xinc / 4; that wraps for steep or long edges (even on small canvases with sub-pixel-dy edges). This kernel uses i64 (exact across the ±8191 px domain).Sampling geometry (kept faithful to the reference): sub-row r covers the half-open band [y + r/4, y + (r+1)/4) and sub-column c counts as covered when its RIGHT edge x + (c+1)/8 lies strictly to the right of the edge crossing (the edge's line at the sub-row's top grid line, see the integer model above; a sample exactly on the edge is outside).
Definition in file poly_abuffer.h.
#include "fl/stl/noexcept.h"#include "fl/stl/static_assert.h"#include "fl/stl/int.h"#include "fl/math/fixed_point/s16x16.h"#include "fl/gfx/canvas.h"#include "fastled_progmem.h"
Include dependency graph for poly_abuffer.h:
This graph shows which files directly or indirectly include this file:Go to the source code of this file.
Classes | |
| struct | fl::gfx::detail::AbEdge |
| Per-edge scanline state. More... | |
Namespaces | |
| namespace | fl |
| Base definition for an LED controller. | |
| namespace | fl::gfx |
| namespace | fl::gfx::detail |
| ============================================================================ | |
Macros | |
| #define | FL_POLYAB_POP2(n) |
| 256-entry byte popcount table (PROGMEM on AVR), generated by macro recursion rather than typed out: a hand-typed copy had 16 wrong entries (bytes 0x58..0x5F and 0x98..0x9F), which made ABuffer drop subpixels on AVR only. | |
| #define | FL_POLYAB_POP4(n) |
| #define | FL_POLYAB_POP6(n) |
Functions | |
| template<typename PixelT, typename Coord, bool Overwrite, int MAXN> | |
| void | fl::gfx::detail::drawPolygonABufferCore (Canvas< PixelT > &canvas, const PixelT &color, fl::span< const PolyPoint< Coord > > pts) FL_NO_EXCEPT |
| A-buffer 8x4 antialiased polygon fill (see file header). | |
| fl::u8 | fl::gfx::detail::polyABAlpha (fl::u32 mask) FL_NO_EXCEPT |
| Alpha (0..255) for an 8x4 mask: 8 per subpixel, saturating at 255 (32 subpixels would otherwise wrap a u8). | |
| fl::i32 | fl::gfx::detail::polyABClampPx (float px) FL_NO_EXCEPT |
| Float -> Q16.16, clamped to ±8191 px. | |
| template<typename PixelT> | |
| void | fl::gfx::detail::polyABFillRun (PixelT *pixels, int py, int width, int x0, int x1, const PixelT &color, fl::u8 br, bool overwrite) FL_NO_EXCEPT |
Fill a run of [x0, x1) pixels of row py with color at alpha br. | |
| fl::i64 | fl::gfx::detail::polyABFloorDivI64 (fl::i64 a, fl::i64 b) FL_NO_EXCEPT |
| Floor-divide a by positive b (rounds toward -inf). | |
| fl::u8 | fl::gfx::detail::polyABPop8 (fl::u8 v) FL_NO_EXCEPT |
| Popcount of a byte. | |
| const fl::u8 * | fl::gfx::detail::polyABPop8Table () FL_NO_EXCEPT |
| fl::u8 | fl::gfx::detail::polyABPopcount32 (fl::u32 v) FL_NO_EXCEPT |
| template<typename Coord> | |
| fl::i32 | fl::gfx::detail::polyABToQ16 (Coord val) FL_NO_EXCEPT |
| Convert any Coord type to Q16.16, clamped to ±8191 px. | |
| template<> | |
| fl::i32 | fl::gfx::detail::polyABToQ16< double > (double val) FL_NO_EXCEPT |
| template<> | |
| fl::i32 | fl::gfx::detail::polyABToQ16< fl::s16x16 > (fl::s16x16 val) FL_NO_EXCEPT |
| template<> | |
| fl::i32 | fl::gfx::detail::polyABToQ16< float > (float val) FL_NO_EXCEPT |
| template<> | |
| fl::i32 | fl::gfx::detail::polyABToQ16< int > (int val) FL_NO_EXCEPT |
Variables | |
| static const fl::i32 | fl::gfx::detail::polyABQ16Max = 8191L << 16 |
| Maximum |vertex coordinate| accepted, in Q16.16 units (8191 px keeps all values and edge deltas in i32 with headroom — same bound as the exact kernel). | |