New subject: [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

31 Jul 2009

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

gschneider(a)svn.reactos.org 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/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">

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