おちゃめくらぶ掲示板 - 1659321896

1531：御茶目菜子：2013/04/13(土) 22:14:04: プチコン用ポリゴン表示プログラムがついに完成
2ヶ月前から作っていたプチコン用ポリゴン表示プログラムがついに完成したにょ。
http://ww5.tiki.ne.jp/~ochame/petitcom/polygon.htm
http://www.youtube.com/watch?v=4OkGjWAIGt8

2ヶ月前から作っていたとはいえベースとなった1日で作ったプログラムを3月末まで放置して
いたので実質的には2週間程度の開発期間にょ。

ポリゴン表示プログラムを作ろうというきっかけになったのはやはり高速な塗りつぶし三角形
描画ルーチンを作ったことにあるにょ。
http://ww5.tiki.ne.jp/~ochame/petitcom/tips/routine.htm#triangle
塗りつぶし三角形が最も有効活用できるのはポリゴン表示であるためそれならばポリゴン表示
ルーチンを作ってこの三角形の描画ルーチンがどのくらい使えるのかという実験的な内容から
始まったにょ。
私はワイヤーフレームプログラムならば何度も作ったことがあるためそれが線から三角形に
変わっただけだからすぐにできるだろうと思っていたにょ。
しかし、Direct3DもOpenGLも実際に使ったことが無かったせいか作ったプログラムは正常動作
しなかったにょ。
何が足りなかったかというとZソートとポリゴンの裏表判断にょ。
何せ一番最初に組んだプログラムはワイヤーフレームと同じようにインデックスデータ順に
表示していたたし、インデックスデータの並び順は時計回りと反時計回りがバラバラになって
いたからね。

インデックスデータの並び順は統一すれば良いため簡単な問題だけどやはり一番悩んだのが
Zソートにょ。
一般的には3頂点の座標のもしくは平均を求めてそれから判断するのだけどそれだと少し
入り組んだモデルは正確に表現できなくなるという問題を抱えているにょ。
例えばサンプルに含まれるトライフォースのようなものだと内側の切り抜かれた三角形の
面が外周面よりも近くに表示される（つまり外周ポリゴンの一部が欠ける）ということが
頻繁に起きてしまうにょ。
これは理由は簡単で四角形は三角形を2つ組み合わせて作られるけど頂点0～頂点3で構成
されていると考えた場合には下記の三角形A、三角形Bを合わせたものと言えるにょ。

　0----------1　4
　|＼　　　　|　|＼　Ｃ
　|　＼　Ａ　|　|　＼　　カメラから遠い　　三角形A、B、Cにおいて
　|　　＼　　|　6----5　　　↑　　　　　　カメラから遠い順に並べると
　|　Ｂ　＼　|　　　　　　　↓　　　　　　どうなる？
　|　　　　＼|　　　　　カメラから近い
　3----------2

この三角形が（これを見ている）モニタの上部がワールド座標においてカメラより遠くに
あると想定した場合には三角形A、三角形Bのどちらが近いかというと単純に3点の平均を
求めた場合にはBの方が近くなるにょ。
これが立方体のように凹凸のない立体ならば問題ないのだけど少し変則的になるだけで
ボロが出てしまうにょ。
それではA、Bの他にZ座標が頂点、1、2の中央に位置する頂点5と6を持つ三角形Cがある
場合（図の関係から便宜上変えているけど実際は頂点1＝頂点4と考えて欲しい）にそれら
位置関係を考えてみるにょ。
例えば頂点0、1が、Z座標30、頂点2がZ座標0とした場合には三角形Aの平均Z座標は、20に
なるけど三角形Cの頂点4は30、頂点5、6は15であるため、5、6の平均Z座標は20であるため
三角形AとCは同じ位置にあると判断されるにょ。
ここで頂点1（頂点4）を基準に少しだけ（モニタ正面から見て）左右どちらかに回転させた
場合にはZ座標の平均はCの方が小さくなり、三角形Cは三角形Aの手前に表示されることに
なるにょ。の平均でトライフォースを表示した場合には外側の面が欠けて内側の面が表示
される理由になっているにょ。

