Degenerate triangle test in pointInTriangle breaks CartographicPolygon

[kring]

A 3D point-in-triangle test was added in #826, and at the same time a test for "degenerate triangles" was added to the 2D point-in-triangle test:

// Return false for degenerate triangles.
if (glm::length2(ab) < CesiumUtility::Math::Epsilon8 ||
    glm::length2(bc) < CesiumUtility::Math::Epsilon8 ||
    glm::length2(ca) < CesiumUtility::Math::Epsilon8) {
  return false;
}

Unfortunately this breaks rectangleIsWithinPolygons and rectangleIsOutsidePolygons in CartographicPolygon, which in turn breaks the ability to filter out tiles that are entirely inside or entirely outside a clipping polygon.

These functions operate in longitude/latitude space with units of radians. They form two triangles from the bounding rectangles of the polygon and the tile, and test various points against these triangles. But in longitude/latitude radians, these triangles are very small. The length squared of their edges is significantly less than 1e-8, and so this test flags them as degenerate even though they most definitely are not.

By the way, this test won't even detect all the possible degenerate triangles. If I have three vertices arranged on a line but far apart from each other, that's a degenerate triangle but the test in this function won't detect it.

I once told someone that epsilons are the root of all evil. That's a little extreme, but only a little. 😁 One thing we can say that is definitely less extreme, though, is that a function like this, which is inherently unitless, must not have an absolute epsilon. If we knew we were working with meters, then we could maybe say "we don't care about triangles smaller than a nanometer, so we can ignore those." But if we don't know the units, we can't make any assertions like that.

A relative epsilon could be ok. Testing the vertices for equality with a relative epsilon of 1e-14 or so would be unlikely to cause a false positive.

But in my opinion, a function like this just shouldn't have a degenerate triangle test at all. Without one, the worst-case scenario is that you intermittently might detect an intersection with a triangle that is degenerate, or close to it. But you'd detect that intersection pretty much where the line or point pretending to be a triangle is actually located, so no one is likely to be surprised by that. Floating point fun could mean that a point that is not quite on the line mathematically gets flagged as being inside the "triangle", but that's no different or worse than when the same floating point fun deems a point very slightly outside a valid triangle to be inside it. On the other hand, if you add a degenerate triangle test, and it's a little too eager, you end up completely missing intersections that actually exist. That's a drastically worse situation, in my view.

[j9liu]

Oof 😬 sorry about that. I see you've self-assigned this, but I can also open a PR for this change if you'd like to focus on other things!

[csciguy8]

An algorithm that's dealing with super tiny triangles sounds a little unusual to me. But aside from that, it does sound reasonable to separate the degenerate triangle check from IntersectionTests::pointInTriangle (and possibly add more checks to it).

Also, rectangleIsWithinPolygons and rectangleIsOutsidePolygons could probably use some unit tests to catch issues like this.

[j9liu]

An algorithm that's dealing with super tiny triangles sounds a little unusual to me.

I think what @kring's saying is in reality, those "super tiny" triangles that get passed in are actually in units of longitude / latitude degrees, and take up substantial physical space. So what we consider unreasonable for the scale of a game engine is going to fail for global-scale polygons.

[kring]

I see you've self-assigned this, but I can also open a PR for this change if you'd like to focus on other things!

Thanks, but I'm still working on the other bug making polygon clipping not work right anymore, so I might as well do both at once.

Also, rectangleIsWithinPolygons and rectangleIsOutsidePolygons could probably use some unit tests to catch issues like this.

Yes yes absolutely!

[kring]

By the way, nothing to apologize about here! I wrote this novel because I thought it was worth explaining how I think about this sort of thing, because it comes up fairly often in the kind of code we write. I guess it probably came across as a little scoldy, but I didn't mean it as a scold.

An algorithm that's dealing with super tiny triangles sounds a little unusual to me.

That's the beauty of floating point numbers though, right? They can representing both enormous and tiny values equally well, with the precision being relative to the scale. We can do intersection tests against triangles the size of subatomic particles in one call, and triangles the size of galaxies in another, and everything works just fine... as long as we don't bake in any scale assumptions in the form of epsilon tests.