FastLED 3.10.10
Loading...
Searching...
No Matches
poly_abuffer.h File Reference

Detailed Description

A-buffer 8x4 antialiased polygon fill (fast, low-stack backend)

Alternate fill backend for drawPolygon (see fl::gfx::PolyFill::ABuffer).

Algorithm

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 model

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.

Deviations from the Go reference (documented)

  1. No static edge ordering. The reference advances edgeStart/ edgeEnd monotonically through a pre-sorted edge list, which requires the edges' x-order to be constant across all scanlines. That holds for the parallelogram (line) shapes TinyGL builds, but breaks for self-intersecting polygons: once two edges' x-order flips (the crossing point), the scan starts at the wrong edge and the part of the polygon on the far side is never painted. This kernel instead collects every crossing of every active edge up front (per scanline, in O(nedges) work) and jumps directly between crossing pixels — correct for arbitrary (even self-intersecting) polygons at negligible cost for the small vertex counts this library targets.
  2. i64 edge state. The reference uses int32 for xinc/xstart and int32-wrapping products in 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).
  3. Off-canvas-left edges. The reference's x-loop starts at the first edge's xleft and rebuilds mask state from there; polygons that extend past the left canvas edge need that state reconstructed. This kernel seeds the row mask with the parity of edges already left of the canvas (X_r < 0) so fully clipped polygons fill correctly.
  4. Floor (not truncate) division. The reference's integer divisions truncate toward zero (Go semantics); this kernel floors (repository convention). At most a 1/8-px (one subpixel) AA difference.
  5. Full pixels saturate at 255. A mask with all 32 bits set yields br = 255 (the reference's popcount << 3 would wrap to 0 there; its full-span fast path is what actually keeps that case from shipping).
  6. Off-grid vertices. The reference's shapes (line parallelograms) have every vertex on the sub-row grid by construction, so its half-open [ytop, ybottom) edge ranges never claim one sub-row twice. Arbitrary Q16 vertices can sit mid-sub-row, where the naive floor/ceil ranges make both edges sharing the vertex claim its sub-row — three crossings on one sub-row, and the even-odd rule fills a spurious tail to the canvas edge. This kernel instead activates a sub-row only when the edge's segment reaches its TOP grid line (ceil/ceil ranges, see the integer model above), which assigns the vertex's sub-row to exactly one of its edges.

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 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).
 

Class Documentation

◆ fl::gfx::detail::AbEdge

struct fl::gfx::detail::AbEdge
Class Members
u8 corr[4]
int py0
int py1
i64 q
i64 x0
i64 xinc
i32 ybot
i32 ytop