QuadTree code

BlitzMax Forums/BlitzMax Programming/QuadTree code

JoshK(Posted 2008) [#1]
It turned out my original scenegraph idea was faster than this, so I am just posting this code and deleting it from my machine. Someone else might find it useful.

Do a search for my maths3d code for the AABB stuff.
'Strict

'Import "Maths3D.bmx"

Type TQuadTree
	Field node:TQuadTree[4]
	Field scale#
	Field x#,y#
	Field aabb:TAABB=New TAABB
	Field toplevel=1
	Field grid:TLeaf[,]
	
	Global iterations
	
	Method UpdateAABB()
		aabb.x0=x-scale*0.5
		aabb.x1=x+scale*0.5
		aabb.y0=0
		aabb.y1=20
		aabb.z0=y-scale*0.5
		aabb.z1=y+scale*0.5
		aabb.w=scale
		aabb.h=20
		aabb.d=scale
		aabb.cx=x
		aabb.cy=10
		aabb.cz=y
		aabb.updateradius()
	EndMethod
	
	Method Fill(levels)
		If toplevel
			Local grid_:TLeaf[2^(levels-1),2^(levels-1)]
			grid=grid_
		EndIf
		
		Local n
		levels:-1
		For n=0 To 3
			If levels
				node[n]=New TQuadTree
			Else
				node[n]=New TLeaf
			EndIf
			node[n].toplevel=0
			node[n].scale=scale/2.0
		Next
		node[0].x=x-scale/4
		node[0].y=y-scale/4
		node[1].x=x+scale/4
		node[1].y=y-scale/4
		node[2].x=x-scale/4
		node[2].y=y+scale/4
		node[3].x=x+scale/4
		node[3].y=y+scale/4
		For n=0 To 3
			node[n].fill(levels)			
		Next
		UpdateAABB()
	EndMethod
	
	Method EvaluatePoint:TQuadTree(x#,y#)
		If x>Self.x
			If y>Self.y
				Return node[3].EvaluatePoint(x,y)
			Else
				Return node[1].EvaluatePoint(x,y)
			EndIf
		Else
			If y>Self.y
				Return node[2].EvaluatePoint(x,y)
			Else
				Return node[0].EvaluatePoint(x,y)
			EndIf
		EndIf
	EndMethod
	
	Method AddObject:TQuadTreeNode(o:Object,x0#,z0#,x1#,z1#)
		Local qto:TQuadTreeNode
		qto=New TQuadTreeNode
		qto.o=o
		qto.x0=x0
		qto.x1=x1
		qto.z0=z0
		qto.z1=z1
		InsertNode(qto)
		If qto.links.isempty()
			qto.free()
			qto=Null
		EndIf
		Return qto
	EndMethod
	
	Method InsertNode(o:TQuadTreeNode)
		If o.x1<aabb.x0 Return
		If o.x0>aabb.x1 Return
		If o.z1<aabb.z0 Return
		If o.z0>aabb.z1 Return
		node[0].InsertNode(o)
		node[1].InsertNode(o)
		node[2].InsertNode(o)
		node[3].InsertNode(o)
	EndMethod
	
	Method DetermineVisibleLeaves:TList(camera:TCamera,List:TList=Null)
		If Not list list=New TList
		If Not camera.cullspoint(aabb.center(),aabb.radius)
			If Not camera.cullsaabb(aabb)
				node[0].DetermineVisibleLeaves(camera,list)
				node[1].DetermineVisibleLeaves(camera,list)
				node[2].DetermineVisibleLeaves(camera,list)
				node[3].DetermineVisibleLeaves(camera,list)
			EndIf
		EndIf
		Return list
	EndMethod

	Method DetermineVisibleNodes:TList(camera:TCamera,List:TList=Null)
		If toplevel iterations:+1
		If Not list list=New TList
		If Not camera.cullspoint(aabb.center(),aabb.radius)
			If Not camera.cullsaabb(aabb)
				node[0].DetermineVisibleNodes(camera,list)
				node[1].DetermineVisibleNodes(camera,list)
				node[2].DetermineVisibleNodes(camera,list)
				node[3].DetermineVisibleNodes(camera,list)
			EndIf
		EndIf
		Return list
	EndMethod
	
EndType

Type TLeaf Extends TQuadTree
	Field nodes:TList=New TList
	
	Method Fill(levels)
		UpdateAABB()
	EndMethod
	
	Method InsertNode(o:TQuadTreeNode)
		If o.x1<aabb.x0 Return
		If o.x0>aabb.x1 Return
		If o.z1<aabb.z0 Return
		If o.z0>aabb.z1 Return
		o.links.addfirst(nodes.addfirst(o))
	EndMethod

	Method DetermineVisibleLeaves:TList(camera:TCamera,List:TList=Null)
		If Not list list=New TList
		If Not camera.cullspoint(aabb.center(),aabb.radius)
			If Not camera.cullsaabb(aabb)
				list.addfirst(Self)
			EndIf
		EndIf
		Return list
	EndMethod
	
	Method DetermineVisibleNodes:TList(camera:TCamera,List:TList=Null)
		If nodes.isempty() Return
		'DrawQuadTree Self
		Local qto:TQuadTreeNode
		If Not list list=New TList
		If Not camera.cullspoint(aabb.center(),aabb.radius)
			If Not camera.cullsaabb(aabb)
				For qto=EachIn nodes
					If qto.iterations<>TQuadTree.iterations
						qto.iterations=TQuadTree.iterations
						list.addfirst(qto.o)
					EndIf
				Next
			EndIf
		EndIf
		Return list
	EndMethod

EndType

Type TQuadTreeNode
	Field o:Object
	Field links:TList=New TList
	Field x0#,z0#,x1#,z1#
	Field iterations
	
	Method Free()
		If links
			If Not links.isempty()
				For Local link:TLink=EachIn links
					link.remove()
				Next
				links=Null
			EndIf
		EndIf
	EndMethod
	
EndType

Function CreateQuadTree:TQuadTree(scale#,subdivisions)
	Local tree:TQuadTree=New TQuadTree
	tree.scale=scale
	tree.fill(subdivisions)
	tree.UpdateAABB()
	Return tree
EndFunction



plash(Posted 2008) [#2]
Shouldn't this be in the code archives and not in discussion forums?