GCC Code Coverage Report

Directory: ./
File: overlays/PolarBufferMap.cpp
Date: 2026-10-29 08:11:58
Exec Total Coverage
Lines: 134 156 85.9%
Functions: 10 12 83.3%
Branches: 119 186 64.0%
Line Branch Exec Source
1 /*
2 * This file is part of the Falcon Player (FPP) and is Copyright (C)
3 * 2013-2025 by the Falcon Player Developers.
4 *
5 * The Falcon Player (FPP) is free software, and is covered under
6 * multiple Open Source licenses. Please see the included 'LICENSES'
7 * file for descriptions of what files are covered by each license.
8 *
9 * This source file is covered under the LGPL v2.1 as described in the
10 * included LICENSE.LGPL file.
11 */
12
13 #include "fpp-pch.h"
14
15 #include <algorithm>
16 #include <cmath>
17 #include <cstdio>
18 #include <fstream>
19 #include <unordered_map>
20
21 #include "log.h"
22 #include "settings.h"
23
24 #include "PolarBufferMap.h"
25
26 namespace {
27
28 /** A radius gap this fraction of the radial span starts a new ring. */
29 constexpr float RING_GAP_FRACTION = 0.02f;
30
31 /**
32 * Below this radial spread — (rmax - rmin) / rmean — the target is ONE ring.
33 *
34 * A single physical ring has no radial structure, but the virtual display map
35 * stores integer screen coordinates, so its pixels still scatter over roughly a
36 * unit of radius. Left alone, gap detection reads that rounding jitter as
37 * structure and shatters a 24-pixel ring into twenty 1-pixel "rings". A ring
38 * cannot radiate, only rotate: it wants one radius column with every pixel
39 * spread around the angular axis.
40 */
41 constexpr float RING_FLAT_FRACTION = 0.15f;
42
43 /** Gap-detected rings are rejected above this overdraw (cells per pixel). */
44 constexpr float MAX_GAP_OVERDRAW = 2.0f;
45
46 /** ...and below this many rings; either way equal-population rings take over. */
47 constexpr int MIN_GAP_RINGS = 3;
48
49 /** Refuse to build a buffer larger than this. Guards a pathological layout. */
50 constexpr size_t MAX_CELLS = 262144;
51
52 /** Which ring does radius r fall in? Bounds are ascending. */
53 672 int ringIndex(float r, const std::vector<float>& bounds) {
54
1/2
✓ Branch 0 taken 672 times.
✗ Branch 1 not taken.
 672 return static_cast<int>(std::upper_bound(bounds.begin(), bounds.end(), r) - bounds.begin());
55 }
56
57 /** Does everything sit at essentially one radius? See RING_FLAT_FRACTION. */
58 16 bool isFlat(const std::vector<float>& radii) {
59
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (radii.size() < 2) {
60 ✗ return true;
61 }
62
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 auto [mn, mx] = std::minmax_element(radii.begin(), radii.end());
63 16 double sum = 0.0;
64
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 16 times.
 400 for (float r : radii) {
65 384 sum += r;
66 }
67 16 double mean = sum / radii.size();
68
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (mean <= 0.0) {
69 ✗ return true;
70 }
71 16 return ((*mx - *mn) / mean) < RING_FLAT_FRACTION;
72 }
73
74 /** Split where consecutive sorted radii jump by a large part of the span. */
75 12 std::vector<float> gapBounds(std::vector<float> rs) {
76 12 std::sort(rs.begin(), rs.end());
77 12 std::vector<float> bounds;
78 12 float span = rs.back() - rs.front();
79
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (span <= 0.0f) {
80 ✗ return bounds;
81 }
82 12 float thresh = span * RING_GAP_FRACTION;
83
2/2
✓ Branch 0 taken 276 times.
✓ Branch 1 taken 12 times.
 288 for (size_t i = 0; i + 1 < rs.size(); i++) {
84
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 254 times.
 276 if ((rs[i + 1] - rs[i]) > thresh) {
85
1/2
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
 22 bounds.push_back((rs[i] + rs[i + 1]) / 2.0f);
86 }
87 }
88 12 return bounds;
89 ✗ }
90
91 /** Equal-population ring boundaries — every ring holds ~n/count pixels. */
92 2 std::vector<float> evenBounds(std::vector<float> rs, int count) {
93
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 std::sort(rs.begin(), rs.end());
94 2 std::vector<float> bounds;
95 2 int n = static_cast<int>(rs.size());
96 2 count = std::max(1, std::min(count, n));
97
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 for (int k = 1; k < count; k++) {
98
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 bounds.push_back(rs[static_cast<size_t>((long long)n * k / count)]);
99 }
100 2 return bounds;
101 ✗ }
102
103 /**
104 * Ring count for equal-population binning. sqrt(n/2) keeps the buffer
105 * near-square, so both axes stay usefully resolved: enough rings for a radial
106 * sweep to read as motion, enough sectors for a rotation to.
107 */
108 2 int defaultRingCount(size_t n) {
109 2 return std::max(2, static_cast<int>(std::lround(std::sqrt(n / 2.0))));
110 }
111
112 /** Largest ring population under these bounds. */
113 12 int busiestRing(const std::vector<float>& radii, const std::vector<float>& bounds) {
114 12 std::unordered_map<int, int> pop;
115
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 12 times.
 300 for (float r : radii) {
116
2/4
✓ Branch 0 taken 288 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 288 times.
✗ Branch 3 not taken.
 288 pop[ringIndex(r, bounds)]++;
117 }
118 12 int mx = 0;
119
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 12 times.
 46 for (auto& [k, v] : pop) {
120 34 mx = std::max(mx, v);
121 }
122 12 return mx;
123 12 }
124
125 /** Walk outward from s to the first sector no pixel has claimed. Wraps. */
126 ✗ int nearestFreeSector(const std::vector<bool>& taken, int s, int S) {
127 ✗ for (int d = 1; d < S; d++) {
128 ✗ int up = (s + d) % S;
129 ✗ if (!taken[up]) {
130 ✗ return up;
131 }
132 ✗ int down = ((s - d) % S + S) % S;
133 ✗ if (!taken[down]) {
134 ✗ return down;
135 }
136 }
137 ✗ return s; // unreachable: S >= the busiest ring's population
138 }
139
140 } // namespace
141
142 1196 PolarMode PolarModeFromName(std::string_view name) {
143
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 1184 times.
 1196 if (name == "Radial Out") {
144 12 return PolarMode::RadialOut;
145 }
146
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1181 times.
 1184 if (name == "Radial In") {
147 3 return PolarMode::RadialIn;
148 }
149
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1178 times.
 1181 if (name == "Angular CW") {
150 3 return PolarMode::AngularCW;
151 }
152
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1173 times.
 1178 if (name == "Angular CCW") {
153 5 return PolarMode::AngularCCW;
154 }
155 // Every other value -- the four original mappings, and anything a newer
156 // config might name that this build does not know -- is not polar.
157 1173 return PolarMode::None;
158 }
159
160 22 bool LoadVirtualDisplayPositions(std::vector<std::pair<uint32_t, std::pair<float, float>>>& out) {
161
4/8
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 22 times.
✗ Branch 7 not taken.
 22 std::ifstream in(FPP_DIR_CONFIG("/virtualdisplaymap"));
162
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 20 times.
 22 if (!in.is_open()) {
163 // No xLights layout has ever been uploaded. Not an error: the caller
164 // falls back to the ordinary buffer mapping.
165 2 return false;
166 }
167 20 std::string line;
168
4/6
✓ Branch 0 taken 600 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 600 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 580 times.
✓ Branch 5 taken 20 times.
 600 while (std::getline(in, line)) {
169
4/8
✓ Branch 0 taken 580 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 580 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 580 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 580 times.
 580 if (line.empty() || line[0] == '#') {
170 ✗ continue;
171 }
172 580 int x = 0, y = 0, z = 0;
173 580 unsigned int ch = 0;
174 // x,y,z,channel,channelCount,colorOrder,pixelSize -- the channel is a
175 // 0-based index into fppd's channel data.
176
2/2
✓ Branch 0 taken 560 times.
✓ Branch 1 taken 20 times.
 580 if (std::sscanf(line.c_str(), "%d,%d,%d,%u", &x, &y, &z, &ch) == 4) {
177
1/2
✓ Branch 0 taken 560 times.
✗ Branch 1 not taken.
 560 out.emplace_back(ch, std::make_pair(static_cast<float>(x), static_cast<float>(y)));
178 }
179 }
180 20 return !out.empty();
181 22 }
182
183 16 PolarBufferMap BuildPolarBufferMap(const std::vector<PolarPixel>& pixels, PolarMode mode) {
184 16 PolarBufferMap map;
185
3/6
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 16 times.
 16 if (mode == PolarMode::None || pixels.empty()) {
186 ✗ return map;
187 }
188
189 // Centroid.
190 16 double sx = 0.0, sy = 0.0;
191
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 16 times.
 400 for (const auto& p : pixels) {
192 384 sx += p.x;
193 384 sy += p.y;
194 }
195 16 float cx = static_cast<float>(sx / pixels.size());
196 16 float cy = static_cast<float>(sy / pixels.size());
197
198 // To polar. Angle is shifted to 0..2pi so the sector axis is monotonic;
199 // zero is +x (screen right), matching the map's coordinate sense.
200 struct PolarPt {
201 float r;
202 float theta;
203 uint32_t cell;
204 };
205 16 std::vector<PolarPt> polar;
206
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 polar.reserve(pixels.size());
207 16 std::vector<float> radii;
208
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 radii.reserve(pixels.size());
209 16 const float TWO_PI = static_cast<float>(2.0 * M_PI);
210
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 16 times.
 400 for (const auto& p : pixels) {
211 384 float dx = p.x - cx;
212 384 float dy = p.y - cy;
213 384 float r = std::sqrt(dx * dx + dy * dy);
214 384 float t = std::fmod(std::atan2(dy, dx) + TWO_PI * 2.0f, TWO_PI);
215
1/2
✓ Branch 0 taken 384 times.
✗ Branch 1 not taken.
 384 polar.push_back({ r, t, p.cell });
216
1/2
✓ Branch 0 taken 384 times.
✗ Branch 1 not taken.
 384 radii.push_back(r);
217 }
218
219 // Everything at one point: no polar structure to build.
220
2/4
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
 16 if (*std::max_element(radii.begin(), radii.end()) <= 0.0f) {
221 ✗ return map;
222 }
223
224 // Ring strategy. A single physical ring is decided before anything else,
225 // because every strategy would otherwise invent rings out of coordinate
226 // rounding. Otherwise prefer physically-detected rings -- on a model built
227 // from discrete concentric rings those are what a viewer sees light up --
228 // and fall back to equal-population rings when detection finds no structure
229 // (a solid disc is one continuous ring) or would leave the buffer mostly
230 // empty.
231 16 std::vector<float> bounds;
232
3/4
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 4 times.
 16 if (!isFlat(radii)) {
233
2/4
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 bounds = gapBounds(radii);
234 12 int R = static_cast<int>(bounds.size()) + 1;
235
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 int S = busiestRing(radii, bounds);
236 12 float overdraw = static_cast<float>((long long)R * S) / pixels.size();
237
3/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
 12 if (R < MIN_GAP_RINGS || overdraw > MAX_GAP_OVERDRAW) {
238
3/6
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 bounds = evenBounds(radii, defaultRingCount(pixels.size()));
239 }
240 }
241
242 // Bin by ring, then reindex densely: detection can leave a ring empty when
243 // a boundary falls outside the data, and an empty column wastes a sweep step.
244 16 std::unordered_map<int, std::vector<PolarPt>> byRing;
245
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 16 times.
 400 for (const auto& pt : polar) {
246
3/6
✓ Branch 0 taken 384 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 384 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 384 times.
✗ Branch 5 not taken.
 384 byRing[ringIndex(pt.r, bounds)].push_back(pt);
247 }
248 16 std::vector<int> ringKeys;
249
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 ringKeys.reserve(byRing.size());
250
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 16 times.
 54 for (auto& [k, v] : byRing) {
251
1/2
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
 38 ringKeys.push_back(k);
252 }
253
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 std::sort(ringKeys.begin(), ringKeys.end());
254
255 16 int R = static_cast<int>(ringKeys.size());
256 16 int S = 0;
257
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 16 times.
 54 for (int k : ringKeys) {
258
1/2
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
 38 S = std::max(S, static_cast<int>(byRing[k].size()));
259 }
260
2/4
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
 16 if (R < 1 || S < 1) {
261 ✗ return map;
262 }
263
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (static_cast<size_t>(R) * S > MAX_CELLS) {
264 ✗ LogWarn(VB_CHANNELOUT,
265 "Polar buffer would be %d x %d cells; falling back to the ordinary mapping\n", R, S);
266 ✗ return map;
267 }
268
269 // Place each ring's pixels around the sector axis by true bearing,
270 // nudging a collision to the nearest free sector.
271
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 std::vector<uint32_t> grid(static_cast<size_t>(R) * S, PolarBufferMap::Empty);
272
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 16 times.
 54 for (int ri = 0; ri < R; ri++) {
273
1/2
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
 38 std::vector<PolarPt>& items = byRing[ringKeys[ri]];
274
1/2
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
 38 std::sort(items.begin(), items.end(),
275 1284 [](const PolarPt& a, const PolarPt& b) { return a.theta < b.theta; });
276
1/2
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
 38 std::vector<bool> taken(S, false);
277
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 38 times.
 422 for (const auto& pt : items) {
278 384 int s = static_cast<int>(std::lround(pt.theta / TWO_PI * S)) % S;
279
2/4
✓ Branch 0 taken 384 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 384 times.
 384 if (taken[s]) {
280 ✗ s = nearestFreeSector(taken, s, S);
281 }
282
1/2
✓ Branch 0 taken 384 times.
✗ Branch 1 not taken.
 384 taken[s] = true;
283 384 grid[static_cast<size_t>(ri) * S + s] = pt.cell;
284 }
285 38 }
286
287 // Emit in the order the requested mode wants. The LUT is walked linearly by
288 // Bus::setPixelColor, so the ordering here IS the mapping -- there is no
289 // div/mod left in the hot path.
290 //
291 // WLED walks the WIDTH axis first (that is what the original Horizontal /
292 // Vertical pair selects), so whatever should light "all at once" has to be
293 // contiguous in the index. A radial wave lights a whole RING at a time, so
294 // sectors run along the width and rings step down the height; an angular
295 // sweep lights a whole SPOKE at a time, so the two swap. Getting this the
296 // wrong way round yields a spiral -- correct pixels, wrong motion.
297
4/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 5 times.
 16 const bool radial = (mode == PolarMode::RadialOut || mode == PolarMode::RadialIn);
298
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 5 times.
 16 map.width = radial ? S : R;
299
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 5 times.
 16 map.height = radial ? R : S;
300
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 map.indexToCell.assign(static_cast<size_t>(map.width) * map.height, PolarBufferMap::Empty);
301
302
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 16 times.
 54 for (int ri = 0; ri < R; ri++) {
303
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 38 times.
 422 for (int si = 0; si < S; si++) {
304 384 uint32_t cell = grid[static_cast<size_t>(ri) * S + si];
305
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 384 times.
 384 if (cell == PolarBufferMap::Empty) {
306 ✗ continue;
307 }
308
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 312 times.
 384 int r = (mode == PolarMode::RadialIn) ? (R - 1 - ri) : ri;
309
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 336 times.
 384 int s = (mode == PolarMode::AngularCCW) ? (S - 1 - si) : si;
310
2/2
✓ Branch 0 taken 264 times.
✓ Branch 1 taken 120 times.
 384 size_t idx = radial ? (static_cast<size_t>(r) * map.width + s)
311 120 : (static_cast<size_t>(s) * map.width + r);
312 384 map.indexToCell[idx] = cell;
313 }
314 }
315 16 return map;
316 16 }
317