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
|