1// The floodfill routine.
2// By Shawn Hargreaves.
3//
4// Changes by David Capello:
5// - Adapted to Aseprite
6// - Added non-contiguous mode
7// - Added mask parameter
8//
9// This file is released under the terms of the MIT license.
10// Read LICENSE.txt for more information.
11//
12// TODO rewrite this algorithm from scratch
13
14#ifdef HAVE_CONFIG_H
15#include "config.h"
16#endif
17
18#include "base/base.h"
19#include "doc/algo.h"
20#include "doc/image.h"
21#include "doc/mask.h"
22#include "doc/primitives.h"
23#include "doc/primitives_fast.h"
24
25#include <climits>
26#include <cmath>
27#include <vector>
28
29namespace doc {
30namespace algorithm {
31
32struct FLOODED_LINE { // store segments which have been flooded
33 short flags; // status of the segment
34 short lpos, rpos; // left and right ends of segment
35 short y; // y coordinate of the segment
36 int next; // linked list if several per line
37};
38
39/* Note: a 'short' is not sufficient for 'next' above in some corner cases. */
40
41
42static std::vector<FLOODED_LINE> flood_buf;
43static int flood_count; /* number of flooded segments */
44
45#define FLOOD_IN_USE 1
46#define FLOOD_TODO_ABOVE 2
47#define FLOOD_TODO_BELOW 4
48
49#define FLOOD_LINE(c) (&flood_buf[c])
50
51static inline bool color_equal_32_raw(color_t c1, color_t c2)
52{
53 return (c1 == c2);
54}
55
56static inline bool color_equal_32(color_t c1, color_t c2, int tolerance)
57{
58 if (tolerance == 0)
59 return (c1 == c2) || (rgba_geta(c1) == 0 && rgba_geta(c2) == 0);
60 else {
61 int r1 = rgba_getr(c1);
62 int g1 = rgba_getg(c1);
63 int b1 = rgba_getb(c1);
64 int a1 = rgba_geta(c1);
65 int r2 = rgba_getr(c2);
66 int g2 = rgba_getg(c2);
67 int b2 = rgba_getb(c2);
68 int a2 = rgba_geta(c2);
69
70 if (a1 == 0 && a2 == 0)
71 return true;
72
73 return ((ABS(r1-r2) <= tolerance) &&
74 (ABS(g1-g2) <= tolerance) &&
75 (ABS(b1-b2) <= tolerance) &&
76 (ABS(a1-a2) <= tolerance));
77 }
78}
79
80static inline bool color_equal_16(color_t c1, color_t c2, int tolerance)
81{
82 if (tolerance == 0)
83 return (c1 == c2) || (graya_geta(c1) == 0 && graya_geta(c2) == 0);
84 else {
85 int k1 = graya_getv(c1);
86 int a1 = graya_geta(c1);
87 int k2 = graya_getv(c2);
88 int a2 = graya_geta(c2);
89
90 if (a1 == 0 && a2 == 0)
91 return true;
92
93 return ((ABS(k1-k2) <= tolerance) &&
94 (ABS(a1-a2) <= tolerance));
95 }
96}
97
98static inline bool color_equal_8(color_t c1, color_t c2, int tolerance)
99{
100 if (tolerance == 0)
101 return (c1 == c2);
102 else
103 return ABS((int)c1 - (int)c2) <= tolerance;
104}
105
106template<typename ImageTraits>
107static inline bool color_equal(color_t c1, color_t c2, int tolerance)
108{
109 static_assert(false && sizeof(ImageTraits), "Invalid color comparison");
110 return false;
111}
112
113template<>
114inline bool color_equal<RgbTraits>(color_t c1, color_t c2, int tolerance)
115{
116 return color_equal_32(c1, c2, tolerance);
117}
118
119template<>
120inline bool color_equal<GrayscaleTraits>(color_t c1, color_t c2, int tolerance)
121{
122 return color_equal_16(c1, c2, tolerance);
123}
124
125template<>
126inline bool color_equal<IndexedTraits>(color_t c1, color_t c2, int tolerance)
127{
128 return color_equal_8(c1, c2, tolerance);
129}
130
131template<>
132inline bool color_equal<TilemapTraits>(color_t c1, color_t c2, int tolerance)
133{
134 return color_equal_32_raw(c1, c2);
135}
136
137
138
139/* flooder:
140 * Fills a horizontal line around the specified position, and adds it
141 * to the list of drawn segments. Returns the first x coordinate after
142 * the part of the line which it has dealt with.
143 */
144static int flooder(const Image* image,
145 const Mask* mask,
146 int x, int y,
147 const gfx::Rect& bounds,
148 color_t src_color, int tolerance, void *data, AlgoHLine proc)
149{
150#define MASKED(u, v) \
151 (mask && \
152 (!mask->bounds().contains(u, v) || \
153 (mask->bitmap() && \
154 !get_pixel_fast<BitmapTraits>(mask->bitmap(), \
155 (u)-mask->bounds().x, \
156 (v)-mask->bounds().y))))
157
158 FLOODED_LINE *p;
159 int left = 0, right = 0;
160 int c;
161
162 switch (image->pixelFormat()) {
163
164 case IMAGE_RGB:
165 {
166 uint32_t* address = reinterpret_cast<uint32_t*>(image->getPixelAddress(0, y));
167
168 // Check start pixel
169 if (!color_equal_32((int)*(address+x), src_color, tolerance) || MASKED(x, y))
170 return x+1;
171
172 // Work left from starting point
173 for (left=x-1; left>=bounds.x; left--) {
174 if (!color_equal_32((int)*(address+left), src_color, tolerance) || MASKED(left, y))
175 break;
176 }
177
178 // Work right from starting point
179 for (right=x+1; right<bounds.x2(); right++) {
180 if (!color_equal_32((int)*(address+right), src_color, tolerance) || MASKED(right, y))
181 break;
182 }
183 }
184 break;
185
186 case IMAGE_GRAYSCALE:
187 {
188 uint16_t* address = reinterpret_cast<uint16_t*>(image->getPixelAddress(0, y));
189
190 // Check start pixel
191 if (!color_equal_16((int)*(address+x), src_color, tolerance) || MASKED(x, y))
192 return x+1;
193
194 // Work left from starting point
195 for (left=x-1; left>=bounds.x; left--) {
196 if (!color_equal_16((int)*(address+left), src_color, tolerance) || MASKED(left, y))
197 break;
198 }
199
200 // Work right from starting point
201 for (right=x+1; right<bounds.x2(); right++) {
202 if (!color_equal_16((int)*(address+right), src_color, tolerance) || MASKED(right, y))
203 break;
204 }
205 }
206 break;
207
208 case IMAGE_INDEXED:
209 {
210 uint8_t* address = image->getPixelAddress(0, y);
211
212 // Check start pixel
213 if (!color_equal_8((int)*(address+x), src_color, tolerance) || MASKED(x, y))
214 return x+1;
215
216 // Work left from starting point
217 for (left=x-1; left>=bounds.x; left--) {
218 if (!color_equal_8((int)*(address+left), src_color, tolerance) || MASKED(left, y))
219 break;
220 }
221
222 // Work right from starting point
223 for (right=x+1; right<bounds.x2(); right++) {
224 if (!color_equal_8((int)*(address+right), src_color, tolerance) || MASKED(right, y))
225 break;
226 }
227 }
228 break;
229
230 case IMAGE_TILEMAP:
231 {
232 // TODO add support for mask
233
234 uint32_t* address = reinterpret_cast<uint32_t*>(image->getPixelAddress(0, y));
235
236 // Check start pixel
237 if (!color_equal_32_raw((int)*(address+x), src_color))
238 return x+1;
239
240 // Work left from starting point
241 for (left=x-1; left>=bounds.x; left--) {
242 if (!color_equal_32_raw((int)*(address+left), src_color))
243 break;
244 }
245
246 // Work right from starting point
247 for (right=x+1; right<bounds.x2(); right++) {
248 if (!color_equal_32_raw((int)*(address+right), src_color))
249 break;
250 }
251 }
252 break;
253
254 default:
255 // Check start pixel
256 if (get_pixel(image, x, y) != src_color || MASKED(x, y))
257 return x+1;
258
259 // Work left from starting point
260 for (left=x-1; left>=bounds.x; left--) {
261 if (get_pixel(image, left, y) != src_color || MASKED(left, y))
262 break;
263 }
264
265 // Work right from starting point
266 for (right=x+1; right<bounds.x2(); right++) {
267 if (get_pixel(image, right, y) != src_color || MASKED(right, y))
268 break;
269 }
270 break;
271 }
272
273 left++;
274 right--;
275
276 /* draw the line */
277 (*proc)(left, y, right, data);
278
279 /* store it in the list of flooded segments */
280 c = y;
281 p = FLOOD_LINE(c);
282
283 if (p->flags) {
284 while (p->next) {
285 c = p->next;
286 p = FLOOD_LINE(c);
287 }
288
289 p->next = c = flood_count++;
290 flood_buf.resize(flood_count);
291 p = FLOOD_LINE(c);
292 }
293
294 p->flags = FLOOD_IN_USE;
295 p->lpos = left;
296 p->rpos = right;
297 p->y = y;
298 p->next = 0;
299
300 if (y > bounds.y)
301 p->flags |= FLOOD_TODO_ABOVE;
302
303 if (y+1 < bounds.y2())
304 p->flags |= FLOOD_TODO_BELOW;
305
306 return right+2;
307}
308
309
310
311/* check_flood_line:
312 * Checks a line segment, using the scratch buffer is to store a list of
313 * segments which have already been drawn in order to minimise the required
314 * number of tests.
315 */
316static int check_flood_line(const Image* image,
317 const Mask* mask,
318 int y, int left, int right,
319 const gfx::Rect& bounds,
320 int src_color, int tolerance, void *data, AlgoHLine proc)
321{
322 int c;
323 FLOODED_LINE *p;
324 int ret = false;
325
326 while (left <= right) {
327 c = y;
328
329 for (;;) {
330 p = FLOOD_LINE(c);
331
332 if ((left >= p->lpos) && (left <= p->rpos)) {
333 left = p->rpos+2;
334 break;
335 }
336
337 c = p->next;
338
339 if (!c) {
340 left = flooder(image, mask, left, y, bounds, src_color, tolerance, data, proc);
341 ret = true;
342 break;
343 }
344 }
345 }
346
347 return ret;
348}
349
350template<typename ImageTraits>
351static void replace_color(const Image* image, const gfx::Rect& bounds, int src_color, int tolerance, void* data, AlgoHLine proc)
352{
353 typename ImageTraits::address_t address;
354
355 for (int y=bounds.y; y<bounds.y2(); ++y) {
356 address = reinterpret_cast<typename ImageTraits::address_t>(image->getPixelAddress(bounds.x, y));
357
358 for (int x=bounds.x; x<bounds.x2(); ++x, ++address) {
359 int right = -1;
360
361 if (color_equal<ImageTraits>((int)(*address), src_color, tolerance)) {
362 ++address;
363 for (right=x+1; right<bounds.x2(); ++right, ++address) {
364 if (!color_equal<ImageTraits>((int)(*address), src_color, tolerance))
365 break;
366 }
367 (*proc)(x, y, right-1, data);
368 x = right;
369 }
370 }
371 }
372}
373
374/* floodfill:
375 * Fills an enclosed area (starting at point x, y) with the specified color.
376 */
377void floodfill(const Image* image,
378 const Mask* mask,
379 const int x, const int y,
380 const gfx::Rect& bounds,
381 const doc::color_t src_color,
382 const int tolerance,
383 const bool contiguous,
384 const bool isEightConnected,
385 void* data,
386 AlgoHLine proc)
387{
388 // Make sure we have a valid starting point
389 if ((x < 0) || (x >= image->width()) ||
390 (y < 0) || (y >= image->height()))
391 return;
392
393 // Non-contiguous case, we replace colors in the whole image.
394 if (!contiguous) {
395 switch (image->pixelFormat()) {
396 case IMAGE_RGB:
397 replace_color<RgbTraits>(image, bounds, src_color, tolerance, data, proc);
398 break;
399 case IMAGE_GRAYSCALE:
400 replace_color<GrayscaleTraits>(image, bounds, src_color, tolerance, data, proc);
401 break;
402 case IMAGE_INDEXED:
403 replace_color<IndexedTraits>(image, bounds, src_color, tolerance, data, proc);
404 break;
405 case IMAGE_TILEMAP:
406 replace_color<TilemapTraits>(image, bounds, src_color, tolerance, data, proc);
407 break;
408 }
409 return;
410 }
411
412 /* set up the list of flooded segments */
413 flood_buf.resize(image->height());
414 flood_count = image->height();
415 FLOODED_LINE* p = (FLOODED_LINE*)&flood_buf[0];
416 for (int c=0; c<flood_count; c++) {
417 p[c].flags = 0;
418 p[c].lpos = SHRT_MAX;
419 p[c].rpos = SHRT_MIN;
420 p[c].y = y;
421 p[c].next = 0;
422 }
423
424 // Start up the flood algorithm
425 flooder(image, mask, x, y, bounds, src_color, tolerance, data, proc);
426
427 // Continue as long as there are some segments still to test
428 bool done;
429 do {
430 done = true;
431
432 // For each line on the screen
433 for (int c=0; c<flood_count; c++) {
434 p = FLOOD_LINE(c);
435
436 // Check below the segment?
437 if (p->flags & FLOOD_TODO_BELOW) {
438 p->flags &= ~FLOOD_TODO_BELOW;
439
440 if (isEightConnected) {
441 if (p->lpos+1 < bounds.x2() &&
442 check_flood_line(image, mask, p->y+1, p->lpos+1, p->rpos, bounds,
443 src_color, tolerance, data, proc)) {
444 done = false;
445 p = FLOOD_LINE(c);
446 }
447
448 if (p->lpos-1 >= 0 &&
449 check_flood_line(image, mask, p->y+1, p->lpos-1, p->rpos, bounds,
450 src_color, tolerance, data, proc)) {
451 done = false;
452 p = FLOOD_LINE(c);
453 }
454
455 if (p->rpos+1 < bounds.x2() &&
456 check_flood_line(image, mask, p->y+1, p->lpos, p->rpos+1, bounds,
457 src_color, tolerance, data, proc)) {
458 done = false;
459 p = FLOOD_LINE(c);
460 }
461
462 if (p->rpos-1 >= 0 &&
463 check_flood_line(image, mask, p->y+1, p->lpos, p->rpos-1, bounds,
464 src_color, tolerance, data, proc)) {
465 done = false;
466 p = FLOOD_LINE(c);
467 }
468 }
469
470 if (check_flood_line(image, mask, p->y+1, p->lpos, p->rpos, bounds,
471 src_color, tolerance, data, proc)) {
472 done = false;
473 p = FLOOD_LINE(c);
474 }
475 }
476
477 // Check above the segment?
478 if (p->flags & FLOOD_TODO_ABOVE) {
479 p->flags &= ~FLOOD_TODO_ABOVE;
480
481 if (isEightConnected) {
482 if (p->lpos+1 < bounds.x2() &&
483 check_flood_line(image, mask, p->y-1, p->lpos+1, p->rpos, bounds,
484 src_color, tolerance, data, proc)) {
485 done = false;
486 p = FLOOD_LINE(c);
487 }
488
489 if (p->lpos-1 >= 0 &&
490 check_flood_line(image, mask, p->y-1, p->lpos-1, p->rpos, bounds,
491 src_color, tolerance, data, proc)) {
492 done = false;
493 p = FLOOD_LINE(c);
494 }
495
496 if (p->rpos+1 < bounds.x2() &&
497 check_flood_line(image, mask, p->y-1, p->lpos, p->rpos+1, bounds,
498 src_color, tolerance, data, proc)) {
499 done = false;
500 p = FLOOD_LINE(c);
501 }
502
503 if (p->rpos-1 >= 0 &&
504 check_flood_line(image, mask, p->y-1, p->lpos, p->rpos-1, bounds,
505 src_color, tolerance, data, proc)) {
506 done = false;
507 p = FLOOD_LINE(c);
508 }
509 }
510
511 if (check_flood_line(image, mask, p->y-1, p->lpos, p->rpos, bounds,
512 src_color, tolerance, data, proc)) {
513 done = false;
514
515 // Special case shortcut for going backwards
516 if ((c > bounds.y) && (c < bounds.y2()))
517 c -= 2;
518 }
519 }
520 }
521 } while (!done);
522}
523
524} // namespace algorithm
525} // namespace doc
526