OpenGL flood fill not recognizing boundary

Question

I'm trying to implement the flood fill algorithm in OpenGL, but I'm encountering an error doing so. The error is that the algorithm does not stop at the boundary, and simply keeps going until the edge of the window, and eventually crashes with a bad memory access error. I'm working on MacOS Mojave 10.14.4.

I think my implementation's logic is correct, however, I've printed out the color of each pixel from getPixel, and it is always white (the background color), even when getting the color of boundary pixels.

The code below draws a circle using Bresenham's Line algorithm (midpoint algorithm), and then flood fills it (unsuccessfully).

#include <GLUT/GLUT.h>
#include <iostream>


struct Color {
    GLubyte r;
    GLubyte g;
    GLubyte b;
};

Color getPixelColor(GLint x, GLint y) {
    Color color;
    glReadPixels(x, y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, &color);
    return color;
}

void setPixel (GLint x, GLint y) {
    glBegin(GL_POINTS);
    glVertex2i(x, y);
    glEnd();
    Color color = getPixelColor(x, y);
}


void setPixelColor(GLint x, GLint y, Color color) {
    glColor3ub(color.r, color.g, color.b);
    setPixel(x, y);
    glEnd();
    glFlush();
}

void floodFill4 (GLint x, GLint y, Color fillColor, Color interiorColor) {
    Color color = getPixelColor(x, y);
    if (color.r == interiorColor.r && color.g == interiorColor.g &&
        color.b == interiorColor.b) {
        setPixelColor(x, y, fillColor);
        floodFill4 (x + 1, y, fillColor, interiorColor);
        floodFill4 (x - 1, y, fillColor, interiorColor);
        floodFill4 (x, y + 1, fillColor, interiorColor);
        floodFill4 (x, y - 1, fillColor, interiorColor);
    }
}

void drawCirclePoint(GLint x, GLint y, GLint cx, GLint cy) {
    setPixel(cx+x, cy+y);
    setPixel(cx+y, cy+x);
    setPixel(cx-y, cy+x);
    setPixel(cx-x, cy+y);
    setPixel(cx-x, cy-y);
    setPixel(cx-y, cy-x);
    setPixel(cx+y, cy-x);
    setPixel(cx+x, cy-y);
}

void drawCircle(GLint cx, GLint cy, GLint radius) {
    int p = 1 - radius;
    GLint x = 0;
    GLint y = radius;
    while (x < y) {
        drawCirclePoint(x, y, cx, cy);
        if (p < 0) {
            x++;
            p += (2 * x) + 1;
        } else {
            x++;
            y--;
            p += (2 * x) + 1 - (2 * y);
        }
    }
}


void displayMe(void) {
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3ub(0, 0, 0);
    GLint cx = 0;
    GLint cy = 0;
    GLint radius = 200;
    // Draw head
    glColor3ub(0, 0, 0);
    drawCircle(cx, cy, radius);
    glEnd();
    glFlush();
    Color interiorColor = {255, 255, 255};
    Color fillColor = {0, 0, 255};
//    floodFill4(100, 100, fillColor, interiorColor);
}

void init (void) {
    glClearColor(1.0, 1.0, 1.0, 0.0);  // Set display-window color to white.
    glMatrixMode(GL_PROJECTION);       // Set projection parameters.
    glLoadIdentity();
    gluOrtho2D(-1000.0, 1000.0, -1000.0, 1000.0);
    glMatrixMode(GL_MODELVIEW);
}

int main(int argc, char** argv) {
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowSize(1000, 1000);
    glutInitWindowPosition(100, 100);
    glutCreateWindow("My Drawing");
    init();
    glutDisplayFunc(displayMe);
    glutMainLoop();
    return 0;
}

I've looked at this post, which seems similar, but wasn't able to find a solution.

genpfault genpfault · Accepted Answer · 2019-06-12T14:07:50

If you're going to persist with glVertex() for point plotting make sure you set up your matrix stack transforms (GL_PROJECTION/GL_MODELVIEW) so they match the glReadPixels() coordinate system:

glMatrixMode( GL_PROJECTION );
glLoadIdentity();
gluOrtho2D( 0, glutGet(GLUT_WINDOW_WIDTH), 0, glutGet(GLUT_WINDOW_HEIGHT) );
glMatrixMode( GL_MODELVIEW );
glLoadIdentity();

Or switch to glRasterPos() + glDrawPixels() for setPixel*().

Better yet, do the flood-fill logic host-side & upload the results to a GL texture for display.

Either way you're going to run into a stack overflow with that recursive solution on even fairly reasonably sized inputs so you'll probably want to switch to an explicit stack/queue:

void floodFill4( GLint aX, GLint aY, Color fillColor, Color interiorColor )
{
    typedef std::pair< GLint, GLint > Location;
    std::queue< Location > locations;

    locations.push( Location( aX, aY ) );
    while( !locations.empty() )
    {
        const Location loc = locations.front();
        locations.pop();

        GLint x = loc.first;
        GLint y = loc.second;

        Color color = getPixelColor( x, y );
        if( color.r == interiorColor.r &&
            color.g == interiorColor.g &&
            color.b == interiorColor.b )
        {
            setPixelColor( x, y, fillColor );
            locations.push( Location( x, y - 1 ) );
            locations.push( Location( x, y + 1 ) );
            locations.push( Location( x - 1, y ) );
            locations.push( Location( x + 1, y ) );
        }
    }
}

OpenGL flood fill not recognizing boundary

1 Answers