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">