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?

Thanks in advance

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 > 0:
				positive = positive + 1
			elif t < 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]) > 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]) > 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) < 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