1// This file is part of SmallBASIC
2//
3// FloodFill - Source code is based on:
4// "Programmer's guide to PC & PS/2 Video Systems"
5//
6// This program is distributed under the terms of the GPL v2.0 or later
7// Download the GNU Public License (GPL) from www.gnu.org
8//
9// Copyright(C) 2000 Nicholas Christopoulos
10
11#include "common/sys.h"
12#include "common/device.h"
13
14#define QUEUESIZE 2048
15#define UP 1
16#define DN -1
17#define FILLED 1
18#define NOT_FILLED 0
19#define SCAN_UNTIL 0
20#define SCAN_WHILE 1
21
22struct tagParams {
23 uint16_t xl; // leftmost pixel in run
24 uint16_t xr; // rightmost pixel in run
25 int16_t y; // y-coordinate of run
26 byte f; // TRUE if run is filled (blocked)
27};
28
29struct tagQUEUE {
30 struct tagQUEUE *pQ; // pointer to opposite queue
31 int d; // direction (UP or DN)
32 int n; // number of unfilled runs in queue
33 int h; // index of head of queue
34 int t; // index of tail of queue
35 struct tagParams *run;
36};
37typedef struct tagQUEUE QUEUE;
38
39// Global variables of the module.
40static struct tagParams ff_buf1[QUEUESIZE];
41static struct tagParams ff_buf2[QUEUESIZE];
42static long ucBorder;
43static QUEUE Qup;
44static QUEUE Qdn;
45static int scan_type;
46
47uint16_t ff_scan_left(uint16_t, uint16_t, long, int);
48uint16_t ff_scan_right(uint16_t, uint16_t, long, int);
49uint16_t ff_next_branch(uint16_t, uint16_t, int);
50void ff_add_queue(QUEUE *, uint16_t, uint16_t, int, int);
51int ff_in_queue(QUEUE *, uint16_t, uint16_t, int);
52
53void dev_ffill(uint16_t x0, uint16_t y0, long fill_color, long border_color) {
54 int y = y0, qp;
55 int bChangeDirection;
56 uint16_t x, xl = x0, xr = x0, xln, xrn;
57 QUEUE *Q;
58 long pcolor;
59
60 // reset all globals
61 memset(ff_buf1, 0, sizeof(ff_buf1));
62 memset(ff_buf2, 0, sizeof(ff_buf2));
63 memset(&Qup, 0, sizeof(QUEUE));
64 memset(&Qdn, 0, sizeof(QUEUE));
65 ucBorder = 0;
66 scan_type = 0;
67
68 pcolor = dev_fgcolor;
69 dev_setcolor(fill_color);
70
71 // do nothing if the seed pixel is a border pixel
72 if (border_color == -1) {
73 border_color = dev_getpixel(x0, y0);
74 scan_type = SCAN_WHILE;
75 } else {
76 scan_type = SCAN_UNTIL;
77 }
78 if (scan_type == SCAN_UNTIL) {
79 if (dev_getpixel(x0, y0) == border_color) {
80 return;
81 }
82 } else {
83 if (dev_getpixel(x0, y0) == fill_color) {
84 return;
85 }
86 }
87
88 Qup.run = ff_buf1;
89 Qdn.run = ff_buf2;
90
91 // save the border and fill values in global variables
92 ucBorder = border_color;
93
94 // initialize the queues
95 Qup.pQ = &Qdn; // pointer to opposite queue
96 Qup.d = UP; // direction for queue
97 Qup.h = -1;
98 Qup.t = 0;
99
100 Qdn.pQ = &Qup;
101 Qdn.d = DN;
102 Qdn.h = -1;
103 Qdn.t = 0;
104
105 // put the seed run in the up queue
106 Q = &Qup;
107 ff_add_queue(Q, ff_scan_left(x0, y0, ucBorder, scan_type),
108 ff_scan_right(x0, y0, ucBorder, scan_type), y0, NOT_FILLED);
109
110 // main loop
111 for (;;) {
112 if (dev_events(0) < 0) {
113 break;
114 }
115
116 // if the queue is empty, switch queues
117 if (Q->n == 0) {
118 Q = Q->pQ;
119
120 // exit if the other queue is empty
121 if (Q->n == 0) {
122 break;
123 }
124 }
125
126 // get the first non-filled run from the head of the queue
127 qp = Q->h;
128 while (qp >= Q->t) {
129 if (!Q->run[qp].f) {
130 y = Q->run[qp].y;
131 xl = Q->run[qp].xl;
132 xr = Q->run[qp].xr;
133
134 // fill the run
135 dev_line(xl, y, xr, y);
136 Q->run[qp].f = FILLED;
137 Q->n--;
138 break;
139 } else {
140 qp--;
141 }
142 }
143
144 // remove previously-filled runs from the current queue
145 if (Q->d == UP) {
146 while ((Q->h > qp) && (Q->run[Q->h].y < (y - 1))) {
147 Q->h--;
148 }
149 } else {
150 while ((Q->h > qp) && (Q->run[Q->h].y > (y + 1))) {
151 Q->h--;
152 }
153 }
154
155 // branch in the current direction
156 xln = ff_next_branch(xl, xr, y + Q->d);
157 while (xln != 0xFFFF) {
158 // determine the starting point for ScanRight
159 x = (xln > xl) ? xln : xl;
160
161 // add the new branch if it's not already in the queue
162 xrn = ff_scan_right(x, y + Q->d, ucBorder, scan_type);
163 if (!ff_in_queue(Q, xln, xrn, y + Q->d)) {
164 ff_add_queue(Q, xln, xrn, y + Q->d, NOT_FILLED);
165 }
166
167 // if the new branch does not extend beyond the current run,
168 // look for another branch
169 if (xrn > (xr - 2)) {
170 break;
171 }
172 else {
173 x = xrn + 2;
174 xln = ff_next_branch(x, xr, y + Q->d);
175 }
176 }
177
178 // branch in the opposite direction
179 bChangeDirection = 0;
180 xln = ff_next_branch(xl, xr, y - Q->d);
181 while (xln != 0xFFFF) {
182 // determine the starting point for ScanRight
183 x = (xln > xl) ? xln : xl;
184
185 // add the new branch to the opposite queue if it is not
186 // already in the current queue
187 xrn = ff_scan_right(x, y - Q->d, ucBorder, scan_type);
188 if (!ff_in_queue(Q, xln, xrn, y - Q->d)) {
189 ff_add_queue(Q->pQ, xln, xrn, y - Q->d, NOT_FILLED);
190 bChangeDirection = 1;
191 }
192
193 // if the new branch does not extend beyond the current run,
194 // look for another branch
195 if (xrn > (xr - 2)) {
196 break;
197 }
198 else {
199 x = xrn + 2;
200 xln = ff_next_branch(x, xr, y - Q->d);
201 }
202 }
203
204 // change direction if any turns were detected
205 if (bChangeDirection) {
206 // select the opposite queue
207 Q = Q->pQ;
208
209 // copy the current run to the opposite queue
210 ff_add_queue(Q, xl, xr, y, FILLED);
211 }
212 }
213
214 // cleanup
215 dev_setcolor(pcolor);
216}
217
218uint16_t ff_scan_left(uint16_t xl, uint16_t y, long ucPixel, int f) {
219 long v;
220
221 if (f == SCAN_UNTIL) {
222 // return 0xFFFF if starting pixel is a border pixel
223 if (dev_getpixel(xl, y) == ucPixel) {
224 return 0xFFFF;
225 }
226
227 do {
228 xl--;
229 // clip
230 if (xl == 0xFFFF || xl < dev_Vx1) {
231 break;
232 }
233 v = dev_getpixel(xl, y);
234 } while (v != ucPixel);
235 } else {
236 // f == SCAN_WHILE
237 // return 0xFFFF if starting pixel is not a border pixel
238 if (dev_getpixel(xl, y) != ucPixel) {
239 return 0xFFFF;
240 }
241
242 do {
243 xl--;
244 // clip
245 if (xl == 0xFFFF || xl < dev_Vx1) {
246 break;
247 }
248 v = dev_getpixel(xl, y);
249 } while (v == ucPixel);
250 }
251 return ++xl;
252}
253
254uint16_t ff_scan_right(uint16_t xr, uint16_t y, long ucPixel, int f) {
255 long v;
256
257 if (f == SCAN_UNTIL) {
258 // return 0xFFFF if starting pixel is a border pixel
259 if (dev_getpixel(xr, y) == ucPixel) {
260 return 0xFFFF;
261 }
262
263 do {
264 xr++;
265
266 // clip
267 if (xr > dev_Vx2) {
268 break;
269 }
270 v = dev_getpixel(xr, y);
271 } while (v != ucPixel);
272 } else {
273 // f == SCAN_WHILE
274 // return 0xFFFF if starting pixel is not a border pixel
275 if (dev_getpixel(xr, y) != ucPixel) {
276 return 0xFFFF;
277 }
278
279 do {
280 xr++;
281 // clip
282 if (xr > dev_Vx2) {
283 break;
284 }
285 v = dev_getpixel(xr, y);
286 } while (v == ucPixel);
287 }
288
289 return --xr;
290}
291
292uint16_t ff_next_branch(uint16_t xl, uint16_t xr, int y) {
293 uint16_t xln;
294
295 // clip y
296 if ((y < dev_Vy1) || (y > dev_Vy2)) {
297 return 0xFFFF;
298 }
299
300 // look for a branch adjacent to the first pixel in the run
301 xln = ff_scan_left(xl, y, ucBorder, scan_type);
302
303 // if the adjacent pixel is on the border, scan for the
304 // first non-border pixel
305 if (xln == 0xFFFF) {
306 xln = ff_scan_right(xl, y, ucBorder, (scan_type == SCAN_WHILE) ? SCAN_UNTIL : SCAN_WHILE);
307 if (xln < xr) {
308 xln++;
309 } else {
310 xln = 0xFFFF;
311 }
312 }
313
314 return xln;
315}
316
317void ff_add_queue(QUEUE *Q, uint16_t xl, uint16_t xr, int y, int f) {
318 int qp;
319 int i;
320
321 if (Q->d == UP) {
322 // find the last larger queue y-value
323 for (qp = Q->t; qp <= Q->h; qp++) {
324 if (Q->run[qp].y <= y) {
325 break;
326 }
327 }
328 } else {
329 // find the last smaller queue y-value
330 for (qp = Q->t; qp <= Q->h; qp++) {
331 if (Q->run[qp].y >= y) {
332 break;
333 }
334 }
335 }
336
337 // expand the queue if necessary
338 if (qp <= Q->h) {
339 // update the head pointer
340 Q->h++;
341
342 // expand up
343 for (i = Q->h; i > qp; --i) {
344 Q->run[i].xl = Q->run[i - 1].xl;
345 Q->run[i].xr = Q->run[i - 1].xr;
346 Q->run[i].y = Q->run[i - 1].y;
347 Q->run[i].f = Q->run[i - 1].f;
348 }
349 } else {
350 // can't insert in queue; add to head
351 Q->h++;
352 }
353
354 // enter the data in the queue
355 Q->run[qp].xl = xl;
356 Q->run[qp].xr = xr;
357 Q->run[qp].y = y;
358 Q->run[qp].f = f;
359
360 // update the number of unfilled runs in the queue
361 if (!f) {
362 Q->n++;
363 }
364}
365
366int ff_in_queue(QUEUE *Q, uint16_t xl, uint16_t xr, int y) {
367 int qp;
368 int bRVal = 0;
369
370 if (Q->d == UP) {
371 // search from head to tail
372 for (qp = Q->h; qp >= 0; --qp) {
373 // quit searching if y is not in the ordered list
374 if (Q->run[qp].y > y) {
375 break;
376 }
377
378 // quit searching if the specified run is in the list
379 if ((Q->run[qp].y == y) && (Q->run[qp].xl == xl) && (Q->run[qp].xr == xr)) {
380 bRVal = 1;
381 break;
382 }
383 }
384 }
385
386 else {
387 // search from head to tail
388 for (qp = Q->h; qp >= 0; --qp) {
389 // quit searching if y is not in the ordered list
390 if (Q->run[qp].y < y) {
391 break;
392 }
393
394 // quit searching if the specified run is in the list
395 if ((Q->run[qp].y == y) && (Q->run[qp].xl == xl) && (Q->run[qp].xr == xr)) {
396 bRVal = 1;
397 break;
398 }
399 }
400 }
401
402 return bRVal;
403}
404
405