added hashing
MODIFY
include/irr/asset/IMeshManipulator.h
include/irr/asset/IMeshManipulator.h
@@ -75,7 +75,7 @@ namespace asset
virtual asset::ICPUMeshBuffer* createMeshBufferUniquePrimitives(asset::ICPUMeshBuffer* inbuffer) const = 0;
//
- virtual asset::ICPUMeshBuffer* calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, const float creaseAngle, bool makeTriangleSoup = true) const = 0;
+ virtual asset::ICPUMeshBuffer* calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, const float creaseAngle, float epsilon = 1.525e-5f) 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
@@ -698,19 +700,27 @@ asset::ICPUMeshBuffer* CMeshManipulator::createMeshBufferUniquePrimitives(asset:
return clone;
}
-asset::ICPUMeshBuffer* CMeshManipulator::calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, const float creaseAngle, bool makeTriangleSoup) const
+asset::ICPUMeshBuffer* CMeshManipulator::calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, const float creaseAngle, float epsilon) const
{
if (inbuffer == nullptr)
return nullptr;
asset::ICPUMeshBuffer* outbuffer;
- if (makeTriangleSoup)
+ //will get rid of that
+ if (true)
outbuffer = createMeshBufferUniquePrimitives(inbuffer);
else
outbuffer = createMeshBufferDuplicate(inbuffer);
- CSmoothNormalGenerator::calculateNormals(outbuffer,creaseAngle);
+
+ std::cout << "\n\n computation time: ";
+
+ auto start = std::chrono::high_resolution_clock::now();
+
+ CSmoothNormalGenerator::calculateNormals_hash(outbuffer, creaseAngle, epsilon);
+
+ std::cout << std::chrono::duration_cast<std::chrono::duration<double, std::milli>>(std::chrono::high_resolution_clock::now() - start).count() << std::endl;
return outbuffer;
}

