Hatena::ブログ(Diary)

最速チュパカブラ研究会

 | 

2009年2月11日

Canvasによる3Dテクスチャマッピングパフォーマンスチューニング(仮題) 23:53

MAX 打ち上げのときに川崎さんに「英語の記事書いたら絶対ウケるから書くべきだよ」と言われていつ書こうかなーと思ってたら、そういえば11日は休日だったので、日本語の下書きだけでも一気に書いてみることにしました。 といっても、欲を出してあれもこれも書こうとして、結局まだ書ききれてませんけど。

タイトル

あと、今日(11日)は私の誕生日でもあります。25になりました。そろそろ鏡を見るのが怖くなってきますね。

以下、書きかけ


Texture Mapping with HTML Canvas And Performance Tuning

Introduction

Adobe MAX 2009Spark Project は、拡張現実(AR)のデモを展示し、来場者の注目を集めていた。Shibuya.JSメンバーもこのデモに感激し、是非 Javascript でもこのようなデモを行いたいという話題になった。AR のデモを行うための大きな障壁はカメラであり、この問題は一朝一夕に解決しそうにないので一旦忘れることにした。一方で、3次元コンピュータグラフィクス(以下、3DCG)をどうレンダリングするか、という話は、わりとすぐに解決しそうな気がした。

Javascript エンジンは、何十倍というオーダーで高速化しているし、CanvasSVG のおかげで、いまやJavascriptは、ベクタグラフィクスもラスタグラフィクスも自由に扱える。点、線分、ポリゴン、どれも容易に描画できる。そうすると、テクスチャマッピングを実装したい、という欲求が出てきた。テクスチャマッピングは、3DCG に高い表現力を持たせるための効果的な手段である。私は、魅力的な 3DCG のデモを作るためには、テクスチャマッピングは必須の技術であろうと考え、Javascript でも実用的な速度でテクスチャマッピングが可能であることを確認するために、いくつかのデモを作成した。本稿ではまず、HTML Canvasでテクスチャマッピングを行う方法を解説し、次にCanvasのパフォーマンスについても考察する。

In Adobe Max 2009, Spark Project showed us impressive demonstrations of Augmented Reality(AR) using FLARToolkit. We, Shibuya.JS were also impressed and began discussion about how Javascript (instead of Flash!) can do demonstration like that. First issue, capturing camera is "deep" problem and not to be solved in a day. But I had a foresight to solve second issue, 3D rendering.

Nowadays, Javascript engines are radically boosted. In addition, now we can draw both vector and raster graphics using SVG and Canvas in Javascript. Points, lines and polygons -- no difficulty. And I got to desire to do texture mapping in Javascript. Visual impact of texture mapping is exquisite and necessary to make impressive demonstration. Therefore, I wrote some demonstration programs and made sure Javascript can render textured polygons. This document describes how these demos work and discussion about performance tuning of HTML canvas.

Demos

まず最初に、結果を言おう。テクスチャマッピングは、各ブラウザ現在実装されている Canvas の機能で実現可能である。ただし、その速度については、十分実用的なブラウザもあれば、やや不安なものもある。実際に、あなたのシステムインストールされているブラウザで、以下のデモを確認してほしい。

First of all, see results. My conclusion is YES, Javascript and canvas (of course, currently implemented in release versions) can render textured 3D scene. But its performance relies on browser's engine, especially graphic backends. Check these demos out on browsers installed in your computer.

demo1 http://gyu.que.jp/jscloth/
screen1 Figure 2-1
demo2 http://gyu.que.jp/jscloth/miku.html
screen1 Figure 2-2
demo3 http://gyu.que.jp/jscloth/touch.html
screen1 Figure 2-3

最初のデモは、単純なテクスチャマッピングである。メッシュ状のポリゴンにテクスチャを貼り付けている。メッシュが変形したときに、テクスチャも適切に変形していることがわかる。

2番目のデモは、モデラを使用して作成したデータをレンダリングする例である。上に挙げたデモの中では最も「重い」デモで、1400ポリゴンほどある。

3番目のデモは、スフィア環境マッピングと呼ばれる技術のデモである。スフィア環境マッピングは、オブジェクトから見た周囲の様子をテクスチャとして貼り付けることにより、映り込みを表現する技術である。これは非常に見栄えがよく、高度なことをしているように見えるが、通常のテクスチャマッピングとの違いは、テクスチャ座標を静的に持っているか、動的に生成するか、という程度の小さなものである。

The first demo shows simple texture mapping. Textures are mapped on "cloth" model that consists of polygon mesh. Textures deform following swing of the cloth.

The second demo renders a model composed on modeling tool. This is the heaviest demo, which contains about 1400 polygons.

The third demo shows a technique called "Sphere Environment Mapping". Sphere environment mapping renders pseudo metallic reflection by mapping a texture that contains "environment" from object's view. This demo looks very attractive but is not hard to implement. Difference between previous demos and this demo is not much -- Generate texture coordinates dynamically or store statically.

Texture Mapping Basics

まず、テクスチャマッピングとはどのようなものか、基本的なことを確認しておく。Figure 3-1 にテクスチャマッピングの概念を示す。

