０からRaspberry Pi 4でさくっとマイクラサーバーを建てるまで

知人からマイクラサーバーを建ててくれと頼まれたから仕方なく0から環境構築した話をするよ。

私はケチな上にパソコンの寿命管理にうるさいので（すぐ壊れるから）、自分のメインマシンを24時間稼働させるのは絶対嫌だし、電気代もかけたくなかった。
こういうときはやっぱり消費電力が超少ないシングルボードコンピュータのRaspberry Piに限る。

昔私は2系を使っていたけど、最新のラズパイは4だそうだ。CPUも1.5GHzのクアッドで、メモリも4GBついてるらしい。
最大消費電力は6Wらしいので、24時間ずっと稼働させても電気代は月100円くらい。

というわけでこれを買った↓
LABISTS Raspberry4 4B-32GB（技適マーク入）MicroSDHCカード32G/NOOBSシステムプリインストール/カードリーダ /5.1V/3A Type-C スイッチ付電源/MicroHDMI-to-HDMIケーブルライン/三つヒートシンク/簡単に取り付けケース/日本語取扱説明書/２４ヶ月保証
@amazonJPさんから

とりあえず悩んだら絶対これを買った方がいい。ファン、ヒートシンク、OSプリインストール済Micro SD、HDMIケーブルがついてくる。

OSプリインストール済みSDがあるので、起動してちゃちゃっと環境構築するだけ。普通に起動するとGUIが立ち上がるけどコンピューターリソースの無駄なのでさっさとCLIで起動しなおしたほうがいい。

とりあえずエディタはあったほうがいいので

sudo apt-get install vim

はやっておこう。（個人差アリ）

ローカルIPを固定する

多分デフォルトではDHCPを使ってると思うから、/etc/dhcpcd.confを弄る。

例えば、私のネットワーク環境はネットワークアドレスが192.168.11.0で、ルーターのアドレスが192.168.11.1で、サブネットマスクが255.255.255.0で、ローカルIPのホストの数字は（なんでもいいけど）25を割り当てたかったので、以下のようにした。

interface wlan0
static ip_address=192.168.11.25/24
static routers=192.168.11.1
static domain_name_servers=192.168.11.1

wlan0は無線のこと。無線の場合、そもそもインターネットにつなぐ必要があるので

wpa_passphrase  [SSID] [pass]

しておくこと。ちなみにケーブル管理が絶望的に不得意じゃないのなら有線にしたほうがいいです。マジで。サーバーのレイテンシ全然違うよ（無線の人間が何言ってるんだって話だが）
DNS(domain name servers)アドレスってなんやねんって思った人は、まず間違いなくルーターのアドレスいれれば動くと思う。

(03/15 追記)　サーバーの遅延について抗議されたので有線接続にした。IP固定の方法はinterfaceをeth0にするだけで他は同じ

rebootすればIPが目的のものになっているはず。

公開鍵を登録してSSH接続できるようにする

ラズビアン（ラズパイのデフォルトOS）はデフォルトでSSH接続ができるから、もうすでにSSH接続できるっちゃできるけど、セキュリティ的にも公開鍵を使ったほうが良い。

公開鍵の作り方はいくらでも資料があるのでぐぐってください。

自分のSSH接続したいメインPCで公開鍵を作ったら、scpコマンドでラズパイのホームディレクトリに転送する。
ユーザーネームはpiとすると

scp ./.ssh/id_rsa.pub pi@192.168.11.25:~/

次、ラズパイのコンソールに入って

mkdir .ssh
cat id_rsa.pub >> .ssh/authorized_keys
chmod 700 .ssh
chmod 600 .ssh/authorized_keys

chmodしているのは念のため。sshはセキュリティ上この辺のファイルのパーミッションがガバガバだと弾かれるので。

これで公開鍵接続の準備は整ったので、パスワード接続を禁止する。
/etc/ssh/sshd_configを開いて、

PasswordAuthentication no
PubkeyAuthentication yes
AuthorizedKeysFile  .ssh/authorized_keys

と記載しておく。

メインPCに戻って、./ssh/configで、ラズパイのホストの名前をつけてあげる。
名前はなんでもいいけど私はpi4にした。タイプ数少ないの最高！

Host pi4
    HostName     192.168.11.25
    IdentityFile    ~/.ssh/id_rsa
    User            pi

もうこれですぐつながる。

ssh pi4

ポートを開ける

マイクラサーバーのデフォルトのポートは25565。自分のルーターのマニュアル見ながら開放しよう。
ちなみに私はv6プラス接続なので、開放できるポートには制限がある。その場合もポート変換をかませば可能。
ここは各自ルーターのベンダーにお問い合わせくださいといった感じなので割愛する。

マイクラサーバーのダウンロード、起動

ラズビアンには多分JDKが最初から入ってたはずなので、ダウンロードしてすぐ起動できるはず。

適当にディレクトリ作って、 Download server for Minecraft | Minecraft ここからダウンロードリンクを取得したら

mkdir minecraft
cd minecraft
sudo wget DOWNLOAD_LINK

すると、ディレクトリにサーバー関連ファイルと、利用規約の同意書（eula.txt）が展開されるので
エディタでeula.txtをtrueに書き換える。（公式ページの利用規約を読んでから）

これで準備は完了。
ラズパイ4はメモリ4GBなので2GBくらいアサインするとして

sudo java -Xms2G -Xms2G -jar server.jar nogui

で起動。これでサーバーが全世界に公開されました。

ログ公開サーバーを作る

私はニートの知人にサーバーを貸してるので、仕事中に昼間からマイクラを遊んでる様子をみて励みにしたいから、ログが見れるHTTPサーバーを建てた。

ログサーバーなんて適当でいい、nodejsでちゃちゃっと書こう。ちなみにnodejsはラズビアンに既に入ってた。すげーなおい！

適当にディレクトリ作って、適当に.js拡張子でファイルを作って

var http = require('http');
var fs = require("fs");

const port = XXXX; // 適当なポート
const server = http.createServer((req, res) => {
        if (req.method == "GET") {
                var data = fs.readFileSync(".path/to/minecraft/logs/latest.log");
                res.writeHead(200, {"Content-Type": "text/plain"});
                res.end(data);
        } else {
                res.writeHead(404, {"Content-Type": "text/plain"});
                res.end("Sushi is not found");
        }
}).listen(port);

はい終わり。これはひどい！　GETされるとリクエストパス関係なく常にマイクラサーバーの最新ログを返すだけのサーバー。それ以外のメソッドは404！
いいんだよこういうので。最高に堅牢なサーバーは何もしないサーバーだからね。

ちなみに私は例によってv6プラスなのでHTTPポートが開けられないから、適当なポート番号でlistenしてるよ。

このサーバーはデーモン化させたかったのでforeverを使った。

sudo npm install -g forever 
forever start app.js  

これでどこにいてもサーバーが元気に稼働してる様子が見られる。

終わり。

結局オブジェクト指向とはいったいなんなのかとか、ゲームの設計に関して最近思うこと

2兆年ぶりにブログ記事を書いている気がする。レンダリングエンジンの開発に飽きたからこのブログはほぼ用なしになってしまった。ただ、最近プライベートでプログラムを書いてなさすぎるので、リハビリに再開するのもいいかもしれない。プログラムを書くのは好きだが、致命的に目的意識や目標となるエンジニア像が存在しないため、具体的なマイルストーンを設置しないと絶望的に怠惰になりがちだ。

しかし、最近転職してから「設計」というものを考える機会が莫大に増え、それに関しての自身のナレッジ、あるいはモヤモヤなどを文章化することで、自分の中で情報を整理しようと思い立った。

私はゲームプログラマーだ。作っているゲームはリリースされてから数年が経ち、ソースコードの量は膨大で、そしてありがたいことに収益が安定しているため、数年後もちゃんと保守できることを前提として設計しなくてはならない。

私のチームのクライアントの開発の要素として大きく上げられるものとしては、オブジェクト指向設計・アジャイル開発の2つがある。巷ではどちらもある種のバズワードのような扱われ方をしている。確かにすべてが上手くいく魔法のような開発手法というわけではないことは確かだが、果たして数年続き、大人数で行われる私のチームにとっての開発スタイルとして正しいのだろうか、そういつも考えている。といっても、アジャイル開発に関してはマネジメントの領域なので、その是非については1エンジニアに過ぎない私には判断できない。

