Search for the total volume of two overlapping cuboids

Question

What is the most efficient way to find the shared space occupied by two overlapping cube objects?

I'm not necessarily looking for source code, just a general idea on how to solve it.

For simplicity, the algorithm should not take spinning cubes into account.

Answer 1

Overlaying two non-rotating cubes is still a box. If the two corner points of the box A (x, y, z) and (x ', y', z ') (x'> x, y '> y, z'> z) and the two corner points of the box B are (a, b, c) and (a ', b', c ') (a'> a, b '> b, c'> c), then the overlap volume is

max(min(a',x')-max(a,x),0) * max(min(b',y')-max(b,y),0) * max(min(c',z')-max(c,z),0) 

How to read the formula:

The overlay occurs on the X axis at the maximum of the two coordinates x and a and ends at least on a and x. If the value is <x (i.e., a <a '<x <x'), then there is no overlap, and what happens is that max (a, x) = x> min (a ', x') = a ', therefore, the difference becomes negative, and the volume is equal to zero (therefore, the external max (..., 0)). The same applies to the other two axes.

Answer 2

If the cubes are not rotated (aligned along the axis), overlapping dimensions are sufficient to describe the overlap of the cubes.

Consider the problem in two dimensions:

  ________ | S2 | ____|___ | | | | | | |___|____| | S1 | |________| 

The overlap area is described by the width S1.xmax - S2.xmin and the height S1.ymax - S2.ymin. Several if tests are required to determine the subtraction order. You may find that there are no matches. To do this for cubes, consider the dimension z in addition to x and y.

Answer 3

Calculate min / max in each dimension of each of your cubes, and then test them against each other, for example. in the x direction, where the cubes are labeled 1 and 2

 XminInt; if ( Xmin1 > Xmax2 ) { // no intersection } else if ( Xmin1 >= Xmin2 ) { // possible cube intersection XminInt = Xmin1; } else if ( Xmin2 <= Xmax1 ) { // possible cube intersection XminInt = Xmin2; } 

Do something similar for max and repeat for both y and z. If you hit a single intersection in any of them, you can exit early. If you do not leave early in any of the six possible early exit offers, you will receive all six defining values ​​for the intersection cube ie Min / max for each dimension.

The six early returns are the simplest example of a dividing axis method. Since your shapes are cubed and aligned along the axis, the Cartesian axes are the possible separation axes. Testing is just a matter of comparing min / max values, as stated above.

Please note that I have implemented the above method in C ++ and confirmed that it works.