Rem
Type TTerrain
	'Field Patches:TPatches[,]
	Field Min_Lod:Int
	Field Max_Lod:Int
	Field HeightData:Object
	
	Field Heightmap:THeightmap
	
	Global CELL_Height:Int = 256
	Global CELL_WIDTH:Int = 256
	Field Mesh:TMesh
	Field Surf:TSurface
	Field Tris:Int = 0
	
	Function Create:TTErrain(Url:Object,MinLOD:Int = 1, MaxLOD:Int = 8)
		Local T:TTerrain = New TTerrain
		T.HeightData = Url
		T.Min_LOD = MinLod
		T.Max_LOD = MaxLOD
		
		T. LoadData()
		
		'Create Mesh
		T.Mesh = CreateMesh()
		T.Surf = T.Mesh.CreateSurface()
		Local Scale:Int = 400
		
		For Local X:Int = 0 To (T.Heightmap.width -4)
			For Local Y:Int = 0 To (T.Heightmap.Height - 4)
				If X Mod 100 = 0 Then Print "X: "+x +" Y: " +  y
				Local v0:Int = T.Surf.AddVertex(x *Scale,  T.Heightmap.Heightmap[x*4 , y*4]*(Scale/10) , y*Scale,0,0)
				Local v1:Int = T.Surf.AddVertex((x+1)*Scale ,T.Heightmap.Heightmap[(x+1)*4 , y*4]*(Scale/10),y*Scale,0,0)
				Local v2:Int = T.Surf.AddVertex(x *Scale, T.Heightmap.Heightmap[x*4 , (y + 1)*4]*(Scale/10), (y +1)* Scale,0,0)
				Local v3:Int = T.Surf.AddVertex( (x + 1) * Scale , T.Heightmap.Heightmap[(x + 1)*4 , (y + 1)*4]*(Scale/10) , (y + 1) * Scale , 0 , 0)
				T.Surf.VertexColor(v0 , T.Heightmap.Heightmap[x , y] , T.Heightmap.Heightmap[x , y] , T.Heightmap.Heightmap[x , y]) 
				T.Surf.VertexColor(v1 , T.Heightmap.Heightmap[x+1 , y] , T.Heightmap.Heightmap[x+1 , y] , T.Heightmap.Heightmap[x+1 , y]) 
				T.Surf.VertexColor(v2 , T.Heightmap.Heightmap[x , y+1] , T.Heightmap.Heightmap[x , y+1] , T.Heightmap.Heightmap[x , y+1]) 
				T.Surf.VertexColor(v3 , T.Heightmap.Heightmap[x+1 , y+1] , T.Heightmap.Heightmap[x+1 , y+1] , T.Heightmap.Heightmap[x+1 , y+1]) 
				

				T.surf.AddTriangle(v2 , v1 , v0)
				T.Surf.AddTriangle(v1 , v2 , v3) 
				T.Tris:+2
				
				'If T.Surf.CountVertices() > 15000 Then
				'	T.Surf = T.Mesh.CreateFastSurface()
				'EndIf
			Next
		Next
		
		T.Mesh.UpdateNormals()
		
		T.Mesh.UpdateBuffer()

		Return T
	End Function
	
	Method GetHeight(X:Int,Z:Int)
		Return Heightmap.Get(X,Z)
	End Method
	
	Method LoadData()
		Heightmap = THeightmap.Load(HeightData)
	End Method
	
End Type

