ゲームとアフィン(Afin)変換

平野拓一

概要（ゲームとアフィン変換）

最近のゲーム機（プレイステーション、ゲームキューブ、X-Box など）ではキャラクターが多角形の集合（ポリゴン）で表現されている。多角形は普通簡単のために三角形で表現される。ゲームでコントローラを操作してキャラクターを移動させる場合を考えると、まずポリゴンの座標を計算し直す（この作業を座標変換と言う）。その後、その三次元の座標をテレビのスクリーンに合うように二次元の座標に変換して（投影と言う。これも後で説明するように座標変換の一部としてとらえることができる）、その二次元の座標データをもとに色を塗ったりして画面に絵を描く（レンダリングと言う）。
このような作業が高速で瞬時に行われているために、滑らかに綺麗な映像が動いてゲームができるのである。細かく言うと、普通1/60秒毎に画面を描き変えてパラパラ漫画のようにアニメーションを見せているのである。アニメーションの一つの画面を「フレーム」と言い、一秒間に60回画面を描き変える場合、「秒間60フレーム」と言う。ゲーム機の心臓部のコンピュータであるCPUは画面描画の処理だけを行えば良いという訳ではなく、本来の目的であるゲームの進行状況の処理をする必要もあり、昔の遅いCPUでは画面を描く処理が間に合わなくなることもあった。例えばファミコンのグラディウス（コナミ）で敵や弾がいっぱい出現したときにはものすごく動きがスローになる場合があったが、それは本来のゲームの進行処理（弾が当たったかどうかなど）が間に合わないから画面の更新を例えば1/60秒から1/30秒に一時的に落とすような処理をしているからである（ただし、ファミコンの時代にはポリゴンなど使わず、キャラクターを単にドットの集合で描いていただけである）。テレビ(CRT)が画面を更新するスピードが決まっているから（電子銃をスイープしているから）、少しゲーム自体の処理が遅れたからといって、少しだけ画面の更新を遅らせるということが出来ないからである。つまり、処理が少し遅れたとしても画面の更新速度は整数分の1にするしかない。
実際には映像信号を出力するビデオチップは画面の横方向に電子を走査し終わったことを伝える水平同期割込み(HSYNC)と縦方向に一画面分電子を走査し終わったことを伝える垂直同期割込み(VSYNC)をCPUに対して出しており、VSYNC割込みに合わせて画面を描き変えるようにしている(余談だが、HSYNC割り込みを利用して画面を横方向にグニャグニャとうねらせるラスタースクロールというテクニックもある)。最近のゲーム機では座標変換とレンダリングを行う特別な専用チップがあって、CPUは座標だけその回路に渡して後は自分の仕事に専念できるようになっている。

余談であるが、レンダリングの内容について説明すると、ポリゴンの二次元データを元に画面（正確にはVRAM, ビデオRAM）に描いていく訳だが、画面からはみ出るポリゴンは描かないようにしたり、画面の端をまたぐポリゴンは画面内に残る部分だけを描画する。この作業をクリッピング(Clipping)と言う。奥にあるポリゴンが手前のポリゴンに隠れるような処理をするのによくZバッファ法が用いられる。これらの作業も現在では専用回路が自動的に行うようになっている。
次に色付けについて説明する。ポリゴンの面の法線ベクトルを使ってポリゴン内を同一色で塗ると、キャラクターがカクカクに見えてしまう（セガサターンのゲームでよく見られた）。そこで、ポリゴンに色を塗るときになるべく滑らかに見えるように工夫されている。まず、グローシェーディングと呼ばれる方法について説明する。最初にあるポリゴンについて隣接するポリゴンの平均の法線ベクトルを使って頂点の位置での法線ベクトルを求め、その法線ベクトルを使って色を決める。次に、それらの頂点の色をポリゴンの面内に内挿すると見違えるほど滑らかに見えるのである。プレイステーションではグローシェーディングがハードウェアで用意されていた。なお、セガサターンではグローシェーディングがハードウェアで用意されていなかったため、プレイステーションにくらべてキャラクターがガタガタだったのである。より高度なものでは頂点の法線ベクトルの平均値を面内に内挿してスムーズに色づけするフォーンシェーディングがある。
なお、法線ベクトルからその点の色を決める方法にも、単純に光線がそこに到来する角度との内積を取る方法と、物体毎に光の吸収率を定義して、光の物体による多重反射も考慮する方法などがある。後者の色付け方法はレイトレーシング(Ray Tracing)と言われ、「ジュラシックパーク」、「アポロ13」などの映画でも使われている方法で、驚く程リアルな映像を作り出す。残念ながら、リアルタイム処理が要求されるゲーム機ではまだレイトレーシングが使われていないが、将来実用化されていくことは間違いない。また、レイトレーシングよりもよりリアルな映像を作り出す方法もいくつかあるが、より多くの計算時間がかかるため、現在では映画製作などにレイトレーシングが多く使われている。

