トックのCG部屋-トップ別室へ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

アルゴリズムメモ(視線とポリゴンの交差判定)

今回はレイトレーシングで使う視線とポリゴンの交差判定
レイトレーシングの基本的な仕組みは面倒だから書かないよ

説明は追記で
カメラからレイを飛ばして最初にあたったものを描くわけだけど
要するにレイがあたる可能性があるポリゴンを一個一個判定して
レイが交差する点の中から一番近いのを探してそれを描くことになる

んでそれには線分とポリゴン(三角形)の交差判定ができればいい
図1

図のように三頂点の座標をそれぞれA,B,C
カメラの座標をE,視線の終点座標をDとして
交点座標は面ABC上の点であり直線ED上の点でもあると考えると
交点の座標は下の式のように書ける
式1
ここでk,l,dが一組に定まれば交点座標が出るわけだから
上の式を変形してしたのような方程式を立てる
式2
図にするとこう
図2
赤いベクトルが右辺で青いベクトルが左辺
この方程式はx,y,zそれぞれの成分に分けて書けば3元1次連立方程式になるわけだけど
それを行列ベクトル表記にすると下のようになる
式3
さっきからプログラムのような書き方が混ざってるけどその辺は勘弁してね
で、後はこの連立方程式をクラメールの公式を使って解いてやればk,l,dが求まる
式4
l,dは書き方省略してるけどやってることはkと同じ

さて連立方程式が解けてk,l,dがそれぞれ計算できるけど
これで終わりというわけではないんだよね
まだ連立方程式を解いただけで交差するかどうか判定していない
まず判定しなければいけないのは解が存在するかどうか
面と直線が平行だったら交点がないから解が存在しない
解が存在する条件は公式を見るとわかるけど
式5
計算過程でこれをまず判定して解がなければそこで計算を打ち切る
んで解が存在しk,l,dが出せたら次は線分と三角形が交差するかを判定する
必要な条件は交点が三角形ABC内にあってかつ線分ED上であること
簡単に言うと範囲の問題
面と直線が交差するっても三角形の中ではないかも知れないし
線分が面に届いてないかもしれないという話
で、その条件をまとめると
式6
これらをすべて満たすものが今回求めたかった値
ここでのk,lは後でポリゴン内の値の比例配分に使うし
dは奥行き値(Z値,デプス値)だから後で一番近い交点の判定その他諸々に使う

んでこれをプログラムで書くわけだけど
結局やらなきゃいけないことってクラメールの公式で連立方程式解くことだけだから
ベクトル、行列を作る関数と行列式を計算する関数さえ作れば
交差判定の関数自体はかなりシンプルになるはず
ってことで今回はコード載せなくてもいいよね
-------2011/11/03追記---------
クラメールの公式についての記事を作成
これ
--------追記ここまで----------
  1. 2010/08/30(月) 02:35:18|
  2. 自作レンダラ
  3. | トラックバック:0
  4. | コメント:0
<<キャラ制作 | ホーム | 足部分作り込み>>

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://took.blog72.fc2.com/tb.php/700-59fa01d1
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

Author:トック

プロフィール(仮)

twitter:elgraiv_took
└ブログ更新情報

twitter:elgraiv_take
└無駄な日常つぶやき用

FC2カウンター

コンテンツ一覧

本棚

最近の記事

カテゴリー

月別アーカイブ

ブログ内検索

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。