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 | |
---|
33 | static void pipi_flood_fill_stack_scanline_u32(pipi_pixels_t *dstp, |
---|
34 | int x, int y, |
---|
35 | uint32_t new, uint32_t old); |
---|
36 | static 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); |
---|
40 | static int pop (int *x,int *y, int h); |
---|
41 | static int push(int x, int y, int h); |
---|
42 | static void clear_stack(int h); |
---|
43 | static int stack[STACKSIZE]; |
---|
44 | static int stack_pointer; |
---|
45 | |
---|
46 | static float get_max_color_diff(float r1, float g1, float b1, |
---|
47 | float r2, float g2, float b2); |
---|
48 | static 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 */ |
---|
64 | int 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 */ |
---|
124 | void 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) */ |
---|
180 | static 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 | |
---|
259 | static 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 | |
---|
275 | static 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 | |
---|
289 | static 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 */ |
---|
299 | static 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 | |
---|
310 | static 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 | } |
---|