algorithm - 球とグリッドの高速交差

Question

3D グリッド、球の中心としての 3D ポイント、および半径が与えられた場合、球に含まれる、または球と交差するすべてのセルをすばやく計算したいと思います。

現在、私は球の（グリッド整列された）バウンディングボックスを取り、このバウンディングボックスの最小および最大ポイントの2つのセルを計算します。次に、これら 2 つのセル間の各セルに対して、ボックスと球の交差テストを行います。

もっと効率の良いものがあれば最高です

ありがとう！

Answer 1

円を描くための Bresenham アルゴリズムのバージョンがあります。z=0 の 2 次元の場所を考えて (今のところ、球が 0,0,0 にあると仮定します)、格子点の xy 平面のみを見てください。x= R, y=0 から始まり、y = y_R, x=0 まで Bresenham アルゴリズムに従います。ただし、描画する代わりに結果を使用して、x 座標が低いすべてのグリッド ポイントが円の内側にあることを確認します。 x=x_center に。それらをリストに入れたり、数えたり、メモしたりしてください。2 次元の問題が完了したら、z を変化させ、R の代わりに縮小半径 R(z) = sqrt(R^2-z^2) を使用して、z=R になるまで繰り返します。

球の中心が実際にグリッド ポイント上にある場合、球の右半分の内側または外側のすべてのグリッド ポイントには、左側と同様に上/下にミラー パートナーがあることがわかります。次元ごとのリスト。また、ブレゼンハムを 45 度の線だけに実行する時間を節約することもできます。これは、中心に対する x、y 点にはパートナー y、x があるためです。球がどこにでもある場合、各八分円の結果を計算する必要があります。

Answer 2

球の内側または外側にある個々のセルをどれほど効率的に計算しても、その多くのセルをマークする必要があるため、アルゴリズムは常に O(radius^3) になります。中点 (別名 Bresenham) 円アルゴリズムの DarenW の提案は、sqrt() 呼び出しを回避するために半径の 2 乗を使用して交点を単純にテストできるように、定数倍の速度向上をもたらす可能性があります。

O(r^3) よりも優れたパフォーマンスが必要な場合は、フラット グリッドの代わりにoctreeを使用できる場合があります。ツリーの各ノードは、完全に球の内側、完全に外側、または部分的に球の内側にあるとマークできます。部分的に内側のノードの場合は、最も粒度の細かいセルに到達するまで、ツリーを再帰します。これには、O(r^2 log r) ノード [境界上の O(r^2) ノード、O(log r) がツリーを通過して各ノードに到達する] をマークする必要があるため、アプリケーションの問題。