half-edge 構造を C++11 で実装するメモ

背景

• てっとりばやく三角形, 四角形, or 多角形が混在するポリゴンメッシュにたいして half-edge 構造を求めるコードがほしい
  • たとえばポリゴンの面の隣接を求めたい. 自前で subdivision surface を実装したい
  • libigll では隣接を求める機能があるが, 三角形のみで四角形は対応していない https://github.com/libigl/libigl/blob/master/include/igl/adjacency_list.h
  • embree では四角形(subdivision surface patch)の half-edge を求めるのはできるが, 三角形は無い...
  • CGAL https://www.cgal.org/ はコンパイルがめんどくさすぎる
• 学校の授業(e.g. 中学生幾何)で half-edge 構造を実装する課題が出ていて, 明日までに実装しないといけない.

情報

実装　

にあげました. エラー処理などもしているので 400 行くらいありますが, 賞味量としては 100 ~ 150 行くらいでしょうか.

tinyobjloader,

春到来! TinyObjLoader で始めよう waveront .obj モデルローディング(2016 年版)
https://qiita.com/syoyo/items/bfe45d1bcbd0ab4a125c

で .obj モデルを読んで half-edge 計算する example 付きだよ.

half-edge ではトポロジのみ必要なので, 頂点データ(頂点座標データ)は不要です.

今回の実装では right-handed, CCW(counter-clockwise) で頂点が定義されているものとし, v0 -> v1 -> v2, ... v(N-1) -> v0 順に辿って面(face)の edge の計算をします.

C++11 実装方針

ナウでヤングな若人さまにおかれましては, C++11 が普通かと思います.

half-edge の実装方法はいくつかありますが, ここでは一番楽な map(or unordered_map)を使います.
特に C++11 だと, 基本型の hash が標準でもとまるので, edge(二つの頂点 id)から hash を求めるというのが楽にできますし, std::unordered_map で std::map よりは効率的な処理ができると想像できます.

エッジの頂点でルックアップするのは

std::unorderd_map<std::pair<uint32_t, uint32_t>, XXX>

と書くことできます. ただ, この場合明示的に std::pair<uint32_t, uint32_t> からハッシュ値を求める関数オブジェクトを提供しないとコンパイルエラーになります.

俺のunordered_mapがこんなにpair型をキーにできないわけがない
https://qiita.com/ganariya/items/df35d253726269bda436

今回は std::pair を使いましたが, std::tuple を使うなどもできるでしょう.

古典的(?)な教科書などでの C/C++ half-edge 構造実装はポインタを使っていますが, 昨今生ポインタを使う必要もないし, バグも出やすいのでインデックスベース(64bit int)で実装します.

インデックスベースであれば, 他の言語に移植したり, また将来的に GPU などで hald-edge データ構造を使って mesh processing という課題が授業で出た時にも対応しやすくなります.

実装のこまかいところなど

反対側の half-edge(反対向きの edge)は, いくらか呼び名がありますが,

• opposite
• twin
• pair

どれも意図は同じです.

あと, HalfEdge には, prev でひとつまえの HalfEdge を持たせたり, vertex へのインデックスを持たせたりといくらかバリエーションがあります. 今回の実装は最低限なので, 必要に応じて変数追加するなりしましょう.

制限事項

行儀のよい形状(トポロジ)が入力されるのを想定しています.

点や線(頂点数 1 or 2 の面)の形状は扱えません. この場合はエラーを出します.

異なる面が同じ向きを持つエッジ(v0 -> v1)情報を持つトポロジは扱えません. この場合はエラーもしくは結果がおかしくなります.

たとえば

indices = [0, 1, 2, 0, 1, 2]
face_counts = [3, 3]

のように異なる面が同じ face id を持つときや, トポロジ的に裏表が混在する状況など(この場合はあんまり正しくない状態のはず?). 頑張って作るとなると, face の id や half-edge の prev/next も見て一意性を判断となるでしょうか.

トポロジ

や,

の non-manifold geometry にあるような形状はうまく扱えません
(half-edge 構造自体は作れると思うが, そのあとの構造を使っての隣接関係の検出などが面倒 or 無理になる)

考察

とりあえず half-edge を実装してみましたが, 昨今の豊富な計算資源(マルチスレッド, GPU, メモリ)と, 大規模なメッシュが入力されるケースの場合は, より富豪的かつ効率的なデータ構造があるような気もしますね.

また, 近似で隣接関係を求めたいだけであれば, half-edge を作らず kd-tree や BVH という手もあります.

TODO

• 構築した half-edge 構造が正しいか, visualize する
• マルチスレッド対応
• robin-map https://github.com/Tessil/robin-map で速くなるか試す.
• 64bit の vertex index, edge index に対応する
  • ハッシュ値は 64bit のままなので, ハッシュ周りでいくらか効率は落ちるかもしれない(128bit int にする手もあるが, C++11 標準では int128_t は無い)