tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * draw-poly.c: Fallback polygon drawing function.
3 */
4
5#include <assert.h>
6
7#include "puzzles.h"
8
9struct edge {
10 int x1, y1;
11 int x2, y2;
12 bool active;
13
14 /* whether y1 is a closed endpoint (i.e. this edge should be
15 * active when y == y1) */
16 bool closed_y1;
17
18 /* (x2 - x1) / (y2 - y1) as 16.16 signed fixed point; precomputed
19 * for speed */
20 long inverse_slope;
21};
22
23#define FRACBITS 16
24#define ONEHALF (1 << (FRACBITS-1))
25
26void draw_polygon_fallback(drawing *dr, const int *coords, int npoints,
27 int fillcolour, int outlinecolour)
28{
29 struct edge *edges;
30 int min_y = INT_MAX, max_y = INT_MIN, i, y;
31 int n_edges = 0;
32 int *intersections;
33
34 if(npoints < 3)
35 return;
36
37 if(fillcolour < 0)
38 goto draw_outline;
39
40 /* This uses a basic scanline rasterization algorithm for polygon
41 * filling. First, an "edge table" is constructed for each pair of
42 * neighboring points. Horizontal edges are excluded. Then, the
43 * algorithm iterates a horizontal "scan line" over the vertical
44 * (Y) extent of the polygon. At each Y level, it maintains a set
45 * of "active" edges, which are those which intersect the scan
46 * line at the current Y level. The X coordinates where the scan
47 * line intersects each active edge are then computed via
48 * fixed-point arithmetic and stored. Finally, horizontal lines
49 * are drawn between each successive pair of intersection points,
50 * in the order of ascending X coordinate. This has the effect of
51 * "even-odd" filling when the polygon is self-intersecting.
52 *
53 * I (vaguely) based this implementation off the slides below:
54 *
55 * https://www.khoury.northeastern.edu/home/fell/CS4300/Lectures/CS4300F2012-9-ScanLineFill.pdf
56 *
57 * I'm fairly confident that this current implementation is
58 * correct (i.e. draws the right polygon, free from artifacts),
59 * but it isn't quite as efficient as it could be. Namely, it
60 * currently maintains the active edge set by setting the `active`
61 * flag in the `edge` array, which is quite inefficient. Perhaps
62 * future optimization could see this replaced with a tree
63 * set. Additionally, one could perhaps replace the current linear
64 * search for edge endpoints (i.e. the inner loop over `edges`) by
65 * sorting the edge table by upper and lower Y coordinate.
66 *
67 * A final caveat comes from the use of fixed point arithmetic,
68 * which is motivated by performance considerations on FPU-less
69 * platforms (e.g. most Rockbox devices, and maybe others?). I'm
70 * currently using 16 fractional bits to compute the edge
71 * intersections, which (in the case of a 32-bit int) limits the
72 * acceptable range of coordinates to roughly (-2^14, +2^14). This
73 * ought to be acceptable for the forseeable future, but
74 * ultra-high DPI screens might one day exceed this. In that case,
75 * options include switching to int64_t (but that comes with its
76 * own portability headaches), reducing the number of fractional
77 * bits, or just giving up and using floating point.
78 */
79
80 /* Build edge table from coords. Horizontal edges are filtered
81 * out, so n_edges <= n_points in general. */
82 edges = smalloc(npoints * sizeof(struct edge));
83
84 for(i = 0; i < npoints; i++) {
85 int x1, y1, x2, y2;
86
87 x1 = coords[(2*i+0)];
88 y1 = coords[(2*i+1)];
89 x2 = coords[(2*i+2) % (npoints * 2)];
90 y2 = coords[(2*i+3) % (npoints * 2)];
91
92 if(y1 < min_y)
93 min_y = y1;
94 if(y1 > max_y)
95 max_y = y1;
96
97#define COORD_LIMIT (1<<(sizeof(int)*CHAR_BIT-2 - FRACBITS))
98 /* Prevent integer overflow when computing `inverse_slope',
99 * which shifts the coordinates left by FRACBITS, and for
100 * which we'd like to avoid relying on `long long'. */
101 /* If this ever causes issues, see the above comment about
102 possible solutions. */
103 assert(x1 < COORD_LIMIT && y1 < COORD_LIMIT);
104
105 /* Only create non-horizontal edges, and require y1 < y2. */
106 if(y1 != y2) {
107 bool swap = y1 > y2;
108 int lower_endpoint = swap ? (i + 1) : i;
109
110 /* Compute index of the point adjacent to lower end of
111 * this edge (which is not the upper end of this edge). */
112 int lower_neighbor = swap ? (lower_endpoint + 1) % npoints : (lower_endpoint + npoints - 1) % npoints;
113
114 struct edge *edge = edges + (n_edges++);
115
116 edge->active = false;
117 edge->x1 = swap ? x2 : x1;
118 edge->y1 = swap ? y2 : y1;
119 edge->x2 = swap ? x1 : x2;
120 edge->y2 = swap ? y1 : y2;
121 edge->inverse_slope = ((edge->x2 - edge->x1) << FRACBITS) / (edge->y2 - edge->y1);
122 edge->closed_y1 = edge->y1 < coords[2*lower_neighbor+1];
123 }
124 }
125
126 /* a generous upper bound on number of intersections is n_edges */
127 intersections = smalloc(n_edges * sizeof(int));
128
129 for(y = min_y; y <= max_y; y++) {
130 int n_intersections = 0;
131 for(i = 0; i < n_edges; i++) {
132 struct edge *edge = edges + i;
133 /* Update active edge set. These conditions are mutually
134 * exclusive because of the invariant that y1 < y2. */
135 if(edge->y1 + (edge->closed_y1 ? 0 : 1) == y)
136 edge->active = true;
137 else if(edge->y2 + 1 == y)
138 edge->active = false;
139
140 if(edge->active) {
141 int x = edges[i].x1;
142 x += (edges[i].inverse_slope * (y - edges[i].y1) + ONEHALF) >> FRACBITS;
143 intersections[n_intersections++] = x;
144 }
145 }
146
147 qsort(intersections, n_intersections, sizeof(int), compare_integers);
148
149 assert(n_intersections % 2 == 0);
150 assert(n_intersections <= n_edges);
151
152 /* Draw horizontal lines between successive pairs of
153 * intersections of the scanline with active edges. */
154 for(i = 0; i + 1 < n_intersections; i += 2) {
155 draw_line(dr,
156 intersections[i], y,
157 intersections[i+1], y,
158 fillcolour);
159 }
160 }
161
162 sfree(intersections);
163 sfree(edges);
164
165draw_outline:
166 assert(outlinecolour >= 0);
167 for (i = 0; i < 2 * npoints; i += 2)
168 draw_line(dr,
169 coords[i], coords[i+1],
170 coords[(i+2)%(2*npoints)], coords[(i+3)%(2*npoints)],
171 outlinecolour);
172}
173
174#ifdef STANDALONE_POLYGON
175
176/*
177 * Standalone program to test draw_polygon_fallback(). By default,
178 * creates a window and allows clicking points to build a
179 * polygon. Optionally, can draw a randomly growing polygon in
180 * "screensaver" mode.
181 */
182
183#include <SDL.h>
184
185void draw_line(drawing *dr, int x1, int y1, int x2, int y2, int colour)
186{
187 SDL_Renderer *renderer = GET_HANDLE_AS_TYPE(dr, SDL_Renderer);
188 SDL_RenderDrawLine(renderer, x1, y1, x2, y2);
189}
190
191#define WINDOW_WIDTH 800
192#define WINDOW_HEIGHT 600
193#define MAX_SCREENSAVER_POINTS 1000
194
195int main(int argc, char *argv[]) {
196 SDL_Window* window = NULL;
197 SDL_Event event;
198 SDL_Renderer *renderer = NULL;
199 int running = 1;
200 int i;
201 drawing dr;
202 bool screensaver = false;
203
204 if(argc >= 2) {
205 if(!strcmp(argv[1], "--screensaver"))
206 screensaver = true;
207 else
208 printf("usage: %s [--screensaver]\n", argv[0]);
209 }
210
211 int *poly = NULL;
212 int n_points = 0;
213
214 /* Initialize SDL */
215 if (SDL_Init(SDL_INIT_VIDEO) < 0) {
216 printf("SDL could not initialize! SDL_Error: %s\n", SDL_GetError());
217 return 1;
218 }
219
220 /* Create window */
221 window = SDL_CreateWindow("Polygon Drawing Test", SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, WINDOW_WIDTH, WINDOW_HEIGHT, SDL_WINDOW_SHOWN);
222 if (!window) {
223 printf("Window could not be created! SDL_Error: %s\n", SDL_GetError());
224 SDL_Quit();
225 return 1;
226 }
227
228 /* Create renderer */
229 renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);
230 if (!renderer) {
231 printf("Renderer could not be created! SDL_Error: %s\n", SDL_GetError());
232 SDL_DestroyWindow(window);
233 SDL_Quit();
234 return 1;
235 }
236
237 dr.handle = renderer;
238
239 if(!screensaver)
240 printf("Click points in the window to create vertices. Pressing C resets.\n");
241
242 while (running) {
243 while (SDL_PollEvent(&event) != 0) {
244 if (event.type == SDL_QUIT) {
245 running = 0;
246 }
247 else if (event.type == SDL_MOUSEBUTTONDOWN) {
248 if (event.button.button == SDL_BUTTON_LEFT) {
249 int mouseX = event.button.x;
250 int mouseY = event.button.y;
251
252 poly = realloc(poly, ++n_points * 2 * sizeof(int));
253 poly[2 * (n_points - 1)] = mouseX;
254 poly[2 * (n_points - 1) + 1] = mouseY;
255 }
256 }
257 else if (event.type == SDL_KEYDOWN) {
258 if (event.key.keysym.sym == SDLK_c) {
259 free(poly);
260 poly = NULL;
261 n_points = 0;
262 }
263 }
264 }
265
266 if(screensaver) {
267 poly = realloc(poly, ++n_points * 2 * sizeof(int));
268 poly[2 * (n_points - 1)] = rand() % WINDOW_WIDTH;
269 poly[2 * (n_points - 1) + 1] = rand() % WINDOW_HEIGHT;
270
271 if(n_points >= MAX_SCREENSAVER_POINTS) {
272 free(poly);
273 poly = NULL;
274 n_points = 0;
275 }
276 }
277
278 /* Clear the screen with a black color */
279 SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);
280 SDL_RenderClear(renderer);
281
282 /* Set draw color to white */
283 SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255);
284
285 draw_polygon_fallback(&dr, poly, n_points, 1, 1);
286
287 SDL_SetRenderDrawColor(renderer, 255, 0, 0, 255);
288 for(i = 0; i < 2*n_points; i+=2)
289 SDL_RenderDrawPoint(renderer, poly[i], poly[i+1]);
290
291 /* Present the back buffer */
292 SDL_RenderPresent(renderer);
293 }
294
295 /* Clean up and quit SDL */
296 SDL_DestroyRenderer(renderer);
297 SDL_DestroyWindow(window);
298 SDL_Quit();
299
300 return 0;
301}
302#endif