1. Software render

This series of article will describe software rendering of 2D and 3D graphic. This will help you to understand how graphic rendering works under the hood. We will try to create engine in C++ with JNI connectors for java and android.

2. Requirements

Good knowledge of java or c++

Intellij with java 7 or higher

C++ IDE, in this tutorial I will use netbeans

C++ compiler int this tutorial I will use "g++"

3. Setup environment

If your are not familiar with JNI keep the same package and artifact name, wrong naming between java class nad C++ will cause JNI native method not invoking.

Create java project

First create root folder for our three projects (c++, java, android). My root folder name is "SoftwareRender". Now open Intellij and create new project, specify project location to : SoftwareRender/JavaSoftwareRender, set following project parameter

create java class : pl.duch.articles.renderlib.NativeBitmap and insert following code :

package pl.duch.articles.renderlib;

public class NativeBitmap {

    public static final int PALETTE = 1;
    public static final int ARGB_8888 = 2;

    private final long handler;

    private final int type;
    private final int width;
    private final int height;


    private NativeBitmap(long handler, int type, int width, int height) {
        this.handler = handler;
        this.type = type;
        this.width = width;
        this.height = height;
    }

    public static NativeBitmap createArgb8888(int w, int h) {
        return new NativeBitmap(allocateBitmap(ARGB_8888, w, h), ARGB_8888, w, h);
    }

    public void free() {
        free(this.handler);
    }

    public long getHandler() {
        return handler;
    }

    public int getType() {
        return type;
    }

    public int getWidth() {
        return width;
    }

    public int getHeight() {
        return height;
    }


    private static native long allocateBitmap(int type, int w, int h);

    private static native void free(long handler);
}

We have create hidden constructor that will set memory handler, bitmap type and bitmap dimensions (width and height). To create bitmap we will use static create method that will invoke native c++ that will return memory pointer to java. This memory pointer will be used in NativeBitmap constructor. Static create method will also specify bitmap type, so for example createArgb8888(w, h) will create 32bpp bitmap with selected dimensions. Our java bitmap will only store basic information, pixel will be stored inside native code.

For now we have declared two native methods

    private static native long allocateBitmap(int type, int w, int h);
    private static native void free(long handler);

First one will allocate memory for bitmap, second one will allow us to dispose bitmap and retrieve memory. These method are static methods and all our native method will be static This method(except allocate) will use handler received from allocateBitmap to identify on with bitmap we are executing method.

To keep it OOP we have wrap method for each native method,

    public void free() {
        free(this.handler);
    }

OOP method free will use static method with handler stored inside java object.

Create C++ library

Open netbeans and create new c++ project, select dynamic library and set project location to SoftwareRender/library/softrender and project name to softrender
Open project properties and go to "C++ compiler" and set include directory to $JAVA_HOME/include $JAVA_HOME/include/darwin/ make sure you have JAVA_HOME environment variable

Open terminal/console and go to "SoftwareRender/JavaSoftwareRender/src/main/java" from this location execute :
javah -jni pl.duch.articles.renderlib.NativeBitmap

This should create file : pl_duch_articles_renderlib_NativeBitmap.h
In netbeans project create new header file with this name, and copy content from generated file to file in netbeans. This way we are sure that netbeans will see this file in project. If you just copy file netbeans project might be invalid.
You can remove pl_duch_articles_renderlib_NativeBitmap.h from "SoftwareRender/JavaSoftwareRender/src/main/java"

This file should look like this :

#include <jni.h>

#ifndef _Included_pl_duch_articles_renderlib_NativeBitmap
#define _Included_pl_duch_articles_renderlib_NativeBitmap
#ifdef __cplusplus
extern "C" {
#endif
#undef pl_duch_articles_renderlib_NativeBitmap_PALETTE
#define pl_duch_articles_renderlib_NativeBitmap_PALETTE 1L
#undef pl_duch_articles_renderlib_NativeBitmap_ARGB_8888
#define pl_duch_articles_renderlib_NativeBitmap_ARGB_8888 2L


JNIEXPORT jlong JNICALL Java_pl_duch_articles_renderlib_NativeBitmap_allocateBitmap
  (JNIEnv *, jclass, jint, jint, jint);

JNIEXPORT void JNICALL Java_pl_duch_articles_renderlib_NativeBitmap_free
  (JNIEnv *, jclass, jlong);

#ifdef __cplusplus
}
#endif
#endif

