C ++中Ray和Rectangle的交集(Intersection of Ray and Rectangle in C++)

C ++中Ray和Rectangle的交集(Intersection of Ray and Rectangle in C++)

我需要光线和矩形之间的交集。 到目前为止，我已经按照这里的答案，但经过测试（如下所述），我意识到实施是错误的。

bool checkRayLightIntersection(Vec Origin, Vec Dir) { //(-10,20,9) is Hard-code of the light position and we add (5.0f) on X and Z axis to //make it an area instead of a vertex //"Origin" is the position of the eye. Hard coded: (-25, 8, 5) //"Dir" is LightPosition - Origin float randX = 5.0f; //in the future it will be random, that's why this name float randZ = 5.0f; Vec P1 = Vec(-10 - randX, 20, 9 + randZ); Vec P2 = Vec(-10 + randX, 20, 9 + randZ); Vec P3 = Vec(-10 + randX, 20, 9 - randZ); Vec P4 = Vec(-10 - randX, 20, 9 - randZ); //the majority of the methods first find out where the ray intersects the //plane that the rectangle lies on, Ax + By + Cz + D = 0 //in our case the equation of that plane is easy (I think) -> D = 20 float t = -(-Origin.y + 20) / (-Dir.y); if (t > 0) { Vec hitPoint = Origin + Dir * t; Vec V1 = (P2 - P1).norm(); Vec V3 = (P4 - P3).norm(); Vec V4 = (hitPoint - P1).norm(); Vec V5 = (hitPoint - P3).norm(); float V1dotV4 = V1.dot(V4); float V3dotV5 = V3.dot(V5); if (V1dotV4 > 0 && V3dotV5 > 0) { return true; } } return false; }

我的Vec是一个定义如下的结构：

struct Vec { double x, y, z; // position, also color (r,g,b) Vec(double x_ = 0, double y_ = 0, double z_ = 0){ x = x_; y = y_; z = z_; } Vec operator+(const Vec &b) const { return Vec(x + b.x, y + b.y, z + b.z); } Vec operator-(const Vec &b) const { return Vec(x - b.x, y - b.y, z - b.z); } Vec operator-() const { return Vec(-x, -y, -z); } Vec operator*(double b) const { return Vec(x*b, y*b, z*b); } Vec operator/(double b) const { return Vec(x / b, y / b, z / b); } Vec mult(const Vec &b) const { return Vec(x*b.x, y*b.y, z*b.z); } Vec& norm(){ return *this = *this * (1 / sqrtf(x*x + y*y + z*z)); } double dot(const Vec &b) const { return x*b.x + y*b.y + z*b.z; } // cross: Vec operator%(Vec&b){ return Vec(y*b.z - z*b.y, z*b.x - x*b.z, x*b.y - y*b.x); } double max() const { return x>y && x>z ? x : y > z ? y : z; } };

我测试了这个方法。 所以我试着做的是从我的Origin创建一个光线到一个应该在Rectangle之外的点，如（-10,20,19），我在Z轴上加9，而矩形应该只有5个单位在每个方向（X，-X，Z，-Z）。 所以在我的情况下：

Dir = (-10, 20, 19) - Orig

相反，该方法返回true，它应该返回false。 你能帮我理解我做错了什么吗？ 提前致谢。

I need the intersection between a ray and a rectangle. So far I have followed the answer here, but after testing it (as explained below) I realized that the implementation is wrong.

bool checkRayLightIntersection(Vec Origin, Vec Dir) { //(-10,20,9) is Hard-code of the light position and we add (5.0f) on X and Z axis to //make it an area instead of a vertex //"Origin" is the position of the eye. Hard coded: (-25, 8, 5) //"Dir" is LightPosition - Origin float randX = 5.0f; //in the future it will be random, that's why this name float randZ = 5.0f; Vec P1 = Vec(-10 - randX, 20, 9 + randZ); Vec P2 = Vec(-10 + randX, 20, 9 + randZ); Vec P3 = Vec(-10 + randX, 20, 9 - randZ); Vec P4 = Vec(-10 - randX, 20, 9 - randZ); //the majority of the methods first find out where the ray intersects the //plane that the rectangle lies on, Ax + By + Cz + D = 0 //in our case the equation of that plane is easy (I think) -> D = 20 float t = -(-Origin.y + 20) / (-Dir.y); if (t > 0) { Vec hitPoint = Origin + Dir * t; Vec V1 = (P2 - P1).norm(); Vec V3 = (P4 - P3).norm(); Vec V4 = (hitPoint - P1).norm(); Vec V5 = (hitPoint - P3).norm(); float V1dotV4 = V1.dot(V4); float V3dotV5 = V3.dot(V5); if (V1dotV4 > 0 && V3dotV5 > 0) { return true; } } return false; }

My Vec is a struct defined as follows:

struct Vec { double x, y, z; // position, also color (r,g,b) Vec(double x_ = 0, double y_ = 0, double z_ = 0){ x = x_; y = y_; z = z_; } Vec operator+(const Vec &b) const { return Vec(x + b.x, y + b.y, z + b.z); } Vec operator-(const Vec &b) const { return Vec(x - b.x, y - b.y, z - b.z); } Vec operator-() const { return Vec(-x, -y, -z); } Vec operator*(double b) const { return Vec(x*b, y*b, z*b); } Vec operator/(double b) const { return Vec(x / b, y / b, z / b); } Vec mult(const Vec &b) const { return Vec(x*b.x, y*b.y, z*b.z); } Vec& norm(){ return *this = *this * (1 / sqrtf(x*x + y*y + z*z)); } double dot(const Vec &b) const { return x*b.x + y*b.y + z*b.z; } // cross: Vec operator%(Vec&b){ return Vec(y*b.z - z*b.y, z*b.x - x*b.z, x*b.y - y*b.x); } double max() const { return x>y && x>z ? x : y > z ? y : z; } };

I tested the method. So what I tried to do is creating a ray from my Origin to a point that should be outside the Rectangle such as (-10, 20, 19), I added 9 to the Z-axis while the rectangle should be only 5 units larger in each direction (X,-X,Z,-Z). Therefore in my case:

Dir = (-10, 20, 19) - Orig

The method returns true when instead it should return false. Can you please help me understand what I am doing wrong? Thanks in advance.

最满意答案

看起来你离这里很近，但我很好奇你获得了V1dotV4和V3dotV5 。

也就是说，看起来你正在解决t因为你的平面方程出现-y + 20 = 0（即y = 20的平面，正常[0，-1,0]）。

您可以通过将其插回到飞机的等式并检查结果为0来验证您是否获得了合理的hitPoint 。

假设hitPoint在飞机上正确，看起来你检查hitPoint在矩形内部是错误的。 您正在使用点积来确保hitPoint到边缘[P1，P2]和[P4，P3]的投影位于该边缘内。 问题是[P1，P2]和[P4，P3]是矩形的相对/平行边缘，因此您的检查不会告诉您任何关于hitPoint相对于边缘[P2，P3]和[P4，P1]的信息]。

既然你知道这是一个矩形，我认为应该足够计算

Vec hitPoint = Origin + Dir * t; Vec V1 = (P2 - P1).norm(); Vec V2 = (P3 - P2).norm(); Vec V3 = (P4 - P3).norm(); Vec V4 = (P1 - P4).norm(); Vec V5 = (hitPoint - P1).norm(); Vec V6 = (hitPoint - P2).norm(); Vec V7 = (hitPoint - P3).norm(); Vec V8 = (hitPoint - P4).norm(); if (V1.dot(V5) < 0.0) return false; if (V2.dot(V6) < 0.0) return false; if (V3.dot(V7) < 0.0) return false; if (V4.dot(V8) < 0.0) return false; return true;

编辑我的初始断言是检查两个边的范围为[0,1]，但这实际上并不正确。 更新了示例代码以检查所有4个边缘。

另一个注意事项您可以通过检查hitPoint与矩形的两个垂直边缘来实现此目的

Vec hitPoint = Origin + Dir * t; Vec V1 = P2 - P1; float lengthV1 = V1.length(); Vec normV1 = V1.norm(); Vec V2 = P4 - P1; float lengthV2 = V2.length(); Vec normV2 = V2.norm(); Vec hitVec = P - P1; a = normV1.dot(hitVec); b = normV2.dot(hitVec); return (0.0f <= a && a <= lengthV1 && 0.0f <= b && b <= lengthV2);

It looks like you are pretty close here, but I'd be curious what results you get for V1dotV4 and V3dotV5.

That said, it looks like you are correctly solving for t since your plane equation comes out to -y + 20 = 0 (i.e. a flat plane at y = 20 with normal [0, -1, 0]).

You can verify that you got a reasonable hitPoint by plugging it back into the equation for your plane and checking that the result is 0.

Assuming hitPoint is correctly on the plane, it looks like your check that hitPoint is inside the rectangle is wrong. You are using the dot product to ensure that the projection of hitPoint onto the edges [P1,P2] and [P4,P3] lies inside that edge. The issue is that [P1,P2] and [P4,P3] are opposite/parallel edges of the rectangle, so your check doesn't tell you anything about where hitPoint is relative to edges [P2,P3] and [P4,P1].

Since you know this is a rectangle, I think it should be sufficient to compute

Vec hitPoint = Origin + Dir * t; Vec V1 = (P2 - P1).norm(); Vec V2 = (P3 - P2).norm(); Vec V3 = (P4 - P3).norm(); Vec V4 = (P1 - P4).norm(); Vec V5 = (hitPoint - P1).norm(); Vec V6 = (hitPoint - P2).norm(); Vec V7 = (hitPoint - P3).norm(); Vec V8 = (hitPoint - P4).norm(); if (V1.dot(V5) < 0.0) return false; if (V2.dot(V6) < 0.0) return false; if (V3.dot(V7) < 0.0) return false; if (V4.dot(V8) < 0.0) return false; return true;

Edit My initial assertion was to check two edges for a range of [0,1], but this isn't actually correct. Updated the example code to check all 4 edges.

Another Note You can do this by checking hitPoint against just two perpendicular edges of the rectangle by

Vec hitPoint = Origin + Dir * t; Vec V1 = P2 - P1; float lengthV1 = V1.length(); Vec normV1 = V1.norm(); Vec V2 = P4 - P1; float lengthV2 = V2.length(); Vec normV2 = V2.norm(); Vec hitVec = P - P1; a = normV1.dot(hitVec); b = normV2.dot(hitVec); return (0.0f <= a && a <= lengthV1 && 0.0f <= b && b <= lengthV2);