bashで3Dプログラミング

今日はbashと基本的なシェルコマンドだけで3Dレンダリング(ワイヤフレーム)をしてみました!

Github: ledyba / Bash3D

bashプログラミングテクニック

今回つかったbashのプログラミングテクニックについて、記録のついでに少しまとめます。シェルスクリプトの基本的な所は書きません。

あと、3Dプログラミングに関しては本に書いてある事以上のことが書けそうにないので、(今は)書きません。

bashのデータ構造

bashでそこそこ本格的にプログラミングする事を考えた上でまっさきに「辛そう…」ってなるのはデータ構造ですよね!今回のソフトでは、ベクトルや行列を綺麗に扱えないと困ってしまうでしょう。まずはそこを見ます。

bashの「値」は基本的に全てただの文字列ですが、「リスト構造」にだけはネイティブで対応しています。こんな感じ。

$ lst=(1 2 3)
$ echo ${lst[0]}
1
$ echo ${lst[1]}
2
$ echo ${lst[2]}
3
$ echo ${lst[3]}
#空行

データにアクセスする時に、必ず${}でくくらないといけないのが少し面倒です。ちなみに添字を付けないとリスト全体…と思いたいところですが、最初の要素が出てきます。

$ echo $lst
1

全体を表示するには、${lst[@]}とします。

$ echo ${lst[@]}
1 2 3

リストを定義するときに使ったカッコが出てこないので、リストをコピーしたい場合はそのカッコを補わないといけません。

$ lst2=(${lst[@]})
$ echo ${lst2[@]}
1 2 3

慣れればなんとかなるレベルですが、面倒です。

さらに気を付けないといけないのは、”(1 2 3)”という文字列を返す関数を$(command)で受けて変数に代入してもリストになりません。

$ function fun() { echo \(1 2 3\); }
$ lst=$(fun)
$ echo $lst
(1 2 3)

ただの文字列として代入されます。どうしてもしたい場合は、evalを使わないといけません。

#文字列展開が起こってから実行されるので、lst=(1 2 3)というコマンドが実行されることになる
$ eval "lst=$(fun)"
$ echo ${lst[1]}
2
$ echo ${lst[@]}
1 2 3

通常の用途ならそれで済むのですが、今回は出来る限り高速に処理したいので、こうやってコマンドが沢山必要になるのは避けたいところです。

ところで。

後に言うダイナミックスコープとevalを組み合わせると連想配列みたいなことも出来るのですが、今回のプログラムでは基本的にこのリストでデータ構造を管理しています。

インデックスを指定したアクセスをするためにコストが高いevalを行わなくてよいこと、ベクトルと行列が主役なのでリストで十分な事が理由です。

$ matrix=(MAT 1 0 0 0 0 1 .....)
$ vector=(VEC 0 0 0 1)

最初の要素に型の名前を入れて適宜assertすることで、動的型検査みたいなことをしています。

変数のスコープ

名前空間は基本的にひとつしかありません。関数のネストは一切関係なく上書きされていきます。

$ val=0
$ function fun() { val=1; }
$ fun
$ echo $val
1 #関数内の代入だが、グローバル領域が上書きされてしまった
$ function fun2() { val2=2;echo $val2; }
$ fun2
2
$ echo $val2
2 #オフサイドルールではなく、存在しない変数はグローバルに作られるみたい

一種のダイナミックスコープみたいなものだと理解しておけば大体書けます。

呼び出し元の変数がうっかり書き換えられてしまう可能性があるのですごく不便ですが、逆に利用することも出来ます。

「関数の引数に変数名を渡すと、evalと組み合わせることで指定した変数に結果を格納する関数」が作れます。こんな感じ:

$function setOne() { eval "$1=1"; }
$ setOne val1
$ echo $val1
1
$ setOne val2
$ echo $val2
1

これを使って「最初の引数は入力、最後の引数は出力」と規約を決めて関数を設計しています。たとえば行列の計算はこちらにあります。見た目がアセンブラみたいになりますネ。

「こんなスコープ再帰が出来ないのでは?」という気がしますが、案外なんとかなります。というのも、$(command)はサブシェルとかいうので実行されるらしくて、さらにサブシェルは別の変数空間で動作するようです。つまり、このスコープの問題は起こりません。…たぶん。よく分からない(◞‸◟ )

 #再帰関数といえば階乗である
function kaijo() {
    arg=$1
    next=$(expr $arg - 1)
    if [ $arg -gt 1 ]; then
        result=`kaijo $next`
        echo $(expr $arg \* $result)
    else
        echo 1
    fi
}

kaijo 10 --> 3628800

ついでにevalとこのスコープの仕様を使うと、擬似的な連想配列を作れますが、値のコピーが難しいこともあって使いませんでした。

$ val_key1=123
$ val_key2=456
$ function showKey1() { echo $(eval "echo \$$1_key1"); };
$ showKey1 val
123

固定小数点とexprコマンド

シェルスクリプトで計算をするには、exprコマンドを使う必要があります。このコマンドは整数の計算にしか対応していません。

