“Heat spot” image generation using bilinear interpolation

Question

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 {
    private final ImmutableList<Point> spots;

    // The coordinates of the top-left corner.
    private int xHigh;
    private int yHigh;
    private int step;
    private final List<Point> currentSpots = Lists.newArrayList();

    // The temperatures in the four corners. The suffixes are (scaled) coordinates.
    private float temperature00;
    private float temperature01;
    private float temperature10;
    private float temperature11;

    HeatSpotter(Random random, int width, int height) {
        final ImmutableList.Builder<Point> spots = ImmutableList.builder();
        final int count = WIDTH * HEIGHT / 5000;
        for (int i=0; i<count; ++i) spots.add(new Point(random, WIDTH, HEIGHT));
        this.spots = spots.build();
    }

    public void reset(int x, int y, int step) {
        xHigh = x;
        yHigh = y;
        this.step = step;
        currentSpots.clear();
        final List<Point> otherSpots = Lists.newArrayList();
        final int halfStep = step / 2;
        final int squaredThreshold = DISTANCE_THRESHOLD * DISTANCE_THRESHOLD;
        for (final Point p : spots) {
            if (p.squaredDistance(x+halfStep, y+halfStep) < squaredThreshold) {
                currentSpots.add(p);
            } else {
                otherSpots.add(p);
            }
        }
        temperature00 = computeTemperature(x + 0*step, y + 0*step, otherSpots);
        temperature01 = computeTemperature(x + 0*step, y + 1*step, otherSpots);
        temperature10 = computeTemperature(x + 1*step, y + 0*step, otherSpots);
        temperature11 = computeTemperature(x + 1*step, y + 1*step, otherSpots);
    }

    float getTemperature(int x, int y) {
        return bilinearInterpolation(x-xHigh, y-yHigh) + computeTemperature(x, y, currentSpots);
    }

    /**
     * Interpolate according to https://en.wikipedia.org/wiki/Bilinear_interpolation#Algorithm
     *
     * @param xLow The difference between the current {@code x} coordinate and {@link xHigh}.
     * @param yLow The difference between the current {@code y} coordinate and {@link yHigh}.
     * @return The interpolated temperature contribution by the spots not contained in {@link #currentSpots}.
     */
    float bilinearInterpolation(int xLow, int yLow) {
        float result = 0;
        result += (step-xLow) * (step-yLow) * temperature00;
        result += (step-xLow) * yLow * temperature01;
        result += xLow * (step-yLow) * temperature10;
        result += xLow * yLow * temperature11;
        result /= step * step;
        return result;
    }

    private float computeTemperature(int x, int y, List<Point> spots) {
        float result = 0;
        for (final Point p : spots) result += p.inverseDistance(x, y);
        return result;
    }
}

MyPanel

/** A trivial class used as canvas for the spots. */
private static class MyPanel extends JPanel {
    public MyPanel(Random random, int width, int height) {
        setPreferredSize(new Dimension(width, height));
        heatSpotter = new HeatSpotter(random, width, height);
    }

    @Override protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        final int width = getWidth();
        final int height = getHeight();
        for (int xHigh=0; xHigh<width; xHigh+=STEP) {
            for (int yHigh=0; yHigh<height; yHigh+=STEP) {
                heatSpotter.reset(xHigh, yHigh, STEP);
                for (int xLow=0; xLow<STEP; ++xLow) {
                    final int x = xHigh + xLow;
                    for (int yLow=0; yLow<STEP; ++yLow) {
                        final int y = yHigh + yLow;
                        g.setColor(color(x, y));
                        g.fillRect(x, y, 1, 1);
                    }
                }
            }
        }
    }

    private Color color(int x, int y) {
        int temperature = (int) (COLORS.length * heatSpotter.getTemperature(x, y));
        if (temperature >= COLORS.length) temperature = COLORS.length-1;
        if (temperature < 0) temperature = 0;
        return COLORS[temperature];
    }

    @NonNull private final HeatSpotter heatSpotter;
}

main

public static void main(String[] args) {
    final JFrame frame = new JFrame("HeatSpot");
    frame.add(new MyPanel(new Random(), WIDTH, HEIGHT));
    frame.pack();
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setLocationRelativeTo(null);
    frame.setVisible(true);
}

Answer 1

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<Point> 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 < SPOT_SIZE; y++) {
        for (int x = 0; x < SPOT_SIZE; x++) {
            spotBitmap[y][x] = origin.inverseDistance(x, y);
        }
    }
}

float getTemperature(int x, int y) {
    return bilinearInterpolation(x-xHigh, y-yHigh) +
            computeTemperatureFast(x, y, currentSpots);
}

private float computeTemperatureFast(int x, int y, List<Point> 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:

1. 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.

2. 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.