オブジェクト指向設計に話をフォーカスしよう。

で、実際のところ、「オブジェクト指向」を言語化して説明することは無理なんじゃないかと思っている。多態性とかカプセル化とかそういう言葉の定義を説明することは可能だが、いざプログラムを見せられた時に、「これはオブジェクト指向で設計されているか？」という質問に対して回答することはできない。オブジェクト指向型プログラミング言語で書かれてますね、とは言えるかもしれないけれど。

この時点で、少なくともプログラムを評価したり、あるいは指導する際に「オブジェクト指向設計」という単語を使うことは不適切に感じる。定量化ができず、共通認識も取れない単語なんて地雷にしかならない。

結局、適切なケースにおいて適切なデザインパターンを適用する、適切な抽象化をする、適切なデータ隠蔽をする、そういった「ある局所的なケースにおいて常に適切な」選択を続けていく結果、再利用性や可読性が最強になる桃源郷のようなプログラムが生まれるという仮定のもと、それをオブジェクト指向設計と定義しているんだろう。だから、オブジェクト指向設計を目指すというのは見えてないゴールに向けて適当に走り出すようなもので、実際に私たちがやるべきなのは、もっと「良い設計」とやらを個々の問題に分解して、見えているゴールを目指すことだと思う。その結果、きっと私たちのプログラムはいつかオブジェクト指向設計にたどり着くんじゃないんかな。知らんけど。

設計に関する個々の問題についてなら、私もそれなりに思想がある。
以下に、私が経験則的に上手くいった設計方針の備忘録みたいなものをまとめる。もちろん個人的な思想なのでその辺は留意してほしい。

...思いついたら書き足す。

クラスは常にミニマムに設計する

モジュールは細かく要素分解されているべきだ。もちろん、一連の手続きをラップする上位的なインターフェースはあってもいいけれど、内部の構造としてはミニマムなクラスや関数の組み合わせによって実現されていてほしい。

例えば、AssetManagerというクラスを考えてみる。もうだめだ。作った時はいいけれど、担当者が変わるたびにインターフェイスが増えて、メンバ変数が増えて、そしていつか神にへと昇華するだろう。最初に設計した人はこのManagerクラスは美しいほどによくできたクラスだったのかもしれない。でも担当者が変わった瞬間に、この「Manager」という単語を都合よくとらえて、好き勝手に機能を継ぎ足ししてしまうに違いない。

「このクラスはこの仕事をします！」という設計者の意図を正しく伝えるためには、クラス名を適切にするしかない。このAssetManagerも適切な名前にすべきだ。といっても、リネームでは解決しない。クラスがミニマムではないから。

このManagerクラスがゲームで頻繁に要求される要件をすべて含んでいるとして、それらはAssetDownloder, AssetDependencyResolver, AssetCachePoolといった個々のクラスに分離できるはずだ。もちろん無理にクラスにしなくてもいい。ただの手続きであるのならば、関数でもいい。大事なのは、全ての部分問題を独立させて、適切な名前を割り当てることだ。そうすれば、後任者も機能を追加するとき、「え！？　そこにコード加えるの！？」みたいなトンデモ改修をすることはなくなることが期待できる。

できるだけ副作用のないconst属性のインターフェイスを採用する

処理を記述するときは、結果を返り値で返して、内部の状態には変更を加えないようなメンバ関数を中心に定義すべきだ。
どうしてか？　それは、ユニットテストが書きやすいから。これに尽きる。特に、処理に必要な情報を引数で受け取るように記述されていれば、もうテストが書くのが楽すぎて最高になる。テストの書きやすさは品質に直結する。そして、テストフレンドリーに設計されたクラスは、自然と「命名が適切で」「個々の関数の役割が明確な」クラス/関数になる。信じてもらえないかもしれないけど、経験則的にそうなると思っている。

class Hoge {
  void setData(Data data);
  void calculate();
  int getResult() const;
};

よりも、

class Hoge {
  int calculate(Data data) const;
};

のほうがいいよねって話だ。もちろん、こんな分かりやすいヘンテコなコードはめったに見ないが、本質的に同じコードはよく見かける。大事なのは「ユニットテスト」の「ユニット」とは、「一つの関数」であるべきということ。前者のコードの場合、このcalculate関数のテストを記述するためには３つの関数を実行する必要がある。それはユニットではない。

これは愚痴に近い雑談だが、テスト駆動開発はある種の理想だけど、ゲームではそれが難しいことも多い。ビューが根深く絡むし、この分野は仕様変更がかなり多い傾向にあって、仕様変更の影響で膨大な量のユニットテストを修正していると本当に虚無の感情となる。

セッター関数を減らす

セッター関数はあればあるほど設計者も使用者も混乱する。複数のプロパティの整合性、あるいは単なるデータのセットし忘れなど、落とし穴を生みがちだ。オブジェクトとして十分に振る舞うために必要なデータは全てコンストラクターや生成関数で受け取って、それ以降は変更を加えないべき。もしくは、本質的にはSetterでも、setという命名ではなく、そのデータの格納によってどのようにオブジェクトが振舞うのかを明示した関数名を定義する。簡単な例だと、setStateよりもchangeStateの方がインターフェイスとして明瞭ということ。

1つのクラスでフラグ変数を2つ以上定義しない

フラグ複数持つのは典型的なアンチパターンだ。(2^フラグの数)だけ状態が生まれるから。そして、必ずそれは設計者の想定の範疇を超えてバグを生み出す。
例を挙げてみよう。isTouchable、isVisibleのような二つのフラグを持つとする。この時、「タッチ可能で見える状態」、「タッチ可能だが見えない状態」、「タッチ不可能だが見える状態」、「タッチ不可能でかつ見えない状態」の4つの状態をこのオブジェクトは持ちうる。だが、多くの場合、この4つの状態全ての要件を満たす必要性があることはとても少ない。設計者も、暗黙的に「isVisibleがfalseの時は必ずisTouchableもfalseになるようにしよう」という思想で設計しているだろう。だが、「想定しない状態になりうる」それだけでバグを生み出すオブジェクトの脆弱性になる。見えないけどタッチできてしまうとかありそーなバグだ。設計者は完全に想定された状態を明示的に定義しよう。この場合、enumなどで Active（タッチもできるし見える）, Deactive（タッチはできないが見える）, Invisible（タッチもできないし見えない） のようなステートを定義するのが懸命だ。すると、件の起こりそうなバグは未然に防がれる。

if文はテスト可能な関数に集約し、ビュー側では書かない

これも突き詰めるとテストカバレッジの問題になってくるが、提言しておく。前提として、ビューのコードはテスト困難だ。というか、ビューのテストを実現できているゲームプロジェクトがあるのならばそのナレッジを共有して欲しい。まじでなんでもします。靴も舐めます。
さて、if文があるということは、その関数は毎回同じ動作をしないということだ。それは、つまりバグを生み出す。同じことばっかり言ってる気がするが、プログラマは複雑なロジックを書いた時必ずバグを出す。そしてそれを後任者が改修した時もっと顕著に現れる。それをどう防ぐか？　ユニットテストだ。

幸い、ビューが絡まないロジックの場合はテストを書くことは困難ではない。if文があっても、カバレッジが100%になるようにテストを書こう。（もちろんカバレッジが100%だからといってテストケースが十分である保証は全くない）

例えばこんなコードがあるとする。

void initView() {
  /* ... */
  int64_t remainTimeSec = _model->getRemainTimeSec();
  if (remainTimeSec >= SECOND_PER_DAY) {
    _text->setString(format("残り%d日", remainTimeSec / SECOND_PER_DAY));
  } else if (remainTimeSec >= SECOND_PER_DAY) {
    _text->setString(format("残り%d時間", remainTimeSec / SECOND_PER_HOUR));
  } else {
    _text->setString(format("残り%d時間", remainTimeSec / SECOND_PER_MINUTE));
  }
 /* .. */
}

別に何が悪いというわけではない。ただ、ロジックがあるのに、この関数はビューにアクセスしているためテストできない。それは、不健全だ。

std::string formatRemainTimeText(int64_t remainTimeSec) {
  if (remainTimeSec >= SECOND_PER_DAY) {
    return format("残り%d日", remainTimeSec / SECOND_PER_DAY);
  } else if (remainTimeSec >= SECOND_PER_DAY) {
    return format("残り%d時間", remainTimeSec / SECOND_PER_HOUR);
  } else {
    return format("残り%d時間", remainTimeSec / SECOND_PER_MINUTE);
  }
}


