C++ 3D 线段和平面交点

3D Line Segment and Plane Intersection

提问by kbirk

I'm trying to implement a line segment and plane intersection test that will return true or false depending on whether or not it intersects the plane. It also will return the contact point on the plane where the line intersects, if the line does not intersect, the function should still return the intersection point had the line segmenent had been a ray. I used the information and code from Christer Ericson's Real-time Collision Detection but I don't think im implementing it correctly.

我正在尝试实现一个线段和平面相交测试，该测试将根据它是否与平面相交而返回 true 或 false。它还将返回线相交平面上的接触点，如果线不相交，则该函数仍应返回线段为射线的交点。我使用了 Christer Ericson 的实时碰撞检测中的信息和代码，但我认为我没有正确实现它。

The plane im using is derived from the normal and vertice of a triangle. Finding the location of intersection on the plane is what i want, regardless of whether or not it is located on the triangle i used to derive the plane.

im 使用的平面来自三角形的法线和顶点。找到平面上的交点位置是我想要的，无论它是否位于我用来导出平面的三角形上。

The parameters of the function are as follows:

该函数的参数如下：

contact = the contact point on the plane, this is what i want calculated
ray = B - A, simply the line from A to B
rayOrigin = A, the origin of the line segement
normal = normal of the plane (normal of a triangle)
coord = a point on the plane (vertice of a triangle)

Here's the code im using:

这是我使用的代码：

bool linePlaneIntersection(Vector& contact, Vector ray, Vector rayOrigin, Vector normal, Vector coord) {

    // calculate plane
    float d = Dot(normal, coord);

    if (Dot(normal, ray)) {
        return false; // avoid divide by zero
    }

    // Compute the t value for the directed line ray intersecting the plane
    float t = (d - Dot(normal, rayOrigin)) / Dot(normal, ray);

    // scale the ray by t
    Vector newRay = ray * t;

    // calc contact point
    contact = rayOrigin + newRay;

    if (t >= 0.0f && t <= 1.0f) {
        return true; // line intersects plane
    }
    return false; // line does not
}

In my tests, it never returns true... any ideas?

在我的测试中，它永远不会返回 true ......有什么想法吗？

采纳答案by templatetypedef

I could be wrong about this, but there are a few spots in the code that seem very suspicious. To begin, consider this line:

我可能是错的，但代码中有一些地方看起来很可疑。首先，考虑这一行：

// calculate plane
float d = Dot(normal, coord);

Here, your value dcorresponds to the dot product between the plane normal (a vector) and a point in space (a point on the plane). This seems wrong. In particular, if you have any plane passing through the origin and use the origin as the coordinate point, you will end up computing

在这里，您的值d对应于平面法线（向量）和空间中的点（平面上的点）之间的点积。这似乎是错误的。特别是，如果您有任何平面通过原点并以原点作为坐标点，您将最终计算

d = Dot(normal, (0, 0, 0)) = 0

And immediately returning false. I'm not sure what you intended to do here, but I'm pretty sure that this isn't what you meant.

并立即返回false。我不确定你在这里打算做什么，但我很确定这不是你的意思。

Another spot in the code that seems suspicious is this line:

代码中另一个看起来可疑的地方是这一行：

// Compute the t value for the directed line ray intersecting the plane
float t = (d - Dot(normal, rayOrigin)) / Dot(normal, ray);

Note that you're computing the dot product between the plane's normal vector (a vector) and the ray's origin point (a point in space). This seems weird because it means that depending on where the ray originates in space, the scaling factor you use for the ray changes. I would suggest looking at this code one more time to see if this is really what you meant.

请注意，您正在计算平面法向量（向量）和射线原点（空间中的一个点）之间的点积。这看起来很奇怪，因为这意味着根据光线在空间中的起源位置，您用于光线的比例因子会发生变化。我建议再看一遍这段代码，看看这是否真的是你的意思。

Hope this helps!

希望这可以帮助！

回答by Jomi

I am answering this because it came up first on Google when asked for a c++ example of ray intersection :)

我回答这个是因为当被要求提供光线交叉的 C++ 示例时，它首先出现在 Google 上:)

The code always returns false because you enter the if here :

代码总是返回 false，因为您在此处输入 if：

if (Dot(normal, ray)) {
   return false; // avoid divide by zero
}

And a dot product is only zero if the vectors are perpendicular, which is the case you want to avoid (no intersection), and non-zero numbers are true in C.
Thus the solution is to negate ( ! ) or do Dot(...) == 0.
In all other cases there will be an intersection.

