縮退三角形(Degenerate triangle)による最適化
OpenGLやOpenGL ESの最適化の手法として「縮退三角形(Degenerate triangle)」を使うというものが有ります。
シンプルに考えた場合、以下の様に
ポリゴンが離れれている場合に GL_TRIANGLE_STRIP を使うとすると glDrawArrays などの描画命令を2回実行する様にプログラムを記述します。
しかし、 GL_TRIANGLE_STRIP には三角形が縮退三角形(面積が0の三角形)場合は描画を行わないという特徴が有ります。これを利用して離れた位置にあるポリゴンを一度の描画命令で描画する手法です。
glDrawArrays など描画命令は重い処理であるため出来るだけ回数を減らそうというアプローチになります。
以下の様にA〜Hまでの頂点が有った場合は頂点の定義はABCDEFGHで行い、それを GL_TRIANGLE_STRIP で描画すると描画されます。
GL_TRIANGLE_STRIP の場合、以下のルールで頂点が選択されて三角形の描画が行われます。
1. 頂点配列から3頂点(ABC)を選択して描画。
2. 頂点配列から1頂点追加して、一番最初の頂点を破棄(ここで BCD となる)。それを逆順(DCB)で使用し、描画。
3. 頂点配列から1頂点追加して、一番最初の頂点を破棄(ここで CDE となる)。それをそのままの順番で使用し、描画。
4. 以降、 2. 3. のルールを繰り返す。
そのため描画される三角形は以下のものになります。
- ABC
- BCD(実際は逆順で使用)
- CDE
- DEF(実際は逆順で使用)
- EFG
- FGH(実際は逆順で使用)
ここで、先程の様にC〜Fの範囲の三角形を描画しない様にするのに縮退三角形を活用し、頂点の定義をABCDDEEFGHとします。
この場合、描画されたり、されなかったりする三角形は以下のものになります。
- ABC
- BCD(実際は逆順で使用)
[ここから縮退三角形(描画されない)]
- CDD
- DDE(実際は逆順で使用)
- DEE
- EEF(実際は逆順で使用)
[ここからは描画される]
- EFG
- FGH(実際は逆順で使用)
この様に該当する三角形を一覧にすると良く分かる様に縮退三角形の部分では3頂点中、2つが同じ頂点になっているのが確認できます。
こちらにサンプルを置いておいたので実際の動作はこちら確認して下さい。
デフォルトではA〜Hの三角形全てを描画します。 #if 1 の部分を #if 0 に変更すると「縮退三角形」を利用して、上記で紹介した離れた2つの位置への描画を行います。
注意
と、この様に紹介はしましたが「OpenGLの熟練者＆開発期間、人数に余裕が有る」という場合を除きあまりおすすめはしません。
紹介した内容を見ればよく分かる様に結構複雑な構造です。また、環境やデータによるとは思いますが苦労に見合うほど速度アップが無い場合も多いかと思います。
また、一般的な3Dのファイルのフォーマットの場合は三角形(または四角形)の羅列であり、そのファイルをOpenGLで描画する場合は GL_TRIANGLES などを使用した方が直感的に実装でき、バグも少なくなると思います。
もちろん、熟練者が3Dツールのエクスポートのプラグインとして実装する場合やその様なプラグインから出力されたものを使用する場合は良いと思いますが…
ちなみに自分は熟練者で無いので GL_TRIANGLES 使ってます。
関連資料
三角形ストリップは有効か？ - もんしょの巣穴blog
http://monsho.blog63.fc2.com/blog-entry-84.html
- Wikipedia(英語)。Degenerate triangleについての記載有り。
Triangle strip - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Triangle_strip
- Degenerateの数学的説明。
Mathwords: Degenerate
http://www.mathwords.com/d/degenerate.htm
