ポリゴン上に点があるかの当たり判定

Question

http://marupeke296.com/COL_Basic_No2_ShortTec.html#斜面に立つには？
こちらのサイトにあるポリゴンの上に点があるかの判定で、
法線が同じか異なるかで判断すると書いてあり
float x = 5, y = 0, z = 5;
polygon poly[3];
poly[0].px = 0, poly[0].py = 0, poly[0].pz = 10;
poly[1].px = 10, poly[1].py = 1, poly[1].pz = 0;
poly[2].px = -10, poly[2].py = 0, poly[2].pz = 0;

float cx = 0, cy = 0, cz = 0;


cx = poly[0].py * poly[1].pz - poly[0].pz * poly[1].py;
cy = poly[0].px * poly[1].pz - poly[0].pz * poly[1].px;
cz = poly[0].px * poly[1].py - poly[0].py * poly[1].px;



printf("%f, %f, %f \n", cx, cy, cz);

cx = poly[0].py * z - poly[0].pz * y;
cy = poly[0].px * z - poly[0].pz * x;
cz = poly[0].px * y - poly[0].py * x;

printf("%f, %f, %f", cx, cy, cz);

このようにコードを作ったのですが、中にあるはずの点でも法線が違います。
自分の解釈の違いなのだと思いますが、ポリゴン上に点があるかないかではどこが間違っているのでしょうか？

Answer 1

これは2次元上の話だと思います。

---

【追記】
すいません、説明不足すぎました。

私もリンク先の記述は言葉足らずだと思っていて、自信を持って解釈できないのですが、
少なくとも
・法線についてベクトルでなく「奥から手前」or「手前から奥」の2通りで見ている
・辺の回り方向を見ている
点は、2次元の話だと解釈できます。

その上で、やっと考えがまとまったのですが、
前項からのつながりや「どの平原ポリゴンの上にいるか」という言葉から考えるに、おそらくこれはXY平面への投影を考えています。
まずXY座標だけを見てどのポリゴンの領域内にいるかを判定し、次いでZ座標を当該ポリゴンに接する位置まで移動させるという処理について書かれているのでしょう。
おそらく、すべてのポリゴンに対して平面に接する座標を算出→領域内判定の順で計算するより計算量が少なく済むと思います。

Comments

[fana]

理由の記述が遅くなりましたが，
質問者が提示したURLの先は３次元の話に見えるので，低評価を押しました．

「２次元上」というのが "coplanar" を指しているのかと思えますが，
であれば，そう書かないと伝わらないと思います．

[fana]

加筆修正がなされたため低評価を取り下げさせていただきます．

「２次元上」とは，
「URL先の話がデータ構造として Height Field を相手にしている」ことを意味しての話なのですね．
（すなわち，実質２次元である，と）

Answer 2

ポリゴンの上に点があるかの判定

少なくとも質問文内のコード断片には「判定」を行っている記述が見られません．

法線が違います

とは何を指して言っているのでしょう？
法線の「向き」が揃っているかどうかを判定する話なので，向きの判定をしてください．
具体的には内積の符号を見るとよいでしょう．

※示されたリンク先の記述は，やや言葉足らずな雰囲気もありますので，念のため補足しておきますが，
「ポリゴン上に点が含まれるかを判定」のところの話は，三角形と判定対象の点が同一平面上に存在することが前提となっています．
（一個前の「斜面に立つには？」の続きの話になっている）

Comments

[apa]

内積の符号で判断するというのは、３角ポリゴンの法線ベクトルと調べたい点の内積をとるということなのでしょうか？

[fana]

URL先で説明されているように
「三角形の辺と，調べたい点」の外積と，三角形の法線　との内積を調べるということです．

前者をより詳細に書けば，
三角形の頂点群を A,B,C，調べたい点を P とすると，
ある辺ABについて，
ベクトル B-A(＝AからBに向かうベクトル) と，ベクトル P-A との外積　といった感じです．

[fana]

> ベクトル B-A と，ベクトル P-A との外積

の向き　というのは，（三角形を一方の側（表or裏)から観察した場合において）
「頂点Aから見て頂点Bがある方向を例えば "北" と考えるならば，頂点Aから見て点Pがある方向というのは "東側" か "西側" のどちら側なのか？」
次第で逆転します．

「三角形の内側」というのが，この例で"西側"なのであれば，外積が "西側" に相当する向きになっているかどうかを調べればよい，という話です．（点Pが"東側"にあるならば，それはすなわち，三角形の外側にある，ということだから．）
（比較対象たる三角形の法線は，あらかじめその方法に相当するベクトルして用意しておく）

[fana]

「三角形　内外判定」とかで検索すれば，あなたが示したURLの他にも説明が見つかると思うので，よりわかりやすい説明を見つけることもできるのではないか，と想像します．

[apa]

なるほど
符号を見るということの意味が分かりました。
わかりやすい説明ありがとうございました

[fana]

ほぼ無関係な雑談ですが，
話の内容が解りやすい別の判定方法としては，面積を見る方法もあります．

点Pと辺の２端点とを結んでできる三角形の面積を，三角形の３辺それぞれについて求めて，それらの総和を取った場合，
点Pが三角形の内部にある場合には，その総和は三角形の面積と一致します．
点Pが三角形の外部にある場合には，その総和は三角の面積よりも大きくなります．

[apa]

すごい！面積でもいけるんですね
面積はいっさいやってなかったので、今日勉強してみます！
外積になると頂点abcがあって
abベクトル、acベクトル、bcベクトルの3つと点pの外積計算が必要みたいなので、誤差ですが、面積計算の方が軽そうですね。

[fana]

各面積求める際に外積を使うなら，ほぼ同じ計算を行うことになるので，処理は軽くはならないかな，と．
＃たとえば「三角形の頂点のx,y座標というのが均一に(グリッド状に)並んでいる」みたいな，何かデータ特有の前提条件みたいなのを利用すれば簡単に面積計算できる，みたいな場面ならばワンチャンあるか？　とか一瞬思ったけども，そういう場合であれば法線の向き見る側の方法も同じように簡単化できる余地が相応にあるだろうし．

まぁ，面積側の利点は，扱う値というか概念に親しみがある感(?)な部分ですかね．どっちが表でどっちが裏だっけ…？　という話が出て来ない点が「心理的に楽かも」みたいな．