How to Floodfill a bitmap using Android Renderscript?

Question

I am trying to floodfill a bitmap using Renderscript. and my renderscript file progress.rs is

#pragma version(1)
#pragma rs java_package_name(com.intel.sample.androidbasicrs)

rs_allocation input;

int width;
int height;
int xTouchApply;
int yTouchApply;

static int same(uchar4 pixel, uchar4 in);

uchar4 __attribute__((kernel)) root(const uchar4 in, uint32_t x, uint32_t y) {


    uchar4 out = in;

    rsDebug("Process.rs : image width: ", width);
    rsDebug("Process.rs : image height: ", height);
    rsDebug("Process.rs : image pointX: ", xTouchApply);
    rsDebug("Process.rs : image pointY: ", yTouchApply);

    if(xTouchApply >= 0 && xTouchApply < width && yTouchApply >=0 && yTouchApply < height){

        // getting touched pixel
        uchar4 pixel = rsGetElementAt_uchar4(input, xTouchApply, yTouchApply);
        rsDebug("Process.rs : getting touched pixel", 0);

        // resets the pixel stack
        int topOfStackIndex = 0;

        // creating pixel stack
        int pixelStack[width*height];

        // Pushes the touched pixel onto the stack
        pixelStack[topOfStackIndex] = xTouchApply;
        pixelStack[topOfStackIndex+1] = yTouchApply;
        topOfStackIndex += 2;

        //four way stack floodfill algorithm
        while(topOfStackIndex>0){
            rsDebug("Process.rs : looping while", 0);
            // Pops a pixel from the stack
            int x = pixelStack[topOfStackIndex - 2];
            int y1 = pixelStack[topOfStackIndex - 1];
            topOfStackIndex -= 2;

            while (y1 >= 0 && same(rsGetElementAt_uchar4(input, x, y1), pixel)) {
                y1--;
            }
            y1++;

            int spanLeft = 0;
            int spanRight = 0;

            while (y1 < height && same(rsGetElementAt_uchar4(input, x, y1), pixel)) {
                rsDebug("Process.rs : pointX: ", x);
                rsDebug("Process.rs : pointY: ", y1);
                float3 outPixel = dot(f4.rgb, channelWeights);
                out = rsPackColorTo8888(outPixel);
                // conditions to traverse skipPixels to check threshold color(Similar color)
                if (!spanLeft && x > 0 && same(rsGetElementAt_uchar4(input, x - 1, y1), pixel)) {
                    // Pixel to the left must also be changed, pushes it to the stack
                    pixelStack[topOfStackIndex] = x - 1;
                    pixelStack[topOfStackIndex + 1] = y1;
                    topOfStackIndex += 2;
                    spanLeft = 1;
                } else if (spanLeft && !same(rsGetElementAt_uchar4(input, x - 1, y1), pixel)) {
                    // Pixel to the left has already been changed
                    spanLeft = 0;
                }

                // conditions to traverse skipPixels to check threshold color(Similar color)
                if (!spanRight && x < width - 1 && same(rsGetElementAt_uchar4(input, x + 1, y1), pixel)) {
                    // Pixel to the right must also be changed, pushes it to the stack
                    pixelStack[topOfStackIndex] = x + 1;
                    pixelStack[topOfStackIndex + 1] = y1;
                    topOfStackIndex += 2;
                    spanRight = 1;
                } else if (spanRight && x < width - 1 && !same(rsGetElementAt_uchar4(input, x + 1, y1), pixel)) {
                    // Pixel to the right has already been changed
                    spanRight = 0;
                }
                y1++;
            }
        }
    }

    return out;
}

static int same(uchar4 px, uchar4 inPx){
    int isSame = 0;
    if((px.r == inPx.r) && (px.g == inPx.g) && (px.b == inPx.b) && (px.a == inPx.a)) {
        isSame = 1;
        // rsDebug("Process.rs : matching pixel: ", isSame);
    } else {
        isSame = 0;
    }

    // rsDebug("Process.rs : matching pixel: ", isSame);
    return isSame;
} 

and my Activity's code is:

inputBitmap = Bitmap.createScaledBitmap(inputBitmap, displayWidth, displayHeight, false);

    // Create an allocation (which is memory abstraction in the RenderScript)
    // that corresponds to the inputBitmap.
    allocationIn = Allocation.createFromBitmap(
            rs,
            inputBitmap,
            Allocation.MipmapControl.MIPMAP_NONE,
            Allocation.USAGE_SCRIPT
    );

    allocationOut = Allocation.createTyped(rs, allocationIn.getType());

    int imageWidth = inputBitmap.getWidth();
    int imageHeight = inputBitmap.getHeight();

    script.set_width(imageWidth);
    script.set_height(imageHeight);
    script.set_input(allocationIn);
    //....
    //....

    // and my onTouchEvent Code is
    script.set_xTouchApply(xTouchApply);
    script.set_yTouchApply(yTouchApply);

    // Run the script.
    script.forEach_root(allocationIn, allocationOut);
    allocationOut.copyTo(outputBitmap);

when I touched bitmap it is showing Application not responding. It is because of root method is calling for every pixels. How can I optimize this code. And how can I compare two uchar4 variables in Renderscript? How can I improve my same method? Or How can I find similar neighbor pixels using threshold value? I got stuck. Please guys help me. I don't have much knowledge of c99 programming language and Renderscript. Can you guys debug my renderscript code. and please tell me what's wrong in this code. Or can I improve this renderscript code to floodfill the bitmap. Any help will be appreciated And sorry for my poor English ;-) . Thanks

Answer 1

Renderscript is Android's front-end to GPU-instructions. And it is extremely good if you want to perform operations on each pixel because it uses the massive GPU-parallelism-capabilities. So, you can run an operation on each pixel. For this purpose, you start a program in Renderscript with sth like "for all pixels, do the following".

The flood fill algorithm though cannot run in such a parallel environment because you only know which pixel to paint after painting another pixel before it. This is not only true for renderscript but all GPU-related libraries, like CUDA or others.