reactos/win32ss/gdi/dib/floodfill.c

   1 /*
   2 * COPYRIGHT:         See COPYING in the top level directory
   3 * PROJECT:           ReactOS win32 subsystem
   4 * PURPOSE:           Flood filling support
   5 * FILE:              subsystems/win32/win32k/dib/floodfill.c
   6 * PROGRAMMER:        Gregor Schneider, <grschneider AT gmail DOT com>
   7 */
   8
   9 #include <win32k.h>
  10
  11 #define NDEBUG
  12 #include <debug.h>
  13
  14 /*
  15 *  This floodfill algorithm is an iterative four neighbors version. It works with an internal stack like data structure.
  16 *  The stack is kept in an array, sized for the worst case scenario of having to add all pixels of the surface.
  17 *  This avoids having to allocate and free memory blocks  all the time. The stack grows from the end of the array towards the start.
  18 *  All pixels are checked before being added, against belonging to the fill rule (FLOODFILLBORDER or FLOODFILLSURFACE)
  19 *  and the position in respect to the clip region. This guarantees all pixels lying on the stack belong to the filled surface.
  20 *  Further optimisations of the algorithm are possible.
  21 */
  22
  23 /* Floodfil helper structures and functions */
  24 typedef struct _floodItem
  25 {
  26   ULONG x;
  27   ULONG y;
  28 } FLOODITEM;
  29
  30 typedef struct _floodInfo
  31 {
  32   ULONG floodLen;
  33   FLOODITEM *floodStart;
  34   FLOODITEM *floodData;
  35 } FLOODINFO;
  36
  37 static __inline BOOL initFlood(FLOODINFO *info, RECTL *DstRect)
  38 {
  39   ULONG width = DstRect->right - DstRect->left;
  40   ULONG height = DstRect->bottom - DstRect->top;
  41   info->floodData = ExAllocatePoolWithTag(NonPagedPool, width * height * sizeof(FLOODITEM), TAG_DIB);
  42   if (info->floodData == NULL)
  43   {
  44     return FALSE;
  45   }
  46   info->floodStart = info->floodData + (width * height);
  47   DPRINT("Allocated flood stack from %p to %p\n", info->floodData, info->floodStart);
  48   return TRUE;
  49 }
  50 static __inline VOID finalizeFlood(FLOODINFO *info)
  51 {
  52   ExFreePoolWithTag(info->floodData, TAG_DIB);
  53 }
  54 static __inline VOID addItemFlood(FLOODINFO *info,
  55                                   ULONG x,
  56                                   ULONG y,
  57                                   SURFOBJ *DstSurf,
  58                                   RECTL *DstRect,
  59                                   ULONG Color,
  60                                   BOOL isSurf)
  61 {
  62   if (RECTL_bPointInRect(DstRect,x,y))
  63   {
  64     if (isSurf == TRUE &&
  65       DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) != Color)
  66     {
  67       return;
  68     }
  69     else if (isSurf == FALSE &&
  70       DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) == Color)
  71     {
  72       return;
  73     }
  74     info->floodStart--;
  75     info->floodStart->x = x;
  76     info->floodStart->y = y;
  77     info->floodLen++;
  78   }
  79 }
  80 static __inline VOID removeItemFlood(FLOODINFO *info)
  81 {
  82   info->floodStart++;
  83   info->floodLen--;
  84 }
  85
  86 BOOLEAN DIB_XXBPP_FloodFillSolid(SURFOBJ *DstSurf,
  87                                  BRUSHOBJ *Brush,
  88                                  RECTL *DstRect,
  89                                  POINTL *Origin,
  90                                  ULONG ConvColor,
  91                                  UINT FillType)
  92 {
  93   ULONG x, y;
  94   ULONG BrushColor;
  95   FLOODINFO flood = {0, NULL, NULL};
  96
  97   BrushColor = Brush->iSolidColor;
  98   x = Origin->x;
  99   y = Origin->y;
 100
 101   if (FillType == FLOODFILLBORDER)
 102   {
 103     /* Check if the start pixel has the border color */
 104     if (DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) == ConvColor)
 105     {
 106       return FALSE;
 107     }
 108
 109     if (initFlood(&flood, DstRect) == FALSE)
 110     {
 111       return FALSE;
 112     }
 113     addItemFlood(&flood, x, y, DstSurf, DstRect, ConvColor, FALSE);
 114     while (flood.floodLen != 0)
 115     {
 116       x = flood.floodStart->x;
 117       y = flood.floodStart->y;
 118       removeItemFlood(&flood);
 119
 120       DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_PutPixel(DstSurf, x, y, BrushColor);
 121       if (flood.floodStart - 4 < flood.floodData)
 122       {
 123         DPRINT1("Can't finish flooding!\n");
 124         finalizeFlood(&flood);
 125         return FALSE;
 126       }
 127       addItemFlood(&flood, x, y + 1, DstSurf, DstRect, ConvColor, FALSE);
 128       addItemFlood(&flood, x, y - 1, DstSurf, DstRect, ConvColor, FALSE);
 129       addItemFlood(&flood, x + 1, y, DstSurf, DstRect, ConvColor, FALSE);
 130       addItemFlood(&flood, x - 1, y, DstSurf, DstRect, ConvColor, FALSE);
 131     }
 132     finalizeFlood(&flood);
 133   }
 134   else if (FillType == FLOODFILLSURFACE)
 135   {
 136     /* Check if the start pixel has the surface color */
 137     if (DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) != ConvColor)
 138     {
 139       return FALSE;
 140     }
 141
 142     if (initFlood(&flood, DstRect) == FALSE)
 143     {
 144       return FALSE;
 145     }
 146     addItemFlood(&flood, x, y, DstSurf, DstRect, ConvColor, TRUE);
 147     while (flood.floodLen != 0)
 148     {
 149       x = flood.floodStart->x;
 150       y = flood.floodStart->y;
 151       removeItemFlood(&flood);
 152
 153       DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_PutPixel(DstSurf, x, y, BrushColor);
 154       if (flood.floodStart - 4 < flood.floodData)
 155       {
 156         DPRINT1("Can't finish flooding!\n");
 157         finalizeFlood(&flood);
 158         return FALSE;
 159       }
 160       addItemFlood(&flood, x, y + 1, DstSurf, DstRect, ConvColor, TRUE);
 161       addItemFlood(&flood, x, y - 1, DstSurf, DstRect, ConvColor, TRUE);
 162       addItemFlood(&flood, x + 1, y, DstSurf, DstRect, ConvColor, TRUE);
 163       addItemFlood(&flood, x - 1, y, DstSurf, DstRect, ConvColor, TRUE);
 164     }
 165     finalizeFlood(&flood);
 166   }
 167   else
 168   {
 169     DPRINT1("Unsupported FloodFill type!\n");
 170     return FALSE;
 171   }
 172   return TRUE;
 173 }