`OrientedBox::contained` method does not contain points at some tolerances.

[Patrick Shriwise]

As I was trying to track down another issue in the OrientedBoxTreeTool last week I came across something surprising. When I add a check to the box_from_axes function that all the points used to create the oriented box are also contained by the oriented box, tests fail.

https://bitbucket.org/pshriwise/moab/commits/0e2c2c23681ea957120ade931b0028a474b4b548?at=obb_check

I added this check with a tolerance of zero. @gonuke made the valid point that there is likely some roundoff in the OrientedBox::contained method and 1 or more of these points like right on the boundary of the box, so some small tolerance would probably keep this test from failing.

While I think that's a good explanation of what's going on here, I still think that by definition one should be able to pass any point used to create the box to the OrientedBox::contained method and get a positive result, even with a zero tolerance.

My additional concern here is that the OrientedBox::intersect_ray method doesn't seem to allow for any tolerance and I'm curious if there might be rare cases where we're getting false negatives from that method.

I haven't had the chance to dive into any of this in great detail yet, so if I'm off on something here please let me know.

Had to pick a kind of issue, so I'll go with a proposal that OrientedBox's be expanded to account for the roundoff error of both the box generation, point containment check, and ray intersection.

[Iulian Grindeanu]

so how do you trigger this? just make check on this branch ? In general, we do not do “exact” arithmetic anywhere, so it can happen that a+b - a != b; tolerance 0 is not a good idea, in general; of course, there are many more operations involved in OBB, but the idea is the same

[Patrick Shriwise]

so how do you trigger this? just make check on this branch ?

Yep.

In general, we do not do “exact” arithmetic anywhere, so it can happen that a+b - a != b; tolerance 0 is not a good idea, in general; of course, there are many more operations involved in OBB, but the idea is the same

That makes sense in the case of point containment. It was just surprising to me. I might submit a PR with a note in the documentation about this for clarity if that would be useful. What’s more concerning to me is the OrientedBox::intersect_ray method. There doesn’t appear to be any tolerance parameter for ray intersections with the box, so I’m wondering if this same issue might come up in that situation. Does that sound possible?

[Iulian Grindeanu]

it is a similar problem in delaunay point insertion methods; you need to know if you are in the interior or a circle, or to the left or right of a 2d line in a plane; there are various solutions, and the only one I have some experience is Triangle
https://www.cs.cmu.edu/~quake/robust.html
my concern is that this code is old/ not maintained ?

A quick search shows many libraries that do “precision” or exact arithmetic; many are part of established libraries; boost, CGAL, etc

https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software

[Patrick Shriwise]

I don’t know that exact arithmetic is required here necessarily. I think some way for a user to ensure that they won’t get false negatives for these queries would be good as they could (in theory) lead to missed triangle intersections.