Type THeightMap
	
	Field Heightmap:Int[,]
	Field undefined:Int
	Field minAlt:Int = 257
	Field maxAlt:Int = 0
	Field width:Int
	Field height:Int
		
	Function Load:THeightmap(url:Object)
		Local T:THeightmap= New THeightmap
		
		Local Pix:TPixmap = LoadPixmap(url)
		
		Local BRes:Float = PixmapWidth(Pix)
		If PixmapWidth(Pix) <> PixmapHeight(Pix) Then Throw "Not Quadatic!"
				
		T.Heightmap = New Int[PixmapWidth(Pix)+1, PixmapHeight(Pix)+1]
				
		' Loading HeightValues
		Local r:Int , g:Int , b:Int
		Local avg:Int
		
		For Local x:Int = 0 To BRes - 1
			For Local Y:Int = 0 To Bres - 1
				Local C:Int = ReadPixel(pix , x , y)
				r=(C & $00FF0000) Shr 16
				g=(C & $FF00) Shr 8
				b=(C & $FF)
				avg = (r * 0.299) + (g * 0.587) + (b * 0.114)
				T.Heightmap[x , y] = avg
				If avg < T.minalt Then T.minalt = avg
				If avg > t.maxalt Then T.maxalt = avg
			Next
		Next
		
		T.Width = Sqr(T.Heightmap.Length)'PixmapWidth(Pix)
		T.Height =  Sqr(T.Heightmap.Length)'PixmapHeight(Pix)
		
		Return T
	End Function
	
	Method Get:Int(X:Int , Y:Int) 
		Return Heightmap[x , y]
	End Method
	
	Method GetWidth:Int()
		Return Width
	End Method
	
	Method GetHeight:Int()
		Return Height
	End Method
End Type
End Rem

Rem

MiniB3d Chunked Terrain Mesh Test
(Proof of concept / performance test)

Notes:

	* Faster than non-chunked large terrain meshes, but probably not fast enough 
	  for any practical purposes. 512 x 512 heightmaps will reduce minib3d to a crawl.
	
	* The heightmap must have equal dimensions that are power of two (eg 128x128, 256x256, etc).

	* KEYS: WASD, Arrows.
	
	* MOUSE: Right Button
		
EndRem
		
Function TerrainYMedium:Float(Terrain:TTerrain , X:Float , Y:Float , Z:Float)
	Local XS:Float = (X + Terrain.X) / Terrain.XScale
	Local ZS:Float = (Z + Terrain.Z) / Terrain.ZScale
		
	Local X1:Int = Int(XS + 0.5)
	Local Z1:Int = Int(ZS + 0.5)
		
	If X1 > Terrain.Size Then X1 = Int(XS - 0.5)
	If Z1 > Terrain.Size Then Z1 = Int(ZS - 0.5)
		
	If X1 < 0 Or X1 > Terrain.Size - 1 Then Return 0
	If Terrain.Size - Z1 - 1 < 0 Or Terrain.Size - Z1 - 1 > Terrain.Size - 1 Then Return 0
	If XS < 0 Or XS > Terrain.Size - 1 Then Return 0
	If Terrain.Size - ZS - 1 < 0 Or Terrain.Size - ZS - 1 > Terrain.Size - 1 Then Return 0

	LinePick X , Y + 10000 , Z , 0 , - 10000 - Y , 0 , 1
	If Terrain.CompareMesh(PickedEntity()) = False Then Return 0
	Return PickedY()
End Function