void initView() {
  /* .. */

  int64_t remainTimeSec = _model->getRemainTimeSec();
  _test->setString(formatRemainTimeText(remainTimeSec));

 /* .. */
}

これならば、ビューの初期化コードは常に一貫性のある動作をし、そしてロジックはテスト可能なビューが絡まない関数に集約されているため、品質が保証できる。

protectedメンバー変数は邪悪

クラスというものは、インターフェイスを通じてやり取りするもの。だからこそ、オブジェクトはブラックボックスとして振舞うことができる。公開しているインターフェイスは、「想定された操作」だからだ。さて、ここで継承クラスについて考えよう。これはあんまり浸透している感じがしないのだが、継承クラスと基底クラスは 赤の他人 なのだ。もう少し具体的に言うと、基底クラスは、継承クラスが作られ、どのように拡張されるかを想定して設計することは困難ということ。たいていの場合、overrideやprotectedメンバー変数を悪用すると、基底クラスが「想定された操作」の範疇を超えて継承クラスは設計されてしまう。その状態になると、基底クラスの内部実装をリファクタリングしたりするだけで継承クラスの振る舞いが変わってしまい、不具合を引き起こす。他にも、ある基底クラスから派生したAとBという２つの継承クラスがあるときに、基底クラスはAとBの共通部分であることが期待できるが、本質的にはそうなっておらず、共通機能を実装するときに基底クラスを弄るだけで解決しないことがある。

これらを回避するために一番大事なことは、protectedメンバー変数を定義しないこと。継承先で自由にアクセスできる変数を基底クラスに置くことは、基底クラスが一切カプセル化されていないのと同義だ。たとえ継承先のクラスであっても、全てメンバー関数を通してならばある程度制御が効く。（ここで継承クラスのためだけのGetterとSetterを無理やり定義してしまうと、本質的な問題が解決しないので注意すること）

共通の要件を持つ複数のクラスを設計するとき、継承ではなく内含で設計する

これは前の項の「protectedメンバー変数は邪悪」の話の延長戦上にある。そもそも、継承で「共通の要件」を括りだすことは、保守的な面で非常に困難だ。特に、仮想関数を持ったりしている時点で、基底クラスがそれらの共通要件であり続けることはとても困難である。何度も言うが、将来的に第三者の手で改修されることを常に想定すべきだ。基底クラスで解決するという選択も、作りきりのプログラムではうまくいくかもしれないけれど、保守や改修が必ず困難になる。

内含は、共通要件である機能を完全なカプセルオブジェクトとして設計できる。設計者は、publicインターフェイスがどのように呼ばれるかだけ考慮すればよい。これは、仮想関数を持つ基底クラスを設計することよりも非常に簡単だ。

私は、動的ポリモーフィズムを用いて多態的に振舞わせたいという要件においてのみ、継承を使うべきだと思っている。

グローバルイルミネーションのためのフォトンマップ実装①

　グローバルイルミネーション(Global Illumination: GI)とは、現実世界における間接光を表現するためのアプローチである。（あるいは、間接光そのものを指す）

　本来、現実のライティングというものは、無限にも等しい膨大な量のフォトンと、制限のないバウンスという膨大な物理的現象の結果起きている事象であるが、それをコンピュータで再現するというのは非常に難しい。リアルタイムレンダリングであるならばなおさらだ。
　ゆえに、古きよきレンダリングエンジンというものは、頂点の座標と法線、そして光源の距離と方向から高速に計算することができる「直接光(Direct Lighting)」と、間接光をすべて均一に入射する光として大幅に近似する「環境光（Ambient Lighting）」の二つでライティングは実装されていることが多かった。

　しかし、近年は、オフラインライティングとリアルタイムライティングを組み合わせた近似的GI表現が流行っている。その一つがフォトンマッピングだ。これは、広義的にはレイトレーシングの一種で、狭義のレイトレーシングは視線からレイを飛ばし色を追跡するのに対し、フォトンマッピングは光源からフォトンを放ちその軌道をシミュレーション、キャッシュするアルゴリズムである。
　そして、テクセルベースで特定数のキャッシュされたフォトンを収集、そしてその収集したフォトンの分布から密度を推定、放射照度を計算する。
　この手法は、放射するフォトンの量と、テクセルあたりのフォトン量にしか計算量は依存せず、古典的GI実装手法であったラジオシティ法よりも計算量の見積もりが容易いという利点がある。また、フォトンの放射量及び密度を、関心の高いオブジェクト（例えば、コースティクスを形成する透過材質のオブジェクトなど）に対し調整を加えることで、ほかの手法では難しかったシーンの品質の調整が可能になっている。特に、透過材質に対するコースティクスの生成は、フォトンマッピングの優秀なところを語る際には欠かすことができない。これは最も一般的なラスタライズ法とは根本的に異なるアプローチではあるが、リアルタイムレンダリングでは組み合わせて使われることも多いようだ。

　実際に、GPUレンダラ―における実装を行ってみよう。手順は以下のようなものが考えられる。

①光源からフォトンを照射する
②非完全鏡面に当たるまでバウンス、拡散面に当たった場合はメタリック値、RGB反射能から確率を計算し、ロシアンルーレット法でバウンスするかどうかを決定する
③全てのフォトンがmiss（サーフェイスに吸収されないままどっかいった）、吸収、あるいは数値計算的限界（あらかじめ定めたバウンスオーダーのオーバー）等により計算結果が確定したら、吸収が起きたフォトンの座標の空間分布よりKD-Treeを形成する（平衡条件を満たすように構築するとよい）
④次に、LightMapを生成するために、GIの影響下にあるオブジェクトをテクスチャにUV展開し、テクセルごとにワールド座標やワールドタンジェント等の情報を書き込んでおく。
⑤LightMapをテクセル単位で走査し、各テクセルについてKD-Treeを使ってフォトンのN近傍探索を行い、放射照度を推定する。
⑥シェーダーでLightMapをフェッチしてライティングに使用する。

　結構泥臭い。とくに、LightMapの生成に関しては、ラスタライザーはもちろん、リソースの肥大化を防ぐためにもアトラステクスチャを作って大きいライトマップに複数のオブジェクトベイクするべきであるので、ある種の平面ナップザック問題を解かなくてはならない。メッシュのUV展開アルゴリズムも必要である。
　アルゴリズムそのもの複雑さの割に、なかなかに面倒な代物だ。一方で、CPUで計算する場合はKd-treeのフォトン分布をそのまま放射輝度推定に使えるのでLightMapを作る必要はなく、レンダラは割とシンプルに作れる。

　
　ざっくりレンダリングしてみると以下のような結果が得られる。放射フォトン数は10000、放射輝度推定フォトン数は10、フォトン探索半径は3（このコーネルボックス自体のサイズが30くらい）

　にじみがすさまじい。まあ、フォトンの数的にこんなものだろうか。

　ボールの右側が、近くの青い壁から反射してくる間接光によりうっすら青くなっている様子も確認できる。

　
　ちなみに、これは直接光も間接光も両方フォトンマップから放射輝度を推定しているが、前述の通り直接光は入射ベクトルと法線ベクトルから高速に計算できる。しかし、その場合の光の物理量の辻褄をどう合わせるのか分かっていない。
　今回の実装では、光のIntensity（強度）をポイントライトのパラメータにもち、それを放射束に変換して、フォトンの密度とその放射束の和から放射輝度を計算している。
　一方で、古典的なポイントライティングのライティング手法では、「減衰係数ζ1、ζ2、ζ3」をパラメータとし、そして入射ベクトルと法線ベクトルの内積から放射輝度を推定する。
　
　まったく異なるアプローチのため、直接光と間接光を二つのパスに分けるとしても、同じポイントライトの光の強さから、物理量としての整合性を保つ方法が分からない。うーむ。減衰係数という概念をライティングに持ち出すことをやめたほうがいいのかもしれない。
　あまり実用レベルにならない上に、ちょっと資料の不足により改善の目途が立っていないので、いったんこのGI機能はお蔵入りにしようか。敗北した気分だが。

　どうでもいいが、放射輝度推定に使うフォトン数を１個にすると、ボロノイ図のようなキモイものが浮かび上がる。

　
　

