Line, square intersection algorithm!

[uhraurhua]

Hi I am trying to make an algorithm to find the intersection points between a line and a square. I know the points of the line P1(x1,y1,z1), P2(x2,y2,z2) and the points of the square ABCD, A(xa,ya,za), B(xb,yb,zb) and so on. I would like (if possible) an algorithm that can determine the intersection points (x,y,z) using only the coordinates given. I am still in highschool and we didn't study 3d intersections and I couldn't find a good tutorial so if you could help me that would mean a lot to me! Thank you for taking your time and reading this and I hope I will hear from you soon! Goodbye!

[rollie]

Bleach fan?

I recently had a similar problem...the math is a bit of a pain. I hacked together a solution for my less-general case (my lines were always in the (0,1,0) direction, and my squares were all sorta on the xz plane). Look up tutorials for line-triangle intersection, and just view your square as a pair of triangles. The solution if I recall is to 1) determine if and where the line intersects the plane on which your square (or triangle) resides, then take that intersection point and determine if it's in the triangle. Thinking about it, for a square, it might be even easier. Get the plane/line intersection point (we'll call it ptIntersect; I don't remember the math for it, it's about ~8 operations though). Then do something like:

P1 -= P1; // Obviously, P1 is now (0,0,0)
P2 -= P1;
P3 -= P1;
P4 -= P1;
ptIntersect -= P1;

next, rotate all remaining points (ptIntersect, P2, P3, P4) around the X, Y, and Z axes such that P2 is on the x-axis (y and z both 0). Then rotate all remaining points (ptIntersect, P3, P4) around the x-axis so that they are also on the XZ plane, which means either P3 or P4 winds up on the Z axis, depending on how you are defining your square. Now everything is on the XZ plane, and your problem becomes 2-dimensional - if ptIntersection.x is between P1.x and P2.x, AND ptIntersection.z is between P1.z and P3.z, the original ptIntersect is indeed contained in your square. Else, it isn't.

[Duthomhas]

Actually, a square is more difficult because of precision problems -- without severe restrictions on the domain it is unlikely that the user can enter four points that all lie on the same plane.

But, in any case, this is above high-school math level... Your teacher should know that and have given you an algorithm to do this. Otherwise he is really asking you to prove that you can use the internet to find the answer.

The Moller and Trumbore method is very-well suited to this problem. Here is a site that has both the math and a (slightly difficult to read) code:
http://www.lighthouse3d.com/tutorials/maths/ray-triangle-intersection/

(Try to write you own code. You will have to add the ability to get the intersection point yourself -- using some high-school algebra on the line at point t.)

I would create a struct/class to represent a point:

struct point
  {
  float x, y, z;
  ...
  };

I've got to leave right now. I'll check back later.

[uhraurhua]

We only did 2d geometry in highschool and I need 3d intersections. I tried to find an equation to determine the intersect points but it's either to complicated to solve ( last 1 took me 3 pages and I was just getting strated so I quit) or I couldn't figure it out. Duoas the methos you presented involves vertices and I really don't know how to convert coords to vertices. Also english is my second language so I really don't understand the method used on lighthouse3d. I tried once to use it (several months ago) but I just couldn't figure it out. I am trying to build my own game engine and I am having problems with collision detection. Also rollie I am a bleach fan but my name has nothing to do with bleach it's just randomly typed : ) ( my other names was jhghfjkh). Btw can you please explain what kind of type P1, P2, P3 and P4 are. I mean its obviously they are not int, float or any other usual types. Also I really don't understand your method...

[rollie]

A 'vertex' is simply a corner on a triangle in this case. My variables P1, P2, etc were points, like the definition Duoas gave. The link he gave seems really straightforward - you can just copy and paste their code for what you're writing. Once you get the function working, give it a shot with some sample data. Just for clarification, if you look at the signature:

int rayIntersectsTriangle(float *p, float *d,
			float *v0, float *v1, float *v2)

all of the parameters passed in will be 'float myFloatArray[3]', where the 3 points represent the x, y, and z values of a point. Most implementations I've seen take some form of custom 'point' object, so you could (without too much difficulty) re-write rayIntersectsTriangle to look like

int rayIntersectsTriangle(const point & p, const point & d,
			const point & v0, const point & v1, const point & v2)

with the variables
p - starting point of the ray
d - direction of the ray (you can re-use the point struct for this, though it may more properly be viewed as a vector; nevermind that though)
v0, v1, v2 - the points (aka vertices) that make up the triangle

Give it a shot, see what you can do, post again and you will probably get help resolving any errors you have. Once you have the function working, try:

point p(0,0,0);
point d(0.5f, 0.5f, 0.5f);

point v1(5.0f, 0.0f, 0.0f);
point v2(0.0f, 5.0f, 0.0f);
point v3(0.0f, 0.0f, 5.0f);
point v4(-5.0f, 0.0f, 0.0f);
point v5(0.0f, -5.0f, 0.0f);
point v6(0.0f, 0.0f, -5.0f);

if (rayIntersectsTriangle(p, d, v1, v2, v3)
{
    std::cout << "Ray intersects triangle 1" << std::endl;
}

if (rayIntersectsTriangle(p, d, v4, v5, v6)
{
    std::cout << "Ray intersects triangle 2" << std::endl;
}

Ray should intersect triangle 1, but not 2.

[uhraurhua]

Thank you I will modify the code, make a video of my program and post the link here : )

[uhraurhua]

Oh by the way can someone please tell me how to determine the intersection points using the method here http://www.lighthouse3d.com/tutorials/maths/ray-triangle-intersection/ ? I tried finding them like this x=(1-u-v)*x0+u*x1+v*x2 ,y=(1-u-v)*y0+... and so on where x0, x1, x2, y0, y1, y2...are the coords of p0, p1 and p2. I really don't think that the coords can be found like this....