私はエンジンに動的オブジェクトのフラスタムカリングを実装しており、「ルーズオクツリー」についてできる限り読んでいます。残念ながら、ほとんどのソースは非常に曖昧であり、実際には、O(1) の挿入と削除を行ったが、その背後にあるロジックについては説明していない、彼らがどれほど優れているかを述べている人々の投稿がたくさんあります。
オクタントは実際よりも大きいものとして扱われ、緩い係数は最大 2 になるという主な原則を理解しています。これは、オブジェクトをそのサイズに基づいて単一のノードに挿入できることを意味します。問題は、記事の多くが 2 の「k-factor」を使用していないことです (おそらくよりぴったりとフィットさせるため)。したがって、高速な挿入/削除が失われます。代わりに、隣接構造を維持するため、特定の深さですべてのノードをトラバースし、各ノードでオブジェクトの中心をテストできます。
大まかなカリング テストが必要なだけで、O(1) の挿入時間が必要であり、オブジェクトを挿入する深さ (レベル) を計算するための式を作成しました。ただし、オブジェクトのサイズと位置から正確なノードを計算する式について説明している記事は見つかりません。
アルゴリズムを完全に誤解していて、不可能なものを探していますか? 誰かが私に良い論文や記事を教えてくれたら (私はhttp://tulrich.com/geekstuff/を読みました)、それは素晴らしいことです。
PS 1D 配列に格納された線形 octree を使用していることに言及する価値があるかもしれません
助けてくれてありがとう