Author: gschneider
Date: Fri Jul 31 17:41:09 2009
New Revision: 42311
URL: http://svn.reactos.org/svn/reactos?rev=42311&view=rev
Log:
- Implement Floodfill: iterative four neighbors version
- Details for this algorithm are described in the comments
- Nice with the paint clone since the bucket fill tool works now
Added:
trunk/reactos/subsystems/win32/win32k/dib/floodfill.c (with props)
Modified:
trunk/reactos/subsystems/win32/win32k/dib/dib.h
trunk/reactos/subsystems/win32/win32k/objects/fillshap.c
trunk/reactos/subsystems/win32/win32k/win32k.rbuild
Modified: trunk/reactos/subsystems/win32/win32k/dib/dib.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/subsystems/win32/win32k/dib/dib.h?rev=42311&r1=42310&r2=42311&view=diff
==============================================================================
--- trunk/reactos/subsystems/win32/win32k/dib/dib.h [iso-8859-1] (original)
+++ trunk/reactos/subsystems/win32/win32k/dib/dib.h [iso-8859-1] Fri Jul 31 17:41:09 2009
@@ -133,6 +133,7 @@
BOOLEAN DIB_32BPP_AlphaBlend(SURFOBJ*, SURFOBJ*, RECTL*, RECTL*, CLIPOBJ*, XLATEOBJ*, BLENDOBJ*);
BOOLEAN DIB_XXBPP_StretchBlt(SURFOBJ*,SURFOBJ*,SURFOBJ*,SURFOBJ*,RECTL*,RECTL*,POINTL*,BRUSHOBJ*,POINTL*,XLATEOBJ*,XLATEOBJ*,ROP4);
+BOOLEAN DIB_XXBPP_FloodFill(SURFOBJ*, BRUSHOBJ*, RECTL*, POINTL*, XLATEOBJ*, COLORREF, UINT);
extern unsigned char notmask[2];
extern unsigned char altnotmask[2];
Added: trunk/reactos/subsystems/win32/win32k/dib/floodfill.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/subsystems/win32/win32k/dib/floodfill.c?rev=42311&view=auto
==============================================================================
--- trunk/reactos/subsystems/win32/win32k/dib/floodfill.c (added)
+++ trunk/reactos/subsystems/win32/win32k/dib/floodfill.c [iso-8859-1] Fri Jul 31 17:41:09 2009
@@ -1,0 +1,168 @@
+/*
+ * COPYRIGHT: See COPYING in the top level directory
+ * PROJECT: ReactOS win32 subsystem
+ * PURPOSE: Flood filling support
+ * FILE: subsystems/win32/win32k/dib/floodfill.c
+ * PROGRAMMER: Gregor Schneider, <grschneider AT gmail DOT com>
+ */
+
+#include <w32k.h>
+
+#define NDEBUG
+#include <debug.h>
+
+/*
+* This floodfill algorithm is an iterative four neighbors version. It works with an internal stack like data structure.
+* The stack is kept in an array, sized for the worst case scenario of having to add all pixels of the surface.
+* This avoids having to allocate and free memory blocks all the time. The stack grows from the end of the array towards the start.
+* All pixels are checked before being added, against belonging to the fill rule (FLOODFILLBORDER or FLOODFILLSURFACE)
+* and the position in respect to the clip region. This guarantees all pixels lying on the stack belong to the filled surface.
+* Further optimisations of the algorithm are possible.
+*/
+
+/* Floodfil helper structures and functions */
+typedef struct _floodItem
+{
+ ULONG x;
+ ULONG y;
+} FLOODITEM;
+
+static ULONG floodLen = 0;
+static FLOODITEM *floodStart = NULL, *floodData = NULL;
+
+static __inline BOOL initFlood(RECTL *DstRect)
+{
+ ULONG width = DstRect->right - DstRect->left;
+ ULONG height = DstRect->bottom - DstRect->top;
+ floodData = ExAllocatePoolWithTag(NonPagedPool, width * height * sizeof(FLOODITEM), TAG_DIB);
+ if (floodData == NULL)
+ {
+ return FALSE;
+ }
+ floodStart = (FLOODITEM*)((PBYTE)floodData + (width * height * sizeof(FLOODITEM)));
+ return TRUE;
+}
+static __inline VOID finalizeFlood()
+{
+ ExFreePoolWithTag(floodData, TAG_DIB);
+}
+static __inline VOID addItemFlood(ULONG x,
+ ULONG y,
+ SURFOBJ *DstSurf,
+ RECTL *DstRect,
+ XLATEOBJ* ColorTranslation,
+ COLORREF Color,
+ BOOL isSurf)
+{
+ if (x >= DstRect->left && x <= DstRect->right &&
+ y >= DstRect->top && y <= DstRect->bottom)
+ {
+ if (isSurf == TRUE && XLATEOBJ_iXlate(ColorTranslation,
+ DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y)) != Color)
+ {
+ return;
+ }
+ else if (isSurf == FALSE && XLATEOBJ_iXlate(ColorTranslation,
+ DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y)) == Color)
+ {
+ return;
+ }
+ floodStart--;
+ floodStart->x = x;
+ floodStart->y = y;
+ floodLen++;
+ }
+}
+static __inline VOID removeItemFlood()
+{
+ floodStart++;
+ floodLen--;
+}
+static __inline BOOL isEmptyFlood()
+{
+ if (floodLen == 0)
+ {
+ return TRUE;
+ }
+ return FALSE;
+}
+
+BOOLEAN DIB_XXBPP_FloodFill(SURFOBJ *DstSurf,
+ BRUSHOBJ *Brush,
+ RECTL *DstRect,
+ POINTL *Origin,
+ XLATEOBJ *ColorTranslation,
+ COLORREF Color,
+ UINT FillType)
+{
+ ULONG x, y;
+ ULONG BrushColor;
+
+ BrushColor = Brush->iSolidColor;
+ x = Origin->x;
+ y = Origin->y;
+
+ if (FillType == FLOODFILLBORDER)
+ {
+ /* Check if the start pixel has the border color */
+ if (XLATEOBJ_iXlate(ColorTranslation,
+ DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y)) == Color)
+ {
+ return FALSE;
+ }
+
+ if (initFlood(DstRect) == FALSE)
+ {
+ return FALSE;
+ }
+ addItemFlood(x, y, DstSurf, DstRect, ColorTranslation, Color, FALSE);
+ while (!isEmptyFlood())
+ {
+ x = floodStart->x;
+ y = floodStart->y;
+ removeItemFlood();
+
+ DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_PutPixel(DstSurf, x, y, BrushColor);
+ addItemFlood(x, y + 1, DstSurf, DstRect, ColorTranslation, Color, FALSE);
+ addItemFlood(x, y - 1, DstSurf, DstRect, ColorTranslation, Color, FALSE);
+ addItemFlood(x + 1, y, DstSurf, DstRect, ColorTranslation, Color, FALSE);
+ addItemFlood(x - 1, y, DstSurf, DstRect, ColorTranslation, Color, FALSE);
+ }
+ finalizeFlood();
+ }
+ else if (FillType == FLOODFILLSURFACE)
+ {
+ /* Check if the start pixel has the surface color */
+ if (XLATEOBJ_iXlate(ColorTranslation,
+ DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y)) != Color)
+ {
+ return FALSE;
+ }
+
+ if (initFlood(DstRect) == FALSE)
+ {
+ return FALSE;
+ }
+ addItemFlood(x, y, DstSurf, DstRect, ColorTranslation, Color, TRUE);
+ while (!isEmptyFlood())
+ {
+ x = floodStart->x;
+ y = floodStart->y;
+ removeItemFlood();
+
+ DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_PutPixel(DstSurf, x, y, BrushColor);
+ addItemFlood(x, y + 1, DstSurf, DstRect, ColorTranslation, Color, TRUE);
+ addItemFlood(x, y - 1, DstSurf, DstRect, ColorTranslation, Color, TRUE);
+ addItemFlood(x + 1, y, DstSurf, DstRect, ColorTranslation, Color, TRUE);
+ addItemFlood(x - 1, y, DstSurf, DstRect, ColorTranslation, Color, TRUE);
+
+ }
+ finalizeFlood();
+ }
+ else
+ {
+ DPRINT1("Unsupported FloodFill type!\n");
+ return FALSE;
+ }
+ return TRUE;
+}
Propchange: trunk/reactos/subsystems/win32/win32k/dib/floodfill.c
------------------------------------------------------------------------------
svn:eol-style = native
Modified: trunk/reactos/subsystems/win32/win32k/objects/fillshap.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/subsystems/win32/win32k/objects/fillshap.c?rev=42311&r1=42310&r2=42311&view=diff
==============================================================================
--- trunk/reactos/subsystems/win32/win32k/objects/fillshap.c [iso-8859-1] (original)
+++ trunk/reactos/subsystems/win32/win32k/objects/fillshap.c [iso-8859-1] Fri Jul 31 17:41:09 2009
@@ -1072,12 +1072,11 @@
PDC dc;
PDC_ATTR pdcattr;
SURFACE *psurf = NULL;
- PBRUSH pbrFill = NULL;
+ HPALETTE Pal = 0;
+ XLATEOBJ *XlateObj = NULL;
BOOL Ret = FALSE;
RECTL DestRect;
POINTL Pt;
-
- DPRINT1("FIXME: NtGdiExtFloodFill is UNIMPLEMENTED\n");
dc = DC_LockDc(hDC);
if (!dc)
@@ -1110,17 +1109,21 @@
else
goto cleanup;
- pbrFill = dc->dclevel.pbrFill;
- if (!pbrFill)
+ psurf = dc->dclevel.pSurface;
+ if (!psurf)
{
Ret = FALSE;
goto cleanup;
}
- psurf = dc->dclevel.pSurface;
- if (!psurf)
- {
- Ret = FALSE;
- goto cleanup;
+
+ Pal = dc->dclevel.pSurface->hDIBPalette;
+ if (!Pal) Pal = pPrimarySurface->DevInfo.hpalDefault;
+ XlateObj = (XLATEOBJ*)IntEngCreateXlate(PAL_RGB, 0, NULL, Pal);
+
+ if (XlateObj != NULL)
+ {
+ Ret = DIB_XXBPP_FloodFill(&psurf->SurfObj, &dc->eboFill.BrushObject, &DestRect, &Pt, XlateObj, Color, FillType);
+ EngDeleteXlate(XlateObj);
}
cleanup:
Modified: trunk/reactos/subsystems/win32/win32k/win32k.rbuild
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/subsystems/win32/win32k/win32k.rbuild?rev=42311&r1=42310&r2=42311&view=diff
==============================================================================
--- trunk/reactos/subsystems/win32/win32k/win32k.rbuild [iso-8859-1] (original)
+++ trunk/reactos/subsystems/win32/win32k/win32k.rbuild [iso-8859-1] Fri Jul 31 17:41:09 2009
@@ -31,6 +31,7 @@
<file>dib32bpp.c</file>
<file>dibXXbpp.c</file>
<file>dib.c</file>
+ <file>floodfill.c</file>
<if property="ARCH" value="i386">
<directory name="i386">