コンピュータグラフィックス(CG)
こんぴゅーたぐらふぃっくす

PCinfo トップページプログラミング専門分野ハードウエアその他

目次

いろんな座標系
2D座標変換
3D座標変換
線形補間
αブレンディング
Bresenhamのアルゴリズム
次回の予定


いろんな座標系

CGにおいての空間は座標で表現されます。

座標系というのは原点・座標軸・座標の種類をひっくるめた概念です。3Dにおいては座標系がごちゃごちゃしていて混乱しかけますが座標系が分からんことには話が始まらないので意地でも覚えましょう!


<ローカル座標系>
各物体がそれぞれ独自に持っている座標系のことでオブジェクト座標系と呼ばれたりもします。
モデリングなどをする時にローカル座標の原点を物体の中心に持ってきます。

<ワールド座標系>
3D空間における絶対座標系です。
ローカル座標系が複数あるのに対してワールド座標系は1つだけです。複数のローカル座標系はワールド座標系の中に全て位置付けられることになります。

<視点座標系>
視点の位置を原点として視点の方向をZ軸の正方向にとった座標系です。

<スクリーン座標系>
モデリングされたオブジェクトをディスプレイ上に表示する際に使用する座標系です。 通常原点は画面の左上になります。

<カメラ座標系>
カメラを基準とした座標系です。
基本的にスクリーン座標系と大差はありません。
図を書けばスクリーン座標系違いは一発で分かるのですが面倒なのでまた気が向いたときにでも・・・

目次へ


2D座標変換

座標変換というと何か難しく聞こえますが、要は図形を操作することです。

コンピュータ上においては全ての図形は座標によって管理されてますので、その座標を操作することは 図形を操作することを意味します。ですから図形変換といわずに座標変換とよんでいるのです。

さて、その座標変換ですが主に平行移動・拡大縮小・回転・せん断の4種類があり、その変換の対象が 2次元か3次元か、つまり平面か立体かによってちょっと計算が変わります。

まずは2次元座標変換からみてみましょう。

2次元において、座標を決定するための変数は(x, y)の2つですね。
で、この座標(x, y)を決定するための関係式は

	x' = ax + by + m
	x' = cx + dy + n

となります。上記の式の a, b, c, d, m, n の部分の値を操作することによって新しい座標(X', Y')を 決定するのです。では平行移動・拡大縮小・回転・せん断それぞれの式をみてみましょう。

《平行移動》
	x' = x + tx
	y' = y + ty

《拡大縮小》
	x' = sx
	y' = sy

《回転》
	x' = xcosθ - ysinθ
	y' = xsinθ + ycosθ

《せん断》
	X軸について	Y軸について
	x' = x + dx	x' = x
	y' = y		y' = y + dy

さて、上の式を見てもらうと分るように変数名が a とか b とかじゃなくなってます。例えば拡大縮小 の部分は先の説明の通りに書けば X' = ax Y' = dy と書くのが筋でしょう。にも関わらずなぜ 変数名を s としたのかというと、拡大縮小を英語で書くと scale だから頭文字を取って・・・というのも ありますが、次ぎに述べる行列との対応関係を分りやすくするためなのです。

いままで座標を操作するための式をみてきたわけですが、実際には上の式をそのまま使用するのではなく 行列として計算することになります。なぜわざわざ行列を使わにゃならんのかといいますと、複数の 変換を同時にする場合、行列の性質上計算が楽になるからです。

それでは最初に示した関係式を行列で表現してみましょう。

	|x'|   |a   b   m||x|
	|y'| = |c   d   n||y|
	|1 |   |0   0   1||1|

行列って何だったか忘れちゃった人は高校の教科書でも引っ張り出してきて 勉強し直しましょう。では、この式を平行移動・拡大縮小・回転・せん断それぞれの式 に当てはめてみましょう。

■平行移動■
	|x'|   |1   0  tx||x|
	|y'| = |0   1  ty||y|
	|1 |   |0   0   1||1|

■拡大縮小■
	|x'|   |s   0   0||x|
	|y'| = |0   s   0||y|
	|1 |   |0   0   1||1|

■回転■
	|x'|   | cosθ  sinθ   0||x|
	|y'| = |-sinθ  cosθ   0||y|
	|1 |   |  0      0     1||1|

