Find where 2 line segments intersect from coordinates

[annikk.exe]

I'm working from this page: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2

Excellent article, that.. :>


So this is actually a 5 part problem that deals with the generation of pseudovertices.

The first part of the problem is developing a structure of for loops that will correctly addess all of the edges to look for potential pseudovertices.
function GeneratePseudovertices()


The second part of the problem is to work out if the selected edge intersects with the compared edge in 2D, and what the 2D intersection coordinates are (pseudovertices are in 2D!)
function Intersect2D()


The third part of the problem is to calculate the point where a line drawn from the camera intersects with the line 1 from part 2, and where it intersects with line 2 from part 2.
function Intersect3D()


The fourth part of the problem is to determine which intersection point we found in part 3 is further from the camera; the line that is furthest from the camera will have the pseudovertex added (potentially).
function Intersect3D() (I'll include both part 3 and part 4 in this function)


The fifth part of the problem is to work out whether this newly calculated pseudovertex is behind anything.  If it's not behind anything, a pseudovertex is created for that edge.
function IsBehindAFace()

[annikk.exe]

Parts 2-5 are distinct problems that can be generalised fairly easily.

I'll look at part 3/4 first since I've already convincingly solved part 2 several times over..


The third part of the problem is to calculate the point where a line drawn from the camera intersects with the line 1 from part 2, and where it intersects with line 2 from part 2.
The fourth part of the problem is to determine which intersection point we found in part 3 is further from the camera; the line that is furthest from the camera will have the pseudovertex added (potentially).

Code: [Select]

function Intersect3D(x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4)

camX = GetCameraX()
camY = GetCameraY()
camZ = CameraZ -- this is a custom function of mine..
i3dX = intersectX -- the 2D intersection coordinate from step 2
i3dY = intersectY
i3dZ = 0 -- 2D leveldraw coordinates can expressed in 3D simply by adding Z = 0, the flat plane that is the game screen.

-- So where does the line defined by (camX, camY, camZ) (i3dX, i3dY, i3dZ) intersect with (x1, y1, z1) (x2, y2, z2) ?
-- First calculate camdx, camdy, camdz
camdx = camX - i3dX
camdy = camY - i3dY
camdz = camZ - i3dZ

-- Then calculate dx, dy, dz
dx = x2 - x1
dy = y2 - y1
dz = z2 - z1

-- Define line 1 to contain point (camX,camY,camZ) with vector (camdx,camdy,camdz).
-- Define line 2 to contain point (x1,y1,z1) with vector (dx, dy, dz).


(Need help with this!)

[annikk.exe]

Hmm, how about something like this:

Code: [Select]

if LinesIntersect(x1,y1,x2,y2) then
-- XY intersection detected, i3Dx and i3Dy calculated by this function

if LinesIntersect(x1,z1,x2,z2) then
-- XZ intersection detected, i3Dz calculated by this function

-- lines intersect in 3D.  i3Dx, i3Dy and i3Dz are the coordinates of the intersection

IE, check where they intersect in the XY plane, then check where they intersect in the XZ plane, and use the results as the intersection point.

Would that work?

[annikk.exe]

I'm rapidly becoming convinced this is the way to do it..  I can visualise how it works in my head now..

[Pilchard123]

So let me get this straight...

You have two (potentially skew - they may not intersect in 3D space) lines L1-3 and L2-3 in 3D space.
These are projected onto a 2D plane (the screen) to give lines L1-2 and L2-2.
You want to know the point (X,Y) where the two projected lines intersect on the plane.

After finding this information, you want to know which of the 3D-space lines is closer to the camera at the point. If these lines L1-3 and L2-3 are skew they will pass through the points (X,Y,Z1) and (X,Y, Z2) respectively. You need to find which of the values Z1 and Z2 is smallest, as the smaller value will mean the line is closer to the camera at that point. If Z1 == Z2, then the lines intersect in 3D space and (I think) this will pose no problem.

Am I right, or have I missed something somewhere?

[annikk.exe]

So let me get this straight...

You have two (potentially skew - they may not intersect in 3D space) lines L1-3 and L2-3 in 3D space.

It's not "potentially"... they _definitely_ intersect.  There will never be a case where these lines do not intersect.  They can also never be parallel. This can be made an assumption in the maths used.

Also I'd probably call them L1-2, and L3-4.  Where 1 and 2 are coordinates forming line L1-2, and 3 and 4 and two other coordinates that define line L3-4.

L1-2 and L3-4 definitely intersect.

Also note that these are lines rather than line segments.  :>

These are projected onto a 2D plane (the screen) to give lines L1-2 and L2-2.

Yes that's right.  :>  The screen is a 2D plane defined by Z=0.  However this is only relevant in that it gives me my 4th coordinate in order to form a line.

(click to show/hide)

To give some background, at this point we have already determined that, in 2D, the line we are checking intersects the line we are checking against.
The X and Y coordinates of that 2D intersection point are now known.
To get the Z coordinate, recall that all 2D action effectively takes place on the flat plane Z=0.  So Z = 0 is our third coordinate.
Now we have an X, Y, and Z coordinate; we then draw an imaginary line from the camera toward this X, Y and Z coordinate.

If you imagine this in your head, it's clear that the line we draw MUST intersect both of the other lines in 3D.  We calculate the 3D intersection point for the first line, then the second line, then compare them to see which is furthest from the camera.  Whichever one is furthest has a pseudovertex added...provided the pseudovertex isn't obscured behind another face.

Anyway, that's all pie in the sky right now; rather complicated stuff to try and explain, and not really necessary to understand the specific problem I'm having.

You want to know the point (X,Y) where the two projected lines intersect on the plane.

Nope, forget the screen/plane for now.

I have two 3D lines.
I know 2 coordinates on both lines (4 coordinates total).
I know that they intersect.

I need to find the 3D coordinates of where they intersect.

After finding this information, you want to know which of the 3D-space lines is closer to the camera at the point. If these lines L1-3 and L2-3 are skew they will pass through the points (X,Y,Z1) and (X,Y, Z2) respectively. You need to find which of the values Z1 and Z2 is smallest, as the smaller value will mean the line is closer to the camera at that point. If Z1 == Z2, then the lines intersect in 3D space and (I think) this will pose no problem.

Am I right, or have I missed something somewhere?

You're sort of on the right track with this last bit, but I have my own plans for how to handle the comparisons later down the line - code for lots of it has already been written.

For now, I only want to find out the coordinates of where those two lines intersect.

[Pilchard123]

So they will always intersect. Makes things a lot easier.

Just for reference, I'll use letters in bold (e.g. a, b, c) to refer to vectors in three dimensions  and letters in italics to refer to scalar quantities (a, b, c).

A line can be represented as r = a + n b.
A different line can be represented as s = c + m d

a and c are the position vectors of a single point on each lines. b and d are the direction vectors of the lines. They define which direction the lines go in. The scalar multipliers n and m before them are infinitely variable and can be any real number (no imaginary stuff here! ).

Since these lines will always intersect, r = s at a single point (X, Y, Z).

Therefore:

For r		For s
x = aX + nbX		x = cX + mdX
y = aY + nbY		y = cY + mdY
z = aZ + nbZ		z = cZ + mdZ

Or,
aX + nbX = cX + mdX
aY + nbY = cY + mdY
aZ + nbZ = cZ + mdZ

Solve two of these for n and m. I'll solve X and Y, equations are attached.

Once you have these two values, substitute in n or m in the equations for x, y and z. One point of intersection.

Will you always know two points on the lines? It make what I'm going to do next a lot easier to work with, trust me.

[annikk.exe]

Thanks for the maths Pilchard, haven't properly digested it yet...  just came on to say that my plan from earlier today:

Code: [Select]

-- load camera
AX1 = GetCameraX()
AY1 = GetCameraY()
AZ1 = CameraZ

AX2 = intersectX
AY2 = intersectY
AZ2 = 0

-- load edge
BX1 = vertex3dX[efe]
BY1 = vertex3dY[efe]
BZ1 = vertex3dZ[efe]

BX2 = vertex3dX[ete]
BY2 = vertex3dY[ete]
BZ2 = vertex3dZ[ete]

LinesIntersect(AX1, AY1, AX2, AY2, BX1, BY1, BX2, BY2)

-- set the Xintersect Edge coords, in case we get a Z match
XintEdge = intersectX
YintEdge = intersectY

LinesIntersect(AX1, AZ1, AX2, AZ2, BX1, BZ1, BX2, BZ2)

ZintEdge = intersectY

-- calculated the intersection point for Edge!

-- load otheredge
BX1 = vertex3dX[efoe]
BY1 = vertex3dY[efoe]
BZ1 = vertex3dZ[efoe]

BX2 = vertex3dX[etoe]
BY2 = vertex3dY[etoe]
BZ2 = vertex3dZ[etoe]

-- calculate intersection point in XY plane
LinesIntersect(AX1, AY1, AX2, AY2, BX1, BY1, BX2, BY2)

-- set the Xintercept Edge coords
XintOtherEdge = intersectX
YintOtherEdge = intersectY

LinesIntersect(AX1, AZ1, AX2, AZ2, BX1, BZ1, BX2, BZ2)

ZintOtherEdge = intersectY

...is not working.  Stuff goes very screwy indeed.


So it's back to this for now:

Code: [Select]

-- load camera
AX1 = GetCameraX()
AY1 = GetCameraY()
AZ1 = CameraZ

AX2 = intersectX
AY2 = intersectY
AZ2 = 0

-- load edge
BX1 = vertex3dX[efe]
BY1 = vertex3dY[efe]
BZ1 = vertex3dZ[efe]

BX2 = vertex3dX[ete]
BY2 = vertex3dY[ete]
BZ2 = vertex3dZ[ete]

t = (BX1 - AX1) / (AX2 + BX1 - AX1 - BX2)

-- intercepts edge at...
XintEdge = AX1 + ((AX2-AX1)*t)
YintEdge = AY1 + ((AY2-AY1)*t)
ZintEdge = AZ1 + ((AZ2-AZ1)*t)

XintEdge = (t * AX1) + ((1 - t) * BX1)
YintEdge = (t * AY1) + ((1 - t) * BY1)
ZintEdge = (t * AZ1) + ((1 - t) * BZ1)

-- load otheredge
BX1 = vertex3dX[efoe]
BY1 = vertex3dY[efoe]
BZ1 = vertex3dZ[efoe]

BX2 = vertex3dX[etoe]
BY2 = vertex3dY[etoe]
BZ2 = vertex3dZ[etoe]

t = (BX1 - AX1) / (AX2 + BX1 - AX1 - BX2)

-- intercepts otheredge at...
XintOtherEdge = AX1 + ((AX2-AX1)*t)
YintOtherEdge = AY1 + ((AY2-AY1)*t)
ZintOtherEdge = AZ1 + ((AZ2-AZ1)*t)

[Pilchard123]

So, will you always know the co-ordinates of two points on any line?

[annikk.exe]

Yes.

Three different lines are referenced by the above code.

Two of them are actually line segments.


Here's what happens...

First the code takes each edge, and checks it (in 2D) against each other edge checking to see whether they intersect...  both the lines involved here are line segments, and the code only triggers if they intersect within the boundaries of those segments.
This process repeats until all edges have been checked against all other edges.

When an edge is checked against another edge and an intersection is found, we have a potential pseudovertex.
To form our third line (this one won't be a segment), we need 2 points.  We take the first coordinate to be that intersection point.
But how can we do this if we only have 2D coordinates of the intersection point???

The answer is: recall that in 2D, the z coordinate is always 0.
Therefore the 3D coordinates of the intersection point are the same as the 2D coordinates, except that we add z = 0.

To get the other coordinate for the third line, we use the camera's position - which is already in 3D.


So we have two line segments that intersect in 2D:

Segment 1 (vertex 1 and 2)
Segment 2 (vertex 3 and 4)

And we also have 1 line, formed between the above 2D intersection point and the camera:

Line 1 (intersection point and camera)


So we start out with just segments 1 and 2, calculate their intersection point in 2D, then use that as a 3D coordinate (z=0) to calculate the point where the two segments intersect with the line drawn between the 2D intersection point and the camera.

That's a difficult sentence to digest but it's the most concise I can make the explanation of what this code does.


Lets also try in list form:

1.  Get the 4 coordinates that form Line Segment 1 and Line Segment 2.
2.  Calculate if the segments intersect in 2D
3.  If they do, take that 2D intersection point and use the X and Y as 3D coordinates, and set z = 0.  Lets call that point "fluffy"
4.  Draw an imaginary line between the camera and fluffy.
5.  Calculate where the imaginary line intersects with Segment 1.
6.  Calculate where the imaginary line intersects with Segment 2.
7.  Calculate which intersection point is furthest away.
8.  Calculate if that intersection point is hidden behind any faces (we have to check all faces, so this means even more loops...)
9.  If it's not hidden behind any other faces, add the pseudovertex to the edge that had the furthest away intersection point in step 7.



That's the entire process...
The above code comprises steps 3-6.

Step 3: If they do, take that 2D intersection point and use the X and Y as 3D coordinates, and set z = 0.  Lets call that point "fluffy" (in the code it's actually referred to as intersectX, intersectY, and 0)

Code: [Select]

-- load camera
AX1 = GetCameraX()
AY1 = GetCameraY()
AZ1 = CameraZ

AX2 = intersectX
AY2 = intersectY
AZ2 = 0

Step 4 and 5: Draw an imaginary line between the camera and fluffy.  Calculate where the imaginary line intersects with Segment 1.

Code: [Select]

-- load edge
BX1 = vertex3dX[efe]
BY1 = vertex3dY[efe]
BZ1 = vertex3dZ[efe]

BX2 = vertex3dX[ete]
BY2 = vertex3dY[ete]
BZ2 = vertex3dZ[ete]

t = (BX1 - AX1) / (AX2 + BX1 - AX1 - BX2)

-- intercepts edge at...
XintEdge = AX1 + ((AX2-AX1)*t)
YintEdge = AY1 + ((AY2-AY1)*t)
ZintEdge = AZ1 + ((AZ2-AZ1)*t)

-- not sure what this bit did... but i've disabled it and the whole thing still works the same as before.  bizarre..
-- XintEdge = (t * AX1) + ((1 - t) * BX1)
-- YintEdge = (t * AY1) + ((1 - t) * BY1)
-- ZintEdge = (t * AZ1) + ((1 - t) * BZ1)
Step 6: Calculate where the imaginary line intersects with Segment 2.

Code: [Select]

-- load otheredge
BX1 = vertex3dX[efoe]
BY1 = vertex3dY[efoe]
BZ1 = vertex3dZ[efoe]

BX2 = vertex3dX[etoe]
BY2 = vertex3dY[etoe]
BZ2 = vertex3dZ[etoe]

t = (BX1 - AX1) / (AX2 + BX1 - AX1 - BX2)

-- intercepts otheredge at...
XintOtherEdge = AX1 + ((AX2-AX1)*t)
YintOtherEdge = AY1 + ((AY2-AY1)*t)
ZintOtherEdge = AZ1 + ((AZ2-AZ1)*t)

So.. yes...  I always know 5 coordinates, and I've calculated the 6th already at this point.