1/////////////////////////////////////////////////////////////////////////////
2// Name:        src/common/imagfill.cpp
3// Purpose:     FloodFill for wxImage
4// Author:      Julian Smart
5// RCS-ID:      $Id: imagfill.cpp 63770 2010-03-28 22:34:12Z VZ $
6// Copyright:   (c) Julian Smart
7// Licence:     wxWindows licence
8/////////////////////////////////////////////////////////////////////////////
9
10
11// For compilers that support precompilation, includes "wx.h".
12#include "wx/wxprec.h"
13
14#ifdef __BORLANDC__
15    #pragma hdrstop
16#endif
17
18#if wxUSE_IMAGE && !defined(__WXMSW__)
19// we have no use for this code in wxMSW...
20
21#ifndef WX_PRECOMP
22    #include "wx/brush.h"
23    #include "wx/dc.h"
24    #include "wx/dcmemory.h"
25    #include "wx/image.h"
26#endif
27
28// DoFloodFill
29// Fills with the colour extracted from fillBrush, starting at x,y until either
30// a color different from the start pixel is reached (wxFLOOD_SURFACE)
31// or fill color is reached (wxFLOOD_BORDER)
32
33static bool LINKAGEMODE MatchPixel(wxImage *img, int x, int y, int w, int h, const wxColour& c)
34{
35    if ((x<0)||(x>=w)||(y<0)||(y>=h)) return false;
36
37    unsigned char r = img->GetRed(x,y);
38    unsigned char g = img->GetGreen(x,y);
39    unsigned char b = img->GetBlue(x,y);
40    return c.Red() == r && c.Green() == g && c.Blue() == b ;
41}
42
43static bool LINKAGEMODE MatchBoundaryPixel(wxImage *img, int x, int y, int w, int h, const wxColour & fill, const wxColour& bound)
44{
45    if ((x<0)||(x>=w)||(y<0)||(y>=h)) return true;
46
47    unsigned char r = img->GetRed(x,y);
48    unsigned char g = img->GetGreen(x,y);
49    unsigned char b = img->GetBlue(x,y);
50    if ( fill.Red() == r && fill.Green() == g && fill.Blue() == b )
51        return true;
52    if ( bound.Red() == r && bound.Green() == g && bound.Blue() == b )
53        return true;
54    return false;
55}
56
57
58static void LINKAGEMODE
59wxImageFloodFill(wxImage *image,
60                 wxCoord x, wxCoord y, const wxBrush & fillBrush,
61                 const wxColour& testColour, int style,
62                 int WXUNUSED(LogicalFunction))
63{
64    /* A diamond flood-fill using a circular queue system.
65    Each pixel surrounding the current pixel is added to
66    the queue if it meets the criteria, then is retrieved in
67    its turn.  Code originally based on http://www.drawit.co.nz/Developers.htm,
68    with explicit permission to use this for wxWidgets granted by Andrew Empson
69    (no copyright claimed)
70     */
71
72    int width = image->GetWidth();
73    int height = image->GetHeight();
74
75    //Draw using a pen made from the current brush colour
76    //Potentially allows us to use patterned flood fills in future code
77    wxColour fillColour = fillBrush.GetColour();
78    unsigned char r = fillColour.Red();
79    unsigned char g = fillColour.Green();
80    unsigned char b = fillColour.Blue();
81
82    //initial test :
83    if (style == wxFLOOD_SURFACE)
84    {
85       //if wxFLOOD_SURFACE, if fill colour is same as required, we don't do anything
86       if (     image->GetRed(x,y)   != r
87             || image->GetGreen(x,y) != g
88             || image->GetBlue (x,y) != b   )
89        {
90        //prepare memory for queue
91        //queue save, start, read
92        size_t *qs, *qst, *qr;
93
94        //queue size (physical)
95        long qSz= height * width * 2;
96        qst = new size_t [qSz];
97
98        //temporary x and y locations
99        int xt, yt;
100
101        for (int i=0; i < qSz; i++)
102            qst[i] = 0;
103
104        // start queue
105        qs=qr=qst;
106        *qs=xt=x;
107        qs++;
108        *qs=yt=y;
109        qs++;
110
111        image->SetRGB(xt,yt,r,g,b);
112
113        //Main queue loop
114        while(qr!=qs)
115        {
116            //Add new members to queue
117            //Above current pixel
118            if(MatchPixel(image,xt,yt-1,width,height,testColour))
119            {
120                *qs=xt;
121                qs++;
122                *qs=yt-1;
123                qs++;
124                image->SetRGB(xt,yt-1,r,g,b);
125
126                //Loop back to beginning of queue
127                if(qs>=(qst+qSz)) qs=qst;
128            }
129
130            //Below current pixel
131            if(MatchPixel(image,xt,yt+1,width,height,testColour))
132            {
133                *qs=xt;
134                qs++;
135                *qs=yt+1;
136                qs++;
137                image->SetRGB(xt,yt+1,r,g,b);
138                if(qs>=(qst+qSz)) qs=qst;
139            }
140
141            //Left of current pixel
142            if(MatchPixel(image,xt-1,yt,width,height,testColour))
143            {
144                *qs=xt-1;
145                qs++;
146                *qs=yt;
147                qs++;
148                image->SetRGB(xt-1,yt,r,g,b);
149                if(qs>=(qst+qSz)) qs=qst;
150            }
151
152            //Right of current pixel
153            if(MatchPixel(image,xt+1,yt,width,height,testColour))
154            {
155                *qs=xt+1;
156                qs++;
157                *qs=yt;
158                qs++;
159                image->SetRGB(xt+1,yt,r,g,b);
160                if(qs>=(qst+qSz)) qs=qst;
161            }
162
163            //Retrieve current queue member
164            qr+=2;
165
166            //Loop back to the beginning
167            if(qr>=(qst+qSz)) qr=qst;
168            xt=*qr;
169            yt=*(qr+1);
170
171        //Go Back to beginning of loop
172        }
173
174        delete[] qst;
175        }
176    }
177    else
178    {
179    //style is wxFLOOD_BORDER
180    // fill up to testColor border - if already testColour don't do anything
181    if (  image->GetRed(x,y)   != testColour.Red()
182          || image->GetGreen(x,y) != testColour.Green()
183          || image->GetBlue(x,y)  != testColour.Blue() )
184    {
185        //prepare memory for queue
186        //queue save, start, read
187        size_t *qs, *qst, *qr;
188
189        //queue size (physical)
190        long qSz= height * width * 2;
191        qst = new size_t [qSz];
192
193        //temporary x and y locations
194        int xt, yt;
195
196        for (int i=0; i < qSz; i++)
197            qst[i] = 0;
198
199        // start queue
200        qs=qr=qst;
201        *qs=xt=x;
202        qs++;
203        *qs=yt=y;
204        qs++;
205
206        image->SetRGB(xt,yt,r,g,b);
207
208        //Main queue loop
209        while (qr!=qs)
210        {
211            //Add new members to queue
212            //Above current pixel
213            if(!MatchBoundaryPixel(image,xt,yt-1,width,height,fillColour,testColour))
214            {
215                *qs=xt;
216                qs++;
217                *qs=yt-1;
218                qs++;
219                image->SetRGB(xt,yt-1,r,g,b);
220
221                //Loop back to beginning of queue
222                if(qs>=(qst+qSz)) qs=qst;
223            }
224
225            //Below current pixel
226            if(!MatchBoundaryPixel(image,xt,yt+1,width,height,fillColour,testColour))
227            {
228                *qs=xt;
229                qs++;
230                *qs=yt+1;
231                qs++;
232                image->SetRGB(xt,yt+1,r,g,b);
233                if(qs>=(qst+qSz)) qs=qst;
234            }
235
236            //Left of current pixel
237            if(!MatchBoundaryPixel(image,xt-1,yt,width,height,fillColour,testColour))
238            {
239                *qs=xt-1;
240                qs++;
241                *qs=yt;
242                qs++;
243                image->SetRGB(xt-1,yt,r,g,b);
244                if(qs>=(qst+qSz)) qs=qst;
245            }
246
247            //Right of current pixel
248            if(!MatchBoundaryPixel(image,xt+1,yt,width,height,fillColour,testColour))
249            {
250                *qs=xt+1;
251                qs++;
252                *qs=yt;
253                qs++;
254                image->SetRGB(xt+1,yt,r,g,b);
255                if(qs>=(qst+qSz)) qs=qst;
256            }
257
258            //Retrieve current queue member
259            qr+=2;
260
261            //Loop back to the beginning
262            if(qr>=(qst+qSz)) qr=qst;
263            xt=*qr;
264            yt=*(qr+1);
265
266        //Go Back to beginning of loop
267        }
268
269        delete[] qst;
270        }
271    }
272    //all done,
273}
274
275
276bool wxDoFloodFill(wxDC *dc, wxCoord x, wxCoord y,
277                   const wxColour& col, int style)
278{
279    if (dc->GetBrush().GetStyle() == wxTRANSPARENT)
280        return true;
281
282    int height = 0;
283    int width  = 0;
284    dc->GetSize(&width, &height);
285
286    //it would be nice to fail if we don't get a sensible size...
287    wxCHECK_MSG(width >= 1 && height >= 1, false,
288                wxT("In FloodFill, dc.GetSize routine failed, method not supported by this DC"));
289
290    const int x_dev = dc->LogicalToDeviceX(x);
291    const int y_dev = dc->LogicalToDeviceY(y);
292
293    // if start point is outside dc, can't do anything
294    if (!wxRect(0, 0, width, height).Contains(x_dev, y_dev))
295        return false;
296
297    wxBitmap bitmap(width, height);
298    wxMemoryDC memdc(bitmap);
299    // match dc scales
300    double sx, sy;
301    dc->GetUserScale(&sx, &sy);
302    memdc.SetUserScale(sx, sy);
303    dc->GetLogicalScale(&sx, &sy);
304    memdc.SetLogicalScale(sx, sy);
305
306    // get logical size and origin
307    const int w_log = dc->DeviceToLogicalXRel(width);
308    const int h_log = dc->DeviceToLogicalYRel(height);
309    const int x0_log = dc->DeviceToLogicalX(0);
310    const int y0_log = dc->DeviceToLogicalY(0);
311
312    memdc.Blit(0, 0, w_log, h_log, dc, x0_log, y0_log);
313    memdc.SelectObject(wxNullBitmap);
314
315    wxImage image = bitmap.ConvertToImage();
316    wxImageFloodFill(&image, x_dev, y_dev, dc->GetBrush(), col, style,
317                     dc->GetLogicalFunction());
318    bitmap = wxBitmap(image);
319    memdc.SelectObject(bitmap);
320    dc->Blit(x0_log, y0_log, w_log, h_log, &memdc, 0, 0);
321
322    return true;
323}
324
325#endif // wxUSE_IMAGE
326