2011/09/27

頂点の可視性判定(同時上映:Processingで行列操作)

3次元情報が与えられた頂点集合のうち、実際にレンダリングする際にカメラに写るものとそうでないものを判定する実験です。

通常、3D における可視性の判定は非常に重たい問題なのですが、今回は単に、『頂点とカメラの間に遮蔽物が存在するか否か』という簡単な問題だけを扱う事にしました。

テストデータはこんなの(↓)。四角形の板がたくさんあり、それぞれの頂点は 3 次元世界座標が既知であるとします

 

愚直な方法ではありますが、判定したい頂点とカメラ視点とを結ぶ線分が、任意のポリゴンと交差するか否かで可視性を決定できます。

通常、より手前のポリゴンに覆い隠されてしまう頂点は、カメラに写りません。

前回のお絵描きテクスチャで用いた幾何テストを応用します。

すべての頂点に対して遮蔽物の有無を判定する場合、アルゴリズムの時間計算量は恐らく O(n2) になるのですが、今回の例くらいの規模ならば、充分にリアルタイムでの実行が可能でしょう。

結果は以下の通り。赤色で示した頂点は可視点、青色で示した頂点は不可視点です。


実際にポリゴンを張ってみた結果は以下の通り。どさくさに紛れて一部に青頂点の切れ端が写り込んでいますが、いずれも大きさが誇張された頂点が、遮蔽物からはみ出ているだけです。


というわけで、邪魔な頂点を消すとこんな感じですっきりしました。


これだけだと特に面白みはありません(そのため、動作するサンプルやムービーはありません)。ですが、3D インタフェース等を考える際に何かしら使えそうな気がします。



【※ おまけの話】

一般的なレンダリングパイプラインでは、物体のローカル座標 pl に対して、投影面座標 pp を以下のように求めます(※ Processing は左手系のくせに列ベクトルを採用しているため、DirectX とは異なる式になります)。

pp = Mp Mv Mw pl

ここで、 Mp を射影変換行列、Mv をカメラ行列(ビュー行列)、Mw をワールド行列と言い、それぞれ以下のような役割を持っています。
  • Mw … ローカル座標空間から世界座標空間への変換
  • Mv … ワールド座標空間からカメラ座標空間への変換
  • Mp … カメラ座標空間から投影面座標空間への変換

実例で学ぶゲーム 3D 数学』によると、世界座標空間(ワールド座標系)は、「他のすべての座標系を指定するための大域的な基準座標系を設置する特別な座標系」で、要するに 3次元空間を最も客観的に示す事ができると考えて差し支えのないものです。

その他の座標空間は、いずれも(3次元空間中の)何らかの物体に関連付けられており、その空間内における座標値は、座標空間に関連付けられた物体からの相対的な位置関係を表す事になります。

たとえば、Processing におけるカメラ座標空間の原点はカメラの視点と一致しており、さらにカメラ z 軸は光軸に平行になっています。




さて、これらの行列にアクセスする事ができれば、とある 3 次元点のローカル座標値とカメラ座標値、そして世界座標値を相互変換する事ができるようになります。実際、過去に Processing のカメラ行列を再現して座標空間の変換を行った事がありました。

以前まではいちいちカメラ行列を計算で求めていましたが、実は Processing でカメラ行列にアクセスする裏技的な方法が存在する事に気付きました。camera() メソッドでカメラを初期化した直後に、g.getMatrix() を呼ぶと、カメラ行列が取得できるのです。

void setup() {
  size(400, 300, P3D);
  noLoop();
}

