diff options
Diffstat (limited to 'Runtime/Misc/MeshWelding.cpp')
| -rw-r--r-- | Runtime/Misc/MeshWelding.cpp | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/Runtime/Misc/MeshWelding.cpp b/Runtime/Misc/MeshWelding.cpp new file mode 100644 index 0000000..2fee400 --- /dev/null +++ b/Runtime/Misc/MeshWelding.cpp @@ -0,0 +1,249 @@ +#include "UnityPrefix.h" +#include "Runtime/Misc/MeshWelding.h" +#include "Editor/Src/AssetPipeline/ImportMesh.h" + + +inline UInt32 GetVector3HashValue (const Vector3f& value) +{ + const UInt32* h = (const UInt32*)(&value); + UInt32 f = (h[0]+h[1]*11-(h[2]*17))&0x7fffffff; // avoid problems with +-0 + return (f>>22)^(f>>12)^(f); +} + +/* + In 12 operations, this code computes the next highest power of 2 for a 32-bit integer. The result may be expressed by the formula 1U << (lg(v - 1) + 1). + It would be faster by 2 operations to use the formula and the log base 2 methed that uses a lookup table, but in some situations, + lookup tables are not suitable, so the above code may be best. + */ + +inline int nextPowerOfTwo (UInt32 v) +{ + v--; + v |= v >> 1; + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + v++; + return v + (v==0); +} + +inline bool CompareBone(const BoneInfluence& lhs, const BoneInfluence& rhs) +{ + for (int i=0;i<4;i++) + { + if (!CompareApproximately(lhs.weight[0], rhs.weight[0]) || lhs.boneIndex[i] != rhs.boneIndex[i]) + return false; + } + return true; +} + + +#if UNITY_EDITOR + +/*-----------------------------------------------------------------------//* + ! + * \brief an array of vertex positions + * \param p Array of vertex positions (will be modified!) + * \param N Number of vertices in array + * \return Number of vertices after the welding operation + * \note The unique vertices are stored into the beginning of array + * 'p'. + * \note This welder is "bit-exact", i.e. only duplicate vertices are + * removed. For distance-based welding a somewhat more complicated + * algorithm needs to be used. + + *-------------------------------------------------------------------------*/ + +int weld (std::vector<Vector3f>& vertices, dynamic_array<BoneInfluence>& skin, std::vector<ImportBlendShape>& shapes, std::vector<int>& remap) +{ + const int NIL = -1; // linked list terminator symbol + int outputCount = 0; // # of output vertices + int hashSize = nextPowerOfTwo(vertices.size()); // size of the hash table + int* hashTable = new int[hashSize + vertices.size()]; // hash table + linked list + int* next = hashTable + hashSize; // use bottom part as linked list + + remap.resize(vertices.size()); + + memset (hashTable, NIL, (hashSize) * sizeof(int)); // init hash table (NIL = 0xFFFFFFFF so memset works) + + for (int i = 0; i < vertices.size(); i++) + { + const Vector3f& v = vertices[i]; + UInt32 hashValue = GetVector3HashValue(v) & (hashSize-1); + int offset = hashTable[hashValue]; + while (offset != NIL) + { + Assert (offset < i); + bool euqals = (vertices[offset] == v); + + if (euqals && !skin.empty() && !CompareBone(skin[i], skin[offset])) + euqals = false; + + if (euqals && !shapes.empty()) + { + for (int j = 0; j < shapes.size(); ++j) + { + if (shapes[j].vertices[i] != shapes[j].vertices[offset]) + { + euqals = false; + break; + } + } + } + + if (euqals) + break; + + offset = next[offset]; + } + + if (offset == NIL) // no match found - copy vertex & add to hash + { + remap[i] = outputCount; + vertices[outputCount] = v; // copy vertex + if (!skin.empty()) + skin[outputCount] = skin[i]; + for (int j = 0; j < shapes.size(); ++j) + shapes[j].vertices[outputCount] = shapes[j].vertices[i]; + + next[outputCount] = hashTable[hashValue]; // link to hash table + hashTable[hashValue] = outputCount++; // update hash heads and increase output counter + } + else + { + Assert (offset < i); + remap[i] = offset; + } + } + + delete[] hashTable; // cleanup + if (outputCount < vertices.size()) + { + vertices.resize(outputCount); + if (!skin.empty()) + skin.resize_initialized(outputCount); + for (int j = 0; j < shapes.size(); ++j) + shapes[j].vertices.resize(outputCount); + return true; + } + else + return false; +} + +void WeldVertices (ImportMesh& mesh) +{ + std::vector<int> remap; + if (weld (mesh.vertices, mesh.skin, mesh.shapes, remap)) + { + UInt32* indices = &mesh.polygons[0]; + for (int i=0;i<mesh.polygons.size();i++) + indices[i] = remap[indices[i]]; + } +} + +#endif + +bool WeldVertexArray(dynamic_array<Vector3f>& vertices, dynamic_array<UInt16>& triangles, dynamic_array<UInt16>& remap) +{ + Mesh::BoneInfluenceContainer skin; + return WeldVertexArray(vertices, skin, triangles, remap); +} + +bool WeldVertexArray(dynamic_array<Vector3f>& vertices, Mesh::BoneInfluenceContainer& skin, dynamic_array<UInt16>& triangles, dynamic_array<UInt16>& remap) +{ + const int NIL = -1; // linked list terminator symbol + int outputCount = 0; // # of output vertices + int hashSize = nextPowerOfTwo(vertices.size()); // size of the hash table + int* hashTable = new int[hashSize + vertices.size()]; // hash table + linked list + int* next = hashTable + hashSize; // use bottom part as linked list + + remap.resize_uninitialized(vertices.size()); + + memset (hashTable, NIL, (hashSize) * sizeof(int)); // init hash table (NIL = 0xFFFFFFFF so memset works) + + for (int i = 0; i < vertices.size(); i++) + { + const Vector3f& v = vertices[i]; + UInt32 hashValue = GetVector3HashValue(v) & (hashSize-1); + int offset = hashTable[hashValue]; + while (offset != NIL) + { + Assert (offset < i); + if (vertices[offset] == v) + { + if (skin.empty() || CompareBone(skin[i], skin[offset])) + break; + } + offset = next[offset]; + } + + if (offset == NIL) // no match found - copy vertex & add to hash + { + remap[i] = outputCount; + vertices[outputCount] = v; // copy vertex + + if (!skin.empty()) + skin[outputCount] = skin[i]; + + next[outputCount] = hashTable[hashValue]; // link to hash table + hashTable[hashValue] = outputCount++; // update hash heads and increase output counter + } + else + { + Assert (offset < i); + remap[i] = offset; + } + } + + delete[] hashTable; // cleanup + + if (outputCount < vertices.size()) + { + vertices.resize_uninitialized(outputCount); + if (!skin.empty()) + skin.resize_uninitialized(outputCount); + for (int i=0;i<triangles.size();i++) + triangles[i] = remap[triangles[i]]; + return true; + } + return false; +} + + +#if ENABLE_UNIT_TESTS + +#include "External/UnitTest++/src/UnitTest++.h" +#include "Runtime/Utilities/ArrayUtility.h" +SUITE (VertexWeldingTests) +{ + + TEST (TestVertexWelding) + { + Vector3f vertices[] = { Vector3f (0,0,0), Vector3f (1,0,0), Vector3f (1,0,0), Vector3f (0,0,0) }; + dynamic_array<Vector3f> dVertices; dVertices.assign(vertices, vertices + ARRAY_SIZE(vertices)); + + UInt16 indices[] = { 0, 1, 2, 3 }; + dynamic_array<UInt16> dIndices; dIndices.assign(indices, indices + ARRAY_SIZE(indices)); + + dynamic_array<UInt16> remap; + + WeldVertexArray(dVertices, dIndices, remap); + + CHECK_EQUAL(2, dVertices.size()); + CHECK(Vector3f(0,0,0) == dVertices[0]); + CHECK(Vector3f(1,0,0) == dVertices[1]); + + CHECK(0 == dIndices[0]); + CHECK(1 == dIndices[1]); + CHECK(1 == dIndices[2]); + CHECK(0 == dIndices[3]); + + CHECK_EQUAL(4, remap.size()); + CHECK_EQUAL(0, remap[0]); + CHECK_EQUAL(1, remap[1]); + CHECK_EQUAL(1, remap[2]); + CHECK_EQUAL(0, remap[3]); + } +} +#endif |