Firstly, I'd like to explain basics of texture mapping. Figure 3-1 shows overview of u-v based texture mapping.

texture mapping Figure 3-1

Figure 3-1 では、左のテクスチャを右のポリゴンに貼り付けている。一般的に、1枚のテクスチャはいくつかの部分で構成されている。例えば、人物の描画に使うテクスチャは、顔、腕、胴体、脚などの画像を1枚に詰め込んだものである。テクスチャマッピングを行う場合、テクスチャのある部分を座標で指定して切り出すことになる。このときの座標系は UV座標系 と呼ばれ、テクスチャの左上が原点となり、テクスチャの右端が u=1、テクスチャの下端が v=1 となるよう正規化されている。モデルデータの作成者は、ポリゴンの各頂点にUV座標系の座標(UV座標)を割り当てることにより、テクスチャ画像上のある点とポリゴンの各頂点との対応を指示することができる。レンダラは、この指示に従ってテクスチャを変形して描画しなければならない。

In Figure 3-1, the source on left side is mapped onto a target polygon on right side. Texture image generally consists of several parts. For instance, a texture of man contains a face, legs, arms and so on. A part of it is clipped by specifying coordinates. These coordinates are called 'u-v coordinates' where left-top of the image is (u,v)=(0,0), right-end is u=1 and bottom-end is v=1. Author of model data can specify correspondence relation between vertices of polygon and pixels on source image. Renderer must deform textures following u-v coordinates.

Canvas は、描画結果を変形するために transform メソッドを用意している。transform メソッド引数にアフィン変換行列を指定することで、以後の描画にすべてアフィン変換が適用される。もちろん、これは drawImage メソッドにも適用されるので、transform メソッドに続けて drawImage メソッドを呼び出すことで画像の変形を行える。

以下の例では、画像の縦方向を縮小して描画している。

Canvas has a method "transform" to deform rendered images. transform method takes an affine transformation matrix and apply it to subsequent drawings. Of course, it's also applied to drawImage method then you can get deformed bitmap images.

Following example draws an image with vertical scaling.

var g = document.getElementById("canvas").getContext("2d");

g.drawImage(img, 0, 0);

g.transform(1, 0, 0, 0.3, 0, 0);
g.drawImage(img, 200, 0);

出力結果を Figure 3-2 に示す

Figure 3-2 shows a result

texture mapping Figure 3-2

画像の変形が可能であることを確認したら、次は transform メソッドに指定する行列の求め方を考えよう。transform メソッドは、

Next, obtain the matrix which transform method requires. transform method takes 6 parameters like this:

transform(a, b, c, d, tx, ty)

という引数を受け取ると、

These parameters are built into a matrix like this:

a c tx
b d ty
0 0 1

という行列として解釈する(transform メソッドを複数回呼び出すと、前回の変換と合成される点に注意)。描画時は、この行列に変換前の座標を縦ベクトル

and then source coordinates are treated as col vectors like this:

x
y
1

として右から掛け、変換後の座標 (x', y') を得る。式に書くと

transforming the col vectors, then destination coordinates are obtained

x' = a*x + c*y + tx
y' = b*x + d*y + ty

となる。

アフィン変換行列には「変形」と「移動」が同時に含まれているので、まずは「変形」の方を考える。

Figure 3-3 に示すように、三角形のポリゴンを描画するとき、3つの頂点のうち1つを基点にして、のこりの頂点にベクトルを2本伸ばすことができる。貼り付け元のテクスチャ上でのベクトルを A および B 、描画先でのベクトルを A' および B' としよう。

Affine transformation matrix consists of "deform" part and "move" part. So let's start with calculation of deformation.

Imagine two vectors shown in Figure 3-3. Vector A is from point[0] to point[1] of the triangle on the source texture. B is from point[0] to point[2] on the source texture, A' and B' are corresponding vectors on the (target) polygon.

texture mapping Figure 3-3

ベクトル A および B に(移動を除く)アフィン変換をかけた結果、ベクトルを A' および B' になればよいのだから、

We have to get A' and B' as a result of applying affine transformation to A and B. So...

A'x = a*Ax + c*Ay (1)
A'y = b*Ax + d*Ay (2)
B'x = a*Bx + c*By (3)
B'y = b*Bx + d*By (4)

(1)と(3)を行列で書くと

(1) and (3) in matrices:

 |A'x| = |Ax Ay| |a|
 |B'x|   |Bx By| |c|

だから、

So invert the matrix and multiply from left. Then a and c are determined.

 |Ax Ay|^-1 |A'x| = |a|
 |Bx By|    |B'x|   |c|

という操作で a と c を求めることができる。b と d についても、

 |Ax Ay|^-1 |A'y| = |b|
 |Bx By|    |B'y|   |d|

で求めることができる。コーディング作業を楽にするために、2x2行列のユーティリティを作っておこう。

Get started by writing utilities for 2x2 matrix.

function M22()
{
	this._11 = 1;
	this._12 = 0;
	this._21 = 0;
	this._22 = 1;
}

M22.prototype.getInvert = function()
{
	var out = new M22();
	var det = this._11 * this._22 - this._12 * this._21;
	if (det > -0.0001 && det < 0.0001)
		return null;

	out._11 = this._22 / det;
	out._22 = this._11 / det;

	out._12 = -this._12 / det;
	out._21 = -this._21 / det;

	return out;
}	

