Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Ray and 3D Face Intersection

Tags:

c#

geometry

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.

like image 254
Graviton Avatar asked Dec 15 '10 08:12

Graviton


People also ask

How do you know if a line intersects a 3D triangle?

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.

Can the intersection of a plane and a ray be a ray?

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).

Does Ray intersect triangle?

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).


2 Answers

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.

like image 120
Alex Shtof Avatar answered Oct 21 '22 09:10

Alex Shtof


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.

like image 40
Skizz Avatar answered Oct 21 '22 08:10

Skizz