これまでの設計上の決定について少し背景を説明します... ポイントを格納できる octree 構造を開発しました。特定の基本ボクセル サイズに基づいて、「世代」の再帰を制限することにしました。子ノードは、そのノードにポイントが追加されたときにのみ作成されます。これは動的なグラフィックス アプリケーションではありません。この octree とその中のオブジェクトは静的であるため、パフォーマンスを向上させるための前処理は問題になりません。
ここで、オクツリーに「シェイプ」を追加したいと思います。具体的には、三角形で構成されるサーフェス メッシュです。これらの三角形の頂点は、八分木に格納されている点に対応していません。これらの形状を octree にどのように格納しますか? 2つのオプションが表示されます...
灰色のノードは、形状がないという点で「空」です。代替案 1 では、シェイプが交差するすべてのノードに保存されます。つまり、ノード 1a には shape1 が含まれ、4c と 4d は shape2 を共有します。別の方法 2 では、形状は交差する最小のノードにのみ格納されます。つまり、ノード 1a には形状 1 が含まれ、ノード 4 には形状 2 が含まれます。
私が見た octrees に関するほとんどの投稿は、Alt1 を前提としていますが、その理由は説明されていません。Alt2 は私にとってより理にかなっており、ノード境界に存在する形状に対してのみ余分な作業を作成します。Alt1 が望ましいのはなぜですか?
編集:明確にするために、使用する実装言語は C++ であるため、その言語でのサンプル実装を好みますが、質問は言語に依存しません。タグの使い方が間違っていたらごめんなさい。
Edit2:形状ストレージの問題とは直接関係ありませんが、このリンクには、質問の背後にあるオクツリートラバーサルに関する良い議論があります。この質問に取り組むことに興味のある人なら誰でも役立つかもしれないと思いました。
更新: 4 年後、Alt2 は実装が簡単になりましたが、より高い octree レベルに格納された大きな三角形が octree を走査するたびにテストされるため、非常に遅くなりました。私の場合、それは数百から数千の不要なテストを意味しました。代わりにR*-Tree バリアントを使用するようにコードを修正することになりました。これは実装が簡単で、大幅に高速でした。