Winged-Edgeデータ構造

Winged-Edgeデータ構造（ウイングド・エッジデータこうぞう）とは計算幾何学において多角形モデルを表現するために使用される境界表現(B-rep)である。3つ以上の面が集まり辺を共有しているときに面、辺、および頂点の形状と位相を明示的に表現する。面は交差している辺の本来の方向に対して反時計回りに順序付けられる。さらにこの表現では下に示されているような数値的に不安定な状態も可能になる。

Winged-Edgeデータ構造ではネットワークが明示的に結び付けられているため、面、辺、頂点間を高速にトラバースすることができる。This rich form of specifying an unstructured grid is in contrast to simpler specifications of polygon meshes such as a node and element list, or the implied connectivity of a regular grid.

ここにWinged-Edgeを表現するのに適したデータ構造を載せる。"WE"という略称は"Winged Edge"を表わす。

class WE_Edge {
  WE_Vertex vert1, vert2;
  WE_Face aFace, bFace;
  WE_Edge aPrev, aNext, bPrev, bNext; // 時計回り
  WE_EdgeDataObject data;
}
class WE_Vertex {
  List<WE_Edge> edges;
  WE_VertexDataObject data;
}
class WE_Face {
  List<WE_Edge> edges;
  WE_FaceDataObject data;
}

• en:Quad-edge data structure
• en:Combinatorial maps
• en:Doubly connected edge list
• en:Doubly linked face list

英語版ウィキブックスに本記事に関連した解説書・教科書があります。

The Nature of Subdivision Modeling/Winged Edge Topology

• Bruce G. Baumgart. 1972. Winged Edge Polyhedron Representation.. Technical Report. Stanford University, Stanford, CA, USA.
• Bruce G. Baumgart. 1975. A polyhedron representation for computer vision. In Proceedings of the May 19-22, 1975, national computer conference and exposition (AFIPS '75). ACM, New York, NY, USA, 589-596. DOI=10.1145/1499949.1500071 http://doi.acm.org/10.1145/1499949.1500071 ( Winged Edge Polyhedron Representation for Computer Vision )
• The Winged-Edge Data Structure, on Michigan Technological University
• Winged Edge, on university of Pisa