1 files changed, 171 insertions, 0 deletions
diff --git a/thirdparty/thekla_atlas/nvmesh/weld/Weld.h b/thirdparty/thekla_atlas/nvmesh/weld/Weld.h
new file mode 100644
index 0000000000..e615539461
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/weld/Weld.h
@@ -0,0 +1,171 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#ifndef NV_MESH_WELD_H
+#define NV_MESH_WELD_H
+
+#include "nvcore/Array.h"
+#include "nvcore/Hash.h"
+#include "nvcore/Utils.h" // nextPowerOfTwo
+
+#include <string.h> // for memset, memcmp, memcpy
+
+// Weld function to remove array duplicates in linear time using hashing.
+
+namespace nv
+{
+
+/// Generic welding routine. This function welds the elements of the array p
+/// and returns the cross references in the xrefs array. To compare the elements
+/// it uses the given hash and equal functors.
+/// 
+/// This code is based on the ideas of Ville Miettinen and Pierre Terdiman.
+template <class T, class H=Hash<T>, class E=Equal<T> >
+struct Weld
+{
+	// xrefs maps old elements to new elements
+	uint operator()(Array<T> & p, Array<uint> & xrefs)
+	{
+		const uint N = p.size();							// # of input vertices.
+		uint outputCount = 0;								// # of output vertices
+		uint hashSize = nextPowerOfTwo(N);					// size of the hash table
+		uint * hashTable = new uint[hashSize + N];			// hash table + linked list
+		uint * next = hashTable + hashSize;					// use bottom part as linked list
+
+		xrefs.resize(N);
+		memset( hashTable, NIL, hashSize*sizeof(uint) );	// init hash table (NIL = 0xFFFFFFFF so memset works)
+
+		H hash;
+		E equal;
+		for (uint i = 0; i < N; i++)
+		{
+			const T & e = p[i];
+			uint32 hashValue = hash(e) & (hashSize-1);
+			uint offset = hashTable[hashValue];
+
+			// traverse linked list
+			while( offset != NIL && !equal(p[offset], e) )
+			{
+				offset = next[offset];
+			}
+
+			xrefs[i] = offset;
+
+			// no match found - copy vertex & add to hash
+			if( offset == NIL )
+			{
+				// save xref
+				xrefs[i] = outputCount;
+
+				// copy element
+				p[outputCount] = e;
+
+				// link to hash table
+				next[outputCount] = hashTable[hashValue];
+
+				// update hash heads and increase output counter
+				hashTable[hashValue] = outputCount++;
+			}
+		}
+
+		// cleanup
+		delete [] hashTable;
+
+		p.resize(outputCount);
+		
+		// number of output vertices
+		return outputCount;
+	}
+};
+
+
+/// Reorder the given array accoding to the indices given in xrefs.
+template <class T>
+void reorderArray(Array<T> & array, const Array<uint> & xrefs)
+{
+	const uint count = xrefs.count();
+	Array<T> new_array;
+    new_array.resize(count);
+
+	for(uint i = 0; i < count; i++) {
+		new_array[i] = array[xrefs[i]];
+	}
+
+	swap(array, new_array);
+}
+
+/// Reverse the given array so that new indices point to old indices.
+inline void reverseXRefs(Array<uint> & xrefs, uint count)
+{
+	Array<uint> new_xrefs;
+    new_xrefs.resize(count);
+	
+	for(uint i = 0; i < xrefs.count(); i++) {
+		new_xrefs[xrefs[i]] = i;
+	}
+	
+	swap(xrefs, new_xrefs);
+}
+
+
+
+//
+struct WeldN
+{
+    uint vertexSize;
+
+    WeldN(uint n) : vertexSize(n) {}
+
+	// xrefs maps old elements to new elements
+	uint operator()(uint8 * ptr, uint N, Array<uint> & xrefs)
+	{
+		uint outputCount = 0;								// # of output vertices
+		uint hashSize = nextPowerOfTwo(N);					// size of the hash table
+		uint * hashTable = new uint[hashSize + N];			// hash table + linked list
+		uint * next = hashTable + hashSize;					// use bottom part as linked list
+
+		xrefs.resize(N);
+		memset( hashTable, NIL, hashSize*sizeof(uint) );	// init hash table (NIL = 0xFFFFFFFF so memset works)
+
+		for (uint i = 0; i < N; i++)
+		{
+			const uint8 * vertex = ptr + i * vertexSize;
+			uint32 hashValue = sdbmHash(vertex, vertexSize) & (hashSize-1);
+			uint offset = hashTable[hashValue];
+
+			// traverse linked list
+			while (offset != NIL && memcmp(ptr + offset * vertexSize, vertex, vertexSize) != 0)
+			{
+				offset = next[offset];
+			}
+
+			xrefs[i] = offset;
+
+			// no match found - copy vertex & add to hash
+			if (offset == NIL)
+			{
+				// save xref
+				xrefs[i] = outputCount;
+
+				// copy element
+                memcpy(ptr + outputCount * vertexSize, vertex, vertexSize);
+
+				// link to hash table
+				next[outputCount] = hashTable[hashValue];
+
+				// update hash heads and increase output counter
+				hashTable[hashValue] = outputCount++;
+			}
+		}
+
+		// cleanup
+		delete [] hashTable;
+
+		// number of output vertices
+		return outputCount;
+	}
+};
+
+
+} // nv namespace
+
+#endif // NV_MESH_WELD_H