みたにっき@はてな

三谷純のブログ

Halfedgeの参照頂点は後ろか前か

ポリゴンモデルのデータ構造の1つにHalfedge Structure(ハーフエッジ構造)というものがあって、私自身のプログラムでもよく使っています。

次の図は、私が学生のころにtgifで作った説明図(なつかしい!)。

Halfedgeには始点と終点があるのですが、データ構造としては始点の頂点の参照を保持するようになっています。

一方で、終点(矢印の先)の頂点の参照を保持させる、というデータ構造を採用するケースもあるようです。

もちろん、どちらでも問題ありません。


でも、長年にわたってHalfedgeが始点の頂点を参照する実装を使っていたので、終点の頂点を参照するデータ構造のプログラムコードを見ると、ちょっと戸惑います。


で、どっちが主流なのかなと思って調べてみました。


■ 終点(矢印の先)を参照するデータ構造を採用している例
CGAL該当箇所
OpenMesh該当箇所
The Half-Edge Data Structure by Max McGuire

■ 始点を参照するデータ構造を採用している例
Hisui(株式会社カタッチ)該当箇所
東京大学 鈴木宏正先生の講義スライド:ソリッドモデリングとCADの基礎 28ページ
・齋藤満昭, 多重解像度Marching-Cubes法 (PDF)


というわけで、(サンプル数が非常に少ないですが)見事に日本と海外で別れましたw( ̄o ̄)w
国内は、東京大学鈴木宏正先生の研究室の流派かな、という気がします(私もそうです)。同じく鈴木研究室出身の金井崇先生も、たぶん、始点を参照する派だったと思います。記憶が定かではないですが、勉強会で読んだ Martti Mantyla. "An Introduction to Solid Modeling. Computer Science Press", 1988に載っていた実装方法が原点と思います。

ただ、現在の普及率からすると、終点を参照する方が主流なのかなぁ、と感じました。

ちなみに、Mario Botschらの"Polygon Mesh Processing"でも、終点を参照する方法が紹介されています。


(追記 2012.2.21)
Brown 大学のGabriel Taubin氏の講義資料では始点を参照しています。
http://mesh.brown.edu/3dpgp-2007/pdfs/02-HalfEdge.pdf


Ryan Holmes氏のDCEL(Doubly-Connected Edge List)の実装でも始点を参照しています。
http://www.holmes3d.net/graphics/dcel/


Xianfeng Gu氏のHalfedge Mesh Libraryの実装でも始点を参照しています。
http://www.cs.sunysb.edu/~gu/software/MeshLib/index.html


ちなみに、対になるHalfedgeへの参照の変数名は mate, pair, twin, opposite など様々です。