I am trying to solve the following problem in Python. The problem comes from an image processing problem when i use the Finite Element Method.

In my problem, I have a set of triangles and a ray. Each triangle consists of three 3-D points, and the ray is in the form of a 3-D point and a 3-D vector. How can I determine the first triangle that is passed through by the ray? Now I do not even have an algorithm for this. Any inputs will be appreciated.

CodePudding user response：

The first thing I would do, is translate the whole data set, subtracting the 3D ray origin. Then rotate the data set so that the ray's 3D vector aligns with the X-axis. See How to find the orthonormal transformation that will rotate a vector to the x axis?.

Now the problem has been converted to filter for triangles that cross the X-axis with a non-negative X-coordinate, and among those find the one whose crossing point has the minimal X-coordinate. So

• For each triangle check where its plane crosses the X-axis. See Determine point of interesction of plane with axis given points of plane

• Then throw away the triangles where that crossing point (on the X-axis) is not within the bounds of the triangle (check for each of the three edges that this point is at the "inner" side of it). See Check whether a point is within a 3D Triangle

• Throw away the triangles whose crossing point has a negative X-coordinate.

• Among the remaining triangles (that really cross the X-axis on the positive side) find the one with the minimum crossing point in terms of X-coordinate.