ハーフエッジデータ構造について学び、CGALというライブラリを用いて実装し図形をいろいろ構成してみたので、本記事にて紹介する。

レンダリングのためのデータ構造

OpenGLなどグラフィクスAPIでひとまず図像を出力したい場合、頂点座標の配列と、その頂点をどういった順番でつなげて図形(点・線・面)をつくるかを表現するインデックスの配列が必要となる。これらをAPI側にカメラ視点を表現する行列とともに転送してやればCG図像としての2次元のピクセル配列に出力できる。(シェーディングのため、法線情報も必要ではあるが、このデータはモデリング段階でなくとも、レンダリングのプロセスの中でも頂点とインデックスさえわかれば簡単に計算できる。)これはポリゴン法、ポリゴンモデルと呼ばれ、面は三角形で統一されるのが一般的だ。plystlはこのデータ構造をそのまま構造どおりに記述している。このデータ構造は、レンダリングのみに必要最低限のものであり単純明快だ。とはいえ、なにか図形の変形操作をしたい場合、より良いデータ構造の必要性が出てくる。ポリゴンモデルだけでは、頂点のまわりにある面を列挙したい、とか、ポリゴンの辺を列挙したいといった割と初歩的なニーズに答えるのにも、冗長な実装が必要になってくる。

CADのためのデータ構造

幾何操作の実用的な例は、CAD・モデリングソフトにおいて標準実装されているような機能がわかりやすい。DCCアプリのユーザであれば、エッジのベベル、面の押し出し(エクストルード)、ブーリアン演算などが思い浮かぶと思う。しかし、そのどれもに頂点と面以上の情報が必要になってくる。こうした課題に対して基本的な道具となるのがハーフエッジデータ構造である。ハーフエッジデータ構造の詳細を論じることは、自分の能力に及ばないし目的ではないので以下などの優れた解説を参考されるのが良い。

上記を読むと、ハーフエッジデータ構造によって、抽象的な数学概念もうまく実用における具体的な表現に落とし込んでおり、データ構造として優れていることがわかる。
少しだけかいつまむと、

という感じ。自分も最初は「ん??」となり理解するまで少しかかったが、理解したとたんその構造の妙に驚く。ハーフエッジのクラスは2つのハーフエッジへのポインタと、1つの頂点、1つの面へのポインタをもつだけの構造体で非常にシンプルにかける。頂点、面に加え辺を列挙できるし、一番の恩恵は、頂点・辺・面そのすべての「隣接関係」も、ポインタをたどれば構造的に得られることだ。

とはいえ、このデータ構造を知り実装したところで、過去の先人が発明・発見した面分割アルゴリズムや、CADで必要とされる基本的なサーフェスの変形操作を実装するには、まだまだ長い隔たりがある。線分、面の交差判定を基本的に伴い、検索・ソートなどの計算効率と戦うかなり込み入った実装が必要になってくる。

ハーフエッジデータ構造とCAD用ライブラリ

HE_MESH

Frederik Vanhoutte (wblut) 氏がハーフエッジデータ構造と高度な幾何操作をProcessing上で実装したライブラリHE_MESHは優れた実装の例だ。モディファイアというクラス(命名をBlenderに寄せてるのも良い)から派生したベベルやエクストルード、頂点数削減、面分割アルゴリズムなど様々な高度なCAD系のアルゴリズムを提供している。個人的にはProcessingというプラットフォームで簡便な記法でAPI提供されているということは非常に意義があることに感じる。

CGAL

C++においてはCGALがおそらく提供されるアルゴリズムとしては豊富だ。GUIによる出力はツールとしてではなく、ソフトウェアに組み込まれる前提のいわゆるライブラリなので、自身のプロジェクトに組み込むことができる。ハーフエッジデータストラクチャーをBoostやStlといった堅牢なテンプレートライブラリによって実装している。また、図形(だいたいは多面体のサーフェス)オブジェクトから、頂点、面、辺などを標準コンテナで取り出しイテレートできるので捗る。

