7

3D 空間では、光線/線が正方形と交差するかどうかを判断しようとしています。

私は2点で表される光線を持っています:

R1 = (Rx1, Ry1, Rz1) and 
R2 = (Rx2, Ry2, Rz2)

また、正方形は 4 つの頂点で表されます。

S1 = (Sx1, Sy1, Sz1), 
S2 = (Sx2, Sy2, Sz2), 
S3 = (Sx3, Sy3, Sz3) and 
S4 = (Sx4, Sy4, Sz4).

このオンラインの代数方程式をたくさん見つけましたが、この問題に正確に適合するものはないようです。理想的には Java コードで答えてもらいたいのですが、簡単にコードに変換できる方程式でも構いません。

すべての助けをいただければ幸いです。

4

1 に答える 1

20

ソリューションの概要は次のとおりです。

  1. 正方形の平面方程式を計算します (4 つの点が同一平面上にあると仮定します)。

  2. 光線/平面の交差を行います。これにより、何も得られません (正方形に平行な光線であり、光線が平面に埋め込まれている場合は無視します)、または点が得られます。

  3. 交点を取得したら、それを正方形の平面にローカル 2D ベースで投影します。これにより、平面上の点の 2D 座標 (u, v) が得られます。

  4. 2D 座標 (u, v) が正方形内にあるかどうかを確認します (4 つの点が平行四辺形を形成し、ローカル 2D 基底に隣接する 2 つのエッジを選択したと仮定します)。 ）。

実際の方程式では、4 つの正方形の頂点が次のように配置されていると仮定します。

   S1 +------+ S2
      |      |
      |      |
   S3 +------+ S4

  1. 平面の法線: n = (S2 - S1) x (S3 - S1)

    点 M は、この方程式 n を満たす場合、この平面に属します。( M - S1 ) = 0

  2. 点 M は次のように書ける場合、光線に属します: M = R1 + t * dR with dR = R2 - R1

    光線/平面の交点を計算します (前の 2 つの方程式を等しくします)。

    n. ( M - S1 ) = 0 = n . ( R1 + t * dR - S1 ) = n . (R1 - S1) + t * n . dR

    n の場合。dR が 0 の場合、平面は光線に平行であり、交差はありません (ここでも、光線が平面に埋め込まれている場合は無視します)。

    そうでなければ t = -n . (R1 - S1) / n . dR を計算し、この結果を前の式 M = R1 + t * dR に代入すると、交点 M の 3D 座標が得られます。

  3. ベクトル M - S1 を 2 つのベクトル S2 - S1 および S3 - S1 (S1 から始まる正方形のエッジ) に射影すると、2 つの数値 (u, v) が得られます。

    u = (M - S1) . (S2 - S1)

    v = (M - S1) . (S3 - S1)

  4. 0 <= u <= |S2 - S1|^2 かつ 0 <= v <= |S3 - S1|^2 の場合、交点 M は正方形の内側にあり、それ以外の場合は外側にあります。

そして最後に、前の方程式のサンプル Java 実装 (読みやすさのために最適化されています...):

public class Test {
    static class Vector3 {
        public float x, y, z;

        public Vector3(float x, float y, float z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        public Vector3 add(Vector3 other) {
            return new Vector3(x + other.x, y + other.y, z + other.z);
        }

        public Vector3 sub(Vector3 other) {
            return new Vector3(x - other.x, y - other.y, z - other.z);
        }

        public Vector3 scale(float f) {
            return new Vector3(x * f, y * f, z * f);
        }

        public Vector3 cross(Vector3 other) {
            return new Vector3(y * other.z - z * other.y,
                               z - other.x - x * other.z,
                               x - other.y - y * other.x);
        }

        public float dot(Vector3 other) {
            return x * other.x + y * other.y + z * other.z;
        }
    }

    public static boolean intersectRayWithSquare(Vector3 R1, Vector3 R2,
                                                 Vector3 S1, Vector3 S2, Vector3 S3) {
        // 1.
        Vector3 dS21 = S2.sub(S1);
        Vector3 dS31 = S3.sub(S1);
        Vector3 n = dS21.cross(dS31);

        // 2.
        Vector3 dR = R1.sub(R2);

        float ndotdR = n.dot(dR);

        if (Math.abs(ndotdR) < 1e-6f) { // Choose your tolerance
            return false;
        }

        float t = -n.dot(R1.sub(S1)) / ndotdR;
        Vector3 M = R1.add(dR.scale(t));

        // 3.
        Vector3 dMS1 = M.sub(S1);
        float u = dMS1.dot(dS21);
        float v = dMS1.dot(dS31);

        // 4.
        return (u >= 0.0f && u <= dS21.dot(dS21)
             && v >= 0.0f && v <= dS31.dot(dS31));
    }

    public static void main(String... args) {
        Vector3 R1 = new Vector3(0.0f, 0.0f, -1.0f);
        Vector3 R2 = new Vector3(0.0f, 0.0f,  1.0f);

        Vector3 S1 = new Vector3(-1.0f, 1.0f, 0.0f);
        Vector3 S2 = new Vector3( 1.0f, 1.0f, 0.0f);
        Vector3 S3 = new Vector3(-1.0f,-1.0f, 0.0f);

        boolean b = intersectRayWithSquare(R1, R2, S1, S2, S3);
        assert b;

        R1 = new Vector3(1.5f, 1.5f, -1.0f);
        R2 = new Vector3(1.5f, 1.5f,  1.0f);

        b = intersectRayWithSquare(R1, R2, S1, S2, S3);
        assert !b;
    }
}
于 2014-01-14T13:40:27.423 に答える