IT用語集 › プログラミング › ウィングドエッジ

ウィングドエッジ

プログラミング Svenska → 更新: 2026-10-26

各辺が、2つの頂点、隣接する2つの面、そして近傍の4本の辺を覚えている、古典的なポリゴンメッシュのデータ構造。

メッシュを三角形のリストとして持つだけだと、「この辺を共有する面はどれか」という問いに答えるのが高くつく。全体を探索しなければならないからだ。1972年にBruce Baumgartがスタンフォード大学の学位論文で導入したウィングドエッジは、位相情報をすべて辺に持たせる。辺の両端の頂点、辺が隔てる2つの面、そして辺の両端から翼のように伸びる4本の辺である。これで隣接関係の問い合わせは定数時間になる。

代償はメモリと管理の手間で、編集のたびに多くの相互参照を矛盾なく更新しなければならない。その後に現れたハーフエッジ(向きを持つ半辺)やクワッドエッジといった構造は走査を単純にし、今日のモデリングツールやメッシュ処理の主役になっている。それでも、任意のトポロジーを扱えるようにした最初の構造はウィングドエッジだった。

← 用語集に戻る