点と三角形の衝突判定

hit-point-triangle.png

やり方は3通りあります

  1. 外積を使って、1辺ずつ点の位置との相対関係を調べる方法
  2. 重心座標を使う方法
  3. 内積を使う方法

各方法の比較

概要 次元 三角形の頂点の並び順
重心座標を比較する方法 辺の上に点があるかどうか判定するのが難しい。内側か外側かだけ判定するのなら向いている 2D なんでもok
外積を使う方法 内積の方法より高コスト[2] 3Dok 3Dだと反時計周り限定
内積を使う方法 外積の方法より低コストで結果的に重心座標を使う方法と似ている 3Dok 3Dだと反時計周り限定
2D外積を使う方法 高速 2D 反時計周り限定
2D外積+符号判定 2D なんでもok

三角形の中の点は重心座標を使って表現できます。
それを逆手にとって、
点の位置から重心座標のパラメータ(u,v)を逆算して、
u,vが両方とも0~1の範囲だったら三角形の内側に点が存在している、と判定する方法です[1]。

/**
    @return 0:外側,1:内側-1:異常終了,2:辺BCの上,3:辺ACの上,4:辺ABの上*/
    static int hit(const glm::vec3& p,const tri& t){
        //Barycentric Technique(重心座標を使った方法)
        //http://www.blackpawn.com/texts/pointinpoly/default.html
        glm::vec3 ac = (t.c) - (t.a);
        glm::vec3 ab = (t.b) - (t.a);
        glm::vec3 ap = p - (t.a);
 
        //点の位置pから重心座標パラメータ(u,v)を解くために必要な値を計算する
        float acac = glm::dot(ac, ac);
        float acab = glm::dot(ac, ab);
        float acap = glm::dot(ac, ap);
        float abab = glm::dot(ab, ab);
        float abap = glm::dot(ab, ap);
 
        float denom = acac * abab - acab * acab;
 
        if (denom == 0) {
            cout << "devide by 0 at point triangle hit test" << endl;
            return -1;
        }
 
        float u = (abab * acap - acab * abap) / denom;
        float v = (acac * abap - acab * acap) / denom;
 
        cout << "u=" << u << " v=" << v << endl;
        const float eps = numeric_limits<float>::epsilon();
 
        //辺ABの上に点がある場合
        if (abs(u) <= eps && v <= 1.0 && v>0.0) {
            return 4;//on INIEDGE;
        }
 
        //辺ACの上に点がある場合
        if (abs(v) <= eps && u <= 1.0 && u>0.0) {
            return 3;//on PREVEDGE;
        }
 
        //辺BCの上に点がある場合
        if ( abs(u + v - 1.0) <= eps ) {
            return 2;//on NEXTEDGE;
        }
 
        if ( u >= eps && v >= eps  && (u + v <= 1)) {
            return 1;//内側
        }
        return 0;//外側
    }

C++デモ..point_in_triangle_test.cpp

q?_encoding=UTF8&ASIN=493900791X&Format=_SL160_&ID=AsinImage&MarketPlace=JP&ServiceVersion=20070822&WS=1&tag=lifeiscool01-22
q?_encoding=UTF8&ASIN=B00CLZIKC2&Format=_SL160_&ID=AsinImage&MarketPlace=JP&ServiceVersion=20070822&WS=1&tag=lifeiscool01-22

barycentric-coordinates cross dot

サポートサイト Wikidot.com barycentric-coordinatescrossdot