Flood-fill fails to fill whole shape when reaching boundary color?

Question

I would like to draw some shape and then fill those shape with chosen color. At this time, I have just completed in drawing some basic shapes, but I'm still stuck at coloring them with flood-fill algorithm.

In details, I can not coloring the whole shape after clicking on it. All it could do is just drawing a line to the edge of the screen, leaking the chosen color outside the edge of the shape (ignoring the boundary color of the shape).

Here is all my work, can anyone help me???

#include <GL/glut.h>
#include <math.h>
#include <iostream>
using namespace std;

static int window;
static int value = 0;
GLsizei width, height;
int flag = 0;
bool up = false, down = false;

struct Point {
    GLint x;
    GLint y;
};
struct RGBColor
{
    GLfloat r;
    GLfloat g;
    GLfloat b;
};
struct Position
{
    Position() : x(0), y(0) {}
    float x;
    float y;
};
Position start;
Position finish; 
void init()
{
    glClearColor(0, 0, 0, 0);
    glPointSize(2.0);
    glLineWidth(2.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, 500.0, 500.0, 0.0);
}
void menu(int num) {
    if (num == 0) {
        glutDestroyWindow(window);
        exit(0);
    }
    else {
        value = num;
    }
    glutPostRedisplay();
}
void createMenu(void) 
{
    int sub_Triangle = glutCreateMenu(menu);
    glutAddMenuEntry("Isoceles right", 2);
    glutAddMenuEntry("Equilateral", 3);
    int menu_Triangle = glutCreateMenu(menu);
    int sub_Quadrilateral = glutCreateMenu(menu);
    glutAddMenuEntry("Rectangle", 4);
    glutAddMenuEntry("Square", 5);
    int menu__Quadrilateral = glutCreateMenu(menu);
    int sub_Oval = glutCreateMenu(menu);
    glutAddMenuEntry("Circle", 6);
    glutAddMenuEntry("Ellipse", 7);
    int menu_Oval = glutCreateMenu(menu);
    int sub_RegularPolygon = glutCreateMenu(menu);
    glutAddMenuEntry("Pentagon", 8);
    glutAddMenuEntry("Hexagon", 9);
    int menu_RegularPolygon = glutCreateMenu(menu);
    int sub_OtherShape = glutCreateMenu(menu);
    glutAddMenuEntry("Arrow", 10);
    glutAddMenuEntry("Star", 11);
    int menu_OtherShape = glutCreateMenu(menu);
    int sub_Operation = glutCreateMenu(menu);
    glutAddMenuEntry("Add", 12);
    glutAddMenuEntry("Subtract", 13);
    glutAddMenuEntry("Multiply", 14);
    glutAddMenuEntry("Divide", 15);
    int menu_Operation = glutCreateMenu(menu);
    int sub_ColorFill = glutCreateMenu(menu);
    glutAddMenuEntry("Red", 16);
    glutAddMenuEntry("Green", 17);
    glutAddMenuEntry("Blue", 18);
    int menu_ColorFill = glutCreateMenu(menu);
    glutAddMenuEntry("Line", 1);
    glutAddSubMenu("Triangle", sub_Triangle);
    glutAddSubMenu("Quadrilateral", sub_Quadrilateral);
    glutAddSubMenu("Oval", sub_Oval);
    glutAddSubMenu("Regular Polygon", sub_RegularPolygon);
    glutAddSubMenu("Other Shape", sub_OtherShape);
    glutAddSubMenu("Operation", sub_Operation);
    glutAddSubMenu("Color Fill", sub_ColorFill);
    glutAddMenuEntry("Shape Choice", 19);
    glutAttachMenu(GLUT_RIGHT_BUTTON);
}
void draw_Line()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINE_LOOP);
    glVertex2f(start.x, start.y);
    glVertex2f(finish.x, finish.y);
    glEnd();
    glutSwapBuffers();
}
void draw_IsocelesRight()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINE_LOOP);
    int a = finish.y - start.y;
    glVertex2f(start.x, start.y);
    glVertex2f(start.x, start.y + a);
    glVertex2f(start.x + a, start.y + a);
}
void draw_Equilateral()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINE_LOOP);
    int midx = (finish.x + start.x) / 2;
    int midbotx = (start.y - finish.y)*(1 / sqrt(3));
    int midboty = finish.y;
    glVertex2f(midx, start.y);
    glVertex2f(midx - midbotx, finish.y);
    glVertex2f(midx + midbotx, finish.y);
}
void draw_Rectangle()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINE_LOOP);
    glVertex2f(start.x, start.y);
    glVertex2f(finish.x, start.y);
    glVertex2f(finish.x, finish.y);
    glVertex2f(start.x, finish.y);
}
void draw_Square()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINE_LOOP);

    int a = finish.y - start.y;
    glVertex2f(start.x, start.y);
    glVertex2f(start.x, start.y + a);
    glVertex2f(start.x + a, start.y + a);
    glVertex2f(start.x + a, start.y);
}
void draw_Circle() 
{
    float PI = 3.14;
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINE_LOOP);
    int size = sqrt(pow(finish.x - start.x, 2) + pow(finish.y - start.y, 2));
    for (int i = 0; i <= 360; i++)
    {
        float theta = (2 * 3.14 * i) / 360;
        glVertex2f((size / 2) * cos(theta) + finish.x, (size / 2) * sin(theta) + finish.y);
    }
}
void draw_Ellipse()
{
    float PI = 3.14;
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINE_LOOP);
    int size1 = sqrt(pow(finish.x - start.x, 2) + pow(finish.x - start.x, 2));
    int size2 = sqrt(pow(finish.y - start.y, 2) + pow(finish.y - start.y, 2));

    for (int i = 0; i <= 360; i++)
    {
        float theta = (2 * 3.14 * i) / 360;
        glVertex2f((size1 / 2) * cos(theta) + finish.x, (size2 / 2) * sin(theta) + finish.y);
    }
}
void draw_Pentagon()
{
    const double PI = 3.14159265358979323846;
    double r = sqrt(pow(finish.x - start.x, 2));
    int sides = 5;
    int center_x = start.x + (finish.x - start.x) / 2;
    int center_y = start.y + (finish.y - start.y) / 2;

    glBegin(GL_LINE_LOOP);
    for (int i = 0; i < sides; i++) {
        double angle = i * 2 * PI / sides;
        glVertex2d(center_x + r*cos(angle), center_y + r*sin(angle));
    }
}
void draw_Hexagon()
{
    const double PI = 3.14159265358979323846;
    double r = sqrt(pow(finish.x - start.x, 2));
    int sides = 6;
    int center_x = start.x + (finish.x - start.x) / 2;
    int center_y = start.y + (finish.y - start.y) / 2;
    glBegin(GL_LINE_LOOP);
    for (int i = 0; i < sides; i++) {
        double angle = i * 2 * PI / sides;
        glVertex2d(center_x + r*cos(angle), center_y + r*sin(angle));
    }
}
void draw_Arrow()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINES);
    const double PI = 3.14159265358979323846;
    double length = finish.x - start.x;
    double e = length / 3;
    double x1 = finish.x - e *  (1/tan(45 * PI /180));
    double y1 = start.y - e * tan(45 * PI / 180);
    double x2 = finish.x - e *  (1 / tan(45 * PI / 180));
    double y2 = start.y + e * tan(45 * PI / 180);
    glVertex2f(start.x, start.y);
    glVertex2f(finish.x, start.y);
    glVertex2f(finish.x, start.y);
    glVertex2f(x1, y1);
    glVertex2f(finish.x, start.y);
    glVertex2f(x2, y2);
}
void draw_Star()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINE_LOOP);
    glVertex2f(100, 225);
    glVertex2f(210, 225);
    glVertex2f(250, 100);
    glVertex2f(290, 225);
    glVertex2f(400, 225);
    glVertex2f(315, 290);
    glVertex2f(350, 400);
    glVertex2f(250, 330);
    glVertex2f(150, 400);
    glVertex2f(185, 290);
}
void draw_Add()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINES);
    double length = finish.x - start.x;
    double half_length = length / 2;
    glVertex2f(start.x + half_length, start.y);
    glVertex2f(start.x + half_length, start.y + length);
    glVertex2f(start.x, start.y + half_length);
    glVertex2f(start.x + length, start.y + half_length);
}
void draw_Subtract()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINES);
    double length = finish.x - start.x;
    glVertex2f(start.x, start.y);
    glVertex2f(start.x + length, start.y);
}
void draw_Multiply()
{
    glColor3f(1.0, 1.0, 1.0);
    glBegin(GL_LINES);
    double length = finish.x - start.x;
    glVertex2f(start.x, start.y);
    glVertex2f(start.x + length, start.y + length);
    glVertex2f(start.x + length , start.y);
    glVertex2f(start.x, start.y + length);
}


