HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Box and triangle intersection

Submitted by: @import:stackexchange-cs··
0
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?

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

Context

StackExchange Computer Science Q#13573, answer score: 3

Revisions (0)

No revisions yet.