この三角形AとBにおいて本来ならば同一平面上にある四角形を2つに分断しただけなので
「両者が同じ位置関係にある」と考えた方が表示の間違いは少なくできるにょ。
そこで考えたのは3つの頂点のZ座標を並べ替えて真ん中を取り除いて2点の座標から求める
というものにょ。
これならばAとBの位置関係は等しくなるにょ。
それと同時に（Cが手前に来るような回転をさせない限り）CはAより奥になるにょ。
単純に2点の座標の合計（もしくは平均）を求めてもいいけど少しでもポリゴン欠けを軽減
するため重み付けをすることにしたにょ。
いろいろ試した結果最も大きい座標を2倍した場合に最もポリゴン欠けが少なくなったため
このプログラムでは「3頂点の最も小さい座標＋最も大きい座標×2」をZソートの基準に
おくことにしたにょ。
これでポリゴン表示プログラムの初期バージョン（β1）はできたにょ。
http://www.youtube.com/watch?v=NUZD6W5qw2M

ただ、このプログラムは「既存のポリゴンルーチンより速い」ということをアピールする
ために最小限の機能のみとなっているにょ。
光源設定やシェーディングもないため光と陰の表現ははポリゴンの面の色をデータ上で
あらかじめ変えておくことで擬似的に行っているにょ。
そして、法線ベクトルを簡略化するためパースはOFFの状態のみの表示サポートとなって
いるにょ。（こうすることで法線ベクトルのZ成分のみを求めれば済むため高速化ができて
いる）

この状態では完成までほど遠いためもう少し改良して正式公開しよう・・・と思いつつ
大幅な改修が必要であるためしばらく放置の日々が続いたにょ。
そこに第2回大喜利の開催の情報が入ってきたにょ。
いいネタがないのでこのポリゴンルーチンを使ったレースゲームを作ろうと考えたにょ。
そして、3月末にまずは改善点としてシェーディングを搭載したにょ。
多少重くなったけど「光源は正面からのみ」とすることで高速化して何とかβ1と同レベルの
速度を維持してシェーディングが搭載したβ2ができたにょ。
それを使ってアンドアジェネシスもどきを表示たのがこの動画にょ。
http://www.youtube.com/watch?v=XmvYJA1iuz0

このβ2で完成・・・としても良かったけど速度面ではまだ不満があるためさらなる高速化を
行うことにしたにょ。
そして、やはり光源の自由な設定が欲しいと感じたにょ。
光源の色や環境光の設定は実行前にパレットを書き換えておけば良いだけなので速度的な
マイナスはゼロで実装できたにょ。
問題は光源の場所の指定にょ。
3次元座標を入力もしくはプログラム上で変数の初期値を書き換えることで実装という手段も
あるけどそれだとインパクトに欠けるし、何よりユーザーに座標を入力すると言われても
全くピンと来ないからね。（例えばユーザーを中心に前方100m、右に150m、上に50mと言った
場合にどの方向を示しているのかは瞬間的に比例計算できるか長さや距離の目安になる
ガイドとなる物体が別にない限りは難しい）
やはり、X、Y、Zの座標ではなく極座標の方が分かりやすいと思ったにょ。
要するに緯度経度のように右（左）○度、仰角△度のような感じでの指定にょ。
これをタッチパネルでリアルタイムで変化させることができればインパクトはあるにょ。

そのUIとして考えたのがプチコンコンテストで発表した簡易地球儀2で用いている世界地図
からの入力にょ。
http://wiki.hosiken.jp/ptcmcon/?Toukou%2F%B4%CA%B0%D7%C3%CF%B5%E5%B5%B72
これを使えば球面の極座標を2次元の直交座標と同じ感覚で指定できるにょ。
上画面の太陽マークが球面上を動いている関係で下画面は先日作ったアナログPADルーチンの
ような円形の入力画面の方が上下の座標が一致して分かりやすいという考えもあるかも
しれないけど実際に試してみたら上画面の太陽マークはスムーズに動かせる反面で座標の
指定は分かりにくくなってしまったにょ。
アナログPADルーチンを使ってキャラを動かす場合にはキャラの動きに合わせて微調整する
ためあまり気にならないけれどここでは座標を1対1に対応させる必要があるにょ。
これは相対座標入力が絶対座標入力かということの違いにょ。
アナログPADルーチンは相対座標入力に特化しているため特定の座標を直接指定する絶対
座標入力用には向かないにょ。