RGBColor getPixelColor(GLint x, GLint y)
{
    RGBColor color;
    glReadPixels(x, y, 1, 1, GL_RGB, GL_FLOAT, &color);
    return color;
}
void setPixelColor(GLint x, GLint y, RGBColor color)
{
    glColor3f(color.r, color.g, color.b);
    glBegin(GL_POINTS);
    glVertex2i(x, y);
    glEnd();
    glFlush();
}
void floodFill(GLint x, GLint y, RGBColor oldColor, RGBColor newColor)
{
    RGBColor color;
    color = getPixelColor(x, y);
    if (color.r == oldColor.r && color.g == oldColor.g && color.b == oldColor.b)
    {
        setPixelColor(x, y, newColor);
        floodFill(x + 1, y, oldColor, newColor);
        floodFill(x, y + 1, oldColor, newColor);
        floodFill(x - 1, y, oldColor, newColor);
        floodFill(x, y - 1, oldColor, newColor);
    }
    return;
}

bool IsSameColor(RGBColor x, RGBColor y) {
    if (x.r == y.r && x.b == y.b && x.g == y.g) {
        cout << "is same color true" << endl;
        return true;
    }
    else {
        cout << "is same color false" << endl;
        return false;
    }
}
void BoundaryFill(int x, int y, RGBColor F_Color, RGBColor B_Color) {
    cout << "bound fill" << endl;
    RGBColor currentColor;

    currentColor = getPixelColor(x, y);

    if (!IsSameColor(currentColor, B_Color) && !IsSameColor(currentColor, F_Color)) {
        cout << "bound" << endl;
        setPixelColor(x, y, F_Color);
        BoundaryFill(x - 1, y, F_Color, B_Color);
        BoundaryFill(x, y + 1, F_Color, B_Color);
        BoundaryFill(x + 1, y, F_Color, B_Color);
        BoundaryFill(x, y - 1, F_Color, B_Color);
    }
}

