java中的3D Ray-Quad相交测试 [英] 3D Ray-Quad intersection test in java
问题描述
在 3D 空间中，我试图确定一条射线/线是否与正方形相交，如果是，则确定它相交的正方形上的 x 和 y 位置.
In 3D space I am trying to determine if a ray/line intersects a square and if so, the x and y position on the square that it intersects.
我有一条由两点表示的射线:
I have a ray represented by two points:
R1 = (Rx1, Ry1, Rz1) and
R2 = (Rx2, Ry2, Rz2)
而正方形由四个顶点表示:
And the square is represented by four vertices:
S1 = (Sx1, Sy1, Sz1),
S2 = (Sx2, Sy2, Sz2),
S3 = (Sx3, Sy3, Sz3) and
S4 = (Sx4, Sy4, Sz4).
我在网上找到了很多代数方程，但似乎没有一个完全适合这个问题.理想情况下，我想要 Java 代码中的答案，但我可以轻松转换为代码的等式也可以.
I’ve found lots of algebraic equations for this online but none seem to fit this problem exactly. Ideally I would like the answer in Java code, but an equation that I can easily convert to code will do also.
我们将不胜感激.
推荐答案
以下是解决方案的概述:
Here is an overview of the solution:
计算正方形的平面方程(假设四点共面)，
Compute the plane equation of the square (assuming the four points are coplanar),
做一个射线/平面相交，这会给你任何东西(射线平行于正方形，我忽略射线嵌入平面的情况)或一个点，
Do a ray / plane intersection, this gives you either nothing (ray parallel to the square and I ignore the case where the ray is embedded in the plane) or a point,
一旦你有了交点，把它投影到正方形平面上的局部二维基础上，这将给出平面上点的二维坐标(u，v)，
Once you have the intersection point, project it on a local 2D basis in the plane of the square, this will give the 2D coordinates (u, v) of the point on the plane,
检查二维坐标 (u, v) 是否在正方形内(假设四个点形成一个平行四边形，并且您选择了两个相邻边作为局部二维基础)，如果是，则有交集(并且您有 u/v 坐标).
Check whether the 2D coordinates (u, v) are within the square (assuming the four points form a parallelogram and you chose two adjacent edges for the local 2D basis), if yes then there is intersection (and you have the u/v coordinates).
现在有了实际方程，假设四个正方形顶点放置如下:
Now with actual equations, assuming the four square vertices are placed as follows:
S1 +------+ S2
| |
| |
S3 +------+ S4
平面的法线是:n = (S2 - S1) x (S3 - S1)
The normal to the plane is: n = (S2 - S1) x (S3 - S1)
一个点 M 属于这个平面，如果它满足这个方程: n .( M - S1 ) = 0
A point M belongs to this plane iff it satisfies this equation: n . ( M - S1 ) = 0
点 M 属于射线，如果它可以写成:M = R1 + t * dR，其中 dR = R2 - R1
A point M belongs to the ray iff it can be written: M = R1 + t * dR with dR = R2 - R1
计算射线/平面的交点(等同于前面的两个方程):
Compute the ray / plane intersection (equate the two previous equations):
n.( M - S1 ) = 0 = n .( R1 + t * dR - S1 ) = n .(R1 - S1) + t * n .dR
n . ( M - S1 ) = 0 = n . ( R1 + t * dR - S1 ) = n . (R1 - S1) + t * n . dR
如果 n .dR为0则平面与光线平行，没有交点(再次忽略光线嵌入平面的情况)
If n . dR is 0 then the plane is parallel to the ray, and there is no intersection (again, ignoring the case where the ray is embedded in the plane).
否则 t = -n .(R1 - S1)/n .dR 并将这个结果代入前面的方程 M = R1 + t * dR 给出交点 M 的 3D 坐标.
Else t = -n . (R1 - S1) / n . dR and plugging this result into the previous equation M = R1 + t * dR gives the 3D coordinates of the point of intersection M.
将向量 M - S1 投影到两个向量 S2 - S1 和 S3 - S1(从 S1 开始的方形边)，得到两个数字 (u, v):
Project the vector M - S1 onto the two vectors S2 - S1 and S3 - S1 (the square edges starting from S1), this gives two numbers (u, v):
u = (M - S1) .(S2 - S1)
u = (M - S1) . (S2 - S1)
v = (M - S1) .(S3 - S1)
v = (M - S1) . (S3 - S1)
如果 0 <= u <= |S2 - S1|^2 且 0 <= v <= |S3 - S1|^2，则交点 M 位于正方形内，否则它在外面.
If 0 <= u <= |S2 - S1|^2 and 0 <= v <= |S3 - S1|^2, then the point of intersection M lies inside the square, else it's outside.
最后是前面等式的示例 Java 实现(为便于阅读而优化...):
And finally a sample Java implementation of the previous equations (optimized for reading ease...):
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;
}
}
这篇关于java中的3D Ray-Quad相交测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
