May 7th, 2012

Android NDK, using JNI bitmap processing – comparing Java to C using flood fill algorithm

Android C Cloud Doodle Flood fill JNI NDK

Categories

Android NDK, using JNI bitmap processing – comparing Java to C using flood fill algorithm

There are times when you need to use the Java Native Interface (JNI) when developing Android applications. One example that is often used is bitmap processing. You pass your bitmap to your C/C++ code with a Java native method and you do some work on the pixels in the bitmap. Here is an example of bitmap processing that we did on recent project.

Before you start you should download and install Android NDK

We wanted to implement flood fill algorithm in a drawing application. We started with a Java implementations.

public static RectFS floodFillScanLineQueue(int[] pixels,int w, int h, Point pt, int targetColor, int fillColor){

        if(targetColor == fillColor) return null;

        Queue<point> q = new LinkedList<point>();

        q.add(pt);
        int top = pt.y,bottom=pt.y,left=pt.x,right=pt.x;
        int y1;
        boolean spanLeft, spanRight;
        Point p;
        boolean fullScreen = true;

        while( q.size() > 0)
        {
            p = q.poll();
            y1 =p.y;

            while(y1 >= 0 && pixels[y1*w+p.x] == targetColor) y1--;
            y1++;
            spanLeft = spanRight = false;
            while(y1 < h && pixels[y1*w+p.x] == targetColor )
            {
                pixels[y1*w+p.x]=fillColor;
                if(top > y1) top = y1;
                if(bottom < y1) bottom = y1;
                if(left > p.x) left = p.x;
                if(right < p.x) right = p.x;
                if(!spanLeft && p.x > 0 && pixels[y1*w+(p.x-1)] == targetColor)
                {
                    q.add(new Point(p.x - 1, y1));
                    spanLeft = true;
                }
                else if(spanLeft && p.x > 0 &&  pixels[y1*w+(p.x-1)] != targetColor)
                {
                    spanLeft = false;
                    fullScreen = false;
                }
                if(!spanRight && p.x < w - 1 && pixels[y1*w+(p.x+1)] == targetColor)
                {
                    q.add(new Point(p.x + 1, y1));
                    spanRight = true;
                }
                else if(spanRight && p.x < w - 1 && pixels[y1*w+(p.x+1)] != targetColor)
                {
                    spanRight = false;
                    fullScreen = false;
                }
                y1++;
            }
        }

        return new RectFS(new Rect(left,top,right,bottom),fullScreen);
    }

The performance was good but not great. We wanted our app to be as responsive as we could make it. We then decide to try out JNI. Our first step was to take the above method and implement the way it is in C.

JNIEXPORT jobject JNICALL Java_com_golysoft_view_DrawThread_floodFillScanLineQueue(JNIEnv * env, jobject  obj,jintArray pixels,jint w, jint h, jobject pt, jint targetColor, jint fillColor)
{
     if(targetColor == fillColor) return NULL;
     jint *pixelPtr;

     jboolean spanLeft = JNI_FALSE, spanRight = JNI_FALSE;
     jboolean fullScreen = JNI_TRUE;


     pixelPtr = (*env)->GetIntArrayElements(env, pixels, NULL);
     if (pixelPtr == NULL) {
         return NULL;
     }

     jclass listClass = (*env)->FindClass(env, "java/util/LinkedList");

     jmethodID listConstructor =  (*env)->GetMethodID(env, listClass, "<init>", "()V");
     jmethodID addObj = (*env)->GetMethodID(env, listClass, "add", "(Ljava/lang/Object;)Z");
     jmethodID sizeMethod = (*env)->GetMethodID(env, listClass, "size", "()I");
     jmethodID pollMethod = (*env)->GetMethodID(env, listClass, "poll", "()Ljava/lang/Object;");

     jobject listObj = (*env)->NewObject(env, listClass, listConstructor);
     (*env)->CallBooleanMethod(env, listObj, addObj, pt);

     jclass pointClass = (*env)->FindClass(env, "android/graphics/Point");
     jmethodID pointInitWithData = (*env)->GetMethodID(env,pointClass,"<init>","(II)V");

     jfieldID pointX = (*env)->GetFieldID(env,pointClass,"x","I");
     jfieldID pointY = (*env)->GetFieldID(env,pointClass,"y","I");

     jint ptx = (*env)->GetIntField(env,pt,pointX);
     jint pty = (*env)->GetIntField(env,pt,pointY);

     jint top = pty, bottom=pty, left=ptx, right=ptx;

     while( (*env)->CallIntMethod(env,listObj,sizeMethod) > 0)
     {
            jobject pointObj = (*env)->CallObjectMethod(env,listObj,pollMethod);

            jint py = (*env)->GetIntField(env,pointObj,pointY);
            jint px = (*env)->GetIntField(env,pointObj,pointX);

            while(py >= 0 && pixelPtr[py*w+px] == targetColor) py--;
            py++;
            spanLeft = spanRight = JNI_FALSE;

            while(py < h && pixelPtr[py*w+px] == targetColor )
            {
                pixelPtr[py*w+px]=fillColor;

                if(top > py) top = py;
                if(bottom < py) bottom = py;
                if(left > px) left = px;
                if(right < px) right = px;

                if(spanLeft == JNI_FALSE  && px > 0 && pixelPtr[py*w+(px-1)] == targetColor)
                {
                    //Create new point add it to queue
                    jobject point = (*env)->NewObject(env,pointClass,pointInitWithData,(px-1),py);
                    (*env)->CallBooleanMethod(env, listObj, addObj, point);
                    (*env)->DeleteLocalRef(env,point);

                    spanLeft = JNI_TRUE;
                }
                else if(spanLeft == JNI_TRUE && px > 0 &&  pixelPtr[py*w+(px-1)] != targetColor)
                {
                    spanLeft = JNI_FALSE;
                    fullScreen = JNI_FALSE;
                }

                if(spanRight == JNI_FALSE  && px < w - 1 && pixelPtr[py*w+(px+1)] == targetColor)
                {
                    //Create new point add it to queue
                    jobject point = (*env)->NewObject(env,pointClass,pointInitWithData,(px+1),py);
                    (*env)->CallBooleanMethod(env, listObj, addObj, point);
                    (*env)->DeleteLocalRef(env,point);

                    spanRight = JNI_TRUE;
                }
                else if(spanRight == JNI_TRUE && px < w - 1 && pixelPtr[py*w+(px+1)] != targetColor)
                {
                    spanRight = JNI_FALSE;
                    fullScreen = JNI_FALSE;
                }
                py++;
            }


            (*env)->DeleteLocalRef(env,pointObj);
      }


        (*env)->ReleaseIntArrayElements(env, pixels, pixelPtr, 0);

        jclass rectClass = (*env)->FindClass(env, "android/graphics/Rect");
        jclass rectFSClass = (*env)->FindClass(env, "com/golysoft/util/dto/RectFS");

        jmethodID rectInit = (*env)->GetMethodID(env,rectClass,"<init>","(IIII)V");
        jmethodID rectFSInit = (*env)->GetMethodID(env,rectFSClass,"<init>","(Landroid/graphics/Rect;Z)V");

        jobject boundingRect = (*env)->NewObject(env,rectClass,rectInit,left,top,right,bottom);

        jobject rectFS = (*env)->NewObject(env,rectFSClass,rectFSInit,boundingRect,JNI_TRUE);

        return rectFS;
}

