source: libpipi/trunk/pipi/fill/floodfill.c @ 2676

Last change on this file since 2676 was 2676, checked in by Jean-Yves Lamoureux, 14 years ago
  • First shot of a floodfiller (both u32 and float, 4 neighbours)
File size: 8.9 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,
39                                                  float or, float og, float ob);
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)
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_RGBA32) {
82        uint32_t  *dstdata;
83        unsigned char nr, ng, nb;
84
85        /* Get ARGB32 pointer */
86        dstp = pipi_getpixels(dst, PIPI_PIXELS_RGBA32);
87        dstdata = (uint32_t *)dstp->pixels;
88
89        nr = r*255.0f;
90        ng = g*255.0f;
91        nb = b*255.0f;
92
93        dstp->w = w;
94        dstp->h = h;
95        pipi_flood_fill_stack_scanline_u32(dstp, px, py, (nr<<16)|(ng<<8)|(nb), dstdata[px+py*w]);
96
97    } else {
98        int gray = (dst->last_modified == PIPI_PIXELS_Y_F);
99        float *dstdata;
100        float or, og, ob;
101
102        dstp = gray ? pipi_getpixels(dst, PIPI_PIXELS_Y_F)
103            : pipi_getpixels(dst, PIPI_PIXELS_RGBA_F);
104
105        dstdata = (float *)dstp->pixels;
106
107        or = dstdata[(px+py*w)*4];
108        og = dstdata[(px+py*w)*4 + 1];
109        ob = dstdata[(px+py*w)*4 + 2];
110
111        dstp->w = w;
112        dstp->h = h;
113
114        pipi_flood_fill_stack_scanline_float(dstp, px, py, r, g, b, or, og, ob);
115    }
116
117    return 0;
118}
119
120
121/* ARGB32 */
122void pipi_flood_fill_stack_scanline_u32(pipi_pixels_t *dstp,
123                                        int x,    int y,
124                                        uint32_t new, uint32_t old)
125{
126    if(new==old) return;
127
128    clear_stack(dstp->h);
129
130    int yt;
131    int left, right;
132
133    uint32_t *dstdata = (uint32_t *)dstp->pixels;
134
135    if(!push(x, y, dstp->h)) return;
136
137    while(pop(&x, &y, dstp->h))
138    {
139        yt = y;
140        while(yt >= 0 && (dstdata[x+yt*dstp->w] == old)) {
141            yt--;
142        }
143
144        yt++;
145        left = right = 0;
146
147        while(yt < dstp->h && (dstdata[x+yt*dstp->w] == old))
148        {
149            uint32_t *cur_line = &dstdata[(yt*dstp->w)];
150            int   xp1 = (x+1);
151            int   xm1 = (x-1);
152            cur_line[x]     = new;
153
154            if(!left && x > 0 && (cur_line[xm1] == old))
155            {
156                if(!push(x - 1, yt, dstp->h)) return;
157                left = 1;
158            }
159            else if(left && x > 0 && (cur_line[xm1] != old))
160            {
161                left = 0;
162            }
163            if(!right && x < dstp->w - 1 && (cur_line[xp1] == old))
164            {
165                if(!push(x + 1, yt, dstp->h)) return;
166                right = 1;
167            }
168            else if(right && x < dstp->w - 1 && (cur_line[xp1] != old))
169            {
170                right = 0;
171            }
172            yt++;
173        }
174    }
175}
176
177/* Float version. Much slower, but supports HDR and (soon antialiasing) */
178static void pipi_flood_fill_stack_scanline_float(pipi_pixels_t *dstp,
179                                                 int x,    int y,
180                                                 float nr, float ng, float nb,
181                                                 float or, float og, float ob)
182{
183    if((nr==or) && (ng==og) && (nb==ob)) return;
184
185    clear_stack(dstp->h);
186
187    int yt;
188    int left, right;
189    float *dstdata = (float *)dstp->pixels;
190
191    if(!push(x, y, dstp->h)) return;
192
193    while(pop(&x, &y, dstp->h))
194    {
195        yt = y;
196        while(yt >= 0 && validate_pixel_f(dstdata[(x+yt*dstp->w)*4] ,
197                                          dstdata[(x+yt*dstp->w)*4 + 1] ,
198                                          dstdata[(x+yt*dstp->w)*4 + 2] ,
199                                          or, og, ob)) {
200            yt--;
201        }
202
203        yt++;
204        left = right = 0;
205
206        while(yt < dstp->h && validate_pixel_f(dstdata[(x+yt*dstp->w)*4] ,
207                                               dstdata[(x+yt*dstp->w)*4 + 1] ,
208                                               dstdata[(x+yt*dstp->w)*4 + 2] ,
209                                               or, og, ob))
210        {
211            float *cur_line = &dstdata[(yt*dstp->w)*4];
212            int   xp1 = (x+1)*4;
213            int   xm1 = (x-1)*4;
214            cur_line[x*4]     = nr;
215            cur_line[x*4 + 1] = ng;
216            cur_line[x*4 + 2] = nb;
217
218            if(!left && x > 0 && validate_pixel_f(cur_line[xm1],
219                                                  cur_line[xm1 + 1],
220                                                  cur_line[xm1 + 2],
221                                                  or, og, ob))
222            {
223                if(!push(x - 1, yt, dstp->h)) return;
224                left = 1;
225            }
226            else if(left && x > 0 && !validate_pixel_f(cur_line[xm1] ,
227                                                       cur_line[xm1 + 1] ,
228                                                       cur_line[xm1 + 2] ,
229                                                       or, og, ob))
230            {
231                left = 0;
232            }
233            if(!right && x < dstp->w - 1 && validate_pixel_f(cur_line[xp1] ,
234                                                             cur_line[xp1 + 1] ,
235                                                             cur_line[xp1 + 2] ,
236                                                             or, og, ob))
237            {
238                if(!push(x + 1, yt, dstp->h)) return;
239                right = 1;
240            }
241            else if(right && x < dstp->w - 1 && !validate_pixel_f(cur_line[xp1] ,
242                                                                  cur_line[xp1 + 1] ,
243                                                                  cur_line[xp1 + 2],
244                                                                  or, og, ob))
245            {
246                right = 0;
247            }
248            yt++;
249        }
250    }
251}
252
253
254/* Following functions are local  */
255
256static int pop(int *x, int *y, int h)
257{
258    if(stack_pointer > 0)
259    {
260        int p = stack[stack_pointer];
261        *x = p / h;
262        *y = p % h;
263        stack_pointer--;
264        return 1;
265    }
266    else
267    {
268        return 0;
269    }
270}
271
272static int push(int x, int y, int h)
273{
274    if(stack_pointer < STACKSIZE - 1)
275    {
276        stack_pointer++;
277        stack[stack_pointer] = h * x + y;
278        return 1;
279    }
280    else
281    {
282        return 0;
283    }
284}
285
286static void clear_stack(int h)
287{
288    int x, y;
289    while(pop(&x, &y, h));
290}
291
292#define MAX(a, b) (b>a?b:a)
293
294
295/* FIXME : Paves the way to antialiasing, but could be only 3 tests */
296static float get_max_color_diff(float r1, float g1, float b1,
297                                float r2, float g2, float b2)
298{
299    float r = abs(r2-r1);
300    float g = abs(g2-g1);
301    float b = abs(b2-b1);
302
303    return MAX(MAX(r, g), b);
304}
305
306
307static int validate_pixel_f(float r1, float g1, float b1,
308                            float r2, float g2, float b2)
309{
310
311    if(get_max_color_diff(r1, g1, b1,
312                          r2, g2, b2)
313       == 0) return 1;
314    else
315        return 0;
316}
Note: See TracBrowser for help on using the repository browser.