Algorithm for checking if within a triangle

[Misu]

Hi everyone. Im trying to figure out a way to check whether a point is within a triangle boundary for a shader. I came up with one method but its ratherly slow because it uses so much if statements. Does anyone know any possible method on detecting a point within a triangle boundary?

 

[NazGhuL]

Is the point_in_triangle(px, py, x1, y1, x2, y2, x3, y3) function can do that?

 

[Misty]

Think he means 3D, in which case he will have problems with degenerate projections at certain angles. It will work 99.8 percent of the time though.

 

[Misu]

Everyone, I clearly specified for shader as well. I know about the point_in_triangle command but that wont work in glsl. And im talking about 2D.

 

[jo-thijs]

@NazGhuL, that's unfortunately not a function for shaders.

@Misty, he never said he is using 3D, and I'm actually guessing he wants it in 2D.
Correct me if I'm wrong.

@Misu,
I know a method do it and I can explain, but I think you can find everything you need here already:
http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-2d-triangle

 

[Roa]

2d or 3d doesn't matter. Same techniques can be deployed. That said, this is no different than general ray cast algorithms.

a simple way close to ray cast is

find the point and do checks that are axis aligned.

If those axis goes through 2 of the lines of the triangle, then its inside.

the axis can be tested against the triangle by using basic trig/linear equation rules for intersections.

How to write this in a shader, I've no clue, but thats the general concept.

 

[jo-thijs]

@Roa, that's not true, it does matter if it is in 2D or 3D.
You could for example use a basic operation in 2D to look at what side of a line a certain point lies.
This can very efficiently be done in 2D and can be used for creating the algorithm to this problem.
In 3D however, there is boolean concept of side of a line, which makes that method unusable (without extra care).

Now, as to your suggested method, it sounds like it would be more complicated and less performant than could be,
as you need to calculate multiple intersections and do axis aligned checks and such.
I'm not an expert yet with ray casting algorithms yet though, so I might be wrong.

 

[Roa]

I'm no expert either, but if its shader work, GPUs are happier crunching numbers than a bunch of ifs.

 

[Yal]

This might be helpful, I guess?
http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-2d-triangle

Tried doodling a bit, but didn't really get any good results. The idea I had was using the triangle inequality to compare the distance between corners and the point with the length of sides - the sides are the shortest possible distance between the corresponding corners since they're straight lines - but the issue is that points inside and outside a triangle both have longer distances, so that can only be used to see if a point is on the boundary of a triangle, and checking which side you're on results in a lot of angle computations I'm not caffeinated enough to do right now. So I hope Stack Overflow will do... x3

 

[jo-thijs]

@Yal, that's the same link I gave.
Must mean it's good enough.

@Roa, that's true, but at least 1 comparison operation is unavoidable due to the nature of the problem.
The algorithm I had in mind uses 3 comparison operators (slight variant of the top answer algorithm in the link I gave to replace comparisons with multiplications, not sure if that's more performant)
and it uses no ifs.

 

[Yal]

@Yal, that's the same link I gave.
Must mean it's good enough.

At least it proves that I just read the first post and then immediately type a reply way more often than I should.

 

[Misu]

That link helped me. Thanks!