私は三角メッシュを持っています。でこぼこした表面のように見えると仮定します。メッシュの周囲の境界にあるすべてのエッジを見つけられるようにしたいと考えています。(内側の頂点は忘れてください)
1 つの三角形にのみ接続されているエッジを見つけて、これらすべてをまとめる必要があることはわかっています。それが答えです。ただし、これらのエッジの頂点が形状の周りで時計回りに並べられていることを確認したいと思います。
これをやりたいのは、メッシュの外側に多角形の線を引きたいからです。
これが理解できるほど明確であることを願っています。ある意味で、私はメッシュを「De-Triangulate」しようとしています。ハ！そんな言葉があれば。
境界エッジはメッシュ内の単一の三角形によってのみ参照されるため、それらを見つけるには、メッシュ内のすべての三角形をスキャンし、単一の参照カウントでエッジを取得する必要があります。O(N)ハッシュ テーブルを使用することで、これを効率的に ( で) 行うことができます。
エッジ セットを順序付きポリゴン ループに変換するには、トラバーサル メソッドを使用できます。
[v_start,v_next]を選択し、これらの頂点をポリゴン ループに追加します。[v_i,v_j]または のいずれv_i = v_nextかを持つ未訪問のエッジ セグメントを見つけ、もう一方の頂点 (と等しくないもの) をポリゴン ループにv_j = v_next追加します。この新しく追加された頂点としてリセットし、エッジを訪問済みとしてマークし、2 から続行します。v_nextv_nextv_startます。走査により、時計回りまたは反時計回りの順序を持つポリゴン ループが得られます。多角形の符号付き面積を考慮することで、一貫した順序を確立できます。トラバーサルの結果が間違った方向になった場合は、ポリゴン ループの頂点の順序を逆にする必要があります。
ことわざにあるように、「うまくいくように」、「うまくいくように」ということです。上記の例では、エッジ配列内のすべてのエッジが実際に素敵な境界線でリンクされていると想定していることに気付きました。これは現実の世界では当てはまらないかもしれません (私が使用している入力ファイルから発見したように!) 実際、私の入力ファイルのいくつかには実際には多くのポリゴンがあり、すべての境界線を検出する必要があります。また、巻き順が正しいことを確認したかったのです。だから私もそれを修正しました。下記参照。（やっと前進した感じ！）
private static List<int> OrganizeEdges(List<int> edges, List<Point> positions)
{
var visited = new Dictionary<int, bool>();
var edgeList = new List<int>();
var resultList = new List<int>();
var nextIndex = -1;
while (resultList.Count < edges.Count)
{
if (nextIndex < 0)
{
for (int i = 0; i < edges.Count; i += 2)
{
if (!visited.ContainsKey(i))
{
nextIndex = edges[i];
break;
}
}
}
for (int i = 0; i < edges.Count; i += 2)
{
if (visited.ContainsKey(i))
continue;
int j = i + 1;
int k = -1;
if (edges[i] == nextIndex)
k = j;
else if (edges[j] == nextIndex)
k = i;
if (k >= 0)
{
var edge = edges[k];
visited[i] = true;
edgeList.Add(nextIndex);
edgeList.Add(edge);
nextIndex = edge;
i = 0;
}
}
// calculate winding order - then add to final result.
var borderPoints = new List<Point>();
edgeList.ForEach(ei => borderPoints.Add(positions[ei]));
var winding = CalculateWindingOrder(borderPoints);
if (winding > 0)
edgeList.Reverse();
resultList.AddRange(edgeList);
edgeList = new List<int>();
nextIndex = -1;
}
return resultList;
}
/// <summary>
/// returns 1 for CW, -1 for CCW, 0 for unknown.
/// </summary>
public static int CalculateWindingOrder(IList<Point> points)
{
// the sign of the 'area' of the polygon is all we are interested in.
var area = CalculateSignedArea(points);
if (area < 0.0)
return 1;
else if (area > 0.0)
return - 1;
return 0; // error condition - not even verts to calculate, non-simple poly, etc.
}
public static double CalculateSignedArea(IList<Point> points)
{
double area = 0.0;
for (int i = 0; i < points.Count; i++)
{
int j = (i + 1) % points.Count;
area += points[i].X * points[j].Y;
area -= points[i].Y * points[j].X;
}
area /= 2.0f;
return area;
}
トラバーサル コード (効率的ではありません - 整理する必要があります。ある時点でそれに到達します) 注意:ダレンが提案する 1 つではなく、チェーン内の各セグメントを2 つのインデックスとして保存します。これは純粋に私自身の実装/レンダリングのニーズのためです。
// okay now lets sort the segments so that they make a chain.
var sorted = new List<int>();
var visited = new Dictionary<int, bool>();
var startIndex = edges[0];
var nextIndex = edges[1];
sorted.Add(startIndex);
sorted.Add(nextIndex);
visited[0] = true;
visited[1] = true;
while (nextIndex != startIndex)
{
for (int i = 0; i < edges.Count - 1; i += 2)
{
var j = i + 1;
if (visited.ContainsKey(i) || visited.ContainsKey(j))
continue;
var iIndex = edges[i];
var jIndex = edges[j];
if (iIndex == nextIndex)
{
sorted.Add(nextIndex);
sorted.Add(jIndex);
nextIndex = jIndex;
visited[j] = true;
break;
}
else if (jIndex == nextIndex)
{
sorted.Add(nextIndex);
sorted.Add(iIndex);
nextIndex = iIndex;
visited[i] = true;
break;
}
}
}
return sorted;