Drawing lots of particles efficiently

Question

I have written a particle system applet; currently I am creating, and drawing each particle separately. (Here is the code)

BufferedImage backbuffer;
Graphics2D g2d;

public void init(){
    backbuffer = new BufferedImage(WIDTH,HEIGHT,BufferedImage.TYPE_INT_RGB);
    g2d = backbuffer.createGraphics();
    setSize(WIDTH, HEIGHT);

    //creates the particles
    for (int i = 0; i < AMOUNTPARTICLES; i++) {
        prtl[i] = new particleO();
        prtl[i].setX(rand.nextInt(STARTX));
        prtl[i].setY(rand.nextInt(STARTY));
        prtl[i].setVel(rand.nextInt(MAXSPEED)+1);
        prtl[i].setFAngle(Math.toRadians(rand.nextInt(ANGLESPREAD)));

        }

    //other code
}



    public void update(Graphics g) {        

    g2d.setTransform(identity);

    //set background
    g2d.setPaint(BGCOLOUR);
    g2d.fillRect(0,0,getSize().width,getSize().height);
    drawp();
    paint(g);           
    }


public void drawp() {

    for (int n = 0; n < AMOUNTPARTICLES; n++) {

    if (prtl[n].getAlive()==true){
            g2d.setTransform(identity);
            g2d.translate(prtl[n].getX(), prtl[n].getY());
            g2d.setColor(prtl[n].getColor());

            g2d.fill(prtl[n].getShape());


            }
    }

}

It's performance was alright, I could get ~40FPS with 20,000 particles (although, I have a decent laptop). But after I added collision detection (see below), that number plummeted to less than 2000,

public void particleUpdate(){
 for (int i = 0; i < AMOUNTPARTICLES; i++) {
        //other update code (posx, posy, angle etc etc)

          for (int j = 0; j < AMOUNTPARTICLES; j++) {

                if (i!=j && prtl[j].getAlive()==true){

                     if(hasCollided(i, j)){
                        prtl[i].setcolor(Color.BLACK);
                        prtl[j].setcolor(Color.BLACK);
     }
            }
  }

public boolean hasCollided(int prt1, int prt2){

        double dx = prtl[prt1].getX() - prtl[prt2].getX();
        double dy = prtl[prt1].getY() - prtl[prt2].getY();
        int edges =  prtl[prt1].getRadius() + prtl[prt2].getRadius();

        double distance = Math.sqrt( (dx*dx) + (dy*dy) );
        return (distance <= edges);


    }

I have searched quite a bit for a better way of drawing the particles to the screen, but the examples either confused me, or were not applicable.

I am doing a boat load of calculations (too many). But I couldn’t think of another way of doing it, suggestions are welcome.

Answer 1

First of all, adding in something like collision detection always takes a lot of memory. However, let's look at your collision detection algorithm

public void particleUpdate(){
 for (int i = 0; i < AMOUNTPARTICLES; i++) {
        //other update code (posx, posy, angle etc etc)

          for (int j = 0; j < AMOUNTPARTICLES; j++) {

                if (i!=j && prtl[j].getAlive()==true){

                     if(hasCollided(i, j)){
                        prtl[i].setcolor(Color.BLACK);
                        prtl[j].setcolor(Color.BLACK);
                }
            }
  }

Let's pretend there was only 2 particles, 1 and 2. You will check, in order 1,1 1,2 2,1 2,2

The truth is, you only really needed to check 1 vs 2 in this case. If 1 hits 2, 2 will also hit 1. So change your for loop skip previously tested, and the same number for that matter.

public void particleUpdate(){
 for (int i = 0; i < AMOUNTPARTICLES; i++) {
        //other update code (posx, posy, angle etc etc)

          for (int j = i+1; j < AMOUNTPARTICLES; j++) {

Another thing I notice is that you do a sqrt operation, but only to compare to what looks like a static number. If you remove that, and compare it to the number squared, you'll get a large improvement, especially with something you do so much.

    double distance_squared = ( (dx*dx) + (dy*dy) );
    return (distance <= edges*edges);

Keep looking for improvements like this. Then you might carefully look at other options, like using a different class, threading, etc, which all might improve the system. But make sure you optimize the code where you can first. Here is a list of other things that I would try, roughly in order.

1. Check to see if particle i is alive before you even calculate anything else after i comes into view.
2. Do a quick pass over the pairs, only even bothering to check in detail if they are close. A simple way would be to detect if they are within the x and y dimensions first, before taking a sqrt operation. Always do the cheapest test first, before doing complex ones.
3. Look at your code, to see if you really use all of the values calculated, or if you might be able to reduce the number of operations somehow.
4. Perhaps you could cluster the images on a regular basis with a broad stroke, then refine only objects which passed the initial cluster for a period of time, then do a broad cluster algorithm.
5. You could thread the collision detection. However, if you are going to do this, you should only thread the checking to see if something has collided, and after all of those threads are done, update the objects on the view.
6. Look into alternative architectures, which might speed things up some.

Answer 2

Painting is a complex process and paint requests can be triggered for any number of reasons, the OS might want the window to update, the repaint manager might want to repaint, the programer might want to repaint.

Updating the particles within the paint process is bad idea. What you want to do is update the particles in a separate thread on a separate buffer. When you're ready, request that the component responsible for painting the buffer perform a repaint, passing a new copy of the buffer to repainted (you don't want to be painting on the buffer that is begin updated to the screen, you'll end up with dirty paints).

It's hard to tell from you code, but it would appear you're using java.awt.Applet, personally, I'd upgrade to javax.swing.JApplet.

I'd move the painting to a java.swing.JPanel. Swing components provide double buffering (as well as other buffering strategies). The only job this panel has is to paint a buffer to the screen when the particles engine has a new frame.

The particles engine is responsible for updating all the particles and painting these results to a backing buffer (BufferedImage), this would then be handed to the panel and the panel would make a copy and schedule an update.

Swing is NOT THREAD SAFE. That is, you shouldn't make changes to the UI from any thread other then the Event Dispatching Thread. To this end, you might like to have a read through Concurrency in Swing for solutions to resync the off screen buffer to the client.