OBJ形式の3DモデルデータからCコードを自動生成

CG プログラミング

旧Wavefront Technologies 社の OBJ 形式で保存された3DモデルデータからCコードを自動生成するツールを作成したので公開します。
http://homepage.mac.com/radio_nights/files/obj_parser.tar.gz
次のように引数に .obj ファイルのパスを指定すると標準出力にコードが出力されます。

% ruby code_gen.rb polygon.obj

生成したコードは自分のプログラムに手軽に組み込むことができますので、モデルデータがちょっと必要な時に便利なのではないでしょうか。例えば、下の cube.obj から cube.c が生成されます。

# cube.obj
g cube
v 0 0 0
v 1 0 0
v 0 1 0
v 1 1 0
v 0 0 1
v 1 0 1
v 0 1 1
v 1 1 1
vn 0 0 -1
vn -1 0 0
vn 1 0 0
vn 0 -1 0
vn 0 1 0
vn 0 0 1
f 1//1 3//1 4//1 2//1
f 1//2 5//2 7//2 3//2
f 2//3 4//3 8//3 6//3
f 1//4 2//4 6//4 5//4
f 3//5 7//5 8//5 4//5
f 5//6 6//6 8//6 7//6

// cube.c generated from cube.obj
#include <stdarg.h>
#include "obj_format.h"
#define malloc_container(type, n)  ((type **)malloc(sizeof(type *)*n))
#define malloc_group               ((Group *)malloc(sizeof(Group)))
#define assert_not_null(pointer)    assert(pointer != NULL)

static float   *
vec_3f(float x, float y, float z)
{
	float          *v = (float *) malloc(3 * sizeof(float));
	assert_not_null(v);
	v[0] = x;
	v[1] = y;
	v[2] = z;
	return v;
}

static float   *
vec_4f(float x, float y, float z, float w)
{
	float          *v = (float *) malloc(4 * sizeof(float));
	assert_not_null(v);
	v[0] = x;
	v[1] = y;
	v[2] = z;
	v[3] = w;
	return v;
}

static int     *
vec_3i(int x, int y, int z)
{
	int            *v = (int *) malloc(3 * sizeof(int));
	assert_not_null(v);
	v[0] = x;
	v[1] = y;
	v[2] = z;
	return v;
}

static Face    *
face_new(int num,...)
{
	Face           *face = (Face *) malloc(sizeof(Face));
	assert_not_null(face);
	face->face_points_num = num;
	face->face_points = malloc_container(int, num);
	assert_not_null(face->face_points);

	int             i;
	va_list         args;
	va_start(args, num);
	for (i = 0; i < num; i++) {
		int            *fp = va_arg(args, int *);
		face->face_points[i] = fp;
	}
	va_end(args);

	return face;
}

static Group   *
_obj_group_new(int vertice_num, int tex_vertice_num, int normals_num, int faces_num)
{
	Group          *g = malloc_group;
	assert_not_null(g);
	g->vertice_num = vertice_num;
	g->tex_vertice_num = tex_vertice_num;
	g->normals_num = normals_num;
	g->faces_num = faces_num;
	g->vertice = malloc_container(float, vertice_num);
	assert_not_null(g->vertice);
	g->tex_vertice = malloc_container(float, tex_vertice_num);
	assert_not_null(g->tex_vertice);
	g->normals = malloc_container(float, normals_num);
	assert_not_null(g->normals);
	g->faces = malloc_container(Face, faces_num);
	assert_not_null(g->faces);
	return g;
}

static void 
obj_group_initialize__default(Group * g)
{
}

Group          *
obj_group_new__default()
{
	Group          *g = _obj_group_new(0, 0, 0, 0);
	obj_group_initialize__default(g);
	return g;
}

