Why is this approach not being used more? The computation runs in O(n) where n is the number of pixels on the screen, but it can be massively parallelized. Is it still not cheap enough?
doberdog91
The same side of line test can be used to check which side of a line (which half plane) a point is on. For line segment AB and points P and Q, take the cross product of vector AB with vector AP, and look at its z-component (x and y will be 0). Also take the cross product of vector AB with vector AQ. If their signs are the same, they are on the same side of line segment AB.
Then for a triangle ABC and point P, check if P and C are on the same side of AB, P and A are on the same side of BC, and P and B are on the same side of AC.
This is the simplest to undertand point-in-triangle test.
chovedrecht
I love @doberdog91's approach. How do you handle edge cases using this approach?
alexz2
I find @doberdog91's approach very effective. A quick note I'll add to that is be careful of the line's direction: what's to the left of AB is not to the left of BA!
Why is this approach not being used more? The computation runs in O(n) where n is the number of pixels on the screen, but it can be massively parallelized. Is it still not cheap enough?
The same side of line test can be used to check which side of a line (which half plane) a point is on. For line segment AB and points P and Q, take the cross product of vector AB with vector AP, and look at its z-component (x and y will be 0). Also take the cross product of vector AB with vector AQ. If their signs are the same, they are on the same side of line segment AB.
Then for a triangle ABC and point P, check if P and C are on the same side of AB, P and A are on the same side of BC, and P and B are on the same side of AC.
This is the simplest to undertand point-in-triangle test.
I love @doberdog91's approach. How do you handle edge cases using this approach?
I find @doberdog91's approach very effective. A quick note I'll add to that is be careful of the line's direction: what's to the left of AB is not to the left of BA!