patternMinor
Box and triangle intersection
Viewed 0 times
andtriangleboxintersection
Problem
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?
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?
Solution
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*}
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*}
Context
StackExchange Computer Science Q#13573, answer score: 3
Revisions (0)
No revisions yet.