static void 
obj_group_initialize__cube(Group * g)
{
	g->vertice[0] = vec_4f(0.0, 0.0, 0.0, 1.0);
	g->vertice[1] = vec_4f(1.0, 0.0, 0.0, 1.0);
	g->vertice[2] = vec_4f(0.0, 1.0, 0.0, 1.0);
	g->vertice[3] = vec_4f(1.0, 1.0, 0.0, 1.0);
	g->vertice[4] = vec_4f(0.0, 0.0, 1.0, 1.0);
	g->vertice[5] = vec_4f(1.0, 0.0, 1.0, 1.0);
	g->vertice[6] = vec_4f(0.0, 1.0, 1.0, 1.0);
	g->vertice[7] = vec_4f(1.0, 1.0, 1.0, 1.0);
	g->normals[0] = vec_3f(0.0, 0.0, -1.0);
	g->normals[1] = vec_3f(-1.0, 0.0, 0.0);
	g->normals[2] = vec_3f(1.0, 0.0, 0.0);
	g->normals[3] = vec_3f(0.0, -1.0, 0.0);
	g->normals[4] = vec_3f(0.0, 1.0, 0.0);
	g->normals[5] = vec_3f(0.0, 0.0, 1.0);
	g->faces[0] = face_new(4, vec_3i(1, -1, 1), vec_3i(3, -1, 1), vec_3i(4, -1, 1), vec_3i(2, -1, 1));
	g->faces[1] = face_new(4, vec_3i(1, -1, 2), vec_3i(5, -1, 2), vec_3i(7, -1, 2), vec_3i(3, -1, 2));
	g->faces[2] = face_new(4, vec_3i(2, -1, 3), vec_3i(4, -1, 3), vec_3i(8, -1, 3), vec_3i(6, -1, 3));
	g->faces[3] = face_new(4, vec_3i(1, -1, 4), vec_3i(2, -1, 4), vec_3i(6, -1, 4), vec_3i(5, -1, 4));
	g->faces[4] = face_new(4, vec_3i(3, -1, 5), vec_3i(7, -1, 5), vec_3i(8, -1, 5), vec_3i(4, -1, 5));
	g->faces[5] = face_new(4, vec_3i(5, -1, 6), vec_3i(6, -1, 6), vec_3i(8, -1, 6), vec_3i(7, -1, 6));
}

Group          *
obj_group_new__cube()
{
	Group          *g = _obj_group_new(8, 0, 6, 6);
	obj_group_initialize__cube(g);
	return g;
}

#undef malloc_container
#undef malloc_group
#undef assert_not_nil

見ての通り、OBJ 形式は行指向のテキストデータなので、文字列処理が得意なスクリプトでさくっと片付けようとプログラムは Ruby で書きました。でも、ゴリゴリ正規表現でパースしているわけではなく、再帰下降パーサーを手書きしているので、C/C++で書いた場合と面倒臭さはあんまり変わらなかったかもしれません。現在サポートしているデータ型は、基本的に一部の形状データのみですが、個人的に当面の用途はこれで十分。いずれ気が向いたらマテリアルにも対応する予定です。

  • グループ（g）
  • 頂点（v）
  • 法線ベクトル（vn）

今の悩みはポリゴン数の多いモデルの扱い方。数万ポリゴンとなると生成コードのサイズが10MBを越えるのはざらで、コンパイルに非常に時間がかかる、もしくはコンパイルが出来ません。試しに30万ポリゴンのモデルを食わせてみたところ、コンパイル途中で仮想メモリが底を尽きGCCが音を上げてしまいました。まあ、そんなハイポリなデータを対象とすること自体間違っているのかもしれないのですけど．．．。単純にファイルサイズを抑えようとして、マクロの多用や関数名・変数名の短縮や空白スペースの削減を行っても焼け石に水で全然効果がありません。

ちなみに、上の画像はThe Stanford 3D Scanning Repositoryから取ってきたHappy Buddhaをレンダリングしたもの。元データがPLY形式なので Blender を使ってOBJ形式に変換して利用しました。変換後のデータサイズは、頂点数が7108、ポリゴン数が15536です。このサイズのモデルの場合、手元のPowerBookG4だと、コード生成に1分、生成したコードのコンパイルに1分半もかかります。一世代以上も前のマシンなのであんまり参考にはなりませんが、もう少し短くできないものかな？

% time ruby -I./lib code_gen.rb examples/happy_buddha.obj > examples/happy_buddha.c
'o' is not supported yet. 
'usemtl' is not supported yet. 
's' is not supported yet. 
ruby -I./lib code_gen.rb examples/happy_buddha.obj > examples/happy_buddha.c  51.60s user 0.81s system 89% cpu 58.868 total
% time gcc -I./src -c examples/happy_buddha.c 
gcc -I./src -c examples/happy_buddha.c  68.93s user 5.28s system 85% cpu 1:26.42 total

商用のモデリングツールには、Vertex Array や Display List に対応したOpenGL用のコードを生成する機能が備わっているものがあるようですね。どんなコードを吐くのかちょっと気になります。

MacOSXのデバッグ手法(1)

プログラミング

就職活動が苦戦しています。いまだ最終面接すらいけない始末。おかげで最近はちょっと自信喪失気味です．．．。
§
さて、今回はちょっと気分を変えて、MacOSXにおけるデバッグ手法を一つ紹介。
MacOSのメモリアロケーターは、標準でデバッグを支援する様々な機能が備わっています。例えば、プログラムの実行後に以下のようなメッセージが表示された場合、free() によるメモリの二重解放又は未割当てのメモリ領域の解放を通知してくれます。メモリ関連のバグは、普段は表面化しない事が多いので、大きな問題になる前に発見することができ大変重宝してます。

