在3D两个矩形的交集 [英] Intersection between two rectangles in 3D
问题描述
要获得交点两个矩形之间的线3D，我转换他们的飞机，然后利用它们的法线的交叉产品得到交线，然后我试图让与矩形的每条线段的线的交点。
To get the line of intersection between two rectangles in 3D, I converted them to planes, then get the line of intersection using cross product of their normals, then I try to get the line intersection with each line segment of the rectangle.
现在的问题是线平行于三段，和相交只有一个在南，南，南这是完全错误的。你能告诉我什么是错误的，我code？
The problem is the line is parallel to three segments, and intersect with only one in NAN,NAN,NAN which is totally wrong. Can you advise me what's wrong in my code?
我使用Vector3类型从这个链接 http://www.koders.com/csharp/fidCA8558A72AF7D3E654FDAFA402A168B8BC23C22A。 ASPX
I use vector3 from this link http://www.koders.com/csharp/fidCA8558A72AF7D3E654FDAFA402A168B8BC23C22A.aspx
和创建我的飞机类如下
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace referenceLineAlgorithm
{
struct Line
{
public Vector3 direction;
public Vector3 point;
}
struct lineSegment
{
public Vector3 firstPoint;
public Vector3 secondPoint;
}
class plane_test
{
public enum Line3DResult
{
Line3DResult_Parallel = 0,
Line3DResult_SkewNoCross = 1,
Line3DResult_SkewCross = 2
};
#region Fields
public Vector3 Normal;
public float D;
public Vector3[] cornersArray;
public Vector3 FirstPoint;
public Vector3 SecondPoint;
public Vector3 temp;
public Vector3 normalBeforeNormalization;
#endregion
#region constructors
public plane_test(Vector3 point0, Vector3 point1, Vector3 point2, Vector3 point3)
{
Vector3 edge1 = point1 - point0;
Vector3 edge2 = point2 - point0;
Normal = edge1.Cross(edge2);
normalBeforeNormalization = Normal;
Normal.Normalize();
D = -Normal.Dot(point0);
///// Set the Rectangle corners
cornersArray = new Vector3[] { point0, point1, point2, point3 };
}
#endregion
#region Methods
/// <summary>
/// This is a pseudodistance. The sign of the return value is
/// positive if the point is on the positive side of the plane,
/// negative if the point is on the negative side, and zero if the
/// point is on the plane.
/// The absolute value of the return value is the true distance only
/// when the plane normal is a unit length vector.
/// </summary>
/// <param name="point"></param>
/// <returns></returns>
public float GetDistance(Vector3 point)
{
return Normal.Dot(point) + D;
}
public void Intersection(plane_test SecondOne)
{
///////////////////////////// Get the parallel to the line of interrsection (Direction )
Vector3 LineDirection = Normal.Cross(SecondOne.Normal);
float d1 = this.GetDistance(LineDirection);
float d2 = SecondOne.GetDistance(LineDirection);
temp = (LineDirection - (this.Normal * d1) - (SecondOne.Normal * d2));
temp.x = Math.Abs((float)Math.Round((decimal)FirstPoint.x, 2));
temp.y = Math.Abs((float)Math.Round((decimal)FirstPoint.y, 2));
Line line;
line.direction = LineDirection;
line.point = temp;
////////// Line segments
lineSegment AB, BC, CD, DA;
AB.firstPoint = cornersArray[0]; AB.secondPoint = cornersArray[1];
BC.firstPoint = cornersArray[1]; BC.secondPoint = cornersArray[2];
CD.firstPoint = cornersArray[2]; CD.secondPoint = cornersArray[3];
DA.firstPoint = cornersArray[3]; DA.secondPoint = cornersArray[0];
Vector3 r1 = new Vector3(-1, -1, -1);
Vector3 r2 = new Vector3(-1, -1, -1);
Vector3 r3 = new Vector3(-1, -1, -1);
Vector3 r4 = new Vector3(-1, -1, -1);
/*
0,0 |----------------| w,0
| |
| |
0,h |________________| w,h
*/
IntersectionPointBetweenLines(AB, line, ref r1);
IntersectionPointBetweenLines(BC, line, ref r2);
IntersectionPointBetweenLines(CD, line, ref r3);
IntersectionPointBetweenLines(DA, line, ref r4);
List<Vector3> points = new List<Vector3>();
points.Add(r1);
points.Add(r2);
points.Add(r3);
points.Add(r4);
points.RemoveAll(
t => ((t.x == -1) && (t.y == -1) && (t.z == -1))
);
if (points.Count == 2)
{
FirstPoint = points[0];
SecondPoint = points[1];
}
}
public Line3DResult IntersectionPointBetweenLines(lineSegment first, Line aSecondLine, ref Vector3 result)
{
Vector3 p1 = first.firstPoint;
Vector3 n1 = first.secondPoint - first.firstPoint;
Vector3 p2 = aSecondLine.point;
Vector3 n2 = aSecondLine.direction;
bool parallel = AreLinesParallel(first, aSecondLine);
if (parallel)
{
return Line3DResult.Line3DResult_Parallel;
}
else
{
float d = 0, dt = 0, dk = 0;
float t = 0, k = 0;
if (Math.Abs(n1.x * n2.y - n2.x * n1.y) > float.Epsilon)
{
d = n1.x * (-n2.y) - (-n2.x) * n1.y;
dt = (p2.x - p1.x) * (-n2.y) - (p2.y - p1.y) * (-n2.x);
dk = n1.x * (p2.x - p1.x) - n1.y * (p2.y - p1.y);
}
else if (Math.Abs(n1.z * n2.y - n2.z * n1.y) > float.Epsilon)
{
d = n1.z * (-n2.y) - (-n2.z) * n1.y;
dt = (p2.z - p1.z) * (-n2.y) - (p2.y - p1.y) * (-n2.z);
dk = n1.z * (p2.z - p1.z) - n1.y * (p2.y - p1.y);
}
else if (Math.Abs(n1.x * n2.z - n2.x * n1.z) > float.Epsilon)
{
d = n1.x * (-n2.z) - (-n2.x) * n1.z;
dt = (p2.x - p1.x) * (-n2.z) - (p2.z - p1.z) * (-n2.x);
dk = n1.x * (p2.x - p1.x) - n1.z * (p2.z - p1.z);
}
t = dt / d;
k = dk / d;
result = n1 * t + p1;
// Check if the point on the segmaent or not
// if (! isPointOnSegment(first, result))
//{
// result = new Vector3(-1,-1,-1);
// }
return Line3DResult.Line3DResult_SkewCross;
}
}
private bool AreLinesParallel(lineSegment first, Line aSecondLine)
{
Vector3 vector = (first.secondPoint - first.firstPoint);
vector.Normalize();
float kl = 0, km = 0, kn = 0;
if (vector.x != aSecondLine.direction.x)
{
if (vector.x != 0 && aSecondLine.direction.x != 0)
{
kl = vector.x / aSecondLine.direction.x;
}
}
if (vector.y != aSecondLine.direction.y)
{
if (vector.y != 0 && aSecondLine.direction.y != 0)
{
km = vector.y / aSecondLine.direction.y;
}
}
if (vector.z != aSecondLine.direction.z)
{
if (vector.z != 0 && aSecondLine.direction.z != 0)
{
kn = vector.z / aSecondLine.direction.z;
}
}
// both if all are null or all are equal, the lines are parallel
return (kl == km && km == kn);
}
private bool isPointOnSegment(lineSegment segment, Vector3 point)
{
//(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1) = (z - z1) / (z2 - z1)
float component1 = (point.x - segment.firstPoint.x) / (segment.secondPoint.x - segment.firstPoint.x);
float component2 = (point.y - segment.firstPoint.y) / (segment.secondPoint.y - segment.firstPoint.y);
float component3 = (point.z - segment.firstPoint.z) / (segment.secondPoint.z - segment.firstPoint.z);
if ((component1 == component2) && (component2 == component3))
{
return true;
}
else
{
return false;
}
}
#endregion
}
}
static void Main(string[] args)
{
//// create the first plane points
Vector3 point11 =new Vector3(-255.5f, -160.0f,-1.5f) ; //0,0
Vector3 point21 = new Vector3(256.5f, -160.0f, -1.5f); //0,w
Vector3 point31 = new Vector3(256.5f, -160.0f, -513.5f); //h,0
Vector3 point41 = new Vector3(-255.5f, -160.0f, -513.5f); //w,h
plane_test plane1 = new plane_test(point11, point21, point41, point31);
//// create the Second plane points
Vector3 point12 = new Vector3(-201.6289f, -349.6289f, -21.5f);
Vector3 point22 =new Vector3(310.3711f,-349.6289f,-21.5f);
Vector3 point32 = new Vector3(310.3711f, 162.3711f, -21.5f);
Vector3 point42 =new Vector3(-201.6289f,162.3711f,-21.5f);
plane_test plane2 = new plane_test(point12, point22, point42, point32);
plane2.Intersection(plane1);
}
这是测试值 最好的问候
and this is test values Best regards
推荐答案
您需要指定一件事第一：
You need to specify one thing first:
- 将3D矩形，你的意思是在3D平面的平面矩形。 （不是 矩形棱柱）。
- by 3D rectangle, you mean plane rectangle on a 3D plane. (not a rectangular prism).
假设你的矩形不共面平行，也没有，因此，有一个独特的线D1的重新presents每个矩形所描述的平面的交叉点。
Let's say your rectangles are not coplanar nor parallele, and therefore there is one unique line D1 that represents the intersection of the plane described by each rectangle.
鉴于这种假设其是为2矩形R1和R2的交叉点4可能的情形：
Given this assumption their are 4 possible situations for the intersection of 2 rectangles R1 and R2:
（注：有时D1不相交既不R1也R2和R1，R2可以旋转一点点让D1并不总是相交的平行上的两侧，但连续的两侧）
(note: sometimes D1 doesn't intersect neither R1 nor R2 and R1 , R2 can be rotated a little bit so D1 doesn't always intersect on parallele sides, but consecutive sides)
当有2个矩形之间的交点时，D1总是相交R1和R2在同一交叉点（参见第一和第二图像）
When there is an intersection between the 2 rectangles, D1 always intersect R1 and R2 on the same intersection (cf 1st and 2nd picture)
您模式是不好的，因为你的线不能平行同一个矩形的3段...
Your model is not good because your line cannot be parallele to 3 segments of the same rectangle...
正如你在这个问题问： 3D线交会算法一旦你有D1（<一href="http://stackoverflow.com/questions/6993462/algorithm-to-get-the-line-of-two-planes-intersection">Algorithm以获得的两个平面相交中的线）刚刚确定的交点与矩形的各段。（各矩形的4个段需要检查）
As you asked in this question : 3D lines intersection algorithm once you have D1 ( Algorithm to get the line of two planes intersection ) just determinate the intersection with each segment of the rectangle.(The 4 segments of each rectangles need to be checked)
然后检查公共交集......如果你找到一个那么你的矩形相交。
Then check for common intersection... if you find one then your rectangles intersect.
对不起这是很难直接检查code，但我想用这些信息撕成小块，你应该能够找到错误。
Sorry it's very hard to directly check the code, but I guess with these peaces of information you should be able to find the error.
希望它帮助。
编辑：
限定由一个点的矩形和2矢量：
define a rectangle by a point and 2 vectors :
R2 {A ,u ,v}
R1 {B, u',v'}
限定由R1和R2中所述的平面：P1和P2
define the planes described by R1 and R2 : P1 and P2
一个正交向量P1（相应地，P2）是N1（相应地，N2）。让 N1 = U ^ V 和 N2 = U用^ V
One orthogonal vector to P1(resp. P2) is n1 (resp. n2).Let n1 = u ^ v and n2 = u' ^ v' with :
然后
P1: n1.(x-xA,y-yA,z-zA)=0
P2: n2.(x-xB,y-yB,z-zB)=0
然后，如果你只是在寻找D1 D1的公式是：
Then if you're just looking for D1 the equation of D1 is :
D1: P1^2 + P2 ^2 =0 (x,y,z verify P1 =0 an P2 =0 )
D1 : n1.(x-xA,y-yA,z-zA)^2 + n2.(x-xB,y-yB,z-zB)^2 =0
（所以只要你的矩形的前pression你可以得到D1与封闭公式公式。）
(so just with the expression of your rectangles you can get the equation of D1 with a closed formula.)
现在让我们来看看十字路口：
Now let's look at the intersections :
4点R1是：
{A，A + U，A + V，A + U + V}
{ A , A+u , A+v, A+u+v }
作为描述 3D线交会算法做的：
D1 inter [A,A+u] = I1
D1 inter [A,A+v] = I2
D1 inter [A+u,A+u+v] = I3
D1 inter [A+v,A+u+v] = I4
（I1，I2，I3，I4可以为null）
(I1,I2,I3,I4 can be null)
same for D2 you get I1' I2' I3' I4'
如果IJ'= IK'！= null，则它是一个交叉点
如果你没有一步是正确的一步，你应该得到正确的解决方案;除非我没有完全理解这个问题...
if you did that correctly step by step you should get to the correct solution; unless I didn't fully understand the question...
这篇关于在3D两个矩形的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