$ expr 1 \* 2 \* 3
6
$ expr 1 \* 2 \* 3.2
expr: non-numeric argument

3Dソフトでそれでは困るので、整数だけで小数を計算します。それにはどうするかというと、扱う小数を適当に1000倍とかして、それを小数に見立てます。つまり、1000は1、1001は1.001、3140は3.140だと思うことにします。その場合、計算する時にちょっとした手間が必要になります。

#3.14 + 3.14
$ expr 3140 + 3140 #足し算・引き算はそのまま足し算で大丈夫です。
6280
#3.14 / 3.14
$ expr 3140 \* 1000 / 3140 #割り算するときは、倍率で掛けてから割ります。この世界では「1.0」は1000であることに注意
1000
#3.14 * 3.14
$ expr 3140 \* 3140 / 1000 #掛け算するときは、掛け算してから倍率で割ります。
9859

倍率を1000じゃなくてもっと高くすれば、もっと小数演算の結果が正確になります。

私の環境だけかもしれませんが、exprはどんな大きな数でもちゃんと扱ってくれるようなので、ガンガン倍率を上げていけば誤差がまったく気にならなくなります。これはすごい楽…(楽すぎた)

なお、sin/cosは(テイラー展開を自分で展開しない限り)計算できないようだったので、0~360度について事前に求めておいて、これを先ほどのリスト構造にいれて使っています。平方根も使いたかったんですが、どうやっても無理そうなので諦めました。

表示:オフスクリーンレンダリング

もちろんターミナルにはピクセルがないので、ターミナル上に表示する文字で代用します。普通に表示するなら、tput cup (line) (col)を使うとターミナル上の任意の位置に移動できるので、これを使いたいところです。

# 斜め45度に線を引いてみた
for1;do
    for2;do
        tput cup y x
        echo -n \*
    done
done

が、この方法では線を引く様子が目で分かるぐらい時間がかかります。これで最初レンダリングしたみたのですが、レンダリング中に線を引いている様子がバッチリ見えてしまい、あんまり回転アニメーションしてるように見えませんでした。

ほんもののゲームでもそういう、更新途中の絵が表示されてしまってちらつく問題があります。ほんもののゲームでは、そういう時は、書いてもすぐには表示されない「裏の画面」を用意しておいて、そちらに時間を掛けてレンダリングして、最後に表示される「表の画面」と入れ替える「オフスクリーンレンダリング」と「ダブルバッファリング」をしているのでした。私も同様にそのテクニックを使いました。

具体的には、こんな感じ。

SCR_BUFF=$(head -c $size < /dev/zero | tr '\0' '_')

今回の「ピクセル」は文字ですから、「裏の画面」はただの文字列になります。
画面のサイズを取得しておいて、そのサイズ分何もない文字列を意味する「_」をtrを使って入れておきます。空白でいいじゃないかと思うかもしれませんが、シェルスクリプトでは空白はかなり重要な意味を持っていて面倒なのでこうしています。

「ドットを打つ」時は、対応する文字列中のインデックスの文字を*に書き換えます。

SCR_BUFF=$(echo $SCR_BUFF | sed s/./*/<置き換える文字の位置>)

zshだとstr[12]=\*ってやると文字列を更新できるのですが、bashでは使えなかったので、sedを使って書き換えています。この処理が非常に重く、今回のレンダリングエンジン(?)の処理時間の殆どはこのドットを打つ処理に費やされています。上手い方法を知ってたら教えてください!

最後に表の画面に更新する方法ですが、単純にechoするだけです。この時、何も入っていない所には_が入っていたので、空白に直します。

$ tput cup 0 0
$ echo -n $SCR_BUFF | tr '_' ' '

ちゃんと幅に合わせて改行されるので、うまく表示できます。

高速化

インライン展開 → プロセスforkを抑える

当初綺麗に関数を使って書いた所、行列の掛け算に1秒近く掛かってしまい、さすがにレンダリングは出来ないのかな…と諦めかけたのですが、行列やベクトルの掛け算や足し算を全てインライン展開したところ、座標計算に関しては十二分すぎる程の速度が出せるようになりました。前述した通り、今回遅いのはオフスクリーンにピクセル(文字)を書き込む処理が異常に時間が掛かっているからです。

やはりプロセスの起動はものすごい重い処理のようで、可読性をそこまで損なわない範囲でプロセスの呼び出しを一箇所にまとめています。

感想

線を引くのにえげつない時間が掛かるのを見た時、初めて触ったBASICの処理系を思い出しました。懐かしい。

ところで、なんで3Dライブラリを作るとOpenGL風の名前にしちゃうんだろ。

ニコ動に「次はシェーディングだな!」というコメントがついているのですが、テクスチャの表示をやってみたいです!7色くらいしか使えないので、たいへんそう…。影は「暗い色」が基本的に無いのでかなりつらい気がします。

  1. x=0;x<10;++x []
  2. y=0;y<10;++y []