問題タブ [octree]

点群を接続されていないオブジェクトに分離しようとしています。k-means アルゴリズムを使用してみましたが、すべての作業を行うことはできませんでした。
追加した写真に示されている結果を改善したいと考えています。考えや方向性はありますか？ k-means を使用して分離された私の雲

各リーフ (最も深いノード) が色付きの 3D ポイントを格納する 3D グリッド (スパース octree) があります。オクトリー全体を、OpenGL に直接アップロードできる 3D ポイントの線形配列 (頂点バッファー) に変換したいと思います。

素朴な方法で、octree のすべてのノードを繰り返し処理し、線形配列を埋めることができます。

今、私が直面した問題は、新しい 3d ポイントをスパース octree に追加し、頂点バッファーを更新したい場合、データを OpenGL に取り込むために完全な octree を反復処理する必要があることです。

いくつかのポイントのみが更新/追加されたときに完全な反復を回避する方法を知っている人はいますか?

私が考えることができる唯一のアプローチは、octree のどの要素が追加されたかを記憶し、それらを頂点バッファー配列に直接追加することです。これはうまく機能しますが、octree から要素を削除すると機能しません。

私はc++を使用しています。

10 ポイントから 10 億ポイントの範囲の Octree ベースのコンテナーをメモリに書き込んでいます。ロードされるデータの量が多いため、メモリの消費に注意する必要があります。

すべてが適切に機能し、必要に応じてセグメント化されているように見えますが、挿入時間は非常に遅いです。おそらく、親から子へのデータの再配布が原因です。これを最適化するためにできることはありますか? これを適切に実装しましたか？ポイントの最大量を含めるために各ノードのベクトルを予約することもできますが、これにより必要なメモリが大幅に急増します。

単純な R ツリー タイプのコンテナーを使用すると、約 48 秒で 4 億 6800 万ポイントを読み込んでいます。以下の octree を使用すると、245 秒で読み込んでいます。

軸に沿ったバウンディング ボックス (AABB) のボリューム メッシュを格納するために octree を使用しているアプリケーションがあります。

水密な三角形メッシュが与えられた場合、次のことを行う必要があります。

• AABB がサーフェス メッシュと交差しているか、完全にサーフェス メッシュの内側/外側にあるかを確認します。

• 交差した AABB でサーフェス メッシュをクリップして、各 AABB 内に完全に収まる三角形を生成します。

三角測量と AABB を含む octree はどちらも動的です。octree のリーフ ノードの数は膨大です。サーフェス メッシュ内の三角形の数ははるかに少なくなります (O(10^9 - 10^13) 個の octree ノードに対して、O(10^6) 個の三角形)。

問題に適したデータ構造とアルゴリズムはどれですか?

今私は：

• 三角形をボリューム メッシュと同じ octree に格納し、
• 各三角形をそれを含む最小の八分木ノードに格納し、
• AABB からルート ノードとそのリーフの両方にトラバースして、ノードに含まれる各三角形を AABB でクリッピングすることにより、単一の AABB で三角形メッシュをクリッピングします。

リーフが AABB 内に完全に含まれるまでのノード内の三角形はクリッピングを必要としませんが、AABB からルートまでのノードに含まれるものはクリッピングが必要です。でも：

• 三角形を格納する方法が原因で、各 octree ノード内に格納できる三角形の最大数に上限がないため、必要な三角形の数に上限がありません。単一の AABB でサーフェス メッシュをクリッピングするときにクリッピングされます。

• 三角形がルート ノードに格納されている場合、AABB が三角形メッシュと交差しているかどうかをテストするには、クリッピングが必要になる場合があります。

• ノードがメッシュの内側/外側/交差しているかどうかをすばやく判断する方法はありません。

オクトリーがあり、そのブランチで検索されたノードを削除する必要があります。プログラムはノードを見つけることができますが、削除するのに苦労しています。Octree のオブジェクトを作成し、いくつかのノードを作成しますが、それらを削除しない場合、デストラクタは Octree を削除します:

