2013年06月23日

計算幾何学の勉強 その1

点群からメッシュ作成を何となく自分でやってみたくなったので[1]を買ってきました。
自分でやらずに既存のライブラリを使った方が速くて良いものができると思います。

本から式とかアルゴリズムって引用していいんでしょうか。
とりあえず引用なしで書いてみます。

1章

凸包を計算する場合、点群から構成される全ての直線において、直線以外の全ての点に対して左側に折れるか折れないかをチェックしていって、全て左側に折れなければその直線は凸包を構成する直線である、ということだそうです。
確かに直線から見て左に折れない、ということは一番外側の直線なのでそうなるみたいですね。
左側にあるかどうかは、直線を構成する2点p1, p2と、それ以外のある点p3からつくることができる行列の行列式が0より大きければ左側に折れ、0以下の場合は左側に折れないそうです。

実行結果

geometry_001.png

適当な7点でやってみましたが、同一直線状の3点など退化した状態ではうまくいかない場合があるようです。
2章ではその対策として、整数帰着法と記号摂動法というものを使った超ロバスト計算原理が説明されています。

実行結果

geometry_000.png

読んでもわからないところは適当に実装したので合っているのかどうかわかりませんが、一応直線状にある場合でも凸包が計算できました。

3章は省略

4章 ボロノイ図とドロネー図

三角形分割などでよく聞く名前ですね。
まずはある3点p1, p2, p3とある1点pに対する関数Gを定義しています。
このGが0の場合は3点p1, p2, p3が作る円上に点pがあり、G<0の場合は内部に点pが存在するそうです。

実行結果

geometry_002.png

黒が3点で構成される三角形で、画像上の画素に対してG≦0のところを赤、それ以外を白にしています。
また、3点から計算できるボロノイ点(円の中心)を緑色の点で表し、そこから三角形への垂直二等分線を青色で表示しています。

とりあえず3点だけの場合はできたので、これから点が増えた場合のボロノイ図の作り方を試していきたいと思います。

[1] 杉原厚吉著,“計算幾何学”,朝倉書店,2013
web拍手 by FC2
posted by シンドラー at 02:10 | Comment(0) | TrackBack(0) | Computational Geometry | このブログの読者になる | 更新情報をチェックする

2013年06月13日

法線ベクトルとスムージング角度について

メタセコのモデルを使っているときに、法線ベクトルのデータがないので自分で用意する必要があります。
基本的に、面の法線ベクトルを外積を使って計算して、頂点の法線ベクトルはそれを面積や角度に応じた加重平均で求めることができるようです[1]。

以前どこかの掲示板?で、頂点の法線ベクトルは、面の法線ベクトルを正規化せずに足し合わせていって、最後に足し合わせた結果を正規化すれば良い、と書かれていました。
特に何も考えずにその方法を使っていたのですが、外積を計算した結果のベクトルの大きさは、2つのベクトルからなる平行四辺形の面積(三角形の面積×2)に等しいので、正規化せずにこれを足し合わせた後に頂点法線ベクトルを正規化するということは、面積に応じた加重平均をしているということだったようです。

角度もやりたいことは同じですが、角度を計算して保持する必要がありますので、面積を用いるよりは少し面倒になるかと思います。

この方法で滑らかに変化する場合は問題ないのですが、立方体など、角度変化が大きい場合は困ってしまいます[2]。
こういった場合に、スムージング角度というものを設定しておいて、設定した角度以上の変化がある場合は、法線ベクトルに足しこまない方法や、フラットシェーディングに切り替える方法などがあるようです[3]。
ちなみにメタセコのスムージング角度は59.5度らしいです。

OpenGLでVBOを使用する場合、基本的に頂点の法線ベクトルしかサポートされていないため、スムージング角度によって部分的に補間・部分的にフラットシェーディングという方法はうまくいかないかなと思います。
そのための対策として、以下のような方法が使用できるようです[4]。

(a) glProvokingVertexを使用する[5][6]
(b) テクスチャに面法線ベクトルを格納して渡す
(c) ジオメトリシェーダで面/頂点法線ベクトルを計算する
(d) フラグメントシェーダで法線ベクトルを計算する[7]

最初(c)を考えていたのですが、(d)の方が簡単そうだったのでこれを試してみることにしました。

モデル読込時
1.メタセコのモデルを読込む
2.面法線,面積,三角形の角度の計算と,各頂点に属する面のリストを作成
3.各頂点において,面のリストを参照し,面法線ベクトルの内積からスムージング角より大きい面があるかどうかチェックしてフラグを保存
4.各頂点において,面のリストを参照し,面積比や角度比を重みに加重平均を計算して頂点法線ベクトルを計算

レンダリング時
1.VBOで頂点やIndex、法線ベクトル等をシェーダに渡す
2.VertexAttributeでスムージング角を越えたかどうかのフラグをシェーダに渡す
3.Vertex shaderでスムージング角を越えたかどうかのフラグをVaryingでFragment Shaderに渡す
4.Fragment shaderで、フラグ値が0より大きければ,フラットシェーディングを行い,0の場合はスムーズシェーディングを行う

Fragment shaderでフラットシェーディングを行う方法は、[4]に書かれているdFdx, dFdyを使用しました。こんな関数あったんですね[8]。

実行結果

メタセコで適当に作った単純なモデルです。

normal_flat_001.png

スムージング角を越えているかどうかのフラグを可視化した結果です。
Varyingで渡すのでfloat型にしています。

normal_flat_002.png

これにより計算した法線ベクトルです。

normal_flat_003.png

単純に光線ベクトルと法線ベクトルの内積を色に掛けた結果です。

normal_flat_004.png

一応スムージングしたい物体と、フラットシェーディングしたい物体が混ざっていても何とかなりますが、部分的にスムージングとフラットが混ざると境目が目立って駄目なようです。
ジオメトリシェーダで周辺ポリゴンも考慮すればうまくできるのでしょうか。

[1] 法線ベクトルの生成とスムージング
[2] 法線ベクトルとスムージング角
[3] 面法線と頂点法線_3DCG
[4] VBO with flat shading
[5] glProvokingVertex
[6] フラットシェーディング
[7] Re: Access to triangle normals, rather than vertex
[8] dFdx, dFdy

web拍手 by FC2
posted by シンドラー at 18:00 | Comment(0) | TrackBack(0) | OpenGL & Metasequoia | このブログの読者になる | 更新情報をチェックする