Freesteel Blog » Point inside triangle correct

Point inside triangle correct

Monday, June 11th, 2007 at 11:02 am Written by:

Following from the incorrect method for finding which triangle of a mesh a given point is inside, here is the right answer.

The trick is to know that the only lines you can reliably tell sidedness along are those parallel to the X or Y axes, and the special cases of the lines x = y and x = -y. All other lines, defined by, say, a + tv, are going to prove somewhat noisy close in when attempting to determine which side of them a given point lies if you use the standard relation:

(p - a) . vT > 0

In particular, if you have three lines passing through the same point and that point is not the a point in all of them, they won’t, and you’ll get a little unexpected area inside the triangle where they don’t all meet.

So, the scan line method works along the Y-axis. The triangle here has, relative to this direction, ay < cy < by. All the intervals are half-open, which means the point p can hit the triangle only when ay <= py < cy. The triangle also separates into two parts, the lower where py < cy and the upper where py >= cy.

In this diagram p is in the upper part, so we find the intersections of the line Y = py with the lines ab and cb to get points xab and xcb (not labeled). It doesn’t matter what order because they can be sorted and then treated as a half-open interval for comparison to the value px.

Actually, it is a good question whether the condition xab < xcb will remain the same for all values of py. I don’t know the answer to this one, and it probably depends on how carefully you calculate it. Ideally, if it’s determined that c is to the right of the line ab, then it’s consistent for all Y.

One has to assume the 2D triangle meshes are very nasty because the problem we’re actually trying to solve is the intersection of a 3D line through a polyhedral mesh representing the surface of a solid volume. The first step is always to project the entire model onto the plane perpendicular to the line (so that the line becomes a point). Even though you began with a well-behaved triangular surface, there are projections where the triangles turn into slivers and shards.

3 Comments

  • 1. SJ replies at 12th June 2007, 5:52 am :

    Bogus logic. If you start with line segments represented in terms of their endpoints, and triangles represented in terms of line segments with common endpoints, then you can solve the problem robustly using only that single ‘sign of the determinant’ function. But if you choose to throw away
    information (and accuracy) by converting the line representation to a ‘standard’ parametric one, you are introducing the noise yourself. Frankly, you are big-headed and unbearable…

  • 2. Julian replies at 21st November 2008, 4:18 pm :

    You needed to follow the link given to know what it is correcting:

    http://www.freesteel.co.uk/wpblog/2007/05/finding-points-in-triangles/

    The standard method is fine if you only have one triangle. The reason for this non-standard method is it guarentees that the point will be found in exactly one triangle of a mesh covering of the plane.

    But obviously if you don’t know this, the method looks kind of stupid. Depending on how quick-witted you want to be, you can leap to the conclusion that you are right and I am wrong, if that’s how you’d like it to be.

  • 3. anderswallin.net ›&hellip replies at 17th December 2011, 11:39 am :

    […] check if the CC point lies within the triangle, but that will have to wait until the next post… (Mr. Todd has some thoughts on this) This was written by admin. Posted on Monday, June 25, 2007, at 21:06. Filed under Drop-Cutter. […]

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>