We have definitions for required method, now we need to create implementation.
Create pl_duch_articles_renderlib_NativeBitmap.cpp and insert this code :

#include <cstdlib>
#include <jni.h>
#include "pl_duch_articles_renderlib_NativeBitmap.h"


JNIEXPORT jlong JNICALL Java_pl_duch_articles_renderlib_NativeBitmap_allocateBitmap
  (JNIEnv *env, jclass clazz, jint type, jint width, jint height) {
    return 0xBAD;
}

JNIEXPORT void JNICALL Java_pl_duch_articles_renderlib_NativeBitmap_free
  (JNIEnv *env, jclass clazz, jlong handler) {

}

This will define two stubs, allocateBitmap method will always return 0xBAD as pointer. We will use this value to check if integration java with c++ works ok. Second method do nothing.

We will create actual implementations for this method later during this tutorial.

Execute "build" from netbeans, if you name project like I you should have library with name : softrender.

Where extension depend on your pc, for example valid names : softrender.so, softrender.dynlib

Integrate C++ with Java project

Open intellij project, and create class pl.duch.articles.renderlib.Main

package pl.duch.articles.renderlib;

public class Main {

    static {
        System.loadLibrary("softrender");
    }

    public static void main(String[] args) {
        NativeBitmap nativeBitmap = NativeBitmap.createArgb8888(800, 600);
        System.out.println("SUCCESS: " + (nativeBitmap.getHandler() == 0xBAD));
        nativeBitmap.free();;
    }


}

Execute main method it will fail with exception java.lang.UnsatisfiedLinkError but Intellij will create for you Run configuration, open it end set VM option "-Djava.library.path=" to location of softrender.* file, for example

-Djava.library.path=/user/dybuk87/SoftwareRender/library/softrender/dist/Debug/GNU-MacOSX

SUCCESS: true

This mean we have loaded our library, and we got 0xBAD handler after invoking createArgb8888 so we know that native method was executed and successfully return value.

Create Android project

Not available. Coming soon.

3. Image representation

Basically images are represented by array of numbers, each number describe color for each pixel.
Image with resolution ResX on ResY can be represented by array with size ResX * ResY of numbers. Number size specify how many colours we can use in image, from this point we will call it BPP(bits per pixel) .

Most common are:

For example Full HD (1920x1080) image in 32 BPP require array of 1920*1080 * 4 bytes, this is almost 8MB for one image(!)

3.1 Image memory structure

Most implementation of graphic engines store image as 1D tensor (one dimension array - vector), because image are 2D array they need to be "translate" to 1D. To translate 2D image to 1D we simply store each line one by one next to each other, this is simple example for image 4x3 pixels :

Pixel indexing is done by couple (X, Y) - (COLUMN / ROW) number, Top - left pixel index is (0,0), right - bottom (ResX-1, ResY-1).
To get pixel(x,y) position inside tensor we simply calculate x + y * ResX, y-th line require to skip "y" full rows, that is why we need to multiply y by Resolution X.

3.2 Image colour representation

We now how to store image in memory, now we need a way to transform colour number into actual colour.
Computer describe color with RGB(Red - green - blue) values, size of each field depend on total bpp.
- 16 BPP usually use 5R 6G 5B model, this is 5 bits for red, 6 bits for green, and 5 bits.
- 24 BPP use format 8R 8G 8B, each color channel have 8 bits.
- 32 BPP use format 8A 8R 8G 8B, additional 4th value is alpha or not used. This use more memory than 24 bpp but each pixel fully fit memory alignment

Colors with BPP lower or equal 8 use palette to describe colour. Palette is just an array of color definitions in 24bpp or 32bpp, number from image is used as an index to palette. Simple example for 3BPP image :

Palette define four colours: Black (index: 0), Red (index: 1), Green(index: 2), White(index: 3) as 24 bpp :

Lets define image as :

This is memory representation for simple image, to get actual color to render we need to use palette

4. Image implementation

Lets define our image class as follow :

class Image {
public:
    Image(int resX, int resY, int bpp);

    void setColor(int x, int y, uint32 col);

    uint32 getColor(int x, int y);

    void dump(int withPal);

private:
    int bpp;
    int resX;
    int resY;

    int palSize;

    unique_ptr<byte[]> data;
    unique_ptr<byte[]> palette;
};

