Emscriptenを使ってブラウザ上でレイトレする

これは[KLab Advent Calendar 2016](http://qiita.com/advent-calendar/2016/klab)の5日目の記事です。

---

C++で開発したレイトレーサ「tsukihi」をEmscriptenを使ってJavaScriptに変換して、ブラウザ上で動作させました！

次のリンクから動作を確認できます。

- [#emscripten_tsukihi - gam0022.net/webgl](http://gam0022.net/webgl/#emscripten_tsukihi)

![#emscripten_tsukihi - gam0022.net/webgl](https://qiita-image-store.s3.amazonaws.com/0/17718/7af1035a-8aca-a5a8-b59d-dff4fd067b50.png)

[tsukihi](http://gam0022.hatenablog.com/entry/raytracingcamp4)は[レイトレ合宿4!?](https://sites.google.com/site/raytracingcamp4/)向けに[edupt](http://kagamin.net/hole/edupt/)をベースに開発したレンダラーです。

この記事の前半では、レイトレーサにおけるGPU実装の課題や制約などについて紹介します。

後半では、実際にC++のレイトレーサをEmscriptenで移植して得られた知見などを紹介します。

- Emscriptenの紹介と導入方法
- EmscriptenでOpenGL+GLFW3をビルドする注意点
- Emscriptenの印象

読者の対象としては、レイトレは実装したことがあるけど、Emscriptenは触ったことがないという方を想定しています。

レイトレに興味が無い方でも、Emscriptenの雰囲気を掴む目的であれば、後半の内容がお役に立てるかもしれません。

# GPUによるレイトレの限界とCPUへの回帰
去年のWebGLアドベントカレンダーではWebGLフラグメントシェーダを使って、ブラウザ上で動作する**GPU**を用いたリアルタイムなレイトレーシング（レイマーチング）を実装しました。

- [これがGPUの力！Three.jsによる“リアルタイム”なレイトレーシング](http://qiita.com/gam0022/items/03699a07e4a4b5f2d41f)

今年はあえてGPUではなく**CPU**をつかったレイトレに挑戦しました。

パフォーマンスでは圧倒的にGPUが優れていますが、GPUだけでは難しい問題もあります。
Solid AngleのArnold Rendererをはじめとして、映画などで実際に使われているレンダラーの多くはGPUに未対応です（要出典）。背景にはGPUでの実装における制約があると筆者は考えています。
では、どのような制約があるのかを説明していきます。

## 大きなデータをCPUからGPUに送ることができない
CPUからGPUへのデータの転送はコストがかかるので、なるべく避けなくてはいけません。

最初のデモでは、レイマーチングという手法を使うことで、GPU側で実装した距離関数でシーンを定義しました。
こうすることで、シーン情報に関するCPUからGPUでのデータの転送が不要になりました。

しかし、距離関数による表現にも限界があります。例えば、フラクタルのような幾何学的な形状は得意ですが、アニメのキャラクターのモデルを距離関数で表現するのは非現実的です。
そこで、次の記事ではポリゴンデータを浮動小数点テクスチャに詰めてCPUからGPUに送ることで、ポリゴンをGPUでレイトレすることに挑戦しました。

- [これがGPUの力！three.jsによる“リアルタイム”なレイトレーシング 〜宝石編〜](http://qiita.com/gam0022/items/9875480d33e03fe2113c)

頂点の数が数百程度あればこの手法でも十分なのですが、頂点の数だけテクスチャをフェッチするので、数万ポリゴンのモデルを複数表示するような状況だと対応できません。

## 状態を保存する手段に乏しい
テクスチャに値を書き出す以外に状態を保存する手段が無いので、以前の処理結果をキャッシュして高速化するなどの最適化は困難です。

## 複雑なアルゴリズムの実装の難易度が高い
WebGLで使用できるシェーディング言語であるGLSLには様々な制約があります。
例えば、再帰関数は使えませんし、基本的にforのループ回数は定数でなくてはなりません。
またGPUは予測分岐が苦手であるため、条件分岐のような処理も苦手です。
このため、実装できるアルゴリズムにも制限があります。

とはいえ、工夫によっては複雑なアルゴリズムも実現は可能だとは思いますので、最初の2つの問題と比較すれば軽微なものだと思います。

## まとめ
GPUによるレイトレへの挑戦はまだまだ諦めていませんが、これらの課題もあるのも事実だと思います。
そこで、今回は勉強の意味を込めて、CPUのレイトレに回帰することにしました。

# EmscriptenでC++のコードをブラウザで動かす
前置きが長くなりましたが、ここから後半のEmscriptenの説明に入ります。

EmscriptenはC++などから生成されるLLVMのバイトコードを入力として、ブラウザ上で動作するJavaScript(asm.js)に変換するコンパイラです。

具体的には`emcc`や`emmake`コマンドを用いて、C++からasm.jsの変換を行います。

公式サイトはコチラです。
http://kripken.github.io/emscripten-site/

## Emscriptenのインストール
次の公式サイトの通りにEmscriptenをインストールしました。
http://kripken.github.io/emscripten-site/docs/getting_started/downloads.html

Mac環境では、Portable Emscripten SDK for Linux and OS Xをダウンロードして解凍し、次のコマンドを実行することでインストールできました（2016-12-04現在）。

```
# Fetch the latest registry of available tools.
./emsdk update

# Download and install the latest SDK tools.
./emsdk install latest

# Make the "latest" SDK "active"
./emsdk activate latest
```

Python3系だと、`./emsdk update` で失敗したので、Python2系に切り替える必要がありました。

## Emscriptenでビルドできるようにする
元々tsukihiはWindowsで開発していて、VC++でしかビルドできない状態でした。
Emscriptenでビルドする前に、まずはMacのClangでビルドできる状態に修正しました。

OpenMPを無効化したのと、`fopen_s` のようなVC++の独自の関数を置き換えました。
詳しくは次のPRをご覧ください。
https://github.com/gam0022/tsukihi/pull/3

元々依存ライブラリはほぼ無かったので、Clangでビルドできる状態にすれば`emcc`コマンドでビルドができるようになりました。

本当にわずかな変更だけでEmscriptenでブラウザ上で動くようになりました！Emscriptenすごい！

## OpenGLで結果を画面に出力する
ブラウザ上で動くようになったものの、結果画像はファイルとしてPNGに出力する仕様なので、このままではブラウザ上で結果を確認できません。

せっかくブラウザ上で動かすのであれば、途中結果を含めて画面出力させたいと思いました。

Emscriptenは最初からOpenGLに対応していたので、画面出力するためにOpenGLを用いました。

### OpenGLをEmscriptenでビルドする
`Clang`ではビルドできるOpenGLを使ったC++のコードでも、`emcc`でビルドするためには定数を宣言したりヘッダを読み込む必要がありました。

```
#ifdef EMSCRIPTEN
    #include <emscripten/emscripten.h>
    #define GL_GLEXT_PROTOTYPES
    #define EGL_EGLEXT_PROTOTYPES
#endif
```

この定数の存在はこのサイトを見て知りました。
http://d.hatena.ne.jp/simpg/20120619/1340121206

どうしてEmscriptenではこれらの定数が必要なのか私もよく分かっていません。

### GLFW3をEmscriptenでビルドする
EmscriptenではOpenGLだけでなく、GLFW3にも対応しています。

`emcc`のオプションに`-s USE_GLFW=3`をくっつけるとGLFW3が有効となり、GLFW3をつかったC++のコードをビルドできるようになります。

### glDrawPixelsが使えない問題に対処
OpenGLにはBMPを画面出力する`glDrawPixels`というAPIがあるので、最初はこれを使おうと考えました。
しかし、`glDrawPixels`はOpenGL ES 2.0では削除された関数でした。
WebGLはOpenGL ES 2.0相当のAPIなので、試してみたところ、やはり`glDrawPixels`は使えませんでした。

そこで、板ポリを1枚置いて、2次元のテクスチャを貼り付けることで`glDrawPixels`を代用しました。

途中結果を出力するためにテクスチャのアップデートをする必要がありました。
これには`glTexSubImage2D`を使いました。

こうして、途中結果をOpenGLで画面出力できるようになりました。
詳しくは次のPRをご覧ください。
https://github.com/gam0022/tsukihi/pull/4

## emscripten_sleep
ネイティブ版ではsleepをせずに標準出力や画面の更新の反映ができていたのですが、Emscripten版ではsleepが必要でした。

ところがCのsleepはこんな感じの無限ループ（busyループ)に置き換えられてします！

```
function sleep(ms) {
  var t = Date.now() + ms;
  while(Date.now() < t) ;
}
```

そこで登場するのが`emscripten_sleep`という代替の関数です。

`emscripten_sleep`を用いるためには、`emcc`のオプションに`-s ASYNCIFY=1`をくっつける必要がありました。

詳しくは公式サイトに紹介されています。
https://kripken.github.io/emscripten-site/docs/porting/asyncify.html

# 考察
## Emscriptenのパフォーマンス

MacBook Air 13インチ 2013Midモデルでの実行結果です。

同じ環境同じスペックでもEmscripten版の方が7倍ほど遅くなりました。

| 環境 | 実行時間(sec) | 実行時間(比率) |
| :--- | ---: | ---: |
| ネイティブ | 4.54495 | 1.0 |
| Emscripten | 30.752 | 6.766 |

特にEmscripten向けのチューニングを行ったわけでもないので、個人的には思ったよりは速いなという印象を受けました。

## マルチスレッドについて
今回はマルチスレッドの対応まで着手できなかったのですが、レイトレにおいてCPUのコアを複数使えないのは致命的な欠点だと考えています。

軽く調査したところ、`Web Worker`などEmscriptenの外の技術を使わないと実現できないようなので、既存のC++のプログラムのマルチスレッドの対応はかなり大掛かりになるではないかという印象を持ちました。

# 感想とまとめ
ほとんど苦労することなくC++のレイトレーサをブラウザで動かすことができました。
導入も簡単ですし、すぐにブラウザで動かせるように作られていたので、Emscriptenはとても優秀だと感じました。

またOpenGLだけでなく、GLFWまで対応していることには驚きました。
しかし、[公式サイトのOpenGLの項目](http://kripken.github.io/emscripten-site/docs/porting/multimedia_and_graphics/OpenGL-support.html)では、GLFWは存在すら言及されておらず、OpenGLの使用の制約なども曖昧だったので、その周辺の情報の不足を感じました。

ブラウザ上で動くレイトレーサの開発は完全に個人の趣味なのですが、Emscriptenはこの目的を達成するため強力な道具としての可能性を大いに感じました！

ところで、筆者はC++やEmscriptenに関して完全な素人なので、何かツッコミ点等あればご指摘お願い致します！

最後に[WebGLアドベントカレンダー](http://qiita.com/advent-calendar/2016/webgl)に向けてブラウザ上で動くGPUによるパストレーサを鋭意開発中なので、期待して待っていて下さい！

![pathtracing-1.gif](https://qiita-image-store.s3.amazonaws.com/0/17718/fd602727-b891-9c6d-c4e0-66e6cf062b9f.gif)