Function TerrainYSlow:Float(Terrain:TTerrain ,X:Float,Y:Float,Z:Float)
	Local XL:Int = Sqr(Terrain.Chunks.length)
	Local ZL:Int = XL
	
	Local X1:Int = ((X / Terrain.XScale)/Terrain.ChunkSize )
	Local Z1:Int = ZL - ( (Z / Terrain.ZScale) / Terrain.ChunkSize )
	Local XX1:Float = ((X / Terrain.XScale)/Terrain.ChunkSize )
	Local ZZ1:Float = ZL - ( (Z / Terrain.ZScale) / Terrain.ChunkSize )
	
	
	If X1 < 0 Or X1 >= XL Then Return Null
	If Z1 < 0 Or Z1 >= ZL Then Return Null
	
	Local S:TSurface = Terrain.Chunks[X1,Z1].GetSurface(1)
	If S = Null Then Return Null
	
	Local Tris:Int = 9999999999
	Local TrisDist:Float = 99999999
	
	Local M:TMesh = Terrain.Chunks[X1,Z1]
	
	For Local I:Int = 0 To S.no_tris - 1
		Local V0:Int = S.TriangleVertex(I,0) 
		Local V1:Int = S.TriangleVertex(I,1) 
		Local V2:Int = S.TriangleVertex(I , 2)
		
		Local VX1:Float = S.VertexX(V0)
		Local VZ1:Float = S.VertexZ(V0)
		TFormPoint (Vx1, 0, VZ1, M, Null)
		VX1 = TFormedX()
		VZ1 = TFormedZ()
		
		
		
		Local VX2:Float = S.VertexX(V1)
		Local VZ2:Float = S.VertexZ(V1)
		TFormPoint (Vx2, 0, VZ2, M, Null)
		VX2 = TFormedX()
		VZ2 = TFormedZ()

		
		Local VX3:Float = S.VertexX(V2)
		Local VZ3:Float = S.VertexZ(V2)
		TFormPoint (Vx3, 0, VZ3, M, Null)
		VX3 = TFormedX()
		VZ3 = TFormedZ()

		
		Local DX:Float = ((VX1+VX2+VX3)/3)-(X)
		Local DZ:Float = ( (VZ1 + VZ2 + VZ3) / 3) - (Z)

		
		Local DistSqr:Float = DX * DX + DZ * DZ
		If DistSqr < TrisDist Then 
			TrisDist = DistSqr
			Tris = I
		EndIf		 
	Next
	
	Local V:Int[3]
	V[0] = S.TriangleVertex(Tris,0) 
	V[1] = S.TriangleVertex(Tris,1) 
	V[2] = S.TriangleVertex(Tris,2)
	
	
	Local XS:Float[3]
	Local YS:Float[3]
	Local ZS:Float[3]

	
	For Local II:Int = 0 To 2
			Local XX:Float = S.VertexX(V[II])
			Local YY:Float = S.VertexY(V[II])
			Local ZZ:Float = S.VertexZ(V[II])
			
			TFormPoint (xx, yy, zz, M, Null)
			
			XS[II] = TFormedX()
			YS[II] = TFormedY()
	 		ZS[II] = TFormedZ()	
	Next
	
	
	Local H:Float = PointHeightOnTri(X,Z,XS[0],YS[0],ZS[0],XS[1],YS[1],ZS[1],XS[2],YS[2],ZS[2])
		
	Return H
	
End Function

Function PointHeightOnTri#(px#,pz#, x1#,y1#,z1#,x2#,y2#,z2#,x3#,y3#,z3#)
	Local e#=(x2-x1)*(z3-z1)-(x3-x1)*(z2-z1)
	e=1.0/e
	Local e1#=e*((x2-px)*(z3-pz)-(x3-px)*(z2-pz))
	Local e2#=e*((x3-px)*(z1-pz)-(x1-px)*(z3-pz))
	Local e3#=e*((x1-px)*(z2-pz)-(x2-px)*(z1-pz))
	Return e1*y1+e2*y2+e3*y3
End Function
	

'********** CHUNKED TERRAIN CLASS **********


