多くの粒子を効率的に描く

Question

私はパーティクルシステムアプレットを作成しました。現在私は作成しており、各パーティクルを個別に描画しています。 それは私20,000粒子（、私はまともなノートパソコンを持っているが）で〜40FPSを得ることができ、パフォーマンスは大丈夫だったのです

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


      } 
    } 

} 

（ここでは、コードです）。しかし、私は衝突検出を追加した後（下記参照）、その数が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); 


    } 

私は画面に粒子を描画するより良い方法のためにかなり検索しましたが、例はどちらか私を混同しました、または適用されなかった。

私は計算のボート負荷を（あまりにも）行っています。しかし、私はそれをやって別の方法を考えることができなかった、提案は大歓迎です。

Answer 1

まず、衝突検出のようなものを追加するには、常に多くのメモリが必要です。しかし、

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,1 1,2 2,1 2,2に、チェックするだけで2粒子、1と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. ペアをすばやく通過し、近くにいると詳細に確認するのも面倒です。簡単な方法は、sqrt操作を実行する前に、xおよびy次元内にあるかどうかを最初に検出することです。複雑なテストを行う前に、常に最も安いテストをまず実行してください。
3. コードを見て、実際に計算された値のすべてを使用しているか、何らかの操作の数を減らすことができるかどうかを確認してください。
4. 多分、広いストロークで画像を定期的にクラスタリングしてから、最初のクラスタを一定期間通過したオブジェクトだけを絞り込み、広範なクラスタアルゴリズムを実行することができます。
5. あなたは衝突検出をスレッドすることができます。ただし、これを行う場合は、何かが衝突したかどうかを確認するためだけにスレッドを実行し、すべてのスレッドが完了したらビューのオブジェクトを更新してください。
6. いくつかのことをスピードアップする可能性がある代替アーキテクチャを調べてください。

Answer 2

ペインティングは複雑なプロセスであり、いくつかの理由でペイント要求がトリガされる可能性があります。ウィンドウが更新される可能性があり、再描画マネージャが再描画したい場合があります。

paintプロセス内の粒子を更新することは悪い考えです。あなたがしたいことは、別のバッファ上の別のスレッドの中のパーティクルを更新することです。準備ができたら、バッファのペイントを担当するコンポーネントが再描画を実行し、バッファの新しいコピーを再描画するように要求します（バッファにペイントしたくない場合は、汚れた塗料で終わるでしょう）。

コードは難しいですが、java.awt.Appletを使用しているように見えますが、私はにアップグレードします。

私は絵をjava.swing.JPanelに移動します。スイングコンポーネントは、ダブルバッファリング（および他のバッファリング戦略）を提供する。このパネルが持つ唯一の仕事は、パーティクルエンジンに新しいフレームがあるときにバッファをペイントすることです。

パーティクルエンジンはすべてのパーティクルを更新し、これらの結果をバッキングバッファー（BufferedImage）にペイントする必要があります。これがパネルに渡され、パネルはコピーを作成して更新をスケジュールします。

スイングは安全ではありません。つまり、Event Dispatching Thread以外のスレッドからUIに変更を加えるべきではありません。この目的のために、オフスクリーンバッファをクライアントに再同期させるソリューションについては、Concurrency in Swingを読んで読んでください。

Answer 3

すべてのパーティクルと衝突していることを確認しています。これは、n^2のオーダのかなりの条件です（2,000個のパーティクルは各フレームで4,000,000の組み合わせを意味します）。

問題はJavaではなくアルゴリズムです。より良いオプションが必要ですが、まずは比較を減らすことができます。最高速度Sがあり、あなたの世界の時間がTで増分される場合、T * Sを使って、あなたが考えている粒子と衝突する可能性のある粒子の最大距離Dを求めます。距離が同じかそれ以下の粒子に検索を減らしてください。たぶん、高さ/幅D（これはあまりにも遠すぎるが、小切手をより簡単にする粒子が含まれている）で、粒子を中心とする正方形のものに検索を制限する方が簡単かもしれません。

さらに、あなたのコードでは、P1対P2とP2対P1の衝突をチェックしています。つまり、簡単に回避できる冗長性です。