GLSLのレイマーチングをシェルとAWKで実装したらどうなるか

## 生成物

![ray_marching.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/136875/23f9358f-eb77-f4ae-d07a-dcae50df6531.gif)

## 概要

レイマーチングをシェルとAWKで実装したらどんな感じになるのか、以下の点から気になったためやってみる。

* ピクセル単位の処理をするGLSLが、行単位の処理に特化したAWKにどう書き換わるか？
* レイマーチングはシンプルな考えで実現されているが、GLSL以外でもシンプルに実装できるか？
* AWKは制約が大きい言語だが、自然に実装できるか？
* どれほどの速度が出るか

GLSLのレイマーチング自体は、

* https://qiita.com/JPNYKW/items/7096fe59d1edf3ef3aa3

を参考にさせて頂く。

## 静止画の生成

### 全貌

* Bashで1行にピクセルでのx、y値を指定したデータをAWKに渡す
* AWKでは、1行に対応して、SVGのpathで1ピクセルを出力していく
* ピクセル単位のSVGは重すぎるので、ImageMagickでSVGからPNGへ変換する

### Bash

```
#!bash
w=320 h=240
{
  echo '<svg width="'$w'" height="'$h'" xmlns="http://www.w3.org/2000/svg">'
  for y in $(seq 0 $((h - 1))); do
    for x in $(seq 0 $((w - 1))); do
      echo $x $y
    done
  done \
    | awk \
      -v resolution0=$w -v resolution1=$h \
      -f ray_marching.awk
  echo '</svg>'
} | convert - ray_marching.png

```

### AWK

AWKで気を付ける必要がある点は以下。

* ローカル変数は、引数の最後に複数スペースを置いて引数として同様に並べる
* returnで配列は返せない、なので第一引数を利用する

```
function vec2(v, x, y) {
    v[0] = x;
    v[1] = (y == "") ? x : y;
}

function vec3(v, x, y, z) {
    v[0] = x;
    v[1] = (y == "") ? x : y;
    v[2] = (z == "") ? x : z;
}

function vec3Clone(v, v0) {
    vec3(v, v0[0], v0[1], v0[2]);
}

function vec3Length(v) {
    return sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
}

function vec3Add(v, v0) {
    vec3(v, v[0] + v0[0], v[1] + v0[1], v[2] + v0[2]);
}

function vec3Sub(v, v0) {
    vec3(v, v[0] - v0[0], v[1] - v0[1], v[2] - v0[2]);
}

function vec3Mul(v, s) {
    vec3(v, v[0] * s, v[1] * s, v[2] * s);
}

function vec3Mod(v, s) {
    vec3(v,
        v[0] % s + (v[0] < 0 ? s : 0),
        v[1] % s + (v[1] < 0 ? s : 0),
        v[2] % s + (v[2] < 0 ? s : 0));
}

function vec3Dot(v0, v1) {
    return v0[0] * v1[0] + v0[1] * v1[1] + v0[2] * v1[2];
}

function vec3Clamp(v, minVal, maxVal) {
    vec3(v,
        (v[0] < minVal) ? 0 : ((v[0] > maxVal) ? maxVal : v[0]),
        (v[1] < minVal) ? 0 : ((v[1] > maxVal) ? maxVal : v[1]),
        (v[2] < minVal) ? 0 : ((v[2] > maxVal) ? maxVal : v[2]));
}

function vec3Normalize(v,  l) {
    l = vec3Length(v);
    if (l == 0.0) {
        vec3(v, 0.0);
        return;
    }
    vec3(v, v[0] / l, v[1] / l, v[2] / l);
}

function getDistance(pos, size,  p, vs) {
    vec3Clone(p, pos);
    vec3Mod(p, 6.0);
    vec3(vs, 2.0);
    vec3Sub(p, vs);
    return vec3Length(p) - size;
}

function getNormal(v, pos, size,  ep, v0, v1, v2, baseDistance) {
    ep = 0.0001;
    vec3(v0, pos[0] - ep, pos[1], pos[2]);
    vec3(v1, pos[0], pos[1] - ep, pos[2]);
    vec3(v2, pos[0], pos[1], pos[2] - ep);
    baseDistance = getDistance(pos, size);
    vec3(v,
        baseDistance - getDistance(v0, size),
        baseDistance - getDistance(v1, size),
        baseDistance - getDistance(v2, size));
    vec3Normalize(v);
}

BEGIN {
    vec2(resolution, resolution0, resolution1);
    vec3(lightDir, 1.0);
}

{
    vec2(fragCoord, $1, $2);
    vec2(pos,
        (fragCoord[0] * 2.0 - resolution[0]) / resolution[1],
        (fragCoord[1] * 2.0 - resolution[1]) / resolution[1]);
    vec3(col, 0);
    vec3(cameraPos, 0.0, 0.0, 10.0);
    vec3(ray, pos[0], pos[1], 0.0);
    vec3Sub(ray, cameraPos);
    vec3Normalize(ray);
    vec3Clone(cur, cameraPos);
    size = 0.75;
    for (i = 0; i < 200; ++i) {
        d = getDistance(cur, size);
        if (d < 0.0001) {
            getNormal(normal, cur, size);
            vec3(col, 0.5 + 0.5 * vec3Dot(normal, lightDir));
            break;
        }
        vec3Clone(delta, ray);
        vec3Mul(delta, d);
        vec3Add(cur, delta);
    }
    vec3Clamp(col, 0.0, 1.0);
    printf "<path d=\"M%d,%d.5h1\" stroke=\"rgb(%d,%d,%d)\" />\n",
        fragCoord[0], fragCoord[1],
        int(col[0] * 255.99), int(col[1] * 255.99), int(col[2] * 255.99)
}
```

