Introduction

I am trying to implement the flood fill algorithm manually in my Qt Computer Graphics Project. I have used simple BFS algorithm to implement flood fill.

Problem

• The simple BFS version of flood fill is taking a long time.
• Why am I not getting any significant advantage of parallelizing the for loop

My Approaches

• Initially I was using recursive DFS, then I switched to iterative BFS.
• Moved the plotPoint function outside, I stored all the points to be colored in a pre allocated QVector but that didn’t help either.
• I thought parallelizing the plotPoint function will help but it didn’t help either, although I am not really sure if I have used openmp correctly.

My flood fill routines are as follows:

void MainWindow::iterativeFloodFill(int x, int y, QVector<QPoint> &interior)
{
    std::queue<QPoint> q;
    q.push(QPoint(x, y));

    int xdir[] = {0, -1, 1, 0};
    int ydir[] = {-1, 0, 0, 1};

    while (!q.empty())
    {
        QPoint p = q.front();
        q.pop();

        if (visited.contains(p) || pts.contains(p))
            continue;

        interior.push_back(QPoint(p.x(), p.y()));
        visited.insert(p);

        for (int i = 0; i < 4; ++i)
        {
            QPoint neighbor = QPoint(p.x() + xdir[i], p.y() + ydir[i]);
            if (!visited.contains(neighbor) && !pts.contains(neighbor))
            {
                q.push(neighbor);
            }
        }
    }
}


void MainWindow::on_floodfill_clicked()
{
    if (polygonPoints.size() == 0) return;
    QPoint seed = polygonPoints[0];
    QVector<QPoint> interior_points;
    interior_points.reserve(1011);
    polygonPoints.clear();
    iterativeFloodFill(seed.x(), seed.y(), interior_points);
    #pragma omp parallel for
    for(int i = 0; i<interior_points.size(); i++)
    {
        #pragma omp critical
        plotPoint(interior_points[i], QColor(10,20,30));
    }
}
void MainWindow::plotPoint(int x, int y, int r, int g, int b)
{

    pts[QPoint(x, y)] =  QColor(r,g,b) ;
    int gridOffset = (ui->gridOffset->value()==0)?1:ui->gridOffset->value();
    int width = ui->workArea->width();
    int height = ui->workArea->height();
    int centerX=width/2;
    int centerY=height/2;
    int calcX = centerX+ x*gridOffset + gridOffset/2;
    int calcY = centerY -  y*gridOffset - gridOffset/2;
    colorPoint(calcX, calcY, r,g,b, gridOffset);
}
void MainWindow::plotPoint(QPoint pt, QColor col)
{
    plotPoint(pt.x(), pt.y(), col.red(), col.green(), col.blue());
}
void MainWindow::colorPoint(int x, int y, int r, int g, int b, int penwidth=1) {

    QPixmap canvas=ui->workArea->pixmap();
    QPainter painter(&canvas);
    QPen pen=QPen(QColor(r,g,b),penwidth);
    painter.setPen(pen);
    painter.drawPoint(x, y);

    ui->workArea->setPixmap(canvas);
}

Brief explanation of what each function does

• plotPoint This function accepts (x, y) in my coordinate system where origin is in the center of pixmap and maps it to the pixmap’s coordinate system. Then calls colorPoint routine on those points to color the appropriate pixel.
• colorPoint Simply colors the point it has accepted in the parameter.
• visited and pts are QSet and QHash respectively.