Add `pointInTriangle` for 3D triangles + output for barycentric coordinates

[j9liu]

This adds IntersectionTests::pointInTriangle, a 3D version of pointInTriangle2D. There is an overload that outputs the barycentric coordinates of the point, assuming the intersection is valid.

There may be a more efficient way of computing the barycentric coordinates, but my linear algebra is really rusty and I didn't want to copy + paste random code from the internet. So I went with the method I learned in college 😃

[j9liu]

Thanks for the review @csciguy8. Based on offline conversation I'm pushing back at changing the algorithm, at the moment. We aren't using it for a use case that demands the optimization. But I left a PERFORMANCE comment to be sure we remember. :)

I addressed your other comments, let me know if there are any other issues.

[timoore]

If you are going to calculate barycentric coordinates, which is a good approach to finding the intersection point, I highly recommend checking out the section on triangle - ray intersection in the Physically Based Rendering book, https://www.pbr-book.org/4ed/Shapes/Triangle_Meshes . They project everything into 2D, so the cross products give the double area directly and don't need to be normalized.

[csciguy8]

I think I have an idea to narrow the scope of this PR a bit...

The PR that depends on this looks like it doesn't really need a fast pointInTriangle test, it needs to calculate barycentric coordinates.

Given this, you may be able to:

• Leave the new pointInTriangle overload that calculates barycentric coords and if an intersection happens. Could even rename it with Barycentric somewhere in the name for clarity. In the comments, you could mention that this is not the function you would choose if performance was the highest concern.
• Remove the new pointInTriangle 3d point version completely. We don't need to worry about performance for a function that doesn't exist. We could always implement this functionality later, and could base it on the "check sides with dot product" approach, which has good performance, and is similar to our pointInTriangle 2D point logic.

In the end, we don't have to change this algorithm, nor are we leaving a performance TODO for ourselves.

[csciguy8]

Was poking around the test code and noticed a couple things:

• The 3d triangle tests are only testing tris on the XY plane (all z values are 0)
• The tests are only testing right triangles
• We should probably test degenerate tris

Also, not sure the best thing to do when the input is garbage, like equal to NaN or infinity.

[j9liu]

I think I have an idea to narrow the scope of this PR a bit...

The PR that depends on this looks like it doesn't really need a fast pointInTriangle test, it needs to calculate barycentric coordinates.

Given this, you may be able to:

• Leave the new pointInTriangle overload that calculates barycentric coords and if an intersection happens. Could even rename it with Barycentric somewhere in the name for clarity. In the comments, you could mention that this is not the function you would choose if performance was the highest concern.
• Remove the new pointInTriangle 3d point version completely. We don't need to worry about performance for a function that doesn't exist. We could always implement this functionality later, and could base it on the "check sides with dot product" approach, which has good performance, and is similar to our pointInTriangle 2D point logic.

In the end, we don't have to change this algorithm, nor are we leaving a performance TODO for ourselves.

Not trying to be contrarian on purpose.

It's common practice for us to leave PERFORMANCE_IDEA comments in our software so I think it's 100% acceptable for us to leave it as is. In no way am I defending my algorithm as 100% optimized or performant, I fully recognize that it is not.

But, as a personal admission, I would not be able to derive an algorithm from those external resources from a conceptual level. I simply cannot vouch for the code I would write as being completely derived by myself with linear algebra skills, rather than copying or taking heavy inspiration from the code you shared. These sources either do not have a license explicitly specified, or use noncommercial Creative Commons licenses, which are not compatible with Apache. (including the PBR book code that Tim linked unfortunately)

Both the licensing issues with using external resources, and the timeframe necessary for just getting this function, out there, are my main forces of resistance. I'm MORE than happy to review and accept a follow-up PR for a more optimized, license-compatible (or self-derived) implementation. I'm also willing to relearn linear algebra and recompute the algorithm by hand. But I sense that this isn't necessary for the scope of this PR, nor enough of a priority that this follow-up needs to happen ASAP.

I'm in the middle of processing your comments about unit tests, which I agree can and should be expanded. But I would like to avoid other modifications unless they are related to correctness or other points of necessity.

[timoore]

I think I have an idea to narrow the scope of this PR a bit...

But, as a personal admission, I would not be able to derive an algorithm from those external resources from a conceptual level. I simply cannot vouch for the code I would write as being completely derived by myself with linear algebra skills, rather than copying or taking heavy inspiration from the code you shared. These sources either do not have a license explicitly specified, or use noncommercial Creative Commons licenses, which are not compatible with Apache. (including the PBR book code that Tim linked unfortunately)

Just a note that algorithms aren't copyrightable. I hadn't thought about the license on the PBR code cuz I would not think to copy / paste that code, nor recommend it; it's an implementation for a raytracer and goes to a great deal of trouble to stay in fp32, which would be nice but perhaps not possible for our needs. Nevertheless, the algorithm is pretty clever. I'm pretty sure you could write the code after reading the algorithm; heavy inspiration is not at crime :smile:

[j9liu]

@csciguy8

The 3d triangle tests are only testing tris on the XY plane (all z values are 0) The tests are only testing right triangles We should probably test degenerate tris

I addressed the first two with the most recent commits.

For the third item, what do you mean by testing degenerate triangles? Testing that they work with this algorithm, or testing that they are rejected?

[csciguy8]

For the third item, what do you mean by testing degenerate triangles? Testing that they work with this algorithm, or testing that they are rejected?

Yes, and yes :) I think it's up to you as to whether you think intersections on a degenerate triangle are valid or not. Is a triangle that has degenerated into a line essentially now doing a pointInLine test? Or is a "no area" triangle not a valid object in 3d space so it should always return false?

I think the important thing is that it's known what the behavior will be (and that it doesn't crash).

[j9liu]

@csciguy8 This is ready for another look when you get the chance!

[csciguy8]

@j9liu Looks good!

I took the liberty in adding another performance comment, and also made the reverse winding test apply to all tests (so we don't need explicit tests for this).

@timoore, I saw you had one comment that wasn't resolved yet. Are you satisfied with the latest algorithm?

[timoore]

@timoore, I saw you had one comment that wasn't resolved yet. Are you satisfied with the latest algorithm?

That comment referred to an earlier version and isn't relevant anymore. Looks fine to me.