### ピクセル単位での並列化

それぞれのピクセル処理は独立しているためせっかくなら並列化したい。
Bashでの並列化、特に集約部分については、

* https://qiita.com/debug-ito/items/1bc877d62ec04dfa938a

を参考にさせて頂く。

気を付ける点は以下、

* ファイルを生成すると重たそうなためmkfifoする
* 行の途中で混ざらないようにしないとSVGデータとして成り立たなくなるので混ざらないようにする

```
#!bash
w=320 h=240
procs=16
rootDir=$(cd $(dirname $0) && pwd)
partDir=$rootDir/part
# パイプ用ディレクトリを作成する
mkdir $partDir
trap "rm -rf $partDir" EXIT
# 各プロセスで各パイプへの書き込みを並列実行する
for i in $(seq 0 $((procs - 1))); do
  mkfifo $partDir/$i
  for y in $(seq $((i * h / procs)) $(((i + 1) * h / procs - 1))); do
    for x in $(seq 0 $((w - 1))); do
      echo $x $y
    done
  done \
    | awk \
      -v resolution0=$w -v resolution1=$h \
      -f ray_marching.awk \
    > $partDir/$i &
done
# 各パイプから行単位で集約して画像を生成する
{
  echo '<svg width="'$w'" height="'$h'" xmlns="http://www.w3.org/2000/svg">'
  paste -d \\n $partDir/*
  echo '</svg>'
} | convert - ray_marching.png
```

使用マシンのコア数までは、指定したprocsに比例して実行速度が上がることが確認できた。

## アニメーション化

静止画の生成ができれば特に取り立てる点が無い。
既存のコードに少し手を加えつつ、静止画生成するシェルスクリプトを複数回呼び出すシェルスクリプトを書けばできる。

* awkコマンドでtimeを渡すようにする
* time違いで静止画を複数枚生成する
* 静止画をImageMagickのconvertでgifに変換する

## 感想

* レイマーチングはGLSL以外でもシンプルに実現できる
* AWKの制約はあるものの、それでもある程度自然なコードで実現できる
* 遅い、320x240の20フレを16コア3.6GHzのマシンで処理したが30分程掛かった