Type TOctree

	Field x#,y#,z# ' mid point of oct cube
	Field w#,h#,d#

	Field oct_child:TOctree[8]
	Field oct_polys:TPolygon[]
	
	' debug fields
	Global no_polys_mesh=0 ' no of polys before octree created
	Global no_polys_octree=0 ' no of polys after octree created
	Global no_polys_active=0 ' no of active polys
	
	' MiniB3D functions
	
	' Internal - not recommended for general use
	
	' creates a mesh's octree
	Function CreateOctree(mesh:TMesh,max_polys,max_levels)
	
		' 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 error
		If max_polys=0 And max_levels=0 Then RuntimeError "Octree cannot be created - max_polys or max_levels must be greater than 0"
	
		Local polys:TPolygon[]=TPolygon.MeshToPolygons(mesh)
		
		mesh.octree:TOctree=New TOctree
		
		mesh.octree.w=mesh.MeshWidth()
		mesh.octree.h=mesh.MeshHeight()
		mesh.octree.d=mesh.MeshDepth()
		mesh.octree.x=mesh.min_x+mesh.octree.w/2.0
		mesh.octree.y=mesh.min_y+mesh.octree.h/2.0
		mesh.octree.z=mesh.min_z+mesh.octree.d/2.0

		mesh.octree.Create(polys,max_polys,max_levels)
		
		mesh.octree.no_polys_mesh=polys.length
	
	End Function
	
	' returns true if, from an array of polys, more than limit triangles are referenced
	Method TestTris(polys:TPolygon[],limit=50)

		' if limit=0 then return true immediately, we don't want to test tris
		If limit=0 Then Return True

		Local tris[limit]
		Local i=0
		
		For Local poly:TPolygon=EachIn polys
		
			Local tri=poly.tri
			
			Local ref_exists=False
			For Local check_ref=0 To i
				If tris[check_ref]=tri Then ref_exists=True
			Next
			
			If ref_exists=False
			
				tris[i]=tri
				i=i+1
				
			EndIf
			
			If i>=limit Then Exit
			
		Next

		If i>=limit Return True Else Return False

	End Method

	' returns, from an array of polys, no. of triangles referenced
	Method CountTris(polys:TPolygon[],limit=500)

		Local tris[limit]
		Local i=0
		
		For Local poly:TPolygon=EachIn polys
		
			Local tri=poly.tri
			
			Local ref_exists=False
			For Local check_ref=0 To i
				If tris[check_ref]=tri Then ref_exists=True
			Next
			
			If ref_exists=False
			
				tris[i]=tri
				i=i+1
				
			EndIf
			
			If i>=limit Then Exit
			
		Next

		Return i

	End Method

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

		If TestTris(polys,max_polys)=True 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.SplitPolygons(polys,plane_x,polys1,polys2) ' left and right
			TPolygon.SplitPolygons(polys1,plane_y,polys11,polys12) ' left bottom, left top
			TPolygon.SplitPolygons(polys2,plane_y,polys21,polys22) ' right bottom, right top
		
			TPolygon.SplitPolygons(polys11,plane_z,child_polys[0],child_polys[1]) ' left bottom front, left bottom back
			TPolygon.SplitPolygons(polys12,plane_z,child_polys[2],child_polys[3]) ' left top front, left top back
			TPolygon.SplitPolygons(polys21,plane_z,child_polys[4],child_polys[5]) ' right bottom front, right botttom back
			TPolygon.SplitPolygons(polys22,plane_z,child_polys[6],child_polys[7]) ' right top front, right bottom back

			For Local i=0 To 7
			
				oct_child[i]=New TOctree
				
				oct_child[i].w=w/2.0
				oct_child[i].h=h/2.0
				oct_child[i].d=d/2.0
	
				Select i
				
					Case 0
					oct_child[i].x=x-(w/4.0)
					oct_child[i].y=y-(h/4.0)
					oct_child[i].z=z-(d/4.0)
					Case 1
					oct_child[i].x=x-(w/4.0)
					oct_child[i].y=y-(h/4.0)
					oct_child[i].z=z+(d/4.0)
					Case 2
					oct_child[i].x=x-(w/4.0)
					oct_child[i].y=y+(h/4.0)
					oct_child[i].z=z-(d/4.0)
					Case 3
					oct_child[i].x=x-(w/4.0)
					oct_child[i].y=y+(h/4.0)
					oct_child[i].z=z+(d/4.0)
					Case 4
					oct_child[i].x=x+(w/4.0)
					oct_child[i].y=y-(h/4.0)
					oct_child[i].z=z-(d/4.0)
					Case 5
					oct_child[i].x=x+(w/4.0)
					oct_child[i].y=y-(h/4.0)
					oct_child[i].z=z+(d/4.0)
					Case 6
					oct_child[i].x=x+(w/4.0)
					oct_child[i].y=y+(h/4.0)
					oct_child[i].z=z-(d/4.0)
					Case 7
					oct_child[i].x=x+(w/4.0)
					oct_child[i].y=y+(h/4.0)
					oct_child[i].z=z+(d/4.0)
				
				End Select
				
				oct_child[i].Create(child_polys[i],max_polys,max_levels,level)
					
			Next
				
		Else
		
			oct_polys=polys
			no_polys_octree=no_polys_octree+polys.length
	
		EndIf
	
	End Method

	Method OctPick(a:TVector,b:TVector,mesh:TMesh,t_min# Var,t_min2# Var)
	
		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 p:TVector
		
		Local pick=TPick.IntersectSegmentAABB(a,b,xx#,yy#,zz#,ww#,hh#,dd#,t#,p)
			
		If pick
		
			If t#<t_min2#

				If oct_polys<>Null
				
					Local pick=TPick.PickPolys(a,b,oct_polys,mesh,t_min#)
					
					If pick=True
						t_min2#=t#
					EndIf
				
				Else
	
					For Local i=0 To 7
						If oct_child[i]<>Null
							oct_child[i].OctPick(a,b,mesh,t_min#,t_min2#)
						EndIf
					Next
					
				EndIf

			EndIf
			
		EndIf
			
	End Method
	
	Method OctCollision(collisionPackage:TCollisionPacket)

		Local a:AABB=collisionPackage.bb
		
		Local b:AABB=New AABB
		b.mini[0]=x-w/2.0
		b.maxi[0]=x+w/2.0
		b.mini[1]=y-h/2.0
		b.maxi[1]=y+h/2.0
		b.mini[2]=z-d/2.0
		b.maxi[2]=z+d/2.0

		Local test=AABB.AABBAABBIntersection(a,b)
		
		If test

			If oct_polys<>Null
			
				no_polys_active=no_polys_active+oct_polys.length
				'HighlightTris(oct_polys)
				TCollision.PolysCheckCollision(collisionPackage:TCollisionPacket,oct_polys)
		
			Else

				For Local i=0 To 7
					If oct_child[i]<>Null
						oct_child[i].OctCollision(collisionPackage:TCollisionPacket)
					EndIf
				Next
				
			EndIf
			
		EndIf
			
	End Method
	
	Method HighlightTris(polys:TPolygon[])
	
		For Local poly:TPolygon=EachIn oct_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)
	
			VertexColor surf,v0,255,0,0
			VertexColor surf,v1,255,0,0
			VertexColor surf,v2,255,0,0
	
		Next
	
	End Method
	
End Type