8分木空間でのレイトレースのコリジョンリスト収集処理を見直して10倍速くした

　フォトンマッピングの実装で、フォトンを1万～10万くらいバラまく処理が死ぬほど重かったので、8分木空間におけるレイトレースの処理を見直した。

　8分木はもとより衝突判定を高速にするための空間分割アルゴリズムだが、レイトレースをする際に、衝突判定をすべき空間の収集に最適化の余地があったのでいろいろコードを弄っていたら、10倍速くなった。

　まず簡潔に8分木の分割のロジックを説明する。が、簡略化のために2次元で考える。つまり、4分木として考える。
　例えば、分割レベル3の空間では、ルート空間、インデックス0～3の空間レベル1、インデックス0～15の空間レベル2の3つのレベルが作られる。この時、あるオブジェクトPが空間レベル2のインデックス3に属するとする。Pの衝突判定を行う場合、その空間と、そして親空間である、空間レベル1のインデックス0、ルート空間、この3つの空間に属するオブジェクトと比較をすればよい。これがN分木空間における衝突判定の高速化の原理である。ちなみに、空間レベルのグリッドをまたぐ場合は属する空間が親空間に移る。この辺の説明は以前の記事（Hashed-Octree(ハッシュ化八分木)による空間分割を実装した - My life accelerated）を参照されたい。
　

　さて、図を示すと上記のようなインデックスになる。特殊な配番に注意すること。これはシフト演算による処理の高速化のための、モートンオーダーを使った配番である。衝突処理の仕組みについては、前述の通りだが、ここで、レイトレースを行う場合の衝突処理を考える。原理的には、レイのポジションに対し、レイの方向ベクトルを加算し、そのたびにレイのポジションからN分木空間のインデックスを算出、衝突判定処理をすればよいが、それは効率的ではない。図を挙げてみよう。

　
　

　右上のオブジェクトはレイに衝突しないのは自明である。右下のオブジェクトは、グリッドをまたいでいるため、空間レベル2ではなく、空間レベル1のインデックス3に属している。私の従来の実装では、レイの衝突判定は、空間レベル2ベースでグリッドを移動する。インデックスのビジット順序は、空間レベル2の「0,2,3,9,12,14,15」、空間レベル1の「0,2,3」、そしてルート空間である。
　
　このような衝突リスト収集処理をエンジンから抜粋する。

std::set<uint32_t> GetColliderMortonList(SpaceOctree::OctreeFactoryBase* factory, Ray ray) {
    auto size = factory->GetMinBoxSize(); // 最大の空間レベルの分割サイズ
    auto rayForward = Vector3D(ray.dir.x * size.w, ray.dir.y * size.h, ray.dir.z * size.d); // レイが1ステップに進む距離
    auto rootAABB = factory->GetRootAABB(); // ルート空間
    
    _Vector3D<int16_t> grid = factory->CalculateGridCoordinate(ray.pos); // レイの初期位置から空間のグリッド座標を算出
    _Vector3D<int8_t> gridForward = _Vector3D<int8_t>( // レイ方向ベクトルの符号から1ステップにおけるグリッドの移動データを算出
        ray.dir.x >= 0.0f ? 1 : -1,
        ray.dir.y >= 0.0f ? 1 : -1,
        ray.dir.z >= 0.0f ? 1 : -1
        );

    Vector3D pos = Vector3D(grid.x * size.w, grid.y * size.h, grid.z * size.h) + rootAABB.bpos; // 初期位置
    _Vector3D<int16_t> nextGrid = grid;
    std::set<uint32_t> colliderList; // 衝突リスト（リストの中身は空間ハッシュ）

    while (rootAABB.Contains(pos)) {
　　 // グリッドから空間ハッシュ算出
        uint32_t number = SpaceOctree::Get3DMortonOrder(grid);

        // 空間ハッシュを、ルート空間まで遡って、衝突リストに格納していく（存在する場合のみ）
        for (int i = 0; i <= factory->GetSplitLevel(); i++) {
            uint32_t idx = static_cast<uint32_t>((number >> i * 3) + PrecomputedConstants::PowNumbers<8, 8>::Get(factory->GetSplitLevel() - i) / 7);
            if (factory->BoxExists(idx)) {
                colliderList.insert(idx);
            }
        }

        // 次のグリッド
        nextGrid = grid + gridForward;
        // 次の座標
        Vector3D nextpos = Vector3D(nextGrid.x * size.w, nextGrid.y * size.h, nextGrid.z * size.h) + rootAABB.bpos;

        // レイベクトルから、X方向、Y方向、Z方向のグリッドに到達する時のレイベクトルの係数を算出 
        float ax = ray.dir.x != 0.0f ? std::abs((nextpos.x - pos.x) / rayForward.x) : FLT_MAX;
        float ay = ray.dir.y != 0.0f ? std::abs((nextpos.y - pos.y) / rayForward.y) : FLT_MAX;
        float az = ray.dir.z != 0.0f ? std::abs((nextpos.z - pos.z) / rayForward.z) : FLT_MAX;

        // 最短で到達するグリッドの探索
        if (ax < ay && ax < az) {
            pos += rayForward * ax;
            grid.x += gridForward.x;
        }
        else if (ay < ax && ay < az) {
            pos += rayForward * ay;
            grid.y += gridForward.y;
        }
        else if (az < ax && az < ay) {
            pos += rayForward * az;
            grid.z += gridForward.z;
        }
        else {
            pos += rayForward;
            grid += gridForward;
        }
    }

    return colliderList;
}

　
　これはうまく動く。ただし、レイの1ステップにおける移動距離が、必ず最大空間レベル（例えば、上の4分木の例だとレベル2）の分割サイズにしかならない。これは、最適ではない。

　（少なくとも私の実装では）オブジェクトの存在しない空間は、ハッシュリストに登録されない。（あるオブジェクトを登録するとき、その親空間、更にその親空間...と遡って登録はする）。
　つまり、上記の例だと、ハッシュリストに登録されている空間は、空間レベル2の「5」、空間レベル1の「1,3」、そしてルート空間だけである。ならば、空間レベル1のインデックス0、左上の空間はまとめて無視できることがハッシュリストの構造から推測ができて、レイの距離は一気に9まで進めていいことがわかる。これを具体的にロジックで考えるならば、あるレイの点が属するすべての空間レベルのうち、「実際にハッシュリストに登録されている空間のレベル+1」の「分割サイズ」の距離だけレイを進めることができる。
　上記の例の場合、レイの始点がレベル2インデックス0空間とすると、レベル2のインデックス0及びレベル1のインデックス0はハッシュリストに存在せず、ルート空間（空間レベル0）のみが存在する。そのため、レイは空間レベル1の分割サイズだけレイを進めることができる。

　上記の疎空間におけるレイのステップ距離の最適化を施した後のコードが以下。

