Intersection point of line and polygon in 3d space

M

marcin

New member
Joined
Nov 15, 2018
Messages
2
I`m 3d modeler and I write scripts from time to time.

Please tell me how to find intersection point between line and polygon (plane - not infinity).

 I`ve got line vertices (points) A,B. I have vector build from those points (A-B).
I`ve got four vertices (points) of polygon (CDEF). I`ve got also N - normal vector to polygon plane.

I need to check is there any intersection between line and polygon and find that intersection point.

intersection.jpg

I`ve found few code snippets but they don`t work as they should, So I thought that I should understand that problem well before I start to code it.


Maybe do you know any book with similair problems like this?
 
Advice

You can maybe try to find formulas for analytic geometry in plane.
 
Just out of curiosity, some questions occur right off the bat.

What programming language are you using?

How is your coordinate system oriented? (EG: polygon in xy-plane, vector N parallel to z-axis)

Your sketch appears to show line AB parallel to N. Is this always the case?


Historically, relatively few active members at this forum have shown much appetite for helping developers. You're certainly free to post and wait. Yet, you may want to consider also the programming areas at sites like quora and stackexchange. (Be sure to read their guidelines, before posting. Those sites seem to have less tolerance for "incompletely presented" questions than we do.)

Cheers :cool:
 
marcin said:
I`m 3d modeler and I write scripts from time to time.

Please tell me how to find intersection point between line and polygon (plane - not infinity).

 I`ve got line vertices (points) A,B. I have vector build from those points (A-B).
I`ve got four vertices (points) of polygon (CDEF). I`ve got also N - normal vector to polygon plane.

I need to check is there any intersection between line and polygon and find that intersection point.

View attachment 10489

I`ve found few code snippets but they don`t work as they should, So I thought that I should understand that problem well before I start to code it.
Click to expand...

I assume you are asking only about the math, not about the details of programming; and that you know at least some of the math involved. You might want to be more specific about what didn't work, and in what way.

Let's start with point A and vector V = AB, to define the line, and point C and normal vector N, to define the plane. (Presumably you know that D, E, and F are really on that plane.) We can think of the points' coordinates as position vectors relative to some origin O.

You want point P on the line (i.e. P = A + tV) such that vector CP is perpendicular to N, so that it lies in the plane. One way to do this is to project vector AC on line AB.

Do you know how to do that?

Then, it sounds like you also want to determine whether P is in the interior of the given polygon. Do you know how to do that? Of course, you also want to check whether P is between A and B, which is easy.
 
Thanks for your help. I code this in Python but it`s not related with coding language. This calculation will be computed on many polygons which are on many different places of scene (not directed to any axis and not in origin of the scene). Each point has got three values: x,y,z.

I`ve make mistake becouse it`s possible to solve only with three sided polygons (three vectors) - not four. It`s hard to assume that every four of points are laying on same plane (it`s possible but not on every case).

I`ve already found point IP which is laying on the plane. Now I should use barycentric equation to check: is that point is inside three vectors. Now I`m stuck here.
 
marcin said:
… I`ve already found point IP which is laying on the plane. Now I should use barycentric equation to check: is that point inside three vectors. Now I`m stuck …
Click to expand...
Ah, you've made progress.

I'm not familiar with barycentric descriptions, but I see lots of search results. Did you try googling? :cool:

Do pages like this one seem helpful? To check, scroll down the page, to the following paragraph.

Now let’s see how we can use this. Imagine we’re trying to write a function in our game that determines whether or not a point is contained within a triangle. This is actually quite the common problem to solve in collision detection. In two dimensions, it might be a direct collision detection query. In three dimensions, we normally will first determine if a point is in the plane of a triangle, and if so, then reduce it to a two dimensional problem exactly like the normal 2D case. In either situation, we need a robust way to determine if a point is contained within a triangle. We can use barycentric coordinates in the reduced form to solve this, by taking the following steps:
Click to expand...
 
marcin said:
Thanks for your help. I code this in Python but it`s not related with coding language. This calculation will be computed on many polygons which are on many different places of scene (not directed to any axis and not in origin of the scene). Each point has got three values: x,y,z.

I`ve make mistake becouse it`s possible to solve only with three sided polygons (three vectors) - not four. It`s hard to assume that every four of points are laying on same plane (it`s possible but not on every case).

I`ve already found point IP which is laying on the plane. Now I should use barycentric equation to check: is that point is inside three vectors. Now I`m stuck here.
Click to expand...

Please be precise: What are you doing, exactly? Where are you stuck? What is going wrong?

You mentioned earlier wanting a book about such questions; have you searched for one about "mathematics for computer graphics", or the like? I don't know any specifics, but I have certainly seen such books, and they would probably help you.
 
Dr.Peterson said:
… What are you doing, exactly? Where are you stuck? …
Click to expand...
Hi doc. If I read correctly, marcin has the vertices of a triangle in 3d space and has determined the (x,y,z) coordinates of a point (named IP) where some line AB intersects the plane which contains the triangle. marcin now needs to confirm whether or not IP is located inside the triangle. :cool:
 
mmm4444bot said:
Hi doc. If I read correctly, marcin has the vertices of a triangle in 3d space and has determined the (x,y,z) coordinates of a point (named IP) where some line AB intersects the plane which contains the triangle. marcin now needs to confirm whether or not IP is located inside the triangle. :cool:
Click to expand...

Yes, that's how I understand it, too.

I'm just asking HOW he is "stuck" in doing that. He seems to know of a method (which is mentioned at the bottom of the page I suggested, as well as in more detail in yours); so what is going wrong in applying it? Hopefully it will be working now.
 
You must log in or register to reply here.
Top