Tinting pixels in Java - Need a faster method

Question

I'm making a doom style pseudo-3D game. The world is rendered pixel by pixel into a buffered image, which is later displayed on the JPanel. I want to keep this approach so that lighting individual pixels will be easier.

I want to be able to color the textures in the game to many different colors. Coloring the whole texture and storing it in a separate buffered image takes too much time and memory for my purpose. So I am tinting each pixel of the texture during the rendering stage.

The problem I am having is that tinting each pixel is quite expensive. When an uncolored wall covers the entire screen, I get around 65 fps. And when a colored wall covers the screen, I get 30 fps.

This is my function for tinting the pixels:

//Change the color of the pixel using its brightness.
public static int tintABGRPixel(int pixelColor, Color tintColor) {
    //Calculate the luminance. The decimal values are pre-determined.
    double lum = ((pixelColor>>16 & 0xff) * 0.2126 +
                 (pixelColor>>8 & 0xff) * 0.7152 +
                 (pixelColor & 0xff) * 0.0722) / 255;

    //Calculate the new tinted color of the pixel and return it.
    return ((pixelColor>>24 & 0xff) << 24) |
           ((int)(tintColor.getBlue()*lum) & 0xff) |
           (((int)(tintColor.getGreen()*lum) & 0xff) << 8) |
           (((int)(tintColor.getRed()*lum) & 0xff) << 16);
}

Sorry for the illegible code. This function calculates the brightness of the original pixel, multiplies the new color by the brightness, and converts it back into an int.

It only contains simple operations, but this function is called up to a million times per frame in the worst case. The bottleneck is the calculation in the return statement.

Is there a more efficient way to calculate the new color? Would it be best if I changed my approach?

Thanks

Answer 1

Do the work in Parallel

Threads aren't necessarily the only way to parallelise code, CPUs often have instructions sets such as SIMD which allow you to compute the same arithmetic on multiple numbers at once. GPUs take this idea and run with it, allowing you to run the same function on hundreds to thousands of numbers in parallel. I don't know how to do this in Java, but I'm sure with some googling its possible to find an method that works.

Algorithm - Do less work

Is it possible to reduce the amount of time the function needs to be called? Calling any function a million times per frame is going to hurt. Unless the overhead of each function call is managed (inlining it, reusing the stack frame, caching the result if possible), you'll want to do less work.

Possible options could be:

• Make the window/resolution of the game smaller.
• Work with a different representation. Are you doing a lot of operations that are easier to do when pixels are HSV instead of RGB? Then only convert to RGB when you are about to render the pixel.
• Use a limited number of colours for each pixel. That way you can work out the possible tints in advance, so they are only a lookup away, as opposed to a function call.
• Tint as little as possible. Maybe there is some UI that is tinted and shouldn't be. Maybe lighting effects only travel so far.
• As a last resort, make tinted the default. If tinting pixels is done so much then possibly "untinting" happens far less and you can get better performance by doing that.

Performance - (Micro-)optimising the code

