Jump to content
  • Advertisement
NewbZach

Noob question regarding checking point in triangle using barycentric coordinates

Recommended Posts

Hi, i'm currently reading the book on real time collision by Christer Ericson and i'm kind of stuck understanding this concept. In the book, it says that under the property of barycentric coordinates remaining invariant under projection, which is reflected in the code below. However, while trying to visualize it, I don't understand why. For example if the u and v was calculated from the projection onto the xz plane, meaning it represents whether x z of point p is within the triangle projected on the xz plane. But how does it remain invariant across other planes? Like if the y coordinate is not within the plane generated by triangle ABC. This ties into my second question on whether the code below applies to a triangle in 3d space or is it limited to 2d? If it is limited to 2d why is there a need to project onto a 2d plane. And if its 3d, what do the u v coordinates reflect? Does it reflect if the point lies within the plane defined by triangle ABC in 3d space? Sorry if this is a weird question, it's just that the book doesn't really go into super detail about the math and skips a few steps, as it's just supposed to be a primer. Any help is appreciated, a point to a good resource that explains it in depth would also suffice, thank you!

temp.PNG

Share this post


Link to post
Share on other sites
Advertisement
Posted (edited)

Maybe this document helps understanding it: https://pdfs.semanticscholar.org/0141/b1416bb749bb5ba94210a30d70f0824760a4.pdf

I don't know why projecting the triangle onto the plane should work, it seems wrong to me. I mean, the normal is different, that doesn't sound right. Unless the point is already on the the plane of the triangle.

The method from that paper seems to be faster and easier. And it works for points that are not on the triangle.

Edited by Magogan

Share this post


Link to post
Share on other sites
Posted (edited)

I presume this is part of a routine for finding the nearest points between two shapes? In which case, Point p has already been calculated as a point in the plane of the triangle.

Now, imagine a rigid frame with points A, B and C. When you project the triangle and Point p into a 2D plane, you create a flat image. Depending on the sign of the projection axis compared with the sign of the triangle's normal you might get a flipped image, but you then move, rotate and stretch the whole image so that A, B and C on the image match up with A, B and C on the frame. This is your barycentric coordinate system, with distances measured relative to the vertices and edges of the fixed frame, not the image or the original triangle.

Whatever projection you use, Point p will have the same barycentric coordinates. The reason for using the axis most closely aligned with the normal (You could use the normal itself, but then converting back to world space is slightly more complicated for no real benefit) is that you get the widest possible spread of triangle points in the projected image. This means you don't get degenerate triangles (Imagine projecting along the axis perpendicular to the normal, the image of your triangle would just be a line) and you minimise the likelihood of Point p ending up on the outside due to float point rounding (In practice, if it does end up on the wrong side it's probably still close enough to be useful).

Does that help?

Edited by OandO

Share this post


Link to post
Share on other sites
Posted (edited)
55 minutes ago, Magogan said:

Maybe this document helps understanding it: https://pdfs.semanticscholar.org/0141/b1416bb749bb5ba94210a30d70f0824760a4.pdf

I don't know why projecting the triangle onto the plane should work, it seems wrong to me. I mean, the normal is different, that doesn't sound right. Unless the point is already on the the plane of the triangle.

The method from that paper seems to be faster and easier. And it works for points that are not on the triangle.

Thats why the book says that barycentric coordinates are invariant between planes of projection. As the magnitude of the normal represents twice the surface area of the triangle formed by the 2 vectors, by projecting the triangle onto a plane, we can get the magnitude of the normal without any calculation as the other two values will be 0.  (I think) essentially saying that although the areas of the sub-triangles (u and v before dividing by total area) on different planes (xy, xz, yz) are different, because the total area (represented by the normal resulting from the cross product) is also different, the ratio between sub-triangle areas and total area is maintained. What I don't really understand is how these projected u and v values are represented in the original un-projected triangle. If the values are calculated in 2 dimensions, which means having less information then in 3 dimensions, how does it get represented in 3 dimensions?

I tried to draw it to better explain what i'm asking, sorry if its not to scale. So if the u and v values are calculated by the projected triangle and coordinates, p will be considered inside the projected triangle. However, it is not on the actual triangle as the y coordinate is higher up. I'm clearly misunderstanding something here, so I was wondering what it was. Thanks for the link though! I will be sure to check it out!

temp.PNG

Edited by NewbZach

Share this post


Link to post
Share on other sites