MODIFY
src/irr/asset/CMeshManipulator.h
src/irr/asset/CMeshManipulator.h
@@ -66,7 +66,7 @@ public:
virtual asset::ICPUMeshBuffer* createMeshBufferUniquePrimitives(asset::ICPUMeshBuffer* inbuffer) const;
//
- virtual asset::ICPUMeshBuffer* calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, const float creaseAngle, bool makeTriangleSoup = true) const override;
+ virtual asset::ICPUMeshBuffer* calculateSmoothNormals(asset::ICPUMeshBuffer* inbuffer, const float creaseAngle, float epsilon = 1.525e-5f) 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
@@ -7,6 +7,12 @@ namespace irr
namespace asset
{
+static inline bool compareVertexPosition(const core::vectorSIMDf& a, const core::vectorSIMDf& b, float epsilon)
+{
+ const core::vectorSIMDf difference = core::abs(b - a);
+ return (difference.x <= epsilon && difference.y <= epsilon && difference.z <= epsilon);
+}
+
static inline core::vector3df_SIMD getAngleWeight(const core::vector3df_SIMD & v1,
const core::vector3df_SIMD & v2,
const core::vector3df_SIMD & v3)
@@ -27,11 +33,12 @@ 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)
+asset::ICPUMeshBuffer* irr::asset::CSmoothNormalGenerator::calculateNormals(asset::ICPUMeshBuffer* buffer, float creaseAngle, float epsilon)
{
core::vector<Vertex> vertexArray = setupData(buffer, creaseAngle);
- processConnectedVertices(buffer, vertexArray, creaseAngle);
+ processConnectedVertices(buffer, vertexArray, creaseAngle, epsilon);
return buffer;
}
@@ -40,8 +47,8 @@ core::vector<CSmoothNormalGenerator::Vertex> CSmoothNormalGenerator::setupData(a
{
core::vector<Vertex> vertices;
- size_t idxCount = buffer->getIndexCount();
- size_t vxCount = buffer->calcVertexCount();
+ const size_t idxCount = buffer->getIndexCount();
+ const size_t vxCount = buffer->calcVertexCount();
_IRR_DEBUG_BREAK_IF((idxCount % 3));
vertices.reserve(idxCount);
@@ -59,15 +66,16 @@ core::vector<CSmoothNormalGenerator::Vertex> CSmoothNormalGenerator::setupData(a
faceNormal = core::normalize(faceNormal);
//set data for vertices
- core::vector3df_SIMD angleWages = getAngleWeight(buffer->getPosition(i), buffer->getPosition(i + 1), buffer->getPosition(i + 2));
- vertices.push_back({ i, faceNormal * angleWages.x, faceNormal, angleWages.x });
- vertices.push_back({ i + 1, faceNormal * angleWages.y, faceNormal, angleWages.y });
- vertices.push_back({ i + 2, faceNormal * angleWages.z, faceNormal, angleWages.z });
+ 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;
}
-void CSmoothNormalGenerator::processConnectedVertices(asset::ICPUMeshBuffer* buffer, core::vector<Vertex>& vertices, float creaseAngle)
+
+void CSmoothNormalGenerator::processConnectedVertices(asset::ICPUMeshBuffer* buffer, core::vector<Vertex>& vertices, float creaseAngle, float epsilon)
{
for (size_t i = 0; i < vertices.size(); i++)
{
@@ -76,22 +84,127 @@ void CSmoothNormalGenerator::processConnectedVertices(asset::ICPUMeshBuffer* buf
for (size_t j = i+1; j < vertices.size(); j++)
{
- if (buffer->getPosition(processedVertex.indexOffset).x == buffer->getPosition(vertices[j].indexOffset).x &&
- buffer->getPosition(processedVertex.indexOffset).y == buffer->getPosition(vertices[j].indexOffset).y &&
- buffer->getPosition(processedVertex.indexOffset).z == buffer->getPosition(vertices[j].indexOffset).z)
+ 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);
- if (!buffer->setAttribute(processedVertex.normal, asset::E_VERTEX_ATTRIBUTE_ID::EVAI_ATTR3, processedVertex.indexOffset))
- _IRR_DEBUG_BREAK_IF(true);
+ 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
+{
+ 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;
+
+ return (((uint32_t)position.x * primeNumber1) ^
+ ((uint32_t)position.y * primeNumber2) ^
+ ((uint32_t)position.z * primeNumber3)) % hashTableSize;
}
+
+void CSmoothNormalGenerator::VertexHashMap::add(const Vertex& vertex)
+{
+ hashTable[hash(vertex)].push_back(vertex);
}
+asset::ICPUMeshBuffer * irr::asset::CSmoothNormalGenerator::calculateNormals_hash(asset::ICPUMeshBuffer * buffer, float creaseAngle, float epsilon)
+{
+ VertexHashMap vertexArray = setupData_hash(buffer, creaseAngle);
+ processConnectedVertices_hash(buffer, vertexArray, creaseAngle, epsilon);
+
+ return buffer;
+}
+
+CSmoothNormalGenerator::VertexHashMap CSmoothNormalGenerator::setupData_hash(asset::ICPUMeshBuffer * buffer, float creaseAngle)
+{
+ //hash map and cell size is constant (that will be changed ofc)
+ VertexHashMap vertices(200, 0.001f);
+
+ const size_t idxCount = buffer->getIndexCount();
+ const size_t vxCount = buffer->calcVertexCount();
+ _IRR_DEBUG_BREAK_IF((idxCount % 3));
+
+ core::vector3df_SIMD faceNormal;
+
+ for (uint32_t i = 0; i < idxCount; i += 3)
+ {
+ //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.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 });
+ }
+
+ 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++)
+ {
+ core::vector<Vertex> vertices = vertexHashMap.getBucket(cell);
+
+ 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
+
+}
+}
\ No newline at end of file

MODIFY
src/irr/asset/CSmoothNormalGenerator.h
src/irr/asset/CSmoothNormalGenerator.h
@@ -14,23 +14,52 @@ namespace asset
class CSmoothNormalGenerator
{
public:
- static asset::ICPUMeshBuffer* calculateNormals(asset::ICPUMeshBuffer* buffer, float creaseAngle);
+ static asset::ICPUMeshBuffer* calculateNormals(asset::ICPUMeshBuffer* buffer, float creaseAngle, float epsilon);
+ static asset::ICPUMeshBuffer* calculateNormals_hash(asset::ICPUMeshBuffer* buffer, float creaseAngle, float epsilon);
-private:
+ CSmoothNormalGenerator() = delete;
+ ~CSmoothNormalGenerator() = delete;
+
+public:
struct Vertex
{
- uint32_t indexOffset;
- core::vector3df_SIMD normal;
+ 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;
- float wage;
};
private:
+ class VertexHashMap
+ {
+ public:
+ VertexHashMap(size_t _hashTableSize, float _cellSize);
+
+ //similar to std::unordered_map::insert
+ void add(const Vertex& vertex);
+
+ 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]; }
+
+ private:
+ core::vector<core::vector<Vertex>> hashTable;
+ const size_t hashTableSize;
+ const float cellSize;
+
+ private:
+ uint32_t hash(const Vertex& vertex) 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);
+ 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);
- CSmoothNormalGenerator() {};
- ~CSmoothNormalGenerator() {};
};

added hashing