■せん断■
	X軸について		Y軸について
	|x'|   |1   0  dx||x|	|x'|   |1   0   0||x|
	|y'| = |0   1   0||y|	|y'| = |0   1  dy||y|
	|1 |   |0   0   1||1|	|1 |   |0   0   1||1|

近いうちにC言語とJavaとVBでのプログラム例をのっけときます。(たぶん・・・)
次回は3次元座標変換です。

目次へ


3D座標変換

では引き続き座標変換の話です。今回は3次元座標変換です。

3次元での座標は(x, y, z)の3変数により管理されることになります。2次元での縦・横に加え 新たに奥行きという要素が加わることになります。

まずは、座標(x, y, z)を決定するための式をみてみましょう。

	x' = ax + by + cz + l
	y' = dx + ey + fz + m
	z' = gx + hy + iz + n

要素が1つ増えただけなので2次元のときと大して違いはありません。 では3次元での平行移動・拡大縮小・回転・せん断の式をば。

《平行移動》
	x' = x + tx
	y' = y + ty
	z' = z + tz

《拡大縮小》
	x' = sx
	y' = sy
	z' = sz

《回転》
	X軸回転			Y軸回転			Z軸回転
	x' = x			x' = xcosθ + zsinθ	x' = xcosθ - ysinθ
	y' = ycosθ - zsinθ	y' = y			y' = xsinθ + ycosθ
	z' = ysinθ + zcosθ	z' = -xsinθ + zcosθ	z' = z

《せん断》
	X軸について	Y軸について	Z軸について
	x' = x + dx	x' = x		x' = x
	y' = y		y' = y + dy	y' = y
	z' = z		z' = z		z' = z + dz

回転のとこがちょっと面倒くさくなってますね。それぞれの軸に対しての回転を考えなければなりません。 この3つの回転の組み合わせで対象物の向きを操作する訳ですが、回転させる順番によって結果が変わって しまうので注意が必要です。

例えばX軸回転→Y軸回転とした場合とY軸回転→X軸回転とした場合とでは結果が異なります。

それでは行列に話を移しましょう。

	|x'|   |a   b   c   l||x|
	|y'| = |d   e   f   m||y|
	|z'| = |g   h   i   n||z|
	|1 |   |0   0   0   1||1|

要素が増えてもやり方は2次元のときと一緒です。もはや話すことはありませんね。あっ・・・1つありました。 2次元のときは3×3の行列、3次元のときは4×4の行列になっています。普通に考えたらそれぞれ2×2、3×3の 行列でも良いように一見思えますが、そうしてしまうと定数部分が消えてしまい平行移動ができなくなって しまいます。だから1つ分余計に行列を増やして定数部分を確保している訳です。
せん断に関しては回避法がないこともないですが・・・・・

■平行移動■
	|x'|   |1   0   0  tx||x|
	|y'| = |0   1   0  ty||y|
	|z'|   |0   0   1  tz||z|
	|1 |   |0   0   0   1||1|

■拡大縮小■
	|x'|   |s   0   0   0||x|
	|y'| = |0   s   0   0||y|
	|z'|   |0   0   s   0||z|
	|1 |   |0   0   0   1||1|

■回転■
	X軸について
	|x'|   |  1      0     0    0||x|
	|y'| = |  0   cosθ  -sinθ  0||y|
	|z'| = |  0   sinθ   cosθ  0||z|
	|1 |   |  0      0     0    1||1|

	Y軸について
	|x'|   | cosθ   0   sinθ   0||x|
	|y'| = |  0      1     0    0||y|
	|z'| = |-sinθ   0   cosθ   0||z|
	|1 |   |  0      0     0    1||1|

	Z軸について
	|x'|   |cosθ  -sinθ   0    0||x|
	|y'| = |sinθ   cosθ   0    0||y|
	|z'| = |  0      0     1    0||z|
	|1 |   |  0      0     0    1||1|

■せん断■
	X軸について		Y軸について
	|x'|   |1   0   0  dx||x|	|x'|   |1   0   0   0||x|
	|y'| = |0   1   0   0||y|	|y'| = |0   1   0  dy||y|
	|z'| = |0   0   1   0||z|	|z'| = |0   0   1   0||z|
	|1 |   |0   0   0   1||1|	|1 |   |0   0   0   1||1|

	Z軸について
	|x'|   |1   0   0   0||x|
	|y'| = |0   1   0   0||y|
	|z'| = |0   0   1  dz||z|
	|1 |   |0   0   0   1||1|

