VertexHashMap refactor
MODIFY
include/irr/asset/IMeshManipulator.h
include/irr/asset/IMeshManipulator.h
#include "IAnimatedMesh.h"
#include "irr/asset/ICPUMeshBuffer.h"
#include "SVertexManipulator.h"
+#include "irr/asset/CSmoothNormalGenerator.h"
#include "irr/asset/SCPUMesh.h"
namespace irr
@@ -75,7 +76,8 @@ namespace asset
virtual asset::ICPUMeshBuffer* createMeshBufferUniquePrimitives(asset::ICPUMeshBuffer* inbuffer) const = 0;
//
- virtual asset::ICPUMeshBuffer* calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, const float creaseAngle, float epsilon = 1.525e-5f) const = 0;
+ virtual asset::ICPUMeshBuffer* calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, float epsilon = 1.525e-5f,
+ asset::E_VERTEX_ATTRIBUTE_ID normalAttrID = asset::E_VERTEX_ATTRIBUTE_ID::EVAI_ATTR3, VxCmpFunction vxcmp = defaultVxCmpFunction) const = 0;
//! Creates a copy of a mesh with vertices welded
/** \param mesh Input mesh

MODIFY
src/irr/asset/CMeshManipulator.cpp
src/irr/asset/CMeshManipulator.cpp
#include "irr/asset/ICPUSkinnedMeshBuffer.h"
#include "irr/asset/CSmoothNormalGenerator.h"
-#include <chrono>
-
namespace irr
{
namespace asset
@@ -700,27 +698,15 @@ asset::ICPUMeshBuffer* CMeshManipulator::createMeshBufferUniquePrimitives(asset:
return clone;
}
-asset::ICPUMeshBuffer* CMeshManipulator::calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, const float creaseAngle, float epsilon) const
+asset::ICPUMeshBuffer* CMeshManipulator::calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, float epsilon,
+ asset::E_VERTEX_ATTRIBUTE_ID normalAttrID, VxCmpFunction vxcmp) const
{
if (inbuffer == nullptr)
return nullptr;
- asset::ICPUMeshBuffer* outbuffer;
-
- //will get rid of that
- if (true)
- outbuffer = createMeshBufferUniquePrimitives(inbuffer);
- else
- outbuffer = createMeshBufferDuplicate(inbuffer);
-
-
- std::cout << "\n\n computation time: ";
-
- auto start = std::chrono::high_resolution_clock::now();
-
- CSmoothNormalGenerator::calculateNormals_hash(outbuffer, creaseAngle, epsilon);
+ asset::ICPUMeshBuffer* outbuffer = createMeshBufferUniquePrimitives(inbuffer);
- std::cout << std::chrono::duration_cast<std::chrono::duration<double, std::milli>>(std::chrono::high_resolution_clock::now() - start).count() << std::endl;
+ CSmoothNormalGenerator::calculateNormals(outbuffer, epsilon, normalAttrID, vxcmp);
return outbuffer;
}

MODIFY
src/irr/asset/CMeshManipulator.h
src/irr/asset/CMeshManipulator.h
@@ -66,7 +66,8 @@ public:
virtual asset::ICPUMeshBuffer* createMeshBufferUniquePrimitives(asset::ICPUMeshBuffer* inbuffer) const;
//
- virtual asset::ICPUMeshBuffer* calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, const float creaseAngle, float epsilon = 1.525e-5f) const override;
+ virtual asset::ICPUMeshBuffer* calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, float epsilon = 1.525e-5f,
+ asset::E_VERTEX_ATTRIBUTE_ID normalAttrID = asset::E_VERTEX_ATTRIBUTE_ID::EVAI_ATTR3, VxCmpFunction vxcmp = defaultVxCmpFunction) const override;
//! Creates a copy of the mesh, which will have all duplicated vertices removed, i.e. maximal amount of vertices are shared via indexing.
virtual asset::ICPUMeshBuffer* createMeshBufferWelded(asset::ICPUMeshBuffer *inbuffer, const SErrorMetric* _errMetrics, const bool& optimIndexType = true, const bool& makeNewMesh=false) const;

MODIFY
src/irr/asset/CSmoothNormalGenerator.cpp
src/irr/asset/CSmoothNormalGenerator.cpp
#include "CSmoothNormalGenerator.h"
#include <iostream>
+#include <algorithm>
namespace irr
{
namespace asset
{
+bool defaultVxCmpFunction(const SSNGVertexData& v0, const SSNGVertexData& v1, asset::ICPUMeshBuffer* buffer)
+{
+ static constexpr float cosOf45Deg = 0.70710678118f;
+ return v0.parentTriangleFaceNormal.dotProductAsFloat(v1.parentTriangleFaceNormal) > cosOf45Deg;
+}
+
+//needed for std::upper_boud
+static inline bool operator<(uint32_t lhs, const SSNGVertexData& rhs)
+{
+ return lhs < rhs.hash;
+}
+
static inline bool compareVertexPosition(const core::vectorSIMDf& a, const core::vectorSIMDf& b, float epsilon)
{
const core::vectorSIMDf difference = core::abs(b - a);
@@ -33,121 +46,73 @@ static inline core::vector3df_SIMD getAngleWeight(const core::vector3df_SIMD & v
acosf((b - c + a) / (2.f * bsqrt * asqrt)));
}
-#pragma region linearSearch
-
-asset::ICPUMeshBuffer* irr::asset::CSmoothNormalGenerator::calculateNormals(asset::ICPUMeshBuffer* buffer, float creaseAngle, float epsilon)
+asset::ICPUMeshBuffer* irr::asset::CSmoothNormalGenerator::calculateNormals(asset::ICPUMeshBuffer* buffer, float epsilon, asset::E_VERTEX_ATTRIBUTE_ID normalAttrID, VxCmpFunction vxcmp)
{
- core::vector<Vertex> vertexArray = setupData(buffer, creaseAngle);
- processConnectedVertices(buffer, vertexArray, creaseAngle, epsilon);
+ //should i always trust RVO?
+ VertexHashMap vertexArray = setupData(buffer, epsilon);
+ processConnectedVertices(buffer, vertexArray, epsilon, normalAttrID, vxcmp);
return buffer;
}
-core::vector<CSmoothNormalGenerator::Vertex> CSmoothNormalGenerator::setupData(asset::ICPUMeshBuffer* buffer, float creaseAngle)
-{
- core::vector<Vertex> vertices;
-
- const size_t idxCount = buffer->getIndexCount();
- const size_t vxCount = buffer->calcVertexCount();
- _IRR_DEBUG_BREAK_IF((idxCount % 3));
-
- vertices.reserve(idxCount);
-
- core::vector3df_SIMD faceNormal;
-
- for (uint32_t i = 0; i < idxCount; i += 3)
+CSmoothNormalGenerator::VertexHashMap::VertexHashMap(size_t _vertexCount, uint32_t _hashTableMaxSize, float _cellSize)
+ :hashTableMaxSize(_hashTableMaxSize),
+ cellSize(_cellSize)
{
- //calculate face normal of parent triangle
- core::vectorSIMDf v1 = buffer->getPosition(i);
- core::vectorSIMDf v2 = buffer->getPosition(i + 1);
- core::vectorSIMDf v3 = buffer->getPosition(i + 2);
-
- faceNormal = core::cross(v2 - v1, v3 - v1);
- faceNormal = core::normalize(faceNormal);
-
- //set data for vertices
- core::vector3df_SIMD angleWages = getAngleWeight(v1, v2, v3);
- vertices.push_back({ i, angleWages.x, v1, faceNormal * angleWages.x, faceNormal });
- vertices.push_back({ i + 1, angleWages.y, v2, faceNormal * angleWages.y, faceNormal });
- vertices.push_back({ i + 2, angleWages.z, v3, faceNormal * angleWages.z, faceNormal });
- }
-
- return vertices;
+ vertices.reserve(_vertexCount);
+ buckets.reserve(_hashTableMaxSize+1);
}
-void CSmoothNormalGenerator::processConnectedVertices(asset::ICPUMeshBuffer* buffer, core::vector<Vertex>& vertices, float creaseAngle, float epsilon)
-{
- for (size_t i = 0; i < vertices.size(); i++)
- {
- float cosOfCreaseAngle = std::cos(creaseAngle);
- Vertex processedVertex = vertices[i];
-
- for (size_t j = i+1; j < vertices.size(); j++)
- {
- if (compareVertexPosition(processedVertex.position, vertices[j].position, epsilon))
- if (processedVertex.parentTriangleFaceNormal.dotProductAsFloat(vertices[j].parentTriangleFaceNormal) > cosOfCreaseAngle)
- {
- processedVertex.normal += vertices[j].parentTriangleFaceNormal * vertices[j].wage;
- vertices[j].normal += processedVertex.parentTriangleFaceNormal * processedVertex.wage;
- }
-
- }
-
- processedVertex.normal = core::normalize(processedVertex.normal);
- buffer->setAttribute(processedVertex.normal, asset::E_VERTEX_ATTRIBUTE_ID::EVAI_ATTR3, processedVertex.indexOffset);
- }
-
-}
-
-#pragma endregion
-
-
-#pragma region hashing
-
-CSmoothNormalGenerator::VertexHashMap::VertexHashMap(size_t _hashTableSize, float _cellSize)
- :hashTableSize(_hashTableSize), cellSize(_cellSize)
-{
- hashTable.reserve(hashTableSize);
-
- for (int i = 0; i < hashTableSize; i++)
- hashTable.emplace_back();
-
-}
-
-uint32_t CSmoothNormalGenerator::VertexHashMap::hash(const CSmoothNormalGenerator::Vertex& vertex) const
+uint32_t CSmoothNormalGenerator::VertexHashMap::hash(const SSNGVertexData& vertexPosition) const
{
static constexpr uint32_t primeNumber1 = 73856093;
static constexpr uint32_t primeNumber2 = 19349663;
static constexpr uint32_t primeNumber3 = 83492791;
- const core::vector3df_SIMD position = vertex.position / cellSize;
+ const core::vector3df_SIMD position = vertexPosition.position / cellSize;
return (((uint32_t)position.x * primeNumber1) ^
((uint32_t)position.y * primeNumber2) ^
- ((uint32_t)position.z * primeNumber3)) % hashTableSize;
+ ((uint32_t)position.z * primeNumber3)) & (hashTableMaxSize - 1);
}
-void CSmoothNormalGenerator::VertexHashMap::add(const Vertex& vertex)
+void CSmoothNormalGenerator::VertexHashMap::add(const SSNGVertexData& vertex)
{
- hashTable[hash(vertex)].push_back(vertex);
+ const_cast<uint32_t&>(vertex.hash) = hash(vertex);
+ vertices.push_back(vertex);
}
-asset::ICPUMeshBuffer * irr::asset::CSmoothNormalGenerator::calculateNormals_hash(asset::ICPUMeshBuffer * buffer, float creaseAngle, float epsilon)
+void CSmoothNormalGenerator::VertexHashMap::validate()
{
- VertexHashMap vertexArray = setupData_hash(buffer, creaseAngle);
- processConnectedVertices_hash(buffer, vertexArray, creaseAngle, epsilon);
+ std::sort(vertices.begin(), vertices.end(), [](SSNGVertexData& a, SSNGVertexData& b) { return a.hash < b.hash; });
- return buffer;
-}
+ uint16_t prevHash = vertices[0].hash;
+ core::vector<SSNGVertexData>::iterator prevBegin = vertices.begin();
+ buckets.push_back(prevBegin);
-CSmoothNormalGenerator::VertexHashMap CSmoothNormalGenerator::setupData_hash(asset::ICPUMeshBuffer * buffer, float creaseAngle)
+ while (true)
{
- //hash map and cell size is constant (that will be changed ofc)
- VertexHashMap vertices(200, 0.001f);
+ core::vector<SSNGVertexData>::iterator next = std::upper_bound(prevBegin, vertices.end(), prevHash);
+
+ buckets.push_back(next);
+
+ if (next == vertices.end())
+ break;
+ prevBegin = next;
+ prevHash = next->hash;
+ }
+}
+
+CSmoothNormalGenerator::VertexHashMap CSmoothNormalGenerator::setupData(asset::ICPUMeshBuffer * buffer, float epsilon)
+{
const size_t idxCount = buffer->getIndexCount();
const size_t vxCount = buffer->calcVertexCount();
+
_IRR_DEBUG_BREAK_IF((idxCount % 3));
+ _IRR_DEBUG_BREAK_IF((idxCount != vxCount));
+
+ VertexHashMap vertices(vxCount, std::min(16u * 1024u, core::roundUpToPoT<unsigned int>(idxCount * 1.0f / 32.0f)), epsilon * 1.2f);
core::vector3df_SIMD faceNormal;
@@ -164,47 +129,46 @@ CSmoothNormalGenerator::VertexHashMap CSmoothNormalGenerator::setupData_hash(ass
//set data for vertices
core::vector3df_SIMD angleWages = getAngleWeight(v1, v2, v3);
- vertices.add({ i, angleWages.x, v1, faceNormal * angleWages.x, faceNormal });
- vertices.add({ i + 1, angleWages.y, v2, faceNormal * angleWages.y, faceNormal });
- vertices.add({ i + 2, angleWages.z, v3, faceNormal * angleWages.z, faceNormal });
+ vertices.add({ i, 0, angleWages.x, v1, faceNormal * angleWages.x, faceNormal });
+ vertices.add({ i + 1, 0, angleWages.y, v2, faceNormal * angleWages.y, faceNormal });
+ vertices.add({ i + 2, 0, angleWages.z, v3, faceNormal * angleWages.z, faceNormal });
}
+ vertices.validate();
+
return vertices;
}
-void CSmoothNormalGenerator::processConnectedVertices_hash(asset::ICPUMeshBuffer * buffer, CSmoothNormalGenerator::VertexHashMap& vertexHashMap, float creaseAngle, float epsilon)
-{
-
- for (uint32_t cell = 0; cell < vertexHashMap.getTableSize(); cell++)
+void CSmoothNormalGenerator::processConnectedVertices(asset::ICPUMeshBuffer * buffer, VertexHashMap & vertexHashMap, float epsilon, asset::E_VERTEX_ATTRIBUTE_ID normalAttrID, VxCmpFunction vxcmp)
{
- core::vector<Vertex> vertices = vertexHashMap.getBucket(cell);
+ core::vector<SSNGVertexData>::iterator bucketBegin;
+ core::vector<SSNGVertexData>::iterator bucketEnd;
- for (size_t i = 0; i < vertices.size(); i++)
+ for (uint32_t cell = 0; cell < vertexHashMap.getBucketCount() - 1; cell++)
{
- float cosOfCreaseAngle = std::cos(creaseAngle);
- Vertex processedVertex = vertices[i];
+ bucketBegin = vertexHashMap.getBucket(cell);
+ bucketEnd = vertexHashMap.getBucket(cell + 1);
- for (size_t j = i + 1; j < vertices.size(); j++)
+ for (core::vector<SSNGVertexData>::iterator processedVertex = bucketBegin; processedVertex != bucketEnd; processedVertex++)
{
- if (compareVertexPosition(processedVertex.position, vertices[j].position, epsilon))
+ for (core::vector<SSNGVertexData>::iterator nextVertex = processedVertex+1; nextVertex != bucketEnd; nextVertex++)
{
- if (processedVertex.parentTriangleFaceNormal.dotProductAsFloat(vertices[j].parentTriangleFaceNormal) > cosOfCreaseAngle)
+ if (compareVertexPosition(processedVertex->position, nextVertex->position, epsilon) &&
+ vxcmp(*processedVertex, *nextVertex, buffer))
{
- processedVertex.normal += vertices[j].parentTriangleFaceNormal * vertices[j].wage;
- vertices[j].normal += processedVertex.parentTriangleFaceNormal * processedVertex.wage;
- }
+ processedVertex->normal += nextVertex->parentTriangleFaceNormal * nextVertex->wage;
+ nextVertex->normal += processedVertex->parentTriangleFaceNormal * processedVertex->wage;
}
}
- processedVertex.normal = core::normalize(processedVertex.normal);
- buffer->setAttribute(processedVertex.normal, asset::E_VERTEX_ATTRIBUTE_ID::EVAI_ATTR3, processedVertex.indexOffset);
+ processedVertex->normal = core::normalize(processedVertex->normal);
+ buffer->setAttribute(processedVertex->normal, normalAttrID, processedVertex->indexOffset);
}
}
}
-#pragma endregion
-
}
}
+

MODIFY
src/irr/asset/CSmoothNormalGenerator.h
src/irr/asset/CSmoothNormalGenerator.h
#define __C_SMOOTH_NORMAL_GENERATOR_H_INCLUDED__
#include <iostream>
+#include <functional>
#include "irr/asset/ICPUMeshBuffer.h"
#include "irr/core/math/irrMath.h"
+
namespace irr
{
namespace asset
{
+//vertex data needed for CSmoothNormalGenerator
+struct SSNGVertexData
+{
+ uint32_t indexOffset; //offset of the vertex into index buffer
+ uint32_t hash; //
+ float wage; //angle wage of the vertex
+ core::vector4df_SIMD position; //position of the vertex in 3D space
+ core::vector3df_SIMD normal; //normal to be smoothed
+ core::vector3df_SIMD parentTriangleFaceNormal; //
+};
+
+typedef std::function<bool(const SSNGVertexData&, const SSNGVertexData&, asset::ICPUMeshBuffer*)> VxCmpFunction;
+
+//returns true if crease angle between parent triangles of vertices v0 and v1 is lower than 45 degrees
+bool defaultVxCmpFunction(const SSNGVertexData&, const SSNGVertexData&, asset::ICPUMeshBuffer*);
class CSmoothNormalGenerator
{
public:
- static asset::ICPUMeshBuffer* calculateNormals(asset::ICPUMeshBuffer* buffer, float creaseAngle, float epsilon);
- static asset::ICPUMeshBuffer* calculateNormals_hash(asset::ICPUMeshBuffer* buffer, float creaseAngle, float epsilon);
+ static asset::ICPUMeshBuffer* calculateNormals(asset::ICPUMeshBuffer* buffer, float epsilon, asset::E_VERTEX_ATTRIBUTE_ID normalAttrID, VxCmpFunction function);
CSmoothNormalGenerator() = delete;
~CSmoothNormalGenerator() = delete;
-public:
- struct Vertex
- {
- uint32_t indexOffset; //offset of the vertex into index buffer
- float wage; //angle wage of the vertex
- core::vector3df_SIMD position; //position of the vertex in 3D space
- core::vector3df_SIMD normal; //normal to be smoothed
- core::vector3df_SIMD parentTriangleFaceNormal;
- };
-
private:
class VertexHashMap
{
public:
- VertexHashMap(size_t _hashTableSize, float _cellSize);
+ VertexHashMap(size_t _vertexCount, uint32_t _hashTableMaxSize, float _cellSize);
+
+ //inserts vertex into hash table
+ void add(const SSNGVertexData& vertex);
- //similar to std::unordered_map::insert
- void add(const Vertex& vertex);
+ //sorts hashtable and sets iterators at beginnings of bucktes
+ void validate();
- inline size_t getTableSize() { return hashTableSize; }
- //returns array of vertices assigned to hash with value of parameter index
- inline core::vector<Vertex>& getBucket(size_t index) { return hashTable[index]; }
+ //small number of unused buckets still may occure
+ inline uint32_t getBucketCount() const { return buckets.size(); }
+ inline core::vector<SSNGVertexData>::iterator getBucket(uint32_t index) { return buckets[index]; }
private:
- core::vector<core::vector<Vertex>> hashTable;
- const size_t hashTableSize;
+ //holds iterators pointing to beginning of each bucket, last iterator points to vertices.end()
+ core::vector<core::vector<SSNGVertexData>::iterator> buckets;
+ core::vector<SSNGVertexData> vertices;
+ const uint32_t hashTableMaxSize;
const float cellSize;
private:
- uint32_t hash(const Vertex& vertex) const;
+ uint32_t hash(const SSNGVertexData& vertexPosition) const;
+
};
private:
- //I keep these for reference
- static core::vector<Vertex> setupData(asset::ICPUMeshBuffer* buffer, float creaseAngle);
- static void processConnectedVertices(asset::ICPUMeshBuffer* buffer, core::vector<Vertex>& vertices, float creaseAngle, float epsilon);
-
- static VertexHashMap setupData_hash(asset::ICPUMeshBuffer* buffer, float creaseAngle);
- static void processConnectedVertices_hash(asset::ICPUMeshBuffer* buffer, VertexHashMap& vertices, float creaseAngle, float epsilon);
+ static VertexHashMap setupData(asset::ICPUMeshBuffer* buffer, float epsilon);
+ static void processConnectedVertices(asset::ICPUMeshBuffer* buffer, VertexHashMap& vertices, float epsilon, asset::E_VERTEX_ATTRIBUTE_ID normalAttrID, VxCmpFunction vxcmp);
};

VertexHashMap refactor