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.
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