Terrain curve to array of points

Question

In my 2D game I'm using graphic tools to create nice, smooth terrain represented by black color:

Simple algorithm written in java looks for black color every 15 pixels, creating following set of lines (gray):

As you can see, there's some places that are mapped very bad, some are pretty good. In other case it would be not necessary to sample every 15 pixels, eg. if terrain is flat.

What's the best way to covert this curve to set of points [lines], using as little points as possible? Sampling every 15 pixels = 55 FPS, 10 pixels = 40 FPS

Following algorithm is doing that job, sampling from right to left, outputting pasteable into code array:

public void loadMapFile(String path) throws IOException {
    File mapFile = new File(path);
    image = ImageIO.read(mapFile);
    boolean black;
    System.out.print("{ ");

    int[] lastPoint = {0, 0};

    for (int x = image.getWidth()-1; x >= 0; x -= 15) {
        for (int y = 0; y < image.getHeight(); y++) {
            black = image.getRGB(x, y) == -16777216 ? true : false;

            if (black) {
                lastPoint[0] = x;
                lastPoint[1] = y;
                System.out.print("{" + (x) + ", " + (y) + "}, ");
                break;
            }

        }
    }

    System.out.println("}");
}

Im developing on Android, using Java and AndEngine

Answer 1

This problem is nearly identical to the problem of digitization of a signal (such as sound), where the basic law is that the signal in the input that had the frequency too high for the sampling rate will not be reflected in the digitized output. So the concern is that if you check ever 30 pixels and then test the middle as bmorris591 suggests, you might miss that 7 pixel hole between the sampling points. This suggests that if there are 10 pixel features you cannot afford to miss, you need to do scanning every 5 pixels: your sample rate should be twice the highest frequency present in the signal.

One thing that can help improve your algorithm is a better y-dimension search. Currently you are searching for the intersection between sky and terrain linearly, but a binary search should be faster

int y = image.getHeight()/2; // Start searching from the middle of the image
int yIncr = y/2;
while (yIncr>0) {
    if (image.getRGB(x, y) == -16777216) {
        // We hit the terrain, to towards the sky
        y-=yIncr;
    } else {
        // We hit the sky, go towards the terrain
        y+=yIncr;
    }
    yIncr = yIncr/2;
}
// Make sure y is on the first terrain point: move y up or down a few pixels
// Only one of the following two loops will execute, and only one or two iterations max
while (image.getRGB(x, y) != -16777216) y++; 
while (image.getRGB(x, y-1) == -16777216) y--;

Other optimizations are possible. If you know that your terrain has no cliffs, then you only need to search the window from lastY+maxDropoff to lastY-maxDropoff. Also, if your terrain can never be as tall as the entire bitmap, you don't need to search the top of the bitmap either. This should help to free some CPU cycles you can use for higher-resolution x-scanning of the terrain.

Answer 2

The most efficient solution (with respect to points required) would be to allow for variable spacing between points along the X axis. This way, a large flat part would require very few points/samples and complex terrains would use more.

In 3D mesh processing, there is a nice mesh simplification algorithm named "quadric edge collapse", which you can adapt to your problem.

Here is the idea, translated to your problem - it actually gets much simpler than the original 3D algorithm:

1. Represent your curve with way too many points.
2. For each point, measure the error (i.e. difference to the smooth terrain) if you remove it.
3. Remove the point that gives the smallest error.
4. Repeat until you have reduced the number of points far enough or errors get too large.

To be more precise regarding step 2: Given points P, Q, R, the error of Q is the difference between the approximation of your terrain by two straight lines, P->Q and Q->R, and the approximation of your terrain by just one line P->R.

Note that when a point is removed only its neighbors need an update of their error value.

Answer 3

I propose to find border points which exists on the border between white and dark pixels. After that we can digitize those points. To do that, we should define DELTA which specify which point we should skip and which we should add to result list.

DELTA = 3, Number of points = 223

DELTA = 5, Number of points = 136

DELTA = 10, Number of points = 70