std::set<uint32_t> GetColliderMortonList(SpaceOctree::OctreeFactoryBase* factory, Ray ray) {
    auto min_size = factory->GetMinBoxSize();
    auto rootAABB = factory->GetRootAABB();
    
    _Vector3D<int16_t> grid = factory->CalculateGridCoordinate(ray.pos);
    _Vector3D<int16_t> gridForward = _Vector3D<int16_t>(
        ray.dir.x >= 0.0f ? 1 : -1,
        ray.dir.y >= 0.0f ? 1 : -1,
        ray.dir.z >= 0.0f ? 1 : -1
        );

    Vector3D pos = Vector3D(grid.x * min_size.w, grid.y * min_size.h, grid.z * min_size.h) + rootAABB.bpos;
    Vector3D next_pos = pos;
    std::set<uint32_t> colliderList;

    while (true) {
        uint32_t number = SpaceOctree::Get3DMortonOrder(grid);

        int exists_max_split_level = 0;
        for (int i = 0; i <= factory->GetSplitLevel(); i++) {
            int split_level = factory->GetSplitLevel() - i;
            uint32_t idx = static_cast<uint32_t>((number >> i * 3) + PrecomputedConstants::PowNumbers<8, 8>::Get(split_level) / 7);
            if (factory->BoxExists(idx)) {
                colliderList.insert(idx);
                // 存在していた空間レベルを保存
                exists_max_split_level = std::max(exists_max_split_level, split_level);
            }
        }

        // 探索すべき空間レベルの決定（+1する）
        exists_max_split_level = std::min(exists_max_split_level + 1, factory->GetSplitLevel());
        // 探索空間レベル基準の座標系で次のグリッド座標を決定する 
        auto next_grid = gridForward + factory->CalculateGridCoordinate(pos, exists_max_split_level);
        // 探索空間における分割サイズを計算する
        auto size = rootAABB.size() / static_cast<float>(1 << exists_max_split_level);
        // 次のグリッドサイズから、探索空間における座標を算出する
        next_pos = Vector3D(next_grid.x * size.w, next_grid.y * size.h, next_grid.z * size.h) + rootAABB.bpos;

        // 次のグリッドの座標がシーンから出ていたら終了
        if (!rootAABB.Contains(next_pos)) {
            break;
        }

        float ax = ray.dir.x != 0.0f ? std::abs((next_pos.x - pos.x) / ray.dir.x) : FLT_MAX;
        float ay = ray.dir.y != 0.0f ? std::abs((next_pos.y - pos.y) / ray.dir.y) : FLT_MAX;
        float az = ray.dir.z != 0.0f ? std::abs((next_pos.z - pos.z) / ray.dir.z) : FLT_MAX;

        if (ax < ay && ax < az) {
            pos += ray.dir * ax;
            grid.x = next_grid.x;
        }
        else if (ay < ax && ay < az) {
            pos += ray.dir * ay;
            grid.y = next_grid.y;
        }
        else if (az < ax && az < ay) {
            pos += ray.dir * az;
            grid.z = next_grid.z;
        }
        else {
            pos += Vector3D(ray.dir.x * ax, ray.dir.y * ay, ray.dir.z * az);
            grid = next_grid;
        }
    }

    return colliderList;
}

　これは小さなロジックの変更だが、非常に疎な空間（特に、空に向けて放たれるようなレイ）を進むレイのステップを著しく減らすことができる。これにより、私の開発中のレンダリングエンジンのベースのシーンであるコーネルボックスにおける、フォトン散布処理は10倍程度高速化された。

　しかし依然として現在はフォトンが1万個、バウンス制限3回という制約下でも、フォトン散布処理に10sec、ライトマップベイク処理に40secかかっている。特に、シーンの複雑度が増す場合、ライトマップのベイク処理はより増加することが想定される。高い品質のフォトンマッピングのために、まだまだチューニングの余地はあるだろう。（事前計算処理とはいえ、毎度数分待たされるとげんなりする）

　フォトンマッピングの実装は大体終わっているが、ノイズというかにじみがとれない。フォトンの量を十分に増やせばいずれなくなるのか、それとも何かミスがあるのか、判断がつかないでいる。全然わからない。私は雰囲気でGI実装をしている。

その気になれば前提知識無し機材無しの無の状態から2週間で美少女VTuberになれたという話

　最近、美少女になりました。
　いつもは、このブログでは文語体を用いてプログラミングに関する記事を投稿しているのですが、今回はあえて口語体で書くことにします。

　なんやかんやあって、美少女のアバターを使ってYoutubeに動画を投稿してしまうという事件を起こしました。
　私的には、情報発信の媒体がブログから動画共有サイトに移っただけとも言えると思うですが、世間一般的にはそれをVTuberと呼ぶらしいです。

　ことの発端は、とあるフォロワーの絵師ぎゃー氏が、とあるバーチャル幼女プログラマにドハマりしたのがきっかけでした。

www.youtube.com

ぎゃー氏(貝塚 (@gyaaaaaaaaaaaa) | Twitter)
きりみんちゃん(きりみん (@kirimin) | Twitter)

　「きりみんちゃんねる」はVTuberでは異色ともいえる、技術発信系VTuberです。ほかにもいるのかな？　こう言ってしまうのもなんですが男性Youtuberです。

　ぎゃー氏は、プログラマでもなんでもなく、さらに言うなら動画の内容は基本的に全然わかっていないとのことですが、淡々としゃべり続けるラジオのような動画が非常に好きらしく、きりみんちゃんの動画を死ぬほど摂取する日々を送っていたらしいです。（作業用BGMとして）

　そんな中、私はいつものようにレンダリングエンジンの開発ブログの更新（まさにここ）をして、適当に日々を送っていたのですが。ある日フォロワーとの交流として、確か「美少女になりたいよね～」みたいな話をぎゃー氏としました。
　「美少女になりたい」なんて言葉は、Twitter民ならだれでも口にするようなありきたりなセリフで、ラップで言うならYO!と同レベルの中身のない発言なわけですが...

顧客が求めていたりやさん pic.twitter.com/q84jZtyb6S

— 貝塚 (@gyaaaaaaaaaaaa) 2018年4月3日

朝起きたら美少女にされていた

　フォロワーを女体化するなんて正気の沙汰ではないと思うのですが、女体化されてしまいました。

　その後も女体化の攻防は続く。

りやちゃん…… pic.twitter.com/ZXhPIVf5Kz

— 貝塚 (@gyaaaaaaaaaaaa) 2018年4月4日

りやちゃん……… pic.twitter.com/aJrWwTPcfb

— 貝塚 (@gyaaaaaaaaaaaa) 2018年4月6日

　ぶっちゃけるとあまりの可愛さ（性癖にドストライクだった）に普通に自分（？）に惚れてしまった。

そしてその時はやってきた

りやさんバーチャル空間でりやちゃんになって技術の話して……

— 貝塚 (@gyaaaaaaaaaaaa) 2018年4月6日

貴様には美少女になってもらう

— 貝塚 (@gyaaaaaaaaaaaa) 2018年4月12日

奴の目的は....私をVTuberにすることだったのだ！！！（テテドン！！）

　どうやら、私が定期的にブログで情報発信しているのを見て、きりみんちゃんと同存在になれると思ったらしい。

りやちゃんモデル作ったらフェイスリグ買って実装して動画作るまでやります？(ノリでやりなよ〜wwって言うにはちょっとめんどそうだなと思った)

— 貝塚 (@gyaaaaaaaaaaaa) 2018年4月16日

　ド直球で「VTuberになってもらえませんか？」と言われたとき、私は非常に悩みました。なにせ、男性のしかも別に声が優れているわけでもない人間がVTuberになって一体どうするというのだ、という気持ちが強かったからですね。

　でも、それ以上に、「この可愛いキャラクターをこの先も観測したい」という気持ちが強かったので、私は「OK」と答えました。

3日後

りやちゃんLive2Dモデルが完成する

… pic.twitter.com/HJe4Jds1Yi

— 貝塚 (@gyaaaaaaaaaaaa) 2018年4月18日

　3日です。彼はもちろんLive2Dなんて触ったことがないお絵かきマン。Live2D凄すぎる。

　正直私も面食らってしまいましたが、その完成度に驚愕。恥をかき捨て動画作成に踏み切りました。

　即座に必要な機材・ソフトウェアを購入。

・マイク
・Webカメラ（ところでなんでWebカメラというのだろう）
・USBオーディオインターフェース
・FaceRig （顔を認識してアバターを動かすソフトウェア）
・FaceRig Live2Dプラグイン
・Live2Dサブスクリプション

　合計で1万円くらい？

　急いで動画の内容を考える。コンセプトは「美少女が意味不明な高度な技術を淡々を喋る動画」

　平日は普通に仕事なので、休日メインで作業。自分の声を録音して編集するという苦痛に慣れるのに非常に時間を要しました。
　私も動画撮影・編集は完全に素人。手探りでいろいろと試行錯誤。

そして

　闇がこの世に生れ落ちた。

ろりやちゃん on Twitter: "動画を投稿しました。本編は～0：10までで、それ以降おまけにC++ SFINAEの解説をしています。/

りやちゃんプログラミング講座①「C++ SFINAE」 https://t.co/75Xjk2AiXJ @YouTubeさんから"

　はっきり言って非常に完成度が低いです。ターゲット層も意味不明で、音量がめちゃくちゃ小さいという痛恨のミスも犯したり。

　でも、確かにこの瞬間、私はVTuberという世界に足を踏み入れたのでした。

　その期間、「ボクと契約してVTuberになってよ」と持ち掛けられた4月16日からおよそ13日。

　2週間で美少女VTuberになってしまいました。

　1個投稿すれば編集も慣れたもので、GWを活用し、怒涛のペースで動画を仕上げていきます。
2作目は、見てるだけで楽しいグラフィクスプログラミング×ライブコーディングを組み合わせた動画をつくって、まあそこそこ面白い動画になったんじゃないかなあと思います。BGMとかもいれたり。

