ReactOS 0.4.16-dev-340-g0540c21
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 */
24typedef struct _floodItem
25{
29
30typedef struct _floodInfo
31{
36
37static __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}
51{
52 ExFreePoolWithTag(info->floodData, TAG_DIB);
53}
55 ULONG x,
56 ULONG y,
57 SURFOBJ *DstSurf,
58 RECTL *DstRect,
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
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}
unsigned char BOOLEAN
#define DPRINT1
Definition: precomp.h:8
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define NonPagedPool
Definition: env_spec_w32.h:307
unsigned int BOOL
Definition: ntddk_ex.h:94
static __inline VOID removeItemFlood(FLOODINFO *info)
Definition: floodfill.c:80
static __inline VOID addItemFlood(FLOODINFO *info, ULONG x, ULONG y, SURFOBJ *DstSurf, RECTL *DstRect, ULONG Color, BOOL isSurf)
Definition: floodfill.c:54
static __inline VOID finalizeFlood(FLOODINFO *info)
Definition: floodfill.c:50
struct _floodInfo FLOODINFO
static __inline BOOL initFlood(FLOODINFO *info, RECTL *DstRect)
Definition: floodfill.c:37
struct _floodItem FLOODITEM
BOOLEAN DIB_XXBPP_FloodFillSolid(SURFOBJ *DstSurf, BRUSHOBJ *Brush, RECTL *DstRect, POINTL *Origin, ULONG ConvColor, UINT FillType)
Definition: floodfill.c:86
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLint GLint GLsizei GLsizei height
Definition: gl.h:1546
GLint GLint GLsizei width
Definition: gl.h:1546
#define ExFreePoolWithTag(_P, _T)
Definition: module.h:1109
unsigned int UINT
Definition: ndis.h:50
#define DPRINT
Definition: sndvol32.h:73
PFN_DIB_PutPixel DIB_PutPixel
Definition: dib.h:45
PFN_DIB_GetPixel DIB_GetPixel
Definition: dib.h:46
long bottom
Definition: polytest.cpp:53
long right
Definition: polytest.cpp:53
long top
Definition: polytest.cpp:53
long left
Definition: polytest.cpp:53
LONG y
Definition: windef.h:330
LONG x
Definition: windef.h:329
ULONG iBitmapFormat
Definition: winddi.h:1215
FLOODITEM * floodData
Definition: floodfill.c:34
ULONG floodLen
Definition: floodfill.c:32
FLOODITEM * floodStart
Definition: floodfill.c:33
ULONG x
Definition: floodfill.c:26
ULONG y
Definition: floodfill.c:27
uint32_t ULONG
Definition: typedefs.h:59
DIB_FUNCTIONS DibFunctionsForBitmapFormat[]
Definition: dib.c:20
FORCEINLINE BOOL RECTL_bPointInRect(_In_ const RECTL *prcl, _In_ INT x, _In_ INT y)
Definition: rect.h:52
#define TAG_DIB
Definition: tags.h:17
#define FLOODFILLBORDER
Definition: wingdi.h:644
#define FLOODFILLSURFACE
Definition: wingdi.h:645