これは簡単な2x2行列のクラスで、以下のようにして使える。

Following example calculates inverted matrix using this class.

var m = new M22();
m._11 = 0.5;
m._22 = 0.5;
var inv = m.getInvert();

alert([inv._11, inv._12, "\n"+inv._21, inv._22].join('  '));
// 2 0
// 0 2

では早速、テクスチャマップされた三角形を描く「drawTriangle 関数」の実装を始めよう。まずはスケルトンを書いて仕様を決める。

Now write a skeleton of drawTriangle function that renders a textured polygon.

function drawTriangle(g, img, vertex_list, uv_list)
{
}

この関数は、第1引数に Canvas の 2Dコンテキスト、第2引数にテクスチャとして使う Image オブジェクト、第3引数に三角形の各頂点座標の配列、第4引数にUV座標の配列を受け取る。呼び出し側のコードは以下のようになるだろう。

drawTriangle function takes four parameters. The first is a 2d-context of the canvas, the second is an image to be mapped, the third is a list of vertex positions and the last is a list of u-v coordinates.

We will use drawTriangle function like this:

drawTriangle(g, img, 
[
 100, 100,
 150, 110,
 60, 160
],
[
 0.75, 0,
 1   , 0,
 0.75, 0.25
]
);

ここで指定したUV座標は、Figure 3-3 に示したテクスチャの青い部分である。

それではまず、変形の部分の計算だけ実装してみよう。

u-v coordinates in the example above are blue area in Figure 3-3.

Following code implements "deform" part.

function drawTriangle(g, img, vertex_list, uv_list)
{
	var _Ax = vertex_list[2] - vertex_list[0];
	var _Ay = vertex_list[3] - vertex_list[1];
	var _Bx = vertex_list[4] - vertex_list[0];
	var _By = vertex_list[5] - vertex_list[1];

	var Ax = (uv_list[2] - uv_list[0]) * img.width;
	var Ay = (uv_list[3] - uv_list[1]) * img.height;
	var Bx = (uv_list[4] - uv_list[0]) * img.width;
	var By = (uv_list[5] - uv_list[1]) * img.height;

	var m = new M22();
	m._11 = Ax;
	m._12 = Ay;
	m._21 = Bx;
	m._22 = By;
	var mi = m.getInvert();
	if (!mi) return;
	var a, b, c, d;

	a = mi._11 * _Ax + mi._12 * _Bx;
	c = mi._21 * _Ax + mi._22 * _Bx;

	b = mi._11 * _Ay + mi._12 * _By;
	d = mi._21 * _Ay + mi._22 * _By;

	g.save();
	g.transform(a, b, c, d, 0, 0);
	g.drawImage(img, 0, 0);
	g.restore();

	// for debugging
	g.strokeStyle = "#f00";
	g.moveTo(vertex_list[0], vertex_list[1]);
	g.lineTo(vertex_list[2], vertex_list[3]);
	g.lineTo(vertex_list[4], vertex_list[5]);
	g.lineTo(vertex_list[0], vertex_list[1]);
	g.stroke();
}

このコードで注意すべき点は、変数 Ax, Ay, Bx, By に値をセットするとき、UV座標に画像の幅と高さを掛けている点である。この操作により、UV座標が描画先と同じピクセル座標系になる。先ほどの呼び出し側のコードをもう一度実行すると、Figure 3-4 を得る。

Note that code above multiplies width/height by u/v to convert into pixel coordinates.

Use this implementation from aforementioned (caller) sample. Then you'll get a result shown in Figure 3-4.

texture mapping Figure 3-4

赤い三角形は、このポリゴンが描画されるべき位置である。次にすべきことは、アフィン変換行列の「移動」の要素を使い、この位置にテクスチャを移動させることである。

This polygon must be located inside red triangle in Figure 3-4. So we have to calculate "move" part of the affine matrix.

Figure 3-3 に示したベクトル A および B の基点のUV座標を(u0, v0)、A' および B' の基点のピクセル座標を(x0, y0)、画像の大きさを W x H とすると、(u0, v0)は先の変形により(移動を行わない場合)

When we don't set any translation, the pixel at (u0, v0) will be drawn at:

(a*u0*W + c*v0*H , b*u0*W + d*v0*H)

where (u0, v0) is u-v coordinate at the origin of A' and B', WxH is size of the image.

の位置に描画される。これを

We want to translate this point to:

(x0, y0)

の位置まで移動したいのだから、

So delta x/y is

(x0 - a*u0*W + c*v0*H , y0 - b*u0*W + d*v0*H)

だけ描画結果を移動すればよいことになる。これを実装すると以下のようになる。