ろりやちゃん on Twitter: "動画を投稿しました。本編00:10までで、おまけにGLSLでピクセルシェーダによるグラフィクスプログラミングを解説しています。プログラミングが分からない人にも楽しめる内容にしました。

りやちゃんプログラミング講座②「GLSL ピクセルシェーダ 前編」 https://t.co/azo05FW51k @YouTubeさんから"

　そして今日、GW最終日、3作目を投稿しました。

ろりやちゃん on Twitter: "GW最後の動画を投稿しました。本編は0:20までで、おまけにGLSLによるレイマーチ... https://t.co/SDqHtVsMAZ"

　字幕や通釈を加えた、一番動画らしい動画になりました。

　そんなこんなで、振り返ってみれば非常に密度の高い一か月で、よく頑張ったなあとしみじみ感じています。

　個人的にはノリと勢いで始めた活動にしては本気で、そして楽しく取り組めたことを凄いうれしく思っていて、まるでサークル活動のようだなと思いました。

　GWが終われば私も普通に仕事が待っているし、ぎゃー氏も自身の創作活動に時間を割かなくてはいけません。
　なので、とりあえず「バーチャル美少女プログラマ りやちゃん」としての活動は、小休止となります。
　1か月くらい期間をおいて、機会に恵まれれば、また誰向けかもわからない謎な動画を、まずはぎゃー氏と二人で楽しむことに重点を置いて作れていけたらなと思います。

　最後に、全ての始まりであるきりみんちゃんの言葉を引用しておわります。

VTuberは特別なものじゃなく、ブログなどと同じようなネット上でのアウトプットの新しいプラットフォームとしての可能性があるんじゃないかなと思っているので、いろいろと試してみたいという想いがあります。

　私もそう思います。別に、VTuberである必要はないと思うのですが、美少女のアバターを借りたエンジニアが技術動画を配信するという形態、そんな不思議なアウトプットをきっかけとして、インターネット上で自身の技術について共有するということがより一般的に広まって、技術のコミュニティが活性化されれば、それは素敵なことだなと思います。

Boost.Spirit.QiによるXモデルパーザ実装の紹介①

※先に断っておきますがバイナリフォーマット、スキンメッシュ及びアニメーションのパーズは未実装です。

　DirectX11からはD3DX系統の補助関数的なAPIはすべて排除されたため、シェーダーのコンパイル、テクスチャの読み込み、モデルの読み込みはユーザーが実装する必要がある。（Microsoftは別途ライブラリを用意する形にしてくれているが、結局外部ライブラリとリンクするなら、自分の好きなライブラリなりオレオレライブラリを作ったりする等、選択肢はいろいろある）

　3Dレンダリングエンジン開発において、プログラムの動作を確認するためには、やはりテストデータが必要である。そのため、レンダリングエンジンの開発の前に、3Dモデルのローダの実装は不可欠といえる。

　今回は、DirectX推奨の3Dモデルフォーマット、テキスト形式.xファイルのパーザ―の実装の紹介をする。

　C+＋でテキストファイルのパーズとなると、多くの人間が頭を悩ませることだろう。大抵の場合、文字列を線形探索して識別子を取得し、if文で分岐のような実装になるのだろうか。C++は文字列を言語でサポートしていないので、std::stringの恩恵を受けても中々に厳しい実装となることは想像に難くない。

　あるいは、C++11でサポートされた正規表現を使うという手もある。ただし、正規表現でファイルフォーマットの解析というのは、少しばかり無理があるような気もする。正規表現には、ネストされた構文の表現が困難であるといった様々な特性がある。正規表現がダメという話ではない。相性の問題だ。

　ところで、C++ Boost Libraryには、おあつらえ向きの構文解析ライブラリがある。Boost.Spirit.Qiだ。
　Boost.Spirit.Qiは、構文解析をC++の文法で完結する闇のライブラリである。冗談抜きで闇だ。
　
　文法はBNF文法に近く、演算子のオーバーロードによって、C++の構文の範囲内で文法を定義することが出来る。

　簡単な例を挙げてみよう。

#include <boost/spirit/include/qi.hpp>
#include <iostream>

using namespace boost;
namespace qi = boost::spirit::qi;

int main() {
    std::string const test = "1235_124";

    boost::fusion::vector<int, int> result; 
    
    auto itr = test.begin();
    auto rule = qi::int_ >> qi::lit('_') >> qi::int_;
    if (qi::parse(itr, test.end(), rule, result)) {
        std::cout << fusion::at_c<0>(result) << ',' << fusion::at_c<1>(result) << std::endl;
    } else {
        std::cout << "failed." << std::endl;
    }
}

Output
1235,124

　Boost.Spirit.Qi（以降Qiと呼称する）では、一つの文法に相当するものをRuleと呼ぶ。
　上記のコードの場合、任意の整数＋'_'という文字＋任意の整数という構文をRuleと定義している。

　ちなみにBoost.Fusionシーケンスを内部で作る版の（疑似）可変長変数版のパーズもある。こちらの方が使いやすいだろう。

#include <boost/spirit/include/qi.hpp>
#include <iostream>

namespace qi = boost::spirit::qi;

int main() {
    std::string const test = "1235_124";

    int r1, r2;
    auto itr = test.begin();
    auto rule = qi::int_ >> qi::lit('_') >> qi::int_;
    if (qi::parse(itr, test.end(), rule, r1, r2)) {
        std::cout << r1 << ',' << r2 << std::endl;
    } else {
        std::cout << "failed." << std::endl;
    }
}

　RuleにはAttributeという概念があって、構文解析後の値をどのような型として振舞うのかを示す。例えば、qi::int_のAttributeはintである。qi::litはUnused。つまりバインドされない。すると、全体のAttributeは「int, int」となり、そしてこのAttributeがqi::parseに渡されるバインド先の変数（これらもAttributesと呼ばれるようだ）と一致していなくてはならない。（実際には、Boost.Fusionシーケンスはスライシングを許容しているので、渡す変数が少ない分にはちゃんと機能する）

　これはQiの最も基本的な機能に過ぎない。Qiの機能をここで解説しきるには、残念ながら余白と私の知能が足りない。

　さて、では早速Xモデルパーザの実装の紹介をしていく。

　Xモデルのフォーマットは簡潔に述べると以下のようになる。

・ヘッダー
・テンプレート定義
・データボディ

　最終的なアウトプットとなるデータ構造を以下に示す。

class DXModel
{
public:
    enum class FileFormat {
        NONE,
        TEXT,
        BINARY,
        TZIP,
        BZIP
    };

    struct XHeader {
        std::string magic;
        std::string version;
        FileFormat format;
        int floatSize;
    };
    XHeader header;

    struct XProperty {
        std::string type;
        std::string name;
        int size;
    };

    struct XTemplate {
        std::string TemplateName;
        std::string UID;
        std::vector<XProperty> properties;
    };

    std::vector<XTemplate> templates;

    struct MeshTextureCoords {
        DWORD nTextureCoords;
        std::vector<Vector2D> textureCoords;
    };

    struct MeshFace {
        DWORD nFaceVertexIndices;
        std::vector<DWORD> faceVertexIndices;
    };

    struct MeshNormals {
        DWORD nNormals;
        std::vector<Vector3D> normals;
        DWORD nFaceNormals;
        std::vector<MeshFace> faceNormals;
    };

    struct MeshVertexColors {
        DWORD nVertexColors;
        std::vector<Vector4D> vertexColors;
    };

    struct Material {
        Vector4D faceColor;
        float power;
        Vector3D specularColor;
        Vector3D emissiveColor;
        std::string textureFileName;
    };

    struct MeshMaterialList {
        DWORD nMaterials;
        DWORD nFaceIndexes;
        std::vector<DWORD> faceIndexes;
        std::vector<DXModel::Material> materials;
    };

    struct Mesh {
        DWORD nVertices;
        std::vector<Vector3D> vertices;
        DWORD nFaces;
        std::vector<std::vector<int>> faces;

        // optional data elements
        MeshTextureCoords meshTextureCoords;
        MeshNormals meshNormals;
        MeshVertexColors meshVertexColors;
        MeshMaterialList meshMaterialList;
    } mesh;
};

