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.
To find the intersection between a line and a triangle in 3D, follow this approach: Compute the plane supporting the triangle, Intersect the line with the plane supporting the triangle: If there is no intersection, then there is no intersection with the triangle.
Either the plane and the ray perfectly coincide in which case there is an infinity of solutions or the ray is away from the plane in which case there is no intersection. Generally in a C++ implementation, when the denominator is lower than a very small value, we simply return false (no intersection was found).
The ray can intersect the triangle or miss it. If the ray is parallel to the triangle there is not possible intersection. This situation occurs when the normal of the triangle and the ray direction are perpendicular (and the dot product of these two vectors is 0).
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With