Intersection of Cartesian Box and Polygon in 3D

Question

I am looking for a method and/or library in C++ to check if a convex polygon (defined by 4 or more points in 3D) intersect one or more cartesian boxes (defined by xmin, xmax, ymin, ymax, zmin and zmax).

The context: I have a cartesian grid (finite element), and I need to check which boxes are crossed by an arbitrary polygon.

I believe if I find a function/algorithm that computes the intersection of two polygons in 3D, the problem is solved. I can individually check against each of the box faces.

I looked into OpenCV intersectConvexConvex, but it doesn't seem to handle 3D polygons (Polygons with planar points but in 3D space).

Any suggestions?

Answer 1

A polygon in 3D space defines a plane.

Find the intersection of that plane with all of the boxes. The intersections, if there are any, will also be convex polygons, so the problem is thus reduced to 2D polygon-polygon intersection.

You can find the intersection of a plane and a box by just finding the plane-line segment intersections of all the edges of the box and finding the convex hull of those points.