四面体の内部にある整数座標を持つすべてのポイントを見つけようとしています (何らかの方法でそれらをループできるようにしたい)。四面体を定義する 4 つの点 (A、B、C、D) の座標を知っています。
私が現在行っていることは、四面体の境界ボックス (A、B、C、D の最小および最大 x、y、z 座標) を見つけて、境界ボックス内のすべてのポイントをループすることです。そのようなすべての点について、重心座標を計算し (ウィキペディアの方程式を使用)、点が四面体の内側にあるかどうかを確認します (いずれかの重心座標が負または 1 より大きい場合、点は内側にありません)。
これを行うより良い方法はありますか？現在、私がテストしているポイント (バウンディング ボックスから) が実際に四面体の内側にある可能性は約 1/6 であるため、不要な計算が多すぎると思います。
より大きなボリュームを三角測量して生成した四面体のリストを使用しています (ボリュームを拡張していて、四面体補間を使用して欠損値を補間したい)。外部ライブラリは使用していません。
あなたのアプローチは正しいものです。いくつかの可能な最適化がありますが、要件に応じて、それだけの価値がある場合とない場合があります。例えば：
特定の点が四面体の内側にあるか外側にあるかを確認する簡単な方法があります。これは、四面体の4つの辺のそれぞれに関して、ポイントがどの半空間に属するかを確認することを意味します。
各辺は3つのポイント（たとえば、A、B、C）で定義されます。その場合、平面法線は（CA）x（BA）（平面内のベクトルの外積）です。この座標が（a、b、c）の場合、平面方程式はF(x,y,z) = ax+by+cz = 0です。与えられた点（x0、y0、z0）に対して、F（x0、y0、z0）の符号は、点が属する半平面を決定します。
重要なのは、四面体の各側の平面の方程式と、「外側」に対応する符号を事前に計算できることです。その後、特定の点のチェックは、最大4つの評価（各側に1つ）を実行することになります。 3回の乗算と2回の加算。
改善のための別のアイデア：
z 軸 (つまり、x=4、y=6) に平行な「棒」が四面体を貫通しているかどうかを確認します。そうでない場合、(x=4, y=5, z) の値は中に入れられません。
それ以外の場合は、ロッドが四面体のエッジと交差する場所を見つけます (四面体のエッジを構成する平面が交差する場所を見つけることによって)。
これらの平面が z=1.3 と z= 10.04 で交差するとします。次に、すべてのポイント (4,5, 2) から (4,5,10) が内側にあることがわかります。
x と y のすべての値について繰り返します。
これにより、ループが 1 つ節約されるため、実際には高速になります。