床井研究室

■ 2009年10月07日 - とっても簡単なボクセル化

納豆襲来

長男が仕事で納豆を作っているので、少しでも売り上げに貢献しようと、その納豆を買って毎日食べています。本当に毎日毎日食べています。納豆はおいしいですよ。健康にもいいですし。でも、毎日毎日毎日食べ続けていると、少しばかり飽きてくることもあります。それで納豆チャーハンにしてみたり、油揚げに包んで巾着にして焼いてみたり、いろいろ工夫しながら毎日毎日毎日毎日食べています。でも、チャーハンに納豆を入れると、チャーハンのパラパラとした食感が失われてしまいます。巾着は、納豆だけでもダイレクトに食べられるうちの奥さんならおいしくいただけるのでしょうけど、納豆を食べると言う食習慣自体がなかった私には少しつらいものがあります。本当に毎日毎日毎日毎日毎日…ああ、そうだよ、私は納豆が嫌いなんだよ。もう、どうしよう。納豆を毎日毎日毎日毎日毎日毎日飽きずにおいしく食べられる方法はないでしょうか。

ちなみに長男の職場は、「ふるさとをください」という映画の舞台にもなりました。この映画は、まあ、そういうある種のメッセージを持った映画なんですけれど、脚本がジェームス三木さんというだけあって、普通のホームドラマとしても楽しめます。

ボクセル化の方法

夏休みも終わったことだし、夏休みゼミは一旦お休みにして、「しどう」君に約束したボクセル化のサンプル書きます。ポリゴンモデルをボクセル化する方法 (solid voxelization) には、対象形状を 6 方向から平行投影してデプスバッファを取得して論理積を取る方法やら、depth peeling を使う方法やら、本当にたくさんの人が様々な手法を提案しています。私の趣味的にはスキャンライン法を使いたいところですが (1 パスで済むし CSG にも対応できるので), これはラスタライザを自分で書くことになりますから、ちょっと面倒です。あんまり複雑なことをここに書くのは難しいので、効率はあんまりよくありませんが、クリッピングを使ったとっても簡単な方法を紹介します。

平行投影で図形を描く

とりあえず、対象形状を平行投影で表示するプログラムを作ります。2 点 Pmin, Pmax を対向する頂点とする直方体の空間 (境界箱) に含まれる図形を画面に表示します。

物体と境界箱

glOrtho() を使って、境界箱をビュー空間に設定します。ただし、そのままでは視点が原点にありますから、これを境界箱の前方面の位置に移動します (実際には図形を反対方向に移動します). 透視投影だと視点を前方面上に置けませんが、平行投影では問題ありません。

#if defined(_WIN32)
#  define _USE_MATH_DEFINES
#  define _CRT_SECURE_NO_WARNINGS
#  include <GL/glew.h>
#  include <GL/glut.h>
#elif defined(__APPLE__) || defined(MACOSX)
#  define GL_SILENCE_DEPRECATION
#  include <GLUT/glut.h>
#else
#  define GL_GLEXT_PROTOTYPES
#  include <GL/glut.h>
#endif

/*
** 境界箱
*/
static GLdouble pmin[] = { -1.0, -1.0, -1.0 };
static GLdouble pmax[] = {  1.0,  1.0,  1.0 };

/*
** 画面表示
*/
static void display(void)
{
  /* 境界箱をビュー空間に設定する */
  glMatrixMode(GL_PROJECTION);
  glLoadIdentity();
  glOrtho(pmin[0], pmax[0], pmin[1], pmax[1], 0.0, pmax[2] - pmin[2]);

  /* 視点を境界箱の前方面の位置に移動する */
  glMatrixMode(GL_MODELVIEW);
  glLoadIdentity();
  glTranslated(0.0, 0.0, -pmax[2]);

  /* 画面消去 */
  glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

  /* 図形表示 */
  glutSolidTeapot(0.5);

  glFlush();
}

/*
** 初期設定
*/
static void init(void)
{
  /* 背景色 */
  glClearColor(0.0, 0.0, 0.0, 1.0);

  /* 光源設定 */
  glEnable(GL_LIGHTING);
  glEnable(GL_LIGHT0);

  /* 隠面消去処理 */
  glEnable(GL_DEPTH_TEST);
}

/*
** メインプログラム
*/
int main(int argc, char* argv[])
{
  glutInit(&argc, argv);
  glutInitDisplayMode(GLUT_RGB | GLUT_DEPTH);
  glutCreateWindow(argv[0]);
  glutDisplayFunc(display);
  init();
  glutMainLoop();

  return 0;
}