function drawTriangle(g, img, vertex_list, uv_list)
{
	var _Ax = vertex_list[2] - vertex_list[0];
	var _Ay = vertex_list[3] - vertex_list[1];
	var _Bx = vertex_list[4] - vertex_list[0];
	var _By = vertex_list[5] - vertex_list[1];

	var Ax = (uv_list[2] - uv_list[0]) * img.width;
	var Ay = (uv_list[3] - uv_list[1]) * img.height;
	var Bx = (uv_list[4] - uv_list[0]) * img.width;
	var By = (uv_list[5] - uv_list[1]) * img.height;

	var m = new M22();
	m._11 = Ax;
	m._12 = Ay;
	m._21 = Bx;
	m._22 = By;
	var mi = m.getInvert();
	if (!mi) return;
	var a, b, c, d;

	a = mi._11 * _Ax + mi._12 * _Bx;
	c = mi._21 * _Ax + mi._22 * _Bx;

	b = mi._11 * _Ay + mi._12 * _By;
	d = mi._21 * _Ay + mi._22 * _By;

	g.save();
	g.transform(a, b, c, d,
		vertex_list[0] - (a * uv_list[0] * img.width + c * uv_list[1] * img.height),
		vertex_list[1] - (b * uv_list[0] * img.width + d * uv_list[1] * img.height));
	g.drawImage(img, 0, 0);
	g.restore();

	// for debugging
	g.strokeStyle = "#f00";
	g.moveTo(vertex_list[0], vertex_list[1]);
	g.lineTo(vertex_list[2], vertex_list[3]);
	g.lineTo(vertex_list[4], vertex_list[5]);
	g.lineTo(vertex_list[0], vertex_list[1]);
	g.stroke();
}

再び、先ほどの呼び出し側のコードを実行すると、Figure 3-5 を得る。

After implementing "move" part, results in Figure 3-5

texture mapping Figure 3-5

UV座標で指定した部分が、ポリゴンの中にすっぽりと収まっている。最後にすべきことは、ポリゴンの外側の余分な部分を切り落とすことである。この操作は clip メソッドで可能である。以下のように clip メソッドを利用し、drawTriangle 関数を完成させる。

The area specified by uv coordinates is inside the polygon. To finish up, clip extra area. clip method is very way to do it. Use clip method like this:

function drawTriangle(g, img, vertex_list, uv_list)
{
	var _Ax = vertex_list[2] - vertex_list[0];
	var _Ay = vertex_list[3] - vertex_list[1];
	var _Bx = vertex_list[4] - vertex_list[0];
	var _By = vertex_list[5] - vertex_list[1];

	var Ax = (uv_list[2] - uv_list[0]) * img.width;
	var Ay = (uv_list[3] - uv_list[1]) * img.height;
	var Bx = (uv_list[4] - uv_list[0]) * img.width;
	var By = (uv_list[5] - uv_list[1]) * img.height;

	var m = new M22();
	m._11 = Ax;
	m._12 = Ay;
	m._21 = Bx;
	m._22 = By;
	var mi = m.getInvert();
	if (!mi) return;
	var a, b, c, d;

	a = mi._11 * _Ax + mi._12 * _Bx;
	c = mi._21 * _Ax + mi._22 * _Bx;

	b = mi._11 * _Ay + mi._12 * _By;
	d = mi._21 * _Ay + mi._22 * _By;

	g.save();
	g.beginPath();
	g.moveTo(vertex_list[0], vertex_list[1]);
	g.lineTo(vertex_list[2], vertex_list[3]);
	g.lineTo(vertex_list[4], vertex_list[5]);
	g.clip();

	g.transform(a, b, c, d,
		vertex_list[0] - (a * uv_list[0] * img.width + c * uv_list[1] * img.height),
		vertex_list[1] - (b * uv_list[0] * img.width + d * uv_list[1] * img.height));
	g.drawImage(img, 0, 0);
	g.restore();
}

clip メソッドを save メソッドの直後に呼んでいることが重要である。save〜restore ペアの外でclip メソッドを呼ぶと、clip メソッドキャンバスに描かれているもの全てを切り取ってしまう。それまでに描かれた他のポリゴンも、これから描こうとするポリゴンも、全て切り取って消してしまう。だから、clip メソッドはこの位置で呼ばれなければいけない。

Call clip method inside save()~restore() pair. This is important. If you call clip method without save/restore, clip method will clip everything on the canvas. save/restore methods limit effect of clip method to one polygon.

これを実行すると Figure 3-6 を得る。

texture mapping Figure 3-6

まさに、テクスチャが貼られたポリゴンが描画されている。三角形を組み合わせ、多角形を描くこともできる。

drawTriangle(g, img, 
[
 100, 100,
 150, 110,
 60, 160
],
[
 0.75, 0,
 1   , 0,
 0.75, 0.25
]
);

drawTriangle(g, img, 
[
 60, 160,
 150, 110,
 110, 170
],
[
 0.75, 0.25,
 1   , 0,
 1   , 0.25
]
);

これを実行するとFigure 3-7 を得る。

texture mapping Figure 3-7

これでテクスチャマッピングのルーチンは用意できた。次節では3次元の座標計算と組み合わせ、3DCGを描画してみる。

3D Rendering

3次元描画のための API が無いのと同様、Javascript には3次元の座標計算のための API は無い。幸い、これらは単なる足し算と掛け算の集合であるから簡単に実装できるし、描画に比べれば実行コストも微々たる物である。というわけで、駆け足でそれらをライブラリ化してしまおう。

まずは3次元ベクトル。