If you can settle for an "approximate tint" this SO answer gives an approximation for the brightness (lum) of a pixel that should be cheaper to compute. (The formula from the link is Y = 0.33 R + 0.5 G + 0.16 B, which can be written Y = (R+R+B+G+G+G)/6.

The next step is to time your code (profile is a good term to know for googling) to see what takes up the most resources. It may well be that it isn't this function here, but another piece of code. Or waiting for textures to load.

From this point on we will assume the function provided in the question takes up the most time. Let's see what it is spending its time on. I don't have the rest of your code, so I can't benchmark all of it, but I can compile it and look at the bytecode that is produced. Using javap on a class containing the function I get the following (bytecode has been cut where there are repeats).

public static int tintABGRPixel(int, Color);
    Code:
       0: iload_0
       1: bipush        16
       3: ishr
       4: sipush        255
       7: iand
       8: i2d
       9: ldc2_w        #2                  // double 0.2126d
      12: dmul
      13: iload_0
      ...
      37: dadd
      38: ldc2_w        #8                  // double 255.0d
      41: ddiv
      42: dstore_2
      43: iload_0
      44: bipush        24
      46: ishr
      47: sipush        255
      50: iand
      51: bipush        24
      53: ishl
      54: aload_1
      55: pop
      56: invokestatic  #10                 // Method Color.getBlue:()I
      59: i2d
      60: dload_2
      61: dmul
      62: d2i
      63: sipush        255
      66: iand
      67: ior
      68: aload_1
      69: pop
      ...
      102: ireturn

This can look scary at first, but Java bytecode is nice, in that you can match each line (or instruction) to a point in your function. It hasn't done anything crazy like rewrite it or vectorize it or anything that makes it unrecognizable.

The general method to see if a change has made an improvement, is to measure the code before and after. With that knowledge you can decide if a change is worth keeping. Once the performance is good enough, stop.

Our poor man profiling is to look at each instruction, and see (on average, according to online sources) how expensive it is. This is a little naive, as how long each instruction takes to execute can depend on a multitude of things such as the hardware it is running on, the versions of software on the computer, and the instructions around it.

I don't have a comprehensive list of the time cost for each instruction, so I'm going to go with some heuristics.

• integer operations are faster than floating operations.
• constants are faster than local memory, which is faster than global memory.
• powers of two can allow for powerful optimisations.

I stared at the bytecode for a while, and all I noticed was that from lines [8 - 42] there are a lot of floating point operations. This section of code works out lum (the brightness). Other than that, nothing else stands out, so let's rewrite the code with our first heuristic in mind. If you don't care for the explanation, I'll provide the final code at the end.

Let us just consider what the blue colour value (which we will label B) will be by the end of the function. The changes will apply to red and green too, but we will leave them out for brevity.

double lum = ((pixelColor>>16 & 0xff) * 0.2126 +
             (pixelColor>>8 & 0xff) * 0.7152 +
             (pixelColor & 0xff) * 0.0722) / 255;
...
... | ((int)(tintColor.getBlue()*lum) & 0xff) | ...

This can be rewritten as

int x = (pixelColor>>16 & 0xff), y = (pixelColor>>8 & 0xff), z = (pixelColor & 0xff);
double a = 0.2126, b = 0.7152, c = 0.0722;
double lum = (a*x + b*y + c*z) / 255;
int B = (int)(tintColor.getBlue()*lum) & 0xff;

We don't want to be doing as many floating point operations, so let us do some refactoring. The idea is that the floating point constants can be written as fractions. For example, 0.2126 can be written as 2126/10000.

int x = (pixelColor>>16 & 0xff), y = (pixelColor>>8 & 0xff), z = (pixelColor & 0xff);
int a = 2126, b = 7152, c = 722;
int top = a*x + b*y + c*z;
double temp = (double)(tintColor.getBlue() * top) / 10000 / 255;
int B = (int)temp & 0xff;

So now we do three integer multiplications (imul) instead of three dmuls. The cost is one extra floating division, which alone would probably not be worth it. We can avoid this issue by piggybacking on the other division that we are already doing. Combining the two sequential divisions into one division is as simple as changing / 10000 / 255 to /2550000. We can also setup the code for one more optimization by moving the casting and division to one line.

int x = (pixelColor>>16 & 0xff), y = (pixelColor>>8 & 0xff), z = (pixelColor & 0xff);
int a = 2126, b = 7152, c = 722;
int top = a*x + b*y + c*z);
int temp = (int)((double)(tintColor.getBlue()*top) / 2550000);
int B = temp & 0xff;

This could be a good place to stop. However, if you need to squeeze a tiny bit more performance out of this function, we can optimise dividing by a constant and casting a double to an int (which I believe are two expensive operations) to a multiply (by a long) and a shift.

int x = (pixelColor>>16 & 0xff), y = (pixelColor>>8 & 0xff), z = (pixelColor & 0xff);
int a = 2126, b = 7152, c = 722;
int top = a*x + b*y + c*z;
int Btemp = (int)((tintColor.getBlue() * top * 1766117501L) >> 52);
int B = temp & 0xff;

