java - 使用 Java2D 高效绘制数千个形状？

Question

我在使用 Java2D 绘制可能数十万个矩形时遇到问题。

起初我所做的事情是这样的:

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

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

经过测试，我意识到，当有超过 500 个矩形时，这是非常低效的，所以我想也许将图形绘制到 BufferedImage 然后显示 BufferedImage 会更有效，所以我想出了这个。

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

然而，这仍然和第一种方法一样效率低下，我很难想出更好的方法来做到这一点，而且我宁愿远离像 OpenGL 这样的东西。

在 500-1000 个矩形之间，它会变得非常慢，超过这个范围，程序就会很快卡住。

因此，碰撞检测似乎是主要问题，而不是 Java2D 渲染。这就是我处理检测的方式，它检查两个矩形是否在任何一边接触。如果有人有更好的方法，我将不胜感激，因为我发现这是多么低效。

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

虽然我不确定如何处理问题的内容/目标由于编辑而完全改变的事实......

总结:正如评论中所指出的(您似乎已经预料到了)，即使是数千个矩形的渲染在 Java2D 中也不应该成为一个问题。在内部，它使用 DirectX 或 OpenGL 的硬件支持，并且您确实必须将大量抗锯齿文本和复杂的纹理或渐变绘制形状溢出到屏幕上，才能真正减慢速度。/p> <小时/>

话虽这么说，碰撞检测确实不太可能是这里的瓶颈。

据推测，您发布的方法位于 Entity 类中。据推测，e.bounds 是一个Rectangle2D。在这种情况下，您可以简单地测试与

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

目前尚不清楚您希望通过创建 Line2D 对象来实现什么目的，您可能应该用文字解释这一点。 (也许实际边界周围有某种“阈值”？)。但您应该记住，intersectsLine 方法的计算成本可能很高，至少与您实际想要执行的测试相比是这样。您应该尝试将其归结为间隔检查。

<小时/>

但即使你对你的 collides 方法进行这种(微观？-)优化，问题可能是一个更普遍的问题:从你到目前为止所写的内容来看，人们必须假设您正在测试每个实体是否与其他实体发生碰撞，并且在如下循环中调用此方法

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

如果是这种情况，实现的任何优化都不会帮助您，因为问题在于渐近复杂性:相交测试的数量(即，对collides方法的调用次数)随对象数量呈二次方增长。对于 500 个对象，您必须对该方法执行约 125.000 次调用。这已经相当多了，每秒几乎不可能完成 60 次。但对于 5000 个对象，您不需要 1.250.000 次调用，而是 12.500.000 次 - 这是其数量的 100 倍，当然，在 60 FPS 下是不可能做到的。

有复杂的数据结构用于对如此多的对象进行(成对)碰撞检测。不幸的是，这里的“复杂”通常意味着“实现起来极其复杂”。 Bounding Volume Hierarchies可能是一种有助于通过合理的努力加速碰撞检测的方法。但是，如果“小”空间中有“许多”和“小”对象，空间哈希可能是更合适的解决方案。您可以使用此关键字快速找到教程/博客条目和示例代码，一个示例位于 Spatial hashing implementation for fast 2D collisions ，但还有其他几个。