ReactOS  0.4.14-dev-297-g23e575c
floodfill.c
Go to the documentation of this file.
1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS win32 subsystem
4 * PURPOSE: Flood filling support
5 * FILE: win32ss/gdi/dib/floodfill.c
6 * PROGRAMMER: Gregor Schneider, <grschneider AT gmail DOT com>
7 */
8 
9 #include <win32k.h>
10 
11 #define NDEBUG
12 #include <debug.h>
13 
14 /*
15 * This floodfill algorithm is an iterative four neighbors version. It works with an internal stack like data structure.
16 * The stack is kept in an array, sized for the worst case scenario of having to add all pixels of the surface.
17 * This avoids having to allocate and free memory blocks all the time. The stack grows from the end of the array towards the start.
18 * All pixels are checked before being added, against belonging to the fill rule (FLOODFILLBORDER or FLOODFILLSURFACE)
19 * and the position in respect to the clip region. This guarantees all pixels lying on the stack belong to the filled surface.
20 * Further optimisations of the algorithm are possible.
21 */
22 
23 /* Floodfil helper structures and functions */
24 typedef struct _floodItem
25 {
28 } FLOODITEM;
29 
30 typedef struct _floodInfo
31 {
35 } FLOODINFO;
36 
37 static __inline BOOL initFlood(FLOODINFO *info, RECTL *DstRect)
38 {
39  ULONG width = DstRect->right - DstRect->left;
40  ULONG height = DstRect->bottom - DstRect->top;
42  if (info->floodData == NULL)
43  {
44  return FALSE;
45  }
46  info->floodStart = info->floodData + (width * height);
47  DPRINT("Allocated flood stack from %p to %p\n", info->floodData, info->floodStart);
48  return TRUE;
49 }
50 static __inline VOID finalizeFlood(FLOODINFO *info)
51 {
52  ExFreePoolWithTag(info->floodData, TAG_DIB);
53 }
54 static __inline VOID addItemFlood(FLOODINFO *info,
55  ULONG x,
56  ULONG y,
57  SURFOBJ *DstSurf,
58  RECTL *DstRect,
59  ULONG Color,
60  BOOL isSurf)
61 {
62  if (RECTL_bPointInRect(DstRect,x,y))
63  {
64  if (isSurf &&
66  {
67  return;
68  }
69  else if (isSurf == FALSE &&
71  {
72  return;
73  }
74  info->floodStart--;
75  info->floodStart->x = x;
76  info->floodStart->y = y;
77  info->floodLen++;
78  }
79 }
81 {
82  info->floodStart++;
83  info->floodLen--;
84 }
85 
87  BRUSHOBJ *Brush,
88  RECTL *DstRect,
89  POINTL *Origin,
90  ULONG ConvColor,
91  UINT FillType)
92 {
93  ULONG x, y;
94  ULONG BrushColor;
95  FLOODINFO flood = {0, NULL, NULL};
96 
97  BrushColor = Brush->iSolidColor;
98  x = Origin->x;
99  y = Origin->y;
100 
101  if (FillType == FLOODFILLBORDER)
102  {
103  /* Check if the start pixel has the border color */
104  if (DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) == ConvColor)
105  {
106  return FALSE;
107  }
108 
109  if (initFlood(&flood, DstRect) == FALSE)
110  {
111  return FALSE;
112  }
113  addItemFlood(&flood, x, y, DstSurf, DstRect, ConvColor, FALSE);
114  while (flood.floodLen != 0)
115  {
116  x = flood.floodStart->x;
117  y = flood.floodStart->y;
118  removeItemFlood(&flood);
119 
120  DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_PutPixel(DstSurf, x, y, BrushColor);
121  if (flood.floodStart - 4 < flood.floodData)
122  {
123  DPRINT1("Can't finish flooding!\n");
124  finalizeFlood(&flood);
125  return FALSE;
126  }
127  addItemFlood(&flood, x, y + 1, DstSurf, DstRect, ConvColor, FALSE);
128  addItemFlood(&flood, x, y - 1, DstSurf, DstRect, ConvColor, FALSE);
129  addItemFlood(&flood, x + 1, y, DstSurf, DstRect, ConvColor, FALSE);
130  addItemFlood(&flood, x - 1, y, DstSurf, DstRect, ConvColor, FALSE);
131  }
132  finalizeFlood(&flood);
133  }
134  else if (FillType == FLOODFILLSURFACE)
135  {
136  /* Check if the start pixel has the surface color */
137  if (DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) != ConvColor)
138  {
139  return FALSE;
140  }
141 
142  if (initFlood(&flood, DstRect) == FALSE)
143  {
144  return FALSE;
145  }
146  addItemFlood(&flood, x, y, DstSurf, DstRect, ConvColor, TRUE);
147  while (flood.floodLen != 0)
148  {
149  x = flood.floodStart->x;
150  y = flood.floodStart->y;
151  removeItemFlood(&flood);
152 
153  DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_PutPixel(DstSurf, x, y, BrushColor);
154  if (flood.floodStart - 4 < flood.floodData)
155  {
156  DPRINT1("Can't finish flooding!\n");
157  finalizeFlood(&flood);
158  return FALSE;
159  }
160  addItemFlood(&flood, x, y + 1, DstSurf, DstRect, ConvColor, TRUE);
161  addItemFlood(&flood, x, y - 1, DstSurf, DstRect, ConvColor, TRUE);
162  addItemFlood(&flood, x + 1, y, DstSurf, DstRect, ConvColor, TRUE);
163  addItemFlood(&flood, x - 1, y, DstSurf, DstRect, ConvColor, TRUE);
164  }
165  finalizeFlood(&flood);
166  }
167  else
168  {
169  DPRINT1("Unsupported FloodFill type!\n");
170  return FALSE;
171  }
172  return TRUE;
173 }
GLint GLint GLsizei width
Definition: gl.h:1546
static __inline VOID removeItemFlood(FLOODINFO *info)
Definition: floodfill.c:80
#define TRUE
Definition: types.h:120
struct _floodItem FLOODITEM
static __inline VOID addItemFlood(FLOODINFO *info, ULONG x, ULONG y, SURFOBJ *DstSurf, RECTL *DstRect, ULONG Color, BOOL isSurf)
Definition: floodfill.c:54
long bottom
Definition: polytest.cpp:53
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
ULONG iBitmapFormat
Definition: winddi.h:1215
ULONG y
Definition: floodfill.c:27
struct Color Color
LONG y
Definition: windef.h:315
long right
Definition: polytest.cpp:53
unsigned int BOOL
Definition: ntddk_ex.h:94
long top
Definition: polytest.cpp:53
PFN_DIB_PutPixel DIB_PutPixel
Definition: dib.h:45
unsigned char BOOLEAN
smooth NULL
Definition: ftsmooth.c:416
void DPRINT(...)
Definition: polytest.cpp:61
long left
Definition: polytest.cpp:53
#define FLOODFILLSURFACE
Definition: wingdi.h:644
LONG x
Definition: windef.h:314
static __inline VOID finalizeFlood(FLOODINFO *info)
Definition: floodfill.c:50
BOOLEAN DIB_XXBPP_FloodFillSolid(SURFOBJ *DstSurf, BRUSHOBJ *Brush, RECTL *DstRect, POINTL *Origin, ULONG ConvColor, UINT FillType)
Definition: floodfill.c:86
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
PFN_DIB_GetPixel DIB_GetPixel
Definition: dib.h:46
FORCEINLINE BOOL RECTL_bPointInRect(_In_ const RECTL *prcl, _In_ INT x, _In_ INT y)
Definition: rect.h:52
GLint GLint GLsizei GLsizei height
Definition: gl.h:1546
FLOODITEM * floodData
Definition: floodfill.c:34
DIB_FUNCTIONS DibFunctionsForBitmapFormat[]
Definition: dib.c:20
struct _floodInfo FLOODINFO
unsigned int UINT
Definition: ndis.h:50
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
ULONG floodLen
Definition: floodfill.c:32
#define DPRINT1
Definition: precomp.h:8
unsigned int ULONG
Definition: retypes.h:1
static __inline BOOL initFlood(FLOODINFO *info, RECTL *DstRect)
Definition: floodfill.c:37
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1099
FLOODITEM * floodStart
Definition: floodfill.c:33
#define FLOODFILLBORDER
Definition: wingdi.h:643
ULONG x
Definition: floodfill.c:26
#define TAG_DIB
Definition: tags.h:17