//the floodfill algorithms
void floodFill4(int x, int y, int newColor, int oldColor);
void floodFill8(int x, int y, int newColor, int oldColor);
void floodFill4Stack(int x, int y, int newColor, int oldColor);
void floodFill8Stack(int x, int y, int newColor, int oldColor);
void floodFillScanline(int x, int y, int newColor, int oldColor);
void floodFillScanlineStack(int x, int y, int newColor, int oldColor);
//the stack
#define stackSize 16777216
int stack[stackSize];
int stackPointer;
//the auxiliary functions
bool paint_drawLine(int x1, int y1, int x2, int y2, ColorRGB
color);
void clearScreenBuffer(ColorRGB color);
//the graphics buffer
#define screenW 256
#define screenH 256
int screenBuffer[screenW][screenH];
|
int main(int argc, char *argv[])
{
screen(screenW, screenH, 0, "Flood Fill");
clearScreenBuffer(RGB_White);
int mouseX, mouseY;
int oldMouseX, oldMouseY;
bool LMB, RMB;
while(!done())
{
oldMouseX = mouseX;
oldMouseY = mouseY;
getMouseState(mouseX, mouseY, LMB, RMB);
//3 different mouse input actions
if(LMB) paint_drawLine(oldMouseX, oldMouseY, mouseX, mouseY, RGB_Black);
if(RMB)
{
int color = RGBtoINT(ColorRGB((mouseX % 3 + 1) * 64, (mouseY % 8) * 32, (mouseX + mouseY) % 256));
floodFillScanlineStack(mouseX, mouseY, color, screenBuffer[mouseX][mouseY]);
}
if(RMB && LMB) clearScreenBuffer(RGB_White);
//benchmark
readKeys();
if(inkeys[SDLK_SPACE])
{
float startTime = getTime();
for(int i = 1; i < 50; i++) floodFill4Stack(mouseX, mouseY, RGBtoINT(ColorRGB(i,255,i)), screenBuffer[mouseX][mouseY]);
float endTime = getTime();
float startTime2 = getTime();
for(int i = 1; i < 50; i++) floodFillScanlineStack(mouseX, mouseY, RGBtoINT(ColorRGB(i,255,i)), screenBuffer[mouseX][mouseY]);
float endTime2 = getTime();
drawBuffer(screenBuffer[0]);
print(endTime - startTime, 0, 0, 0, RGB_Black, 1, RGB_White);
print(endTime2 - startTime2, 0, 0, 8, RGB_Black, 1, RGB_White);
redraw();
sleep();
}
//redraw the screen each frame
drawBuffer(screenBuffer[0]);
redraw();
}
return 0;
}
|
bool pop(int
&x, int &y)
{
if(stackPointer > 0)
{
int p = stack[stackPointer];
x = p / h;
y = p % h;
stackPointer--;
return 1;
}
else
{
return 0;
}
}
bool push(int x, int y)
{
if(stackPointer < stackSize - 1)
{
stackPointer++;
stack[stackPointer] = h * x + y;
return 1;
}
else
{
return 0;
}
}
void emptyStack()
{
int x, y;
while(pop(x, y));
}
|
void clearScreenBuffer(ColorRGB color)
{
for(int x = 0; x < w; x++)
for(int y = 0; y < h; y++)
{
screenBuffer[x][y] = RGBtoINT(color);
}
}
|
//Recursive 4-way floodfill, crashes if recursion stack is full
void floodFill4(int x, int y, int newColor, int oldColor)
{
if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
{
screenBuffer[x][y] = newColor; //set color before starting recursion
floodFill4(x + 1, y, newColor, oldColor);
floodFill4(x - 1, y, newColor, oldColor);
floodFill4(x, y + 1, newColor, oldColor);
floodFill4(x, y - 1, newColor, oldColor);
}
}
|
//Recursive 8-way floodfill, crashes if recursion stack is full
void floodFill8(int x, int y, int newColor, int oldColor)
{
if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
{
screenBuffer[x][y] = newColor; //set color before starting recursion!
floodFill8(x + 1, y, newColor, oldColor);
floodFill8(x - 1, y, newColor, oldColor);
floodFill8(x, y + 1, newColor, oldColor);
floodFill8(x, y - 1, newColor, oldColor);
floodFill8(x + 1, y + 1, newColor, oldColor);
floodFill8(x - 1, y - 1, newColor, oldColor);
floodFill8(x - 1, y + 1, newColor, oldColor);
floodFill8(x + 1, y - 1, newColor, oldColor);
}
}
|
//4-way floodfill using our own stack routines
void floodFill4Stack(int x, int y, int newColor, int oldColor)
{
if(newColor == oldColor) return; //avoid infinite loop
emptyStack();
if(!push(x, y)) return;
while(pop(x, y))
{
screenBuffer[x][y] = newColor;
if(x + 1 < w && screenBuffer[x + 1][y] == oldColor)
{
if(!push(x + 1, y)) return;
}
if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor)
{
if(!push(x - 1, y)) return;
}
if(y + 1 < h && screenBuffer[x][y + 1] == oldColor)
{
if(!push(x, y + 1)) return;
}
if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor)
{
if(!push(x, y - 1)) return;
}
}
}
|
//4-way floodfill using our own stack routines
void floodFill4Stack(int x, int y, int newColor, int oldColor)
{
if(newColor == oldColor) return; //avoid infinite loop
emptyStack();
if(!push(x, y)) return;
while(pop(x, y))
{
screenBuffer[x][y] = newColor;
if(x + 1 < w && screenBuffer[x + 1][y] == oldColor)
{
if(!push(x + 1, y)) return;
}
if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor)
{
if(!push(x - 1, y)) return;
}
if(y + 1 < h && screenBuffer[x][y + 1] == oldColor)
{
if(!push(x, y + 1)) return;
}
if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor)
{
if(!push(x, y - 1)) return;
}
if(x + 1 < w && y + 1 < h && screenBuffer[x + 1][y + 1] == oldColor)
{
if(!push(x + 1, y + 1)) return;
}
if(x + 1 < w && y - 1 >= 0 && screenBuffer[x + 1][y - 1] == oldColor)
{
if(!push(x + 1, y - 1)) return;
}
if(x - 1 >= 0 && y + 1 < h && screenBuffer[x - 1][y + 1] == oldColor)
{
if(!push(x - 1, y + 1)) return;
}
if(x - 1 >= 0 && y - 1 >= 0 && screenBuffer[x - 1][y - 1] == oldColor)
{
if(!push(x - 1, y - 1)) return;
}
}
}
|
There is very likely to be an error in this chapter. I'll investigate this later.
This algorithm is based on the following steps:
//stack friendly and fast floodfill algorithm
void floodFillScanline(int x, int y, int newColor, int oldColor)
{
if(oldColor == newColor) return;
if(screenBuffer[x][y] != oldColor) return;
int y1;
//draw current scanline from start position to the top
y1 = y;
while(y1 < h && screenBuffer[x][y1] == oldColor)
{
screenBuffer[x][y1] = newColor;
y1++;
}
//draw current scanline from start position to the bottom
y1 = y - 1;
while(y1 >= 0 && screenBuffer[x][y1] == oldColor)
{
screenBuffer[x][y1] = newColor;
y1--;
}
//test for new scanlines to the left
y1 = y;
while(y1 < h && screenBuffer[x][y1] == newColor)
{
if(x > 0 && screenBuffer[x - 1][y1] == oldColor)
{
floodFillScanline(x - 1, y1, newColor, oldColor);
}
y1++;
}
y1 = y - 1;
while(y1 >= 0 && screenBuffer[x][y1] == newColor)
{
if(x > 0 && screenBuffer[x - 1][y1] == oldColor)
{
floodFillScanline(x - 1, y1, newColor, oldColor);
}
y1--;
}
//test for new scanlines to the right
y1 = y;
while(y1 < h && screenBuffer[x][y1] == newColor)
{
if(x < w - 1 && screenBuffer[x + 1][y1] == oldColor)
{
floodFillScanline(x + 1, y1, newColor, oldColor);
}
y1++;
}
y1 = y - 1;
while(y1 >= 0 && screenBuffer[x][y1] == newColor)
{
if(x < w - 1 && screenBuffer[x + 1][y1] == oldColor)
{
floodFillScanline(x + 1, y1, newColor, oldColor);
}
y1--;
}
}
|
//The scanline floodfill algorithm using our own stack routines, faster
void floodFillScanlineStack(int x, int y, int newColor, int oldColor)
{
if(oldColor == newColor) return;
emptyStack();
int y1;
bool spanLeft, spanRight;
if(!push(x, y)) return;
while(pop(x, y))
{
y1 = y;
while(y1 >= 0 && screenBuffer[x][y1] == oldColor) y1--;
y1++;
spanLeft = spanRight = 0;
while(y1 < h && screenBuffer[x][y1] == oldColor )
{
screenBuffer[x][y1] = newColor;
if(!spanLeft && x > 0 && screenBuffer[x - 1][y1] == oldColor)
{
if(!push(x - 1, y1)) return;
spanLeft = 1;
}
else if(spanLeft && x > 0 && screenBuffer[x - 1][y1] != oldColor)
{
spanLeft = 0;
}
if(!spanRight && x < w - 1 && screenBuffer[x + 1][y1] == oldColor)
{
if(!push(x + 1, y1)) return;
spanRight = 1;
}
else if(spanRight && x < w - 1 && screenBuffer[x + 1][y1] != oldColor)
{
spanRight = 0;
}
y1++;
}
}
}
|