File: algofill.cpp

package info (click to toggle)
aseprite 1.0.5+ds-2
  • links: PTS, VCS
  • area: main
  • in suites: jessie, jessie-kfreebsd
  • size: 9,504 kB
  • ctags: 18,296
  • sloc: cpp: 84,144; ansic: 49,119; xml: 1,971; objc: 1,211; asm: 117; makefile: 45
file content (399 lines) | stat: -rw-r--r-- 10,248 bytes parent folder | download
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
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
// The floodfill routine.
// By Shawn Hargreaves.
// Adapted to Aseprite by David Capello
// Added non-contiguous mode by David Capello
//
// This file is released under the terms of the MIT license.
// Read LICENSE.txt for more information.

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "raster/algo.h"
#include "raster/image.h"
#include "raster/primitives.h"

#include <climits>
#include <cmath>
#include <vector>

namespace raster {

struct FLOODED_LINE {   // store segments which have been flooded
  short flags;          // status of the segment
  short lpos, rpos;     // left and right ends of segment
  short y;              // y coordinate of the segment
  int next;             // linked list if several per line
};

/* Note: a 'short' is not sufficient for 'next' above in some corner cases. */


static std::vector<FLOODED_LINE> flood_buf;
static int flood_count;          /* number of flooded segments */

#define FLOOD_IN_USE             1
#define FLOOD_TODO_ABOVE         2
#define FLOOD_TODO_BELOW         4

#define FLOOD_LINE(c)            (&flood_buf[c])

static inline bool color_equal_32(color_t c1, color_t c2, int tolerance)
{
  if (tolerance == 0)
    return (c1 == c2) || (rgba_geta(c1) == 0 && rgba_geta(c2) == 0);
  else {
    int r1 = rgba_getr(c1);
    int g1 = rgba_getg(c1);
    int b1 = rgba_getb(c1);
    int a1 = rgba_geta(c1);
    int r2 = rgba_getr(c2);
    int g2 = rgba_getg(c2);
    int b2 = rgba_getb(c2);
    int a2 = rgba_geta(c2);

    if (a1 == 0 && a2 == 0)
      return true;

    return ((ABS(r1-r2) <= tolerance) &&
            (ABS(g1-g2) <= tolerance) &&
            (ABS(b1-b2) <= tolerance) &&
            (ABS(a1-a2) <= tolerance));
  }
}

static inline bool color_equal_16(color_t c1, color_t c2, int tolerance)
{
  if (tolerance == 0)
    return (c1 == c2) || (graya_geta(c1) == 0 && graya_geta(c2) == 0);
  else {
    int k1 = graya_getv(c1);
    int a1 = graya_geta(c1);
    int k2 = graya_getv(c2);
    int a2 = graya_geta(c2);

    if (a1 == 0 && a2 == 0)
      return true;

    return ((ABS(k1-k2) <= tolerance) &&
            (ABS(a1-a2) <= tolerance));
  }
}

static inline bool color_equal_8(color_t c1, color_t c2, int tolerance)
{
  if (tolerance == 0)
    return (c1 == c2);
  else
    return ABS((int)c1 - (int)c2) <= tolerance;
}

template<typename ImageTraits>
static inline bool color_equal(color_t c1, color_t c2, int tolerance)
{
  static_assert(false && sizeof(ImageTraits), "Invalid color comparison");
}

template<>
inline bool color_equal<RgbTraits>(color_t c1, color_t c2, int tolerance)
{
  return color_equal_32(c1, c2, tolerance);
}

template<>
inline bool color_equal<GrayscaleTraits>(color_t c1, color_t c2, int tolerance)
{
  return color_equal_16(c1, c2, tolerance);
}

template<>
inline bool color_equal<IndexedTraits>(color_t c1, color_t c2, int tolerance)
{
  return color_equal_8(c1, c2, tolerance);
}



/* flooder:
 *  Fills a horizontal line around the specified position, and adds it
 *  to the list of drawn segments. Returns the first x coordinate after
 *  the part of the line which it has dealt with.
 */
static int flooder(Image *image, int x, int y,
  const gfx::Rect& bounds,
  color_t src_color, int tolerance, void *data, AlgoHLine proc)
{
  FLOODED_LINE *p;
  int left = 0, right = 0;
  int c;

  switch (image->pixelFormat()) {

    case IMAGE_RGB:
      {
        uint32_t* address = reinterpret_cast<uint32_t*>(image->getPixelAddress(0, y));

        // Check start pixel
        if (!color_equal_32((int)*(address+x), src_color, tolerance))
          return x+1;

        // Work left from starting point
        for (left=x-1; left>=bounds.x; left--) {
          if (!color_equal_32((int)*(address+left), src_color, tolerance))
            break;
        }

        // Work right from starting point
        for (right=x+1; right<bounds.x2(); right++) {
          if (!color_equal_32((int)*(address+right), src_color, tolerance))
            break;
        }
      }
      break;

    case IMAGE_GRAYSCALE:
      {
        uint16_t* address = reinterpret_cast<uint16_t*>(image->getPixelAddress(0, y));

        // Check start pixel
        if (!color_equal_16((int)*(address+x), src_color, tolerance))
          return x+1;

        // Work left from starting point
        for (left=x-1; left>=bounds.x; left--) {
          if (!color_equal_16((int)*(address+left), src_color, tolerance))
            break;
        }

        // Work right from starting point
        for (right=x+1; right<bounds.x2(); right++) {
          if (!color_equal_16((int)*(address+right), src_color, tolerance))
            break;
        }
      }
      break;

    case IMAGE_INDEXED:
      {
        uint8_t* address = image->getPixelAddress(0, y);

        // Check start pixel
        if (!color_equal_8((int)*(address+x), src_color, tolerance))
          return x+1;

        // Work left from starting point
        for (left=x-1; left>=bounds.x; left--) {
          if (!color_equal_8((int)*(address+left), src_color, tolerance))
            break;
        }

        // Work right from starting point
        for (right=x+1; right<bounds.x2(); right++) {
          if (!color_equal_8((int)*(address+right), src_color, tolerance))
            break;
        }
      }
      break;

    default:
      // Check start pixel
      if (get_pixel(image, x, y) != src_color)
        return x+1;

      // Work left from starting point
      for (left=x-1; left>=bounds.x; left--) {
        if (get_pixel(image, left, y) != src_color)
          break;
      }

      // Work right from starting point
      for (right=x+1; right<bounds.x2(); right++) {
        if (get_pixel(image, right, y) != src_color)
          break;
      }
      break;
  }

  left++;
  right--;

  /* draw the line */
  (*proc)(left, y, right, data);

  /* store it in the list of flooded segments */
  c = y;
  p = FLOOD_LINE(c);

  if (p->flags) {
    while (p->next) {
      c = p->next;
      p = FLOOD_LINE(c);
    }

    p->next = c = flood_count++;
    flood_buf.resize(flood_count);
    p = FLOOD_LINE(c);
  }

  p->flags = FLOOD_IN_USE;
  p->lpos = left;
  p->rpos = right;
  p->y = y;
  p->next = 0;

  if (y > bounds.y)
    p->flags |= FLOOD_TODO_ABOVE;

  if (y+1 < bounds.y2())
    p->flags |= FLOOD_TODO_BELOW;

  return right+2;
}



/* check_flood_line:
 *  Checks a line segment, using the scratch buffer is to store a list of
 *  segments which have already been drawn in order to minimise the required
 *  number of tests.
 */
static int check_flood_line(Image* image, int y, int left, int right,
  const gfx::Rect& bounds,
  int src_color, int tolerance, void *data, AlgoHLine proc)
{
  int c;
  FLOODED_LINE *p;
  int ret = false;

  while (left <= right) {
    c = y;

    for (;;) {
      p = FLOOD_LINE(c);

      if ((left >= p->lpos) && (left <= p->rpos)) {
        left = p->rpos+2;
        break;
      }

      c = p->next;

      if (!c) {
        left = flooder(image, left, y, bounds, src_color, tolerance, data, proc);
        ret = true;
        break;
      }
    }
  }

  return ret;
}

template<typename ImageTraits>
static void replace_color(Image* image, const gfx::Rect& bounds, int src_color, int tolerance, void *data, AlgoHLine proc)
{
  typename ImageTraits::address_t address;

  for (int y=bounds.y; y<bounds.y2(); ++y) {
    address = reinterpret_cast<typename ImageTraits::address_t>(image->getPixelAddress(bounds.x, y));

    for (int x=bounds.x; x<bounds.x2(); ++x, ++address) {
      int right = -1;

      if (color_equal<ImageTraits>((int)(*address), src_color, tolerance)) {
        ++address;
        for (right=x+1; right<bounds.x2(); ++right, ++address) {
          if (!color_equal<ImageTraits>((int)(*address), src_color, tolerance))
            break;
        }
        (*proc)(x, y, right-1, data);
        x = right;
      }
    }
  }
}

/* floodfill:
 *  Fills an enclosed area (starting at point x, y) with the specified color.
 */
void algo_floodfill(Image* image, int x, int y,
  const gfx::Rect& bounds,
  int tolerance, bool contiguous,
  void* data, AlgoHLine proc)
{
  // Make sure we have a valid starting point
  if ((x < 0) || (x >= image->width()) ||
      (y < 0) || (y >= image->height()))
    return;

  // What color to replace?
  color_t src_color = get_pixel(image, x, y);

  // Non-contiguous case, we replace colors in the whole image.
  if (!contiguous) {
    switch (image->pixelFormat()) {
      case IMAGE_RGB:
        replace_color<RgbTraits>(image, bounds, src_color, tolerance, data, proc);
        break;
      case IMAGE_GRAYSCALE:
        replace_color<GrayscaleTraits>(image, bounds, src_color, tolerance, data, proc);
        break;
      case IMAGE_INDEXED:
        replace_color<IndexedTraits>(image, bounds, src_color, tolerance, data, proc);
        break;
    }
    return;
  }

  /* set up the list of flooded segments */
  flood_buf.resize(image->height());
  flood_count = image->height();
  FLOODED_LINE* p = (FLOODED_LINE*)&flood_buf[0];
  for (int c=0; c<flood_count; c++) {
    p[c].flags = 0;
    p[c].lpos = SHRT_MAX;
    p[c].rpos = SHRT_MIN;
    p[c].y = y;
    p[c].next = 0;
  }

  // Start up the flood algorithm
  flooder(image, x, y, bounds, src_color, tolerance, data, proc);

  // Continue as long as there are some segments still to test
  bool done;
  do {
    done = true;

    // For each line on the screen
    for (int c=0; c<flood_count; c++) {

      p = FLOOD_LINE(c);

      // Check below the segment?
      if (p->flags & FLOOD_TODO_BELOW) {
        p->flags &= ~FLOOD_TODO_BELOW;
        if (check_flood_line(image, p->y+1, p->lpos, p->rpos, bounds,
            src_color, tolerance, data, proc)) {
          done = false;
          p = FLOOD_LINE(c);
        }
      }

      // Check above the segment?
      if (p->flags & FLOOD_TODO_ABOVE) {
        p->flags &= ~FLOOD_TODO_ABOVE;
        if (check_flood_line(image, p->y-1, p->lpos, p->rpos, bounds,
                             src_color, tolerance, data, proc)) {
          done = false;
          // Special case shortcut for going backwards
          if ((c > bounds.y) && (c < bounds.y2()))
            c -= 2;
        }
      }
    }
  } while (!done);
}

} // namespace raster