FastLED 3.10.10
Loading...
Searching...
No Matches
poly_abuffer.h
Go to the documentation of this file.
1#pragma once
2
92
93#include "fl/stl/noexcept.h"
95#include "fl/stl/int.h"
97#include "fl/gfx/canvas.h"
98#include "fastled_progmem.h"
99
100namespace fl {
101namespace gfx {
102namespace detail {
103
108 fl::i64 q = a / b;
109 if ((a % b) < 0) --q;
110 return q;
111}
112
116static const fl::i32 polyABQ16Max = 8191L << 16;
117
121inline fl::i32 polyABClampPx(float px) FL_NO_EXCEPT {
122 if (!(px == px)) return 0; // NaN
123 if (px > 8191.0f) return polyABQ16Max;
124 if (px < -8191.0f) return -polyABQ16Max;
125 return static_cast<fl::i32>(px * 65536.0f);
126}
127
132template<typename Coord>
133inline fl::i32 polyABToQ16(Coord val) FL_NO_EXCEPT {
134 return polyABClampPx(val.to_float());
135}
136
137template<>
138inline fl::i32 polyABToQ16<float>(float val) FL_NO_EXCEPT {
139 return polyABClampPx(val);
140}
141
142template<>
143inline fl::i32 polyABToQ16<double>(double val) FL_NO_EXCEPT {
144 if (!(val == val)) return 0; // NaN
145 if (val > 8191.0) return polyABQ16Max;
146 if (val < -8191.0) return -polyABQ16Max;
147 return static_cast<fl::i32>(val * 65536.0);
148}
149
150template<>
151// 16-bit int coordinate overload: the public API accepts int PolyPoint
152// coords (int on AVR); values clamp to ±8191 px, so the i32 result is exact.
153inline fl::i32 polyABToQ16<int>(int val) FL_NO_EXCEPT { // fl-lint: int-template-ok int coord API
154 if (val > 8191) return polyABQ16Max;
155 if (val < -8191) return -polyABQ16Max;
156 return static_cast<fl::i32>(val) << 16;
157}
158
159template<>
160// s16x16 spans ±32767 px, so its raw value must be clamped too: unclamped,
161// edge deltas (vx[j] - vx[i]) overflow i32.
163 const fl::i32 r = val.raw();
164 if (r > polyABQ16Max) return polyABQ16Max;
165 if (r < -polyABQ16Max) return -polyABQ16Max;
166 return r;
167}
168
174#define FL_POLYAB_POP2(n) n, n + 1, n + 1, n + 2
175#define FL_POLYAB_POP4(n) FL_POLYAB_POP2(n), FL_POLYAB_POP2(n + 1), \
176 FL_POLYAB_POP2(n + 1), FL_POLYAB_POP2(n + 2)
177#define FL_POLYAB_POP6(n) FL_POLYAB_POP4(n), FL_POLYAB_POP4(n + 1), \
178 FL_POLYAB_POP4(n + 1), FL_POLYAB_POP4(n + 2)
180 static const fl::u8 kPop8[256] FL_PROGMEM = {
182 };
183 return kPop8;
184}
185#undef FL_POLYAB_POP6
186#undef FL_POLYAB_POP4
187#undef FL_POLYAB_POP2
188
192#if defined(__AVR__)
194#elif defined(__GNUC__) || defined(__clang__)
195 return (fl::u8)__builtin_popcount((unsigned)v);
196#else
197 v = v - ((v >> 1) & 0x55u);
198 v = (v & 0x33u) + ((v >> 2) & 0x33u);
199 return (fl::u8)((v + (v >> 4)) & 0x0Fu);
200#endif
201}
202
204 return (fl::u8)(polyABPop8((fl::u8)(v & 0xFFu))
205 + polyABPop8((fl::u8)((v >> 8) & 0xFFu))
206 + polyABPop8((fl::u8)((v >> 16) & 0xFFu))
207 + polyABPop8((fl::u8)(v >> 24)));
208}
209
212inline fl::u8 polyABAlpha(fl::u32 mask) FL_NO_EXCEPT {
213 const fl::u8 p = polyABPopcount32(mask);
214 const fl::u8 br = (fl::u8)(p * 8u);
215 return (p >= 32u) ? 255u : br;
216}
217
237struct AbEdge {
238 fl::i64 x0; // sub-row-0 crossing, Q16.16, current scanline
239 fl::i64 xinc; // per-scanline step, Q16.16: floor(65536 * B / dy)
240 fl::i64 q; // xinc >> 2
241 fl::u8 corr[4]; // per-sub-row correction, 0..3
242 fl::i32 ytop; // first in-range sub-row, .2 (ceil of top vertex)
243 fl::i32 ybot; // one past last in-range sub-row, .2 (ceil of bottom)
244 int py0; // first active canvas row
245 int py1; // last active canvas row
246};
247
250template<typename PixelT>
251inline void polyABFillRun(PixelT* pixels, int py, int width,
252 int x0, int x1, const PixelT& color,
253 fl::u8 br, bool overwrite) FL_NO_EXCEPT {
254 if (x1 <= x0) return;
255 PixelT c = color;
256 if (br < 255u) c.nscale8(br);
257 PixelT* row = pixels + py * width + x0;
258 if (overwrite) {
259 for (int i = 0; i < x1 - x0; ++i) row[i] = c;
260 } else {
261 for (int i = 0; i < x1 - x0; ++i) row[i] += c;
262 }
263}
264
274template<typename PixelT, typename Coord, bool Overwrite, int MAXN>
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}
465
466} // namespace detail
467} // namespace gfx
468} // namespace fl
fl::CanvasRGB canvas(fl::span< CRGB >(leds, NUM_LEDS), WIDTH, HEIGHT)
Canvas types for gfx primitives (implementation)
#define FL_PGM_READ_BYTE_NEAR(x)
Read a byte (8-bit) from PROGMEM memory.
#define FL_PROGMEM
PROGMEM keyword for storage.
Wrapper definitions to allow seamless use of PROGMEM in environments that have it.
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 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).
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.
static const fl::i32 polyABQ16Max
Maximum |vertex coordinate| accepted, in Q16.16 units (8191 px keeps all values and edge deltas in i3...
fl::i64 polyABFloorDivI64(fl::i64 a, fl::i64 b) FL_NO_EXCEPT
Floor-divide a by positive b (rounds toward -inf).
fl::i32 polyABToQ16< int >(int val) FL_NO_EXCEPT
fl::u8 polyABPop8(fl::u8 v) FL_NO_EXCEPT
Popcount of a byte.
fl::i32 polyABToQ16< fl::s16x16 >(fl::s16x16 val) FL_NO_EXCEPT
fl::i32 polyABClampPx(float px) FL_NO_EXCEPT
Float -> Q16.16, clamped to ±8191 px.
fl::i32 polyABToQ16(Coord val) FL_NO_EXCEPT
Convert any Coord type to Q16.16, clamped to ±8191 px.
const fl::u8 * polyABPop8Table() FL_NO_EXCEPT
fl::u8 polyABPopcount32(fl::u32 v) FL_NO_EXCEPT
fl::i32 polyABToQ16< double >(double val) FL_NO_EXCEPT
fl::i32 polyABToQ16< float >(float val) FL_NO_EXCEPT
============================================================================
Per-edge scanline state.
Polygon vertex (x, y coordinate pair) for drawPolygon C++11 aggregate: PolyPoint<float> p{3....
Definition canvas.h:25
u8 u8 fract8 blur_amount FL_NO_EXCEPT
Definition blur.h:186
u8 u8 height
Definition blur.h:186
fl::i64 i64
Definition s16x16x4.h:222
u8 width
Definition blur.h:186
Base definition for an LED controller.
#define FL_POLYAB_POP6(n)
#define FL_STATIC_ASSERT(...)
Portable compile-time assertion wrapper.
Simple rectangular canvas for graphics operations Combines a pixel buffer with dimensions for cache-o...
Definition canvas.h:138