Efficiently rendering an Occupancy Grid in Java Swing

Question

First off, please accept my apologies if this question is basic, I mainly have knowledge of C# but am forced to use Java for this particular project!

I'm trying to implement a GUI to display an occupancy grid based on robot sensor data. The occupancy grid will be quite large, perhaps up to 1500x1500 grid squares representing real-world area of around 10cm2 per grid cell.

Each grid square will simply store an Enumerable status, for example:

• Unknown
• Unoccupied
• Occupied
• Robot

I would simply like to find the best way to render this as a grid, using different colour squares to depict different grid cell status'.

I have implemented a naive, basic algorithm to draw squares and grid lines, however it performs VERY badly on larger occupancy grids. Other code in the class redraws the window every 0.5s as new sensor data is collected, I suspect the reason for the very poor performance is the fact that i am rendering EVERY cell EVERY time. Is there an easy way i can selectively render these cells, should I wrap each cell in an observable class?

My current implementation:

@Override
public void paint(Graphics g) {
    Graphics2D g2 = (Graphics2D) g;

    int width = getSize().width;
    int height = getSize().height;

    int rowHeight = height / (rows);
    int colWidth = width / (columns);

    //Draw Squares
    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < columns; col++) {
            switch (this.grid[row][col]) {
                case Unexplored:
                    g.setColor(Color.LIGHT_GRAY);
                    break;
                case Empty:
                    g.setColor(Color.WHITE);
                    break;
                case Occupied:
                    g.setColor(Color.BLACK);
                    break;
                case Robot:
                    g.setColor(Color.RED);
                    break;
            }

            g.drawRect(col * colWidth, height - ((row + 1) * rowHeight), colWidth,     rowHeight);
            g.fillRect(col * colWidth, height - ((row + 1) * rowHeight), colWidth,     rowHeight);
        }
    }

    int k;
    if (outline) {
        g.setColor(Color.black);
        for (k = 0; k < rows; k++) {
            g.drawLine(0, k * rowHeight, width, k * rowHeight);
        }

        for (k = 0; k < columns; k++) {
            g.drawLine(k * colWidth, 0, k * colWidth, height);
        }
    }

}


 private void setRefresh() {
    Action updateUI = new AbstractAction() {
        boolean shouldDraw = false;

        public void actionPerformed(ActionEvent e) {
            repaint();
        }
    };

    new Timer(updateRate, updateUI).start();
}

Please help! Thanks in advance.

Answer 1

ROS - robot operating system from willowgarage has an occupancygrid implementation in java: http://code.google.com/p/rosjava/source/browse/android_honeycomb_mr2/src/org/ros/android/views/map/OccupancyGrid.java?spec=svn.android.88c9f4af5d62b5115bfee9e4719472c4f6898665&repo=android&name=88c9f4af5d&r=88c9f4af5d62b5115bfee9e4719472c4f6898665

You may use it or get ideas from it.

Answer 2

You need to respect the clip rectangle when painting (assuming your grid is in a JScrollPane) and use JComponent#repaint(Rectangle) appropriately.

See this sample program (although it related to loading the value of a cell lazily, it also has the clip bounds painting):

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;

import javax.swing.*;


public class TilePainter extends JPanel implements Scrollable {

    public static void main(String[] args) {
        EventQueue.invokeLater(new Runnable() {
            public void run() {
                JFrame frame = new JFrame("Tiles");
                frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
                frame.getContentPane().add(new JScrollPane(new TilePainter()));
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }
        });
    }

    private final int TILE_SIZE = 50;
    private final int TILE_COUNT = 1000;
    private final int visibleTiles = 10;
    private final boolean[][] loaded;
    private final boolean[][] loading;
    private final Random random;

    public TilePainter() {
        setPreferredSize(new Dimension(
                TILE_SIZE * TILE_COUNT, TILE_SIZE * TILE_COUNT));
        loaded = new boolean[TILE_COUNT][TILE_COUNT];
        loading = new boolean[TILE_COUNT][TILE_COUNT];
        random = new Random();
    }

    public boolean getTile(final int x, final int y) {
        boolean canPaint = loaded[x][y];
        if(!canPaint && !loading[x][y]) {
            loading[x][y] = true;
            Timer timer = new Timer(random.nextInt(500),
                    new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    loaded[x][y] = true;
                    repaint(x * TILE_SIZE, y * TILE_SIZE, TILE_SIZE, TILE_SIZE);
                }
            });
            timer.setRepeats(false);
            timer.start();
        }
        return canPaint;
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);

        Rectangle clip = g.getClipBounds();
        int startX = clip.x - (clip.x % TILE_SIZE);
        int startY = clip.y - (clip.y % TILE_SIZE);
        for(int x = startX; x < clip.x + clip.width; x += TILE_SIZE) {
            for(int y = startY; y < clip.y + clip.height; y += TILE_SIZE) {
                if(getTile(x / TILE_SIZE, y / TILE_SIZE)) {
                    g.setColor(Color.GREEN);
                }
                else {
                    g.setColor(Color.RED);
                }
                g.fillRect(x, y, TILE_SIZE, TILE_SIZE);
            }
        }
    }

    @Override
    public Dimension getPreferredScrollableViewportSize() {
        return new Dimension(visibleTiles * TILE_SIZE, visibleTiles * TILE_SIZE);
    }

    @Override
    public int getScrollableBlockIncrement(
            Rectangle visibleRect, int orientation, int direction) {
        return TILE_SIZE * Math.max(1, visibleTiles - 1);
    }

    @Override
    public boolean getScrollableTracksViewportHeight() {
        return false;
    }

    @Override
    public boolean getScrollableTracksViewportWidth() {
        return false;
    }

    @Override
    public int getScrollableUnitIncrement(
            Rectangle visibleRect, int orientation, int direction) {
        return TILE_SIZE;
    }
}

