2平面が交わっているかの判定

Question

それぞれ4つの頂点がわかっている３次元空間上にある四角形が、交わっているか判定したく、
ファーストステップとして、下記のサイトを参考に2平面から交線を求めるコードを実装してみました。
https://www.hiramine.com/programming/graphics/3d_planeintersection.html
http://webmath.las.osakafu-u.ac.jp/top/std/help/help0201011036.pdf

交線を求めて、平行か平行じゃないかというところはわかったのですが、
平面が交わっているかの判定方法がわからず困っています。

欲を言えば、交わっていた場合、交線の線分の情報も知りたく、両端の2点の座標も取りたいと思っています。
ひとまず最初の交差判定でつまずいているので、こちらだけでも教えていただけると幸いです。
よろしくお願いいたします。

下記コードはopenFrameworks(c++)で実装しております。

// ofVec4f(float x,float y,float z,float w) 4次元座標格納するクラス
// ofVec3f(float x,float y,float z) 3次元座標格納するクラス
// ofPoint(float x,float y,float z = 0.0) 2次元or3次元座標格納するクラス

//--------------------------------------------------------------
void ofApp::update(){
    ofVec4f planeA(1,-1,-1,1); //サイトの例の値を仮にいれてます
    ofVec4f planeB(2,1,4,-1);
    ofVec3f vec;
    ofPoint point;
    cout << calcIntersection(planeA, planeB, vec, point) << endl;
}

//--------------------------------------------------------------
ofVec4f ofApp::getPlaneEquation(const ofPoint &p1, const ofPoint &p2, const ofPoint &p3) {
    ofVec3f vecAB(p2.x - p1.x, p2.y - p1.y, p2.z - p1.z);
    ofVec3f vecAC(p3.x - p1.x, p3.y - p1.y, p3.z - p1.z);
    ofVec3f cross = vecAB.cross(vecAC); //外積を計算
    float d = -(cross.x * p1.x + cross.y * p1.y + cross.z * p1.z);
    return ofVec4f(cross.x, cross.y, cross.z, d);
}

//--------------------------------------------------------------
bool ofApp::calcIntersection(ofVec4f planeA, ofVec4f planeB, ofVec3f &vec, ofPoint &point) {
    vec = ofVec3f(planeA.x, planeA.y, planeA.z).cross(ofVec3f(planeB.x, planeB.y, planeB.z));
    if (vec.z != 0.0) {
        point.x = (planeA.w * planeB.y - planeB.w * planeA.y) / vec.z;
        point.y = (planeA.w * planeB.x - planeB.w * planeA.x) / (-vec.z);
        point.z = 0;
        return true;
    }
    if (vec.y != 0.0) {
        point.x = (planeA.w * planeB.z - planeB.w * planeA.z) / (-vec.y);
        point.y = 0;
        point.z = (planeA.w * planeB.x - planeB.w * planeA.x) / vec.y;
        return true;
    }
    if (vec.x != 0.0) {
        point.x = 0;
        point.y = (planeA.w * planeB.z - planeB.w * planeA.z) / vec.x;
        point.z = (planeA.w * planeB.y - planeB.w * planeA.y) / (-vec.x);
        return true;
    }
    return false;
}

Comments

[yuba]

「アルゴリズム」タグを追加した方が識者の目にとまりやすくなるかと思います。

[nasymt]

アドバイスありがとうございます。追加させていただきました。

[Orlofsky]

URLは https://teratail.com/help#about-markdown の [リンク] に修正してください。

[swordone]

四角形は凸四角形(へこみのない四角形)であることは保証されていますか？ブーメラン型のような四角形が来る可能性はありますか？

[nasymt]

> Orlofskyさん
すみません、修正させていただきました。

> swordoneさん
4点の座標はどこを移動するかわからないので、ブーメラン型になる可能性もありますね。。
（三角形に分割して考えた方が良い気もしてきました。。）

Answer 1

1. ２つ無限平面の交線を求める
2. 一方の四角形について考えたとき，その四角形が乗る無限平面を交線で２つの領域に分けたときに，４個の頂点全てが一方の領域に属するなら，２つの四角形は交差していない．

（要は，交線が四角形の中を通るかどうかを調べる）という話にはならないかな？

2の判定自体は，交線上の１点の座標Pさえ得ることができれば，
交線の方向ベクトルと平面の法線ベクトルとの外積から作った判定用の方向ベクトルVを用いて，
(頂点 - P)*V
の符号でチェックできる．(*は内積)

（Pを簡単に求める方法が自分の頭からちょっと出て来ないけど…^^）

