Overlapping cubes

Question

I'm trying to determine if two cubes overlap. I've read up on overlapping rectangles, but I'm not sure how to translate it into the third dimension.

My goal is to generate a number of randomly positioned and sized non-overlapping cubes.

These cubes are represented on a x,y,z Cartesian plane.

score 14 · Answer 1 · edited Feb 07 '21 at 06:40

The accepted answer is wrong and very confusing. Here is what I have come up with.

Determining overlap in the x plane

    if (cubeA.maxX > cubeB.minX)
    if (cubeA.minX < cubeB.maxX)

Determining overlap in the y plane

    if (cubeA.maxY > cubeB.minY)
    if (cubeA.minY < cubeB.maxY)

Determining overlap in the z plane

    if (cubeA.maxZ > cubeB.minZ)
    if (cubeA.minZ < cubeB.maxZ)

if you AND all of these conditions together and the result is true, you know that the cubes intersect at some point.

Credit: https://silentmatt.com/rectangle-intersection/

score 6 · Accepted Answer · edited Dec 22 '21 at 07:46

6

You should be able to modify Determine if two rectangles overlap each other? to your purpose fairly easily.

Suppose that you have CubeA and CubeB. Any one of 6 conditions guarantees that no overlap can exist:

Cond1.  If A's left face is to the right of the B's right face,
           -  then A is Totally to right Of B
              CubeA.X2 < CubeB.X1
Cond2.  If A's right face is to the left of the B's left face,
           -  then A is Totally to left Of B
              CubeB.X2 < CubeA.X1
Cond3.  If A's top face is below B's bottom face,
           -  then A is Totally below B
              CubeA.Z2 < CubeB.Z1
Cond4.  If A's bottom face is above B's top face,
           -  then A is Totally above B
              CubeB.Z2 < CubeA.Z1
Cond5.  If A's front face is behind B's back face,
           -  then A is Totally behind B
              CubeA.Y2 < CubeB.Y1
Cond6.  If A's left face is to the left of B's right face,
           -  then A is Totally to the right of B
              CubeB.Y2 < CubeA.Y1

So the condition for no overlap is:

Cond1 or Cond2 or Cond3 or Cond4 or Cond5 or Cond6

Therefore, a sufficient condition for Overlap is the opposite (De Morgan)

Not Cond1 AND Not Cond2 And Not Cond3 And Not Cond4 And Not Cond5 And Not Cond6

edited Dec 22 '21 at 07:46

Thorarin

47,289
11
75
111

answered Feb 15 '11 at 21:14

btilly

43,296
3
59
88

what do you mean by edges?, maybe faces? – Dave O. Feb 16 '11 at 00:56
Does your algorithm assume that the cubes are axis-aligned? Sry for bothering you^^ – Dave O. Feb 16 '11 at 02:58
@Dave, it does. As did the answers to the previous question. If that assumption is wrong, the problem becomes more complex to solve. – btilly Feb 16 '11 at 04:39
Noone probably noticed, but there was an error in the post's Cond5. It reads "CubeA.Y1 < CubeB.Y2" but should read "CubeA.Y2 < CubeB.Y1" – Istrebitel Sep 08 '16 at 10:13
Yeah, and stack overflow "edit review" brigade rejected my edit on the matter because it's "Addressed to the author". Yeah, good job. Let's leave a WRONG answer marked as correct one staying as it is! – Istrebitel Sep 08 '16 at 14:55
@Istrebitel Thank you for pointing out the error, but you didn't quite have the right fix. I fixed it properly. – btilly Sep 08 '16 at 15:24
@btilly are you sure? I am still seing cond5 being "CubeB.Y2 < CubeA.Y1" and cond6 being " CubeB.Y2 < CubeA.Y1", which is erroneous. It's the same condition twice, how can it be correct? – Istrebitel Sep 29 '16 at 12:50
@Istrebitel I just fixed 6. – btilly Sep 29 '16 at 18:10
@btilly but you have just duplicated the condition 2, have you not? look! – Istrebitel Nov 21 '16 at 20:08
1

this is still not fixed, ridiculous – Istrebitel Dec 10 '16 at 09:39
what if cubeA contains cubeB or vice versa? – shinxg Feb 21 '19 at 07:07
@shinxg Then none of the conditions will match. :-) – btilly Feb 21 '19 at 19:42
4

@Istrebitel I finally fixed it for you, thanks to https://adventofcode.com/2021/day/22 :) – Thorarin Dec 22 '21 at 15:16

score 3 · Answer 3 · answered Feb 15 '11 at 21:18

3

Cubes are made up of 6 rectangular (okay, square) faces.

Two cubes do not intersect if the following conditions are met.

None of the faces of 2 cubes intersect.
One cube does not completely contain the other.

The post you linked can be easily extended. Just add Z.

answered Feb 15 '11 at 21:18

nmichaels

49,466
12
107
135

+1 easily implemented if you already have code that tests case 1 – Dave O. Feb 16 '11 at 02:59
2

Just a side note...cube A completely contains cube B if cube A contains any vertex of cube B. You need only check one vertex of each cube for containment in the other cube; if the cube faces don't intersect, then either none of the vertices will be contained, or they all will be. – jprete Feb 16 '11 at 22:09

score 1 · Answer 4 · answered Feb 16 '11 at 21:44

1

I suppose (did not think much, maybe my condition is not enough) check if all the vertices of first cube are out of the second and inverse: all vertices of second are out of the first.

To check if the vertex is in the cube or not, transform it's coordinates to cube-related coordinate system (apply translation to the cube center and cube rotation). Then simply check each coord (x, y, z) is smaller then half a side

answered Feb 16 '11 at 21:44

Andrew

24,218
13
61
90

1

That condition is not enough, because all the vertices of each cube can be out of the other and yet they still intersect (for example, if cube A is a slightly-rotated copy of cube B, you should be able to arrange them so that the above condition is true but they still intersect). – jprete Feb 16 '11 at 22:07

tink · Answer 5 · 2018-12-11T06:18:04.520

This is just the accepted answer rewritten with the correction. It tests to see if the two axis aligned cuboids have any segment of the X,Y, and Z axis in common, if they dont then it is impossible for them to have a collision. The function assumes there is a collision and performs the tests to check if there isnt.

Function func_Intersect(ByVal cuboid1_MinX As Double, ByVal cuboid1_MaxX As Double, ByVal cuboid1_MinY As Double, ByVal cuboid1_MaxY As Double, ByVal cuboid1_MinZ As Double, ByVal cuboid1_MaxZ As Double, ByVal cuboid2_MinX As Double, ByVal cuboid2_MaxX As Double, ByVal cuboid2_MinY As Double, ByVal cuboid2_MaxY As Double, ByVal cuboid2_MinZ As Double, ByVal cuboid2_MaxZ As Double) As Boolean
    func_Intersect = True
    If cuboid1_MaxX < cuboid2_MinX Then
        func_Intersect = False
    ElseIf cuboid2_MaxX < cuboid1_MinX Then
        func_Intersect = False
    ElseIf cuboid1_MaxY < cuboid2_MinY Then
        func_Intersect = False
    ElseIf cuboid2_MaxY < cuboid1_MinY Then
        func_Intersect = False
    ElseIf cuboid1_MaxZ < cuboid2_MinZ Then
        func_Intersect = False
    ElseIf cuboid2_MaxZ < cuboid1_MinZ Then
        func_Intersect = False
    End If
End Function

Overlapping cubes

5 Answers5