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