1

ボクセルで 3D ボリュームを分解するアルゴリズムを実装する必要があります。アルゴリズムは、どの頂点が切断計画の各側にあるかを識別することから始まり、2 番目のステップでどのエッジが切断計画を横切るかを識別します。

このプロセスは、ソートされたリストの利点を利用して最適化できます。分割点を特定するのは O log(n) です。しかし、軸ごとに 1 つのソートされたリストを維持する必要があり、これは頂点とエッジに対して維持する必要があります。これは GPU で使用するために実装されるため、メモリ管理 (つまり CUDA) にもいくつかの制約があります。押し付けがましいリスト M/trees と C が課せられます。

完全な「ボクセル化」により、最終的に 4000 個のポイントと 12000 個のエッジになると予想しています。幸いなことに、これはよりスマートな戦略を使用して処理されたボクセルを取り除き、残りのボリュームをカットしてその数を最小限に抑えることで最適化できます。この場合、100 個未満のポイントと 300 個のエッジがあると予想されます。これにより、プロセスの管理がより複雑になりますが、最終的にはより効率的になります。

したがって、問題は、並べ替えられたデータ構造を使用する利点が、単純な侵入型リンクリストと比較して、労力と複雑なオーバーヘッドに見合う価値があるかどうかを判断する基準を特定するのに役立つことです。

4

3 に答える 3

2

chmike、これは本当にあなたが最初にもっと簡単な方法でやりたいようなことのように聞こえます、そしてそれがどのように振る舞うかを見てください。少なくとも（あなたが持っていないように見える）大容量に入ると、あらゆる種類のGPUボクセル化アプローチはシステムの詳細に対してかなり脆弱です。あなたの立場では、他にチェックする理由がなければ、私は間違いなく最初に簡単な実装を望んでいます...。

于 2009-04-21T14:13:08.347 に答える
1

問題は常に、どの演算子が最も一般的で、アクセスまたは追加であるかに要約されます。順序付けられていないリストがある場合は、追加に時間がかからず、特定の項目へのアクセスに余分な時間がかかります。並べ替えられたリストがある場合、追加には時間がかかりますが、アクセスはより高速です。

ほとんどのアプリケーションは、ほとんどの時間をデータに追加するのではなく、データにアクセスすることに費やします。つまり、ソートされたリストを作成する際の (実行) 時間のオーバーヘッドは、通常、リストへのアクセスで節約される時間によってバランスが取られるか、カバーされます。データに大量のチャーンがある場合 (実際にはそうではないように思えます)、ソートされたリストを維持することは必ずしも推奨されません。これは、かなりの CPU コストとしてリストを常に再利用することになるためです。

データ構造の複雑さは、有用な方法でソートできない場合にのみ問題になります。それらをソートできる場合は、次のヒューリスティックを使用する必要があります

アクセス数:変更回数

並べ替えが適切かどうかを判断します。

于 2009-04-21T15:21:08.577 に答える
1

すべての回答を検討した結果、重複計算を回避するために使用される後者の方法は、データ構造を維持およびナビゲートするための労力のために、効率が低下することがわかりました。さらに、最初の方法は、いくつかの小さなカーネル ルーチンで簡単に並列化できるため、GPU の実装により適しています。

最初の方法を振り返ってみると、ボリューム カット方法を大幅に後回しにする重要な最適化の機会も見つかりました。

答えを 1 つ選ばなければならなかったので、質問に答える devinb を選びましたが、Tobias Warre のコメントに裏打ちされた Simon のコメントは、私にとって同じくらい価値がありました。

この問題を整理するのを手伝ってくれてありがとう。スタック オーバーフローは印象的なサービスです。

于 2009-04-22T17:52:54.240 に答える