ちなみにこのプログラムでは光源の指定は絶対座標入力が用いられているけど拡大縮小や
回転には相対座標入力が用いられているにょ。
これはその方が使いやすいからにょ。
光源の指定は絶対座標入力が相対座標入力よりも良いということは上記の通りだけど
回転に関してはどちらでも良いという考えがありそうにょ。
回転を絶対座標入力で行う場合には画面中央をタッチしたら0度で横方向への回転ならば
256ドットを360度で置き換えて1ドットあたり1.4度回転させればいいにょ。
縦方向だとドット数の関係からそれが4/3倍になってしまうけど厳密な操作が要求される
ようなゲームではないので問題ないにょ。（ゲームに使う場合に縦横の回転量が異なると
いうのはアナログPADルーチンが円形ではなく楕円形だったことを考えると分かりやすい）

このように考えると回転を相対座標入力ではなく絶対座標入力で行うことに何ら問題は
ないように感じるけどこれは光源の指定と組み合わせると変わってくるにょ。
絶対座標入力を行った際に例えば何もボタンを押していない場合に画面タッチをした場合に
どのような挙動になるかというと当然ながらそのタッチした座標に応じて回転となるにょ。
では、回転をしないで光源だけを移動させたい場合はどうするのかというと最後にタッチ
した場所と同じ座標を再びタッチして[L]ボタンを押す必要があるにょ。
そんなことは無理なので[L]ボタンを押すしかないにょ。
しかし、[L]ボタンを単独で押したら光源が初期化（正面向き）されてしまうにょ。

つまり、両方が絶対座標入力の場合には「その機能専用ボタン」による操作が別途必要に
なってくるということにょ。
例えば回転ならばタッチで座標が変わらないようにするためには回転用のボタンを押しながら
タッチさせる必要があるにょ。
回転をタッチのみでまかなうためには光源設定ボタンで光源モードに入り（この時点で
光源の位置は初期化されない）確定ボタンで光源を確定させる必要があるにょ。（確定
ボタンを押さずにモードを終了した場合には位置が初期化されるという感じ）
要するに現状よりワンクッション動作が増えてしまうということにょ。
たかが、ワンクッションだけどこの差は大きいと思うにょ。
これが、相対座標入力による回転と絶対座標入力による光源指定だとシームレスで非常に
直感的な操作が可能になるにょ。

さて、UIもいろいろ考えたけどやはり重要なのは処理速度にょ。
プチコンがいくら高性能とはいえCPUパワーのみでポリゴン表示を行うならばかなり非力
だからね。
これに関してはβ2でかなり高速化はしたもののやはり時間を掛ければまだまだ高速化
できる余地が見つかってきたにょ。
プチコンは演算そのものは速いけど代入処理が相対的に見てかなり遅いからね。

　　　　1000回あたりの実行時間
　　　　　プチコンmkII　　　　ポケコン（PC-E650）
　加算　　　0.004秒　　　　　　　0.8秒　　　　　　　　約200倍
　乗算　　　0.0037秒　　　　　　 1.6秒　　　　　　　　約432倍
　代入　　　0.0098秒　　　　　　 0.8秒　　　　　　　　約81倍
　（加算、乗算は代入処理を含まない実時間）

