+Unity Runtime codeHEADmaster

1 files changed, 359 insertions, 0 deletions

diff --git a/Runtime/Filters/Mesh/MeshOptimizer.cpp b/Runtime/Filters/Mesh/MeshOptimizer.cpp
new file mode 100644
index 0000000..068dc53
--- /dev/null
+++ b/Runtime/Filters/Mesh/MeshOptimizer.cpp
@@ -0,0 +1,359 @@
+#include "UnityPrefix.h"
+#include "MeshOptimizer.h"
+#include <vector>
+
+//@TODO: 
+
+// Step 1
+
+//* bool ExtractCollisionData (Mesh& mesh, UNITY_TEMP_VECTOR(kMemGeometry, Vector3f)& vertices, UNITY_TEMP_VECTOR(kMemGeometry, UInt32)& triangles);
+//   -> make it return welded vertices and triangle array
+//* Enable Deformablemesh code and make it work with welding code and check that cloth works visually...
+
+// Testing:
+//* Check mesh collision detection code to work visually correct.
+// * run functional test suite
+// * run lightmapper tests in the integration test suite. They have a complete test for the lightmap uv coordinates picking up lightmap values...
+
+
+// Step 2:
+//* Verify vertex cache performance on iPad1 / Wii / intel integrated graphics
+//* Switch to default gpu optimized mode and update all model importer templates
+
+
+
+template<typename T, const int CACHE_SIZE>
+class VertexCacheOptimizer 
+{
+	UInt32* m_cacheEntries;
+	UInt32 m_cacheSize;
+
+	mutable UInt32 m_cacheMisses;
+	mutable UInt32 m_cacheHits;
+
+	UInt32 GetInCache(UInt32 lIndex, const char* vertexInCache) const 
+	{ 
+		return vertexInCache[lIndex] ? 1 : 0; 
+	}
+	
+	void AddToCache(UInt32 lIndex, char* vertexInCache) 
+	{
+		if(m_cacheEntries[0]!=-1) 
+			vertexInCache[m_cacheEntries[0]]=0;
+
+		for(UInt32 i=0; i<m_cacheSize-1; i++) 
+			m_cacheEntries[i]=m_cacheEntries[i+1];
+
+		m_cacheEntries[m_cacheSize-1]=lIndex;
+		vertexInCache[lIndex]=1;
+	}
+
+public:
+	
+	VertexCacheOptimizer () : m_cacheSize(CACHE_SIZE)
+	{
+		m_cacheEntries=new UInt32 [m_cacheSize];
+
+		m_cacheHits = m_cacheMisses = 0;
+		for(UInt32 i=0; i<m_cacheSize; i++) 
+			m_cacheEntries[i]=(UInt32)-1;
+	}
+
+	~VertexCacheOptimizer() { delete m_cacheEntries; }
+
+	UInt32 GetCacheMisses() { return m_cacheMisses; }
+	UInt32 GetCacheHits() { return m_cacheHits; }
+
+	void OptimizeTriangles(T* pdstTris, UInt32 numVertices, const T* srcTris, UInt32 numTriangles) 
+	{
+		UInt32 cachedVerts=0;
+		char* triangleUsed=new char [numTriangles];
+		char* vertexInCache=new char [numVertices];
+		memset(triangleUsed,0,numTriangles);
+		memset(vertexInCache,0,numVertices);
+
+		bool foundTriangle=true;
+		while (foundTriangle) 
+		{
+			foundTriangle=false;
+			UInt32 bestCandidate=0;
+			UInt32 bestCacheValue=0;
+			for (UInt32 i = 0; i < numTriangles; i++) 
+			{
+				if (triangleUsed[i]) 
+					continue;
+
+				foundTriangle=true;
+				UInt32 i1=srcTris[i*3+0];
+				UInt32 i2=srcTris[i*3+1];
+				UInt32 i3=srcTris[i*3+2];
+
+				UInt32 lCacheValue=GetInCache(i1,vertexInCache)+GetInCache(i2,vertexInCache)+GetInCache(i3,vertexInCache)+1;
+				if (lCacheValue > bestCacheValue) 
+				{
+					bestCandidate=i;
+					bestCacheValue=lCacheValue;
+					if (bestCacheValue == 4) 
+						break;
+				}
+			}
+			if(foundTriangle) 
+			{
+				triangleUsed[bestCandidate]=1;
+				UInt32 i1=srcTris[bestCandidate*3+0];
+				UInt32 i2=srcTris[bestCandidate*3+1];
+				UInt32 i3=srcTris[bestCandidate*3+2];
+				*pdstTris++=(T)i1;
+				*pdstTris++=(T)i2;
+				*pdstTris++=(T)i3;
+				if (!GetInCache(i1,vertexInCache)) { AddToCache(i1,vertexInCache); cachedVerts++; m_cacheMisses++; } else m_cacheHits++;
+				if (!GetInCache(i2,vertexInCache)) { AddToCache(i2,vertexInCache); cachedVerts++; m_cacheMisses++; } else m_cacheHits++;
+				if (!GetInCache(i3,vertexInCache)) { AddToCache(i3,vertexInCache); cachedVerts++; m_cacheMisses++; } else m_cacheHits++;
+			}
+		}
+		delete[] triangleUsed;
+		delete[] vertexInCache;
+	}
+};
+
+inline bool CompareBlendShapeVertexIndex (const BlendShapeVertex& lhs, const BlendShapeVertex& rhs)
+{
+	return lhs.index < rhs.index;
+}
+
+void OptimizeReorderVertexBuffer (Mesh& mesh)
+{
+	const int submeshCount = mesh.GetSubMeshCount();
+	const int vertexCount = mesh.GetVertexCount();
+
+	// backup required data
+	VertexData backupVertexData(mesh.m_VertexData, mesh.GetAvailableChannels(), mesh.GetVertexData().GetStreamsLayout(), mesh.GetVertexData().GetChannelsLayout());
+
+	Mesh::BoneInfluenceContainer backupSkin;	
+	if (!mesh.m_Skin.empty())		
+		backupSkin.swap(mesh.m_Skin);
+
+	// reorder the vertices so they come in increasing order
+	dynamic_array<UInt32> oldToNew;
+	dynamic_array<UInt32> newToOld;
+	newToOld.resize_initialized(vertexCount, 0xFFFFFFFF);
+	oldToNew.resize_initialized(vertexCount, 0xFFFFFFFF);
+	
+	Mesh::TemporaryIndexContainer dstIndices;
+	int newVertexCount = 0;
+	for (int submesh = 0; submesh < submeshCount; submesh++) 
+	{
+		Mesh::TemporaryIndexContainer indices;
+		mesh.GetTriangles (indices, submesh);
+
+		const int indexCount = indices.size();
+		dstIndices.resize(indexCount);
+		for (int index=0; index < indexCount; index++) 
+		{
+			int vertex = indices[index];				
+			AssertBreak(vertex >= 0);
+			AssertBreak(vertex < vertexCount);
+			
+			if (oldToNew[vertex] == 0xFFFFFFFF)
+			{
+				oldToNew[vertex]=newVertexCount;
+				newToOld[newVertexCount]=vertex;
+				newVertexCount++;
+			}
+			dstIndices[index] = oldToNew[vertex];
+		}
+		
+		mesh.SetIndices (&dstIndices[0], dstIndices.size(), submesh, kPrimitiveTriangles);
+	}
+	
+	mesh.ResizeVertices(newVertexCount, backupVertexData.GetChannelMask());
+
+	if (!backupSkin.empty())
+		mesh.m_Skin.resize_initialized(newVertexCount);
+
+	for (int vertex=0; vertex < newVertexCount; vertex++) 
+	{
+		UInt32 remapNew = newToOld[vertex];
+		Assert(remapNew != 0xFFFFFFFF);
+		
+		if (!backupSkin.empty())
+			mesh.m_Skin[vertex] = backupSkin[remapNew];
+
+		mesh.GetVertexBegin()[vertex] = backupVertexData.MakeStrideIterator<Vector3f> (kShaderChannelVertex)[remapNew];
+
+		if (backupVertexData.HasChannel(kShaderChannelNormal))
+			mesh.GetNormalBegin()[vertex] = backupVertexData.MakeStrideIterator<Vector3f> (kShaderChannelNormal)[remapNew];
+
+		if (backupVertexData.HasChannel(kShaderChannelColor))
+			mesh.GetColorBegin()[vertex] = backupVertexData.MakeStrideIterator<ColorRGBA32> (kShaderChannelColor)[remapNew];
+
+		if (backupVertexData.HasChannel(kShaderChannelTexCoord0))
+			mesh.GetUvBegin(0)[vertex] = backupVertexData.MakeStrideIterator<Vector2f> (kShaderChannelTexCoord0)[remapNew];
+
+		if (backupVertexData.HasChannel(kShaderChannelTexCoord1))
+			mesh.GetUvBegin(1)[vertex] = backupVertexData.MakeStrideIterator<Vector2f> (kShaderChannelTexCoord1)[remapNew];
+
+		if (backupVertexData.HasChannel(kShaderChannelTangent))
+			mesh.GetTangentBegin()[vertex] = backupVertexData.MakeStrideIterator<Vector4f> (kShaderChannelTangent)[remapNew];
+	}
+	
+	// Remap vertex indices stored in blend shapes
+	BlendShapeData& blendShapeData = mesh.GetWriteBlendShapeDataInternal();
+	BlendShapeVertices& blendShapeVertices = blendShapeData.vertices;
+	for (BlendShapeVertices::iterator itv = blendShapeVertices.begin(), endv = blendShapeVertices.end(); itv != endv; ++itv)
+	{
+		BlendShapeVertex& bsv = *itv;
+		bsv.index = oldToNew[bsv.index];
+	}
+
+	// Sort each shape's vertices by index so the blending writes to memory as linearly as possible
+	for (int shapeIndex = 0; shapeIndex < blendShapeData.shapes.size(); shapeIndex++)
+	{
+		const BlendShape& shape = blendShapeData.shapes[shapeIndex];
+		BlendShapeVertex* vertices = &blendShapeVertices[shape.firstVertex];
+		std::sort(vertices, vertices + shape.vertexCount, CompareBlendShapeVertexIndex);
+	}
+
+	mesh.SetChannelsDirty(mesh.GetAvailableChannels(), true);
+}
+
+void OptimizeIndexBuffers (Mesh& mesh)
+{
+	const int submeshCount = mesh.GetSubMeshCount();
+	const int vertexCount = mesh.GetVertexCount();
+
+	// first optimize the indices for each submesh
+	for (int submesh = 0; submesh < submeshCount; submesh++)
+	{
+		Mesh::TemporaryIndexContainer unoptimizedIndices;
+		mesh.GetTriangles (unoptimizedIndices, submesh);
+		
+		Mesh::TemporaryIndexContainer optimizedIndices;
+		optimizedIndices.resize(unoptimizedIndices.size());
+		
+		VertexCacheOptimizer<UInt32, 16> vertexCacheOptimizer;
+		vertexCacheOptimizer.OptimizeTriangles(&optimizedIndices[0], vertexCount, &unoptimizedIndices[0], unoptimizedIndices.size() / 3);
+		// LogString(Format("[Optimize] mesh: %s: submesh: %d hits: %d misses: %d\n", mesh.GetName(), submesh, vertexCacheOptimizer.GetCacheHits(), vertexCacheOptimizer.GetCacheMisses()));
+
+		mesh.SetIndices (&optimizedIndices[0], optimizedIndices.size(), submesh, kPrimitiveTriangles);
+	}
+}
+
+
+template<typename T, const int CACHE_SIZE>
+class VertexCacheDeOptimizer 
+{
+	UInt32* m_cacheEntries;
+	UInt32 m_cacheSize;
+    
+	mutable UInt32 m_cacheMisses;
+	mutable UInt32 m_cacheHits;
+    
+	UInt32 GetInCache(UInt32 lIndex, const char* vertexInCache) const 
+	{ 
+		return vertexInCache[lIndex] ? 1 : 0; 
+	}
+    
+	void AddToCache(UInt32 lIndex, char* vertexInCache) 
+	{
+		if(m_cacheEntries[0]!=-1) 
+			vertexInCache[m_cacheEntries[0]]=0;
+        
+		for(UInt32 i=0; i<m_cacheSize-1; i++) 
+			m_cacheEntries[i]=m_cacheEntries[i+1];
+        
+		m_cacheEntries[m_cacheSize-1]=lIndex;
+		vertexInCache[lIndex]=1;
+	}
+    
+public:
+    
+	VertexCacheDeOptimizer () : m_cacheSize(CACHE_SIZE)
+	{
+		m_cacheEntries=new UInt32 [m_cacheSize];
+        
+		m_cacheHits = m_cacheMisses = 0;
+		for(UInt32 i=0; i<m_cacheSize; i++) 
+			m_cacheEntries[i]=(UInt32)-1;
+	}
+    
+	~VertexCacheDeOptimizer() { delete m_cacheEntries; }
+	
+	UInt32 GetCacheMisses() { return m_cacheMisses; }
+	UInt32 GetCacheHits() { return m_cacheHits; }
+    
+	void DeOptimizeTriangles(T* pdstTris, UInt32 numVertices, const T* srcTris, UInt32 numTriangles) 
+	{
+		UInt32 cachedVerts=0;
+		char* triangleUsed=new char [numTriangles];
+		char* vertexInCache=new char [numVertices];
+		memset(triangleUsed,0,numTriangles);
+		memset(vertexInCache,0,numVertices);
+        
+		bool foundTriangle=true;
+		while (foundTriangle) 
+		{
+			foundTriangle=false;
+			UInt32 bestCandidate=0;
+			UInt32 bestCacheValue=4;
+			for (UInt32 i = 0; i < numTriangles; i++) 
+			{
+				if (triangleUsed[i]) 
+					continue;
+                
+				foundTriangle=true;
+				UInt32 i1=srcTris[i*3+0];
+				UInt32 i2=srcTris[i*3+1];
+				UInt32 i3=srcTris[i*3+2];
+                
+				UInt32 lCacheValue=GetInCache(i1,vertexInCache)+GetInCache(i2,vertexInCache)+GetInCache(i3,vertexInCache)+1;
+				if (lCacheValue <= bestCacheValue) 
+				{
+					bestCandidate=i;
+					bestCacheValue=lCacheValue;
+					if (bestCacheValue == 1) 
+						break;
+				}
+			}
+			if(foundTriangle) 
+			{
+				triangleUsed[bestCandidate]=1;
+				UInt32 i1=srcTris[bestCandidate*3+0];
+				UInt32 i2=srcTris[bestCandidate*3+1];
+				UInt32 i3=srcTris[bestCandidate*3+2];
+				*pdstTris++=(T)i1;
+				*pdstTris++=(T)i2;
+				*pdstTris++=(T)i3;
+				if (!GetInCache(i1,vertexInCache)) { AddToCache(i1,vertexInCache); cachedVerts++; m_cacheMisses++; } else m_cacheHits++;
+				if (!GetInCache(i2,vertexInCache)) { AddToCache(i2,vertexInCache); cachedVerts++; m_cacheMisses++; } else m_cacheHits++;
+				if (!GetInCache(i3,vertexInCache)) { AddToCache(i3,vertexInCache); cachedVerts++; m_cacheMisses++; } else m_cacheHits++;
+			}
+		}
+		delete triangleUsed;
+		delete vertexInCache;
+	}
+};
+
+void DeOptimizeIndexBuffers (Mesh& mesh)
+{
+	const int submeshCount = mesh.GetSubMeshCount();
+	const int vertexCount = mesh.GetVertexCount();
+    
+	// first optimize the indices for each submesh
+	for (int submesh = 0; submesh < submeshCount; submesh++)
+	{
+		Mesh::TemporaryIndexContainer unoptimizedIndices;
+		mesh.GetTriangles (unoptimizedIndices, submesh);
+        
+		Mesh::TemporaryIndexContainer deOptimizedIndices;
+		deOptimizedIndices.resize(unoptimizedIndices.size());
+        
+		VertexCacheDeOptimizer<UInt32, 16> vertexCacheDeOptimizer;
+		vertexCacheDeOptimizer.DeOptimizeTriangles(&deOptimizedIndices[0], vertexCount, &unoptimizedIndices[0], unoptimizedIndices.size() / 3);
+        
+		//LogString(Format("[Deoptimize] mesh: %s: submesh: %d hits: %d misses: %d\n", mesh.GetName(), submesh, vertexCacheDeOptimizer.GetCacheHits(), vertexCacheDeOptimizer.GetCacheMisses()));
+        
+		mesh.SetIndices (&deOptimizedIndices[0], deOptimizedIndices.size(), submesh, kPrimitiveTriangles);
+	}
+}
+