7

一連のポリゴン データから一意のエッジを取得できる優れたアルゴリズムを探しています。この場合、ポリゴンは 2 つの配列によって定義されます。1 つの配列はポリゴンごとのポイント数で、もう 1 つの配列は頂点インデックスのリストです。

動作しているバージョンがありますが、500,000 ポリゴンを超えるとパフォーマンスが低下します。私のバージョンでは、各面を歩き回り、各エッジの並べ替えられた頂点を stl::set に追加します。私のデータ セットは主に三角形と四角形のポリゴンで、ほとんどのエッジは共有されます。

これのためのよりスマートなアルゴリズムはありますか?

4

5 に答える 5

4

明確にするために、次のようなポリゴン リストが必要です。

A +-----+ B
   \    |\
    \ 1 | \
     \  |  \
      \ | 2 \
       \|    \
      C +-----+ D

次に、次のようなエッジの代わりに:

A - B -+
B - C  +- first polygon
C - A -+

B - D -+
D - C  +- second polygon
C - B -+

次に、重複する B - C 対 C - B エッジを削除して共有しますか?

アルゴリズムでどのようなパフォーマンスの問題が発生していますか? 合理的なハッシュ実装を備えたセットは、かなりうまく機能するはずです。一方、ハッシュがデータに対して最適でない場合、多くの衝突が発生し、パフォーマンスに悪影響を与える可能性があります。

于 2008-10-16T08:15:07.420 に答える
4

はい
ダブル ハッシュ マップを使用します。
すべてのエッジには 2 つのインデックス A、B があります。A > B としましょう。
最初のトップ レベルのハッシュ マップは、A を別のハッシュ マップにマップし、次に B を、すべてのエッジについて必要な情報を表す値にマップします。（または、エッジの情報を保持する必要がない場合は単にブール値）。
基本的に、これにより、ハッシュ マップで構成される 2 レベルのツリーが作成されます。

この構造のエッジを検索するには、より大きなインデックスを取得し、最上位でそれを検索して、ハッシュ マップで終了します。次に、小さい方のインデックスを取得して、この 2 番目のハッシュ マップで検索します。

于 2008-10-16T08:16:32.067 に答える
2

あなたは両方とも正しいです。優れたハッシュセットを使用すると、必要なレベルをはるかに超えるパフォーマンスが得られます. 私は自分の小さなハッシュセットを展開することになりました。

エッジの総数は、N/2 から N の間になります。N は、メッシュ内の一意の頂点の数です。すべての共有エッジは N/2 になり、すべての一意のエッジは N になります。そこから、uint64 のバッファーを割り当て、インデックスをこれらの値にパックします。ユニークなテーブルの小さなセットを使用すると、ユニークなエッジをすばやく見つけることができます!

于 2008-10-17T17:44:39.517 に答える
1

これは、顔からエッジをすばやく作成する目的で正確に Blender で使用されるエッジ ハッシングの C 実装であり、他の人が独自のものを作成するためのヒントを提供する可能性があります。

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/edgehash.c

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_edgehash.h

これは、BLI_mempool、 https: //gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c を使用します。

https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_mempool.h

于 2013-05-10T12:21:21.783 に答える
0

まず、頂点が一意であることを確認する必要があります。これは、特定の位置に 1 つのエッジのみが必要な場合です。次に、このデータ構造を使用します

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Edge には、並べ替えられた順序でエッジを構成する頂点インデックスが含まれます。したがって、sampleEdge がインデックス番号 12 と 5 の頂点で構成されるエッジである場合、sampleEdge.first = 5 および sampleEdge.12 となります。

それからあなたはただすることができます

uniqueEdges[sampleEdge] = true;

すべてのエッジに。uniqueEdges はすべての一意のエッジを保持します。

于 2012-04-03T21:40:28.867 に答える