malloc: ***  Deallocation of a pointer not malloced: 0xbffff8ac; 
This could be a double free(), or free() called with the middle of an allocated block; 
Try setting environment variable MallocHelp to see tools to help debug

この問題の解決にあたっては、GDB から malloc_printf という関数にブレークポイントを設定してプログラムが停止したところでバックトレースを見れば、大体どこがエラーの原因なのか特定することができます。おそらくデバッグ中に何度もGDBを起動することになると思うので、.gdbinit に

b malloc_printf

と書いておけば便利でしょう。

参考URL：http://developer.apple.com/jp/technotes/tn2004/tn2124.html

クォータニオン

数学 CG

ずっと以前から頭の片隅にあったクォータニオンを、最近になってようやく少し分かった気がしてきました。
§
自分の印象としては、クォータニオンはその定義からして一見とっつきにくいものの、予め複素平面の知識があれば、おそらく自然と理解できるのではないかということ。クォータニオン自体が複素数の拡張ということで、なぜ単位クォータニオンの積が回転を表すのかは、複素数の積が回転を表すのとよく似ています。例えば、加法定理。昔からとても記憶力の弱い私は、実はあの sin と cos が入り混じった式を未だに覚えられません。サイン、コサイン、コサイン、．．．あれ？どっちだっけ？*1。でも、ある時この加法定理がオイラーの公式から至極単純に導けてしまうこと知って、大変驚いたことは今でも記憶に残っています。複素数を仲立ちとして、指数関数と三角関数が相互に関係し合っていることを実感できた一瞬でした。
この辺りの詳しい解説は、吉田武さんの「オイラーの贈り物」がとても参考になるでしょう。本書は、オイラーの公式の理解を目的として、その証明に辿り着くまでに必要な数学的概念を一つ一つ丁寧に説明した珍しい構成の本で、今回クォータニオンを学ぶ際にも何度か読み返したりしました。学生時代は数学が苦手だったけど心のどこかで理解したいと思っている方に是非お勧めします。ただし、オイラーの公式に辿り着くまでが結構長いので、頭からじっくりと読み進めるのもいいですが、既に前提知識がある方は、途中の章をすっ飛ばしていきなり本題から読んでもいいと思います。

オイラーの贈物―人類の至宝eiπ=-1を学ぶ (ちくま学芸文庫)

オイラーの贈物―人類の至宝eiπ=-1を学ぶ (ちくま学芸文庫)

§
さて、せっかくクォータニオンでベクトルを回転する術を学んだので、早速OpenGLを使って仮想トラックボールを作ってみました。元ネタは、GLUTのサンプルプログラム trackball.c。実装方法はオリジナルと異なりますが、基本的なアイデアは同じです。操作方法は、ウィンドウ内でマウスをドラッグするとオブジェクトが回転するほか、さらにシフトキーを押しながらドラッグすると拡大・縮小することができます。興味のある方は参考にどうぞ。

http://homepage.mac.com/radio_nights/files/trackball.tar.gz

*1:ちなみに、教科書に書いてある公式をなかなか鵜呑みに出来ない性格だったので、学校の数学の成績はいつも悪かった．．．

射影ベクトルと外積

数学

久しぶりに「ゲームプログラミングのための3Dグラフィックス数学」から。ぶらぶらと本屋に行ったついでに、また立ち読みしてきました。○ュンク堂書店さん、本当に冷やかしばかりですみません．．．。
§
射影ベクトルと外積の計算は線形変換なので行列で表現できます。あらためて指摘されて別に驚くことでもないですが、内積と外積が入り交じった行列計算を行う場合に便利です。例えば、外積を使って任意軸周りの回転行列を求める時など応用できます。

射影ベクトルの表現行列

