Re: [ros-dev] [ros-diffs] [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

[Timo Kreuzer]

1.) Why are you using global variables?
2.) Why are you using an XLATEOBJ inside the fill loop?

[e-mail] schrieb:
> 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...
> ==============================================================================
> --- 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...
> ==============================================================================
> --- 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/obj...
> ==============================================================================
> --- 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/win...
> ==============================================================================
> --- 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">