プチコンはポケコン（PC-E650）と比べて200～400倍の演算速度になっているにも関わらず
実際に演算速度のベンチを実行した場合には100倍程度の速度にしかならないのはこの代入
処理がボトルネックになっているためにょ。（あとプチコンのFOR～NEXTは終了値の値を毎回
チェックされているため遅いのでここは固定数にした方が高速化に繋がる）
つまり、代入処理を減らし、ループ処理を工夫すれば普通に作った場合にはポケコン比で
100倍程度にしかならないものがポケコン比で200～400倍の速度に近いものが得られるため
高速化できるということにょ。
したがって、多少リストの長さに無駄が出ても速度を重視することにしたにょ。

これによって、立方体の表示ならば17～20fps、24面体で13～14fpsと高速になったにょ。
これは最も処理が軽かったβ1と比べて1割程度の高速化になっているにょ。
1割程度だと大したことはないと感じるかもしれないけど実際はポリゴン面の法線ベクトルは
β1ではZ成分しか求めておらず、裏表を判断するための内積もZ成分のみで済んでいた（視線
ベクトルのZ成分は1であるため内積を計算する必要性さえなかった）けれどパースON、OFFで
きちんと表示されるようにZ成分だけではなくX、Y成分の計算に単位ベクトル化処理や各成分の
内積もちゃんと行っているにょ。
それに加えて光源の位置も自由に変えられるようになったためそのベクトルの内積も計算して
いるにょ。
おおざっぱに見て2～3割は処理が増えているにも関わらず、1割程度の高速化ができていると
言えば実際は3～4割程度の高速化ができているといっても過言ではないにょ。
これは処理の高速化だけではなく場合分けを行い不要な処理を行わないことで高速化も行って
いるためにょ。（2～3割は処理が増えても条件でふるい落としをして実質処理増を1～2割
程度の増へと軽減し、それで2～3割の高速化が行えればトータルで1割程度の高速化となる）
一見して無駄に見えるIF文も高速化のためというわけにょ。
これによって、ポリゴンの速度が速くなったというだけではなくワイヤーフレームに関しても
β1と比べて2～3割速くなっているにょ。

　　　　　　　　　β1　　　　　　　　正式公開版
　立方体　　　　　96～97fps　　→　　122～123fps
　24面体　　　　　56～57fps　　→　　　65～66fps
　トライフォース　65～66fps　　→　　　81～82fps
　　　　　　　（※正式公開版はタッチしていない場合の速度）

これだけ高速化を駆使してもβ1の2倍とか3倍とかの速度にならないのはβ1の段階である程度
高速化されているためにょ。
要するにβ1の段階で2～3倍の高速化をやっていて今回さらにそこから2～3割の高速化を行った
ということにょ。
リストの可読性を下げてリストの長さを捨てて限界まで高速化すればさらに高速化できるにょ。
といってもその数字は微々たるものでせいぜい1～2％だと思われるにょ。
あと三角関数をテーブル化して高速化などの方法もあるけどプチコンの三角関数は非常に速く
例えばA=SIN(X)は配列変数を使ってテーブル化してA=S(X)と配列変数を使った方が遅くなる
といった感じにょ。（テーブル化をしたらRADを使わなくていい分だけわずかに速くなるけど
テーブル化のリスト増を考えると微妙すぎるくらいの速度向上であるためこのプログラムでは
テーブル化は使用していない）
それよりはZソートにおいて上記のようにポリゴン欠けが起きにくくする措置をとるのをやめて
単純加算で行えば簡単に5～6％高速化可能にょ。
それならば光源位置もβ2の段階までのように固定化すればさらに高速化できる要素があるため
これ以上高速化できる余地が全くないというわけではないけど可読性と機能性とリストの
長さを考慮した場合にはこれがほぼ限界の速度だと思われるにょ。

もっとも、これだけ高速化してもわずか24面体で13～14fpsであるため（陰面消去をしている
ため単純に計算はできないものの）300ポリゴン/秒くらいの演算、描画速度となっているにょ。
実際152ポリゴンのアンドアジェネシスで2fps弱だからね。
この速度ではゲームに利用するのはかなり厳しそうだけど工夫次第では活用の用途はいろいろ
見つかるのではないかと思われるにょ。