openGL を使用してゲームまたは 3D アプリケーションを作成しようとしています。ゲーム/プログラムには多くのオブジェクトがあり、画面に描画されます (約 7000 個)。それらをレンダリングするときは、シーン内のオブジェクトを正しくレンダリングするために、カメラとオブジェクト間の距離を計算して並べ替える必要があります。これを知って、それらをソートする最良の方法は何ですか? ソートを非常に高速に実行したいのですが、それらには「トレードオフ」があると聞いています。最高のパフォーマンスを得るには、どのアルゴリズムを使用すればよいですか?
どんな助けでも大歓迎です。
編集: 多くの人が z-buffer/depth buffer について話しています。数人が話しているように、これは場合によっては機能しません。これが私がこの質問をした理由です。
距離で並べ替えても、透明性の問題は完全には解決されません。2 つの透明なサーフェスが交差し、それぞれに近い部分がある状況を考えてみましょう。ゲームではまれかもしれませんが、レンダラーに時折のグリッチの外観が必要ない場合は、考慮すべきことがあります。
より良い解決策は、順序に依存しない透過性です。アトミック操作をサポートする最新のグラフィックス ハードウェアでは、A バッファーを使用してメモリ オーバーヘッドをほとんど発生させずに単一パスでこれを実行できるため、非常に効率的です。たとえば、この記事を参照してください。
シーンの並べ替えの問題は、透明性のためでなくても有効です。不透明なオブジェクトを前後に並べ替えて、深度テストで目に見えないフラグメントを破棄できるようにすることは依然として有用です。このために、Vaughn は BSP ツリーの優れたソリューションを提供しました。これらは、3D ゲームが存在する限り、この目的のために使用されてきました。
ほぼソートされた配列に対して O(n) の複雑さを持つhttp://en.wikipedia.org/wiki/Insertion_sortを使用します。
あなたの場合、一時的な結合挿入ソートを利用することで、最速の結果が得られます。http://en.wikipedia.org/wiki/Sweep_and_pruneに使用されます
上記のリンクから：
多くのアプリケーションでは、あるタイム ステップから次のタイム ステップまでの物理的なボディの構成はほとんど変化しません。オブジェクトの多くはまったく動かない場合があります。アルゴリズムは、前の時間ステップで実行された計算を現在の時間ステップで再利用できるように設計されているため、計算をより迅速に完了できます。
したがって、そのような場合、挿入ソートが最適です（または、最良の場合、O（n）を使用した同様のソート）