Type TKDTree Extends TColTree
		
	Method New()
	
		If LOG_NEW
			DebugLog "New TKDTree"
		EndIf
	
	End Method
	
	Method Delete()
	
		If LOG_DEL
			DebugLog "Del TKDTree"
		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

		' max levels not used

		' no minus figures
		If max_polys<0 Then max_polys=0
		If max_levels<0 Then max_levels=0
	
		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

	' creates a mesh's tree
	Method Create(polys:TPolygon[],max_polys,max_levels,level=0)
	
		level=level+1
	
		Local sort_axis
	
		If polys.length>max_polys And max_polys>0
		
			Local left_polys:TPolygon[polys.length]
			Local right_polys:TPolygon[polys.length]
			Local no_left_polys=0
			Local no_right_polys=0
			
			If w>=h And w>=d
				sort_axis=1
			Else If h>=d
				sort_axis=2
			Else
				sort_axis=3
			EndIf
	
			Local sort_val:Float
		
			For Local poly:TPolygon=EachIn polys
	
				If poly.no_verts=3
					
					Local x1:Float=poly.verts[0].x
					Local y1:Float=poly.verts[0].y
					Local z1:Float=poly.verts[0].z
					
					Local x2:Float=poly.verts[1].x
					Local y2:Float=poly.verts[1].y
					Local z2:Float=poly.verts[1].z
	
					Local x3:Float=poly.verts[2].x
					Local y3:Float=poly.verts[2].y
					Local z3:Float=poly.verts[2].z
				
					Local cx:Float = (x1+x2+x3)/3.0
					Local cy:Float = (y1+y2+y3)/3.0
					Local cz:Float = (z1+z2+z3)/3.0
					
					If sort_axis=1 Then sort_val=cx
					If sort_axis=2 Then sort_val=cy
					If sort_axis=3 Then sort_val=cz
															
					poly.sort_val=sort_val
							
				EndIf
				
			Next
			
			polys.Sort
	
			Local minx:Float=10000000
			Local miny:Float=10000000
			Local minz:Float=10000000
			Local maxx:Float=-10000000
			Local maxy:Float=-10000000
			Local maxz:Float=-10000000
			
			Local i=0
			Local half=polys.length/2
					
			For Local poly:TPolygon=EachIn polys
	
				If poly.no_verts=3
				
					i=i+1
					
					Local left_poly:TPolygon
					Local right_poly:TPolygon	
				
					If i<half
			
						left_polys[no_left_polys]=poly.Copy()
						no_left_polys:+1
						
						For Local i=0 To 2
						
							If poly.verts[i].x<minx Then minx=poly.verts[i].x
							If poly.verts[i].x>maxx Then maxx=poly.verts[i].x
							If poly.verts[i].y<miny Then miny=poly.verts[i].y
							If poly.verts[i].y>maxy Then maxy=poly.verts[i].y
							If poly.verts[i].z<minz Then minz=poly.verts[i].z
							If poly.verts[i].z>maxz Then maxz=poly.verts[i].z
						
						Next
				
					Else
					
						right_polys[no_right_polys]=poly.Copy()
						no_right_polys:+1
						
						For Local i=0 To 2
						
							If poly.verts[i].x<minx Then minx=poly.verts[i].x
							If poly.verts[i].x>maxx Then maxx=poly.verts[i].x
							If poly.verts[i].y<miny Then miny=poly.verts[i].y
							If poly.verts[i].y>maxy Then maxy=poly.verts[i].y
							If poly.verts[i].z<minz Then minz=poly.verts[i].z
							If poly.verts[i].z>maxz Then maxz=poly.verts[i].z
						
						Next
						
					EndIf
	
				EndIf
			
			Next
			
			' trim down arrays - important!
			left_polys=left_polys[..no_left_polys]
			right_polys=right_polys[..no_right_polys]

			child=child[..2]

			For i=0 To 1

				child[i]=New TKDTree
						
				Local new_minx:Float=minx
				Local new_miny:Float=miny
				Local new_minz:Float=minz
				Local new_maxx:Float=maxx
				Local new_maxy:Float=maxy
				Local new_maxz:Float=maxz
									
				child[i].w=(new_maxx-new_minx)
				child[i].h=(new_maxy-new_miny)
				child[i].d=(new_maxz-new_minz)
				
				child[i].x=new_minx+child[i].w/2.0
				child[i].y=new_miny+child[i].h/2.0
				child[i].z=new_minz+child[i].d/2.0
	
				If i=0 Then child[i].Create(left_polys,max_polys,max_levels,level)
				If i=1 Then child[i].Create(right_polys,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)

		' tree box
		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 1
						If child[i]<>Null
							polys=TKDTree(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 1
						If child[i]<>Null
							polys=TKDTree(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
