vertex_order_optimization.lua

local MAXVCACHE = 32

local function CalculateScore(Object)
	if #Object.Uses > 0 then
		Object.Score = 2.0 * ((#Object.Uses) ^ -0.5)
		if Object.CacheRank >= 3 then
			Object.Score = Object.Score + ((1.0 - (Object.CacheRank - 3) / MAXVCACHE) ^ 1.5)
		elseif Object.CacheRank >= 0 then
			Object.Score = Object.Score + 0.75
		end
	else
		Object.Score = -1.0
	end
end

local function PythonRemoveFind(Tab, What)
	for I = 1, #Tab do
		if Tab[I] == What then
			return I
		end
	end
end

local function PythonRemove(Tab, What)
	local Index = PythonRemoveFind(Tab, What)
	
	while Index ~= nil do
		Remove(Tab, Index)
		Index = PythonRemoveFind(Tab, What)
	end
end

local function OptimizeVertex(Object, ZeroIndexBased, IsIQM)
	Write("Optimizing Vertex..")
	--Linear-speed vertex cache optimization algorithm by Tom Forsyth
	
	local Position = {}
	local GlobalUV = {}
	local UV = {}
	local Normal = {}
	local SubMesh = {}
	local Color = {}
	local Tangent = {}
	local Indices = {}
		
	local TotalIndicesCount = 0
	
	for Key, SubMesh2 in IteratePairs(Object.SubMeshes) do
		local Vertices = {}
		
		if not IsIQM then
			for I = SubMesh2.VertexIndexStart, SubMesh2.VertexIndexEnd - 1 do
				local Position = {Object.Mesh.Position[(Object.Mesh.Indices[I] - 1) * 3 + 1], Object.Mesh.Position[(Object.Mesh.Indices[I] - 1) * 3 + 2], Object.Mesh.Position[(Object.Mesh.Indices[I] - 1) * 3 + 3]}
				local GlobalUV = {Object.Mesh.GlobalUV[(Object.Mesh.Indices[I] - 1) * 2 + 1], Object.Mesh.GlobalUV[(Object.Mesh.Indices[I] - 1) * 2 + 2]}
				local UV = {Object.Mesh.UV[(Object.Mesh.Indices[I] - 1) * 2 + 1], Object.Mesh.UV[(Object.Mesh.Indices[I] - 1) * 2 + 2]}
				local Normal = {Object.Mesh.Normal[(Object.Mesh.Indices[I] - 1) * 3 + 1], Object.Mesh.Normal[(Object.Mesh.Indices[I] - 1) * 3 + 2], Object.Mesh.Normal[(Object.Mesh.Indices[I] - 1) * 3 + 3]}
				local SubMesh = {Key, Key}
				local Color = {Object.Mesh.Color[(Object.Mesh.Indices[I] - 1) * 3 + 1], Object.Mesh.Color[(Object.Mesh.Indices[I] - 1) * 3 + 2], Object.Mesh.Color[(Object.Mesh.Indices[I] - 1) * 3 + 3]}
				
				local Tangent
				if Object.Mesh.Tangent then
					Tangent = {Object.Mesh.Tangent[(Object.Mesh.Indices[I] - 1) * 4 + 1], Object.Mesh.Tangent[(Object.Mesh.Indices[I] - 1) * 4 + 2], Object.Mesh.Tangent[(Object.Mesh.Indices[I] - 1) * 4 + 3], Object.Mesh.Tangent[(Object.Mesh.Indices[I] - 1) * 4 + 4]}
				end
				
				local Index = #Vertices + 1
				Vertices[Index] = {Position = Position, GlobalUV = GlobalUV, UV = UV, Normal = Normal, SubMesh = SubMesh, Color = Color, Tangent = Tangent, Index = -1, Uses = {}, CacheRank = -1}
			end
		else
			for I = SubMesh2.VertexIndexStart, SubMesh2.VertexIndexEnd - 1 do
				local Position = {Object.Mesh.Position[(Object.Mesh.Indices[I] - 1) * 3 + 1], Object.Mesh.Position[(Object.Mesh.Indices[I] - 1) * 3 + 2], Object.Mesh.Position[(Object.Mesh.Indices[I] - 1) * 3 + 3]}
				local UV = {Object.Mesh.UV[(Object.Mesh.Indices[I] - 1) * 2 + 1], Object.Mesh.UV[(Object.Mesh.Indices[I] - 1) * 2 + 2]}
				local Normal = {Object.Mesh.Normal[(Object.Mesh.Indices[I] - 1) * 3 + 1], Object.Mesh.Normal[(Object.Mesh.Indices[I] - 1) * 3 + 2], Object.Mesh.Normal[(Object.Mesh.Indices[I] - 1) * 3 + 3]}
				local SubMesh = {Key, Key}
				local Color = {Object.Mesh.Color[(Object.Mesh.Indices[I] - 1) * 3 + 1], Object.Mesh.Color[(Object.Mesh.Indices[I] - 1) * 3 + 2], Object.Mesh.Color[(Object.Mesh.Indices[I] - 1) * 3 + 3]}
				local Tangent = {Object.Mesh.Tangent[(Object.Mesh.Indices[I] - 1) * 4 + 1], Object.Mesh.Tangent[(Object.Mesh.Indices[I] - 1) * 4 + 2], Object.Mesh.Tangent[(Object.Mesh.Indices[I] - 1) * 4 + 3], Object.Mesh.Tangent[(Object.Mesh.Indices[I] - 1) * 4 + 4]}
				
				local Index = #Vertices + 1
				Vertices[Index] = {Position = Position, UV = UV, Normal = Normal, SubMesh = SubMesh, Color = Color, Tangent = Tangent, Index = -1, Uses = {}, CacheRank = -1}
			end
		end
		
		local Triangles = {}
		for I = 1, #Vertices, 3 do
			Insert(Triangles, {Vertices[I], Vertices[I + 1], Vertices[I + 2]})
		end
		
		for I = 1, #Triangles do
			Insert(Triangles[I][1].Uses, I)
			Insert(Triangles[I][2].Uses, I)
			Insert(Triangles[I][3].Uses, I)
		end
		
		for _, Vertex in IteratePairs(Vertices) do
			CalculateScore(Vertex)
		end
		
		local BestTriangle = -1
		local BestScore = -42.0
		local Scores = {}
		for I = 1, #Triangles do
			Insert(Scores, (Triangles[I][1].Score + Triangles[I][2].Score + Triangles[I][3].Score))
			if Scores[I] > BestScore then
				BestTriangle = I
				BestScore = Scores[I]
			end
		end
		
		local GCTurns = 0
		--local VerticesLoads = 0 --debug info
		local VerticeSchedule = {}
		local TriangleSchedule = {}
		local VertexCache = {}
		while BestTriangle >= 0 do
			local Triangle = Triangles[BestTriangle]
			
			Scores[BestTriangle] = -666.0
			Insert(TriangleSchedule, Triangle)
			
			for _, Vertex in IteratePairs(Triangle) do
				--if Vertex.CacheRank < 0 then --debug info
				--	VerticesLoads = VerticesLoads + 1  --debug info
				--end
				
				if Vertex.Index < 0 then
					Vertex.Index = #VerticeSchedule + 1
					Insert(VerticeSchedule, Vertex)
				end
				
				PythonRemove(Vertex.Uses, BestTriangle)
				Vertex.CacheRank = -1
				Vertex.Score = -1.0
			end
			
			GCTurns = GCTurns + 1
			
			if GCTurns % (16384 * 32) == 0 then
				CollectGarbage("step")
				GCTurns = 0
			end
			
			local PreviousVertexCache = VertexCache
			VertexCache = {}
			
			for _, Vertex in IteratePairs(Triangle) do
				if #Vertex.Uses > 0 then
					Insert(VertexCache, Vertex)
				end
			end
			
			for _, Vertex in IteratePairs(PreviousVertexCache) do
				if Vertex.CacheRank >= 0 then
					Insert(VertexCache, Vertex)
				end
			end
			
			for I, Vertex in IteratePairs(VertexCache) do
				Vertex.CacheRank = I
				CalculateScore(Vertex)
			end

			BestTriangle = -1
			BestScore = -42.0
			for _, Vertex in IteratePairs(VertexCache) do
				for _, Index in IteratePairs(Vertex.Uses) do
					Scores[Index] = Triangles[Index][1].Score + Triangles[Index][2].Score + Triangles[Index][3].Score
					if Scores[Index] > BestScore then
						BestTriangle = Index
						BestScore = Scores[Index]
					end
				end
			end
			
			while #VertexCache > MAXVCACHE do
				local Vertex = Remove(VertexCache)
				Vertex.CacheRank = -1
			end
			
			if BestTriangle < 0 then
				for I, Score in IteratePairs(Scores) do
					if Score > BestScore then
						BestTriangle = I
						BestScore = Score
					end
				end
			end
		end
		
		if not IsIQM then
			for _, Vertice in IteratePairs(VerticeSchedule) do
				Position[#Position + 1] = Vertice.Position[1]
				Position[#Position + 1] = Vertice.Position[2]
				Position[#Position + 1] = Vertice.Position[3]
				
				GlobalUV[#GlobalUV + 1] = Vertice.GlobalUV[1]
				GlobalUV[#GlobalUV + 1] = Vertice.GlobalUV[2]
				
				UV[#UV + 1] = Vertice.UV[1]
				UV[#UV + 1] = Vertice.UV[2]
				
				Normal[#Normal + 1] = Vertice.Normal[1]
				Normal[#Normal + 1] = Vertice.Normal[2]
				Normal[#Normal + 1] = Vertice.Normal[3]
				
				SubMesh[#SubMesh + 1] = Vertice.SubMesh[1]
				SubMesh[#SubMesh + 1] = Vertice.SubMesh[2]
				
				Color[#Color + 1] = Vertice.Color[1]
				Color[#Color + 1] = Vertice.Color[2]
				Color[#Color + 1] = Vertice.Color[3]
				
				if Object.Mesh.Tangent then
					Tangent[#Tangent + 1] = Vertice.Tangent[1]
					Tangent[#Tangent + 1] = Vertice.Tangent[2]
					Tangent[#Tangent + 1] = Vertice.Tangent[3]
					Tangent[#Tangent + 1] = Vertice.Tangent[4]
				end
			end
		else
			for _, Vertice in IteratePairs(VerticeSchedule) do
				Position[#Position + 1] = Vertice.Position[1]
				Position[#Position + 1] = Vertice.Position[2]
				Position[#Position + 1] = Vertice.Position[3]
				
				UV[#UV + 1] = Vertice.UV[1]
				UV[#UV + 1] = Vertice.UV[2]
				
				Normal[#Normal + 1] = Vertice.Normal[1]
				Normal[#Normal + 1] = Vertice.Normal[2]
				Normal[#Normal + 1] = Vertice.Normal[3]
				
				SubMesh[#SubMesh + 1] = Vertice.SubMesh[1]
				SubMesh[#SubMesh + 1] = Vertice.SubMesh[2]
				
				Color[#Color + 1] = Vertice.Color[1]
				Color[#Color + 1] = Vertice.Color[2]
				Color[#Color + 1] = Vertice.Color[3]
				
				if Object.Mesh.Tangent then
					Tangent[#Tangent + 1] = Vertice.Tangent[1]
					Tangent[#Tangent + 1] = Vertice.Tangent[2]
					Tangent[#Tangent + 1] = Vertice.Tangent[3]
					Tangent[#Tangent + 1] = Vertice.Tangent[4]
				end
			end
		end
		
		local IndicesCount = 0
		local Offset = ZeroIndexBased and 0 or 1
		
		for _, Triangle in IteratePairs(TriangleSchedule) do
			Indices[IndicesCount + TotalIndicesCount + Offset] = Triangle[1].Index + TotalIndicesCount
			IndicesCount = IndicesCount + 1
			
			Indices[IndicesCount + TotalIndicesCount + Offset] = Triangle[2].Index + TotalIndicesCount
			IndicesCount = IndicesCount + 1
			
			Indices[IndicesCount + TotalIndicesCount + Offset] = Triangle[3].Index + TotalIndicesCount
			IndicesCount = IndicesCount + 1
		end
		
		TotalIndicesCount = TotalIndicesCount + IndicesCount 
		
		CollectGarbage("step")
		
		--print(Format('%s: %d verts optimized to %d/%d loads for %d entry LRU cache', Key, #Vertices, VerticesLoads, #VerticeSchedule, MAXVCACHE))
		--print('%s: %d verts scheduled to %d' % (self.name, len(self.verts), len(VerticeSchedule)))
		--self.verts = VerticeSchedule
		--print('%s: %d tris scheduled to %d' % (self.name, len(self.tris), len(TriangleSchedule)))
		--self.tris = TriangleSchedule
	end
	
	Write("..OK\n")
	
	if not IsIQM then
		Object.Mesh.Position = Position
		Object.Mesh.GlobalUV = GlobalUV
		Object.Mesh.UV = UV
		Object.Mesh.Normal = Normal
		Object.Mesh.SubMesh = SubMesh
		Object.Mesh.Color = Color
		Object.Mesh.Tangent = Tangent
		Object.Mesh.Indices = Indices
	else
		Object.Mesh.Position = Position
		Object.Mesh.UV = UV
		Object.Mesh.Normal = Normal
		Object.Mesh.SubMesh = SubMesh
		Object.Mesh.Color = Color
		Object.Mesh.Tangent = Tangent
		Object.Mesh.Indices = Indices
	end
end