where the magic numbers are two that were magicked up when I compiled a c++ version of the code with clang. I am not able to explain how to produce this magic, but it works as far as I have tested with a couple of values for x, y, z, and tintColor.getBlue(). When testing I assumed all the values are in the range [0 - 256), and I tried only a couple of examples.

The final code is below. Be warned that this is not well tested and may have edge cases that I've missed, so let me know if there are any bugs. Hopefully it is fast enough.

public static int tintABGRPixel(int pixelColor, Color tintColor) {
    // Calculate the luminance. The decimal values are pre-determined.
    int x = pixelColor>>16 & 0xff, y = pixelColor>>8 & 0xff, z = pixelColor & 0xff;
    int top = 2126*x + 7252*y + 722*z;
    int Btemp = (int)((tintColor.getBlue() * top * 1766117501L) >> 52);
    int Gtemp = (int)((tintColor.getGreen() * top * 1766117501L) >> 52);
    int Rtemp = (int)((tintColor.getRed() * top * 1766117501L) >> 52);

    //Calculate the new tinted color of the pixel and return it.
    return ((pixelColor>>24 & 0xff) << 24) | Btemp & 0xff | (Gtemp & 0xff) << 8 | (Rtemp & 0xff) << 16;
}

EDIT: Alex found that the magic number should be 1755488566L instead of 1766117501L.

Answer 2

To get better performance you'll have to get rid of objects like Color during image manipulation, also if you know that a method is to be called million times (image.width * image.height times) then it's best to inline this method. In general JVM would probably inline this method itself, but you should not take the risk.

You can use PixelGrabber to get all the pixels into an array. Here's a general usage

final int[] pixels = new int[width * height];
final PixelGrabber pixelgrabber = new PixelGrabber(image, 0, 0, width, height, pixels, 0, 0);

for(int i = 0; i < height; i++) {
    for(int j = 0; j < width; j++) {
        int p = pixels[i * width + j]; // same as image.getRGB(j, i);

        int alpha = ( ( p >> 24) & 0xff );
        int red = ( ( p >> 16) & 0xff );
        int green = ( ( p >> 8) & 0xff );
        int blue = ( p  & 0xff );

        //do something i.e. apply luminance
    }
}

Above is just an example of how to iterate row and column indexes, however in your case nested loop is not needed. This should reasonably improve the performance.

This can probably be parallelized also using Java 8 streams easily, however be careful before using streams while dealing with images, as streams are a lot slower than plain old loops.

You can also try replacing int with byte where applicable (i.e. individual color components don't need to be stored in int). Basically try using primitive datatypes and even in primitive datatypes use smallest that's applicable.

Answer 3

At this point you are really close to the metal on this calculation. I think you'll have to change your approach to really improve things, but a quick idea is to cache the lum calculation. That is a simple function of pixel color and your lum isn't dependent on anything but that. If you cache that it could save you a lot of calcs. While you're caching you could cache this calc too:

((pixelColor>>24 & 0xff) << 24)

I don't know if that'll save you a ton of time, but I think at this point that is just about all you could do from a micro-optimization stand point.

Now you could refactor your pixel loop to use parallelism, and do those pixel calcs in parallel on your CPU this might set you up for the next idea too.

If neither of those above ideas work I think you might need to try and push color calculations off to the GPU card. This is all bare metal math that has to happen millions of times which is what graphics cards do best. Unfortunately this is a deep topic with lots of education that has to happen in order to pick the best option. Here were some interesting things to research:

• https://code.google.com/archive/p/java-gpu/
• https://github.com/nativelibs4java/JavaCL
• http://jogamp.org/jogl/www/
• https://www.lwjgl.org/

I know some of those are huge frameworks which isn't what you asked for. But they might contain other relatively unknown libs that you could use to push these math calcs off to the GPU. The @Parrallel annotation looked like it could be the most useful or JavaCL bindings.