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

Last change on this file since 2902 was 2902, checked in by Sam Hocevar, 11 years ago

Support C99 types on Win32 through the same hacks as in libcaca.

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