Intersection point of line and polygon in 3d space

[marcin]

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${\displaystyle vegotl\in evertices(p\oint s)A,B.Ihave\overrightarrow{\to }rbuildomthosep\oint s(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.



I${\displaystyle vefoundfewcodesnippetsbuttheydon}$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?

 

[Zivojin]

Advice

You can maybe try to find formulas for analytic geometry in plane.

 

[mmm4444bot]

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:

 

[Dr.Peterson]

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${\displaystyle vegotl\in evertices(p\oint s)A,B.Ihave\overrightarrow{\to }rbuildomthosep\oint s(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${\displaystyle vefoundfewcodesnippetsbuttheydon}$t work as they should, So I thought that I should understand that problem well before I start to code it.

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.

 

[marcin]

Thanks for your help. I code this in Python but it${\displaystyle s\neg relatedwithcod\in glangua\ge .Thiscalc\underline{a}tionwillbeco\mp utedonmanypolygonswhichareonmanyd\iff erentplacesofsce\ne (\neg directed\to anya\xi s\text{and}\neg \in \text{or}ig\in ofthesce\ne ).Eachp\oint hasgotthreevalues:x,y,z.I}$ve make mistake becouse it${\displaystyle spossib\le \to solveonlywiththreesdpolygons\left(three\overrightarrow{\to }rs\right)-\neg four.It}$s hard to assume that every four of points are laying on same plane (it${\displaystyle spossib\le but\neg oneverycase).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.

 

[mmm4444bot]

… I${\displaystyle vealreadyfoundp\oint IPwhichislay\in gonthepla\ne .NowIsho\underline{d}use\overline{y}centricequation\to check:ist\hat{p}\oint \in sthree\overrightarrow{\to }rs.NowI}$m stuck …

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:

 

[Dr.Peterson]

Thanks for your help. I code this in Python but it${\displaystyle s\neg relatedwithcod\in glangua\ge .Thiscalc\underline{a}tionwillbeco\mp utedonmanypolygonswhichareonmanyd\iff erentplacesofsce\ne (\neg directed\to anya\xi s\text{and}\neg \in \text{or}ig\in ofthesce\ne ).Eachp\oint hasgotthreevalues:x,y,z.I}$ve make mistake becouse it${\displaystyle spossib\le \to solveonlywiththreesdpolygons\left(three\overrightarrow{\to }rs\right)-\neg four.It}$s hard to assume that every four of points are laying on same plane (it${\displaystyle spossib\le but\neg oneverycase).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.

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.

 

[mmm4444bot]

… What are you doing, exactly? Where are you stuck? …

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:

 

[Dr.Peterson]

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:

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.

 

[mmm4444bot]

… I'm just asking HOW he is "stuck" in doing that …

Oh, my bad. I misinterpreted your question, "What are you doing, exactly?"