さて、困ったことにこれもプログラムを用意していません。本当は用意していたのですがどうやら 間違って削除してしまったようです。よって再び作り直しです。

話を先に進めていきたいのでソースの方は少々遅れるかもしれませんが、気長に待っていてください。

目次へ


線形補間

私がこの「線形補間」という言葉を初めて知ったとき「点と点の間を線で結ぶ」という連想をしました。 点同士を線で結んでいく折れ線グラフのようなものを想像した訳です。

まぁ、この考え方も線形補間の1つの例としては間違っていないのですが、線形補間という言葉自体 はもっと広い意味で使われます。


補間というのは読んで字のごとく「間を補う」という意味ですが、数学的には 特に「ある数値とある数値の間の値を求めること」を指します。で、線形補間の場合、 その間の値を求めるのに線形性(直線の性質)を利用する訳です。

例えば、(3 ,? ,7)というように3,7の間の ? の数値を求めたい場合、線形補間を用いると 5になるというのは直感的に理解できると思います。(5, ?, ?, ?, 25)という場合でも この数列に線形性があるとするなら(5, 10, 15, 20, 25)というように補間できることは 分りますね。

2次元座標で、座標(X1, Y1) (X2, Y2) の2点間において座標(X, Y)を線形補間する場合、


	Y=(Y2-Y)/(X2-X)*(X-X1)+Y1  でOK!ってことですね。

特定の座標を求める場合は X か Y のどちらかにそれぞれ(X1<X<X2) (Y1<Y<Y2) の範囲で値を代入すれば 良いですし、その範囲で値を変化させれば直線で補間されることになります。

とりあえず、”線形補間ってこんなもんなんだ”というのは以上で分ったとして、問題なのは これが一体何の役に立つのってことですよね。

結論から言うと、かなり色々と役立ちます。最初に話したように直線描画ができますし、 色のグラデーションを作ったり、画像の半透明処理なんかも出来ます。3Dグラフィックの分野では 法線ベクトルの計算とかモーフィング処理などで大活躍です。

半透明処理に関しては次回に具体的なお話をしますんでお楽しみに!

目次へ


αブレンディング

前回の予告通りアルファブレンド(半透明処理)の話しをします。

半透明処理は特に説明せずともみなさんご存知でしょう。よくゲームなどで使われる技術ですよね。例えば、RPGやADVゲームなんかの メニューウィンドウやらメッセージウィンドウは単なる塗潰しじゃなくて半透明になっていますよね。 ウィンドウに限らずエフェクトに使われたりなど用途も広くて、かなり使える画像処理技術といえるでしょう。

そんな半透明処理を実現する手法としてアルファブレンディングがあります。で、早速αブレンディングの話しに入りたい のですが、その前に半透明処理の簡単な原理を説明します。

要するに半透明というのは「画像同士の色の混ぜ合わせ」であるといえます。コンピュータでの色の情報と言うのは RGB値で表現されますので、各画素(Pixel)同士のRGB値を加工することで半透明を実現することができます。最も簡単な方法は ”各画素同士を足して割る2”してやる方法です。

	R' = (R1+R2)/2
	G' = (G1+G2)/2
	B' = (B1+B2)/2

とするとちょうど半々の色の混ぜ合わせになります。(サンプル↓)

+ =

上のサンプルですと、2つの画像は50%ずつの混ぜ合わせ(ブレンド)ということになります。さて、それでは 本題のαブレンディングの話しに入りましょう。αブレンディングとはα値(アルファ値)を変更することによって 自由に画像同士の色の混ぜ合わせ比率を変更することのできる半透明処理手法です。計算方法は、

	R' = R1*(1-α) + R2*α
	G' = G1*(1-α) + G2*α
	B' = B1*(1-α) + B2*α

となります。α値は0〜1までの値を取ります。ちなみに先のサンプルである50%ブレンドの場合はα= 0.5として 計算すると同じ結果になります。


補講:

さて、以上αブレンドの計算式を紹介した訳ですが、実はこの計算式をそのままプログラムに当てはめてしまうのは あまり良く無いようです。もう少し高速に処理できる様に手直ししてやる必要があります。

あと、画像の画素(Pixel)を取り出す方法ですが、Windows APIにGetPixel()という画素を取り出すための 関数が用意されています。ですのでGetPixel()を使って画像処理を試みてください。きっとあまりの 処理の遅さにあ然とすること間違いありません。(だめじゃん!)

