source: libpipi/trunk/pipi/paint/floodfill.c @ 2772

Last change on this file since 2772 was 2772, checked in by Sam Hocevar, 12 years ago
  • pipi.h: add the PIPI_PIXELS_MASK_C pixel format for canvas boundaries.
  • pipi.h: rename RGBA32 and BGR24 into RGBA_C and BGR_C.
File size: 9.1 KB
Line 
1/*
2 *  libpipi       Proper image processing implementation library
3 *  Copyright (c) 2004-2008 Sam Hocevar <sam@zoy.org>
4 *                2008 Jean-Yves Lamoureux <jylam@lnxscene.org>
5 *                All Rights Reserved
6 *
7 *  $Id$
8 *
9 *  This library is free software. It comes without any warranty, to
10 *  the extent permitted by applicable law. You can redistribute it
11 *  and/or modify it under the terms of the Do What The Fuck You Want
12 *  To Public License, Version 2, as published by Sam Hocevar. See
13 *  http://sam.zoy.org/wtfpl/COPYING for more details.
14 */
15
16/*
17 * floodfill.c: flood fill (4 neighbours) functions
18 */
19
20#include "config.h"
21#include "common.h"
22
23#include <stdlib.h>
24#include <stdio.h>
25#include <string.h>
26#include <math.h>
27
28#include "pipi.h"
29#include "pipi_internals.h"
30
31#define STACKSIZE (1<<20)
32
33static void  pipi_flood_fill_stack_scanline_u32(pipi_pixels_t *dstp,
34                                                int x,    int y,
35                                                uint32_t new, uint32_t old);
36static void  pipi_flood_fill_stack_scanline_float(pipi_pixels_t *dstp,
37                                                  int x,    int y,
38                                                  float nr, float ng, float nb, float na,
39                                                  float or, float og, float ob, float oa);
40static int   pop (int *x,int *y, int h);
41static int   push(int x, int y, int h);
42static void  clear_stack(int h);
43static int   stack[STACKSIZE];
44static int   stack_pointer;
45
46static float get_max_color_diff(float r1, float g1, float b1,
47                                float r2, float g2, float b2);
48static int   validate_pixel_f(float r1, float g1, float b1,
49                              float r2, float g2, float b2);
50
51/*
52  Stack based flood fill.
53  Instead of using system stack (calling recursively functions,
54  which can lead to big problems as this stack is a fixed and small sized one),
55  we create our own one.
56  Additionnaly, we use a scanline trick to speed up the whole thing.
57
58  This method is more or less the one described at
59  http://student.kuleuven.be/~m0216922/CG/floodfill.html
60
61*/
62
63/* Public function */
64int pipi_flood_fill(pipi_image_t *src,
65                    int px, int py,
66                    float r, float g, float b, float a)
67{
68    pipi_image_t  *dst = src;
69    pipi_pixels_t *dstp;
70    int w, h;
71
72    if(!src) return -1;
73
74    w = src->w;
75    h = src->h;
76
77    if((px >= src->w) || (py >= src->h) ||
78       (px < 0) || (py < 0)) return -1;
79
80
81    if(src->last_modified == PIPI_PIXELS_RGBA_C) {
82        uint32_t  *dstdata;
83        unsigned char nr, ng, nb, na;
84
85        /* Get ARGB32 pointer */
86        dstp = pipi_getpixels(dst, PIPI_PIXELS_RGBA_C);
87        dstdata = (uint32_t *)dstp->pixels;
88
89        nr = r*255.0f;
90        ng = g*255.0f;
91        nb = b*255.0f;
92        na = a*255.0f;
93
94        dstp->w = w;
95        dstp->h = h;
96        pipi_flood_fill_stack_scanline_u32(dstp, px, py, (na<<24)|(nr<<16)|(ng<<8)|(nb), dstdata[px+py*w]);
97
98    } else {
99        int gray = (dst->last_modified == PIPI_PIXELS_Y_F);
100        float *dstdata;
101        float or, og, ob, oa;
102
103        dstp = gray ? pipi_getpixels(dst, PIPI_PIXELS_Y_F)
104            : pipi_getpixels(dst, PIPI_PIXELS_RGBA_F);
105
106        dstdata = (float *)dstp->pixels;
107
108        or = dstdata[(px+py*w)*4];
109        og = dstdata[(px+py*w)*4 + 1];
110        ob = dstdata[(px+py*w)*4 + 2];
111        oa = dstdata[(px+py*w)*4 + 3];
112
113        dstp->w = w;
114        dstp->h = h;
115
116        pipi_flood_fill_stack_scanline_float(dstp, px, py, r, g, b, a, or, og, ob, oa);
117    }
118
119    return 0;
120}
121
122
123/* ARGB32 */
124void pipi_flood_fill_stack_scanline_u32(pipi_pixels_t *dstp,
125                                        int x,    int y,
126                                        uint32_t new, uint32_t old)
127{
128    if(new==old) return;
129
130    clear_stack(dstp->h);
131
132    int yt;
133    int left, right;
134
135    uint32_t *dstdata = (uint32_t *)dstp->pixels;
136
137    if(!push(x, y, dstp->h)) return;
138
139    while(pop(&x, &y, dstp->h))
140    {
141        yt = y;
142        while(yt >= 0 && (dstdata[x+yt*dstp->w] == old)) {
143            yt--;
144        }
145
146        yt++;
147        left = right = 0;
148
149        while(yt < dstp->h && (dstdata[x+yt*dstp->w] == old))
150        {
151            uint32_t *cur_line = &dstdata[(yt*dstp->w)];
152            int   xp1 = (x+1);
153            int   xm1 = (x-1);
154            cur_line[x]     = new;
155
156            if(!left && x > 0 && (cur_line[xm1] == old))
157            {
158                if(!push(x - 1, yt, dstp->h)) return;
159                left = 1;
160            }
161            else if(left && x > 0 && (cur_line[xm1] != old))
162            {
163                left = 0;
164            }
165            if(!right && x < dstp->w - 1 && (cur_line[xp1] == old))
166            {
167                if(!push(x + 1, yt, dstp->h)) return;
168                right = 1;
169            }
170            else if(right && x < dstp->w - 1 && (cur_line[xp1] != old))
171            {
172                right = 0;
173            }
174            yt++;
175        }
176    }
177}
178
179/* Float version. Much slower, but supports HDR and (soon antialiasing) */
180static void pipi_flood_fill_stack_scanline_float(pipi_pixels_t *dstp,
181                                                 int x,    int y,
182                                                 float nr, float ng, float nb, float na,
183                                                 float or, float og, float ob, float oa)
184{
185    if((nr==or) && (ng==og) && (nb==ob)) return;
186
187    clear_stack(dstp->h);
188
189    int yt;
190    int left, right;
191    float *dstdata = (float *)dstp->pixels;
192
193    if(!push(x, y, dstp->h)) return;
194
195    while(pop(&x, &y, dstp->h))
196    {
197        yt = y;
198        while(yt >= 0 && validate_pixel_f(dstdata[(x+yt*dstp->w)*4] ,
199                                          dstdata[(x+yt*dstp->w)*4 + 1] ,
200                                          dstdata[(x+yt*dstp->w)*4 + 2] ,
201                                          or, og, ob)) {
202            yt--;
203        }
204
205        yt++;
206        left = right = 0;
207
208        while(yt < dstp->h && validate_pixel_f(dstdata[(x+yt*dstp->w)*4] ,
209                                               dstdata[(x+yt*dstp->w)*4 + 1] ,
210                                               dstdata[(x+yt*dstp->w)*4 + 2] ,
211                                               or, og, ob))
212        {
213            float *cur_line = &dstdata[(yt*dstp->w)*4];
214            int   xp1 = (x+1)*4;
215            int   xm1 = (x-1)*4;
216            cur_line[x*4]     = nr;
217            cur_line[x*4 + 1] = ng;
218            cur_line[x*4 + 2] = nb;
219            cur_line[x*4 + 3] = na;
220
221            if(!left && x > 0 && validate_pixel_f(cur_line[xm1],
222                                                  cur_line[xm1 + 1],
223                                                  cur_line[xm1 + 2],
224                                                  or, og, ob))
225            {
226                if(!push(x - 1, yt, dstp->h)) return;
227                left = 1;
228            }
229            else if(left && x > 0 && !validate_pixel_f(cur_line[xm1] ,
230                                                       cur_line[xm1 + 1] ,
231                                                       cur_line[xm1 + 2] ,
232                                                       or, og, ob))
233            {
234                left = 0;
235            }
236            if(!right && x < dstp->w - 1 && validate_pixel_f(cur_line[xp1] ,
237                                                             cur_line[xp1 + 1] ,
238                                                             cur_line[xp1 + 2] ,
239                                                             or, og, ob))
240            {
241                if(!push(x + 1, yt, dstp->h)) return;
242                right = 1;
243            }
244            else if(right && x < dstp->w - 1 && !validate_pixel_f(cur_line[xp1] ,
245                                                                  cur_line[xp1 + 1] ,
246                                                                  cur_line[xp1 + 2],
247                                                                  or, og, ob))
248            {
249                right = 0;
250            }
251            yt++;
252        }
253    }
254}
255
256
257/* Following functions are local  */
258
259static int pop(int *x, int *y, int h)
260{
261    if(stack_pointer > 0)
262    {
263        int p = stack[stack_pointer];
264        *x = p / h;
265        *y = p % h;
266        stack_pointer--;
267        return 1;
268    }
269    else
270    {
271        return 0;
272    }
273}
274
275static int push(int x, int y, int h)
276{
277    if(stack_pointer < STACKSIZE - 1)
278    {
279        stack_pointer++;
280        stack[stack_pointer] = h * x + y;
281        return 1;
282    }
283    else
284    {
285        return 0;
286    }
287}
288
289static void clear_stack(int h)
290{
291    int x, y;
292    while(pop(&x, &y, h));
293}
294
295#define MAX(a, b) (b>a?b:a)
296
297
298/* FIXME : Paves the way to antialiasing, but could be only 3 tests */
299static float get_max_color_diff(float r1, float g1, float b1,
300                                float r2, float g2, float b2)
301{
302    float r = abs(r2-r1);
303    float g = abs(g2-g1);
304    float b = abs(b2-b1);
305
306    return MAX(MAX(r, g), b);
307}
308
309
310static int validate_pixel_f(float r1, float g1, float b1,
311                            float r2, float g2, float b2)
312{
313
314    if(get_max_color_diff(r1, g1, b1,
315                          r2, g2, b2)
316       == 0) return 1;
317    else
318        return 0;
319}
Note: See TracBrowser for help on using the repository browser.