座標変換

さて、前置きが長くなったがゲームで画面を描く作業をまとめると
(1) 座標変換
(2) レンダリング
が高速に繰り返されている。本稿では、(1) の座標変換で使われているアフィン変換について説明する。

まず、高校の数学（代数・幾何）では行列で座標変換を行う次のような一次変換を習った。点P=(({{x}, {y}, {z}}))を点P'=(({{x'}, {y'}, {z'}}))に移す場合、変換行列A=(({{(Subscript[a, 11]), (Subscript[a, 12]), (Subscript[a, 13])}, {(Subscript[a, 21]), (Subscript[a, 22]), (Subscript[a, 23])}, {(Subscript[a, 31]), (Subscript[a, 32]), (Subscript[a, 33])}}))を用いて
(({{x'}, {y'}, {z'}}))=(({{(Subscript[a, 11]), (Subscript[a, 12]), (Subscript[a, 13])}, {(Subscript[a, 21]), (Subscript[a, 22]), (Subscript[a, 23])}, {(Subscript[a, 31]), (Subscript[a, 32]), (Subscript[a, 33])}}))(({{x}, {y}, {z}})) ⇔ P' = A P         (1)
と表される。
この行列Aは「拡大・縮小 (scaling)」、「回転(rotation)」の合成となっている。
なぜならば、
(({{(Subscript[a, 11])}, {(Subscript[a, 21])}, {(Subscript[a, 31])}}))=(({{(Subscript[a, 11]), (Subscript[a, 12]), (Subscript[a, 13])}, {(Subscript[a, 21]), (Subscript[a, 22]), (Subscript[a, 23])}, {(Subscript[a, 31]), (Subscript[a, 32]), (Subscript[a, 33])}}))(({{1}, {0}, {0}}))
(({{(Subscript[a, 12])}, {(Subscript[a, 22])}, {(Subscript[a, 32])}}))=(({{(Subscript[a, 11]), (Subscript[a, 12]), (Subscript[a, 13])}, {(Subscript[a, 21]), (Subscript[a, 22]), (Subscript[a, 23])}, {(Subscript[a, 31]), (Subscript[a, 32]), (Subscript[a, 33])}}))(({{0}, {1}, {0}}))
(({{(Subscript[a, 13])}, {(Subscript[a, 23])}, {(Subscript[a, 33])}}))=(({{(Subscript[a, 11]), (Subscript[a, 12]), (Subscript[a, 13])}, {(Subscript[a, 21]), (Subscript[a, 22]), (Subscript[a, 23])}, {(Subscript[a, 31]), (Subscript[a, 32]), (Subscript[a, 33])}}))(({{0}, {0}, {1}}))
となり、各基底(({{1}, {0}, {0}})),(({{0}, {1}, {0}})),(({{0}, {0}, {1}}))は(({{(Subscript[a, 11])}, {(Subscript[a, 21])}, {(Subscript[a, 31])}})),(({{(Subscript[a, 12])}, {(Subscript[a, 22])}, {(Subscript[a, 32])}})),(({{(Subscript[a, 13])}, {(Subscript[a, 23])}, {(Subscript[a, 33])}}))にそれぞれ変換される。別の言い方をすると、
(({{x'}, {y'}, {z'}}))=(({{(Subscript[a, 11]), (Subscript[a, 12]), (Subscript[a, 13])}, {(Subscript[a, 21]), (Subscript[a, 22]), (Subscript[a, 23])}, {(Subscript[a, 31]), (Subscript[a, 32]), (Subscript[a, 33])}}))(({{x}, {y}, {z}}))=x(({{(Subscript[a, 11])}, {(Subscript[a, 21])}, {(Subscript[a, 31])}}))+y(({{(Subscript[a, 12])}, {(Subscript[a, 22])}, {(Subscript[a, 32])}}))+z(({{(Subscript[a, 13])}, {(Subscript[a, 23])}, {(Subscript[a, 33])}}))
となり、基底(({{1}, {0}, {0}})),(({{0}, {1}, {0}})),(({{0}, {0}, {1}}))で張られる空間は基底(({{(Subscript[a, 11])}, {(Subscript[a, 21])}, {(Subscript[a, 31])}})),(({{(Subscript[a, 12])}, {(Subscript[a, 22])}, {(Subscript[a, 32])}})),(({{(Subscript[a, 13])}, {(Subscript[a, 23])}, {(Subscript[a, 33])}}))で張られる空間に移り、下の図のイメージのようになる。

上のイメージを見てもわかるが、この変換では
x' = 2  x + 3,  y' = y + 1,  z' = 3  z + 2
のようなT=(({{3}, {1}, {2}}))の平行移動は行列で表すことができず、
P' = A P + T         (2)
というようにベクトルの足し算を行うしかない。これでもいいが、ゲームでは１つのフレームを作るために多くの頂点を同じように変換する必要がある。そのとき、同じ行列をベクトルに掛けるだけで処理できた方がより高速になるし、計算も簡単になる。
そこで、アフィン変換では平行移動も行列の掛け算として扱えるように（Aに含めることができるように）工夫されている。

アフィン変換

平行移動も行列で扱い、行列の積の結合規則（a*(b*c) = (a*b)*c, 演算の順番を変更できる性質）が適用できるようにするために次元を１つ増やす。行列の結合規則が使えるということは計算量を減らし、演算を高速化するために非常に重要である。

行列の結合規則の重要性を説明するために、ポリゴンの頂点をP（ベクトル）とし、それを座標変換（ベクトルに対する行列の掛け算で表現される）することを考える。例えば、まず原点に対してx軸回りの回転((Subscript[R, x]))をして、原点に対して拡大する(S)ことを考える。頂点Pをこのように座標変換してP'に移ったとすると、
P' = S ((Subscript[R, x]) P)
と書ける。上の右辺の計算は行列の結合規則より、
P' = (S (Subscript[R, x])) P
と書くこともできる。このように、行列の結合規則を使うと先に変換行列だけを計算して一つにまとめておいて、後で同じ行列を全頂点にかけるだけで良いことになり、計算量を減らして高速化することができる上に式が綺麗で見通しが良い。
しかし、残念ながら式(1)で定義される一次変換では平行移動を頂点への行列の掛け算で表現することができない。そこで、次のように座標の最後に1を入れたダミー座標を考えた行列を考える。変換後に座標を読みとるときは左辺ベクトル最後の"1"のダミー座標を無視する。
(({{x'}, {y'}, {z'}, {1}}))=(({{(Subscript[a, 11]), (Subscript[a, 12]), (Subscript[a, 13]), (Subscript[a, 14])}, {(Subscript[a, 21]), (Subscript[a, 22]), (Subscript[a, 23]), (Subscript[a, 24])}, {(Subscript[a, 31]), (Subscript[a, 32]), (Subscript[a, 33]), (Subscript[a, 34])}, {0, 0, 0, 1}}))(({{x}, {y}, {z}, {1}}))        (3)
このように定義すると、
x'=(Subscript[a, 11]) x+(Subscript[a, 12]) y+(Subscript[a, 13]) z+(Subscript[a, 14])
y'=(Subscript[a, 21]) x+(Subscript[a, 22]) y+(Subscript[a, 23]) z+(Subscript[a, 24])
z'=(Subscript[a, 31]) x+(Subscript[a, 32]) y+(Subscript[a, 33]) z+(Subscript[a, 34])
となり、平行移動も行列の掛け算で表現出来ている。式(3)の変換をアフィン変換（一般には線形変換と平行移動の合成を表し、４次元の行列表現を表す訳ではない）と言う。
また、後述するが式(3)でついでに投影処理をすることもできる。透視投影変換をするように拡張した場合は、
(({{x'}, {y'}, {z'}, {w'}}))=(({{(Subscript[a, 11]), (Subscript[a, 12]), (Subscript[a, 13]), (Subscript[a, 14])}, {(Subscript[a, 21]), (Subscript[a, 22]), (Subscript[a, 23]), (Subscript[a, 24])}, {(Subscript[a, 31]), (Subscript[a, 32]), (Subscript[a, 33]), (Subscript[a, 34])}, {(Subscript[a, 41]), (Subscript[a, 42]), (Subscript[a, 43]), (Subscript[a, 44])}}))(({{x}, {y}, {z}, {1}}))        (4)
として、最後に(x', y', z')をw'で割っておく。詳しくは透視投影変換の節で述べる。

各種座標変換

回転

x軸回りの回転
(Subscript[R, x])(θ)=(({{1, 0, 0, 0}, {0, cosθ, -sinθ, 0}, {0, sinθ, cosθ, 0}, {0, 0, 0, 1}}))
y軸回りの回転
(Subscript[R, y])(θ)=(({{cosθ, 0, sinθ, 0}, {0, 1, 0, 0}, {-sinθ, 0, cosθ, 0}, {0, 0, 0, 1}}))
z軸回りの回転
(Subscript[R, z])(θ)=(({{cosθ, -sinθ, 0, 0}, {sinθ, cosθ, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}))

平行移動とこれらの回転を組み合わせれば任意の点の回りの回転が可能である。実際には平行移動と２つの異なる軸の回りの回転だけで任意の回転が可能である。

拡大・縮小

S((Subscript[s, x]), (Subscript[s, y]), (Subscript[s, z]))=(({{(Subscript[s, x]), 0, 0, 0}, {0, (Subscript[s, y]), 0, 0}, {0, 0, (Subscript[s, z]), 0}, {0, 0, 0, 1}}))

原点を中心としてx,y,z軸方向にそれぞれ(Subscript[s, x]), (Subscript[s, y]), (Subscript[s, z])だけ伸縮する。これも平行移動と組み合わせると任意の点を中心とする拡大・縮小が可能である。

平行移動

T((Subscript[t, x]), (Subscript[t, y]), (Subscript[t, z]))=(({{1, 0, 0, (Subscript[t, x])}, {0, 1, 0, (Subscript[t, y])}, {0, 0, 1, (Subscript[t, z])}, {0, 0, 0, 1}}))

透視投影変換について

式(3)のアフィン変換を使うと、投影変換も同時に出来るようになる。
(Subscript[𝕩, c])を光の収束点とし、(Subscript[𝕩, i])を物体上の頂点とすると、(Subscript[𝕩, c]), (Subscript[𝕩, i])を結ぶ直線上の点𝕩はtをパラメータとして次の方程式を満たす。（直線の方程式）
\(TraditionalForm\`𝕩 = 𝕩\_c + \((𝕩\_i - 𝕩\_c)\) t\)
(({{x}, {y}, {z}}))=(({{(Subscript[x, c])}, {(Subscript[y, c])}, {(Subscript[z, c])}}))+(({{(Subscript[x, i]) - (Subscript[x, c])}, {(Subscript[y, i]) - (Subscript[y, c])}, {(Subscript[z, i]) - (Subscript[z, c])}}))t
z = 0(x - y plane)に投影すると、
t = -((Subscript[z, c])/((Subscript[z, i]) - (Subscript[z, c])))
\(TraditionalForm\`x = \(x\_c - \(z\_c\) x\_i - 
            x\_c\/\(z\_i - z\_c\) = \(\(x\_c\) z\_i - \(x\_i\) z\_c\)\/\(z\_i - z\_c\)\)\)
\(TraditionalForm\`y = \(y\_c - \(z\_c\) y\_i - 
            y\_c\/\(z\_i - z\_c\) = \(\(y\_c\) z\_i - \(y\_i\) z\_c\)\/\(z\_i - z\_c\)\)\)
よって、(Subscript[𝕩, i])を𝕩に変換する透視投影変換行列は次のようになる。
(({{-(Subscript[z, c]), 0, (Subscript[x, c]), 0}, {0, -(Subscript[z, c]), (Subscript[y, c]), 0}, {0, 0, 0, 0}, {0, 0, 1, -(Subscript[z, c])}}))        (5)

座標変換した後式(5)の行列を掛け、式(4)の\(TraditionalForm\`\(w\^'\)\)でx', y'を割っておけば透視投影した座標になる。

例 座標変換

Module[{},
	  
	Rx[θ_]:=(({{1, 0, 0, 0}, {0, Cos[θ], -Sin[θ], 0}, {0, Sin[θ], Cos[θ], 0}, {0, 0, 0, 1}}));    
	Ry[θ_]:=(({{Cos[θ], 0, Sin[θ], 0}, {0, 1, 0, 0}, {-Sin[θ], 0, Cos[θ], 0}, {0, 0, 0, 1}}));    
	Rz[θ_]:=(({{Cos[θ], -Sin[θ], 0, 0}, {Sin[θ], Cos[θ], 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}));    
	S[sx_, sy_, sz_]:=(({{sx, 0, 0, 0}, {0, sy, 0, 0}, {0, 0, sz, 0}, {0, 0, 0, 1}}));    
	T[tx_, ty_, tz_]:=(({{1, 0, 0, tx}, {0, 1, 0, ty}, {0, 0, 1, tz}, {0, 0, 0, 1}}));    
	  
	p = Table[0, {i, 16}];  \( (*\ インスタンス生成\ *) \)
	  
	p[[1]] = {1, -1, -1};    
	p[[2]] = {1, 1, -1};
	p[[3]] = {-1, 1, -1};
	p[[4]] = {-1, -1, -1};

	p[[5]] = {1, -1, 1};    
	p[[6]] = {1, 1, 1};
	p[[7]] = {-1, 1, 1};
	p[[8]] = {-1, -1, 1};
	  
	p[[9]] = {1/2, -1/2, 1};    
	p[[10]] = {1/2, 1/2, 1};
	p[[11]] = {-1/2, 1/2, 1};
	p[[12]] = {-1/2, -1/2, 1};

	p[[13]] = {1/2, -1/2, 2};    
	p[[14]] = {1/2, 1/2, 2};
	p[[15]] = {-1/2, 1/2, 2};
	p[[16]] = {-1/2, -1/2, 2};
	  
	  
	sur[1] := {p[[1]], p[[2]], p[[6]], 
              p[[5]]};
	sur[2] := {p[[2]], p[[3]], p[[7]], 
              p[[6]]};
	sur[3] := {p[[3]], p[[4]], p[[8]], 
              p[[7]]};
	sur[4] := {p[[4]], p[[1]], p[[5]], 
              p[[8]]};
	sur[5] := {p[[4]], p[[3]], p[[2]], 
              p[[1]]};
	sur[6] := {p[[5]], p[[6]], p[[7]], 
              p[[8]]};
	  
	sur[7] := {p[[9]], p[[10]], p[[14]], 
              p[[13]]};
	sur[8] := {p[[10]], p[[11]], p[[15]], 
              p[[14]]};
	sur[9] := {p[[11]], p[[12]], p[[16]], 
              p[[15]]};
	sur[10] := {p[[12]], p[[9]], p[[13]], 
              p[[16]]};
	sur[11] := {p[[12]], p[[11]], p[[10]], 
              p[[9]]};
	sur[12] := {p[[13]], p[[14]], p[[15]], 
              p[[16]]};
	  
	poly := Table[Polygon[sur[i]], {i, 1, 12}];
	  
	Show[ Graphics3D[ poly ], 
            PlotRange -> {{-3, 3}, {-3, 3}, {-4, 4}}, 
            Boxed -> True, Axes -> True , 
            ViewPoint -> {1.300,  -2.400,  2.000}];
	  
	transm = 
            T[0, 0, 1] . Rz[45  °] . Rx[45  °] . S[1, 2, 1];    
	(* (({{x}, {y}, {z}, {1}})) を行列で変換する *)
	\(Do[
		\(p[\([i]\)] = 
                Drop[\ transm . 
                    Append[p[\([i]\)], 1], \ \(-1\)];\)
		, {i, 1, 
              Length[p]}
	]\);
	  
	Show[ Graphics3D[ poly ], 
            PlotRange -> {{-3, 3}, {-3, 3}, {-4, 4}}, 
            Boxed -> True, Axes -> True , 
            ViewPoint -> {1.300,  -2.400,  2.000}];
]

例 透視投影変換

Module[{w, p2},
  
P[xc_, yc_, zc_]:=(({{-zc, 0, xc, 0}, {0, -zc, yc, 0}, {0, 0, 0, 0}, {0, 0, 1, -zc}}));    
  
p = Table[0, {i, 8}];  \( (*\ インスタンス生成\ *) \)
  
p[[1]] = {1, -1, -1};    
p[[2]] = {1, 1, -1};
p[[3]] = {-1, 1, -1};
p[[4]] = {-1, -1, -1};

p[[5]] = {1, -1, 1};    
p[[6]] = {1, 1, 1};
p[[7]] = {-1, 1, 1};
p[[8]] = {-1, -1, 1};
  
  
sur[1] := {p[[1]], p[[2]], 
              p[[6]], p[[5]], p[[1]]};
sur[2] := {p[[2]], p[[3]], 
              p[[7]], p[[6]], p[[2]]};
sur[3] := {p[[3]], p[[4]], 
              p[[8]], p[[7]], p[[3]]};
sur[4] := {p[[4]], p[[1]], 
              p[[5]], p[[8]], p[[4]]};
sur[5] := {p[[4]], p[[3]], 
              p[[2]], p[[1]], p[[4]]};
sur[6] := {p[[5]], p[[6]], 
              p[[7]], p[[8]], p[[5]]};
  
obj := Table[Line[sur[i]], {i, 1, 6}];
  
Show[ Graphics3D[ obj ], 
            PlotRange -> {{-3, 3}, {-3, 3}, {-4, 4}}, 
            Boxed -> True, Axes -> True , 
            ViewPoint -> {1.300,  -2.400,  2.000}];
  
Do[ 
p2 = P[5, 5, 8] . Append[p[[i]], 1];      
w = p2[[4]];      
p[[i]] = Drop[p2, -2]/w;
,{i, 1, Length[p]}
];
  
Show[Graphics[obj], 
            AspectRatio -> Automatic, Frame -> Automatic, 
            FrameTicks -> None]
]

[参考文献]
S.ハリントン:「コンピュータ グラフィックス[I]」, マグロウヒルブック, 昭和63年
S.ハリントン:「コンピュータ グラフィックス[II]」, マグロウヒルブック, 昭和63年