Terrain curve to an array of points

Question

In my 2D game, I use graphic tools to create a nice smooth terrain represented in black:

A simple algorithm written in java looks black every 15 pixels, creating the following set of lines (gray):

As you can see, some places that are displayed very poorly, some of them are pretty good. Otherwise, there is no need to try every 15 pixels, for example. if the landscape is flat.

What is the best way to hide this curve to a set of points [lines] using as few points as possible? Sampling every 15 pixels = 55 FPS, 10 pixels = 40 FPS

The following algorithm performs this task, sampling from right to left, which displays the code inserted into the 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 almost identical to the problem of digitizing a signal (for example, sound), where the basic law is that a signal at an input that has a frequency too high for the sampling frequency will not be reflected in the digitized form. So the problem is that if you check 30 pixels and then check the middle, as bmorris591 suggests, you can skip this 7-pixel hole between the sampling points. This suggests that if there are 10 pixel functions that you cannot miss, you need to do a scan every 5 pixels: your sampling rate should be twice the highest frequency present in the signal.

One thing that can help improve your algorithm is a better search by size y. You are currently looking for a linear intersection of sky and terrain, but 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 area does not have rocks, you only need to look for a window from lastY + maxDropoff to lastY-maxDropoff. Also, if your landscape can never be as tall as the entire bitmap, you also don't need to look for the top of the bitmap. This should help free up some processor cycles that you can use for faster x-ray resolution.

Answer 2

The most effective solution (regarding the required points) would be to provide a variable distance between the points along the X axis. Thus, a large flat part will require very few points / patterns and complex landscapes that will use more.

When processing a 3D mesh, there is a good mesh simplification algorithm called "quadric smoothing" that you can adapt to your problem.

Here's an idea translated into your problem - it actually becomes much simpler than the original 3D algorithm:

• Imagine your curve is too many points.
• For each point, measure the error (i.e. the difference with a smooth surface) if you delete it.
• Remove the point that gives the smallest error.
• Repeat until you reduce the number of points far enough, or the errors get too big.

To be more precise with respect to step 2: For given points P, Q, R error Q is the difference between approximating your area with two straight lines P->Q and Q->R , and also approximating your area by only one line P->R

Note that when a point is deleted, only its neighbors need to update their error value.

Answer 3

I suggest finding the boundary points that exist on the border between white and dark pixels. After that we can digitize these points. To do this, we must define a DELTA that indicates which point we should skip and which we should add to the list of results.

 DELTA = 3, Number of points = 223 

 DELTA = 5, Number of points = 136 

 DELTA = 10, Number of points = 70 

Below I put the source code, which prints the image and looks for points. Hope you can 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 used an example from this question:

• Java - get pixel array from image