Because you already know the positions of the triangle's vertices in 3D world space, and barycentric coordinates are relative to the triangle's vertices. if the Point p was above or below the 3D plane the triangle lies in (Using the triangle's normal, not the projection axis) you would lose that information, but if you're doing what I think you're doing, Point p should already lie exactly on that plane.

Share this post


Link to post
Share on other sites
Posted (edited)
1 hour ago, OandO said:

I presume this is part of a routine for finding the nearest points between two shapes? In which case, Point p has already been calculated as a point in the plane of the triangle.

Now, imagine a rigid frame with points A, B and C. When you project the triangle and Point p into a 2D plane, you create a flat image. Depending on the sign of the projection axis compared with the sign of the triangle's normal you might get a flipped image, but you then move, rotate and stretch the whole image so that A, B and C on the image match up with A, B and C on the frame. This is your barycentric coordinate system, with distances measured relative to the vertices and edges of the fixed frame, not the image or the original triangle.

Whatever projection you use, Point p will have the same barycentric coordinates. The reason for using the axis most closely aligned with the normal (You could use the normal itself, but then converting back to world space is slightly more complicated for no real benefit) is that you get the widest possible spread of triangle points in the projected image. This means you don't get degenerate triangles (Imagine projecting along the axis perpendicular to the normal, the image of your triangle would just be a line) and you minimise the likelihood of Point p ending up on the outside due to float point rounding (In practice, if it does end up on the wrong side it's probably still close enough to be useful).

Does that help?

From the code image linked below, it shows how this function is used by the author. So I would assume the function aims to find if point p is within the triangle defined by point a, b, and c by checking if the returned u and v values match up.

 

13 minutes ago, NewbZach said:

Thats why the book says that barycentric coordinates are invariant between planes of projection. As the magnitude of the normal represents twice the surface area of the triangle formed by the 2 vectors, by projecting the triangle onto a plane, we can get the magnitude of the normal without any calculation as the other two values will be 0.  (I think) essentially saying that although the areas of the sub-triangles (u and v before dividing by total area) on different planes (xy, xz, yz) are different, because the total area (represented by the normal resulting from the cross product) is also different, the ratio between sub-triangle areas and total area is maintained. What I don't really understand is how these projected u and v values are represented in the original un-projected triangle. If the values are calculated in 2 dimensions, which means having less information then in 3 dimensions, how does it get represented in 3 dimensions?

I tried to draw it to better explain what i'm asking, sorry if its not to scale. So if the u and v values are calculated by the projected triangle and coordinates, p will be considered inside the projected triangle. However, it is not on the actual triangle as the y coordinate is higher up. I'm clearly misunderstanding something here, so I was wondering what it was. Thanks for the link though! I will be sure to check it out!

temp.PNG

This is the main misunderstanding I have with this algorithm. Is it not projecting the triangle defined by a b c onto a 2d plane by removing the largest dimension, as you have said, to get the largest area to reduce degeneracy. However, I am clearly misunderstanding how the u and v values calculated by the projection can translate over to determining if a point falls within the triangle in 3 dimensions. Hopefully my drawing is clear enough though the scale is a little off. Thank you for taking the time to help me!

temp2.PNG

7 minutes ago, OandO said:

Because you already know the positions of the triangle's vertices in 3D world space, and barycentric coordinates are relative to the triangle's vertices. if the Point p was above or below the 3D plane the triangle lies in (Using the triangle's normal, not the projection axis) you would lose that information, but if you're doing what I think you're doing, Point p should already lie exactly on that plane.

I think I replied to your question after you replied to mine haha sorry but I do not really know what I'm doing. Can you elaborate on what you think I'm doing? Haha sorry i'm such a noob. I understand that they are relative to the triangle vertices in 3 dimensions, but by projecting isnt it removing one dimension? 

Edited by NewbZach

Share this post


Link to post
Share on other sites

What's the big problem that you're trying to solve? I've read this book before, and the use I found for this particular bit of code was after finding the closest points between two shapes. That means Point p was known to lie in the plane of the triangle I was testing against.

Share this post


Link to post
Share on other sites
Posted (edited)
40 minutes ago, OandO said:

What's the big problem that you're trying to solve? I've read this book before, and the use I found for this particular bit of code was after finding the closest points between two shapes. That means Point p was known to lie in the plane of the triangle I was testing against.

What do you mean by closest point between 2 shapes? Are the shapes planes defined by 3 points in 3d space? Maybe I'll Google it. I'm not trying to solve any problem, just trying to understand how this algorithm works, from it's input to output and what it means.

Edit: ohh do you mean that in order to use this function, point p has to be coplanar with the plane generated by abc? 

Edited by NewbZach

Share this post


Link to post
Share on other sites
1 hour ago, NewbZach said:

What do you mean by closest point between 2 shapes? Are the shapes planes defined by 3 points in 3d space? Maybe I'll Google it. I'm not trying to solve any problem, just trying to understand how this algorithm works, from it's input to output and what it means.

Edit: ohh do you mean that in order to use this function, point p has to be coplanar with the plane generated by abc? 

Let me rephrase the last question since I can no longer edit it, sorry. So in order to use this function, the pre condition has to be such that point P is coplanar to the plane generated by ABC? If not it won't return an accurate result? I was under the impression that point P could be any point in space, hence the confusion. Is my understanding correct?

Share this post


Link to post
Share on other sites

If you were to project along the normal of the triangle, your results for point p would always be accurate (although you'd be discarding the height above / below the plane of the triangle). Projecting along the X, Y or Z axis in world space is an optimisation which assumes point p is co-planar.

As for the closest point between two shapes, I was using this function as a follow up to the GJK algorithm, which takes two convex 3D shapes and returns the point on the surface of each that is closest to the other shape.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!