5
\$\begingroup\$

What is the most efficient way for finding out the vertices of the polyhedron formed by the overlapping area of two rotated 3D boxes?

If it is still confusing what I mean by "polyhedron formed by...", see the picture below:

enter image description here

Of course, in that picture the boxes are still not rotated*.

But imagine I rotate both. I would like to identify the vertices that form the inner area of the overlapping.

What is the less expensive way for doing so? (I'm using C#, but can read C++ well).

*The picture comes from a blog post that teaches how to get the overlapping area of two 3D AABBs: http://blog.meltinglogic.com/2015/04/aabb-overlapping-area/

\$\endgroup\$
3
\$\begingroup\$

In the end, here it goes in detail the way I myself figured out to get what I've asked (also inspired by @snake5's comments):

1a) for each of the 12 edges (line-segments) of one box, we test first if it is entirely within the other box. If it is, we already save its both vertices in the final list of vertices that form the desired polyhedron.

1b) if it is not, then we test if such edge pierces (intersects) one or two of all the 6 faces (planes) of the other box (it can't intersect more than two faces). If any intersections exist, we save the intersection point or points (vector3) in the final list of vertices that form the desired polyhedron.

2) then, for these edges (line-segments) which intersected the other box, we take their two vertices and test if they are inside the other box. The ones that are must be also saved in the final list of vertices that form the desired polyhedron.

Although I am not sure whether that's the most efficient way of solving the problem, so far it does not seem too bad performance-wise: the first step, in the unlikely worst case, has to perform 144 line-segment/plane intersection tests and 8 line-segment/plane calculations of intersection points. The second step, in the worst case, has to perform 16 point-within-box test.

In case anyone has any ideas for optimizing that, feel more than welcome to comment that I will update the answer. Or if someone comes up with a better solution, I encourage to put a better answer: I will be glad to uncheck this as the accepted answer. I myself, if this solution proves too heavy, will come back and put a follow up question.

\$\endgroup\$
1
\$\begingroup\$

In an intersection, all of the surface planes involved form a new shape defined by these planes.

To find the points, formally there's vertex enumeration. However, I find it easier to just skip all math theory and do 4 nested loops over the planes, intersection of the first two planes gives a straight line/ray, which is checked against the third to obtain a point, which then has to be checked if it's inside the shape (= it's behind every plane).

All generated points that pass the test are the vertices of the polyhedron. In practice though, remember that there has to be some room for numerical errors (merge similar points and allow for some bias when projecting points on plane axes).

There's also another implementation of vertex enumeration that I could find, perhaps it can help: http://library.wolfram.com/infocenter/MathSource/440/

\$\endgroup\$
  • \$\begingroup\$ Hi, sorry for the late feedback. Many thanks for your answer. I am not sure your second suggestion is the most efficient way. I didn't quite get what you are suggesting. Why should I need to get a straight line/ray between intersecting planes? See my own answer: wouldn't it just be the case of getting the intersection points of the edges of a Box with the planes of the faces of the other box plus the vertices that inside any of the boxes? \$\endgroup\$ – MAnd Nov 13 '15 at 7:23
  • \$\begingroup\$ Also, I am very much interested in learning how do you think vertex enumeration could be directly applied to the current problem. Thanks again! \$\endgroup\$ – MAnd Nov 13 '15 at 7:23
  • \$\begingroup\$ @MAnd My suggestion assumes there is nothing else, just planes. And the way to implement 3 plane intersection is by starting with two of them and using the result (straight line/ray) for the third. If you have edges and you trust your edge set to contain the necessary data, the first step can be skipped. As for vertex enumeration, it is simply the name of this problem. And it's way too academically described in the available literature for me to have any idea how the suggested solutions work there, so I can't help much with that. \$\endgroup\$ – snake5 Nov 13 '15 at 7:48

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.