凹形ポリゴンの表示負荷

SRF共用による軽量化にて、DNM中のSRFデータ量と実際の表示ポリゴン数によるメモリ使用量について検証した。また、この話題と同時期に、OpenGLにおいては凹形ポリゴンは表示出来ず、内部的には三角形として処理されるため負荷が増加するという指摘もあった。

凹形ポリゴンが表示出来ないという点については比較的容易に理解出来るが、どの段階で、どのように分割されるかについては言及が無く、どのような処理が行われるかは不明だった。

もし、読み込み時にfsmainoの内部で三角形に分割されて描写されているのであれば、読み込み処理の負荷は大幅に増大するが、表示時の負荷は予め分割された場合と同じになるはずだ。逆に、凹形ポリゴンのまま保持し、表示の際に分割(fsmainoの機能であるかOpenGLの機能であるかにかかわらず)するのであれば、読み込み時の負荷はそう変わらないが、表示負荷は大幅に増えると予想出来る。

どちらの予想が正しいのか、また発生する負荷はどれほどのものなのか、テスト用にくさび形ポリゴンを生成して検証した。このテスト用データ(wedge.srf)は台形の短辺を共有した形状の六角形と、端となる四角形から構成されている。また、これを台形の短辺で切断し四角形としたデータ(div4_wedge.srf)と、三角形にしたデータ(div3_wedge.srf)を比較対象として用意した。なお、これらのデータはwedge.zipにアーカイブしておいたので、興味ある方は確認してみて欲しい。(gepoly/xでの読み込みにえらい時間かかるので要注意)

上記のデータを用いて検証した結果、次のようになった。
なお、結果中のメモリ増加量はCreate New Flightを選択する前と選択し表示された後のfsmaino.exeの使用メモリ量の差である。また、回転時間は機体選択画面で機体が一回転するのに要する時間で、ポリゴン数に比例して所要時間が増加することから表示負荷の目安とした。ちなみに五回計測した平均となっている。

ファイル名	頂点数	ポリゴン数	データ量(bytes)	メモリ増加量(bytes)	回転時間(sec)
wedge.srf	10,000	4,951	672,325	2,424	18.40
div4_wedge.srf	10,000	9,802	1,179,446	2,980	5.84
div3_wedge.srf	10,000	19,603	1,963,031	4,400	6.56

まず、凸形ポリゴンに分割した場合のdiv4_wedge.srfとdiv3_wedge.srfを比較すると、ポリゴン数は当然2倍になっている。しかし、メモリ増加量は1.48倍となっているが、所要時間は1.12倍となっており、表示の負荷はそれほど増えてはいない事が分かる。

一方、凹型ポリゴンのままのwedge.srfはメモリ増加量こそ一番少ないが、回転所要時間はdiv4_wedge.srf、div3_wedge.srfに対してそれぞれ3.15倍、2.80倍となっており、表示負荷が凸形ポリゴンのおよそ3倍となっている事が分かる。これは全て凸形ポリゴンで、かつ数が4倍のdiv3_wedge.srfよりも明らかに大きい。つまり、三角形化されたポリゴンを表示する以外の処理が行われていることが分かる。

このことから、凹形ポリゴンは読み込み時のメモリ負荷を下げる効果はあるが、表示に関しては極めて大きなペナルティであるといえる。また、凸形ポリゴンであれば三角形でなくとも表示の負荷にはならないことも分かる。

以上の点を踏まえると、同一平面上のポリゴンは、凹形にならない限り多角形化にするべきであろう。記述されたポリゴン数を減らすことが読み込み負荷の低減に繋がることはSRF共用による軽量化にて述べたが、凹形ポリゴンを作ってまで多角形化すると、今度は逆に表示負荷が増加してしまう。また、ファイルサイズを気にするあまり、凹形ポリゴンを放置してしまうのも表示負荷の点からは好ましくないと言えるだろう。

なお、このように百害あって一利無しの凹形ポリゴンだが、Gepoly/xのConvexnizeコマンドで簡単に分割出来る。三角形という最小単位まで分割することなく、凹形ポリゴンだけねらい打ちするこの機能、是非有効に使っていきたい。

コメント

こんにちは。コメント書くのは初めてですがよろしくお願いします。

凹形ポリゴンの表示ですが、OpenGLの上位ライブラリであるGLUには描写時にポリゴンの分割（テセレーション、もしくはタイリングという）を行う機能があります。 fsmainoでもこれを利用していると思われます。 根拠としては、テセレーションを自前で実装するのは手間がかかること、テセレーションを実装したとしてもその最適化は難しいこと、BLUE IMPULSE SDKにおいてもGLUを使用してテセレーションをしていることが挙げられます。 また、もし自前で実装しているのならば、パフォーマンスを考えて読み込み時にテセレーションを施し、その頂点データをメモリ上に確保しているはずでしょう。 ただし、これについてはメモリコストを優先したという可能性もあります。

