Intersection between two line3ds

Rayne · Post by **Rayne** » Sun May 30, 2004 7:06 pm

Hey,

does anyone have an idea on how to check if two line3ds intersect? That is, if there is an intersection, if it is between the start and end points of both lines?

Rayne · Post by **Rayne** » Mon May 31, 2004 9:43 pm

*bump*

Rayne · Post by **Rayne** » Wed Jun 02, 2004 12:37 am

c'mon folks, I thought I was asking for basic math stuff here, not the world formula...

LittleGiant · Post by **LittleGiant** » Wed Jun 02, 2004 1:58 am

First off as you'll read in the link 3d lines intersecting is extremely rare, and in some cases impossible because of floating point inaccuraccy.

Anyways you probably want to find the shortest distance between the two lines, check if thats within your colision threashold(is closer then 0.1 = an intersection) .

Here is some help with the math aspect

yin nadie · Post by **yin nadie** » Wed Jun 02, 2004 8:58 am

Why would you want to use ray-ray intersection in a 3d environment anyway? (just asking, i can't imagine a situation here'n'now in which a game would need it

Tyn · Post by **Tyn** » Wed Jun 02, 2004 9:19 am

Working out the point of intersection of two lines ( doesn't matter that they are in a program ) is not basic math. I have seen it before, however that was in degree standard Math that my bro was doing for his course in Uni. My suggestion is to read around on the net for it because I don't have the books here any more to do it.

Rayne · Post by **Rayne** » Thu Jun 03, 2004 1:20 pm

My Game runs on a flat plane anyway, y is always 0. So an intersection of two line3ds IS a realistic scenario.

I want to use the intersections for collision detection. The included collision detection is not what I was looking for in my special case, so I wrote my own. However, calculating the collision of two very fast moving objects proved to be difficult. Thats why I came up with lines that show where the Node was last frame and where it is now. If the lines intersect, the nodes collided.

I came up with my own algorithm to detect if they intersect or not. Principle of exclusion.
1. Make a Plane out of the two points of the first line and one point of the second. Does the other point of the second line lie on the plane? If not, they cannot intersect (redundand in my case since all lines are planar, but oh well)
2. Take the first line and turn it into an axis (i.e. make it infinitely long). Take the start and end points and get the vectors from the closest point on the axis to the point, then normalize them. If they point in the same direction, the lines cannot intersect, as the second line would be entirely on one side of the first line.
3. Take the four points of the two lines and make a quadrangle outta them. if one of the inner angles is >180, the lines cannot intersect.
4. We're here? Then the lines intersect.

And now for the crazy stuff: it actually works.

yin nadie · Post by **yin nadie** » Thu Jun 03, 2004 3:06 pm

oh, well. the ray-ray intersection in a 2d world is a completaly different question, and a really important one, since is the correct way to make a character collide ith the walls and floor in a 2d environment.

Obvously two rays in a plane will always intersect, except when they are paralel rays, of course.

in order to calculate the intersecition point, the procedure is exactly the same as when calculating ray-polygon intersection:

The data:

pOrigin: a pont in the 'wall'
pNormal: a vector normal to the 'wall'

pOrigin: a point of the trajectory
rOrigin: vector of the trajectory

the proccess:

D = dotProduct(pOrigin, pNormal)
a = dotProduct(pNormal, rOrigin) + D;
b = dotProduct(pNormal, rNormal);
time -(a / b);

if time is between 0 and 1, the collision point is between pOrigin and pOrigin+rOrigin. (The actual collision point is pOrigin + time * rOrigin)

that's what i remember of all this

[dx/x]=HUNT3R · Post by **[dx/x]=HUNT3R** » Thu Jun 03, 2004 4:05 pm

There are much more accurate ways to find the intersection of 2 lines in a plane i.e. you could use Cramer's Rule which requires some linear algebra skill or you could just do some simple algebra:

1. Get the equation of each line in point-slope form: y = mx + b. This may require you to find the slope but if you have 2 points on the line then slope is just m = (y2 - y1)/(x2 - x1). b is the y intercept and if you know x, y, and m then b is easy to solve for.

2. Set the 2 equations equal to each other like so: m1x1 + b1 = m2x2 + b2 and solve for x.

3. Take what you get for x and plug it back into either one of the original equations to solve for y. Done.

yin nadie · Post by **yin nadie** » Thu Jun 03, 2004 4:49 pm

i think i allowed the 'bad algebra' to confound me. [dx/x]=HUNT3R is right. His solution is much better

Rayne · Post by **Rayne** » Thu Jun 03, 2004 11:17 pm

yes i stumbled upon cramers solution later anyway. i didnt look for ray-ray intersection, but line-line (i.e. startpoint endpoint startpoint endpoint). however, that can also be done by turning the lines into rays, checking for the colliding point, then checking if that point is on both lines.

oh well, the problem is solved.