Segment3-Rect3/Square3 intersection finding

[a-jp]

Hi,

I'm currently using your Seg3-Plane3 intersection tests, but my planes really are axis aligned faces of a 3D cube, so each is a square (not a rectangle, if that matters). Can I check that I have not missed anything and that seg3-Rect3 or seg3-Square3 are not currently implemented?

Would you have any recommendations if I'm interests in the intersections of a finite sized plane in 3D i.e. a square/rectangle with a finite length edge (segment) in 3D?

Many thanks, Andy

[davideberly]

I do not have explicit implementations in 3D for segment-rectangle. I will add those. Until I do, you can use the segment-triangle intersection code IntrSegment3Triangle3.h. Split your rectangle into 2 triangles and execute 2 segment-triangle queries.

[a-jp]

Ok, thanks for that. Yes I've just implemented that now and it seems to work as expected, I was keen to use the segment-rectangle just so I don't have to look for and delete anything that ends up in the output due to the "fake" diagonal. In my case the quads are perfectly coplanar and axis aligned. Thanks again, Andy

[davideberly]

Using segment-triangle queries, if both triangles report an intersection, then the intersection point is either exactly on the diagonal or--because of floating-point rounding errors--near the diagonal. In either case, compute the average of the two intersection points and call that the segment-rectangle intersection.

[davideberly]

I should have mentioned in my previous comment that you can have a problem if the segment intersects the rectangle in a single point but the segment-triangle queries both report no-intersection. This would be caused by floating-point rounding errors (a common problem in ray tracing a triangle mesh).

Regardless, I posted IntrLine3Rectangle3.h, IntrRay3Rectangle3.h, and IntrSegment3Rectangle3.h for test-intersection and find-intersection queries. A sample application was added to illustrate and for testing: GeometricTools/GTE/Samples/Intersection/IntersectLineRectangle. I have a brief description of this sample at my website together with some screen captures.

[a-jp]

Thank you so much for doing this. I'll try them tomorrow. Just to understand further, which point would be detected that a tri-segment would not return? Are you thinking diagonal? Thanks

[davideberly]

Yes, the problem can occur when the intersection point is nearly on the diagonal.

[a-jp]

Ok. Would it be right to say that in this instance the seg-rect is more correct to use due to the diagonal of two tris identifying an intersection when the base geometry type is indeed a planar rect?

[davideberly]

Yes. Now if you have a mesh of rectangles, the rounding errors can still cause intersections to be missed. These would occur for intersection points nearly on the common edge of two rectangles.

This is a problem that shows up in collision detection in physics simulation. An object moves towards a wall composed of triangles or rectangles. A simple way to keep the object from moving through the wall is to cast a ray from the object to the wall. If the ray intersects the wall when the object is close to the wall, you disallow the object to keep moving towards the wall. To avoid this problem, you can cast multiple rays in hopes that the majority report intersection.

[a-jp]

Could I ask two follow up questions on this:

• Would it be possible to have tri-rect intersection also?
• For my case all rects are Cartesian aligned. Are there any robustness or speed improvements to be had by using that fact?

Thanks Andy

[davideberly]

Are you asking for triangle-rectangle intersection in 3D? If so, what do you mean by "Cartesian aligned"? Are the axes of the rectangle in the set {(1,0,0),(0,1,0),(0,0,1)}.

It will be helpful if you open a new issue for this. Re-opening the current issue makes it appear as if the segment3-rectangle3 intersection issue is not yet complete. Thank you.