プロジェクトの場合、2つの重なり合う楕円体の重なり合う体積を3Dで計算する必要があります。メソッド自体は問題ではありません。基本的に、バウンディングボックス内のランダムなポイントを選択し、それらが両方の楕円体に同時に存在するかどうかを確認しています。
実行時間の観点からプログラムを最適化するという私の終わりのない探求では、より小さなバウンディングボックスが明らかに有利です。現在、「ボックス」は、楕円体の重心の中間点を中心とし、最長の楕円体軸に対応する直径を持つ球です。これは完全に恣意的であり、重複するボリュームは常にこの球に含まれると確信していますが、プロセス全体を最適化する方法を見つけたいと思います。
バウンディングボリュームを最適化するための一般的な方法はありますか？
モンテカルロに固執したい場合の別のアイデアを次に示します。
楕円体を XZ 平面に投影して、2 つの楕円を取得します。外接する四角形の交点を計算して、計算の外接する四角形として使用します。
次に、Y 軸に沿って、境界矩形内の XZ 平面を通して光線を放ちます。各光線について、楕円体との交点を計算し、両方の内側にある光線の長さを計算します。これを変数「hits_length」に追加します。
楕円体の交点の体積は、次の式で概算する必要があります。
hits_length / ray_shot * bounding_rectangle_area
この方法でも、2D 空間をサンプリングしてボリュームを計算しているため、収束が速くなります。
これはCSの問題ではなく、数学の問題ではありませんか? あなたが求めているように見えるのは、2 つの楕円体の重なりの可能性を定義する式です。確かに、その式を使用してコードをより効率的にするつもりですが、私が知る限り、それはコアの質問とは関係ありません。式があり、それをコードとして記述する方法を理解しようとしている場合、それは別の話になります。たぶん、これをhttps://math.stackexchange.com/に投稿することを検討する必要があります
「3D空間で2つの楕円体が重なり合う可能性のある体積を定義する式は何ですか?」という質問を再定義できるように思えますが、それは計算にはまったく関係ありません。
これはおそらくプログラミングよりも数学の問題ですが、2 つの楕円体の交点は凸形状であると考えているため、このような比較的適切に動作するオブジェクトを処理するためにモンテカルロ以外のアプローチを試すことができるかもしれません。
まず、(どういうわけか) 両方の楕円体の内側に点を見つける必要があります。
次に、その点を中心に、両方の楕円体を完全に含むのに十分な大きさの立方体を作成します。3 つの軸すべてに沿って立方体を 8 つの同じサイズのサブ立方体に分割します (八分木を作成する最初のステップ)。
この後、サブキューブに再帰を適用します。両方の楕円体の内側にあるキューブ コーナーとそうでないキューブ コーナーがある場合は、キューブを再度分割します。また、立方体面の一部の領域が両方の楕円体の内側にあり、他の領域がそうでない場合は、再度細分化します。
必要な再帰の深さまで繰り返します。分割された立方体の体積を合計することで、計算エラーを追跡できます。
ここでの難しい操作は、「立方体面の一部の領域が両方の楕円体の内側にある場合」を解決することです。楕円体と平面の交点は楕円です。6 つの立方体面のそれぞれを検査するには、それらを楕円体と交差させ、残りの楕円体が両方とも立方体面と重なっている場合は互いに交差させる必要があります。幸いなことに、2D 楕円-楕円オーバーラップ テストでは、参照をより簡単に見つけることができます...
モンテカルロでは、O(2^n) の労力で n ビットの精度が得られるため、たとえば 24 ビットでは 1670 万サンプルが必要になります。このような分割統治法を使用して形状面に注目すると、24 ビットで約 65,000 である O(2^(n*2/3)) サンプルのみが必要になるはずです。
また、最初の再帰ステップで超過分がすぐに削除されるため、最初のバウンディング ボックス サイズに関する懸念は無関係になります。