2

8 つのコーナーが球の内側にあるかどうかを個別にテストするよりも、軸が整列した立方体が球の内側にあるかどうかを確認するより速い方法はありますか?

立方体の葉が交差しているか、球体に囲まれているかどうかをチェックするオクツリーを歩いています。ここで交差点の方法を見つけました: Cube sphere Intersection Test?

囲い込みをテストするためのより効率的な方法を見つけたいと思っていました。最終的に必要なのは、次の 3 つの状態のいずれかを返すテストです。

  1. 球の外側
  2. 交差球
  3. 球の内側

立方体は 2 点で定義され、球は中心点と半径で定義されます。

4

2 に答える 2

3

立方体が完全に球内にあるかどうかを確認するには、1 つの頂点 (球の中心から最も遠い頂点) だけをテストするだけで済みます。立方体と球体の中心点を比較することで、テストする頂点を決定できます。たとえば、 に中心が(cx,cy,cz)あり、エッジの半分の長さが である立方体と、半径がlである の球がある場合、テストする点は次のようになります。(sx,sy,sz)r

tx = cx + ( cx > sx ? l : -l );
ty = cy + ( cy > sy ? l : -l );
tz = cz + ( cz > sz ? l : -l );

ただし、球に対して立方体の角をテストしても、交差のすべてのケースを検出できるわけではありません。(-5,-5,-5) から (5,5,5) までの立方体と (0,0, 6) 半径 2 の場合。2 つのボリュームは交差しますが、球の内側に頂点はありません。

私はマルチパスアプローチに行きます：

  1. 立方体に対する球の軸に沿った境界ボックスをチェックします - 明らかに交差していないケースを迅速に拒否する非常に簡単なチェックです。
  2. 球の中心がキューブ内にあるかどうかを確認します
  3. お使いのシステムではこの可能性が排除されている可能性がありますが、球体が完全にキューブ内にある場合は、バウンディング ボックスのチェックも行う必要があります。
  4. この時点で、先に進んで球体と立方体の面の間の交差を確認する以外に選択肢はほとんどありません。

ただし、八分木をたどる目的で、球を軸に沿ったバウンディング ボックスとして扱い、小さな誤検知率を受け入れたいと思うでしょう。これが完全に正しい交差結果を得るよりも速いことを知っても、まったく驚かないでしょう。

于 2013-08-16T07:54:44.090 に答える
0

立方体の中心から球の中心までの距離を測定できます。立方体の対角線の長さと球の半径を合わせて、立方体が球の内側にあるかどうかを判断できます。

于 2013-08-15T10:55:20.543 に答える