Line intersect with Triangle

Hi there!

I've been searching the forums but I didn't find any good answers to my questions.

I need a function that checks these things:
*If a line intersects with a triangle at given coordinates in 3d space
*Where on the line the intersection takes place
*Where (Local 2D space) on the triangle the intersection takes place

Is there any way this could be done? Please help me!

After googling a bit, I found this:

http://www.acm.org/jgt/papers/Moller...re97/code.html

This function is exactly what I was looking for, but I can't get it to return correct values...


Could someone please answer me a couple of questions about this function?

Should all points be [x,y,z]?
Is orig a point in 3d space representing the starting point of the line?
Is dir also a point in 3d space?
Does it represent the end point of the line?

I suck at C/C++ and I also suck at math...That's why I can't get this to work.

Afternoon,

I have not coded C++ before either, however I do know some things about maths.
To answer your questions:


I would imagine that the [3] after all the arguments of intersect triangle refer to arrays of 3, likely to be coordinates. So yes, all points in xyz.

Orig, I would suspect, is a point in 3D space. As are the vert arrays. Orig is the origin, vert are the three vertices of the triangle.

Dir is not, it is a vector describing the direction of the line. You can tell because it is used in the Cross and Dot functions, for Cross and Dot product respectively, and these require vectors as input.


Hope that helps.


zaza

Thanks, that helps a bit. You're right about the [3].

Now I know how to use this function...There's only one problem left.
The thing is I don't really know how vectors work...
Could you please tell me what type of values I should use to describe the vector 'dir'?

Hi,

dir will be the following:

(x2-x1), (y2-y1), (z2-z1)

where the coordinate x1,y1,z1 is the start of the ray (origin, as you can see from one of the comments after the CULL line) and x2,y2,z2 is the endpoint of the ray.

A vector is defined (in 3D) by the above. Then there are handy operations such as the dot and cross products (used here) to transform them.

HTH

zaza

Thanks alot! Now I get it.
The dot and cross function are still a but too advanced for me to understand, but I don't really need to know what they do for this function.

Another thing that I would like to know is how to rotate this ray around its origin point.
I could probably do a search for it, but I figured you might know the answer.

Thanks alot!

Hi,

FYI, the dot product gives you the magnitude of vector a in the direction of vector b, so it is just a number. Perpendicular vectors thus have a dot product of 0. The cross product gives you a vector perpendicular to the plane of the two vectors given in a right-handed sense, which is to say that if you use your right hand and curl the fingers from vector 1 to vector 2, then vector 3 will be in the direction of your thumb. See here for more...


Regarding your other question, I'm not sure what you mean by it. You can use the dot product to find the angle moved: a.b = mod(a)mod(b)cos(theta) where a and b are the initial and final ray vectors, mod(x) is the length of x (use Pythagoras on the vector) and theta is the angle between them, also a.b = a dot b = a1b1 + a2b2 + a3b3...



zaza

That's not really what I meant... I was wondering how to rotate a point by changing the angles. I did a search and found the answer to that question. I turned it to a VB function that lookes like this:

VB Code:

Private Type Point3D
    X As Double
    Y As Double
    Z As Double
End Type
 
Private Function Rotate3D(tPoint3D As Point3D, tOrigin3D As Point3D, dPitch As Double, dYaw As Double, dRoll As Double) As Point3D
    Dim NewX As Double
    Dim NewY As Double
    Dim NewZ As Double
 
    Dim TempPoint As Point3D
 
    With TempPoint
        .X = tPoint3D.X
        .Y = tPoint3D.Y
        .Z = tPoint3D.Z
 
        NewX = (.X * Cos(dRoll)) + (.Y * Sin(dRoll))
        NewY = (.Y * Cos(dRoll)) + (.X * Sin(-dRoll))
 
        .X = NewX
        .Y = NewY
 
        NewX = (.X * Cos(dYaw)) + (-.Z * Sin(dYaw))
        NewZ = -((-.Z * Cos(dYaw)) + (.X * Sin(-dYaw)))
 
        .X = NewX
        .Z = NewZ
 
        NewY = (.Y * Cos(dPitch)) + (-.Z * Sin(dPitch))
        NewZ = -((-.Z * Cos(dPitch)) + (.Y * Sin(-dPitch)))
 
        .Y = NewY
        .Z = NewZ
    End With
 
    Rotate3D = TempPoint
 
End Function

I'm not sure if this is the best/fastest way of doing it, but it works.

Thanks alot for your help!

Glad to have been of use. Don't forget to mark the thread as resolved if you're all done.


Cheers

zaza