void draw() {
  camera(0, -1000, 1400, 0, 0, 0, 0, 1, 0);
  
  // カメラ行列の出力
  printCamera();
  
  // カメラ行列の取得および出力
  PMatrix3D viewMat= (PMatrix3D)g.getMatrix();
  print  (viewMat.m00 + "\t" + viewMat.m01 + "\t");
  println(viewMat.m02 + "\t" + viewMat.m03);
  print  (viewMat.m10 + "\t" + viewMat.m11 + "\t");
  println(viewMat.m12 + "\t" + viewMat.m13);
  print  (viewMat.m20 + "\t" + viewMat.m21 + "\t");
  println(viewMat.m22 + "\t" + viewMat.m23);
  print  (viewMat.m30 + "\t" + viewMat.m31 + "\t");
  println(viewMat.m32 + "\t" + viewMat.m33);
}

これを実行すると、コンソールに printCamera() と、g.getMatrix() で得た行列の要素が出力されます。printCamera() の出力には丸め誤差がありますが、両者がほぼ一致している事がわかります。

> 0001.0000  0000.0000  -0000.0000  0000.0000
> 0000.0000  0000.8137  0000.5812 -0000.0001
> 0000.0000 -0000.5812  0000.8137 -1720.4651
> 0000.0000  0000.0000  0000.0000  0001.0000
>
>1.0    0.0         -0.0        0.0
>0.0    0.81373346  0.5812382   -6.1035156E-5
>0.0    -0.5812382  0.81373346  -1720.4651
>0.0    0.0         0.0         1.0

実は、この g.getMatrix() で取得しているのは、単なるカメラ行列ではなく、Mv Mw なのです。

従って、何らかのワールド変換(translate()rotateX() 等)を施した場合、 printCamera() で出力される行列と g.getMatrix() で得られる行列は当然異なるものになります。

先ほどのプログラムを以下のように修正して実行してみると、その違いを確かめる事ができます。

void setup() {
  size(400, 300, P3D);
  noLoop();
}

void draw() {
  camera(0, -1000, 1400, 0, 0, 0, 0, 1, 0);  
  rotateY(radians(45));  // ←追加
  
  // カメラ行列の出力
  printCamera();
  
  // カメラ行列の取得および出力
  PMatrix3D viewMat= (PMatrix3D)g.getMatrix();
  print  (viewMat.m00 + "\t" + viewMat.m01 + "\t");
  println(viewMat.m02 + "\t" + viewMat.m03);
  print  (viewMat.m10 + "\t" + viewMat.m11 + "\t");
  println(viewMat.m12 + "\t" + viewMat.m13);
  print  (viewMat.m20 + "\t" + viewMat.m21 + "\t");
  println(viewMat.m22 + "\t" + viewMat.m23);
  print  (viewMat.m30 + "\t" + viewMat.m31 + "\t");
  println(viewMat.m32 + "\t" + viewMat.m33);
}

実行結果は以下の通り。

> 0001.0000  0000.0000  -0000.0000  0000.0000
> 0000.0000  0000.8137  0000.5812 -0000.0001
> 0000.0000 -0000.5812  0000.8137 -1720.4651
> 0000.0000  0000.0000  0000.0000  0001.0000
>
>0.70710677  0.0         0.70710677  0.0
>-0.41099748 0.81373346  0.41099748  -6.1035156E-5
>-0.5753964  -0.5812382  0.5753964   -1720.4651
>0.0         0.0         0.0         1.0

明らかに行列が一致していない事が確認できます。

カメラ初期化直後は、特にワールド変換を施していないため、ワールド行列 Mw は単位行列 I ですから、
Mv Mw = Mv IMv

となり、カメラ行列がそのまま得られる事になります。カメラ行列が必要な場合は、必ずカメラ初期化直後に変換行列を取得するようにしましょう。

カメラ行列 Mv が判っていると、ワールド変換を施した後に g.getMatrix() で得た行列 Mv Mw から、ワールド行列 Mw を以下のように求められます。

Mw = Mv-1 Mv Mw

なお、Mv-1Mv の逆行列で、Processing では Mv.invert() で得られます。また、行列の積 Ma Mb は、Mb.preApply(Ma) で得られます。いずれも戻り値は void で、処理結果はメソッドを呼んだインスタンスにそのまま格納されます。

