intersection [RESOLVED, tnx]

[Doddddy]

working in space (3-d)
i have a line (a vector; v=[vx,vy,vz]) and a triangle (three vectors to define three distinct points; v1=[v1x,v1y,v1z],v2=[v2x,v2y,v2z],v3=[v3x,v3y,v3z]) and i need to determine whether there is an intersection between them or not...

chalanging, not?

[sql_lall]

just a brief summary:

0) You need a point on the line also to have a line. Just a direction doesn't help at all.

However, given a proper line, you can do this:
1) Find two of the vectors of the sides of the triangle. (E.g. if triangle is points A, B, and C, find two vectors like AB and AC)
2) Find their cross product, which then gives you the equation of the plane that the triangle is in.
3) Find the intersection of the line and the plane.
4) Check whether this point is inside the triangle.

Now, point 4 is still the harder bit, but i'm sure there is a simple way to do it....maybe project a line form the point to point A, and see where intersects the side BC...i dunno

[NoteMe]

Originally posted by sql_lall

4) Check whether this point is inside the triangle.

Now, point 4 is still the harder bit, but i'm sure there is a simple way to do it....maybe project a line form the point to point A, and see where intersects the side BC...i dunno

Well I would guess you would have to do it the same way as with a sqare, just two times...because if you checks it like a square then it might be on that part of the sqare where not the the triangle is...ie: check 2 vectors, then two "other" vectors in the triangle...not sure tho...

[Doddddy]

well actually i forgot about a point for the line as it crosses the origin. Anyhow tnx for all the help guys, i'll go try it now

[twanvl]

To check if a point is inside a triangle ABC, you can check if it is on the same side of AB, BC, CA. IIRC you can do this using dot(AB,AP), so a point P is in the triangle iif:
sign(dot(AB,AP)) = sign(dot(BC,BP)) = sign(dot(CA,CP))
where dot=inner product.
This is just of the top of my head, so I could be completely wrong.
BTW. a quick google gets you this

[Doddddy]

thanks twanvl

[sunburnt]

Originally posted by twanvl
To check if a point is inside a triangle ABC, you can check if it is on the same side of AB, BC, CA. IIRC you can do this using dot(AB,AP), so a point P is in the triangle iif:
sign(dot(AB,AP)) = sign(dot(BC,BP)) = sign(dot(CA,CP))
where dot=inner product.
This is just of the top of my head, so I could be completely wrong.
BTW. a quick google gets you this

Completely right.

(old post :P)

a point X is outside of a triangle ABC if

   B     X
  /_\
 C   A

ABX is a clockwise turn OR
BCX is a clockwise turn OR
CAX is a clockwise turn

a point X is inside of a triangle ABC if

   B     
  /X\
 C   A

ABX is a counter clockwise turn AND
BCX is a counter clockwise turn AND
CAX is a counter clockwise turn
You can determine clockwise/counterclockwise by taking the determinant:

SomeType Determinant(x1, y1, x2, y2, x3, y3)
{
    float determ = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);

    if (determ >= 0.0)
        return CounterClockwise;
    else
        return Clockwise;
}

so:

if ( (Determinant(A.x, A.y, B.x, B.y, X.x, X.y) == CW) ||
     (Determinant(B.x, B.y, C.x, C.y, X.x, X.y) == CW) ||
     (Determinant(C.x, C.y, A.x, A.y, X.x, X.y) == CW))
{
   Point X is outside
}
else
{
   Point X is inside
}

[kapedu]

Can you do something like this.
If the triangle is A B C and the point is P, check if the area of triangle ABC is equal (difference 0.00001) same as sum of areas of triangles made by either side of triangle and point P

area(ABC) - [area(ABP)+area(ACP)+area(BCP)] < 0.00001

You may calculate area of triangle using Heron Formula:
http://mathworld.wolfram.com/HeronsFormula.html

I need a VB code to determine intersection point of line and a plane. Does anyone have it?