“Heat spot” image generation using bilinear interpolation

This is the code from my answer to a another CR question. My goal was to provide a fast and simple computation and I'm rather unsatisfied with it. It's maybe 10 times faster than the original, but this may be still too slow for bigger displays and/or weaker devices.

I'm mostly interested in performance improvements, including better algorithm, use of graphic cards, or whatever helps. My usual disclaimer concerning coding conventions applies.

I'm splitting the code in parts for easier review. The whole code is actually a single file. You'd need lombok and guava to run it. Alternatively, you can replace the stuff by the obvious alternatives (e.g., replace ImmutableList by ArrayList and @RequiredArgsConstructor by writing it manually) in less than five minutes.

Constants

Colors and sizes are takes from the original question, the last two constants are described in my answer.

private static final Color[] COLORS = new Color[256];
static {
    for (int i=0; i<COLORS.length; ++i) COLORS[i] = new Color(i, 0, 0);
}

private static final int WIDTH = 1280;
private static final int HEIGHT = 720;

private static final int STEP = 30;
private static final int DISTANCE_THRESHOLD = 100;

Point

/** An immutable 2D point with some additional methods. */
@RequiredArgsConstructor @Getter @ToString private static class Point {
    Point(Random random, int width, int height) {
        this(random.nextInt(width), random.nextInt(height));
    }

    public double inverseDistance(int x, int y) {
        return 1.0 / Math.sqrt(squaredDistance(x, y));
    }

    public int squaredDistance(int x, int y) {
        return square(x-this.x) + square(y-this.y);
    }

    private static int square(int a) {
        return a * a;
    }

    private final int x;
    private final int y;
}

HeatSpotter

This is the core class and the only interesting part.

```
/** A holder for the heat spots doing the temperature computation. */
private static final class HeatSpotter {

Use precomputed spot "bitmap"

The function getTemperature() is a little slow because you need to compute the inverse distance between each pixel and each nearby spot:

float getTemperature(int x, int y) {
    return bilinearInterpolation(x-xHigh, y-yHigh) +
          computeTemperature(x, y, currentSpots);
}
private float computeTemperature(int x, int y, List spots) {
    float result = 0;
    for (final Point p : spots) result += p.inverseDistance(x, y);
    return result;
}

You know that the spot must be within DISTANCE_THRESHOLD + STEP/2 pixels, because all of the currentSpots are within DISTANCE_THRESHOLD bytes from the center of the current step x step square. So what you could do is create a "spot bitmap", which is a 2-D array that holds precomputed inverse distance values, and then use that array later instead of computing inverse distances.

private static final int SPOT_SIZE = DISTANCE_THRESHOLD + STEP/2 + 1;
private final double [][] spotBitmap;

HeatSpotter(Random random, int width, int height) {
    // ...
    spotBitmap = new double[SPOT_SIZE][SPOT_SIZE];
    Point origin = new Point(0,0);
    for (int y = 0; y  spots) {
    float result = 0;
    for (final Point p : spots) {
        int dx = Math.abs(p.getX() - x);
        int dy = Math.abs(p.getY() - y);
        result += spotBitmap[dy][dx];
    }
    return result;
}

// Note: you still need the other `computeTemperature()` for doing the bilinear
// interpolation stuff.

The original code drew the screen in 230 ms on my computer. The new code does it in 195 ms, which is an 18% speed increase.
Precomputed bilinear map

I was able to do something similar with the bilinear interpolation by precomputing a binlinearMap[STEP][STEP] on each call to reset(). Here is the main piece of code:

void bilinear(float [][] bilinearMap) {
    float invStep     = 1.0f / step;
    float valRowStart = temperature00;
    float valRowEnd   = temperature10;
    float dyStart     = (temperature01 - temperature00) * invStep;
    float dyEnd       = (temperature11 - temperature10) * invStep;
    float dx          = (valRowEnd - valRowStart) * invStep;
    float ddx         = (dyEnd     - dyStart)     * invStep;

    for (int y = 0; y < step; y++) {
        float val = valRowStart;
        for (int x = 0; x < step; x++) {
            bilinearMap[y][x] = val;
            val += dx;
        }
        valRowStart += dyStart;
        dx          += ddx;
    }
}

Note that the function tries to avoid divides and multiplies, and the inner loop only contains a single add. Using this improved the speed by about 3%.
Tried to use image blitting

I tried creating a BufferedImage for a spot and then using drawImage to draw each spot onto the panel. However, there were a few things that didn't work quite right:

-
I used alpha levels so that subsequent images would overlay and add to previous images. However, the addition was not the same. In the original code, two spots with brightness 0.5 would end up creating a pixel with 1.0 (maximum) brightness. Using alpha blending, two spots with alpha levels 0.5 end up creating a pixel with 0.75 brightness. Therefore, the image as a whole turned out looking a lot different and less bright than the original.

-
Even if I found a blitting mode where the pixel levels were added together instead of alpha blended (and there probably exists such a mode), I was hitting a performance wall. Through experimentation, I found that the speed only was improved if I used small bitmaps (say 400x400 or so). But with heat spots using a 1/r brightness formula, the spots create such a wide area of effect that you can't make your bitmaps so small. For example, each spot creates a 0.001 brightness level 1000 pixels away. Given 300 spots all placed on the right edge of a 1000 pixel wide panel, this means that every pixel on left edge of the panel still has a 0.3 brightness level. So unless the formula were modified to be a 1/r^2 brightness, the bitmap needs to be very large, which causes the performance to be worse than the original code.

StackExchange Code Review Q#98085, answer score: 2