これを基に、ワールド行列 Mw を得るソースコード例を示します。

void setup() {
  size(400, 300, P3D);
  noLoop();
}

void draw() {
  // ======================
  // カメラの初期化
  camera(0, -1000, 1400, 0, 0, 0, 0, 1, 0);
  
  // カメラ逆行列を求める
  PMatrix3D iViewMat= (PMatrix3D)g.getMatrix();
  iViewMat.invert();
  
  // ======================
  // ワールド変換
  rotateY(radians(30));
  
  // ワールド行列を求める
  PMatrix3D worldMat= (PMatrix3D)g.getMatrix();
  worldMat.preApply(iViewMat);
  
  // ワールド行列の出力
  print  (worldMat.m00 + "\t" + worldMat.m01 + "\t");
  println(worldMat.m02 + "\t" + worldMat.m03);
  print  (worldMat.m10 + "\t" + worldMat.m11 + "\t");
  println(worldMat.m12 + "\t" + worldMat.m13);
  print  (worldMat.m20 + "\t" + worldMat.m21 + "\t");
  println(worldMat.m22 + "\t" + worldMat.m23);
  print  (worldMat.m30 + "\t" + worldMat.m31 + "\t");
  println(worldMat.m32 + "\t" + worldMat.m33);
}

実行すると、以下のように出力されます。

> 0.8660254   0.0     0.5             0.0
> 0.0         1.0     2.9802322E-8    0.0
> -0.5        0.0     0.8660253       0.0
> 0.0         0.0     0.0             1.0

これは、y 軸まわりに 30 度(π/6 rad)分の回転行列
にほぼ一致します。

話が長くなってしまったので、もう一度整理しますと、『ワールド行列 Mw はローカル座標から世界座標に変換する行列』であり、敢えてこれを求める動機は、各ローカル座標のみが既知である物体同士の接触判定を、世界座標レベルで可能にするためです。

そこで最後に、とあるローカル座標 pl から、世界座標 pw を求めてみましょう。

この変換は、Processing では Mw.mult(pl, pw); のように書きます。このとき pw は新たに求めた世界座標で上書きされます。

void setup() {
  size(400, 300, P3D);
  noLoop();
}

void draw() {
  // ======================
  // カメラの初期化
  camera(0, -1000, 1400, 0, 0, 0, 0, 1, 0);
  
  // カメラ逆行列を求める
  PMatrix3D iViewMat= (PMatrix3D)g.getMatrix();
  iViewMat.invert();
  
  // ======================
  // ワールド変換
  rotateY(radians(30));
  
  // ワールド行列を求める
  PMatrix3D worldMat= (PMatrix3D)g.getMatrix();
  worldMat.preApply(iViewMat);
  
  
  // ======================
  // ローカル座標から世界座標を求める
  PVector localVec = new PVector(100, 0, 0);
  PVector worldVec = new PVector();  // 領域だけ確保
  
  worldMat.mult(localVec, worldVec);
  
  println("Local: " + localVec);
  println("World: " + worldVec);
}

実行すると、このようになります。

> Local: [ 100.0, 0.0, 0.0 ]
> World: [ 86.60254, 0.0, -50.0 ]

これでめでたく、複数の3 次元座標空間を往ったり来たりするために必要な道具が揃った事になります(ただし射影行列の議論は面倒なので省きました。わざとです)。

ちなみに、この記事の前半で述べた『光線とポリゴンの交差判定』のような幾何テストは、世界座標基準で行いました。

ゲーム等の接触判定の場合は、判定対象をどちらかのローカル座標系に変換する流儀もありますが、それも同様の議論で行う事ができます。

というわけで、今回のまとめ。

行列がわかると、Processing はもっとおもしろくなる!

以上。

0 件のコメント:

コメントを投稿

ひとことどうぞφ(・ω・,,)