5 files changed, 513 insertions, 0 deletions
diff --git a/thirdparty/thekla_atlas/nvmesh/weld/Snap.cpp b/thirdparty/thekla_atlas/nvmesh/weld/Snap.cpp
new file mode 100644
index 0000000000..b6bff4d83d
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/weld/Snap.cpp
@@ -0,0 +1,100 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#include <nvcore/RadixSort.h>
+
+#include <nvmesh/weld/Snap.h>
+#include <nvmesh/TriMesh.h>
+#include <nvmesh/geometry/Bounds.h>
+
+using namespace nv;
+
+namespace {
+	
+	// Snap the given vertices.
+	void Snap(TriMesh::Vertex & a, TriMesh::Vertex & b, float texThreshold, float norThreshold)
+	{
+		a.pos = b.pos = (a.pos + b.pos) * 0.5f;
+		
+		if (equal(a.tex.x, b.tex.x, texThreshold) && equal(a.tex.y, b.tex.y, texThreshold)) {
+			b.tex = a.tex = (a.tex + b.tex) * 0.5f;
+		}
+		
+		if (equal(a.nor.x, b.nor.x, norThreshold) && equal(a.nor.y, b.nor.y, norThreshold) && equal(a.nor.z, b.nor.z, norThreshold)) {
+			b.nor = a.nor = (a.nor + b.nor) * 0.5f;
+		}
+	};
+
+} // nv namespace
+
+uint nv::SnapVertices(TriMesh * mesh, float posThreshold, float texThreshold, float norThreshold)
+{
+	nvDebug("--- Snapping vertices.\n");
+	
+	// Determine largest axis.
+	Box box = MeshBounds::box(mesh);
+	Vector3 extents = box.extents();
+
+	int axis = 2;
+	if( extents.x > extents.y ) {
+		if( extents.x > extents.z ) {
+			axis = 0;
+		}
+	}
+	else if(extents.y > extents.z) {
+		axis = 1;
+	}
+	
+	// @@ Use diagonal instead!
+	
+
+	// Sort vertices according to the largest axis.
+	const uint vertexCount = mesh->vertexCount();
+	nvCheck(vertexCount > 2); // Must have at least two vertices.
+
+	// Get pos channel.
+	//PiMesh::Channel * pos_channel = mesh->GetChannel(mesh->FindChannel(VS_POS));
+	//nvCheck( pos_channel != NULL );
+
+	//const PiArray<Vec4> & pos_array = pos_channel->data;
+
+	Array<float> distArray;
+	distArray.resize(vertexCount);
+
+	for(uint v = 0; v < vertexCount; v++) {
+		if (axis == 0) distArray[v] = mesh->vertexAt(v).pos.x;
+		else if (axis == 1) distArray[v] = mesh->vertexAt(v).pos.y;
+		else distArray[v] = mesh->vertexAt(v).pos.z;
+	}
+
+	RadixSort radix;
+	const uint * xrefs = radix.sort(distArray.buffer(), distArray.count()).ranks();
+	nvCheck(xrefs != NULL);
+
+	uint snapCount = 0;
+	for(uint v = 0; v < vertexCount-1; v++) {
+		for(uint n = v+1; n < vertexCount; n++) {
+			nvDebugCheck( distArray[xrefs[v]] <= distArray[xrefs[n]] );
+			
+			if (fabs(distArray[xrefs[n]] - distArray[xrefs[v]]) > posThreshold) {
+				break;
+			}
+			
+			TriMesh::Vertex & v0 = mesh->vertexAt(xrefs[v]);
+			TriMesh::Vertex & v1 = mesh->vertexAt(xrefs[n]);
+			
+			const float dist = length(v0.pos - v1.pos);
+			
+			if (dist <= posThreshold) {
+				Snap(v0, v1, texThreshold, norThreshold);
+				snapCount++;
+			}
+		}
+	}
+
+	// @@ todo: debug, make sure that the distance between vertices is now >= threshold
+
+	nvDebug("---   %u vertices snapped\n", snapCount);
+
+	return snapCount;
+};
+
diff --git a/thirdparty/thekla_atlas/nvmesh/weld/Snap.h b/thirdparty/thekla_atlas/nvmesh/weld/Snap.h
new file mode 100644
index 0000000000..8e0566cda3
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/weld/Snap.h
@@ -0,0 +1,18 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#ifndef NV_MESH_SNAP_H
+#define NV_MESH_SNAP_H
+
+#include <nvmesh/nvmesh.h>
+#include <nvmath/nvmath.h>
+
+namespace nv
+{
+	class TriMesh;
+
+	NVMESH_API uint SnapVertices(TriMesh * mesh, float posThreshold=NV_EPSILON, float texThreshold=1.0f/1024, float norThreshold=NV_NORMAL_EPSILON);
+
+} // nv namespace
+
+
+#endif // NV_MESH_SNAP_H
diff --git a/thirdparty/thekla_atlas/nvmesh/weld/VertexWeld.cpp b/thirdparty/thekla_atlas/nvmesh/weld/VertexWeld.cpp
new file mode 100644
index 0000000000..2ba4dcae18
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/weld/VertexWeld.cpp
@@ -0,0 +1,205 @@
+// Copyright NVIDIA Corporation 2006 -- Ignacio Castano <icastano@nvidia.com>
+
+#include <nvmesh/TriMesh.h>
+#include <nvmesh/QuadTriMesh.h>
+
+#include <nvmesh/weld/VertexWeld.h>
+#include <nvmesh/weld/Weld.h>
+
+using namespace nv;
+
+// Weld trimesh vertices
+void nv::WeldVertices(TriMesh * mesh)
+{
+	nvDebug("--- Welding vertices.\n");
+	
+	nvCheck(mesh != NULL);
+
+	uint count = mesh->vertexCount();
+	Array<uint> xrefs;
+	Weld<TriMesh::Vertex> weld;
+	uint newCount = weld(mesh->vertices(), xrefs);
+	
+	nvDebug("---   %d vertices welded\n", count - newCount);
+	
+	
+	// Remap faces.
+	const uint faceCount = mesh->faceCount();
+	for(uint f = 0; f < faceCount; f++)
+	{
+		TriMesh::Face & face = mesh->faceAt(f);
+		face.v[0] = xrefs[face.v[0]];
+		face.v[1] = xrefs[face.v[1]];
+		face.v[2] = xrefs[face.v[2]];
+	}
+}
+
+
+// Weld trimesh vertices
+void nv::WeldVertices(QuadTriMesh * mesh)
+{
+	nvDebug("--- Welding vertices.\n");
+	
+	nvCheck(mesh != NULL);
+
+	uint  count = mesh->vertexCount();
+	Array<uint> xrefs;
+	Weld<TriMesh::Vertex> weld;
+	uint newCount = weld(mesh->vertices(), xrefs);
+	
+	nvDebug("---   %d vertices welded\n", count - newCount);
+	
+	// Remap faces.
+	const uint faceCount = mesh->faceCount();
+	for(uint f = 0; f < faceCount; f++)
+	{
+		QuadTriMesh::Face & face = mesh->faceAt(f);
+		face.v[0] = xrefs[face.v[0]];
+		face.v[1] = xrefs[face.v[1]];
+		face.v[2] = xrefs[face.v[2]];
+		
+		if (face.isQuadFace())
+		{
+			face.v[3] = xrefs[face.v[3]];
+		}
+	}
+}
+
+
+
+// OLD code
+
+#if 0
+
+namespace {
+
+struct VertexInfo {
+	uint id;			///< Original vertex id.
+	uint normal_face_group;
+	uint tangent_face_group;
+	uint material;
+	uint chart;
+};
+
+
+/// VertexInfo hash functor.
+struct VertexHash : public IHashFunctor<VertexInfo> {
+	VertexHash(PiMeshPtr m) : mesh(m) {
+		uint c = mesh->FindChannel(VS_POS);
+		piCheck(c != PI_NULL_INDEX);
+		channel = mesh->GetChannel(c);
+		piCheck(channel != NULL);
+	}
+
+	uint32 operator () (const VertexInfo & v) const {
+		return channel->data[v.id].GetHash();
+	}
+	
+private:
+	PiMeshPtr mesh;
+	PiMesh::Channel * channel;
+};
+
+
+/// VertexInfo comparator.
+struct VertexEqual : public IBinaryPredicate<VertexInfo> {
+	VertexEqual(PiMeshPtr m) : mesh(m) {}
+	
+	bool operator () (const VertexInfo & a, const VertexInfo & b) const {
+
+		bool equal = a.normal_face_group == b.normal_face_group && 
+			a.tangent_face_group == b.tangent_face_group &&
+			a.material == b.material && 
+			a.chart == b.chart;
+		
+		// Split vertex shared by different face types.
+		if( !equal ) {
+			return false;
+		}
+		
+		// They were the same vertex.
+		if( a.id == b.id ) {
+			return true;
+		}
+		
+		// Vertex equal if all the channels are equal.
+		return mesh->IsVertexEqual(a.id, b.id);
+	}
+
+private:	
+	PiMeshPtr mesh;
+};
+
+} // namespace
+
+
+/// Weld the vertices.
+void PiMeshVertexWeld::WeldVertices(const PiMeshSmoothGroup * mesh_smooth_group, 
+	const PiMeshMaterial * mesh_material, const PiMeshAtlas * mesh_atlas ) 
+{
+	piDebug( "--- Welding vertices:\n" );
+
+	piDebug( "---   Expand mesh vertices.\n" );
+	PiArray<VertexInfo> vertex_array;
+
+	const uint face_num = mesh->GetFaceNum();
+	const uint vertex_max = face_num * 3;
+	vertex_array.Resize( vertex_max );
+
+	for(uint i = 0; i < vertex_max; i++) {
+
+		uint f = i/3;
+	
+		const PiMesh::Face & face = mesh->GetFace(f);
+		vertex_array[i].id = face.v[i%3];
+
+		// Reset face attributes.
+		vertex_array[i].normal_face_group = PI_NULL_INDEX;
+		vertex_array[i].tangent_face_group = PI_NULL_INDEX;
+		vertex_array[i].material = PI_NULL_INDEX;
+		vertex_array[i].chart = PI_NULL_INDEX;
+		
+		// Set available attributes.
+		if( mesh_smooth_group != NULL ) {
+			if( mesh_smooth_group->HasNormalFaceGroups() ) {
+				vertex_array[i].normal_face_group = mesh_smooth_group->GetNormalFaceGroup( f );
+			}
+			if( mesh_smooth_group->HasTangentFaceGroups() ) {
+				vertex_array[i].tangent_face_group = mesh_smooth_group->GetTangentFaceGroup( f );
+			}
+		}
+		if( mesh_material != NULL ) {
+			vertex_array[i].material = mesh_material->GetFaceMaterial( f );
+		}
+		if( mesh_atlas != NULL && mesh_atlas->HasCharts() ) {
+			vertex_array[i].chart = mesh_atlas->GetFaceChart( f );
+		}
+	}
+	piDebug( "---   %d vertices.\n", vertex_max );
+
+	piDebug( "---   Collapse vertices.\n" );
+
+	uint * xrefs = new uint[vertex_max];
+	VertexHash hash(mesh);
+	VertexEqual equal(mesh);
+	const uint vertex_num = Weld( vertex_array, xrefs, hash, equal );
+	piCheck(vertex_num <= vertex_max);
+	piDebug( "---   %d vertices.\n", vertex_num );	
+	
+	// Remap face indices.
+	piDebug( "---   Remapping face indices.\n" );
+	mesh->RemapFaceIndices(vertex_max, xrefs);
+
+
+	// Overwrite xrefs to map new vertices to old vertices.
+	for(uint v = 0; v < vertex_num; v++) {
+		xrefs[v] = vertex_array[v].id;
+	}
+	
+	// Update vertex order.
+	mesh->ReorderVertices(vertex_num, xrefs);
+
+	delete [] xrefs;
+}
+
+#endif // 0
diff --git a/thirdparty/thekla_atlas/nvmesh/weld/VertexWeld.h b/thirdparty/thekla_atlas/nvmesh/weld/VertexWeld.h
new file mode 100644
index 0000000000..1dc2e4ba4d
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/weld/VertexWeld.h
@@ -0,0 +1,19 @@
+// Copyright NVIDIA Corporation 2006 -- Ignacio Castano <icastano@nvidia.com>
+
+#ifndef NV_MESH_VERTEXWELD_H
+#define NV_MESH_VERTEXWELD_H
+
+#include <nvmesh/nvmesh.h>
+
+namespace nv
+{
+	class TriMesh;
+	class QuadMesh;
+
+	NVMESH_API void WeldVertices(TriMesh * mesh);
+	NVMESH_API void WeldVertices(QuadTriMesh * mesh);
+
+} // nv namespace
+
+
+#endif // NV_MESH_VERTEXWELD_H
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