Drawing thousands of shapes with Java2D efficiently?

Question

I have an issue with drawing potentially hundreds of thousands rectangles with Java2D.

At first what I did was something along these lines:

private void render() {
   BufferStrategy bs = getBufferStrategy();
   if (bs == null) {
      createBufferStrategy(3);
      return;
   }

   Graphics g = bs.getDrawGraphics();
   //Draw Graphics here
   g.dispose();
   bs.show();
}

I then realized after testing that this was horribly inefficient when having anything above 500 rectangles, so I thought that maybe drawing the graphics to a BufferedImage then displaying the BufferedImage would be more efficient, so I came up with this.

private BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);

private void render() {
   BufferStrategy bs = getBufferStrategy();
   if (bs == null) {
      createBufferStrategy(3);
      return;
   }

   Graphics g = image.createGraphics();
   //Draw Graphics here
   g.dispose();

   Graphics g2 = bs.getDrawGraphics();
   g2.drawImage(image, 0, 0, width, height, null);
   g2.dispose();
   bs.show();
}

However this was still just as inefficient as the first way, I'm having trouble thinking of a better way to do this, and I'd prefer to stay away from something like OpenGL for this.

At between 500-1000 rectangles it gets really slow, and anything above that the program freezes very quickly.

So it would seem collision detection seems to be the main problem, rather than Java2D rendering. This is how I've handled the detection, it checks if two rectangles are touching on any side. If someone has a better approach to this I would appreciate it, because I'm seeing how inefficient this is.

public boolean collides(Entity e) {
    Point2D upperLeftIn = new Point2D.Double(bounds.getX() + 1, bounds.getY());
    Point2D upperRightIn = new Point2D.Double(bounds.getX() + 8, bounds.getY());
    Point2D lowerLeftIn = new Point2D.Double(bounds.getX() + 1, bounds.getY() + 9);
    Point2D lowerRightIn = new Point2D.Double(bounds.getX() + 8, bounds.getY() + 9);

    Point2D upperLeftDown = new Point2D.Double(bounds.getX(), bounds.getY() + 1);
    Point2D lowerLeftUp = new Point2D.Double(bounds.getX(), bounds.getY() + 8);
    Point2D upperRightDown = new Point2D.Double(bounds.getX() + bounds.getWidth(), bounds.getY() + 1);
    Point2D lowerRightUp = new Point2D.Double(bounds.getX() + bounds.getWidth(), bounds.getY() + 8);

    Line2D top = new Line2D.Double(upperLeftIn, upperRightIn);
    Line2D bottom = new Line2D.Double(lowerLeftIn, lowerRightIn);
    Line2D left = new Line2D.Double(upperLeftDown, lowerLeftUp);
    Line2D right = new Line2D.Double(upperRightDown, lowerRightUp);

    if (e.bounds.intersectsLine(top)) {
        return true;
    }
    if (e.bounds.intersectsLine(bottom)) {
        return true;
    }
    if (e.bounds.intersectsLine(left)) {
        return true;
    }
    if (e.bounds.intersectsLine(right)) {
        return true;
    }

    return false;
}

Answer 1

Although I'm not sure how to handle the fact that the contents/goal of the question changed completely due to the edit...

To summarize: As it was pointed out in the comment (and you seem to have anticipated), the rendering of even thousands of rectangles should not be so much an issue in Java2D. Internally, it is using hardware support with DirectX or OpenGL, and you really have to spill lots of antialiased text and complex, textured or gradient-painted shapes onto the screen in order to really slow it down.

---

That being said, it's really not unlikely that the collision detection is the bottleneck here.

Presumably, the method that you posted is in the Entity class. And presumably, e.bounds is a Rectangle2D. In this case, you could simply test for intersections with

public boolean collides(Entity e) {
    return this.bounds.intersects(e.bounds);
}

It is not clear what you wanted to achieve with the creation of the Line2D objects there, and you should probably explain this in words. (Maybe some sort of "threshold" around the actual bounds?). But you should keep in mind that the intersectsLine method can be computationally expensive, at least compared to the test that you actually want to do. You should try to boil this down to interval checks.

---

But even if you do this sort of (micro?-)optimizations to your collides method, the problem may be a more general one: From what you have written so far, one has to assume that you are testing each entity for collisions with each other entity, and this method is called in a loop like

for (int i=0; i<allEntities.size(); i++)
{ 
    for (int j=i+1; j<allEntities.size(); j++)
    {
        Entity ei = allEntities.get(i);
        Entity ej = allEntities.get(j);
        if (ei.collides(ej)) handleCollision();
    }
}   

If this is the case, no optimization of the implementation will help you, because the problem lies in the asymptotic complexity: The number of intersection tests (that is, the number of calls to the collides-method) grows quadratically with the number of objects. For 500 objects, you'll have to do do ~125.000 calls to the method. That's already quite a lot, and could hardly be done 60 times per second. But for 5000 objects, you don't need 1.250.000 calls, but 12.500.000 - this is 100 times as many, and of course, impossible to do at 60 FPS.

There are sophisticated data structures for the (pairwise) collision detection of so many objects. Unfortunately, "sophisticated" here often means "horribly complicated to implement". Bounding Volume Hierarchies may be one approach that can help to accelerate the collision detection with reasonable effort. But if you have "many" and "small" objects that are in a "small" space, Spatial Hashing may be the more appropriate solution. You can quickly find tutorials/blog entries and sample code using this keyword, one example is at Spatial hashing implementation for fast 2D collisions, but there are several others.