4
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ This should be migrated to CS.SE. $\endgroup$ – JeffE Jul 16 '13 at 17:51
  • 4
    $\begingroup$ 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. $\endgroup$ – Ivan Kuckir Jul 16 '13 at 19:38
3
$\begingroup$

The following answer is incorrect.

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*}

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ivan Kuckir Jul 16 '13 at 19:42
  • $\begingroup$ Yes, you're right. $\endgroup$ – JeffE Jul 17 '13 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.