　まずはヘッダーのパーザを作ってみる。QiにはGrammerというRuleの集まりを表現する型がある。HeaderというGrammerを作ってみよう。
　Xモデルヘッダーの形式の例は以下。

xof 0302txt 0064

　xofはマジックナンバーで固定。0302はバージョン番号。txtは形式。ほかにもバイナリやtzipなどがある。0064は浮動点小数精度。グラマーにすると...

struct FileFormatSymbol : public qi::symbols<char, DXModel::FileFormat> {
    FileFormatSymbol()
    {
        add("txt", DXModel::FileFormat::TEXT)
            ("bin", DXModel::FileFormat::BINARY)
            ("tzip", DXModel::FileFormat::TZIP)
            ("bzip", DXModel::FileFormat::BZIP);
    }
};

template<typename Iterator>
struct XHeaderGrammar : public qi::grammar<Iterator, DXModel::XHeader()> {
    XHeaderGrammar() : XHeaderGrammar::base_type(expr) {
        expr = +(qi::char_ - qi::lit(' '))
            >> qi::lit(' ') >> +(qi::char_ - (format | qi::lit(' ')))
            >> format >> qi::lit(' ')
            >> qi::int_
            >> qi::omit[*qi::space];

    }
    FileFormatSymbol format;
    qi::rule<Iterator, DXModel::XHeader()> expr;
};

　qi::symbolsで、文字列とEnum識別子のテーブルを作成している。これによって、特定の文字列にマッチするFileFormatのAtributeを持つRuleを定義することができる。
　+(qi::char_ - qi::lit(' '))は、空白を含まない文字の１個以上の繰り返しを意味する。つまり先頭のxofにマッチする。+演算子によってAttributeはstd::vectorとして振舞われるため、ここでのAttributeはstd::vectorとなる。ちなみにstd::stringとしても振舞ってくれる。Qi内部ではこういった似た型をよしなに変換してくれる機能も提供している。
　+(qi::char_ - (format | qi::lit(' ')))は空白及びファイルフォーマットを含まない文字の一個以上の繰り返し。0302まで。
　qi::omitは、[]の中のルールをパーズするが、それらをまとめて無視するディレクティブだ。つまり任意のRuleのAttributeをUnusedとして扱う。

　全体のAtributeをまとめると、「std::string、std::string、FileFormat、int」となっている。これは、XHeaderの定義と一致している。もちろんXHeaderは独立したユーザー定義型であるので、このままではこのRuleにバインドできない。そのためには、Boost.Fusionのアダプトという機能を利用するのだが、これは次回解説する。

　次に、テンプレート定義のGrammerを定義しよう。
　テンプレート定義の例は以下。

template MeshMaterialList {
 <F6F23F42-7686-11cf-8F52-0040333594A3>
 DWORD nMaterials;
 DWORD nFaceIndexes;
 array DWORD faceIndexes[nFaceIndexes];
 [Material]
}

　MeshMaterialListというテンプレートを定義するよ、という宣言だ。ボディの一行目はUID。それ以降は、型と変数名の列挙だ。しかし、ここで面倒くさいことに、特定の配列がそれ以前のプロパティの値に依存することがある。今回の例でいうとfaceIndexesがそれにあたる。しかし、ここでデータの持ち方を動的配列と考えることで、豪快に配列のサイズを無視することにする。
　ちなみに[Material]はテンプレートの限定使用という宣言らしい。個人的にはMaterialというテンプレートを入れ語構造にもつよ、という宣言だと認識しているのだが、公式のMSDNでは

テンプレートの限定使用
テンプレートは、開くか閉じることができ、限定使用も可能である。これにより、テンプレートに定義されたデータ オブジェクトの直接階層で表示されるデータ型を決定できる。開かれたテンプレートには制約はなく、閉じられたテンプレートはすべてのデータ型を拒否する。限定使用テンプレートでは、指定したデータ型を使える。

　なにを言っているのか全然わからない。日本語でしゃべってくれ。お前は本当にファイルフォーマットの話をしているのか？　ちなみにMSDNは大概クソみたいな翻訳（すべて原文は英語）なので、意味が通っていないどころが誤訳によりまったく意味が変わっていることも多々ある。DirectXの敷居が高いのもそのせいだといっても過言ではない。原文すら間違いがあることもある（実際、参照してるXファイルフォーマットのリファレンスは間違いだらけである。特に型のミスが多い）。込み入ったAPIの仕様を確かめようとすると、基本的に絶望しか待っていない。今回もその系統だろうか。つまり何が言いたいのかというと、編集リクエストボタンを用意していないくせにまともな解説も提供できないMSDNはクソということである。

　というわけで意味がわかめすぎるので、このテンプレート限定使用とやらも無視する。qi::omitで消し飛ばしてやろう。

template <typename Iterator>
struct XTemplateGrammar : public qi::grammar<Iterator, DXModel::XTemplate(), qi::space_type> {
    XTemplateGrammar() : XTemplateGrammar::base_type(expr) {
        expr = qi::no_skip[qi::lit("template") >> +qi::lit(' ') >> +(qi::char_ - (qi::lit('{') | qi::space)) >> qi::omit[*qi::space] >> qi::lit('{')]
            // PARSE UID
            >> qi::lit('<') >> +(qi::char_ - qi::lit('>')) >> qi::lit('>')
            // PARSE PROPERTIES
            >> +prop >> qi::omit[*(qi::char_ - qi::lit('}'))] >> qi::lit('}');

        // PROPERTY RULE
        prop = &qi::alpha >> -qi::lit("array") >> qi::lexeme[+(qi::char_ - qi::lit(' '))] >> +(
            qi::char_ - (qi::lit(';') | qi::lit('['))
            ) >> ((qi::lit('[') >> qi::int_ >> qi::lit(']')) | qi::attr(1)) >> qi::omit[*(qi::char_ - qi::lit(';'))] >> qi::lit(';');
    }

    qi::rule<Iterator, DXModel::XTemplate(), qi::space_type> expr;
    qi::rule<Iterator, DXModel::XProperty(), qi::space_type> prop;
};

　ここで新たな概念が登場している。Grammerのテンプレート引数に、qi::space_typeが渡されている。これは、パースにおいてスキップ設定が有効な時に空白及び改行をすべて無視するよ、という宣言だ。"AA BB"を+qi::char_でパースするとAABBという結果が返ってくることになる。

　まずはテンプレートの識別子をパースする。qi::no_skipとは、[]内のRuleにおいてスキップ設定を無効化するというディレクティブである。いや無効化するのかよ！とツッコミをいれたいところだが、スペースを識別子のセパレータに使うケースは多々あるので仕方ない。今回の場合も「template 識別子」のようにスペースで区切られている。
　また、今回は任意の回数のプロパティ宣言の繰り返しの表現を簡潔にするために、プロパティのRuleを別途定義して、それに+演算子を適用している。

　qi::alphaはアルファベットにマッチするPrimitive Rule。これに&演算子をつけると、「アルファベットにマッチするがイテレータは進めない」というRuleになる。つまり存在確認みたいなものだ。これは }で終わるかプロパティの宣言が続いてるかの判定に使っている。
　ai::lexemeはまあ大体no_skipと一緒。　

　(qi::lit('[') >> qi::int_ >> qi::lit(']')) | qi::attr(1)は、[(int)]という表現にマッチする、もしくはマッチしない場合は1として扱うRuleだ。
　[3] -> 3、[AAA] -> 1、その他 -> 1のようにパースする。
　
　

　さて、これでヘッダーとテンプレート識別子のパーズは終わりだ。ここまではファイルフォーマットの宣言部分に相当する。
　つまり、これから大量のデータボディに対するパーズが残っているわけだが....解説は次回に回そう。

　この記事を読んでいるあなたに、Boost.Spirit.Qiの魅力が伝わればと思う。

ミップマップを使ってラフネスのある材質のリフレクションを実装した

　以前、環境マップを用いて、リフレクションを実装した。

Cube Map Reflectionを実装した - riyaaaaasan’s blog

　上記の記事では完全鏡面に限定した実装となっており、マテリアルのラフネス値を無視した綺麗で鮮明なリフレクションしか実現できていない。
　このリフレクションを拡散面にも適用させるには、IBLの定義より環境マップの全テクセルについてライティング処理を行わなくてはならないが、非現実的のため採用していない。

　今回は、拡散面のリフレクションの近似表現として、ミップマップによる実装を紹介する。