Answer 3

Rendering even a subset of 2,250,000 cells is not a trivial undertaking. Two patterns you'll need are Model-View-Controller, discussed here, and flyweight, for which JTable may be useful.

Answer 4

Creating rectangles is probably too slow. Instead, why don't you create a bitmap image, each pixel being a cell of the grid, you can then scale it to whatever size you want.

The following class takes a matrix of integers, and saves it to a bitmap file.

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;

public class BMP {
    private final static int BMP_CODE = 19778;

    byte [] bytes;

    public void saveBMP(String filename, int [][] rgbValues){
        try {
            FileOutputStream fos = new FileOutputStream(new File(filename));

            bytes = new byte[54 + 3*rgbValues.length*rgbValues[0].length + getPadding(rgbValues[0].length)*rgbValues.length];

            saveFileHeader();
            saveInfoHeader(rgbValues.length, rgbValues[0].length);
            saveRgbQuad();
            saveBitmapData(rgbValues);

            fos.write(bytes);

            fos.close();

        } catch (FileNotFoundException e) {

        } catch (IOException e) {

        }

    }

    private void saveFileHeader() {
        byte[]a=intToByteCouple(BMP_CODE);
        bytes[0]=a[1];
        bytes[1]=a[0];

        a=intToFourBytes(bytes.length);
        bytes[5]=a[0];
        bytes[4]=a[1];
        bytes[3]=a[2];
        bytes[2]=a[3];

        //data offset
        bytes[10]=54;
    }

    private void saveInfoHeader(int height, int width) {
        bytes[14]=40;

        byte[]a=intToFourBytes(width);
        bytes[22]=a[3];
        bytes[23]=a[2];
        bytes[24]=a[1];
        bytes[25]=a[0];

        a=intToFourBytes(height);
        bytes[18]=a[3];
        bytes[19]=a[2];
        bytes[20]=a[1];
        bytes[21]=a[0];

        bytes[26]=1;

        bytes[28]=24;
    }

    private void saveRgbQuad() {

    }

    private void saveBitmapData(int[][]rgbValues) {
        int i;

        for(i=0;i<rgbValues.length;i++){
            writeLine(i, rgbValues);
        }

    }

    private void writeLine(int row, int [][] rgbValues) {
        final int offset=54;
        final int rowLength=rgbValues[row].length;
        final int padding = getPadding(rgbValues[0].length);
        int i;

        for(i=0;i<rowLength;i++){
            int rgb=rgbValues[row][i];
            int temp=offset + 3*(i+rowLength*row) + row*padding;

            bytes[temp]    = (byte) (rgb>>16);
            bytes[temp +1] = (byte) (rgb>>8);
            bytes[temp +2] = (byte) rgb;
        }
        i--;
        int temp=offset + 3*(i+rowLength*row) + row*padding+3;

        for(int j=0;j<padding;j++)
            bytes[temp +j]=0;

    }

    private byte[] intToByteCouple(int x){
        byte [] array = new byte[2];

        array[1]=(byte)  x;
        array[0]=(byte) (x>>8);

        return array;
    }

    private byte[] intToFourBytes(int x){
        byte [] array = new byte[4];

        array[3]=(byte)  x;
        array[2]=(byte) (x>>8);
        array[1]=(byte) (x>>16);
        array[0]=(byte) (x>>24);

        return array;
    }

    private int getPadding(int rowLength){

        int padding = (3*rowLength)%4;
        if(padding!=0)
            padding=4-padding;


        return padding;
    }

}

With that class, you can simply do:

new BMP().saveBMP(fieName, myOccupancyMatrix);

Generating the matrix of integers (myOccupancyMatrix) is easy. A simple trick to avoid the Switch statement is assigning the color values to your Occupancy enum:

public enum Occupancy {
        Unexplored(0x333333), Empty(0xFFFFFF), Occupied(0x000000), Robot(0xFF0000);
}

Once you save it do disk, the BMP can be shown in an applet and scaled easily:

public class Form1 extends JApplet {
    public void paint(Graphics g) {
        Image i = ImageIO.read(new URL(getCodeBase(), "fileName.bmp"));
        g.drawImage(i,0,0,WIDTH,HEIGHT,Color.White,null);
    }
}

Hope this helps!