void display()
{
    if (flag == 1)
    {
        if (value == 1) {
            draw_Line();
        }
        else if (value == 2) {
            draw_IsocelesRight();
        }
        else if (value == 3) {
            draw_Equilateral();
        }
        else if (value == 4) {
            draw_Rectangle();
        }
        else if (value == 5) {
            draw_Square();
        }
        else if (value == 6) {
            draw_Circle();
        }
        else if (value == 7) {
            draw_Ellipse();
        }
        else if (value == 8) {
            draw_Pentagon();
        }
        else if (value == 9) {
            draw_Hexagon();
        }
        else if (value == 10) {
            draw_Arrow();
        }
        else if (value == 11) {
            draw_Star();
        }
        else if (value == 12) {
            draw_Add();
        }
        else if (value == 13) {
            draw_Subtract();
        }
        else if (value == 14) {
            draw_Multiply();
        }
        else if (value == 16) 
        {
            RGBColor newColor = { 1.0f, 0.0f, 0.0f }; // red
            RGBColor oldColor = { 0.0f, 0.0f, 0.0f }; // black
            floodFill(start.x, start.y, oldColor, newColor);
        }
        glEnd();
        glutSwapBuffers();
        glFlush();
    }
    flag = 0;
}
void reshape(int w, int h)
{
    glViewport(0, 0, (GLsizei)w, (GLsizei)h); 
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0, w, h, 0);

    width = w;
    height = h;

    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
}
void mouse(int button, int state, int x, int y)
{
    if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
    {
        down = true;
        start.x = x; //x1
        start.y = y; //y1
    }
    if (button == GLUT_LEFT_BUTTON && state == GLUT_UP)
    {
        if (down == true) {
            up = true;
            flag = 1;
            finish.x = x;
            finish.y = y;
        }

        down = false;
        up = false; 
    }
    glutPostRedisplay();
}

