erich666
Line Segment Intersection Improvement
I refer to Volume_08/Number_1/Guigue2003/tri_tri_intersect.c and the line segment of intersection computation.
A line segment intersection endpoint can be computed as a linear combination of the Vertex endpoints. I refer to the paper here: https://cis.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf
In Figure 2, point B can be calculated as a linear combination of V10 and V11 using the already computed projected distances from plane pi2.
More precisely: B = (dv11 * V10 - dv10 * V11) / (dv11 - dv10)
This seems more efficient than the current implementation in CONSTRUCT_INTERSECTION which starts from nothing but the 6 original vertex points.
I asked Philippe Guigue and he replied: "I haven't checked this in details but I agree that is surely faster. However I doubt that it's as robust since there will be more floating point rounding errors due to the cascaded construction.
If speed is the key this would surely be an improvement."
Yes, this should indeed work! Excellent! I wished I had seen that many years ago. Should be faster. I do not have any of the testing environment so cannot test this any longer in a good way. You do not happen to have a framework where you can test for speed? Robustness: my original code involves more floating point math (both equation 3 and 4) and to compute the point B. However, for the overlap test, we also need t_1 to test for overlap on the line. Any ideas on how to compute that as well? Thanks!
To close this one off, I have added a comment to the code:
// NOTE: a faster, but possibly less precise, method of computing
// point B is described here: https://github.com/erich666/jgt-code/issues/5
#define CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) { \
If anyone is game to actually add the code, I'm happy to provide it as an #ifdef to the code - let me know.
Closing issue since there seems to be no move to add the improved code - the comment will have to suffice.