---

上記2のチェックに通らないとき，交線と四角形(の外周)の交点群をV方向にソートした際の並び順から，最終的な判定ができそうに思う．
{α,α,β,β}みたいな並びなら交差しておらず，{α,β,α,β}みたいな並びなら交差している，という感じで．

---

修正：うっかり「接線」と書いていた箇所を「交線」に修正しました

Comments

[nasymt]

度々のご回答ありがとうございます。
確かに、方法はイメージできたので、後ほど試してみようと思います！
Pはやはり求めるの難しそうですよね...

[fana]

おっと，ナチュラルに言葉を間違っている…　×接線　○交線　ですね．

[fana]

交線の方向ベクトルをUとして，Ｐは線上のどこに取っても良いんだから，U方向成分が0，すなわち P*U = 0 みたいなてきとーな条件を設けて
P*N1 = C1 (N1は平面の法線，C1は原点から平面までの距離）
P*N2 = C2 (同上)
P*U = 0　（U = N1とN2の外積)
とかで求められないだろうか…？

[nasymt]

すみません返信遅くなりましたが、こちらの方法で交差判定できました！Pを求めるのは、実装が悪かったのかちょっとうまくいかなかったですが、先日ご回答いただいた方法から諸々手を加えて交線の線分の端点も求めることができました。
ありがとうございました！

Answer 2

2つの平面が取り得る状態は、

1. 交わらない
2. 一点で接する（一方のある一つの頂点が、他方の平面上にある）
3. 線で接する（一方のある辺が、他方の平面上にある＝一方の隣接する2頂点が、いずれも他方の平面上にある）
4. 内包する（一方の平面の全ての頂点が、他方の平面上にある）
5. 交わる

の5種類ですかね。

一方の平面αの各辺と、他方の平面β（を拡張した無限平面）との交差点を算出し、その算出点が元々のβにあるかどうかを判定するのがまず一点。
で、交差点が実は平面αの頂点と一致するかどうかも判定して、一致する頂点の数を数えれば 2, 3, 4 のいずれかは分かるかと思います。

Comments

[nasymt]

ご回答ありがとうございます。先ほどのfanaさんの回答とあわせて、参考にさせていただきます。

Answer 3

平面が交わっているかの判定方法

その提示コードの戻り値がその判定結果じゃないの？……とか思ったのですが，
やりたいことは，２つの「(無限)平面」の交差判定ではなくて，
３次元空間上にある２つの「四角形」の間の交差判定ということでしょうか．

であれば，
とりあえず２つの四角形を｛α，β｝と呼ぶことにすると…
【αが乗っかる無限平面とβの辺との交点を求め，その交点pがαの内部にあるか？を判定】
という処理を全パターン（αとβの役目を交換したパターンも含めて）やれば，
判定できそうに思います．

上記処理中に，「αの内部にあるp」が見つかれば，それが「交線の線分」の端点になると思います．

Comments

[yuba]

αの辺がβを貫いているという判定だけだと、αの頂点が2つβ上にあるというケースを見逃します。

かといってαの頂点がβ上にあれば true という特例を追加すると、交差しておらず接しているだけというケースを誤って交差判定してしまうので悩ましいです。

[nasymt]

ご回答ありがとうございます。そうです2つの四角形の交差判定です！
先ほど試しに実装してみました。
yubaさんのおっしゃるように、αの頂点が2つβ上にあるというケースを見逃さないよう、条件も追加して、接しているだけのケースも誤判定してしまって、どうしようかなと思っていたところでした。
あといくつか判定されないケースもあり（どこか処理ミスってるだけだと思いますが）、もう少し色々試してみます。

[fana]

頂点bが判定相手の上にいるときは，頂点bを共有する２辺を用いて判定すればよいのだろうか？
頂点{a,b,c}が a-b-c な隣接関係にあるとき，aとcがその面を介して反対側にいるかどうか…的な？

[fana]

日　←これの外周矩形をαとして，αを真ん中の横棒を回転軸にしていくらか回転したものがβであるようなパターンとか，考えると面倒そうだなぁ…

Answer 4

それぞれの四角形を三角形2つに分割して、例えば四角形2つをα、βとして、分割した三角形をα1,α2,β1,β2とすると、

• α1の各辺がβ1,β2と交差するか
• α2の各辺がβ1,β2と交差するか
• β1の各辺がα1,α2と交差するか
• β2の各辺がα1,α2と交差するか

