curva di terreno a matrice di punti

Question

nel mio gioco in 2D che sto usando strumenti grafici per creare bello, terreno morbido rappresentato dal colore nero:

semplice algoritmo scritto in java cerca colore nero ogni 15 pixel, creando seguente serie di linee (grigio):

Come si può vedere, ci sono alcuni luoghi che sono mappati molto male, alcuni sono piuttosto buone. In altri casi non sarebbe necessario campionare ogni 15 pixel, ad es. se il terreno è pianeggiante.

Qual è il modo migliore per nascondere questa curva a un insieme di punti [linee], utilizzando il minor numero di punti possibile? campionamento ogni 15 pixel = 55 FPS, 10 pixel = 40 fps

seguente algoritmo sta facendo quel lavoro, il campionamento da destra a sinistra, l'output pasteable in una matrice di codice:

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 in via di sviluppo su Android, utilizzando Java and AndEngine

Answer 1

Questo problema è quasi identico al problema della digitalizzazione di un segnale (come il suono), dove la legge di base è che il segnale nell'ingresso che ha una frequenza troppo alta per la frequenza di campionamento non sarà riflessa nell'output digitalizzato. Quindi la preoccupazione è che se si controllano sempre 30 pixel e si prova la metà come suggerisce bmorris591, si potrebbe perdere quel buco di 7 pixel tra i punti di campionamento. Questo suggerisce che se ci sono 10 caratteristiche pixel che non puoi permetterti di perdere, devi eseguire la scansione ogni 5 pixel: la tua frequenza di campionamento dovrebbe essere il doppio della frequenza più alta presente nel segnale.

Una cosa che può aiutare a migliorare il tuo algoritmo è una migliore ricerca di dimensione y. Attualmente si sta cercando l'intersezione tra cielo e del terreno in modo lineare, ma una ricerca binaria dovrebbe essere più veloce

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--; 

altre ottimizzazioni sono possibili. Se sai che il tuo terreno non ha dirupi, devi solo cercare nella finestra da ultimo + MAX alla fine a lastY-maxDropoff. Inoltre, se il terreno non può mai essere alto come l'intera bitmap, non è necessario eseguire la ricerca nella parte superiore della bitmap. Ciò dovrebbe aiutare a liberare alcuni cicli della CPU che è possibile utilizzare per x-scanning del terreno ad alta risoluzione.

Answer 2

La soluzione più efficiente (rispetto ai punti richiesti) sarebbe quella di consentire una spaziatura variabile tra i punti lungo l'asse X. In questo modo, una grande parte piatta richiederebbe pochissimi punti/campioni e terreni complessi ne farebbero di più.

Nell'elaborazione di mesh 3D, è presente un algoritmo di semplificazione della mesh denominato "Quadric Edge Crollo", che è possibile adattare al problema.

Ecco l'idea, tradotta al vostro problema - in realtà diventa molto più semplice che l'algoritmo originale 3D:

1. rappresentare la vostra curva con troppi punti.
2. Per ciascun punto, misurare l'errore (ad esempio la differenza rispetto al terreno liscio) se lo si rimuove.
3. Rimuovere il punto che dà l'errore più piccolo.
4. Ripetere fino a ridurre il numero di punti abbastanza o gli errori diventano troppo grandi.

Per essere più precisi per quanto riguarda il punto 2: Dato punti P, Q, R, l'errore di Q è la differenza tra il ravvicinamento del terreno da due linee rette, P->Q e Q->R, e l'approssimazione del terreno da una sola riga P->R.

Si noti che quando un punto viene rimosso solo i suoi vicini hanno bisogno di un aggiornamento del loro valore di errore.

Answer 3

Propongo di trovare punti di confine che esistono sul bordo tra pixel bianchi e scuri. Dopo di che possiamo digitalizzare quei punti. Per fare ciò, dovremmo definire DELTA che specifica quale punto dovremmo saltare e quale dovremmo aggiungere alla lista dei risultati.

DELTA = 3, Number of points = 223 

DELTA = 5, Number of points = 136 

DELTA = 10, Number of points = 70 

Qui di seguito, ho messo il codice sorgente, che consente di stampare immagini e alla ricerca di punti. Spero che tu possa leggerlo e trovare un modo per risolvere il tuo problema.

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); 
     } 
    } 
} 

Nel mio codice sorgente ho usato ad esempio da questa domanda:

• Java - get pixel array from image