これで、とりあえず図形を描くことができます。

平行投影で図形を描く

ビュー空間をずらす

この状態で、ビュー空間を少し奥にずらしてみます。

...

/*
** 画面表示
*/
static void display(void)
{
  GLdouble offset = 0.6;

  /* 境界箱をビュー空間に設定する */
  glMatrixMode(GL_PROJECTION);
  glLoadIdentity();
  glOrtho(pmin[0], pmax[0], pmin[1], pmax[1], offset, pmax[2] - pmin[2]);

...

すると前方面で図形がクリップされて、中が見えてしまいます。

前方面でクリップされた図形

クリップされた部分に見えているのは、向こう側のポリゴンの裏側です。もし、この部分だけを描くことができれば、図形の断面形状を得ることができそうです。そこで、この部分を横から見てみます。

断面を横から見る

このように、クリップされていない部分ではポリゴンが偶数回描かれるのに対し、クリップされた部分では奇数回描かれています。そこで、ポリゴンを描くときにポリゴンの色を表示するのではなく、フレームバッファに保持されている色を反転するようにします。これは glLogicOp() で設定できます。こうすると、ポリゴンが偶数回描かれたところ最初の色 (背景色) が描かれ、奇数回描かれたところでは反転した色が表示されます。

...

/*
** 初期設定
*/
static void init(void)
{
  /* 背景色 */
  glClearColor(0.0, 0.0, 0.0, 1.0);

  /* 前景色 */
  glColor3d(1.0, 1.0, 1.0);

  /* フレームバッファに書きこむたびにフレームバッファの内容を反転 */
  glLogicOp(GL_INVERT);

  /* 隠面消去処理は行わない */
  glDisable(GL_DEPTH_TEST);
}

...

上のプログラムでは背景色が黒なので、ポリゴンの色 (前景色) を白にしています。また、この処理では陰影計算と隠面消去処理を行う必要はありませんから、光源の設定は削除し、デプステストはオフにしています。そして画面クリアの際にデプスバッファをクリアしないようにして (GL_DEPTH_BUFFER_BIT を削除する), glEnable(GL_COLOR_LOGIC_OP); (glEnable(GL_LOGIC_OP); でもいいかも?) を実行してから図形を描画するようにします。

...

/*
** 画面表示
*/
static void display(void)
{
  ...

  /* 画面消去 */
  glClear(GL_COLOR_BUFFER_BIT);

  /* 論理演算処理開始 */
  glEnable(GL_COLOR_LOGIC_OP);

  /* 図形表示 */
  glutSolidTeapot(0.5);

  /* 論理演算処理終了 */
  glDisable(GL_COLOR_LOGIC_OP);

  glFlush();
}

...

これで、断面形状だけを描くことができます。

断面形状だけを描く

ただし、この方法には欠点 (というか、仕様上の制限) があります。ポリゴンの重なりが偶数か奇数かだけで判断しているので、複数の物体が重なっている部分が排他的論理和のように空洞になります。これはこれで「正しい」と思っているのですが、対象の形状を複数の物体を組み合わせて表現することもよくあります。その場合には、ステンシルバッファを使って重なりの数を勘定するなどの方法をとる必要があると思います。

重なっている部分が空洞になる

ボクセルデータを生成する

ビュー空間をずらしながら断面形状を表示して、それを配列に保存します。断面形状はフレームバッファオブジェクトにレンダリングし、テクスチャメモリに格納してからテクスチャとして読み出します。ちょっと疲れてきて解説を書くのがつらくなってきたので、ソースプログラムだけ置いておきます。また気力が戻ってきたら解説を書きます。このプログラムはボクセル化したデータをもとに、5 秒周期で断面形状を画面に表示します。気力があったらもうちょっと洒落たサンプルを作りたいと思います。OBJ や PLY の読み出しプログラムは自分で作ってくれ > 「しどう」君。

このプログラムは配列へのデータの書き込みにだいぶ時間がかかっています。ポリゴン数を 1,600 万枚にしても、処理時間はあまり増えませんでした。そこでテクスチャメモリから CPU 側に転送する変わりに pixel buffer object を使ってみました。

でも、処理時間はかえって遅くなってしまいました (RADEON 9800 / Windows XP の場合). なにか間違えてるのかな。