function Vec3(_x, _y, _z)
{
	this.x = _x || 0;
	this.y = _y || 0;
	this.z = _z || 0;
}

Vec3.prototype = {
	zero: function() {
		this.x = this.y = this.z = 0;
	},

	sub: function(v) {
		this.x -= v.x;
		this.y -= v.y;
		this.z -= v.z;

		return this;
	},

	add: function(v) {
		this.x += v.x;
		this.y += v.y;
		this.z += v.z;

		return this;
	},

	copyFrom: function(v) {
		this.x = v.x;
		this.y = v.y;
		this.z = v.z;

		return this;
	},

	norm:function() {
		return Math.sqrt(this.x*this.x + this.y*this.y + this.z*this.z);
	},

	normalize: function() {
		var nrm = Math.sqrt(this.x*this.x + this.y*this.y + this.z*this.z);
		if (nrm != 0)
		{
			this.x /= nrm;
			this.y /= nrm;
			this.z /= nrm;
		}
		return this;
	},

	// scalar multiplication
	smul: function(k) {
		this.x *= k;
		this.y *= k;
		this.z *= k;

		return this;
	},

	// dot product
	dpWith: function(v)	{
		return this.x*v.x + this.y*v.y + this.z*v.z;
	},

	// cross product
	cp: function(v, w) {
		this.x = (w.y * v.z) - (w.z * v.y);
		this.y = (w.z * v.x) - (w.x * v.z);
		this.z = (w.x * v.y) - (w.y * v.x);

		return this;
	},

	toString: function() {
		return this.x + ", " + this.y + "," + this.z;
	}
}

続いて 4x4行列。

function M44(cpy)
{
	if (cpy)
		this.copyFrom(cpy);
	else {
		this.ident();
	}
}

M44.prototype = {
	ident: function() {
			  this._12 = this._13 = this._14 = 0;
		this._21 =       this._23 = this._24 = 0;
		this._31 = this._32 =       this._34 = 0;
		this._41 = this._42 = this._43 =       0;

		this._11 = this._22 = this._33 = this._44 = 1;

		return this;
	},

	copyFrom: function(m) {
		this._11 = m._11;
		this._12 = m._12;
		this._13 = m._13;
		this._14 = m._14;

		this._21 = m._21;
		this._22 = m._22;
		this._23 = m._23;
		this._24 = m._24;

		this._31 = m._31;
		this._32 = m._32;
		this._33 = m._33;
		this._34 = m._34;

		this._41 = m._41;
		this._42 = m._42;
		this._43 = m._43;
		this._44 = m._44;

		return this;
	},

	transVec3: function(out, x, y, z) {
		out[0] = x * this._11 + y * this._21 + z * this._31 + this._41;
		out[1] = x * this._12 + y * this._22 + z * this._32 + this._42;
		out[2] = x * this._13 + y * this._23 + z * this._33 + this._43;
		out[3] = x * this._14 + y * this._24 + z * this._34 + this._44;
	},

	perspectiveLH: function(vw, vh, z_near, z_far) {
		this._11 = 2.0*z_near/vw;
		this._12 = 0;
		this._13 = 0;
		this._14 = 0;

		this._21 = 0;
		this._22 = 2*z_near/vh;
		this._23 = 0;
		this._24 = 0;

		this._31 = 0;
		this._32 = 0;
		this._33 = z_far/(z_far-z_near);
		this._34 = 1;

		this._41 = 0;
		this._42 = 0;
		this._43 = z_near*z_far/(z_near-z_far);
		this._44 = 0;

		return this;
	},

	// multiplication
	mul: function(A, B) {
		this._11 = A._11*B._11  +  A._12*B._21  +  A._13*B._31  +  A._14*B._41;
		this._12 = A._11*B._12  +  A._12*B._22  +  A._13*B._32  +  A._14*B._42;
		this._13 = A._11*B._13  +  A._12*B._23  +  A._13*B._33  +  A._14*B._43;
		this._14 = A._11*B._14  +  A._12*B._24  +  A._13*B._34  +  A._14*B._44;

		this._21 = A._21*B._11  +  A._22*B._21  +  A._23*B._31  +  A._24*B._41;
		this._22 = A._21*B._12  +  A._22*B._22  +  A._23*B._32  +  A._24*B._42;
		this._23 = A._21*B._13  +  A._22*B._23  +  A._23*B._33  +  A._24*B._43;
		this._24 = A._21*B._14  +  A._22*B._24  +  A._23*B._34  +  A._24*B._44;

		this._31 = A._31*B._11  +  A._32*B._21  +  A._33*B._31  +  A._34*B._41;
		this._32 = A._31*B._12  +  A._32*B._22  +  A._33*B._32  +  A._34*B._42;
		this._33 = A._31*B._13  +  A._32*B._23  +  A._33*B._33  +  A._34*B._43;
		this._34 = A._31*B._14  +  A._32*B._24  +  A._33*B._34  +  A._34*B._44;

		this._41 = A._41*B._11  +  A._42*B._21  +  A._43*B._31  +  A._44*B._41;
		this._42 = A._41*B._12  +  A._42*B._22  +  A._43*B._32  +  A._44*B._42;
		this._43 = A._41*B._13  +  A._42*B._23  +  A._43*B._33  +  A._44*B._43;
		this._44 = A._41*B._14  +  A._42*B._24  +  A._43*B._34  +  A._44*B._44;

		return this;
	},

	translate: function(x, y, z) {
		this._11 = 1;  this._12 = 0;  this._13 = 0;  this._14 = 0;
		this._21 = 0;  this._22 = 1;  this._23 = 0;  this._24 = 0;
		this._31 = 0;  this._32 = 0;  this._33 = 1;  this._34 = 0;

		this._41 = x;  this._42 = y;  this._43 = z;  this._44 = 1;
		return this;
	},

	rotX: function(r) {
		this._22 = Math.cos(r);
		this._23 = Math.sin(r);
		this._32 = -this._23;
		this._33 = this._22;

		this._12=this._13=this._14 = this._21=this._24 = this._31=this._34 = this._41=this._42=this._43 = 0;
		this._11 = this._44 = 1;			

		return this;
	},

	rotY: function(r) {
		this._11 = Math.cos(r);
		this._13 = -Math.sin(r);
		this._31 = -this._13;
		this._33 = this._11;

		this._12=this._14 = this._21=this._23=this._24 = this._32=this._34 = this._41=this._42=this._43 = 0;
		this._22 = this._44 = 1;

		return this;
	}
}

