Jump to content
  • Advertisement
Sign in to follow this  
IrYoKu1

Optimal way of dertermining if a point is inside of a triangle

This topic is 2889 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey guys,

I was just wandering, what is the best way of determining if a point (x,y) is inside of a triangle defined by their vertices (p1, p2, p3, where each one is a (x,y) tuple).

It is just that for multisampling, each subsamble must be tested to discover whether it is inside or outside (http://msdn.microsof...2(v=vs.85).aspx, see Multisample Anti-Aliasing Rasterization Rules), and what I found seems to be too expensive for it to be efficient (the barycentric approach: http://www.ugrad.cs....notes-sept9.pdf). Maybe for multisampling a special trick is done somehow?

(by the way, gamedev looks splendid right now, with the redesign =)

Thanks!
Jorge

Share this post


Link to post
Share on other sites
Advertisement
Here is a method I've used in the past:

1. Find vectors (normals) perpendicular to each edge. This is easily done in 2D, just take care to consider the handedness with respect to the triangle winding order, and be consistent.
2. For each edge, see if the test point is "in front" or "behind". Make a vector from any point along the edge (say, either end vertex--it doesn't matter which) to the test point, and take the inner product of that with the normal for that edge. Compare the result with zero.
3. If you get the same comparison result with all three edges, it's inside; otherwise, it's outside.

Share this post


Link to post
Share on other sites
Make three triangles by joining each edge of the triangle under test with the point. Add up the areas of these triangles and if their total area is greater than the area of the triangle under test, the point lies outside the triangle. If their total area is equal the area of the triangle, the point is inside the triangle.

See below the highly professional ms-paint diagram :)

triangles.png

Share this post


Link to post
Share on other sites
Thanks both for the replies!

Three deltas, three cross products, three abs, two sums and one comparison. Seems to be cheap enough =]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!