如果向量垂直，则点积仅为零，这是您想要避免的情况（无交集），并且非零数字在 C 中为真。
因此，解决方案是否定 ( ! ) 或 Dot(. ..) == 0。
在所有其他情况下都会有交集。

On to the intersection computation : All points Xof a plane follow the equation

关于交点计算：平面的所有点X都遵循方程

Dot(N, X) = d

点（N，X）= d

Where Nis the normal and dcan be found by putting a known point of the plane in the equation.

其中N是法线，d可以通过将平面的已知点放入方程中来找到。

float d = Dot(normal, coord);

Onto the ray, all points sof a line can be expressed as a point pand a vector giving the direction D:

在射线上，一条直线上的所有点s都可以表示为一个点p和一个指向D的向量：

s = p + x*D

s = p + x*D

So if we search for which x sis in the plane, we have

所以如果我们搜索哪个xs在平面上，我们有

Dot(N, s) = d
Dot(N, p + x*D) = d

点(N, s) = d
点(N, p + x*D) = d

The dot product a.bis transpose(a)*b.
Let transpose(N)be Nt.

点积ab是transpose(a)*b。
令transpose(N)为Nt。

Nt*(p + x*D) = d
Nt*p + Nt*D*x = d(x scalar)
x = (d - Nt*p) / (Nt*D)
x = (d - Dot(N, p)) / Dot(N, D)

Nt*(p + x*D) = d
Nt*p + Nt*D*x = d (x 标量)
x = (d - Nt*p) / (Nt*D)
x = (d - Dot(N, p)) / 点（N，D）

Which gives us :

这给了我们：

float x = (d - Dot(normal, rayOrigin)) / Dot(normal, ray);

我们现在可以通过放置来获得交点 x线性方程中的x

s = p + x*D

s = p + x*D

Vector intersection = rayOrigin + x*ray;

上面的代码更新了：

bool linePlaneIntersection(Vector& contact, Vector ray, Vector rayOrigin, 
                           Vector normal, Vector coord) {
    // get d value
    float d = Dot(normal, coord);

    if (Dot(normal, ray) == 0) {
        return false; // No intersection, the line is parallel to the plane
    }

    // Compute the X value for the directed line ray intersecting the plane
    float x = (d - Dot(normal, rayOrigin)) / Dot(normal, ray);

    // output contact point
    *contact = rayOrigin + normalize(ray)*x; //Make sure your ray vector is normalized
    return true;
}

Aside 1:旁白1：


What does the dvalue mean ?什么是d值是什么意思？


对于两个向量a一和bb点积实际上返回一个向量在另一个向量上的正交投影的长度。


但是如果aa被归一化（长度 = 1），Dot(a, b)Dot(a, b)是投影的长度bb上a一个。如果是我们的飞机，dd给了我们平面上所有点在法线方向到原点的方向距离（aa是正常的）。然后我们可以通过比较法线（点积）上投影的长度来得到一个点是否在这个平面上。





Aside 2:旁白2：


How to check if a ray intersects a triangle ? (Used for raytracing)如何检查射线是否与三角形相交？（用于光线追踪）


为了测试光线是否进入由 3 个顶点给出的三角形，您首先必须执行此处显示的操作，获得与三角形形成的平面的交点。


下一步是看这个点是否在三角形内。这可以使用重心坐标来实现，重心坐标将平面中的一个点表示为其中三个点的组合。看Barycentric Coordinates and converting from Cartesian coordinates重心坐标和从笛卡尔坐标转换

回答by Keith

This all looks fine to me. I've independently checked the algebra and this looks fine for me.

这一切对我来说都很好。我已经独立检查了代数，这对我来说很好。

As an example test case:

作为示例测试用例：

A = (0,0,1)
B = (0,0,-1)
coord = (0,0,0)
normal = (0,0,1)

This gives:

这给出：

d = Dot( (0,0,1), (0,0,0)) = 0
Dot( (0,0,1), (0,0,-2)) = -2 // so trap for the line being in the plane passes.
t = (0 - Dot( (0,0,1), (0,0,1) ) / Dot( (0,0,1), (0,0,-2)) = ( 0 - 1) / -2 = 1/2
contact = (0,0,1) + 1/2 (0,0,-2) = (0,0,0) // as expected.

So given the emendation following @templatetypedef's answer, the only area where I can see a problem is with the implementation of one of the other operations, be it Dot(), or the Vectoroperators.

因此，考虑到@templatetypedef 的答案之后的修正，我能看到问题的唯一领域是其他操作之一的实现，无论是它Dot()还是Vector运算符。