1 /* 2 * COPYRIGHT: See COPYING in the top level directory 3 * PROJECT: ReactOS win32 subsystem 4 * PURPOSE: Flood filling support 5 * FILE: win32ss/gdi/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 && 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 } 174