Chandler@Berlin -4ページ目

Chandler@Berlin

ベルリン在住

問題は何か: normal の transformation とは何か

コンピュータの内部で物体を移動させたり,回転させたりさせるには,行列を使うのが便利である.多くの場合,コンピュータ内部では物体は三角形やポリゴンなどで表現され,それらの頂点は座標によって表示される.ある物体を回転,移動させるには,この頂点に行列を適用することが通常行なわれる.頂点は通常3次元のベクトルである.

我々は,それぞれの三角形において,面がどこを向いているかの normal ベクトルを定義することができる.この normal も三次元のベクトルである. normalベクトルは照明の計算に必要なので,3D graphics システムで良く利用される.通常のベクトルは行列の適用で変換されるので,この,normalベクトルにも同じように行列を適用するのは straight forward に思われる.しかし,これは上手くいかない.なぜだろうか? これがこの記事のテーマである.


なぜ通常の transformation が normal では上手くいかないのか.

[3]によると, Eric Haines の説明がわかりやすいとある.[6] に同じ説明があり,確かにわかりやすい.同様の説明は [2]にもある.この説明は図 1のようなものである.

Chandler@Berlin-scaling break
Figure 1. Scaling on a normal break the normal.


図1は,z 軸方向から見た z 方向に鉛直に立つ三次元の平面を考えている.この壁平面は (1,1,0) 方向の normal を持つ.つまりこの図は壁を上から見ている.この壁に次の M 行列を適用することを考える.これはx 方向を二倍に拡大する行列である.

Chandler@Berlin-M

壁は x 方向に二倍に拡大されたが,同じ行列を nomal に適用すると normal はこの壁の normal ではなくなってしまう.図 1の左図では,normal は壁に直交しているが,M の変換後(図右)ではもはや直交していない.これが問題である.

では,なぜnormalベクトルの変換は普通のベクトルと異なるのだろうか.

Why is the normal transformation a inverse transpose?


Abstract

Physically Based Rendering[2] の p.87 (2.8.3) や Realtime rendering[6] の p.35 (3.1.7) には normal の transformationが $(M^{-1})^{T}$ であると記されている.これらの本には説明も詳しいのだが,私はいつも忘れてしまう.今回は normal の transformationがなぜこんな形をしているのか,私なりの理解を記そう.


Introduction

あるベクトルに M という matrix で表現された座標変換(transformation)が施されるとしよう.たとえば回転とか拡大縮小とか移動とかである.位置を示すベクトルに変換を施すにはこの matrix M を掛ければよい.しかし,normal の変換を同じようにすると上手くいかない時がある.本には normal の変換は$(M^{-1})^{T}$であると書かれている[2,6].

この記事では次の3つについて述べよう.

- 問題は何か: normal の transformation とは何か
- なぜ通常の transformation が normal では上手くいかないのか.
- なぜ逆行列の転置なのか

である.
私の友人 Christian が -1/2 を int にした場合には 0 か -1 かという話をしてくれた.Christian は binary search を書いていてこれが問題になったということである.lower bound で小さい方がみつからなかった場合にこれを -1 とした場合,

mid = (left+right)/2

left = -1, right = 0 の時, mid は C,C++,Java では 0 を, python, ruby では -1 となる.この簡単そうなコードが言語によって異なる結果というのは驚きだった.

これは丸めの方法による.C,C++,Java, elisp は 0 へのまるめ(truncation)を行うので,これは 0 である. python, ruby は floor をとるので -1 である.特に modulo 演算を考えると, python や ruby は

x = x/y + x%y

が成立するので有用である.modulo演算も負の数が入ってくると振舞いが言語に依存するので注意が必要である.

もう一つ,この mid を求めるコードは overflow の問題がある.そこで,

mid = low + (high - low)/2;

とすべきである.

参考文献
http://en.wikipedia.org/wiki/Modulo_operation
http://en.wikipedia.org/wiki/Rounding
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
http://xlinux.nist.gov/dads//HTML/binarySearch.html
http://www.codecodex.com/wiki/Binary_search

謝辞

この話を教えてくださったChristian R.に感謝する.