4x4行列クラスには、サンプルに必要な最低限のメソッドを含めた。'lookAt'ビュー変換を生成したり、逆行列を求めたりといった機能は意図的に削られている。

早速、3次元のシーンを描画してみる。

	var textureImage;
	function start()
	{
		var img = new Image();
		img.onload = function() {
			textureImage = img;
			renderScene();
		}

		img.src = "boxtex.png";
	}

	function renderScene()
	{
		var roof_1 = [
			-4,  4,  4,
			 4,  4,  4,
			-4,  4, -4
		];

		var roof_2 = [
			-4,  4, -4,
			 4,  4,  4,
			 4,  4, -4
		];

		var wall_1 = [
			-4,  4, -4,
			 4,  4, -4,
			-4, -4, -4
		];

		var wall_2 = [
			-4, -4, -4,
			 4,  4, -4,
			 4, -4, -4
		];

		var wall_3 = [
			-4,  4,  4,
			-4,  4, -4,
			-4, -4,  4
		];

		var wall_4 = [
			-4, -4,  4,
			-4,  4, -4,
			-4, -4, -4
		];


		var wall_5 = [
			 4,  4, -4,
			 4,  4,  4,
			 4, -4, -4
		];

		var wall_6 = [
			 4, -4, -4,
			 4,  4,  4,
			 4, -4,  4
		];


		var wall_7 = [
			 4,  4, 4,
			-4,  4, 4,
			 4, -4, 4
		];

		var wall_8 = [
			 4, -4, 4,
			-4,  4, 4,
			-4, -4, 4
		];


		var matProj  = (new M44()).perspectiveLH(4, 3, 1, 100);
		var matView  = (new M44()).translate(0, 0, 19);
		var matWorld = (new M44()).rotX(-0.7);

		var tmp = (new M44()).mul(matWorld, matView);
		var matAll = (new M44()).mul(tmp, matProj);

		var g = document.getElementById("canvas").getContext("2d");

		transformAndDraw(g, matAll, roof_1, [
			 0  , 0  ,
			 0.5, 0  ,
			 0  , 0.5
		] );

		transformAndDraw(g, matAll, roof_2, [
			 0  , 0.5,
			 0.5, 0  ,
			 0.5, 0.5
		] );


		transformAndDraw(g, matAll, wall_1, [
			 0  , 0.5,
			 0.5, 0.5,
			 0  , 1
		] );

		transformAndDraw(g, matAll, wall_2, [
			 0  , 1,
			 0.5, 0.5,
			 0.5, 1
		] );


		transformAndDraw(g, matAll, wall_3, [
			 0.5, 0,
			 1  , 0,
			 0.5, 0.5
		] );

		transformAndDraw(g, matAll, wall_4, [
			 0.5, 0.5,
			 1  , 0,
			 1  , 0.5
		] );


		transformAndDraw(g, matAll, wall_5, [
			 0.5, 0,
			 1  , 0,
			 0.5, 0.5
		] );

		transformAndDraw(g, matAll, wall_6, [
			 0.5, 0.5,
			 1  , 0,
			 1  , 0.5
		] );


		transformAndDraw(g, matAll, wall_7, [
			 0  , 0.5,
			 0.5, 0.5,
			 0  , 1
		] );

		transformAndDraw(g, matAll, wall_8, [
			 0  , 1,
			 0.5, 0.5,
			 0.5, 1
		] );
	}

	function transformAndDraw(g, mat, vertex_list, uv_list)
	{
		var view_width  = 400;
		var view_height = 300;

		var out_list = new Array(6);
		transformPoints(out_list, vertex_list, mat, view_width, view_height);
		drawTriangle(g, textureImage, out_list, uv_list);
	}

	function transformPoints(out, pts, mat, viewWidth, viewHeight)
	{
		var len = pts.length/3;
		var transformed_temp = [0,0,0,0];
		var oi = 0;

		for (var i = 0;i < len;i++) {
			mat.transVec3(transformed_temp, pts[i*3], pts[i*3 + 1], pts[i*3 + 2]);

			var W = transformed_temp[3];
			transformed_temp[0] /= W;
			transformed_temp[1] /= W;
			transformed_temp[2] /= W;

			transformed_temp[0] *= viewWidth;
			transformed_temp[1] *= -viewHeight;
			transformed_temp[0] += viewWidth/2;
			transformed_temp[1] += viewHeight/2;

			out[oi++] = transformed_temp[0];
			out[oi++] = transformed_temp[1];
		}
	}

