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
Optimal way of dertermining if a point is inside of a triangle
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.
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.
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
See below the highly professional ms-paint diagram
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement