I have a problem with creating a set of unique vertices containing Position Coordinate, Texture Coordinade and Normals. I decided to use std::set for this kind of problem. The problem is that it seems that it somehow does not creating the correct set of vertices. The data I loaded from .obj file 100% correct as it is renders the mesh as I expected. But new set of data is just creates a blob of triangles.
Correct result using only Positions of vertices, expected result:
And generated data:
The code routine:
struct vertex
{
glm::vec3 Position;
glm::vec2 TextureCoord;
glm::vec3 Normal;
bool operator==(const vertex& rhs) const
{
bool Res1 = this->Position == rhs.Position;
bool Res2 = this->TextureCoord == rhs.TextureCoord;
bool Res3 = this->Normal == rhs.Normal;
return Res1 && Res2 && Res3;
}
};
namespace std
{
template<>
struct hash<vertex>
{
size_t operator()(const vertex& VertData) const
{
size_t res = 0;
const_cast<hash<vertex>*>(this)->hash_combine(res, hash<glm::vec3>()(VertData.Position));
const_cast<hash<vertex>*>(this)->hash_combine(res, hash<glm::vec2>()(VertData.TextureCoord));
const_cast<hash<vertex>*>(this)->hash_combine(res, hash<glm::vec3>()(VertData.Normal));
return res;
}
private:
// NOTE: got from glm library
void hash_combine(size_t& seed, size_t hash)
{
hash = 0x9e3779b9 (seed << 6) (seed >> 2);
seed ^= hash;
}
};
}
void mesh::BuildUniqueVertices()
{
std::unordered_set<vertex> UniqueVertices;
//std::unordered_map<u32, vertex> UniqueVertices;
u32 IndexCount = CoordIndices.size();
std::vector<u32> RemapedIndices(IndexCount);
for(u32 VertexIndex = 0;
VertexIndex < IndexCount;
VertexIndex)
{
vertex Vert = {};
v3 Pos = Coords[CoordIndices[VertexIndex]];
Vert.Position = glm::vec3(Pos.x, Pos.y, Pos.z);
if(NormalIndices.size() != 0)
{
v3 Norm = Normals[NormalIndices[VertexIndex]];
Vert.Normal = glm::vec3(Norm.x, Norm.y, Norm.z);
}
if(TextCoords.size() != 0)
{
v2 TextCoord = TextCoords[TextCoordIndices[VertexIndex]];
Vert.TextureCoord = glm::vec2(TextCoord.x, TextCoord.y);
}
// NOTE: think about something faster
auto Hint = UniqueVertices.insert(Vert);
if (Hint.second)
{
RemapedIndices[VertexIndex] = VertexIndex;
}
else
{
RemapedIndices[VertexIndex] = static_cast<u32>(std::distance(UniqueVertices.begin(), UniqueVertices.find(Vert)));
}
}
VertexIndices = std::move(RemapedIndices);
Vertices.reserve(UniqueVertices.size());
for(auto it = UniqueVertices.begin();
it != UniqueVertices.end();)
{
Vertices.push_back(std::move(UniqueVertices.extract(it ).value()));
}
}
What the error could be. I am suspecting that hash function is not doing its job right and therefor I am getting really trashed results of random triangles around initial mesh bounds. Thanks.
CodePudding user response：
This construction shows that you're going down the wrong path:
RemapedIndices[VertexIndex] = static_cast<u32>(std::distance(UniqueVertices.begin(), UniqueVertices.find(Vert)));
It's clear that you want the "offset" of the vertex within the UniqueVertices but you're modifying the container in the same loop with UniqueVertices.insert(Vert);. That means that the std::distance result you calculate is potentially invalidated by the next loop. Every index except the very last one you calculate will potentially be garbage by the time you finish the outer loop.
Just use a vector<vertex> and stop trying to de-dupe vertices. If you later find you need to optimize for better performance, you're going to be better off trying to make sure that the mesh is optimized for cache locality.
If you really, really feel the need to dedupe, you need to do it in a multi-step process, something like this...
First map the original indices to some kind of unique key (NOT the full vertex... you want something that can be used as both a map key and value, so has good hashing and equality functionality, like std::string). For instance, you could take the 3 source indices and convert them to fixed length hex strings concatenated together. Just make sure the transformation is reversible. Here I've stubbed it out wit std::string to_key(uint32_t CoordIndex, uint32_t NormalIndex, uint32_t TextCoordIndex)
std::unordered_map<uint32_t, std::string> originalIndexToKey;
std::unordered_set<std::string> uniqueKeys;
uint32_t IndexCount = CoordIndices.size();
for (u32 VertexIndex = 0; VertexIndex < IndexCount; VertexIndex) {
uint32_t CoordIndex = UINT32_MAX, NormalIndex = UINT32_MAX, TextCoordIndex = UINT32_MAX;
CoordIndex = CoordIndices[VertexIndex];
if (NormalIndices.size() != 0) {
NormalIndex = NormalIndices[VertexIndex];
}
if (TextCoords.size() != 0) {
TextCoordIndex = TextCoordIndices[VertexIndex];
}
std::string key = to_key(CoordIndex, NormalIndex, TextCoordIndex);
originalIndexToKey.insert(VertexIndex, key);
uniqueKeys.insert(key);
}
Next, take all the unique keys and construct the unique vertices with them in a vector, so they have fixed positions. Here you need to get the sub-indices back from the key with a void from_key(const std::string& key, uint32_t & CoordIndex, uint32_t & NormalIndex, uint32_t & TextCoordIndex) function.
std::unordered_map<std::string, uint32_t> keyToNewIndex;
std::vector<vertex> uniqueVertices;
for (const auto& key : uniqueKeys) {
uint32_t NewIndex = uniqueVertices.size();
keyToNewIndex.insert(key, NewIndex)
// convert the key back into 3 indices
uint32_t CoordIndex, NormalIndex, TextCoordIndex;
from_key(key, CoordIndex, NormalIndex, TextCoordIndex);
vertex Vert = {};
v3 Pos = Coords[CoordIndex];
Vert.Position = glm::vec3(Pos.x, Pos.y, Pos.z);
if (NormalIndex != UINT32_MAX) {
v3 Norm = Normals[NormalIndices[VertexIndex]];
Vert.Normal = glm::vec3(Norm.x, Norm.y, Norm.z);
}
if (TextCoordIndex != UINT32_MAX) {
v2 TextCoord = TextCoords[TextCoordIndices[VertexIndex]];
Vert.TextureCoord = glm::vec2(TextCoord.x, TextCoord.y);
}
uniqueVertices.push_back(Vert);
}
Finally, you need to map from the original index out to the new index, preserving the triangle geometry.
std::vector<uint32_t> RemapedIndices;
RemapedIndices.reserve(IndexCount);
for(u32 OriginalVertexIndex = 0; OriginalVertexIndex < IndexCount; OriginalVertexIndex) {
auto key = originalIndexToKey[OriginalVertexIndex];
auto NewIndex = keyToNewIndex[key];
RemapedIndices.push_back(NewIndex );
}
CodePudding user response：
The image is not completely randomly messed up. If you combine the two images, these fit perfectly:
The only problem, a mesh means triangles. You tell Vulkan how to draw each triangle. Having a mesh composed of 8 triangles, 9 unique vertices, you pass vertices for each one of 8 triangles separately, see screenshot below:
1:[1,2,4], 2:[2,5,4], 3:[2,3,5], 4:[3,6,5], 5:[4,5,7], 6:[5,8,7], 7:[5,6,8], 8:[6,9,8] (see red numbers).
So the vertex 5 will be repeated 6 times, because there the triangles 2,3,4,5,6,7 shares the vertex 5. Same goes for normals and textures. The vast majority of vertices with all set coordinates, normals, textures, colors, will be repeated exactly 6 times. If it is double coated it will be repeated 12 times. The boundary vertices will be repeated 3 and respectively 6 times if double coated. And the edge vertices will be repeated 1/2 times, see left and right edge, and respectively 2/4 times if double coated:
If you try to remove the duplicates, you transform a mesh in a mess. And this is regardless of how well these are sorted or unsorted. The order makes no more any sense.
If you want to use unique set of coordinates, there probably exists in Vulkan some technique to add an index buffer, similar to OpenGL. So you can pass unique coordinates, but build correctly the index array. All vertices will be unique, but the indexes in index array will not.