F22愛好会さんのテスト結果を見る限り、毎回テセレーションを行っているようですね。 通常テセレーションを使用する場合は、ディスプレイリストという機能で分割後の描写コマンドをストアしておいてテセレーションを描写毎に行わずに済むようにするのですが、描写するオブジェクトが多く、さらにパーツが可動なYSFSでは少々難しい話なのかもしれません。

ディスプレイリストの効果については自分のところの拙作Ver.1.15とVer.1.16で比較して確認してみてくださればこれ幸い。
ただディスプレイリストは、描写コマンドをグラフィックアクセラレータ内部にストアしてシステムメモリとビデオメモリ間のデータ転送やコマンド発行を最小限にして高速化する為のものなので、テセレーションに限定した比較にはならないことにご注意を。

詳細な解説どうも有り難うございます。

どうしてこのような検証を行ったかと言いますと、まさに
＞パフォーマンスを考えて読み込み時にテセレーションを施し、その頂点データをメモリ上に確保
しているのか否か？と疑問に思ったからなのです。本文中に書いたとおり、gepoly/xにはConvexnizeという機能があります。これが自前実装なのかGLUの機能を呼んでいるのかは分かりませんが(BI SDKがGLUということはGLUの機能なのでしょうか?)、ほぼ完璧な結果が得られます。ですので、fsmainoでも自前で分割を行っている可能性は高いのではないか、と思ったのです。

どちらの実装になっているかで、凹ポリゴンが

• 読み込み時の負荷が多少増えるだけなので許容してもよい
• 表示負荷が大幅に増えるため許容すべきではない

のどちらかになるため、機体制作の方針に大きく影響を与えることになります。今までの機体はファイルサイズ優先で凹形ポリゴンが多いものが多数ありますし。

dnmviewerの最新版は相当高速化されていましたが、そのような変更点があったのですね。高速化の度合いが機体データによって変わってきているのも納得です。

どうやら論旨がずれまくってる駄文を長々と書いてしまったようで申し訳ありませんでした。いろいろ反省しながらgepolyのソースを調査してみました。 GLUのテセレーションは描写用なので、不可能ではないにしろ、恐らくgepoly/xのConvexnizeには使用されていないはず。 という予測の元に調査してみましたが、やはりConvexnizeはGxConvexnize()という関数で自前で実装していました。実際の処理はBLUE IMPULSE SDKのライブラリで行っています。処理の流れを追ってみましたが、リアルタイムで行うには大分きつい感じですので、やはりYSFSのテセレーションにはGLUを使用しているのでしょう。処理の詳細をまとめましたが長いので大筋だけに留めます。

凸型か凹型かをチェックして凸型なら終了、凹型ならBLUE IMPULSE SDKのBiPolygToConvex()にポリゴンを渡します。BiPolygToConvex()は三次元を二次元に落とし込んでBiPolygToConvex2()にポリゴンを渡し、再帰コールを使ってポリゴンをひたすら二つに分割して展開、分割したポリゴンが凸型になった時点で再帰コールを終了します。

こんな感じでしょうか。BLUE IMPULSE SDKにこの関数があったことに驚いたのですが、よく考えるとSDKもYSFSもOpenGLを利用しない場合があるので、この関数は必要なのでしょう。

P.S.
gepolyだとwedge.srfが一番軽くありませんでしたか？NonOpenGLのYSFSでも一番軽くてメモリー消費量も少なかったようなのですが。ひょっとしてSDKやYSFSのRendererはOpenGLを使っていない時は分割自体必要ないのでしょうか。

NonGL版でも検証してみようと思いつつ、時間が取れずずるずると延ばし延ばしになってしまいました…返信遅くなってすみません。

やはりGepolyxのConvexnizeは自前実装でしたか。調査お疲れ様です。確かに二次元に落とし込むと内外判定がかなり簡単に行えますね。上記のアルゴリズムそのままで分割を行うルーチンを(例によってPerlで)書いたら、以前書いた外積の向きから判定するものより圧倒的に高速に、しかもより適切と思われる割線で処理出来るものになりました。

もしかしたら、4角形以上のポリゴンであろうと凹型ポリゴンであろうと処理量を増やさず描画出来るエンジンがあったからこそ、SURFファイルにおいてもそういったポリゴンが許容されているのかもしれませんね。とりあえず、時間を作ってNonGLでも検証してみたいと思います。