diff options
Diffstat (limited to 'apps/plugins/puzzles/src/draw-poly.c')
-rw-r--r-- | apps/plugins/puzzles/src/draw-poly.c | 302 |
1 files changed, 302 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/draw-poly.c b/apps/plugins/puzzles/src/draw-poly.c new file mode 100644 index 0000000000..d4c9975d97 --- /dev/null +++ b/apps/plugins/puzzles/src/draw-poly.c | |||
@@ -0,0 +1,302 @@ | |||
1 | /* | ||
2 | * draw-poly.c: Fallback polygon drawing function. | ||
3 | */ | ||
4 | |||
5 | #include <assert.h> | ||
6 | |||
7 | #include "puzzles.h" | ||
8 | |||
9 | struct 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 | |||
26 | void 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 | |||
165 | draw_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 | |||
185 | void 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 | |||
195 | int 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 | ||