3D物体のカメラ上でのマウスとの当たり判定

Question

コードではなくアルゴリズムや理論、解き方でも構いません。
できるだけprocessing(java)のコードにしていただけるとありがたいです。

ちょっと難しいのですが。(私にとって)

3D物体(平面、立体等)を表示して。
カメラを動かすと、当然、カメラからは回ったり動いたりしてるように見えますよね？
そして、それをキャンバス等に出力する。

その際のキャンバスの座標(2次)に対し。←マウス等
その先にある物体の中で一番近いものを出すには。

つまり、
カメラのある点から直線を引いて一番最初にぶつかる物体をぶつけるには。

どうしたらいいんでしょう。

判定は、いつでも構いません。
オブジェクト描写中でもよければ、全部描写し終わったあとでも。

予定としては、平面しか使わない予定なので。

有限な平面と。
カメラからの直線が、交わるか。
また、距離はどれくらいか、がわかればいいのかなと。

もちろんもっといい方法があればそちらでお願いします<(_ _)>

オブジェクトの情報は、
3次座標、3次回転角度、大きさ(一応正方形しか使わない予定ですが...)

カメラは、原点に対する距離固定で、原点を常に見ているようお願いします。
要するに、3次回転だけです。

どうすればいいのかわかりません。
情報が足りなければ、追記した方がいい内容を教えていただけると助かります。

Answer 1

筋違いな回答であれば申し訳ありません．
座標変換の知識が必要な問題ではないかと思いました．
私自身うろ覚えなのと，ここで説明するのが困難ということもあるので，ここでは概要だけ説明します．

カメラが原点からの距離固定ということであれば，球の極座標形式を使うと便利です．
この空間の原点基準の座標系を「空間座標」とでも名づけます．
こうすると，カメラの位置を空間座標における位置ベクトルで表現することができます．
そして，カメラが原点を常に見ているということなので，これを扱いやすい座標系を考えます．
具体的には，カメラの位置を原点に，カメラと空間座標の原点を結ぶ直線方向をZ軸として，これに直交する平面上に互いに直交するようにX軸，Y軸を取ります．この座標系を「カメラ座標」とします．
そうすれば，カメラが見る画面としてのある平面上の点を，X,Y,Z軸上の単位ベクトルを用いて，カメラ座標での位置ベクトルとして表現できます．カメラからの直線は，この位置ベクトルの0以上の実数倍で表現できます．
こうして，「カメラからの直線上にある点」は，「空間座標でのカメラの位置ベクトル」+「カメラ座標での画面上の位置ベクトル」×「実数」で表現できます．このベクトルがぶつかる物体の中で，実数が最も0に近い物が求める物体ということになります．
ただし，今この2つのベクトルは違う座標系で考えたので，そのまま足すことはできません．カメラ座標における単位ベクトルが，空間座標の単位ベクトルを使ってどのように表現されるかを考え，変換する必要があります．そうすることで初めて，カメラからの直線を空間座標で表現することができます．

「ぶつかる条件」は，物体表面の位置ベクトルと一致するカメラからの直線上の点を表す位置ベクトルが存在するか，という条件で判断します．
物体表面をあらわす位置ベクトルは，単位ベクトルと定数とパラメータ2個で表現することができます．例えば2辺がx軸の正の部分とy軸の正の部分に一致する一辺の長さ1の正方形の内部の点の位置ベクトルtは
t=ax+by(x,yはx軸，y軸各方向の単位ベクトル，a,bは0以上1以下の実数)
と表現できます．a,bが先ほどのパラメータに該当します．
これと，カメラからの直線の表現に使った際の「実数」と合わせてパラメータが3つ登場しました．
2つの位置ベクトルが等しくなるような3つのパラメータが存在するかを，連立方程式を使って解きます．
連立方程式は行列の計算に置き換えられるので，そのための計算を用意すれば解くことができます．
この解が存在し，かつその解が物体表面にあるための条件を満たしていれば「ぶつかる」と判定できます．
条件は，先ほどの正方形の例なら，aかbのどっちかが0以上1以下という条件を満たしていなかったり(その表面を延長した表面にぶつかる)，あるいはカメラ直線の実数の値がマイナスになる(カメラの後ろでぶつかる)ような場合は，ぶつかりません．

Comments

[luma]

わかりやすい説明ありがとうございます！
球の極座標、勉強してみます！
一番汎用性が高いかな～と思ったので選ばせていただきました！！

Answer 2

いわゆるRaycastですね。
自分はあまり詳しいことは分かりませんが、JavaScriptの有名なライブラリである「Three.js」にもその実装があります。

すでにある実装を参考にしてみると分かりやすいかもしれません。
ちなみに該当する箇所は以下の場所でした。

• Ray.js（のintersectTriangleメソッドが面との当たり判定を行ってる部分だと思います）

https://github.com/mrdoob/three.js/blob/master/src/math/Ray.js

ちなみにそれを呼び出している箇所はこちらです↓

• Mesh.js

https://github.com/mrdoob/three.js/blob/master/src/objects/Mesh.js

[追記]
ちなみに、面と線との交差判定についてはこちらが参考になるかもしれません。
http://ft-lab.ne.jp/cgi-bin/wiki.cgi?page=%B8%F2%BA%B9%C8%BD%C4%EA_3DCG

[追記2]
気になって少しRaycastについて調べてみました。
調べたことをQiitaにまとめたのでよかったら見てみてください。

Comments

[luma]

追記のまとめ、とても参考になりました（o_ _)ｏ））
交差判定、勉強になります…
回答ありがとうございます！

Answer 3

画像処理を専門に学んだものではないのでなんともいえませんが，計算を簡単にするために，
表示をするためのモデルと，接触や変形の判定をするためのモデルは分ける，と授業で教わりました．

表示するものは立方体，距離の判定をするのは球体（半径r，座標x1, y1, z1）にすると，
カメラ（半径0，座標x0, y0, z0）と物体との距離は，
sqrt((x0 - x1)^2 + (y0 - y1)^2 + (z0 - z1)^2) - r
で簡単に求められます．
これを真面目に立方体でやろうとすると，
各立方体で最も近い面あるいは辺を求めなければならなくなります．

まず立方体のある面を含む平面を2つの直交ベクトルで表現し，両者に垂直なベクトルを求めます．
3つの直交ベクトルを使って，立方体の面の中の任意のある点からカメラの点までのベクトルを求めます．
最初に使った点に2つのベクトルで作られる成分を足して，その座標が面の中に含まれているかを判定します．
（つまり，平面とカメラとの距離を作る座標が，立方体の面の中に入っているかを判定します．）
含まれていればその面は最短距離になる可能性があります．
含まれていなければその面の4辺のどれかが最短距離になる可能性があります．
このようにしてすべての辺と面に対してカメラからの距離を求めれば，
立方体とカメラの最短距離を求めることができます．

もっと効率よくやる方法があるかもしれませんが，球で近似するのが最も楽です．
まずは球モデルで作ってみて，余力が有れば立方体モデルにしてみてはいかがでしょうか．

Comments

[luma]

判定を考えるうえで、とても参考になりました…
回答ありがとうございます！