Ray and 3D Face Intersection

Question

I have a 3D face defined by n points (v1, v2, v3,..., vn), in 3D coordinates, and I have a ray of the equation:

P=P0+t(P1-P0).

where 0<=t<=1.

Now, how to find the intersection point ( or lack of) between this ray and the face?

Also, it would be great if there is an existing C# implementation on this?

Edit: The 3D face can be concave or convex. All the points are coplanar.

Answer 1

I suppose your 3D polygon is planar (otherwise it's not really a polygon and it's not well defined). Therefore you can find a 2D orthonormal basis for this plane. Which means you can use any 2D triangulation algorithm (you can find many c# implementations on the web) and go back to 3D using your orthonormal basis. This way you will get 3D triangles and will be able to easily do your ray-polygon intersection test by running multiple ray-triangle intersection tests.

Another way is perform a ray-plane intersection calculation. Take the intersection point P, represent it using 2D coordinates with the above orthonormal basis. In addition, as in the previous solution, represent your polygon in 2D using the same basis. Then run any "is point in polygon" 2D algorithm and you will get your results.

Update: Here is the math You can take any two points on the plane p1, p2 (e.g two of the polygon's points) and take the vector u = p2 - p1. Normalize it, and it is the first basis vector. Then you take the plane's normal N and calculate v = cross_product(u , N) and normalize v. This is the second basis vector. Note that both vectors have unit length and they are orthogonal to each other. Therefore they form an orthonormal basis.

Now define p1 to be the plane's origin. Then the translation to 2D of any point q on the polygon (q can be one of the polygon's vertices, or any other point on the polygon's plane):

x = dot_product(q - p1, u)
y = dot_product(q - p1, v)

Here x,y are the point's 2D coordinates.

So after translating everything to 2D and doing your 2D algorithms you can translate any 2D point (x, y) back to 3D like this:

q = p1 + x * u + y * v

Here * is the scalar-vector product (x,y are the scalars and u,v are the vectors).

Alex.

Answer 2

If your points are not co-planar (i.e. the don't all lie on a single plane) then you need to sub-divide the surface into a set of planes and then do the line-polygon intersection for each plane. Better still, define a list of triangles and then do search on the line-triangle intersection results.

However, you don't say if your points define a faceted object (i.e. made of triangles) or define a set of control points for a curved surface. The former is handled by the above. If it's a curved surface, I think this in an incalulatable problem, that is, there is no trivial solution to the problem of determining the intersection of a line and a curved surface defined by a set of points. The best you can do is to use an iterative process of finding the intersection point, but even this could lead to unstable searches (i.e. searches that never complete).

I think converting to a set of triangles is the best answer.

Answer 3

You're after a ray-polygon intersection algorithm, here's a link to the Graphics Gems entry for it: http://www-graphics.stanford.edu/courses/cs348b-98/gg/intersect.html