ものづくりをするきっかけがopenFrameworksだったということもあり、C++での結合を念頭にしていたためにCGALをすぐ検討した。しかしながら、CGALというライブラリはProcessing由来のノンプログラマに敷居を低くしたような思想とは180度発想が異なり、研究用途の厳密な数値計算を念頭におかれている。例えば、計算精度を指定するためのKernelがテンプレート引数にとれ、これを許容することで、多面体テンプレートのベクトルテンプレートのKernelテンプレートの…というようにかなり深いテンプレート構造の異常に長い名前のクラスが爆誕する。これをusingで置換したりautoを使って記述を減らすという感じだが、深いテンプレートに起因するデバッグのしずらさや機能する条件などが分かりづらくなり、計算幾何の初歩レベルの人間が入門するにはなかなか難しいライブラリだと言わざるをえない。辛い。しかし、アルゴリズムの理解やコーディング能力が熟達したときにかなりの可能性を秘めていると言い換えることもできる。

それ以外も多様なライブラリがあり、OpenMesh, OpenSCAD, Libiglあたりはキーワードとして挙げておく。このような分野は広く計算幾何Computer Geometry)の一部だ。

ハーフエッジデータ構造を活用して図形生成してみる

CAD系の操作はDCCアプリケーションとしてゲームエンジン系のアプリケーションとは切り分けて実装されているが、C++で必要最低限のCAD系機能のリアルタイム用途の実装というものをやってみようと思い、前述のCGALをC++ライブラリとしてビルドしてoFのプロジェクトとしてインポートした。3Dプリンティングとしての出力などはあまり考えず、単純に多様な図形処理の引き出しをふやしたいのと、CAD的な図形操作の理解を深めたいという動機でハーフエッジデータ構造および若干の幾何操作アルゴリズムを実装した。openFrameworksとCGALをブリッジするアドオンofxCgalUtilを制作、公開しているので、下の実装が気になった方は、ぜひ覗いてみてほしい。

5角形面の分割

5角形は通常3つの三角形で表現されてしまうが、各面の中心から対称に分割するということを、ハーフエッジ構造から面を取り出し、5角形の各辺ごとのループすることで実現した。あまりハーフエッジにこだわらずにも実装できたかもしれない。

ブーリアン演算

CGALのNef PolyhedronというCSG(Constructive Solid Geometry)に特化したデータ構造を用いて実現。CGALのNefPolyhedronは+,-,*,!といった論理・算術演算子をオーバーロードしているため、CSG表現を抽象的にかける。ジオメトリ生成時の計算負荷は高い。余談だが単純に画面に出力したいだけであれば、レイマーチなどで可視化できるSDF(Signed Distance Function)でやるほうがエレガントだし今っぽいとは常に感じてしまうものの、自分が結構ポリゴンのレンダリングの質感にこだわっているのでこれはこれでやりたかった。

以下のようなコードを書くと、

下記のような図形が得られる。

これを回転させるとこうなる。

View this post on Instagram

 

A post shared by Ayumu Nagamatsu (@ayumu_naga) on

エッジの切断(ベベル)

頂点もしくは辺を切るアルゴリズム。ハーフエッジ毎にイテレーションし、法線に直行する平面で多面体を切断することでエッジでの切断を実現した。しかし、面で切るたびに頂点数が増え、さらにまたポリゴンと面の交差判定を含むアルゴリズムを実行するため、ジオメトリ生成時の計算負荷が非常に高く現状実用性に乏しい…。

エッジからのボクセル構成

ハーフエッジ毎のイテレーション中にボクセルを逐次追加することでできる図形の例。ボクセルをエッジ方向に追加していく。また辺の法線でボクセルの向きを計算できる。

エッジベースの面分割

辺から面を増やしていくようなアルゴリズムを再帰的に実行すると以下のような図形が得られる。再起を適用できるルールをつくる上で、ハーフエッジデータ構造は若干扱いが難しい点がある。辺の重複や面倒しの重なり(自己交差)があるとハーフエッジデータ構造はうまく動かない点だ。(描画するだけなら、多少の面の交差なりを許容できするしそのほうがおもしろい図形ができたりする)

条件によって、面の重なりをなくせるため3Dプリンターでも出力できると思われる。のでSketchFabに類例をアップロードしてみた。

最後に

コードベースで(とくにポリゴン法)でなにか形やパターンを得ようとすると、しばし発想が三角ポリゴン単位にとらわる。ハーフエッジデータ構造を知ると、多角形を扱うことがより容易になったり閉じた多面体を得るために便利な考えを導入できる。ただこのコンセプト自体で図形の発想の幅が広がったかは定かではない(むしろ発想が狭まるとも…)。それ以上に、特に恩恵があるのはブラックボックスに感じられた幾何アルゴリズム(ポリゴン削減や再分割アルゴリズム)を考えるきっかけにはなったことは個人的に意義深いのでよしとする。