# Box and triangle intersection

I am looking for geometry algorithm.

I have an axis-aligned box $B$ and a triangle $T$ in 3D space. I want to compute an axis-aligned bounding box of their intersection.

Both $B$ and $T$ are convex polytopes and $B\cap T$ is also convex polytope. I don't need general algorithm, I need something fast and simple.

Have you heard about such an algorithm? Or is it trivial and I can't see it?

I got an idea to "crop" the triangle with each of 6 box's faces. Cropping triangle with each plane can add 1 new vertex, so the resulting object may have up to 9 vertices. Then I compute the bounding box of that object. Am I right? Can it be simplified to get only bounding box output?

• This should be migrated to CS.SE. – JeffE Jul 16 '13 at 17:51
• I solved it by cropping triangle with each of 6 planes. I use circular linked list for representing polygon. I find two edges, such that their vertices are on opposite sites of plane, find 2 intersections and edit the linked list. It works pretty fast. – Ivan Kuckir Jul 16 '13 at 19:38

Suppose the triangle has vertices $(x_1,y_1,z_1), (x_2,y_2,z_2), (x_3,y_3,z_3)$ and the box has coordinates $[x_\min, x_\max] \times [y_\min,y_\max] \times [z_\min, z_\max]$. Then the bounding box of their intersection is $[x'_\min, x'_\max] \times [y'_\min,y'_\max] \times [z'_\min, z'_\max]$, where \begin{align*} x'_\min &= \max\{\min\{x_1,x_2,x_3\}, x_\min\}, \\ x'_\max &= \min\{\max\{x_1,x_2,x_3\}, x_\max\}, \\[1ex] y'_\min &= \max\{\min\{y_1,y_2,y_3\}, y_\min\}, \\ y'_\max &= \min\{\max\{y_1,y_2,y_3\}, y_\max\}, \\[1ex] z'_\min &= \max\{\min\{z_1,z_2,z_3\}, z_\min\}, \\ z'_\max &= \min\{\max\{z_1,z_2,z_3\}, z_\max\}. \\[1ex] \end{align*}

• You are computing the intersection of B and triangle's bounding box? Your result is the superset of what I am looking for. But note, that triangle's bounding box may intersect B, but not intersect the triangle. – Ivan Kuckir Jul 16 '13 at 19:42
• Yes, you're right. – JeffE Jul 17 '13 at 14:22