[gschneider] 42311: - 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

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/di…
==============================================================================
--- 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/di…
==============================================================================
--- 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/ob…
==============================================================================
--- 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/wi…
==============================================================================
--- 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">