We have Constructor that allocate memory to handle bitmap resX on resY with desired bpp. This basic class will support bpp = { 2, 4, 8, 16, 24, 32 }
setColor / getColor will allow to set/get pixel(x,y)
dump will "print" image to standard output, withPal parameter is used for bitmap withPal (bpp <= 8), when set to true it will translate colors by palette.

lets have, a look on each method:

Image::Image(int resX, int resY, int bpp) {
    this->resX = resX;
    this->resY = resY;
    this->bpp = bpp;

    int totalSize = 1 + (resX * resY * bpp) / 8 ;
    this->palSize = bpp > 8 ? 0 : (1 << bpp);

    this->data.reset(new byte[totalSize]);

    if (this->palSize > 1) {
        palette.reset(new byte[this->palSize * 4]);

        for(int i=0; i<this->palSize; i++) {
           palette[i * 4 + 0] = 255 * i / (this->palSize - 1);
           palette[i * 4 + 1] = 255 * i / (this->palSize - 1);
           palette[i * 4 + 2] = 255 * i / (this->palSize - 1);
           palette[i * 4 + 3] = 255;
        }
    }
}

First we save bitmap parameters, we will need them later to access data.
Next we have to calculate required memory (totalSize) and allocate array to store that data
Third step is to create palette for bitmap with bpp <= 8, color count is simply calculated with 2^bpp. Palette is initialized to grayscale where 0 is black and (palSize-1) color is set to white.

Now we need to have a way to access pixel, for every bitmap type index is calculated by formula index = x + y * ResX
This index need to be translated to actual byte index, this conversion depend on bpp, since we will support bpp = { 2, 4, 8, 16, 24, 32 } we will split support for two types:
a) Bpp that share bytes (more than one pixel in byte) - bpp = { 2, 4 }
b) Pixel use full bytes bpp = { 8, 16, 24, 32 }
c) We will not support weird types like bpp = { 3, 5, 7, ... } this types will require special handling

Ad a.

Bpp = 2 or 4 will fit more than one pixel inside byte, to calculate pixel count in one byte we can simply divide 8 by bpp

pixInByteCount = 8 / 2 => 4;
pixInByteCount = 8 / 4 => 2;

To get pixel byte offset we will simply divide index by picInByteCount
byteNo = index / pixInByteCount = index / (8 / bpp) = index * bpp / 8;

We now with byte to use now we have to find out pixel position inside this byte, to get that value we will use previous formula, but insted of divide by 8 we will do modul 8 operation. Value % 8 can bi simplify to (value & 7).
int offsetInByte = (index * bpp) & 7;

Now we know exact position(byte and bit index) of pixel data, last step is to compute bit mask. Bit mask is used to extract only bpp bits from source byte. To do that we will use logic and operation with all interesting bits set to 1. Example, we will extract only bits from 2 to 5:

To create mask for BPP bits we will simply compute max 2^bpp - 1
a) 2 BPP => 2² - 1 => 3 => 11b
b) 4 BPP => 2⁴ - 1 => 15 => 1111b

Finally we can create code for get color when bpp < 8

    int index = (x + y * resX);             // pixel index

    int byteNo = index * bpp / 8;           // pixel index to byte index
    int offsetInByte = (index * bpp) & 7;   // get bit offset in byte
    int mask = (1<<bpp) - 1;                // calculate mask

    byte val = data[byteNo];                // read byte

    val >>= offsetInByte;                   // shift bytes to right, after this operation our pixel will be in bit range 0..Bpp-1
    val &= mask;                            // apply mask

    return val;                             // return value

Ad b.

Bpp >= 8 will fit more than one byte, but since we only use BPP = { 8, 16, 24, 32 } they will be aligned to byte so no need to work on bit mask, all we have to do is compute byte position and copy required amount of bytes.
ByteNo is calculated in the same way as for Bpp < 8:
byteNo = index * bpp / 8;

to get byte sie for each bpp we simply divide bpp by 8 a) 8 BPP / 8 = 1 byte b) 16 BPP / 8 = 2 byte c) 24 BPP / 8 = 3 byte d) 32 BPP / 8 = 4 byte

Code for BPP >= 8:

    int col;                                     // this is our output
    int byteNo = index * bpp / 8;                // calculate byte index
    memcpy(&col, data.get() + byteNo, bpp/8);    // copy bpp/8 bytes memory from &data[byteNo] to col

    return col;                                  // return value