改善手法に関してはいづれ気が向いたらお話します。ソースもね。

目次へ


Bresenhamのアルゴリズム

今回の試みはズバリ「直線を引こう!」です。

まぁ、直線なんてのは"始点・終点の座標"と"傾き"が分っていれば簡単に引ける訳ですが、 傾きを求めて線を引く(点を打っていく)方法ですとどうしても実数計算が入ってしまう訳です。

特に昔の計算機では実数演算に膨大な処理時間が掛かっていましたので、出来るだけ実数を扱わない アルゴリズムが求められていたのです。今回お話するブレゼンハムの考案したアルゴリズムは実数計算を伴わずに かつ加算・減算のみで直線が引けてしまうアルゴリズムなのです。


Bresenhamの線分描画のように加算・減算のみで実数計算を含まないアルゴリズムをDDA(Digital Differential Analyzer) といいます。日本語に訳すとデジタル微分解析(器)ってことになりますが、何か文字だけ見ると近寄れない オーラがただよってますな。(~o~)

実際はDDAのアルゴリズムは単純な話しなんで、サクッとDDAの代表格であるBresenhamの線分描画アルゴリズムを 理解してしまいましょう。


始点(x1, y1) 終点(x2, y2)に関しての線形補間を考えます。Bresenhamのアルゴリズムにおいては傾きの算出はせずに 誤差値(error)をフラグとしてx値 y値をそれぞれ増加させていく方法を取ります。

例えば(0, 0)から(10, 20)までの 直線描画の場合、何とかしてx値が2増加した場合にy値が1増加するようにプログラムを組めば、目的とする直線が 引けることは分りますね。では、実際にどうすればよいのでしょう?


まずは、始点から終点までの距離を算出します。この場合、

xの距離 = x2-x1 = 10-0
yの距離 = y2-y1 = 20-0


となります。距離が求まったならば、その距離の大きい方を基準として座標の値を増加させていきます。上の計算では yの距離の方が大きいですので、yの値を基準として増加させていきます。

しかし、ただyの値のみを(例えば1ずつ) 増加させただけではxに平行な線が引けるばかりでちっとも望む線を引くことができません。とすると、当然何らかの 方法でy値の増加とともにx値を増加させなければなりません。


そこで登場するのが誤差値(error)です。y値が増加すればそれに伴ってx値も増加しなければならないのに 変化が無いというのは、考え方を変えると、y値の増加に対しx値のズレ(誤差)が現れているともいえます。 よって、そのズレ(誤差)を計算してフラグとして利用することによりx値を増加させることができます。


1. y値の増加ごとに 誤差 += xの距離 の計算をする。

2. 誤差の合計がyの距離を超えたらy値を増加させる。

3. 誤差値をyの距離で引く

4. 1に戻る


この作業を繰り返せば良いことになります。「何かよくワカンナイ(;_;)」という人は実際に方眼紙にでも グラフを書いていってみてください。恐らく予想通りの線が引けると思います。


今回のプログラムのC言語サンプルを載せておきます。参考にしてください。


(Bresenhamの線分描画アルゴリズムのソース)


さて、以上説明してきたBresenhamの線分描画アルゴリズムですが、これって結局何かの役に立つんでしょうか? ただ直線を引くだけでしたら既存の関数を利用すればよいだけの話です。とすると、Bresenhamのアルゴリズムの 価値は”加算・減算のみで実数演算は無し”って部分が、現在のコンピューターを使った場合に既存の関数を 利用するよりどれだけ処理を高速化できるか?という部分に注目されます。

で結論は?と言いますと、

これがあんまり処理の高速化に貢献してくれないみたいなんだよね〜(T0T)、はぁ。

現在のパソコンなんかは昔のパソコンと違ってCPUに高性能な実数演算ユニットが搭載されてる上に、 コンパイラの最適化技術の向上も合わさって、Bresenhamはもう実質不要状態に・・・ (;´Д`)


でもまぁ、3D空間に直線を引く場合なんかに限定的に利用できることがあるっぽいので とりあえずBresenhamのアルゴリズムを学んだことは無駄では無かったっということにしておこう。

目次へ


次回の予定

ブレゼンハムアルゴリズムかな?

目次へ





HOME