　ミップマップとは、オリジナルのテクスチャの縦横半分のテクスチャ、さらにその半分のテクスチャ....という徐々に解像度が小さくなる階層構造を持つ(Ex: 128*128(Origin), 64*64, 32*32, 16*16....1*1)、あらかじめ圧縮されたテクスチャ群のことである。ミップマップによって、あまり詳細を求められない遠くの物体を描画するときに、より高速で、そして圧縮時のアルゴリズムによってはより高品質な結果を得ることがきる。もちろんメモリはより消費するが、33％ほどの増加にしかならない。

　これを使って、リフレクションの拡散表現を行ってみよう。ラフネスの高い材質のリフレクションとはどんな感じか？　簡単な話で、ボヤけている。理屈は置いといて、直感的にそう感じる見た目をしている。つまり、ぼかしをかけたテクスチャを複数枚用意して、ラフネスの値に応じてぼけたテクスチャを使用すればよい。ぼけたテクスチャといえばいろいろ実現手段はあるが、圧縮して解像度を下げたテクスチャを使えば、それもまた「ぼけた」表現になる。その場合幸いミップマップを使えば非常に簡素な記述で済む。その圧縮テクスチャの用意の方法はなんでもよいが（ここのこだわり方で大きく品質が変わってくる。近年のレンダリングエンジンでは後述するがPRTといった技術を使ってより精度の高いテクスチャを生成する）、今回は最も簡単な最近傍（Nearest neiboghr）法を使って実装してみる。

　まずNearest neiboghrによる圧縮コードから。当該部分のみ抜粋する。

Texture2D CompressTexture::NearestNeighbor(Texture2D tex, Size2Dd compressedSize) {
    Size2Dd src_size(tex.Width(), tex.Height());
    unsigned int channels = tex.Channels();
    std::size_t size = channels * compressedSize.w * compressedSize.h;
    char* buf = new char[size];
    const char* srcbuf = reinterpret_cast<const char*>(tex.get());

    for (unsigned int i = 0; i < compressedSize.h; i++) {
        for (unsigned int j = 0; j < compressedSize.w; j++) {
            _Vector2D<unsigned int> src_idx(
                j / static_cast<float>(compressedSize.w) * src_size.w,
                i / static_cast<float>(compressedSize.h) * src_size.h);

            unsigned int idx = i * compressedSize.w * channels + j * channels;

            for (unsigned int c = 0; c < channels; c++) {
                buf[idx + c] = srcbuf[static_cast<int>(src_idx.y * channels * src_size.w + src_idx.x * channels + c)];
            }
        }
    }

    Texture2D dst(compressedSize.w, compressedSize.h, channels, buf, size);
    return dst;
}

非常に簡単なアルゴリズムなので解説は省略する。
次に、テクスチャキューブのミップマップの生成コードを抜粋する。

std::vector<Texture2D> TextureUtils::CreateMipmaps(Texture2D srcTex, unsigned int miplevels) {
    if (miplevels == 0) {
        miplevels = static_cast<unsigned int>(std::floor(std::log2(srcTex.Width())) + 1);
    }

    std::vector<Texture2D> mipmaps;
    mipmaps.reserve(miplevels);

    mipmaps.push_back(srcTex);

    Texture2D compressed = srcTex;
    Size2Dd size(srcTex.Width(), srcTex.Height());
    for (unsigned int i = 1; i < miplevels; i++) {
        size = size / 2;
        compressed = CompressTexture::NearestNeighbor(compressed, size);
        mipmaps.push_back(compressed);
        FileManager::getInstance()->AddCache<Texture2D>(srcTex.GetTextureName() + std::to_string(i), compressed);
    }

    return mipmaps;
}

std::vector<Texture2D> TextureUtils::CreateMipmaps(TextureCube srcTex, unsigned int miplevels) {
    if (miplevels == 0) {
        miplevels = static_cast<unsigned int>(std::floor(std::log2(srcTex.Size())) + 1);
    }

    std::vector<Texture2D> mipmaps;
    mipmaps.reserve(miplevels * 6);

    for (int j = 0; j < 6; j++) {
        std::vector<Texture2D> compresseds = CreateMipmaps(srcTex.textures[j], miplevels);
        std::copy(compresseds.begin(), compresseds.end(), std::back_inserter(mipmaps));
    }

    return mipmaps;
}

TextureCubeの場合、メモリ上のテクスチャの並びは

PositiveX面テクスチャのミップマップ0.....N, NegativeX面テクスチャのミップマップ0....N.......NegativeZ面の...

という配置になるため、まず一面について着目し、ミップレベル0（オリジナル）から（必要であれば）log2(size) + 1までのテクスチャを生成し、配列に展開、また次の面ついて処理、という形になる。

あとは、この生成したテクスチャを使ってGPUリソースを作成するだけだ。
D3D11_TEXTURE2D_DESCのMipLevelsを指定し、D3D11_SUBRESOURCE_DATA配列で初期化する。D3D11_SUBRESOURCE_DATA配列のサイズは、TextureCubeの場合6 * MipLevelsになる。オリジナルのテクスチャの解像度が1024の場合、ミップレベルは最大10で、サブリソース配列のサイズは66。（0～10のミップレベルのテクスチャ11枚が６面分）

最後に、HLSLのピクセルシェーダで、テクスチャサンプリングの関数としてSampleメソッドの代わりにミップレベルを指定できるSampleLevelを使う。
今回は、ラフネスの0～1の値を単純にミップレベルについて線形に投影して実装した。
以下に示すのは、引数にラフネス値を増やした、リフレクションのカラーをフェッチするメソッドである。

float3 ReflectionFrensel(float4 posw, float4 norw, float4 eye, float eta, float roughness)
{
    float3 N = norw;
    float3 I = normalize(posw.xyz - eye);
    float3 R = reflect(I, N);
    float3 T = refract(I, N, eta);
    float fresnel = FrenselEquations(pow(eta - 1 / eta + 1, 2), N, I);

    float Mip = MAX_REFLECTION_MIPLEVEL * roughness;

    float3 reflecColor = EnviromentMap.SampleLevel(EnviromentSampler, R, Mip);
    float3 refracColor = EnviromentMap.SampleLevel(EnviromentSampler, T, Mip);

    float3 col = lerp(refracColor, reflecColor, fresnel);

    return col;
}

ここで、MAX_REFLECTION_MIPLEVELは適切な定数とする。今回は10で固定にしたが、環境マップの解像度を可変にするならコンスタントバッファーで与えるなりした方がいいだろう。

ちなみに、この説明だとミップマップのフェッチが離散的（0～10）になるのではないか？ という疑問が生じるところだが、SampleLevelメソッドは小数を与えると、二つのテクスチャについてよしなに補完してくれる機能を持つ。これはサンプラーの設定で変えることができて、D3D11_FILTER_MIN_MAG_POINT_MIP_LINEAR等を指定すれば線形補完してくれる。

実行結果を示す。まずはラフネス0から。これは最も品質の高いミップレベル0のテクスチャをフェッチするため、従来通り完全鏡面的な見た目になる。

次に、ラフネス0.5。今回の場合はミップレベル5辺りの画像、つまり1024 / (2^5)の解像度のテクスチャをフェッチしてくる。

圧縮アルゴリズムが適当過ぎるせいで品質は低いが、目的は達成できた。
改良すべきはミップマップの生成手段だが、先ほど述べた通りPRTを使うのが主流のようだ。

PRT(Precomputed Raddiance Transfer)とは、事前に放射輝度を遮蔽含めて計算しておくというアプローチである。私もまだ自分で実装したわけではないので解説の紹介は控えるが、全方向の放射輝度を保存するために、球面調和関数を用いて近似することで、ランタイムで現実的な処理速度を実現する。球面調和関数は完全直交な関数であるので、任意の球面上の関数を展開しSH基底関数の線形結合で表すことができる。それにより遮蔽情報を含む放射照度マップは非常にコンパクトなデータになる。環境マップテクスチャについても球面調和展開しておく。すると、二つの展開された関数について、基底関数の係数について内積を取れば、積分の性質により全球積分、すなわち前述した「全ての環境マップテクセルについてのライティング」を実現できるのだ。もちろん、球面調和関数の次数に依存した近似表現だが。

そのうち実装したいが、先にフォトンマッピングを実装したいのでかなり先になりそうだ。

今回はここまで。