start 関数はドキュメントの onload ハンドラなので、そこから読み始めてほしい。start 関数 の中で画像を非同期に読み込み、読み込み完了後に renderScene 関数が呼ばれる。renderScene 関数が実質的なメインルーチンである。このプログラムの実行結果を Figure 4-1 に示す。

texture mapping Figure 4-1

各頂点の位置は正しいし、テクスチャは正確に貼られているが、明らかにおかしい。隠れているはずの面が見えていて、見えているはずの面が隠されている。単純に全ての面を描画するのではなく、見えてはいけない部分を隠す処理を実装する必要がある。この処理を陰面消去と言う。

陰面消去の方法にはいくつがあるが、ここでは最も単純な裏面カリングと呼ばれる手法を使う。裏面カリングとは、視点に対して背を向けているポリゴンの描画をスキップする処理である。ポリゴンが表を向いているか裏を向いているかの判定方法は非常に単純である。ポリゴンの頂点を全て時計回りに指定するというルールの下では、裏を向いているポリゴン(の頂点の順)は、反時計回りに見える。そこで、drawTriangle 関数に次の2行を足す。

	if( ((_Ax * (vertex_list[5]-vertex_list[3])) - (_Ay * (vertex_list[4]-vertex_list[2]))) < 0)
		return;

ベクトルの外積を利用して反時計回りのポリゴンを見分け、処理を中断している。これを実装すると、Figure 4-1 の結果が Figure 4-2のように変わる。

texture mapping Figure 4-2

横や裏側の面は描画されず、正しい結果が得られた。ただし、裏面カリングのみで正しい結果が得られるのは、このような非常に単純なシーンに限った話である。現実的には、Zソート法(ペインターズアルゴリズム)を併用することになる。

最後に、アニメーションを追加してこのデモを完成させよう。ソースと結果は以下のURLを開いて確認してほしい。Javascriptのコードもすべて埋め込まれている。

http://gyu.que.jp/jscloth/article/cube.html

ところで、テクスチャが歪んでいることに気づいたかもしれない。よく見ると、三角形の継ぎ目のところで折れ曲がったように歪んでいる。これは、アフィン変換のみでテクスチャマッピングを実装していることが原因である。例えば、3次元空間内の正方形の面を投影した結果、台形になったとする。台形を表現するには3本のベクトル(例えば、上底と左辺と右辺)が必要だが、我々のアルゴリズムは変形に2本のベクトルしか使っていない。そもそも情報が足りていないので、この歪みは避けられない。モデルのデザイナは、この歪みが目立たないよう、巨大なポリゴンを分割するなどの工夫をすべきである。

本格的な3Dシステムでは、各頂点が持っている奥行きの情報を利用し、歪みを補正することができる。この機能はパースペクティブコレクトと呼ばれている。Direct3D は、現在のバージョンではデフォルトでパースペクティブコレクトが行われる。また、Flash Player もVersion 10からパースペクティブコレクトが利用可能になった。(If the length of this vector is three times the length of the vertices vector then the third coordinate is interpreted as 't' (the distance from the eye to the texture in eye space). This helps the rendering engine correctly apply perspective when mapping textures in three dimensions. )

Benchmark

(書きかけ)

座標計算とレンダリングの処理について、それぞれベンチマークをとるために、20x20 のメッシュをレンダリングする(Figure 5-1)。このテストでは、drawTriangle 関数の代わりに、複数のポリゴンを連続して描画する drawTriangles 関数を実装し、関数呼び出しのオーバーヘッドの影響を減らしている。

benchmark screenshot Figure 5-1

これを Mozilla Firefox 3.0、Mozilla Firefox 3.1 beta2(JIT有効)、Google Chrome で実行した結果を Table 5-1 に示す(50フレームの平均)

Table 5-1 benchmark result on MacBook Late 2008 2.0GHz, Windows Vista
browsercalculation (ms)rendering (ms)
Firefox 3.09.284415.74
Firefox 3.1b22.178398.1
Google Chrome2.5923.5

純粋な計算の処理に関して言えば、Firefox 3.1 の JIT の効果は確かなもので、V8 にも引けをとらない。しかし、描画処理では大きく水を開けられていて、これが Firefox と Google Chrome の体感速度の差になっている。

(書きかけ。 Skia と cairo のパフォーマンス対決とか書く)

