getIntersectionWithLimitedLine() misses at edges of triangle

[merovingian]

I am reasonably certain I've found a marginal bug in Irrlicht. My code is replicating a range-finding laser to measure the distance from the camera to the surrounding walls, at 0.5 degree intervals in a 180-degree arc in a flat plane. As discussed here:

http://irrlicht.sourceforge.net/phpBB2/ ... highlight=

The code uses getIntersectionWithLimitedLine() to find the intersection point between a triangle and a line projected from the camera at 0.5 degree intervals.

What I have observed are occasional readings within a 180 degree laser scan that fail to find any intersection with the surrounding walls of the mesh, even though there are no holes in the mesh. Looking deeper, I've seen that the no-intersection situation occurs when two triangles have a shared side that is right on or very close to a 0.5 degree boundary. e.g. One triangle ends at 72.50007, and the next begins at 72.50007. My code tests for an intersection with both triangles in this case, but finds none. My suspicion is that getIntersectionWithLimitedLine() suffers from a minor floating point accuracy issue.

I know this problem report is not super useful without a code snippet that demonstrates the problem, but my code uses a static model. I have worked around the issue, by catching it and calculating the distance to the edges of the triangles.

[rogerborg]

That was most likely due to vector3d<T>::isBetweenPoints(), using a < test. It wasn't obviously wrong, since the test is "between" points, and we never documented whether that was inclusive of the end points or not.

However, the latest SVN trunk uses a <= test, which I believe gives results that are more likely to be what most uses would intuitively expect. If you get a fresh SVN checkout, you should see better results.

[BlindSide]

That was most likely due to vector3d<T>::isBetweenPoints(), using a < test.

I think this issue is more related to isPointInside(), which in turn uses isOnSameSide(), which seems to be using a >= test "(cp1.dotProduct(cp2) >= 0.0f)". There is no epsilon here, so it might be wise to substitute for "(cp1.dotProduct(cp2) >= -core::ROUNDING_ERROR_32)" if you want a more lenient test.

For more performance however, have you tried substituting the isPointInside() call inside "getIntersectionWithLine()" for isPointInsideFast()? Because it uses a completely different method, it may also automagically solve your problem. I've been using this combination without problems personally.

Cheers

[rogerborg]

Ah, yes, sorry: the isBetweenPoint() check is only relevant when the collision is at the start or end of the intersecting line, not to where it intersects with the triangle. Apologies, I got a bit eager because I submitted a fix for isBetweenPoint() recently.

Do you have a simple, repeatable test case with data that reproduce the problem? That would be the best way to get a definitive answer.

[merovingian]

No I don't have a simple repeatable test case. And as I already have a suitable workaround, I probably won't rush to make one.

I'm not sure whether Blindside's substitution idea was directed at me. If it was, I am not sure why he would think that I should have considered such possibilities, unless he is mistaking me for someone who has been active in Irrlicht's development.

Anyway, due to other problems (namely the dual-core getTime() bug), I have now just started building my own Irrlicht DLL from the SVN trunk to get latest patches. This was surprisingly painless. So I now have the means to start fiddling with Irrlicht itself, as Blindside has suggested. Maybe it's time for me to live up to my newly acquired T-shirt, and start submitting patches.

[hybrid]

Well, do you get better results with the SVN trunk version? Because, as rogerborg mentioned, I did change isBetweenPoints to work inclusive. The other parts of the patch are still under test, and will probably pop up in SVN in the next days.

[merovingian]

Unless I misunderstand, rogerborg and Blindside subsequently agreed that isBetweenPoint() is not relevant because the fix in there makes the end of the line inclusive, but the problem with this bug is that the edges of the triangles are seemingly not inclusive.

Anyway, I can confirm that the problem still exists in SVN revision 1489.

Regarding Blindside's suggestions:

1) isPointInsideFast() does not proivde automagic fix.
2) Use of -core::ROUNDING_ERROR_32 also doesn't fix it.

These observations of course assume that I'm competent in re-building Irrlicht, and making my application use the changes. I don't think I stuffed this up, but Blindside's suggestions seem like good ones - I was quite optimistic that at least one of them would do the trick. The fact that they didn't, starts to give me that operator error kind of feeling.

Got no time to look deeper right now.

[rogerborg]

Is it fairly repeatable with your app? I'm having no luck finding it though code examination or by dumb number crunching with candidate triangles and rays. It would be really great to have an app + resources that demonstrate it.

[merovingian]

It's not all that repeatable. My application is making about 1000 calls to getIntersectionWithLimitedLine() per frame, and there are 90-odd frames per second. I can drive around for maybe 30 seconds before I get one instance of the problem. So, the probability is pretty low of any one call to getIntersectionWithLimitedLine() failing.

I don't think I can send you the source and 3D models - as they were created for my employer, they're not mine to send. If I get some time, I will try to make a cut-down non-IP-sensitive application and model that shows the problem. As it's now 10:30pm here, that won't be tonight.

[rogerborg]

Ah, don't sweat it, I quite understand. Thanks for reporting it: we'll nail it down sooner or later.