Type TTerrain


	Field Size:Int			
	Field ChunkSize:Int
	Field Cols:Int
	Field Rows:Int
	
	Field Pivot:TPivot
	Field Chunks:TMesh[,]
	Field PChunks:TPivot[,]

	Field X:Float
	Field Y:Float
	Field Z:Float
	
	Field XScale:Float
	Field YScale:Float
	Field ZScale:Float
	
	Global MaxHeight:Float = 0.0
	
	Field HeightTable:Float[,]
	Field totalchunks:Int = 0
	Field renderedchunks:Int = 0
	
	
	Method New()
	
		X = 0.0
		Y = 0.0
		Z = 0.0
				
		XScale = 1.0
		YScale = 1.0
		ZScale = 1.0
	
	EndMethod
	
	
	Method Destroy()
	
		For Local col:Int = 0 To Cols - 1
			For Local row:Int = 0 To Rows - 1
				FreeEntity Chunks[col, row]
				Chunks[col, row] = Null
			Next
		Next	
	
		FreeEntity Pivot
		
		Pivot = Null
	
		Chunks = Null
		
		GCCollect		
	
	EndMethod
	
	
	'Chunk Size should be less than the heightmap size and a power of two (eg, 16, 32, 64, etc)
	
	Method Load:Int(hmap_url:String, chunk_size:Int = 64)
	
		Local pix:TPixmap = LoadPixmap(hmap_url)
		If Not pix Return False
		
		
				
		
		Size = pix.height
		
		'Build HeightTable
		HeightTable = New Float[Size,Size]
		
		For Local X:Int = 0 To Size - 1
			For Local Y:Int = 0 To Size - 1
				Local r:Byte = ReadPixel(pix , x , y) 
				HeightTable[x , y] = Float(r) / 255
			Next
		Next
		ChunkSize = chunk_size
		
		Cols = (Size / ChunkSize)
		Rows = (Size / ChunkSize)

		Pivot = CreatePivot()
		
		PositionEntity Pivot, X, Y, Z, True
	
		Chunks = New TMesh[Cols , Rows]
		PChunks = New TPivot[Cols , Rows]
		
		
		For Local col:Int = 0 To Cols - 1
			For Local row:Int = 0 To Rows - 1
		
				Local px:Int = (col * ChunkSize) - col
				Local pz:Int = (row * ChunkSize) - row
		
				Local hmappm:TPixmap = PixmapWindow(pix, px, pz, ChunkSize + 1, ChunkSize + 1)
				Chunks[col , row] = CreateChunk(hmappm , Pivot)
				Chunks[col , row].Name = "Chunk"+col+row
				Local wx:Float = Float(px)
				Local wz:Float = Float(((rows - 1) * chunk_size) - pz)
				PositionEntity Chunks[col, row], wx, 0.0, wz, False
				Chunks[col , row].MeshUSeVBO(True)
				PChunks[Col,row] = CreatePivot(Chunks[col,row])
			Next
		Next

		Scale XScale, YScale, ZScale
		
		Return True

	EndMethod
	
	Method Update(Cam:TCamera)
		
		
			totalchunks= 0
			renderedchunks= 0

		For Local col:Int = 0 To Cols - 1
			For Local row:Int = 0 To Rows - 1
			
				totalchunks:+ 1
				
				Local MaxDistance:Int = Cam.range_Far
				Local Dist:Float = EntityDistance(Cam , Chunks[Col , row])
				
				If Dist > MaxDistance Then
					HideEntity(Chunks[col , row])
				Else
					ShowEntity(Chunks[Col , row])
					renderedchunks:+1
				EndIf
				
			Next
		Next
	End Method
	
	Method GetTotal:Int()
			Return totalchunks
	End Method
	
	Method GetRendered:Int()
		Return renderedchunks
	End Method
	
	Method TextureDetail:Int(Tex:TTexture , index:Int = 0,frame:Int = 0)
		For Local col:Int = 0 To Cols - 1
			For Local row:Int = 0 To Rows - 1
		
				EntityTexture chunks[col, row], tex, frame, index
								
			Next
		Next
		
		Return True
	End Method


	Method TextureFromFile:Int(tex_url:String = "", flags:Int = 1, frame:Int = 0, index:Int = 0)

		If Not pivot Return False
	
		Local tex:TPixmap = LoadPixmap(tex_url)
		If Not tex Then Return False

		tex = ResizePixmap(tex, Size, Size)

		For Local col:Int = 0 To Cols - 1
			For Local row:Int = 0 To Rows - 1
		
				Local px:Int = (col * ChunkSize) - col
				Local pz:Int = (row * ChunkSize) - row
		
				Local fname:String = "temp_chunk_tex_" + col + "_" + row + ".png"
				Local pm:TPixmap = PixmapWindow(tex, px, pz, ChunkSize + 1, ChunkSize + 1)
				SavePixmapPNG(pm, fname, 9)
				
				Local tex_chunk:TTexture = LoadTexture(fname, flags)
				ScaleTexture tex_chunk, pm.width, pm.height
				EntityTexture chunks[col, row], tex_chunk, frame, index
				
				DeleteFile fname
				
			Next
		Next
		
		Return True

	EndMethod
	

	Method Scale(sx:Float, sy:Float, sz:Float)
	
		If Not Pivot Return
	
		XScale = sx
		YScale = sy
		ZScale = sz
		
		TTerrain.MaxHeight:*SY
	
		ScaleEntity Pivot, XScale, YScale, ZScale
	
	EndMethod
	
	
	Method Position(wx:Float, wy:Float, wz:Float)
	
		If Not Pivot Return
	
		X = wx
		Y = wy
		Z = wz
		
		PositionEntity Pivot, X, Y, Z		
	
	EndMethod
	
	
	Function CreateChunk:TMesh(pix:TPixmap, parent:TEntity = Null)
	Rem
		* Ported And slightly modified from Blitz3D code:
  		  <a href="http://www.blitzbasic.com/codearcs/codearcs.php?code=1609" target="_blank">www.blitzbasic.com/codearcs/codearcs.php?code=1609</a>
	EndRem

		If Not pix Return Null

		Local pixw:Int = PixmapWidth(pix)
		Local pixh:Int = PixmapHeight(pix)

		Local mesh:TMesh = CreateMesh(parent) 
		Local surf:TSurface = CreateSurface(mesh)

		For Local ly:Int = 0 To pixh
			For Local lx:Int = 0 To pixw
				AddVertex surf, lx, 0, ly, (1.0 / lx), (1.0 / ly)
			Next
		Next
	
		For Local ly:Int = 1 To (pixw - 2)
			For Local lx:Int = 1 To (pixh - 2)
				AddTriangle surf, lx + ((pixw + 1) * ly), lx + ((pixw + 1) * ly) + (pixw + 1), (lx + 1) + ((pixw + 1) * ly)
				AddTriangle surf, (lx + 1) + ((pixw + 1) * ly), lx + ((pixw + 1) * ly) + (pixw + 1), (lx + 1)+((pixw + 1) * ly) + (pixw + 1)
			Next
		Next

		For Local lx:Int = 0 To (pixw - 1)
			For Local ly:Int = 0 To (pixh - 1)
				Local r:Byte = ReadPixel(pix, lx, pixh - 1 - ly)
				Local index:Int = lx + ((pixw + 1) * ly)
				VertexCoords surf, index, VertexX(surf, index), Float(r) / 255.0, VertexZ(surf, index)
				VertexTexCoords surf , index , lx , - ly 
				If Float(r) / 255.0 > TTerrain.MaxHeight Then TTerrain.MaxHeight = Float(r) / 255.0
			Next
		Next

		UpdateNormals mesh
		
		'EntityAutoFade(mesh,MeshWidth(Mesh)*3,40000)

		
		CreateOctree(mesh,10,3)
		EntityPickMode mesh , 2
		
		
		Return Mesh
	
	End Function
	
	Method CompareMesh:Byte(S:TEntity)
		For Local M:TEntity = EachIn chunks
			If M = S Then Return True
		Next
		Return False
	End Method
		
	
	Method GetHeight:Float(X:Float , Y:Float , Z:Float)
		Rem
		Local pick:TEntity = LinePick(x , TTerrain.MaxHeight, z , 0 , -TTerrain.MaxHeight*2 , 0 , 30)
		If Pick <> Null Then 
			Return PickedY()
		Else 
			Return - 1.0
		EndIf
		End Rem
		Local XS:Float = (X + Self.X) / XScale
		Local ZS:Float = (Z + Self.Z) / ZScale
		
		Local X1:Int = Int(XS + 0.5)
		Local Z1:Int = Int(ZS + 0.5)
		
		If X1 > Size Then X1 = Int(XS - 0.5)
		If Z1 > Size Then Z1 = Int(ZS - 0.5)
		Local W:Int = Sqr(Chunks.Length)
		
		If X1 < 0 Or X1 > Size - 1 Then Return 0
		If Size - Z1 - 1 < 0 Or Size - Z1 - 1 > Size - 1 Then Return 0
		If XS < 0 Or XS > Size - 1 Then Return 0
		If Size - ZS - 1 < 0 Or Size - ZS - 1 > Size - 1 Then Return 0
	
		Local H1:Float = HeightTable[X1 , Size - Z1 - 1]
		Local H2:Float = HeightTable[XS , Size - ZS - 1]
		
		
		Local diffX:Float = XS - X1
		Local diffZ:Float = ZS - Z1
		
		Local diff:Float = Abs(diffx * diffz)
		'Print "Difference : " + diff
		
		Return TUtility.UpdateValue(H2,H1,1.0-diff) * yScale
		
		'Return HeightTable[XS,Size-ZS-1]*YScale

	End Method
	
