私の答えは閉じたメッシュでのみ機能しますが、凹穴と凸穴の場合に対応します。
説明のために、2Dメッシュを想像してみましょう。
メッシュのバウンディングボックスを計算します。この例では、バウンディングボックスに、X軸とY軸の最小値と最大値、および各値に対応する頂点インデックスを格納する必要があります。
struct BoundingBox
{
float minX,maxX,minY,maxY;
int vminX,vmaxX,vminY,vmaxY;
}
メッシュ内のすべての頂点を反復処理し、各ポイントを追加するときにバウンディングボックスを拡大します。頂点が最小/最大値の1つを変更する責任がある場合は、対応するvmin/vmax値を頂点メッシュインデックスで保存または上書きします。
例えば
BoundingBox bounds;
bounds.minX = verts[0].X;
bounds.maxX = verts[0].X;
bounds.minY = verts[0].Y;
bounds.maxY = verts[0].Y;
bounds.vminX = bounds.vmaxX = bounds.vminY = bounds.vmaxY = 0;
for (int i = 1; i < numVerts; i++)
{
Vertex v = verts[i];
if (v.X < bounds.minX) { bounds.minX = v.X; bounds.vminX = i; }
if (v.X > bounds.maxX) { bounds.maxX = v.X; bounds.vmaxX = i; }
if (v.Y < bounds.minY) { bounds.minY = v.Y; bounds.vminY = i; }
if (v.Y > bounds.maxY) { bounds.maxY = v.Y; bounds.vmaxY = i; }
}
次に、境界ボックスに収集したすべての頂点を含む境界が見つかるまで、境界を繰り返し処理します。これがあなたの外側の境界です。残りの境界はメッシュ内の穴です。