int main(int argc, char** argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowSize(500, 500);
    glutInitWindowPosition(450, 100);
    window = glutCreateWindow("Coloring Shapes");

    init();
    createMenu();
    glutDisplayFunc(display);
    glutReshapeFunc(reshape);
    glutMouseFunc(mouse);
    glutMainLoop();
    return 0;
}

Answer 1

The major issue is, that the coordinates which you pass to glReadPixels are wrong.

When a point is drawn, by glVertex then the coordinates are transformed by the modelview and projection matrix.
So the orthographic projection is applied

gluOrtho2D(0.0, 500.0, 500.0, 0.0);

But glReadPixels directly read the fragment of the framebuffer. The coordinates are the x and y coordinate of the fragment in the framebuffer, where the bottom left is always (0, 0) and the top right is (widht, height). You've to flip the y coordinate when you read the the fragment:

RGBColor getPixelColor(GLint x, GLint y) 
{
    RGBColor color;
    glReadPixels(x, height-y, 1, 1, GL_RGB, GL_FLOAT, &color);
    return color;
} 

---

In order not to sit rounding errors when calling glVertex2i, I recommend to use glRasterPos2i and glDrawPixels instead. The coordinates to glRasterPos2i are transformed by the current modelview and projection matrix:

void setPixelColor(GLint x, GLint y, RGBColor color)
{
    glRasterPos2i( x, y );
    glDrawPixels( 1, 1, GL_RGB, GL_FLOAT, &color );
    glFlush();
}

---

Since the color values are floating point values, you've to consider in inaccuracy when reading the color back from the GPU. Consider this when you compare the colors:

e.g.

color1.r == color2.r fabs(color1.r - color2.r) < 0.001f

Write a function which compares colors and use it in floodFill:

bool isEqual( const RGBColor &c1, const RGBColor &c2 )
{
    return fabs(c1.r - c2.r) < 0.001f && fabs(c1.g - c2.g) < 0.001f && fabs(c1.b - c2.b) < 0.001f;
}

void floodFill(GLint x, GLint y, RGBColor oldColor, RGBColor newColor)
{
    RGBColor color;
    color = getPixelColor(x, y);
    if ( isEqual(color, oldColor) )
    {
        setPixelColor(x, y, newColor);
        floodFill(x + 1, y, oldColor, newColor);
        floodFill(x, y + 1, oldColor, newColor);
        floodFill(x - 1, y, oldColor, newColor);
        floodFill(x, y - 1, oldColor, newColor);
    }
    return;
}

---

Anyway your code will only work for small areas, because the algorithm is recursive. The stack usage increased rapidly and causes a stack overflow immediately.
But it works for tine areas.

Answer 2

Make sure your glReadBuffer() points to the right buffer. For double buffered rendering, glDrawBuffer and glReadBuffer point to GL_BACK per default.

Also there are some issues in your code. It seems to me you use double buffered rendering in an incorrect way. Single frame rendering procedure usually looks like this:

void display(){
    // user sees front buffer at the moment
    ClearScreen(); // glClear() or something, done on back buffer
    RenderAllYouHaveOnTheScene(); // rendered to back buffer
    SwapBuffers(); // glutSwapBuffers() does this in glut
    // Now back buffer becomes front buffer and user sees rendered scene.
    // Contents of current back buffer (which was front buffer
    // before glutSwapBuffers()) is undefined and you should 
    // clear it and redraw everything on next iteration.
}

And I don't see any point in swaping buffers in your draw_Line() procedure.

It is not a good thing to do float comparison with == operator. Read here. Use unsigned char pixel format or do float comparison with precision as described in the link.

Also check if your (x, y) coordinates do not overflow your screen boundaries (0 <= x < Width, 0 <= y < Height).

Edit: Also, as I noticed later, you specify GLUT_SINGLE in glutInitDisplayMode which means single buffered rendering, but use glutSwapBuffers, which should only be used in case of double buffered rendering. Read here to learn the difference.