しかし、この方法で具体的なノードを削除したい場合は、

デストラクタが呼び出された後に例外が発生しました。スローされた例外: 読み取りアクセス違反。ノードは 0x4 でした。

私は段階的にデバッグしていて、いくつかの奇妙なものを見つけました。ノードを作成するときは、次のようにします。

値を設定しても問題ありません。ノードの値は xvalue で、子は NULL です。しかし、deletebranch() メソッドでそのノードを削除した後、私のノードはこのように変更されました。

• n 0x00500788 {値=0 子=0x0050078c {0x00000004 {値=??? child=0x00000008 {???, ???, ???, ???, ???, ...} }, ...} } Octree::node * 値 0 int
• 子 0x0050078c {0x00000004 {値=??? child=0x00000008 {???, ???, ???, ???, ???, ???, ???, ???} }, 0xfdfdfdfd {...}, ...} オクトリー::ノード *[8]
• [0] 0x00000004 {値=??? child=0x00000008 {???, ???, ???, ???, ???, ???, ???, ???} } Octree::node *
• [1] 0xfdfdfdfd {値=??? child=0xfdfdfe01 {???, ???, ???, ???, ???, ???, ???, ???} } Octree::node *
• [2] 0xdddddddd {値=??? child=0xddddddde1 {???, ???, ???, ???, ???, ???, ???, ???} } Octree::node *
• [3] 0x29122f71 {値=??? child=0x29122f75 {???, ???, ???, ???, ???, ???, ???, ???} } Octree::node *
• [4] 0x0000a9bd {値=??? child=0x0000a9c1 {???, ???, ???, ???, ???, ???, ???, ???} } Octree::node *
• [5] 0x004d5228 {value=5249384 child=0x004d522c {0x005007a0 {value=5067304 child=0x005007a4 {0x004fe218 {...}, ...} }, ...} } Octree::node *
• [6] 0x004fe218 {値=5244832 子=0x004fe21c {0x004d00c4 {値=5235224 子=0x004d00c8 {0x00501968 {...}, ...} }, ...} } Octree::node *
• [7] 0xdddddddd {値=??? child=0xddddddde1 {???, ???, ???, ???, ???, ???, ???, ???} } Octree::node *
• this 0x0043f818 {root=0x005006b0 {value=0 child=0x005006b4 {0x00000000 , 0x00000000 , 0x00000000 , ...} } } オクトリー *

ノードを削除した後にノードを変更したことがないため、その理由が本当にわかりません。そして、それがデストラクタでその例外を受け取った理由だと思います。ノードを削除するにはどうすればよいですか? たぶんキャッチしてみてください？

ヘッダーファイルは次のとおりです。

Octree データ構造を作成しましたが、まだ完全ではありません。コピー コンストラクタとデストラクタに苦労しています。これが私のヘッダーファイルです：

コンストラクタ、デストラクタ、コピー コンストラクタ

そして、メインでオブジェクトを作成する方法は次のとおりです。

このsearchandset関数では、最初のツリーでノード番号 8 の値を指定しています。その後、コピー コンストラクターを呼び出して、2 番目のツリーの 8 番目のノードを出力します。値は最初のツリーに指定したものと同じですが、デストラクターが呼び出されると、常に次の例外が発生します。

スローされた例外: 読み取りアクセス違反。ノードは 0xDDDDDDDD でした。

私が知っているように、すでに削除したノードを削除しようとしたことを意味します。オブジェクト「tree2」は、同じ値とノードを持つ「tree」とは別のオブジェクトですよね? 次に、上記の例外がわかりません。私はC ++が初めてで、それが基本的なものであることを知っているので、誰かが私を正しい方向に向けてくれれば、とても感謝しています.

点群の最近傍を取得しようとしていますが、何らかの理由で範囲外のベクトル添字を取得しています。デバッガーを使用して範囲外になった原因を調べてみたところ、すべての値が正常に見えます。

これは私が使用しているコードです（公式ドキュメントから取得しました）