ベクトルPからベクトルQへの射影ベクトルP'は
\vec{P'} = \frac{\vec{P}\cdot\vec{Q}}{|\vec{Q}|^{2}} \vec{Q}
と求められます。これをPからP'への線形変換とみなすと、
\vec{P'} = \frac{1}{|\vec{Q}|^{2}} \begin{pmatrix} {Q_{x}}^{2} & Q_{x}Q_{y} & Q_{x}Q_{z} \\ Q_{x}Q_{y} & {Q_{y}}^{2} & Q_{y}Q){z} \\ Q_{x}Q_{z} & Q_{y}Q_{z} & {Q_{z}}^{2} \end{pmatrix} \begin{pmatrix} P_{x} \\ P_{y} \\ P_{z} \end{pmatrix}

外積の表現行列

ベクトルPとベクトルQの外積は
\vec{P}\times\vec{Q} = \begin{pmatrix} P_{y}Q_{z} - P_{z}Q_{y} \\ P_{z}Q_{x} - P_{x}Q_{z} \\ P_{x}Q_{y} - P_{y}Q_{x} \end{pmatrix}
ですが、これをベクトル・行列の積に分解すると、
\vec{P}\times\vec{Q} = \begin{pmatrix} 0 & -P_{z} & P_{y} \\ P_{z} & 0 & -P_{x} \\ -P{y} & P_{x} & 0 \end{pmatrix} \begin{pmatrix} Q_{x} \\ Q_{y} \\ Q_{z} \end{pmatrix}

§
まだ本書を買ってもいない自分が言うのもなんですが、これは確かに良い本ですね。CGに必要な数学の知識が網羅されていると同時に説明も丁寧。分かりやすさは読者のレベルに応じて個人差があると思いますが、これからCGを学ぼうとする方にお勧めします。私も就職できた暁には（それはいつ？）、ぜひ購入してじっくり読んでみたいと思います。ところで、本書は第2版（原書）が出版されてから既に5年も経っていますが、第3版の予定はあるでしょうか？あの「Real-Time Rendering」は第3版がもうすぐ出るらしいですけど*1。

Mathematics for 3d Game Programming and Computer Graphics (Game Development Series)

Mathematics for 3d Game Programming and Computer Graphics (Game Development Series)

*1:まだ出ていないと思ったのですが、既に7月末に発売されていますね。

メモリ管理

プログラミング

最近、ある事情からメモリ管理の手法を調べることになり、ウェブ上の資料を漁っていました。
§
まず最初にあたったのは、「The Memory Management Reference」。このサイトは、メモリ管理が抱える問題点やその解決手法を傍観するのに便利でした。
一般にメモリ管理では、対象とするレイヤーをアプリケーションに限定した場合、まず覚えておくべき３つの制約があります。すなわち、

  1. CPUオーバーヘッド
  2. インタラクティブな停止時間（(1)との違いがよく分かりませんが）
  3. メモリオーバーヘッド

これらの制約は互いにトレードオフの関係にあって、例えば実行速度を要求すると、反対にメモリ管理自体に要するメモリ消費量が大きくなってしまいます。極論でいうと、メモリの浪費（外部断片化）を気にせずに済むならば、空いている領域にどんどん要求されたメモリを割り当てていけば速いというわけです。このトレードオフの関係については、「メモリ管理の内側」と題された developerWorks の記事に実装方法別の分かりやすい説明を見つけました。同時に、dlmalloc を含む様々なアロケータを紹介していて、各アロケータを比較検討したい時にも役立ちそうです。
ところで、メモリ管理プログラムを自作することはそもそも有効な手段なのでしょうか？。結論から先に言うと、メモリ管理を熟知した専門家でない限り、自作するのは現実的ではないようです。メモリプールのようなサブアロケータにしても、ポインタと絡んだやっかいなバグの混入は避けにくく、中途半端な実装では返って性能低下を招く可能性があります。
しかしながら、あらゆる場合においてアロケーターを自作するのは無駄というわけではありません。特定の状況下においては、アロケータの自作は十分検討する価値があります。例えば、組み込みシステムなど、リソースの制約が大きい環境下では、既存の実装では性能要件を満たせない事が多々あると推測されます。また、組み込み以外の分野においても、メモリの割り当てと解放（又はこれに付随する処理）がボトルネックと判明しているならば、独自の割り当てアルゴリズムを用意するのは一つの手だと思われます。例えば、現在Linuxカーネルで採用されているスラブアロケータは、この典型例と言えるでしょう。スラブアロケータでは、カーネルが、プロセス記述子やファイル記述子など一定サイズのオブジェクトを頻繁に生成・破棄する事実に着目し、一度生成したオブジェクトをキャッシュする事で高速化を実現しています。また、割り当て手法が Buddy System であるにも関わらず、メモリの内部断片化が発生しにくい設計になっていて高い空間効率を維持しています。
メモリ管理の制約により万能なアロケータを作るのは到底無理ですが、このようにシステムの挙動をつぶさに観察し、その特性に合わせてアロケータを設計すれば、処理速度の高速化が望めそうです。

あとがき

実は、今回のエントリーを書くきっかけとなったのは、先日ある会社に選考課題の回答として提出したメモリ管理プログラムです*1。課題の内容は、malloc/free の自作ではなく、あくまでサブアロケータを実装するというものでした。残念ながら、結果は不合格。「仕事のコードじゃないんだし、こんなものでいいだろう」と途中で性能を妥協してしまったのが敗因かもしれません。とほほっ。そこで、どなたか面倒見のいい方からの添削を期待してソースコードを公開しておきます*2。メモリ管理の手法を調査する前に作ったので、アルゴリズムに稚拙なところがありますが、そこは大目に見て頂ければと思います。
http://homepage.mac.com/radio_nights/files/memory-pool.tar.gz

*1:もしかすると、これを読んでどこの会社かピンと来る人がいるかもしれませんね。

*2:念のため断っておきますが、公開にあたって先方には事前に許可いただいてます。

任天堂ゲームのユーザー体験

UI設計におけるユーザー体験については、他方で散々解説されてると思いますが、個人的に思うところがあったので敢えて書き残しておきます。
§
夜遅くアパートに帰ってきて、だらだらとTVを眺めていた時のこと。ふと流れた「しゃべる！DSお料理ナビ」*1のCMが目に留まりました。CMの内容は、DSのナビゲーションにしたがって、女優の菅野美穂さんが沖縄料理のゴーヤチャンプルーを作るというものです。
菅野美穂さんのDSのある毎日
このCM映像を見た時、一瞬にして「あっ！」と気付きました。最近、巷でよく見たり聞いたりするユーザー体験っていうのはこういう事なのかと。ユーザー体験の重要性については、これまでウェブ上の解説記事やブログを通してある程度知っていましたが、説明が抽象的で実感としての理解は乏しかったように思います。現在も、正直なところ、他人にはっきりと説明できるレベルまで分かったと言えません。でも今は、以前にはなかった言葉にならないもやもやした概念を身体の中に感じるようになりました。
おそらく大切なのは、ユーザーが楽しんでいる姿がぱっと頭の中に映像として直感的に浮かんでくるかどうか、そして、その姿を見つめる自分も楽しいと思えるかどうかということ。任天堂は自社ゲームのデザインにおいて、このようなゲームを取り巻く”風景”を強く意識しているような気がします。つまり、ゲーム機とユーザーの二人称の関係だけで物事を考えるのではなく、更にゲーム機に触らないもう一人のユーザー（潜在的なユーザー）を追加した三人称の関係で考えているのではないでしょうか。

しゃべる!DSお料理ナビ

しゃべる!DSお料理ナビ

*1:2年前に発売されたゲームにも関わらず、今もなお売れ続けているのは驚きです。

ソーシャルブックマークのデータマイニング

プログラミング

Kikker の学習の仕組みと Rocchio アルゴリズム - naoyaのはてなダイアリー から。
ずっと以前に del.icio.us の登録タグを利用して、これと似たように Cosine similarity からユーザー間の類似性を計算するプログラムを作ったことがあります。
きっかけは、偶然ウェブ上で見つけたアマゾンのレコメンデーションシステムに関する資料。そこには、ユーザーに紹介するおすすめ商品を求める方法の概説が書いてありました。確かこの頃プログラミングのネタをひたすら探していて、その中の候補として協調フィルタリングに関心があったのかな。当時は全く前知識がなかったので、資料を読んだ時は「こんな単純な内積計算で実現されてるのか」と驚いた記憶があります。その後、勢い余って半日ぐらいでプログラムを書き上げました。（もちろん、アマゾンが所有するような大規模データベースとなると、線形代数の参考書の問題を解くようにはいかないのは分かってますが。）ちなみに、この時期ちょっとSchemeにはまっていたので、言語の練習を兼ねてプログラムはGaucheで書いたのでした。
ユーザーの類似性を計算するアルゴリズムはおおよそ以下のような感じです。

  • 適当に収集したユーザー名（行）と各ユーザーの登録タグ名（列）から、登録タグ数を要素とする行列を作成する。なお、登録タグ名は同じ意味の単語でも表記はユーザーによってまちまちなので適当に正規化しておく。
  • ユーザー名の集合から適当にユーザー二人を選んでその行ベクトルを求める。
  • 行ベクトルの内積を計算して結果の正負で類似性を判定する。

ただこの時は、アルゴリズムがそこそこ思い通りに動いたという事だけで満足してしまって、プログラミングが一通り終わった後、いまいち興味が続かず、結局この類似性判定プログラムは日の目をみないままお蔵入りになってしまいました。もう少し根気よく継続していればものになったかもしれないのに。残念。