を調べることになるかと思います。交点が辺の内部で、かつ三角形内部であれば確実に交差するのですが、頂点だったり三角形の辺上だったりすると、凹四角形の場合に厄介になります。なのでまずはそれぞれの四角形が凸四角形か凹四角形かを判定しておいたほうがいいような気がします。
以下、解き方概略

凸四角形か凹四角形か

4頂点をA,B,C,Dとする。以下、ベクトルABをV(AB)のようにあらわすことにする。
V(AD)=sV(AB)+tV(AC)
を満たすような実数s,tを求める。四角形になること前提なら、解は存在するはず。拡大係数行列を利用して解ける。この解が、

• sもtも正の数で、その和が1より大きい

凸四角形ABDCとなる。

• sもtも正の数で、その和が1より小さい

角Dが180°を超える凹四角形ABDCとなる。

• sもtも負の数

角Aが180°を超える凹四角形ABDCとなる。

• sとtのいずれか一方が負の数で、和が1未満

sが負なら凸四角形ABCD、tが負なら凸四角形ADBC

• sとtのいずれか一方が負の数で、和が1より大きい

sが負なら、角Cが180°を超える凹四角形ABCD、
tが負なら、角Bが180°を超える凹四角形ADBC

と判別できる。これにより、分割の仕方も決定できる(最初のケースの場合は△ABDと△ACDのように)。

線分(辺)と三角形の交点

△ABCと線分DEとの交点を求めるにあたり、
pV(AB)+qV(AC)=V(OD)+r*V(DE)
を満たす実数p,q,rを求める。これも拡大係数行列の計算で解ける。
この解が、p>0 かつ q>0 かつ p+q<1 かつ 0<r<1を満たせば、△ABCと線分DEは△ABCの内部かつ線分DEの内部で交わる。
p=0,q=0,p+q=1のいずれかを満たすと、共有点は△ABC上にあり、r=0,1のいずれかなら線分DEの端点で共有点を持つ。

Comments

[nasymt]

ご回答ありがとうございます。
アドバイスに従い、凸四角形か凹四角形かの判定まで実装してみました。
「sとtのいずれか一方が負の数で、和が1未満」でtが負の場合のとき、どうしても凹四角形になってしまうのですが、凸四角形になるはずですよね...

「線分と三角形の交点」について質問なのですが、線分DEとは具体的にどの線分を指してますでしょうか...？よく理解できておらずすみません。
よろしくお願いします。

[swordone]

コメント読んで気づきましたが、凹四角形の場合、つなぎ方次第で何パターンか四角形が作れてしまいますね…(｢sもtも正で和が1未満｣において、ABDCもあるが、ABCDやADBCの可能性もある)となると、凹四角形の場合、四角形の辺が定義できないと交差するかどうかが判定できないのでは？

後半の△ABCと線分DEについては、最初のα,βの議論における三角形と辺のつもりです。

[fana]

（処理への入力の時点で，点群の座標しかわからないのではなく，四角形としての情報が既知なのだと勝手に思い込んでいたが，そこらへんどうなんだろう…？）

[swordone]

たしかに、どういう形で情報が与えられているのか気になりますね。単に4つの頂点なのか、｢四角形ABCD｣の頂点A,B,C,Dなのかで大きく違いますからね。

[nasymt]

swordoneさん、fanaさん
ご返信ありがとうございます。
四角形の情報を具体的にいうと、一方は、立方体の各頂点が変形したような3dモデルで、もう一方はプログラム上で生成する四角形ですが、いずれも単なる点群の座標ではなく、「四角形ABCD」の頂点A,B,C,Dとなります。

△ABCと線分DEについても理解しました！

[nasymt]

すみません、今気付きましたが、3dモデルの情報はメッシュとして受け取れるので、ライブラリ側で全て三角形の情報として受け取ることもでき、プログラム側で生成する四角形も凹四角形になるパターンはない前提なので、最初の「凸四角形か、凹四角形か」の判定は省けそうな気がしました。。

Answer 5

http://marupeke296.com/COL_2D_No4_SquareToSquare.html

正方形Aの頂点から出来るベクトル VAn=(vaxn, vayn), n={1,2,3,4}

正方形Bの頂点と正方形Aの頂点から出来るベクトル VBm(vbxm, vbym), m={1,2,3,4}
VAn×VBmで、1つのmに対すしn=1,2,3,4すべてにおいて
VAn×VBm≦0となれば衝突を起こしている。

正方形じゃなくてもこれでいけそう

Comments

[nasymt]

ご回答ありがとうございます。
衝突判定はこの方法でできそうですね、実装してみようと思います。

[swordone]

これ、平面なら成り立つだろうけど、空間だとこう単純にはいかないと思う。