先のデモを見た人が必ず抱く感想のひとつは、Google Chrome が異様に速いということである。同じスクリプトを実行しているとは思えないほど Google Chrome は速い。Google Chrome の速さの源としてよく知られているのは、V8 Javascript エンジンである。V8 は、Spider MonkeyJavascript Core に先駆けて JIT を実装した Javascript エンジンで、“重い”Javascript アプリケーションの代表格である GMail の体感速度を格段に向上させて見せ、ユーザを唸らせた。

一方で Skia の知名度はやや低い。Skia とは、ベクタグラフィックスを描画するためのライブラリである。Gecko や WebKit など、一般に「HTMLレンダリングエンジン」と呼ばれているものの実態は「レイアウトエンジン」であり、HTML と CSS を解釈して、何をどの位置にどれくらいの大きさで描くのか、という決定を下すことが主な仕事である。その後、実際に線を引いたり、塗りつぶしたり、といった作業は、別のライブラリに分離されているのがモダンなブラウザの設計である。

Gecko の場合、これは cairo というライブラリが担当している。Apple オリジナルの WebKit の場合、Mac OS X ネイティブの API である CoreGraphics か、Gecko と同じ cairo を選択できた。だが Google はこれに満足せず、Skia を会社ごと買収し、第3のバックエンドに据えた。

この Skia がどれくらい速いか測るために、C++ のプログラムから直接呼び出してベンチマークをとってみた。比較のために、cairo も同じプログラムにリンクし、同じ処理を行って計測した。

1つめのベンチマークは、128x128 ピクセルのビットマップを描画する処理である。計測対象はシステムメモリ上に確保した領域への描画で、出力結果を確認するために実画面に転送する処理は計測対象外である。Figure 5-2 はその出力である。

skia vs cairo 1 Figure 5-2

skia vs cairo 1 result

skia vs cairo 2

skia vs cairo 2 result

Performance Tuning

(書きかけ。canvas を使うときの工夫)

Firefox が遅いことはわかったが、少しでも速くする方法はないだろうか。Firefox の canvas でいくつかプログラムを書いていると、drawImage メソッドは大きな画像を扱うと極端に遅くなる、ということに気づく。そこで、テクスチャを複数の小さな画像に分割してみよう。

Table 6-1 benchmark2 result on MacBook Late 2008 2.0GHz, Windows Vista
texture typecalculation (ms)rendering (ms)
one 256x256 texture9.284415.74
two 256x128 textures8.756299.6

これは確かに効果がある。Direct3D や OpenGL では、複数のテクスチャを切り替える操作のコストが高いので、なるべく一枚に詰め込むのが定石だが、Firefox の canvas を使うときは、そういうことはしない方がいい、ということになる。

もう一つアイデアがある。drawImage メソッドは、最も引数が少ない形式(引数が3つ)で呼び出すと、画像全体の描画を意味する。今まではこれを使っていた。ところが、引数が9つの形式で呼び出すことで、画像の一部を描画する指示を出すことができる。画像全体を描画してクリッピングで切り落とすのは無駄なので、クリッピング領域の内側だけを drawImage メソッドで描画するのはどうか、というアイデアである。

Table 6-2 benchmark3 result on MacBook Late 2008 2.0GHz, Windows Vista
texture typecalculation (ms)rendering (ms)
entire image9.284415.74
sub-image8.526437.58

見てのとおり、まったく効果が無い。この理由は、Firefox のソースを見るとすぐにわかる。Firefox の場合、引数が9個の drawImage の実装は引数が3個のときと同じで、途中でクリッピングを入れているだけである。だから、このトリックは意味が無い。

ところが、Safari でベンチマークをとってみると面白いことになる。

Table 6-3 benchmark3 result on MacBook Late 2008 2.0GHz, Safari 3.2.1, Windows Vista
texture typecalculation (ms)rendering (ms)
entire image8.724417.04
sub-image8.9287.68

圧倒的に速くなっていることがわかる。Safari では、drawImage メソッドに指定する領域を狭くすると、実際に描画の無駄を省ける。これは Mac OS X 版でも、iPhone OS 版でも通用する。

しかし、Google Chrome でベンチマークをとると、また結果が変わる。

Table 6-4 benchmark3 result on MacBook Late 2008 2.0GHz, Google Chrome 1.0.154.48, Windows Vista
texture typecalculation (ms)rendering (ms)
entire image2.5923.5
sub-image2.81456.8

今度は遅くなってしまった。同じ WebKit だからといって油断してはいけない。

そろそろ頭が痛くなってきたので、メジャーなブラウザでの結果をまとめておく(IE?何それ)

Table 6-5 benchmark1,2,3 results on MacBook Late 2008 2.0GHz, Windows Vista
Optimization
Browser-NoDivide Texturepartial drawImage()
Firefox 3.0415.74299.6437.58
Safari417.04381.287.68
Opera516.1295.2425
Chrome23.52256.8

言えることは2つ。まず、テクスチャを作るときは、大きな画像に詰め込むのではなく、複数の小さな画像に分けておくといい。次に、drawImage メソッドに9つのパラメータを指定して、貼り付け元画像の領域を限定する ― ただし、Chrome を除く。

一つ目の点はモデルデータを作るときにすべきことで、2つ目は実行時にブラウザを判定して分岐するといい(Chromeを判断する方法はUA文字列ぐらいしかない?)

 |