何千ものクワッドの配列があります。4 辺の 3D ポリゴン。私が知っているのは、クワッドコーナーの座標だけです。
これらの四角形のサブセットは、3D 形状の閉じた外側のシェルを定義します。残りの四角形は、この閉じたソリッドの内側にあります。
どのクワッドがシェルの一部で、どのクワッドが内部の一部であるかを知るにはどうすればよいですか? これはパフォーマンス クリティカルなコードではありません。
編集：シェルの形状に関するさらなる制約
形状自体が交差する場合、これを実装するのは難しいかもしれませんが、サーフェス上にあることがわかっている 1 つの四角形 (重心から最も離れている可能性があります) を見つけることができれば、その周りに四角形の同心円をマッピングします。次に、「反対側」に到達するまで、その外側にあるクワッドの連続リングを見つけます。四角形が交差するか、内部で接続されている場合、それはより困難です。交差するものをバラバラにして、可能な限り滑らかな表面をすべて見つけて、内部容積が最大のものを選びます。
形状が凸状であればかなり簡単にできます。形状が凹状の場合、はるかに難しくなります。
凸の場合、すべての点の平均を計算して重心を見つけます。これにより、次のプロパティが保持される内部にある点が得られます。
重心から四角形の各コーナーに 4 本の光線を投影する場合、2 つの部分に分割されたピラミッドを定義します。一方の部分は形状の内側の空間を含み、もう一方の部分は形状の外側の空間を定義します。
これら 2 つのボリュームは、クワッドが境界上にあるかどうかを確認する決定プロセスを提供します。別のクワッドからのポイントが外側ボリュームにある場合、そのクワッドは境界上になく、内部クワッドとして破棄できます。
編集：上記の説明を見ただけです。形状が凹状であるというより難しいケースでは、次の 2 つのいずれかが必要です。
さらなる編集:あなたが説明しているのは、ポイントの凹型ハルになることに気付きました. この検索ページでいくつかの結果を見てみてください。
これはどう？
四角形の法線ベクトルを計算します (これを「現在の」四角形と呼びます)。そのベクトルと残りのすべてのクワッドで交差テストを実行します。ベクトルの正の部分で別のクワッドと交差する場合、現在のクワッドが内部クワッドであることがわかります。残りのすべてのクワッドについて繰り返します。
これは、四角形が外側に「向いている」ことを前提としています。
すべてのクワッドが密閉された大きな箱の中にあると考えてください。クワッドを 1 つ選びます。レイトレーシングを行います。そのクワッドを光源として扱い、他のすべてのクワッドを反射およびファジーとして扱います。クワッドへのヒットは、その表面からすべての方向に光を送信しますが、コーナーの周りには送信しません。
すべてのノードがヒットする可能性があった後、光線が外部ボックスにヒットしない場合は、そのクワッドを内部として扱います。
凸状の場合、または内部の四角形が外部の四角形とエッジを共有していない場合は、もっと簡単な方法があります。
対処しなければならないクワッドの数を減らすことで、問題をより簡単にすることができる場合があります。
四角形の一部が閉じたシェルを形成していることがわかります。したがって、これらのクワッドはエッジで接続されます。四角形の 3 つの相互に隣接するエッジ (つまり、エッジが閉じたループを形成する) が別の四角形のエッジと重なる場合、これらの四角形はシェルの一部である可能性があります (これらの相互に隣接するエッジは 2D 領域の境界として機能します。その領域をクワッドの「接続面」と呼びます)。これらの「シェル候補」のリストを作成します。ここで、このリストを調べて、別の候補と重ならないエッジを持つ候補 (つまり、エッジがリストにないクワッドのエッジと重なる) を除外します。クワッドを削除できなくなるまで、このカリング プロセスを繰り返します。あなたが残したものは、あなたの殻になるはずです。「非シェル クワッド」を作成する
このシェルの周りにバウンディング ボックス (または球、楕円など) を描画します。ここで、非シェル クワッドのリストを調べて、境界領域の外側にあるクワッドを除外します。これらは間違いなく内部にはありません。
残りの非シェル クワッドを取ります。これらは、形状の内部にある場合とない場合があります。これらの四角形のそれぞれについて、バウンディング シェイプのサーフェスで終わる各面の中心から四角形に垂直な線を引きます。各線をトレースし、線がシェル リスト内のクワッドの「接続された面」を何回通過するかを数えます。この数が奇数の場合、その頂点は形状の内部にあります。偶数の場合、頂点は外側にあります。頂点が内側か外側かに基づいて、四角形が内側か外側かを判断できます。