Type TOctree Extends TColTree
	
	Method New()
	
		If LOG_NEW
			DebugLog "New TOctree"
		EndIf
	
	End Method
	
	Method Delete()
	
		If LOG_DEL
			DebugLog "Del TOctree"
		EndIf
	
	End Method
		
	' clears a mesh's tree
	Method ClearTree()

		For Local tree:TColTree=EachIn child
		
			tree.ClearTree()
		
		Next

		child=child[..0]
		leaf_polys=leaf_polys[..0]
		
		created=False

	End Method

	' creates a mesh's tree
	Method CreateTree(mesh:TMesh,max_polys,max_levels)

		created=True

		' no minus figures
		If max_polys<0 Then max_polys=0
		If max_levels<0 Then max_levels=0
	
		' if max_polys>0 and max_levels>0 then octree is divided until each oct cube contains less than max_polys, or has been divided max_levels times, whatever comes first
		' if max_polys>0 and max_levels=0 then octree is divided until each oct cube contains less than max_polys
		' if max_polys=0 and max_levels>0 then octree is divided until each oct cube has been divided max_levels times
		' if max_polys=0 and max_levels=0 then no division occur
	
		Local polys:TPolygon[]=TPolygon.MeshToPolygons(mesh)
	
		w=mesh.MeshWidth()
		h=mesh.MeshHeight()
		d=mesh.MeshDepth()
		x=mesh.min_x+mesh.col_tree.w/2.0
		y=mesh.min_y+mesh.col_tree.h/2.0
		z=mesh.min_z+mesh.col_tree.d/2.0

		Create(polys,max_polys,max_levels)
	
	End Method
	
	Method Create(polys:TPolygon[],max_polys,max_levels,level=0)
	
		' if max_polys<>0 and max_levels=0 then set max_levels to artificially high no. so that level<=max_levels (below) will always equal true
		If max_polys<>0 And max_levels=0 Then max_levels=100000
		
		level=level+1

		If polys.length>max_polys And level<=max_levels

			Local child_polys:TPolygon[][8]
		
			Local polys1:TPolygon[]
			Local polys2:TPolygon[]
			Local polys11:TPolygon[]
			Local polys12:TPolygon[]
			Local polys21:TPolygon[]
			Local polys22:TPolygon[]
			Local origin:TVector=TVector.Create(x,y,z)
			Local normal_x:TVector=TVector.Create(-1,0,0)
			Local normal_y:TVector=TVector.Create(0,-1,0)
			Local normal_z:TVector=TVector.Create(0,0,-1)
			Local plane_x:TPlane=TPlane.CreatePlane(origin,normal_x)
			Local plane_y:TPlane=TPlane.CreatePlane(origin,normal_y)
			Local plane_z:TPlane=TPlane.CreatePlane(origin,normal_z)
			
			TPolygon.SplitPolygons2(polys,plane_x,polys1,polys2) ' left and right
			TPolygon.SplitPolygons2(polys1,plane_y,polys11,polys12) ' left bottom, left top
			TPolygon.SplitPolygons2(polys2,plane_y,polys21,polys22) ' right bottom, right top
		
			TPolygon.SplitPolygons2(polys11,plane_z,child_polys[0],child_polys[1]) ' left bottom front, left bottom back
			TPolygon.SplitPolygons2(polys12,plane_z,child_polys[2],child_polys[3]) ' left top front, left top back
			TPolygon.SplitPolygons2(polys21,plane_z,child_polys[4],child_polys[5]) ' right bottom front, right botttom back
			TPolygon.SplitPolygons2(polys22,plane_z,child_polys[6],child_polys[7]) ' right top front, right bottom back

			child=child[..8]

			For Local i=0 To 7

				child[i]=New TOctree
				
				child[i].w=w/2.0
				child[i].h=h/2.0
				child[i].d=d/2.0
	
				Select i
				
					Case 0
					child[i].x=x-(w/4.0)
					child[i].y=y-(h/4.0)
					child[i].z=z-(d/4.0)
					Case 1
					child[i].x=x-(w/4.0)
					child[i].y=y-(h/4.0)
					child[i].z=z+(d/4.0)
					Case 2
					child[i].x=x-(w/4.0)
					child[i].y=y+(h/4.0)
					child[i].z=z-(d/4.0)
					Case 3
					child[i].x=x-(w/4.0)
					child[i].y=y+(h/4.0)
					child[i].z=z+(d/4.0)
					Case 4
					child[i].x=x+(w/4.0)
					child[i].y=y-(h/4.0)
					child[i].z=z-(d/4.0)
					Case 5
					child[i].x=x+(w/4.0)
					child[i].y=y-(h/4.0)
					child[i].z=z+(d/4.0)
					Case 6
					child[i].x=x+(w/4.0)
					child[i].y=y+(h/4.0)
					child[i].z=z-(d/4.0)
					Case 7
					child[i].x=x+(w/4.0)
					child[i].y=y+(h/4.0)
					child[i].z=z+(d/4.0)
				
				End Select
				
				child[i].Create(child_polys[i],max_polys,max_levels,level)
					
			Next
				
		Else
		
			leaf_polys=polys

		EndIf
	
	End Method
	
	' returns an array of polys from the tree that are intersecting a box (a1-a2)
	Method TreePolysBox:TPolygon[](ax1:Float,ay1:Float,az1:Float,ax2:Float,ay2:Float,az2:Float,polys:TPolygon[]=Null)

		Local bx1:Float=x-w/2.0
		Local by1:Float=y-h/2.0
		Local bz1:Float=z-d/2.0
		Local bx2:Float=x+w/2.0
		Local by2:Float=y+h/2.0
		Local bz2:Float=z+d/2.0

		Local test=BoxBoxIntersection(ax1,ay1,az1,ax2,ay2,az2,bx1,by1,bz1,bx2,by2,bz2)
		
		If test

			If leaf_polys<>Null
			
				polys=polys+leaf_polys
	
			Else

				If child<>Null
					For Local i=0 To 7
						If child[i]<>Null
							polys=TOctree(child[i]).TreePolysBox(ax1,ay1,az1,ax2,ay2,az2,polys)
						EndIf
					Next
				EndIf
				
			EndIf
			
		EndIf
		
		Return polys
			
	End Method
	
	' returns an array of polys from the tree that are intersecting a line (a-b)
	Method TreePolysLine:TPolygon[](ax:Float,ay:Float,az:Float,bx:Float,by:Float,bz:Float,polys:TPolygon[]=Null)

		' tree box
		Local xx#=x-w/2.0
		Local yy#=y-h/2.0
		Local zz#=z-d/2.0
		Local ww#=w
		Local hh#=h
		Local dd#=d
		
		Local t#
		Local px:Float,py:Float,pz:Float
		
		Local pick=TPick.IntersectSegmentAABB(ax,ay,az,bx,by,bz,xx#,yy#,zz#,ww#,hh#,dd#,t#,px,py,pz)
		
		If pick

			If leaf_polys<>Null
			
				polys=polys+leaf_polys
	
			Else

				If child<>Null
					For Local i=0 To 7
						If child[i]<>Null
							polys=TOctree(child[i]).TreePolysLine(ax,ay,az,bx,by,bz,polys)
						EndIf
					Next
				EndIf
				
			EndIf
			
		EndIf
		
		Return polys

	End Method
		
	Rem
	Method HighlightTris(polys:TPolygon[])
	
		For Local poly:TPolygon=EachIn leaf_polys
	
			Local surf:TSurface=poly.surf
			Local tri=poly.tri
	
			Local v0=surf.TriangleVertex(tri,0)
			Local v1=surf.TriangleVertex(tri,1)
			Local v2=surf.TriangleVertex(tri,2)
			
			Local nv1=debug_surf.AddVertex(surf.VertexX(v0),surf.VertexY(v0),surf.VertexZ(v0))
			Local nv2=debug_surf.AddVertex(surf.VertexX(v1),surf.VertexY(v1),surf.VertexZ(v1))
			Local nv3=debug_surf.AddVertex(surf.VertexX(v2),surf.VertexY(v2),surf.VertexZ(v2))
			
			debug_surf.AddTriangle(nv1,nv2,nv3)
	
		Next
	
	End Method
	End Rem
		
End Type
