4

Octree Containerがどのように機能するかについての説明を、Web全体で検索しました。私は1つがどのように機能するかについての明確な説明を見つけることができません。（少なくとも、それは私には理にかなっています...）Octree Containerを実装する方法を知っている人はいますか？8人（またはそれくらい）の子供がいる人。もしそうなら、ロジックを共有/説明してもよろしいですか...またはロジックを実装する方法を学ぶためにどこに行くことができますか？

4

1 に答える 1

14

あなたの質問は非常に一般的です。しかし、私はあなたにアイデアを与えようとします。アプリケーションに依存する octree を実装する方法は多数あることに注意してください。この例では、常に真ん中で分割する単純なケースに焦点を当てます。

まずはシンプルに始めましょう。一連の数値 (1 次元データ) があるとします。より簡単に検索できるように、これらをグループ化する必要があります。それを行う 1 つの方法 (この特定のケースではより良い方法が存在しますが) は、ツリーを作成することです。これをビットツリーと呼びましょう（バイナリツリーの一種ですが、バイナリツリーと混同しないように）。

このビットツリーでは、各ノードが範囲の中央を表します。左側では値がそれよりも小さく、右側では値が大きくなります。もちろん、ツリーのルートは最小値と最大値の中間を表します。各リーフに、処理しきれないほどの値がある場合は、分割してサブツリーを作成します。たとえば、値が 0 ～ 100 の場合、ビットツリーは次のようになります。

                  50
              /        \
           25            75
         /    \        /    \
        12   {27,33}  62    {}
      /    \        /    \
   {1,3}  {13}   {51,52} {72}

このツリーは、次の配列を表しています。

{1, 3, 13, 27, 33, 51, 52, 72}

あなたは二分木に精通していると思いますので、そのような木の実装は問題にはなりません。

ここで重要なのは、各リーフには特定の数までのノードを含めることができるということです。ビットツリーに挿入するたびに、リーフがオーバーフローした場合、その範囲の中央を取得し、ノードを作成して値を 2 つのリーフに分割します。

これを2次元に拡張してみましょう。(x,y)値が(単なる ではなく)の形式になっていると想像してくださいx。これらの値を上記と同じ方法で分割できますが、中央の左右ではなく、中央の左上、左下、右上、右下に分割します。残りはまったく同じです。4 つの子があるため、これを四分木と呼びます。このクワッドツリーの実装はビットツリーとまったく同じなので、これで理解できるはずです。

各リーフに 1 つの値のみを含めることができるウィキペディアの例:

ここに画像の説明を入力

最終的な動きは、これを 3D に拡張することです。以前と同じように、値は の形式になりました(x,y,z)。今回は、値を 4 つの領域に分割する代わりに、値を 8 つに分割します。 -バック、ダウンライトフロント、ダウンライトバック。これを octree と呼びますが、実装は他のものとまったく同じです。

ゼロから論理的に構築する方法に行き詰まっています。その背後にあるロジックは何ですか？2 つのコンテナーを使用しますか? クラスで仮想関数を使用していますか? 子供の部分はどのように機能しますか？

繰り返しますが、バイナリ ツリーを実装するのとまったく同じ方法です。そこで仮想関数を使えば、八分木でも仮想関数を使えます。

于 2012-07-13T12:09:30.663 に答える