Below, I have put source code, which prints image and looking for points. I hope, you will be able to read it and find a way to solve your problem.

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.awt.image.DataBufferByte;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Program {

    public static void main(String[] args) throws IOException {
        BufferedImage image = ImageIO.read(new File("/home/michal/Desktop/FkXG1.png"));
        PathFinder pathFinder = new PathFinder(10);
        List<Point> borderPoints = pathFinder.findBorderPoints(image);
        System.out.println(Arrays.toString(borderPoints.toArray()));
        System.out.println(borderPoints.size());

        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.getContentPane().add(new ImageBorderPanel(image, borderPoints));
        frame.pack();
        frame.setMinimumSize(new Dimension(image.getWidth(), image.getHeight()));
        frame.setVisible(true);
    }
}

class PathFinder {

    private int maxDelta = 3;

    public PathFinder(int delta) {
        this.maxDelta = delta;
    }

    public List<Point> findBorderPoints(BufferedImage image) {
        int width = image.getWidth();
        int[][] imageInBytes = convertTo2DWithoutUsingGetRGB(image);
        int[] borderPoints = findBorderPoints(width, imageInBytes);

        List<Integer> indexes = dwindlePoints(width, borderPoints);
        List<Point> points = new ArrayList<Point>(indexes.size());
        for (Integer index : indexes) {
            points.add(new Point(index, borderPoints[index]));
        }
        return points;
    }

    private List<Integer> dwindlePoints(int width, int[] borderPoints) {
        List<Integer> indexes = new ArrayList<Integer>(width);
        indexes.add(borderPoints[0]);
        int delta = 0;
        for (int index = 1; index < width; index++) {
            delta += Math.abs(borderPoints[index - 1] - borderPoints[index]);
            if (delta >= maxDelta) {
                indexes.add(index);
                delta = 0;
            }
        }
        return indexes;
    }

    private int[] findBorderPoints(int width, int[][] imageInBytes) {
        int[] borderPoints = new int[width];
        int black = Color.BLACK.getRGB();
        for (int y = 0; y < imageInBytes.length; y++) {
            int maxX = imageInBytes[y].length;
            for (int x = 0; x < maxX; x++) {
                int color = imageInBytes[y][x];
                if (color == black && borderPoints[x] == 0) {
                    borderPoints[x] = y;
                }
            }
        }
        return borderPoints;
    }

    private int[][] convertTo2DWithoutUsingGetRGB(BufferedImage image) {
        final byte[] pixels = ((DataBufferByte) image.getRaster().getDataBuffer()).getData();
        final int width = image.getWidth();
        final int height = image.getHeight();
        final boolean hasAlphaChannel = image.getAlphaRaster() != null;

        int[][] result = new int[height][width];
        if (hasAlphaChannel) {
            final int pixelLength = 4;
            for (int pixel = 0, row = 0, col = 0; pixel < pixels.length; pixel += pixelLength) {
                int argb = 0;
                argb += (((int) pixels[pixel] & 0xff) << 24); // alpha
                argb += ((int) pixels[pixel + 1] & 0xff); // blue
                argb += (((int) pixels[pixel + 2] & 0xff) << 8); // green
                argb += (((int) pixels[pixel + 3] & 0xff) << 16); // red
                result[row][col] = argb;
                col++;
                if (col == width) {
                    col = 0;
                    row++;
                }
            }
        } else {
            final int pixelLength = 3;
            for (int pixel = 0, row = 0, col = 0; pixel < pixels.length; pixel += pixelLength) {
                int argb = 0;
                argb += -16777216; // 255 alpha
                argb += ((int) pixels[pixel] & 0xff); // blue
                argb += (((int) pixels[pixel + 1] & 0xff) << 8); // green
                argb += (((int) pixels[pixel + 2] & 0xff) << 16); // red
                result[row][col] = argb;
                col++;
                if (col == width) {
                    col = 0;
                    row++;
                }
            }
        }

        return result;
    }
}

class ImageBorderPanel extends JPanel {

    private static final long serialVersionUID = 1L;

    private BufferedImage image;
    private List<Point> borderPoints;

    public ImageBorderPanel(BufferedImage image, List<Point> borderPoints) {
        this.image = image;
        this.borderPoints = borderPoints;
    }

    @Override
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        g.drawImage(image, 0, 0, null);

        Graphics2D graphics2d = (Graphics2D) g;

        g.setColor(Color.YELLOW);
        for (Point point : borderPoints) {
            graphics2d.fillRect(point.x, point.y, 3, 3);
        }
    }
}

In my source code I have used example from this question:

• Java - get pixel array from image