| /* flood-fill |
| * |
| * JC 30/8/97 |
| * - VIPSified, cleaned up, from "John Robinson's prog to fill |
| * enclosed areas" |
| * - something Kirk gave me, so thanks John |
| * JC 1/10/97 |
| * - swapped inner memcmp/cpy for a loop ... faster for small pixels |
| * 13/7/02 JC |
| * - im_flood_blob() added |
| * 5/12/06 |
| * - im_invalidate() after paint |
| * 24/3/09 |
| * - added IM_CODING_RAD support |
| * 28/9/09 |
| * - ooops, tiny memleak |
| * 17/12/09 |
| * - use inline rather than defines, so we can add scanline fills more |
| * easily |
| * - gtk-doc comments |
| * 21/12/09 |
| * - rewrite for a scanline based fill, about 4x faster! |
| * - allow separate test and mark images |
| * 22/1/10 |
| * - flood_blob could loop if start point == ink |
| * 6/3/10 |
| * - don't im_invalidate() after paint, this now needs to be at a higher |
| * level |
| */ |
| |
| /* |
| |
| This file is part of VIPS. |
| |
| VIPS is free software; you can redistribute it and/or modify |
| it under the terms of the GNU Lesser General Public License as published by |
| the Free Software Foundation; either version 2 of the License, or |
| (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU Lesser General Public License for more details. |
| |
| You should have received a copy of the GNU Lesser General Public License |
| along with this program; if not, write to the Free Software |
| Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| |
| */ |
| |
| /* |
| |
| These files are distributed with VIPS - http://www.vips.ecs.soton.ac.uk |
| |
| */ |
| |
| #ifdef HAVE_CONFIG_H |
| #include <config.h> |
| #endif /*HAVE_CONFIG_H*/ |
| #include <vips/intl.h> |
| |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <string.h> |
| |
| #include <vips/vips.h> |
| |
| #ifdef WITH_DMALLOC |
| #include <dmalloc.h> |
| #endif /*WITH_DMALLOC*/ |
| |
| #define SWAP( TYPE, A, B ) { \ |
| TYPE t = (A); \ |
| (A) = (B); \ |
| (B) = t; \ |
| } |
| |
| /* Size of a scanline buffer. We allocate a list of these to hold scanlines |
| * we need to visit. |
| */ |
| #define PBUFSIZE (1000) |
| |
| /* A scanline we know could contain pixels connected to us. |
| * |
| * Dir is the direction of connection: +1 means y is increasing, ie. the line |
| * above this one is filled. -1 if y is decreasing. |
| */ |
| typedef struct { |
| int x1, x2; |
| int y; |
| int dir; |
| } Scan; |
| |
| /* A buffer of scanlines, and how many of them have been used. If ->next is |
| * non-NULL, the next block could contain more of them. |
| * |
| * We keep a pair of these, then loop over one and write to the other. |
| */ |
| typedef struct _Buffer { |
| struct _Buffer *next; |
| int n; |
| Scan scan[PBUFSIZE]; |
| } Buffer; |
| |
| /* Our state. |
| */ |
| typedef struct { |
| /* Parameters. |
| */ |
| IMAGE *test; /* Test this image */ |
| IMAGE *mark; /* Mark this image */ |
| int x, y; |
| PEL *ink; /* Copy of ink param */ |
| Rect *dout; /* Write dirty here at end */ |
| |
| /* Derived stuff. |
| */ |
| PEL *edge; /* Boundary colour */ |
| int equal; /* Fill to == edge, or != edge */ |
| int tsize; /* sizeof( one pel in test ) */ |
| int msize; /* sizeof( one pel in mark ) */ |
| int left, right; /* Record bounding box of modified pixels */ |
| int top, bottom; |
| |
| /* Read from in, add new possibilities to out. |
| */ |
| Buffer *in; |
| Buffer *out; |
| } Flood; |
| |
| /* Alloc a new buffer. |
| */ |
| static Buffer * |
| buffer_build( void ) |
| { |
| Buffer *buf = IM_NEW( NULL, Buffer ); |
| |
| if( !buf ) |
| return( NULL ); |
| buf->next = NULL; |
| buf->n = 0; |
| |
| return( buf ); |
| } |
| |
| /* Free a chain of buffers. |
| */ |
| static void |
| buffer_free( Buffer *buf ) |
| { |
| while( buf ) { |
| Buffer *p; |
| |
| p = buf->next; |
| im_free( buf ); |
| buf = p; |
| } |
| } |
| |
| /* Add a scanline to a buffer, prepending a new buffer if necessary. Return |
| * the new head buffer. |
| */ |
| static inline Buffer * |
| buffer_add( Buffer *buf, Flood *flood, int x1, int x2, int y, int dir ) |
| { |
| /* Clip against image size. |
| */ |
| if( y < 0 || y >= flood->test->Ysize ) |
| return( buf ); |
| x1 = IM_CLIP( 0, x1, flood->test->Xsize - 1 ); |
| x2 = IM_CLIP( 0, x2, flood->test->Xsize - 1 ); |
| if( x2 - x1 < 0 ) |
| return( buf ); |
| |
| buf->scan[buf->n].x1 = x1; |
| buf->scan[buf->n].x2 = x2; |
| buf->scan[buf->n].y = y; |
| buf->scan[buf->n].dir = dir; |
| buf->n += 1; |
| |
| if( buf->n == PBUFSIZE ) { |
| Buffer *new; |
| |
| if( !(new = buffer_build()) ) |
| return( NULL ); |
| new->next = buf; |
| buf = new; |
| } |
| |
| return( buf ); |
| } |
| |
| /* Is p "connected"? ie. is equal to or not equal to flood->edge, depending on |
| * whether we are flooding to the edge boundary or flooding edge-coloured |
| * pixels. |
| */ |
| static inline gboolean |
| flood_connected( Flood *flood, PEL *tp ) |
| { |
| int j; |
| |
| for( j = 0; j < flood->tsize; j++ ) |
| if( tp[j] != flood->edge[j] ) |
| break; |
| |
| /* If flood->equal, true if point == edge. |
| */ |
| return( flood->equal ^ (j < flood->tsize) ); |
| } |
| |
| /* Is p painted? |
| */ |
| static inline gboolean |
| flood_painted( Flood *flood, PEL *mp ) |
| { |
| int j; |
| |
| for( j = 0; j < flood->msize; j++ ) |
| if( mp[j] != flood->ink[j] ) |
| break; |
| |
| return( j == flood->msize ); |
| } |
| |
| /* Faster than memcpy for n < about 20. |
| */ |
| static inline void |
| flood_paint( Flood *flood, PEL *q ) |
| { |
| int j; |
| |
| for( j = 0; j < flood->msize; j++ ) |
| q[j] = flood->ink[j]; |
| } |
| |
| /* Fill left and right, return the endpoints. The start point (x, y) must be |
| * connected and unpainted. |
| */ |
| static void |
| flood_scanline( Flood *flood, int x, int y, int *x1, int *x2 ) |
| { |
| const int width = flood->mark->Xsize; |
| |
| PEL *tp; |
| PEL *mp; |
| int i; |
| int len; |
| |
| /* |
| g_assert( flood_connected( flood, |
| (PEL *) IM_IMAGE_ADDR( flood->test, x, y ) ) ); |
| g_assert( !flood_painted( flood, |
| (PEL *) IM_IMAGE_ADDR( flood->mark, x, y ) ) ); |
| */ |
| |
| /* Search to the right for the first non-connected pixel. If the start |
| * pixel is unpainted, we know all the intervening pixels must be |
| * unpainted too. |
| */ |
| tp = (PEL *) IM_IMAGE_ADDR( flood->test, x + 1, y ); |
| for( i = x + 1; i < width; i++ ) { |
| if( !flood_connected( flood, tp ) ) |
| break; |
| tp += flood->tsize; |
| } |
| *x2 = i - 1; |
| |
| /* Search left. |
| */ |
| tp = (PEL *) IM_IMAGE_ADDR( flood->test, x - 1, y ); |
| for( i = x - 1; i >= 0; i-- ) { |
| if( !flood_connected( flood, tp ) ) |
| break; |
| tp -= flood->tsize; |
| } |
| *x1 = i + 1; |
| |
| /* Paint the range we discovered. |
| */ |
| mp = (PEL *) IM_IMAGE_ADDR( flood->mark, *x1, y ); |
| len = *x2 - *x1 + 1; |
| for( i = 0; i < len; i++ ) { |
| flood_paint( flood, mp ); |
| mp += flood->msize; |
| } |
| |
| if( flood->dout ) { |
| flood->left = IM_MIN( flood->left, *x1 ); |
| flood->right = IM_MAX( flood->right, *x2 ); |
| flood->top = IM_MIN( flood->top, y ); |
| flood->bottom = IM_MAX( flood->bottom, y ); |
| } |
| } |
| |
| /* We know the line below or above us is filled between x1 and x2. Search our |
| * line in this range looking for an edge pixel we can flood from. |
| */ |
| static void |
| flood_around( Flood *flood, Scan *scan ) |
| { |
| PEL *tp; |
| int x; |
| |
| g_assert( scan->dir == 1 || scan->dir == -1 ); |
| |
| for( tp = (PEL *) IM_IMAGE_ADDR( flood->test, scan->x1, scan->y ), |
| x = scan->x1; |
| x <= scan->x2; |
| tp += flood->tsize, x++ ) { |
| if( flood_connected( flood, tp ) ) { |
| int x1a; |
| int x2a; |
| |
| /* If mark and test are different images, we also need |
| * to check for painted. Otherwise we can get stuck in |
| * connected loops. |
| */ |
| if( flood->mark != flood->test ) { |
| PEL *mp = (PEL *) IM_IMAGE_ADDR( |
| flood->mark, x, scan->y ); |
| |
| if( flood_painted( flood, mp ) ) |
| continue; |
| } |
| |
| flood_scanline( flood, x, scan->y, &x1a, &x2a ); |
| |
| /* Our new scanline can have up to three more |
| * scanlines connected to it: above, below left, below |
| * right. |
| */ |
| if( x1a < scan->x1 - 1 ) |
| flood->out = buffer_add( flood->out, flood, |
| x1a, scan->x1 - 2, |
| scan->y - scan->dir, -scan->dir ); |
| if( x2a > scan->x2 + 1 ) |
| flood->out = buffer_add( flood->out, flood, |
| scan->x2 + 2, x2a, |
| scan->y - scan->dir, -scan->dir ); |
| flood->out = buffer_add( flood->out, flood, |
| x1a, x2a, scan->y + scan->dir, |
| scan->dir ); |
| |
| x = x2a + 1; |
| tp = (PEL *) IM_IMAGE_ADDR( flood->test, x, scan->y ); |
| } |
| } |
| } |
| |
| static void |
| flood_all( Flood *flood, int x, int y ) |
| { |
| int x1, x2; |
| |
| /* Test start pixel ... nothing to do? |
| */ |
| if( !flood_connected( flood, |
| (PEL *) IM_IMAGE_ADDR( flood->test, x, y ) ) ) |
| return; |
| |
| flood_scanline( flood, x, y, &x1, &x2 ); |
| flood->in = buffer_add( flood->in, flood, x1, x2, y + 1, 1 ); |
| flood->in = buffer_add( flood->in, flood, x1, x2, y - 1, -1 ); |
| |
| while( flood->in->n ) { |
| Buffer *p; |
| |
| for( p = flood->in; p; p = p->next ) { |
| int i; |
| |
| for( i = 0; i < p->n; i++ ) |
| flood_around( flood, &p->scan[i] ); |
| |
| p->n = 0; |
| } |
| |
| SWAP( Buffer *, flood->in, flood->out ); |
| } |
| } |
| |
| static void |
| flood_free( Flood *flood ) |
| { |
| /* Write dirty back to caller. |
| */ |
| if( flood->dout ) { |
| flood->dout->left = flood->left; |
| flood->dout->top = flood->top; |
| flood->dout->width = flood->right - flood->left + 1; |
| flood->dout->height = flood->bottom - flood->top + 1; |
| } |
| |
| IM_FREE( flood->ink ); |
| IM_FREE( flood->edge ); |
| IM_FREEF( buffer_free, flood->in ); |
| IM_FREEF( buffer_free, flood->out ); |
| im_free( flood ); |
| } |
| |
| static Flood * |
| flood_build( IMAGE *test, IMAGE *mark, int x, int y, PEL *ink, Rect *dout ) |
| { |
| Flood *flood = IM_NEW( NULL, Flood ); |
| |
| if( !flood ) |
| return( NULL ); |
| flood->test = test; |
| flood->mark = mark; |
| flood->x = x; |
| flood->y = y; |
| flood->ink = NULL; |
| flood->dout = dout; |
| flood->edge = NULL; |
| flood->tsize = IM_IMAGE_SIZEOF_PEL( test ); |
| flood->msize = IM_IMAGE_SIZEOF_PEL( mark ); |
| flood->left = x; |
| flood->top = y; |
| flood->right = x; |
| flood->bottom = y; |
| |
| flood->in = NULL; |
| flood->out = NULL; |
| |
| if( !(flood->ink = (PEL *) im_malloc( NULL, flood->msize )) || |
| !(flood->edge = (PEL *) im_malloc( NULL, flood->tsize )) || |
| !(flood->in = buffer_build()) || |
| !(flood->out = buffer_build()) ) { |
| flood_free( flood ); |
| return( NULL ); |
| } |
| memcpy( flood->ink, ink, flood->msize ); |
| |
| return( flood ); |
| } |
| |
| /** |
| * im_flood: |
| * @im: image to fill |
| * @x: position to start fill |
| * @y: position to start fill |
| * @ink: colour to fill with |
| * @dout: output the bounding box of the filled area |
| * |
| * Flood-fill @im with @ink, starting at position @x, @y. The filled area is |
| * bounded by pixels that are equal to the ink colour, in other words, it |
| * searches for pixels enclosed by a line of @ink. |
| * |
| * The bounding box of the modified pixels is returned in @dout. |
| * |
| * This an inplace operation, so @im is changed. It does not thread and will |
| * not work well as part of a pipeline. On 32-bit machines, it will be limited |
| * to 2GB images. |
| * |
| * See also: im_flood_blob(), im_flood_other(), im_flood_blob_copy(). |
| * |
| * Returns: 0 on success, or -1 on error. |
| */ |
| int |
| im_flood( IMAGE *im, int x, int y, PEL *ink, Rect *dout ) |
| { |
| Flood *flood; |
| |
| if( im_rwcheck( im ) || |
| im_check_coding_known( "im_flood", im ) ) |
| return( -1 ); |
| if( !(flood = flood_build( im, im, x, y, ink, dout )) ) |
| return( -1 ); |
| |
| /* Flood to != ink. |
| */ |
| memcpy( flood->edge, ink, flood->tsize ); |
| flood->equal = 0; |
| |
| flood_all( flood, x, y ); |
| |
| flood_free( flood ); |
| |
| return( 0 ); |
| } |
| |
| /** |
| * im_flood_blob: |
| * @im: image to fill |
| * @x: position to start fill |
| * @y: position to start fill |
| * @ink: colour to fill with |
| * @dout: output the bounding box of the filled area |
| * |
| * Flood-fill @im with @ink, starting at position @x, @y. The filled area is |
| * bounded by pixels that are equal to the start pixel, in other words, it |
| * searches for a blob of same-coloured pixels. |
| * |
| * The bounding box of the modified pixels is returned in @dout. |
| * |
| * This an inplace operation, so @im is changed. It does not thread and will |
| * not work well as part of a pipeline. On 32-bit machines, it will be limited |
| * to 2GB images. |
| * |
| * See also: im_flood(), im_flood_other(), im_flood_blob_copy(). |
| * |
| * Returns: 0 on success, or -1 on error. |
| */ |
| int |
| im_flood_blob( IMAGE *im, int x, int y, PEL *ink, Rect *dout ) |
| { |
| Flood *flood; |
| int j; |
| |
| if( im_rwcheck( im ) || |
| im_check_coding_known( "im_flood", im ) ) |
| return( -1 ); |
| if( !(flood = flood_build( im, im, x, y, ink, dout )) ) |
| return( -1 ); |
| |
| /* Edge is set by colour of start pixel. |
| */ |
| memcpy( flood->edge, IM_IMAGE_ADDR( im, x, y ), flood->tsize ); |
| flood->equal = 1; |
| |
| /* If edge == ink, we'll never stop :-( or rather, there's nothing to |
| * do. |
| */ |
| for( j = 0; j < flood->tsize; j++ ) |
| if( flood->edge[j] != flood->ink[j] ) |
| break; |
| if( j == flood->tsize ) |
| return( 0 ); |
| |
| flood_all( flood, x, y ); |
| |
| flood_free( flood ); |
| |
| return( 0 ); |
| } |
| |
| /** |
| * im_flood_other: |
| * @test: image to test |
| * @mark: image to mark |
| * @x: position to start fill |
| * @y: position to start fill |
| * @serial: mark pixels with this number |
| * @dout: output the bounding box of the filled area |
| * |
| * Flood-fill @mark with @serial, starting at position @x, @y. The filled |
| * area is bounded by pixels in @test that are equal to the start pixel, in |
| * other words, it searches @test for a blob of same-coloured pixels, marking |
| * those pixels in @mark with @serial. |
| * |
| * The bounding box of the modified pixels is returned in @dout. |
| * |
| * This an inplace operation, so @mark is changed. It does not thread and will |
| * not work well as part of a pipeline. On 32-bit machines, it will be limited |
| * to 2GB images. |
| * |
| * See also: im_flood(), im_label_regions(), im_flood_blob_copy(). |
| * |
| * Returns: 0 on success, or -1 on error. |
| */ |
| int |
| im_flood_other( IMAGE *test, IMAGE *mark, int x, int y, int serial, Rect *dout ) |
| { |
| int *m; |
| Flood *flood; |
| |
| if( im_incheck( test ) || |
| im_rwcheck( mark ) || |
| im_check_coding_known( "im_flood_other", test ) || |
| im_check_uncoded( "im_flood_other", mark ) || |
| im_check_mono( "im_flood_other", mark ) || |
| im_check_format( "im_flood_other", mark, IM_BANDFMT_INT ) || |
| im_check_size_same( "im_flood_other", test, mark ) ) |
| return( -1 ); |
| |
| /* Have we done this point already? |
| */ |
| m = (int *) IM_IMAGE_ADDR( mark, x, y ); |
| if( *m == serial ) |
| return( 0 ); |
| |
| if( !(flood = flood_build( test, mark, x, y, (PEL *) &serial, dout )) ) |
| return( -1 ); |
| |
| /* Edge is set by colour of start pixel. |
| */ |
| memcpy( flood->edge, IM_IMAGE_ADDR( test, x, y ), flood->tsize ); |
| flood->equal = 1; |
| |
| flood_all( flood, x, y ); |
| |
| flood_free( flood ); |
| |
| return( 0 ); |
| } |
| |
| /* A flood blob we can call from nip. Grr! Should be a way to wrap these |
| * automatically. Maybe nip could do it if it sees a RW image argument? |
| */ |
| |
| int |
| im_flood_copy( IMAGE *in, IMAGE *out, int x, int y, PEL *ink ) |
| { |
| IMAGE *t; |
| |
| if( !(t = im_open_local( out, "im_flood_blob_copy", "t" )) || |
| im_copy( in, t ) || |
| im_flood( t, x, y, ink, NULL ) || |
| im_copy( t, out ) ) |
| return( -1 ); |
| |
| return( 0 ); |
| } |
| |
| int |
| im_flood_blob_copy( IMAGE *in, IMAGE *out, int x, int y, PEL *ink ) |
| { |
| IMAGE *t; |
| |
| if( !(t = im_open_local( out, "im_flood_blob_copy", "t" )) || |
| im_copy( in, t ) || |
| im_flood_blob( t, x, y, ink, NULL ) || |
| im_copy( t, out ) ) |
| return( -1 ); |
| |
| return( 0 ); |
| } |
| |
| int |
| im_flood_other_copy( IMAGE *test, IMAGE *mark, IMAGE *out, |
| int x, int y, int serial ) |
| { |
| IMAGE *t; |
| |
| if( !(t = im_open_local( out, "im_flood_other_copy", "t" )) || |
| im_copy( mark, t ) || |
| im_flood_other( test, t, x, y, serial, NULL ) || |
| im_copy( t, out ) ) |
| return( -1 ); |
| |
| return( 0 ); |
| } |
| |