Type TPolygon

	Field no_verts
	
	Field array_size=1
	Field verts:TVector[array_size]
	
	Field surf:TSurface=Null
	Field tri ' tri no
	
	' MiniB3D functions
	
	' Internal - not recommended for general use
	
	Function MeshToPolygons:TPolygon[](mesh:TMesh)
	
		Local no_polys=0
	
		Local s,surf:TSurface
	
		For s=1 To mesh.CountSurfaces()
	
			surf:TSurface=mesh.GetSurface(s)
	
			no_polys=no_polys+surf.CountTriangles()
	
		Next
		
		Local polys:TPolygon[no_polys]
		Local poly_no=0
	
		For s=1 To mesh.CountSurfaces()
	
			surf:TSurface=mesh.GetSurface(s)
	
			For Local t=0 Until surf.CountTriangles()
			
				Local v0=surf.TriangleVertex(t,0)
				Local v1=surf.TriangleVertex(t,1)
				Local v2=surf.TriangleVertex(t,2)
				
				polys:TPolygon[poly_no]=New TPolygon
	
				polys[poly_no].AddVertex(TVector.Create(surf.VertexX(v0),surf.VertexY(v0),surf.VertexZ(v0)))
				polys[poly_no].AddVertex(TVector.Create(surf.VertexX(v1),surf.VertexY(v1),surf.VertexZ(v1)))
				polys[poly_no].AddVertex(TVector.Create(surf.VertexX(v2),surf.VertexY(v2),surf.VertexZ(v2)))
				polys[poly_no].surf=surf
				polys[poly_no].tri=t
				
				poly_no=poly_no+1
				
			Next
	
		Next
		
		Return polys
		
	End Function

	Function SplitPolygons(polys:TPolygon[],plane:TPlane,front_polys:TPolygon[] Var,back_polys:TPolygon[] Var)
	
		Local no_front_polys=0
		Local no_back_polys=0
	
		For Local poly:TPolygon=EachIn polys
	
			Local front_poly:TPolygon
			Local back_poly:TPolygon
	
			' if tri intersects plane
			SplitPolygon(poly,plane,front_poly,back_poly)
		
			If front_poly<>Null
		
				If no_front_polys>=front_polys.length
					If no_front_polys<>0
						front_polys=front_polys[..no_front_polys*2]
					Else
						front_polys=front_polys[..1]
					EndIf
				EndIf
				front_polys[no_front_polys]=front_poly
				no_front_polys:+1
	
			EndIf
			
			If back_poly<>Null
		
				If no_back_polys>=back_polys.length
					If no_back_polys<>0
						back_polys=back_polys[..no_back_polys*2]
					Else
						back_polys=back_polys[..1]
					EndIf
				EndIf
				back_polys[no_back_polys]=back_poly
				no_back_polys:+1
				
			EndIf
				
		Next
		
		' convert quad polys to tris	
		front_polys=TPolygon.QuadToTris(front_polys)
		back_polys=TPolygon.QuadToTris(back_polys)
	
	End Function

	Function SplitPolygons2(polys:TPolygon[],plane:TPlane,front_polys:TPolygon[] Var,back_polys:TPolygon[] Var)
	
		Local no_front_polys=0
		Local no_back_polys=0
	
		For Local poly:TPolygon=EachIn polys
	
			Local front_poly:TPolygon
			Local back_poly:TPolygon
	
			' if tri intersects plane
			SplitPolygon2(poly,plane,front_poly,back_poly)
		
			If front_poly<>Null
		
				If no_front_polys>=front_polys.length
					If no_front_polys<>0
						front_polys=front_polys[..no_front_polys*2]
					Else
						front_polys=front_polys[..1]
					EndIf
				EndIf
				front_polys[no_front_polys]=front_poly
				no_front_polys:+1
	
			EndIf
			
			If back_poly<>Null
		
				If no_back_polys>=back_polys.length
					If no_back_polys<>0
						back_polys=back_polys[..no_back_polys*2]
					Else
						back_polys=back_polys[..1]
					EndIf
				EndIf
				back_polys[no_back_polys]=back_poly
				no_back_polys:+1
				
			EndIf
				
		Next
		
		' convert quad polys to tris	
		front_polys=TPolygon.QuadToTris(front_polys)
		back_polys=TPolygon.QuadToTris(back_polys)
	
	End Function

	Function SplitPolygon(poly:TPolygon,plane:TPlane,front_poly:TPolygon Var,back_poly:TPolygon Var)
	
		Const MAX_POINTS=10
	
		Local numFront=0,numBack=0
		Local frontVerts:TVector[MAX_POINTS]
		Local backVerts:TVector[MAX_POINTS]
	
		' Test all edges (a, b) starting with edge from last to first vertex
		Local numVerts=poly.no_verts
		Local a:TVector=poly.GetVertex(numVerts-1)
		Local aSide=plane.ClassifyPointToPlane(a)
		
		' Loop over all edges given by vertex pair (n-1, n)
		For Local n=0 Until numVerts
		
			Local b:TVector=poly.GetVertex(n)
			Local bSide=plane.ClassifyPointToPlane(b)
			
			If bSide=TPlane.POINT_IN_FRONT_OF_PLANE
			
				If aSide=TPlane.POINT_BEHIND_PLANE
				
					' Edge (a, b) straddles, output intersection point to both sides
					' Consistently clip edge as ordered going from in front -> behind
					Local i:TVector=TPlane.IntersectEdgeAgainstPlane(b,a,plane)
					If plane.ClassifyPointToPlane(i)<>TPlane.POINT_ON_PLANE Then DebugStop
					numFront:+1
					numBack:+1
					frontVerts[numFront]=i
					backVerts[numBack]=i
					
				EndIf
				
				' In all three cases, output b to the front side
				numFront:+1
				frontVerts[numFront]=b
				
			Else If bSide=TPlane.POINT_BEHIND_PLANE
			
				If aSide=TPlane.POINT_IN_FRONT_OF_PLANE
				
					' Edge (a, b) straddles, output intersection point to both sides
					Local i:TVector=TPlane.IntersectEdgeAgainstPlane(a,b,plane)
					If plane.ClassifyPointToPlane(i)<>TPlane.POINT_ON_PLANE Then DebugStop
					numFront:+1
					numBack:+1
					frontVerts[numFront]=i
					backVerts[numBack]=i
					
				Else If aSide=TPlane.POINT_ON_PLANE
				
					' Output a when edge (a,b) goes from 'on' to 'behind' plane
					numBack:+1
					backVerts[numBack]=a
					
				EndIf
				
				' In all three cases, output b to the back side
				numBack:+1
				backVerts[numBack]=b
				
			Else
			
				' b is on the plane. In all three cases output b to the front side
				numFront:+1
				frontVerts[numFront]=b
				
				' in one case, also output b to the backside
				If aSide=TPlane.POINT_BEHIND_PLANE
					numBack:+1
					backVerts[numBack]=b
				EndIf
				
			EndIf
			
			a=b
			aSide=bSide
				
		Next
		
		front_poly=TPolygon.CreateFromPoints(frontVerts)
		back_poly=TPolygon.CreateFromPoints(backVerts)
		
		If front_poly<>Null
			front_poly.surf=poly.surf
			front_poly.tri=poly.tri
		EndIf
		If back_poly<>Null
			back_poly.surf=poly.surf
			back_poly.tri=poly.tri
		EndIf
	
	End Function
	
	Function SplitPolygon2(poly:TPolygon,plane:TPlane,front_poly:TPolygon Var,back_poly:TPolygon Var)
	
		Const MAX_POINTS=10
	
		Local numFront=0,numBack=0
		Local frontVerts:TVector[MAX_POINTS]
		Local backVerts:TVector[MAX_POINTS]
	
		' Test all edges (a, b) starting with edge from last to first vertex
		Local numVerts=poly.no_verts
		Local a:TVector=poly.GetVertex(numVerts-1)
		Local aSide=plane.ClassifyPointToPlane(a)
		
		Local front=False
		Local back=False
		
		' Loop over all edges
		For Local n=0 Until numVerts
		
			Local a:TVector=poly.GetVertex(0)
			Local b:TVector=poly.GetVertex(1)
			Local c:TVector=poly.GetVertex(2)
		
			Local aSide=plane.ClassifyPointToPlane(a)
			Local bSide=plane.ClassifyPointToPlane(b)
			Local cSide=plane.ClassifyPointToPlane(c)
			
			If aSide=TPlane.POINT_IN_FRONT_OF_PLANE Or aSide=TPlane.POINT_ON_PLANE
				front=True
			EndIf
			If bSide=TPlane.POINT_IN_FRONT_OF_PLANE Or bSide=TPlane.POINT_ON_PLANE
				front=True
			EndIf
			If cSide=TPlane.POINT_IN_FRONT_OF_PLANE Or cSide=TPlane.POINT_ON_PLANE
				front=True
			EndIf
			
			If aSide=TPlane.POINT_BEHIND_PLANE Or aSide=TPlane.POINT_ON_PLANE
				back=True
			EndIf
			If bSide=TPlane.POINT_BEHIND_PLANE Or bSide=TPlane.POINT_ON_PLANE
				back=True
			EndIf
			If cSide=TPlane.POINT_BEHIND_PLANE Or cSide=TPlane.POINT_ON_PLANE
				back=True
			EndIf
			
			If front=True And back=True Then Exit
							
		Next
		
		If front=True
			front_poly=poly.Copy()
		EndIf
		
		If back=True
			back_poly=poly.Copy()
		EndIf
		
		If front_poly<>Null
			front_poly.surf=poly.surf
			front_poly.tri=poly.tri
		EndIf
		If back_poly<>Null
			back_poly.surf=poly.surf
			back_poly.tri=poly.tri
		EndIf
	
	End Function
	
	Function CreateFromPoints:TPolygon(points:TVector[])
	
		Local poly:TPolygon=New TPolygon
	
		For Local point:TVector=EachIn points

			poly.AddVertex(point)

		Next
		
		If poly.no_verts>0 Then Return poly Else Return Null

	End Function
	
	Method Copy:TPolygon()

		Local poly:TPolygon=New TPolygon
	
		For Local point:TVector=EachIn verts

			poly.AddVertex(point)

		Next
		
		Return poly

	End Method
	
	Function QuadToTris:TPolygon[](polys:TPolygon[])

		Local no_polys=polys.length

		For Local i=0 Until no_polys

			' if array size exceeds no.of polys, and no polys left, exit loop
			If polys[i]=Null Then Exit

			' quad to 2 tris
			If polys[i].no_verts=4

				Local no_polys2=polys.length

				' new tri
				polys=polys[..no_polys2+1]
				polys[no_polys2]=New TPolygon
				polys[no_polys2].AddVertex(polys[i].verts[0])
				polys[no_polys2].AddVertex(polys[i].verts[2])
				polys[no_polys2].AddVertex(polys[i].verts[3])
				polys[no_polys2].surf=polys[i].surf
				polys[no_polys2].tri=polys[i].tri
				
				' remove vertex from quad to make tri
				polys[i].verts=polys[i].verts[..3]
				polys[i].no_verts=3
				
			EndIf

		Next
		
		Return polys
	
	End Function
	
	Method AddVertex(point:TVector)
	
		verts[no_verts]=point.Copy()
		no_verts:+1
		
		If no_verts=>array_size
			array_size=array_size*2
			verts=verts[..array_size]
		EndIf
			
	End Method
	
	Method GetVertex:TVector(i)
	
		Return verts[i]
			
	End Method

End Type
