# Detecting intersection of bounding boxes

Hi,

I’m writing a python script which dynamically builds a scene from a series of components.

What it does is choose the next object its going to add, copy it into the scene and calculate a translation matrix (which it will later set). Unfortunately sometimes my objects end up trying to occupy the same physical space.

Thus I’d like to calculate if the bounding box of my “current” object intersects with the bounding box of another object in the scene. My problem is … I’m not sure how. Does anyone have any pointers, sample code, webpages etc which can help me find a solution which detects if two 3D boxes intersect one another?

Rich

there is Mesh.pointInside() which you could use to to check if the eight corners of your new objects’ bounding box would be within another mesh or you might check http://en.wikipedia.org/wiki/Bounding_volume#Basic_intersection_checks

as far as I know the Blender API does not provide a bounding box to bounding box intersection test

Cheers, a bit of searching and I turned up some pseudo code for the “separating axis” method.

So having just implemented it in python/blender so I thought I’d share.

Enjoy

Rich

``````
import bpy
import Blender

class BoundingEdge:
def __init__(self,v0,v1):
self.vertex = (v0,v1)
self.vector = v1 - v0

class BoundingFace:
def __init__(self,v0,v1,v2):
self.vertex = (v0,v1,v2)
self.normal = Blender.Mathutils.TriangleNormal(v0,v1,v2)

class BoundingBox:
def __init__(self,ob):
self.vertex = ob.getBoundBox()
if self.vertex != None:
self.edge = [BoundingEdge(self.vertex[0],self.vertex[1]),
BoundingEdge(self.vertex[1],self.vertex[2]),
BoundingEdge(self.vertex[2],self.vertex[3]),
BoundingEdge(self.vertex[3],self.vertex[0]),
BoundingEdge(self.vertex[4],self.vertex[5]),
BoundingEdge(self.vertex[5],self.vertex[6]),
BoundingEdge(self.vertex[6],self.vertex[7]),
BoundingEdge(self.vertex[7],self.vertex[4]),
BoundingEdge(self.vertex[0],self.vertex[4]),
BoundingEdge(self.vertex[1],self.vertex[5]),
BoundingEdge(self.vertex[2],self.vertex[6]),
BoundingEdge(self.vertex[3],self.vertex[7])]
self.face = [BoundingFace(self.vertex[0],self.vertex[1],self.vertex[3]),
BoundingFace(self.vertex[0],self.vertex[4],self.vertex[1]),
BoundingFace(self.vertex[0],self.vertex[3],self.vertex[4]),
BoundingFace(self.vertex[6],self.vertex[5],self.vertex[7]),
BoundingFace(self.vertex[6],self.vertex[7],self.vertex[2]),
BoundingFace(self.vertex[6],self.vertex[2],self.vertex[5])]

def whichSide(self,vtxs,normal,faceVtx):
retVal = 0
positive = 0
negative = 0
for v in vtxs:
t = normal.dot(v - faceVtx)
if t &gt; 0:
positive = positive + 1
elif t &lt; 0:
negative = negative + 1

if positive != 0 and negative != 0:
return 0

if positive != 0:
retVal = 1
else:
retVal = -1
return retVal

# Taken from: http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf
def intersect(self,bb):
retVal = False
if self.vertex != None and bb.vertex != None:
# check all the faces of this object for a seperation axis
for i, f in enumerate(self.face):
d = f.normal
if self.whichSide(bb.vertex,d,f.vertex[0]) &gt; 0:
return False # all the vertexes are on the +ve side of the face

# now do it again for the other objects faces
for i, f in enumerate(bb.face):
d = f.normal
if self.whichSide(self.vertex,d,f.vertex[0]) &gt; 0:
return False # all the vertexes are on the +ve side of the face

# do edge checks
for e1 in self.edge:
for e2 in bb.edge:
d = e1.vector.cross(e2.vector)
side0 = self.whichSide(self.vertex,d,e1.vertex[0])
if side0 == 0:
continue
side1 = self.whichSide(bb.vertex,d,e1.vertex[0])
if side1 == 0:
continue

if (side0 * side1) &lt; 0:
return False

retVal = True
return retVal

sce = bpy.data.scenes.active

tOb = sce.objects.active
tObBb = BoundingBox(tOb)
for ob in sce.objects:
if ob != tOb:
print "intersects: %u" % tObBb.intersect(BoundingBox(ob))

``````

the code starts of very promising but is apparently too long to fit in a single code block. Could you post again and divide the code in chunks ? (or put it on some website if that is possible and point to it)

cheers