logo标签列表

高效绘制大量粒子

javaperformancealgorithmgraphics2d
6

我编写了一个粒子系统小程序，目前我正在单独创建和绘制每个粒子。 (以下是代码)

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


            }
    }

}

它的性能还可以，我使用20000个粒子时可以获得约40FPS的帧率（虽然我的笔记本电脑性能不错）。但是，在我添加了碰撞检测后（见下文），这个数字骤降到不到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);


    }

我搜索了很多关于更好地将粒子绘制到屏幕上的方法，但这些示例要么让我感到困惑，要么不适用。
我进行了很多计算（太多了），但我想不出其他方法，欢迎提出建议。
https://dev59.com/_mcs5IYBdhLWcg3wMxJF - nair.ashvin
不要忘记在你决定哪个答案对你最有帮助时接受它。 - PearsonArtPhoto
3个回答
6

首先，添加类似碰撞检测之类的东西总是需要大量内存。然而，我们来看一下您的碰撞检测算法。

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

假设只有两个粒子，1和2。您将按顺序检查以下内容：

  1. 1,1
  2. 1,2
  3. 2,1
  4. 2,2

事实上，在这种情况下，您只需要检查1与2之间的碰撞。如果1撞击2，2也会撞击1。因此，请更改您的for循环以跳过先前测试过的数字，包括相同的数字。

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++) {

我注意到你进行了sqrt操作，但只是与一个看起来是固定数字的比较。如果你去掉这个操作，并将其与数字的平方进行比较，你会得到一个很大的改善，特别是在你频繁使用它的情况下。

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

保持寻找改进的方法。然后，您可能需要仔细查看其他选项，比如使用不同的类别、线程等，这些都可以改善系统。但请确保先在可以优化代码的地方进行优化。下面是我将尝试的其他事情列表，按照大致顺序排列。
  1. 在粒子i进入视野之后，甚至在计算其他任何内容之前，请检查粒子i是否仍然活着。
  2. 快速遍历对，只有在它们接近时才费力去详细检查。一个简单的方法是先检测它们是否在x和y维度内，然后进行sqrt操作。总是先做最便宜的测试，然后再做复杂的测试。
  3. 查看您的代码，看看您是否真的使用了所有计算出来的值，或者您是否可以通过某种方式减少操作数。
  4. 也许您可以定期以粗略的方式聚集图像，然后仅对通过初始聚类的对象进行细化一段时间，然后执行广泛的聚类算法。
  5. 您可以将碰撞检测线程化。但是，如果您要这样做，应该仅将检查是否发生碰撞的线程化，而在所有这些线程完成后，更新视图上的对象。
  6. 研究可能加速某些操作的替代架构。
非常感谢，我也在考虑类似的方法（嵌套循环），但是一直想不出来（点赞）。 - user1159424
没问题。像这样优化东西可能是我编程中最喜欢的部分 :-) - PearsonArtPhoto
另外，检查一下粒子是否移动了怎么样？只绘制自上一帧以来移动过的粒子。对于碰撞也是如此；两个未移动的粒子不会相互碰撞。 - Lee Taylor
可以这样做，但基本上需要通过将图像进行细分来实现。这取决于粒子不移动的频率。 - PearsonArtPhoto
4
绘画是一个复杂的过程，可以因任何原因触发涂漆请求，操作系统可能希望窗口更新，重新绘制管理器可能需要重新绘制，程序员可能需要重新绘制。
在绘画进程中更新粒子是个坏主意。您需要在单独的线程和单独的缓冲区中更新粒子。当准备好时，请请求负责绘制缓冲区的组件执行重绘，并将缓冲区的新副本传递给已重绘（您不希望在正在更新到屏幕的缓冲区上进行绘画，否则您会得到脏画）。
从您的代码很难看出来，但似乎您正在使用java.awt.Applet，个人建议升级为javax.swing.JApplet。
我会将绘画移到java.swing.JPanel。Swing组件提供了双缓冲（以及其他缓冲策略）。这个面板唯一的工作就是在粒子引擎有新帧时将一个缓冲区绘制到屏幕上。
粒子引擎负责更新所有粒子并将这些结果绘制到后备缓冲区（BufferedImage），然后将其交给面板，面板将制作一个副本并安排更新。
Swing不是线程安全的。也就是说，您不应该从除事件分派线程之外的任何线程更改UI。为此，您可能需要阅读Swing中的并发，以了解重新同步离屏缓冲区与客户端的解决方案。
0

您正在检查所有粒子与所有粒子的碰撞，这是一个相当大的要求，是n^2的顺序（2000个粒子意味着每帧有400万种组合）。

问题不在于Java，而在于算法。必须有更好的选择，但首先可以减少比较；如果您拥有最大速度S，并且您的世界时间按T递增，则使用T*S可以获得可以与您正在考虑的粒子发生碰撞的粒子的最大距离D。将搜索范围缩小到距离等于或小于该距离的那些粒子。也许将搜索限制在以您的粒子为中心并具有高度/宽度D的正方形内会更容易（这将包括一些太远的粒子，但会使检查更容易）。

此外，在您的代码中，您正在检查P1与P2和P2与P1的碰撞，这是相同的，这是可以轻松避免的冗余。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接