EndType


'******************************




'****** MISCELLANEOUS FUNCTIONS (NOT required for Chunked Terrain class) *********



Function createSampleHeightMap(fname:String, width:Int = 128, height:Int = 128, numhills:Int = 1000, maxhsize:Int = 32, island:Int = True)

	'Generate

	Local Map:Float[width, height]

    SeedRnd(MilliSecs())
  
	If island
		numhills :* 0.2
		maxhsize :* 0.5
	EndIf

    For Local n:Int = 1 To numhills

		Local radius:Int = Rand(0, maxhsize)
		Local centrex:Int = Rand(0, Width - 1)
		Local centrez:Int = Rand(0, Height - 1)
		
		If island
			Local theta:Int = Rand(0, 359)
			Local distx:Int = Rand(0, (Width * 0.5) - radius)
			Local distz:Int = Rand(0, (Height * 0.5) - radius)
	  		centrex = (Width * 0.5) + (Cos(theta) * distx)
	  		centrez = (Height * 0.5) + (Sin(theta) * distz)
		EndIf

    	Local startx:Int = centrex - radius
      	If startx < 0 startx = 0

      	Local endx:Int = centrex + radius
	  	If endx > Width endx = Width

      	Local startz:Int = centrez - radius
      	If startz < 0 startz = 0

      	Local endz:Int = centrez + radius
      	If endz > Height endz = Height

      	For Local x:Int = startx To (endx - 1)
       		For Local z:Int = startz To (endz - 1)
	   			Local y:Float = (radius * radius) - (((x - centrex) * (x - centrex)) + ((z - centrez) * (z - centrez)))
	    		If y > 0.0 Map[x, z] :+ y
	    	Next
	  	Next
    
    Next

	'Normalise
	
	Local minv:Float = 10^38, maxv:Float = 10^-38
  
  	For Local x:Int = 0 To (Width - 1)
    	For Local z:Int = 0 To (Height - 1)
 	 		If Map[x, z] < minv minv = Map[x, z] Else If Map[x, z] > maxv maxv = Map[x, z]
     	Next
   	Next

   	For Local x:Int = 0 To (Width - 1)
     	For Local z:Int = 0 To (Height - 1)
			Map[x, z] = (Map[x, z] - minv) / (maxv - minv)
		Next
  	Next

	'Convert to byte Array
	
	Local arr:Byte[,] = New Byte[width, height]

  	For Local x:Int = 0 To (Width - 1)
    	For Local z:Int = 0 To (Height - 1)

			Local v:Int = Floor(Map[x, z] * 255)

			arr[x, z] = Byte(v)

		Next
	Next
		
	'Render to pixmap and save to file
	
	Local pm:TPixmap = CreatePixmap(width, height, PF_RGB888)

    For Local x:Int = 0 To (Width - 1)
    	For Local z:Int = 0 To (Height - 1)
    		WritePixel(pm, x, z, arr[x, z] Shl 16 | arr[x, z] Shl 8 | arr[x, z])
    	Next
    Next

	SavePixmapPNG(pm, fname, 9)	
	
End Function


