[no fix]triangle3di isPointInside

[Eigen]

Either I'm doing something very wrong or there is a bug. Using Irrlicht 1.7.1 but I highly doubt that matters.

This returns true
triangle3di(vector3di(25, 0, 0), vector3di(0, 0, 50), vector3di(50, 0, 50)).isPointInside(vector3di(30,0,30))

This returns false. What gives? isPointInsideFast return true but is less accurate so I can't use that.
triangle3di(vector3di(250, 0, 0), vector3di(0, 0, 500), vector3di(500, 0, 500)).isPointInside(vector3di(300,0,300))

This returns true
triangle3df(vector3df(25, 0, 0), vector3df(0, 0, 50), vector3df(50, 0, 50)).isPointInside(vector3df(30,0,30))

This returns true
triangle3df(vector3df(250, 0, 0), vector3df(0, 0, 500), vector3df(500, 0, 500)).isPointInside(vector3df(300,0,300))

[CuteAlien]

Interesting bug. This is causing an integer overflow internally in triangle3d::isOnSameSide when trying to get the point-product of 2 cross-products.
Maybe integers should have some specialization which scales values when they get too large or something like that... ideas welcome.

[Eigen]

Hmm, I see. Perhaps it's worth trying alternative methods of checking if a point is on a triangle (I know there's one dealing with barycentric coordinates)? When I get home, I'll give it a go. Or I could use floats instead of ints, but I'd rather keep the casting back and forth to a minimum as I'm dealing with textures and need ints for pixel coordinates.

[REDDemon]

... ideas welcome.

What about using the baricenter?

Code: Select all

 
// The triangle is described by 3 points. (P1,P2,P3). The point to check if is inside is "Point"
const vector3d<T> A = P3 - P1;
const vector3d<T> B = P2 - P1;
const vector3d<T> C = Point - P1:
 
// square lenght of triangle sides
const T squareA = A.getLenghtSQ();
const T squareB = B.getLenghtSQ();
 
// dot products.
const T projAB = A.dot( B);
const T projAC = A.dot( C);
const T projBC = B.dot( C);
 
// get coordinates as X and Y
const f32 lenght =  (squareA * squareB - projAB* projAB);  
const T X = (squareB * projAC - projAB * projBC );
const T Y = (squareA * projBC - projAB * projAC );
const f32 check = (X+Y)/(lenght);
 
// final checks
//!Marshalling bug fix here?
return ( check<1 ) && (X>0) && (Y>0);
 
 

maybe this code is not perfect but should work. some test cases are preferred and wellcome now maybe i mistyped something like A instead of B or some sign i don't have time to test it now with lots of triangles.. ^^ .. but it should be a bit faster than the old triangle test. maybe f32 for X and Y will prevent most of integers overflow.

[CuteAlien]

Yeah thanks, I have to run tests, but might be good idea, we're also using tests with barycentric coordinates in your own project.

[CuteAlien]

It's changed in svn release branch 1.7 revision 3894, trunk will follow soon. Integer overflows can certainly still happen, but for way larger numbers (in the test above you can now add one more zero to the numbers and it will still work, 2 more and it will fail). I used the barycentric coordinates (slightly different implementation). Turns out it's even a big deal faster than the old implementation (up to 2 times in many cases) and beats even isPointInsideFast (very slightly - they are about the same speed).

[hybrid]

I hope we have enough test cases and this is not changing too much existing behavior besides the errors. Otherwise we should maybe just put it into trunk here.

[CuteAlien]

It's never used in the engine and I wrote a lot of tests just for that and compared the results with the old behavior.

[CuteAlien]

OK, lesson learned - you can never have enough test-cases *sigh*.
I had to revert that fix as it broke indeed the old behavior in some situations. The existing isPointInside behaves better for some floating-point inaccuracies, which was rather noticeable when working with Direct3D which sets the FPU into single-precision mode.

But as a workaround I changed now isPointInsideFast instead. Although this also changes behavior I think that at least should be fine as I can't think of a good reason why we would want inconsistent behavior for points on the triangle borders. So now it returns throughout points on the border as inside and should be usable for your situation.

Sorry for the mess, but that stuff was really, really hard to find & debug.