FastLED 3.10.10
Loading...
Searching...
No Matches

◆ drawPolygonABufferCore()

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

A-buffer 8x4 antialiased polygon fill (see file header).

MAXN caps the vertex count (vertices beyond it are ignored, polygon closes from #MAXN-1 back to #0 — same as the exact kernel). There is no accumulator to size: the working set is the per-edge state plus one u32 mask, so the stack stays shallow regardless of canvas size. It still scales with MAXN: vertices (8*MAXN B) + edges (40-48*MAXN B) + crossing events (16*MAXN B), too much for an AVR Uno at MAXN = 32, so the default MAXN is platform-dependent (measured frames at FL_GFX_POLYGON_DEFAULT_MAXN in fl/gfx/canvas.h).

Definition at line 275 of file poly_abuffer.h.

276 {
277 FL_STATIC_ASSERT(MAXN >= 3 && MAXN <= 256, "drawPolygon: MAXN must be in [3, 256]");
278 const fl::i32 n = static_cast<fl::i32>(pts.size());
279 if (n < 3) return;
280 PixelT* pixels = canvas.pixels;
281 int width = canvas.width;
282 int height = canvas.height;
283 if (width <= 0 || height <= 0) return;
284
285 const int nv = (n < MAXN) ? n : MAXN;
286
287 // Convert vertices to Q16.16 (clamped to ±8191 px — i32-safe)
288 fl::i32 vx[MAXN];
289 fl::i32 vy[MAXN];
290 for (int i = 0; i < nv; ++i) {
291 vx[i] = polyABToQ16(pts[i].x);
292 vy[i] = polyABToQ16(pts[i].y);
293 }
294
295 // Build per-edge scanline state. One i64 floor division per edge is
296 // the only division in this function (it sets xinc exactly).
297 AbEdge edges[MAXN];
298 int nedges = 0;
299 int ymin = height, ymax = -1;
300 for (int i = 0; i < nv; ++i) {
301 const int j = (i + 1 == nv) ? 0 : (i + 1);
302 const fl::i32 dy = vy[j] - vy[i];
303 if (dy == 0) continue; // horizontal edge: no trapezoid (even-odd convention)
304 // Orient edge top-to-bottom: B measured from the top vertex
305 fl::i32 ytop_q, xtop, B;
306 if (dy > 0) { ytop_q = vy[i]; xtop = vx[i]; B = vx[j] - vx[i]; }
307 else { ytop_q = vy[j]; xtop = vx[j]; B = vx[i] - vx[j]; }
308 const fl::i32 dy2 = (dy > 0) ? dy : -dy; // span height, > 0
309 const fl::i32 ybot_q = ytop_q + dy2;
310
311 // Active pixel rows: same floor/ceil row rule as the exact kernel
312 // (the row containing ytop through the row containing ybot - 1)
313 int py0 = ytop_q >> 16;
314 int py1 = (ybot_q - 1) >> 16;
315 if (py0 < 0) py0 = 0;
316 if (py1 >= height) py1 = height - 1;
317 if (py0 > py1) continue; // edge off-canvas vertically
318
319 AbEdge& e = edges[nedges++];
320 e.py0 = py0;
321 e.py1 = py1;
322 // In-range sub-rows, .2 (4 per px), half-open [ytop, ybot): a
323 // sub-row is in range when its TOP grid line (s*16384 Q16) lies in
324 // the edge's [ytop_q, ybot_q) span — the segment reaches the
325 // sub-row's top. On the grid, a vertex shared by two edges
326 // belongs to exactly one of them; mid-sub-row, the vertex's
327 // sub-row belongs to the edge that ENDS there (its partner starts
328 // at the next sub-row), so no sub-row is claimed twice and the
329 // per-sub-row even-odd crossing set stays consistent.
330 e.ytop = (ytop_q + 16383) >> 14;
331 e.ybot = (ybot_q + 16383) >> 14;
332 // i64 step: |65536 * B| < 2^47, dy >= 1 -> exact floor, no wrap
333 e.xinc = polyABFloorDivI64((fl::i64)65536L * (fl::i64)B, (fl::i64)dy2);
334 e.q = e.xinc >> 2;
335
336 // x0: the edge's line at the TOP grid line of py0's sub-row 0,
337 // measured exactly from the top vertex in Q16: off = 65536*py0 -
338 // ytop_q, so a vertex mid-sub-row introduces no quantization
339 // shift. Every in-range sub-row's top lies within the segment
340 // (see [ytop, ybot) above), so the line value there is valid for
341 // either xinc sign — no clamping needed. off*xinc stays in i64
342 // (same bound as the vertex-snapped seed this replaces).
343 const fl::i64 off = ((fl::i64)py0 << 16) - (fl::i64)ytop_q;
344 e.x0 = (fl::i64)xtop + polyABFloorDivI64(off * e.xinc, 65536L);
345 // corr[r] = floor((n0 + r*16384*m)/65536), n0 = (off*xinc) mod
346 // 65536 in [0, 65536): the exact per-sub-row correction for the
347 // fractional part of xinc/4. X_r = xtop + floor((off + r*16384)
348 // * xinc / 65536) holds exactly, and the row advance (x0 +=
349 // xinc) is exact because off gains a multiple of 65536 per row.
350 const fl::i32 m = (fl::i32)(e.xinc & 3); // in [0, 4)
351 const fl::i64 n0 = ((off & 65535L) * (e.xinc & 65535L)) & 65535L;
352 e.corr[0] = 0;
353 e.corr[1] = (fl::u8)((n0 + 16384L * (fl::i64)m) >> 16);
354 e.corr[2] = (fl::u8)((n0 + 2L * 16384L * (fl::i64)m) >> 16);
355 e.corr[3] = (fl::u8)((n0 + 3L * 16384L * (fl::i64)m) >> 16);
356
357 if (e.py0 < ymin) ymin = e.py0;
358 if (e.py1 > ymax) ymax = e.py1;
359 }
360 if (nedges == 0) return;
361
362 // Per-row scratch: crossing events, packed (pixel << 5) | (row << 3) |
363 // bitOffset. A sub-row crosses at most ONE pixel (its crossing X is
364 // fixed for the scanline), so a row has at most 4*nedges events.
365 fl::i32 cp[4 * MAXN];
366
367 for (int py = ymin; py <= ymax; ++py) {
368 fl::u32 mask = 0; // the running 8x4 mask (per row: 0x00 or 0xFF)
369 int ncp = 0;
370
371 for (int e = 0; e < nedges; ++e) {
372 AbEdge& ed = edges[e];
373 if (py < ed.py0 || py > ed.py1) continue;
374 if (py > ed.py0) ed.x0 += ed.xinc;
375 // In-range sub-rows: ytop <= 4*py + r < ybot, r in [0, 4).
376 // i32 until clamped: for an edge starting above the canvas,
377 // ytop - 4*py reaches -4*8191 - 4*py (polyABQ16Max in .2 units),
378 // past a 16-bit int (AVR).
379 const fl::i32 sub = (fl::i32)4 * py;
380 fl::i32 rlo32 = ed.ytop - sub; // <= 4; 4 only at py0
381 // (vertex below the row's top) -> skipped via rlo > rhi
382 if (rlo32 < 0) rlo32 = 0;
383 fl::i32 rhi32 = ed.ybot - 1 - sub;
384 if (rhi32 < 0) rhi32 = 0;
385 if (rhi32 > 3) rhi32 = 3;
386 if (rlo32 > rhi32) continue;
387 const int rlo = (int)rlo32, rhi = (int)rhi32;
388 // Sub-row crossings, incremental (no multiply): X_{r+1} =
389 // X_r + q + (corr[r+1] - corr[r]), the difference in {0, 1}
390 fl::i64 X = ed.x0;
391 for (int r = 0; r <= rhi; ++r) {
392 if (r > 0) X += ed.q + (fl::i64)((fl::i32)(ed.corr[r] - ed.corr[r - 1]));
393 if (r < rlo) continue;
394 if (X < 0) {
395 // Edge already left of the canvas: full-row
396 // contribution — seed the parity, never crosses again
397 mask ^= (fl::u32)0xFFu << (8 * r);
398 } else {
399 const fl::i32 p = (fl::i32)(X >> 16); // pixel crossed
400 if (p < width) {
401 const fl::u32 bo = (fl::u32)((X - ((fl::i64)p << 16)) >> 13); // in [0, 8)
402 cp[ncp] = (p << 5) | (r << 3) | (fl::i32)bo;
403 ++ncp;
404 }
405 }
406 }
407 }
408
409 if (ncp == 0) {
410 // No crossings this row: uniform mask over the whole row
411 if (mask != 0)
412 polyABFillRun(pixels, py, width, 0, width, color,
413 polyABAlpha(mask), Overwrite);
414 continue;
415 }
416
417 // Sort events by pixel (packed key is pixel-major); insertion sort
418 for (int a = 1; a < ncp; ++a) {
419 const fl::i32 v = cp[a];
420 int b = a - 1;
421 while (b >= 0 && cp[b] > v) { cp[b + 1] = cp[b]; --b; }
422 cp[b + 1] = v;
423 }
424
425 // Walk the row: the mask (per row 0x00/0xFF after each extend) is
426 // constant between crossing pixels, so whole runs are painted in
427 // one go and only crossing pixels pay for the popcount.
428 int x = 0;
429 for (int k = 0; k < ncp; ) {
430 const int p = cp[k] >> 5;
431 if (p > x) {
432 if (mask != 0)
433 polyABFillRun(pixels, py, width, x, p, color,
434 polyABAlpha(mask), Overwrite);
435 x = p;
436 }
437 // Fold every event at p (XOR is commutative — no edge order
438 // is needed, self-intersecting polygons included)
439 fl::u32 rowxor = 0;
440 while (k < ncp && (cp[k] >> 5) == p) {
441 rowxor ^= (fl::u32)((1u << (8 - (cp[k] & 7u))) - 1u)
442 << (8 * ((cp[k] >> 3) & 3u));
443 ++k;
444 }
445 mask ^= rowxor;
446 if (mask != 0) {
447 const fl::u8 br = polyABAlpha(mask);
448 PixelT c = color;
449 if (br < 255u) c.nscale8(br);
450 PixelT& px = pixels[py * width + p];
451 if (Overwrite) px = c; else px += c;
452 }
453 // Extend to the next pixel: a set rightmost subpixel of a row
454 // (bit 0) means the trapezoid continues past the pixel, so the
455 // whole row starts full. (mask & 0x01010101) * 255 ==
456 // (b << 8) - b per row — shifts and a subtract, no multiply.
457 mask = (mask & 0x01010101u) * 255u;
458 x = p + 1;
459 }
460 if (x < width && mask != 0)
461 polyABFillRun(pixels, py, width, x, width, color,
462 polyABAlpha(mask), Overwrite);
463 }
464}
fl::CanvasRGB canvas(fl::span< CRGB >(leds, NUM_LEDS), WIDTH, HEIGHT)
constexpr fl::size size() const FL_NO_EXCEPT
Definition span.h:483
unsigned char u8
Definition s16x16x4.h:132
fl::u8 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 ...
void 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 polyABFloorDivI64(fl::i64 a, fl::i64 b) FL_NO_EXCEPT
Floor-divide a by positive b (rounds toward -inf).
fl::i32 polyABToQ16(Coord val) FL_NO_EXCEPT
Convert any Coord type to Q16.16, clamped to ±8191 px.
Per-edge scanline state.
unsigned char u8
Definition stdint.h:132
u8 u8 height
Definition blur.h:186
fl::i64 i64
Definition s16x16x4.h:222
u8 width
Definition blur.h:186
#define FL_STATIC_ASSERT(...)

References fl::B, canvas, fl::gfx::detail::AbEdge::corr, fl::FL_NO_EXCEPT, FL_STATIC_ASSERT, fl::height, polyABAlpha(), polyABFillRun(), polyABFloorDivI64(), polyABToQ16(), fl::gfx::detail::AbEdge::py0, fl::gfx::detail::AbEdge::py1, fl::gfx::detail::AbEdge::q, fl::width, fl::x, fl::gfx::detail::AbEdge::x0, fl::gfx::detail::AbEdge::xinc, fl::y, fl::gfx::detail::AbEdge::ybot, and fl::gfx::detail::AbEdge::ytop.

Referenced by fl::gfx::drawPolygon().

+ Here is the call graph for this function:
+ Here is the caller graph for this function: