2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS win32 subsystem
4 * PURPOSE: Flood filling support
5 * FILE: subsystems/win32/win32k/dib/floodfill.c
6 * PROGRAMMER: Gregor Schneider, <grschneider AT gmail DOT com>
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.
23 /* Floodfil helper structures and functions */
24 typedef struct _floodItem
30 typedef struct _floodInfo
33 FLOODITEM
*floodStart
;
37 static __inline BOOL
initFlood(FLOODINFO
*info
, RECTL
*DstRect
)
39 ULONG width
= DstRect
->right
- DstRect
->left
;
40 ULONG height
= DstRect
->bottom
- DstRect
->top
;
41 info
->floodData
= ExAllocatePoolWithTag(NonPagedPool
, width
* height
* sizeof(FLOODITEM
), TAG_DIB
);
42 if (info
->floodData
== NULL
)
46 info
->floodStart
= info
->floodData
+ (width
* height
);
47 DPRINT("Allocated flood stack from %p to %p\n", info
->floodData
, info
->floodStart
);
50 static __inline VOID
finalizeFlood(FLOODINFO
*info
)
52 ExFreePoolWithTag(info
->floodData
, TAG_DIB
);
54 static __inline VOID
addItemFlood(FLOODINFO
*info
,
62 if (RECTL_bPointInRect(DstRect
,x
,y
))
65 DibFunctionsForBitmapFormat
[DstSurf
->iBitmapFormat
].DIB_GetPixel(DstSurf
, x
, y
) != Color
)
69 else if (isSurf
== FALSE
&&
70 DibFunctionsForBitmapFormat
[DstSurf
->iBitmapFormat
].DIB_GetPixel(DstSurf
, x
, y
) == Color
)
75 info
->floodStart
->x
= x
;
76 info
->floodStart
->y
= y
;
80 static __inline VOID
removeItemFlood(FLOODINFO
*info
)
86 BOOLEAN
DIB_XXBPP_FloodFillSolid(SURFOBJ
*DstSurf
,
95 FLOODINFO flood
= {0, NULL
, NULL
};
97 BrushColor
= Brush
->iSolidColor
;
101 if (FillType
== FLOODFILLBORDER
)
103 /* Check if the start pixel has the border color */
104 if (DibFunctionsForBitmapFormat
[DstSurf
->iBitmapFormat
].DIB_GetPixel(DstSurf
, x
, y
) == ConvColor
)
109 if (initFlood(&flood
, DstRect
) == FALSE
)
113 addItemFlood(&flood
, x
, y
, DstSurf
, DstRect
, ConvColor
, FALSE
);
114 while (flood
.floodLen
!= 0)
116 x
= flood
.floodStart
->x
;
117 y
= flood
.floodStart
->y
;
118 removeItemFlood(&flood
);
120 DibFunctionsForBitmapFormat
[DstSurf
->iBitmapFormat
].DIB_PutPixel(DstSurf
, x
, y
, BrushColor
);
121 if (flood
.floodStart
- 4 < flood
.floodData
)
123 DPRINT1("Can't finish flooding!\n");
124 finalizeFlood(&flood
);
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
);
132 finalizeFlood(&flood
);
134 else if (FillType
== FLOODFILLSURFACE
)
136 /* Check if the start pixel has the surface color */
137 if (DibFunctionsForBitmapFormat
[DstSurf
->iBitmapFormat
].DIB_GetPixel(DstSurf
, x
, y
) != ConvColor
)
142 if (initFlood(&flood
, DstRect
) == FALSE
)
146 addItemFlood(&flood
, x
, y
, DstSurf
, DstRect
, ConvColor
, TRUE
);
147 while (flood
.floodLen
!= 0)
149 x
= flood
.floodStart
->x
;
150 y
= flood
.floodStart
->y
;
151 removeItemFlood(&flood
);
153 DibFunctionsForBitmapFormat
[DstSurf
->iBitmapFormat
].DIB_PutPixel(DstSurf
, x
, y
, BrushColor
);
154 if (flood
.floodStart
- 4 < flood
.floodData
)
156 DPRINT1("Can't finish flooding!\n");
157 finalizeFlood(&flood
);
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
);
165 finalizeFlood(&flood
);
169 DPRINT1("Unsupported FloodFill type!\n");