43

多数の長方形があり、一部は他の長方形と重なっています。各長方形には、絶対 z オーダーと色があります。(各「長方形」は、実際にはパーティクル エフェクト、メッシュ、またはテクスチャの軸に沿ったバウンディング ボックスであり、半透明の場合があります。しかし、他の長方形の背後にある長方形をカリングしようとしない限り、色付きの長方形について抽象的に考える方が簡単です。 、だから私は問題の説明でそれを使用します:)

「色」を変更するコストは非常に高くなります。2 つの異なる色の四角形を描くよりも、2 つの青い四角形を続けて描く方がはるかに高速です。

画面上にない四角形を描画するコストも非常に高く、避けるべきです。

2 つの長方形が重ならない場合、それらが互いに相対的に描画される順序は重要ではありません。zオーダーが重要なのは、それらが重なっている場合のみです。

例えば：

長方形の重なり

1(赤)と4(赤)はまとめて描けます。2 (青) と 5 (青)、3 (緑) と 7 (緑) を一緒に描くこともできます。ただし、8 (赤) は 6 (青) の後に描画する必要があります。したがって、3 つの赤をすべて一緒に描いて青を 2 つのセットで描くか、すべての青を一緒に描いて赤を 2 つのセットで描くかのどちらかです。

また、長方形の一部が時々移動する場合があります。(すべてではありません。静的であることがわかっている四角形もあれば、移動することがわかっている四角形もあります。)

このシーンを JavaScript/webGL で描画します。

JavaScript のカリング コードと GPU によるカリングの適切なトレードオフを考慮して、色の変化を最小限に抑えるために、適切な順序で四角形を描画するにはどうすればよいでしょうか?

（どの長方形が重なり、どの長方形が表示されているかを調べるだけでも費用がかかります。私は基本的な四分木を持っており、これによりシーンの描画が非常に高速になりました（シーン全体の描画操作を単に発行する場合と比較して）; 問題は、OpenGL を最小限に抑える方法です。状態が変化し、可能な限り属性配列を連結します)

更新問題を説明し、ソリューションのデモンストレーションの基礎として役立つ非常に単純なテストアプリを作成しました: http://williame.github.com/opt_rects/

ソースコードは github にあり、簡単にフォークできます: https://github.com/williame/opt_rects

完全なゲームで見られる問題を実際に再現するのに十分な状態変更を備えた小さなテスト アプリを作成するのは難しいことがわかりました。ある時点で、状態の変更には十分なコストがかかる可能性があることを考慮する必要があります。また、空間インデックス (デモでは四分木) と全体的なアプローチを高速化する方法も重要です。

4

4 に答える 4

16

デスクトップ ブラウザで得られるパフォーマンスが iPhone でのパフォーマンスを何らかの形で決定するという、非常に間違った仮定をしています。iPhone ハードウェアがタイルベースの遅延レンダリングを実装していることを理解する必要があります。つまり、パイプラインの非常に遅い段階でフラグメント シェーダーが使用されるということです。Apple 自身が言っているように (「<em>オブジェクトを前後に並べ替えて CPU 時間を無駄にしないでください」)、プリミティブを Z 並べ替えしてもパフォーマンスはほとんど向上しません。

しかし、ここに私の提案があります: 色の変更にコストがかかる場合は、色を変更しないでください。それを頂点属性として渡し、動作を 1 つのスーパー シェーダーにマージして、並べ替えさえせずに 1 つまたはいくつかのバッチですべてを描画できるようにします。次に、ベンチマークを行い、プラットフォームに最適なバッチ サイズを決定します。

于 2013-01-17T08:21:47.733 に答える
12

ボックスではなく、色を選択してください。

いつでも、1 つまたは複数のボックスがペイント可能になります。つまり、問題を引き起こすことなく次にペイントできます (ただし、最後にペイントしたボックスとは異なる色になるため、コストが発生する可能性があります)。

すべてのポイントでの質問は次のとおりです。次に描画するためにどの色を選択する必要がありますか? ペイント可能なボックスを個別に選択して描画することを考える必要はありません。特定のボックスを選択して次に描画するとすぐに、その時点で描画できる同じ色の利用可能なすべてのボックスを描画する可能性があるからです。それは、ボックスをペイントしても追加されないためです問題への制約、それらを削除するだけです。また、現在の色を変更せずにペイント可能なボックスをペイントできない場合でも、ペイントしないことを選択すると、後でこのボックスをペイントする必要があり、色の変更が必要になる可能性があるため、ソリューションを他の方法よりも安価にすることはできません。これはまた、同じ色のペイント可能なボックスをペイントする順序が重要ではないことも意味します。これは、ボックス ペイント操作の 1 つの「ブロック」で一度にすべてのボックスをペイントするためです。

依存関係グラフ

「下にある」依存関係グラフを作成することから始めます。ここでは、色付きの各四角形が頂点で表され、四角形 v が四角形 u と重なってその下にある場合、v から u への円弧 (矢印) があります。私が最初に考えたのは、これを使用して、推移閉包を見つけて「前に描画する必要がある」依存グラフを構築することでしたが、実際にはこれを行う必要はありません。以下のすべてのアルゴリズムが気にするのは、頂点がペイント可能かどうかであるからです。 . ペイント可能な頂点は、前の頂点 (弧内) を持たない頂点であり、推移閉包を使用しても、頂点の弧内が 0 であるかどうかは変わりません。