The performance was little bit better but now it was time to really optimize it. This first attempt was not really using C. It was using C to make calls to the JVM to find and use the Java classes. We decide to change most of the calls to Java classes to true C code. Here is the code after little bit of re-write.

void floodFillScanLineQueue(AndroidBitmapInfo* info,void* pixels,jshort x,jshort y,uint16_t targetColor,uint16_t fillColor){

   char spanLeft = 0, spanRight = 0;
   int16_t py,px;

   struct entry *item;

   SLIST_INIT(&head); //initialize queue

   //Add the initial point to the queue
   item = malloc(sizeof(struct entry));
   item->x = x;
   item->y = y;
   SLIST_INSERT_HEAD(&head, item, entries);

   while (!SLIST_EMPTY(&head)) {

        item = SLIST_FIRST(&head); //get the first element from the queue
        SLIST_REMOVE_HEAD(&head, entries); //remove the element from the queue

        //Get the point from the element
        py = item->y;
        px = item->x;

        free(item); //element not needed free it

        while(py >= 0 && getPixel(pixels,info,px,py) == targetColor) py--;

        py++;
        spanLeft = spanRight = 0;

        while(py < info->height && getPixel(pixels,info,px,py) == targetColor )
        {
            setPixel(pixels,info,px,py,fillColor);
           
            if(!spanLeft && px > 0 && getPixel(pixels,info,px-1,py) == targetColor)
            {
                //Create new point add it to queue
                item = malloc(sizeof(struct entry));
                item->x = px-1;
                item->y = py;
                SLIST_INSERT_HEAD(&head, item, entries);

                spanLeft = 1;
            }
            else if(spanLeft && px > 0 &&  getPixel(pixels,info,px-1,py) != targetColor)
            {
                spanLeft = 0;
            }

            if(!spanRight && px < info->width - 1 && getPixel(pixels,info,px+1,py) == targetColor)
            {
                //Create new point add it to queue
                item = malloc(sizeof(struct entry));
                item->x = px +1;
                item->y = py;
                SLIST_INSERT_HEAD(&head, item, entries);

                spanRight = 1;
            }
            else if(spanRight && px < info->width - 1 && getPixel(pixels,info,px+1,py) != targetColor)
            {
                spanRight = 0;
            }
            py++;
        }
   }
}

This new implementation was using C list and was accessing the pointer to pixel array created by the method from the Bitmap.h, AndroidBitmap_lockPixels(env, bitmap, &pixels)) method. The previous two version were processing pixel array that was passed in from the Java layer. In the third implementation we decide to do all the processing on the bitmap in the C layer. Here is the standard template you would follow to process bitmaps in C.

   AndroidBitmapInfo info;
   void* pixels;
   int ret;

   if ((ret = AndroidBitmap_getInfo(env, bitmap, &info)) < 0) {
        LOGE("AndroidBitmap_getInfo() failed ! error=%d", ret);
        return;
   }

   if ((ret = AndroidBitmap_lockPixels(env, bitmap, &pixels)) < 0) {
        LOGE("AndroidBitmap_lockPixels() failed ! error=%d", ret);
        return;
   }


   //PROCESS YOUR PIXELS HERE

   AndroidBitmap_unlockPixels(env, bitmap);

You would never want to use JNI for your day to day Android development, but you do have to use it once in a while. I hope this step by step will help you with you JNI development on the Android platform. The final flood fill implementation after load testing morphed into a bit different implementation. We had to optimize and restructure the code event more to handle the very low heap that is on the Android platform.

0 0 votes

Article Rating