CODEWITHSUNDEEP
python3dlinepolygonsegment
rizerphe
rizerphe

Reputation: 1390

3d intersection between segment and triangle

Everything around the web is too complicated.

So, i have a triangle defined by array of three dots, and segment, defined by 2 dots. Dot = 3 floats. I want to know if they intersect. Also point of intersection will be helpful, but not as much.

I have something like this: made in blender 2.78

and 5 coords (15 floats) for every case. I need just python code or math formula, and hopefully some info for starter.

Please, about python: start code with something like this:

plane = [[float(input('plane coord1 x:'), float(input('plane coord1 y:'), float(input('plane coord1 z:')], [float(input('plane coord2 x:'), float(input('plane coord2 y:'), float(input('plane coord2 z:')], [float(input('plane coord3 x:'), float(input('plane coord3 y:'), float(input('plane coord3 z:')]]
line = [[float(input('line coord1 x:'), float(input('line coord1 y:'), float(input('line coord1 z:')], [float(input('line coord2 x:'), float(input('line coord2 y:'), float(input('line coord2 z:')]]

or this:

plane = [[x1,y1,z1], [x2,y2,z2], [x3,y3,z3]]
line = [[X1,Y1,Z1], [X2,Y2,Z2]]

Upvotes: 3

Views: 2563

Answers (1)

Mauricio Cele Lopez Belon
Mauricio Cele Lopez Belon

Reputation: 1507

I will give you a math formula:

All triangles must have an orientation. Orientstion is given by the order of the triangle vertices or, equivalently, the triangle normal. I assume the triangle vertices are p1, p2 and p3 in Counter-Clock-Wise order (CCW).

Triangle normal N is:

N = (p2 - p1) × (p3 - p1)

Where × denotes "cross product". Then create a normal vector for each triangle side:

N12 = (p2 - p1) × N
N23 = (p3 - p2) × N
N31 = (p1 - p3) × N

The side-normals are vectors in the triangle's plane but orthogonal to the triangle sides. Side-normals are useful for computing distance between point and line.

For instance, given a point "p" lying on the triangle's plane, the minimum distance fom p to the line passing thru points p1 and p2 is:

Dist = ((p - p1) • N12) / |N12|

The • denotes the "dot product" and |N12| is the norm of the side-normal.

Side-normals are pointing outwards the triangle. The distance Dist = ((p - p1) • N12) / |N12| will be positive if the point is outside the triangle. If all three distances from p to the triangle sides are negative, then the point is inside the triangle.

The point p lying in the triangle's plane is the intersection of the line and the triamgle's plane. The line segment with points s1 and s2 can be represented by a function like this:

R(t) = s1 + t (s2 - s1)

Where t is a real number going from 0 to 1.

The triangle's plane is defined by the unit normal N and the distance to the origin D. So the plane equation is:

N • x + D = 0

Where x is any 3D point in satisfying the equation. The distance to the origin D can be computing using any point of the triangle, for example:

D = -(N • p1)

The intersection of line segment R(t) and the plane happens when t has the value:

t = - (D + N • s1) / (N • (s2 - s1))

With that t you can compute the intersection point of the line and the plane. Having that point and using the side-normals you can know if the intersection point is inside the trianle or not.

Upvotes: 5

Related Questions