さらに、特定の色のボックスにその祖先と同じ色のボックスしかない場合は常に、同じ「ブロック」にペイントされます。これは、これらすべての祖先が色を変更せずにその前にペイントできるためです。

スピードアップ

計算を減らすために、ある特定の色のすべてのペイント可能なボックスに異なる色の子孫がない場合は常に、この色をペイントしても他のボックスがペイント可能になる新しい機会が開かれないことに注意してください。したがって、これを考慮する必要はありません。次にどの色を塗るかを検討するときの色 - コストを増やすリスクなしに、いつでも後でそれを残すことができます。実際には、この色のペイントは後で行ったほうがよいでしょう。それまでに、この色の他のボックスがペイント可能になる可能性があるからです。役立つ色を呼び出す異なる色の子孫を持つその色のペイント可能なボックスが少なくとも 1 つある場合。有用な色が残っていない時点 (つまり、残りのすべてのボックスが同じ色のボックスのみに重なるか、まったくボックスがない場合) に到達すると、完了です。残りの各色のボックスをペイントし、色を選択するだけです。任意の順序。

アルゴリズム

これらの観察は、2 つの可能なアルゴリズムを示唆しています。

  1. 高速ですが最適ではない貪欲なアルゴリズム:最も新しいペイント可能な頂点を生成する色の次にペイントすることを選択します。(これにより、有用な色のみが自動的に考慮されます。)

  2. 低速で正確な DP または再帰アルゴリズム:有用な色 c の候補ごとに、描画可能なすべての c 色のボックスを次に描画することによって生成される依存関係グラフを検討してください。

    f(g) を、依存グラフ g 内のすべてのボックスをペイントするために必要な色の変更の最小数とします。それで

    f(g) = 1 + 分(f(p(c, g)))

    ここで、p(c, g) は、色 c のすべてのペイント可能なボックスをペイントすることによって生成される依存グラフです。G が元の問題の依存グラフである場合、f(G) は変更の最小数になります。色の選択自体は、DP コスト マトリックスを逆方向にたどることによって再構築できます。

    f(g) を記憶して動的計画法アルゴリズムを作成し、2 つの異なる色選択の順列が同じグラフを生成するたびに時間を節約できます。これは頻繁に発生します。しかし、DP の後でも、このアルゴリズムは、ボックスの数が指数関数的になる時間 (したがってスペース) を要する可能性があります。

于 2013-01-16T16:28:21.717 に答える
2

ランダムな（ただし正しい）順序で、たとえば厳密なzオーダーで描画することから始めます。各フレームを描画するときは、色の変化の数を数えるか、場合によってはフレーム全体にかかる実際の時間を数えます。フレームごとに、2つの長方形の順序を入れ替えてみてください。交換する長方形は重なってはいけません。したがって、正確性を損なうことなく、任意の順序で描画できます。それを除けば、ランダムに選択するか、リストを線形パスするか、または...スワップを実行すると色の変更の数が減る場合は、新しい順序を維持します。元に戻さない場合は、別のスワップを試してください。次のフレーム。スワップを実行しても色の変化の数が減少も増加もしない場合は、50％のオッズで維持してください。前のフレームでオーバーラップしなかったが、移動によってオーバーラップし始めた長方形の場合は、zオーダーになるように交換するだけです。

これは、アイテムのペアを交換する並べ替えアルゴリズムと何らかの関係があります。ただし、アイテムを比較できない場合は、リスト全体を調べて色の変化をカウントする必要があります。これは、最初は非常にパフォーマンスが悪くなりますが、比較的迅速に適切な順序に収束し、シーンの変化に適応します。フレームごとに最適な順序を調べて計算することは、おそらく価値がないと思います。これにより、余分な作業をほとんど必要とせずに、ほぼ最適な順序に到達し、維持されます。

あなたが持っている図面を参照してください：ランダムに選ばれた最初の図面の順序：1,6,2,4,5,8,3,7（5つの色の変化）。5,8を交換します。新しい注文：1,6,2,4,8,5,3,7（4色の変更）=>新しい注文を保持します。

于 2013-01-20T11:33:07.750 に答える
2

ここに可能性があります。実際に改善されているかどうかを確認するには、ベンチマークを実行する必要があります。

For all rectangles, back to front:
  If this rectangle has been marked as drawn, skip to the next one
  Set a screen-sized unseen surface to all black
  Call this rectangle's color "the color"
  For rectangles starting with this one and proceeding toward the front
    If (this rectangle's color is the color and
        all the pixels of this rectangle on the unseen are black) then
      Add this rectangle to the to-draw list
    Draw a white rectangle with this rectangle's shape on the unseen surface
    If the unseen surface is more than half white, break
  For all rectangles on the to-draw list:
    Draw the rectangle
    Mark it as drawn

順序に関して最適であるとは限りませんが、かなり近くなると思います。最悪の場合、描画前のステップでは 2 次です。グラフィックバッファからのリードバックが高速であることに依存します。そこで役立つかもしれない 1 つのトリックは、関心領域の縮小バージョンである新しい 1 ピクセル サーフェスを作成することです。その色は、元の白の部分になります。

于 2013-01-17T18:11:08.847 に答える