軸に沿ったバウンディング ボックス (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 が三角形メッシュと交差しているかどうかをテストするには、クリッピングが必要になる場合があります。
ノードがメッシュの内側/外側/交差しているかどうかをすばやく判断する方法はありません。