.obj加载器顶点去重求助：哈希函数尝试未果，求可行方案

我已经花了一周时间寻找合适的哈希函数，想在加载OBJ文件时避免重复顶点，但一直没成功。我不知道怎么遍历给定的结构体（见源码）并获取正确索引来使用unordered_map，也不确定这是不是最佳方案，任何可行的解决方法我都接受，提前感谢！

源代码 #

结构体定义 #

struct Face
{
    struct VertexConfig
    {
        int i[3];
    };

    int numConfigs = 0;
    VertexConfig configs[4];
};

MeshResource类定义 #

class MeshResource
{
public:
    vector<float> vertices;
    vector<unsigned int> indices;
    vector<float> normals;
    vector<float> textureIndex;
    std::shared_ptr<Material> material;

    GLuint slot;
    GLint components ;
    GLenum type;
    GLsizei stride , offset ;
    GLboolean normalized = GL_FALSE;
    GLuint numIndices, vao;

    MeshResource() = default;
    MeshResource(vector<float> vertices, vector<unsigned int> indices);
    // TODO: Call cleanup from destructor
    void SetupQuad();
    void Draw();
    void DrawMesh2();
    void CreateCube(float width, float height, float depth);
    void Cleanup();
    unsigned int VAO, VBO, EBO;
    void ParseIntoFloat(string line, std::vector<float>& vector);
    void ParseIntoFloat2(string line, std::vector<float>& vector);
    void LoadMeshData(const char* FileName);
    void ParseFace(string line, int pos, std::vector<Face>& faces, bool& hasNormals, bool& hasUvs);
    void Bind();

    void SetupMesh();
private:
};

OBJ解析器实现 #

LoadMeshData函数

void MeshResource::LoadMeshData(const char* FileName)
{
std::ifstream file(FileName);
std::string line;

std::vector<float> vp;
std::vector<float> vt;
std::vector<float> vn;
std::vector<Face> faces;
bool hasNormals = false;
bool hasUvs = false;

while (std::getline(file, line))
{
    //check for vertices
    if (line.substr(0, 2) == "v ") 
        ParseIntoFloat(line, vp);
    //check for texture
    else if (line.substr(0, 2) == "vt") 
        ParseIntoFloat2(line, vt);
    //check for Normals
    else if (line.substr(0, 2) == "vn") 
        ParseIntoFloat(line, vn);
    //check for faces
    else if (line.substr(0, 2) == "f ") 
        MeshResource::ParseFace(line, 2, faces, hasNormals, hasUvs);
}
std::unordered_map<int, int> map;
int currentIndex = 0;
const int step = 1 + (int)hasUvs + (int)hasNormals;
const int posLength = vp.size();
const int uvLength = vt.size();
int counter = 0;

for (int i = 0; i < faces.size(); i++ )
{
    counter++;
    for (int j = 0; j < faces[i].numConfigs; j++)
    {
        int posIndex = i+j;
        int uvIndex = i+j + 1;
        int normalIndex = i+j + (int)hasUvs + 1;
        int index = vertices.size() / 8;

        int baseIndex_Position = (faces[i].configs[j].i[0] - 1) * 3;
        vertices.push_back(vp[baseIndex_Position]);
        vertices.push_back(vp[baseIndex_Position + 1]);
        vertices.push_back(vp[baseIndex_Position + 2]);

        int baseindex_Normals = (faces[i].configs[j].i[2] -1) * 3;
        vertices.push_back(vn[baseindex_Normals]);
        vertices.push_back(vn[baseindex_Normals + 1]);
        vertices.push_back(vn[baseindex_Normals + 2]);

        int baseIndex_Texture = (faces[i].configs[j].i[1] - 1) * 2;
        vertices.push_back(vt[baseIndex_Texture]);
        vertices.push_back(vt[baseIndex_Texture + 1]);

        indices.push_back(currentIndex); 
        if (j == 2)
        {
            auto temp = indices[currentIndex];
            indices[currentIndex] = indices[currentIndex-1];
            indices[currentIndex - 1] = temp;
        }
        currentIndex++;
    }       
}
SetupMesh();
}

ParseFace函数

void MeshResource::ParseFace(string line, int pos, std::vector<Face>& faces, bool &hasNormals, bool &hasUvs)
{   
Face f;
bool eol = false;
while (!eol)
{
    bool eow = false;
    pos = line.find(" ");
    if (line[0] == 'f')
    {
        line = line.substr(line.find(" ") + 1);
        continue;
    }
    pos = line.find(" ");
    eol = pos == -1;
    if (eol && f.numConfigs>=3)
        break;
    string word = line.substr(0,pos);
    int counter = 0;
    bool isOnLast = false;
    for (size_t i = 0; i < 3; i++)
    {

        isOnLast = false;
        int slashIndex = word.find('/');
        bool notCurrent = false;
        eow = slashIndex == -1;
        string number;
        if (eow)
        {
            slashIndex = word.length() - 1;
            number = word.substr(0);
            isOnLast = true;
        }
        else
        {
            number = word.substr(0,slashIndex);
            word = word.substr(slashIndex+1);
            if (slashIndex == 0)
                notCurrent = true;
        }
        counter++;
        if (slashIndex !=-1 && !notCurrent)
        {
            if (counter == 1)
                f.configs[f.numConfigs].i[0] = std::stoi(number);
            else if (counter == 2)
            {
                f.configs[f.numConfigs].i[1] = std::stoi(number);
                hasNormals = true;
            }
            else if (counter == 3 && word.length() > 0)
            {
                f.configs[f.numConfigs].i[2] = std::stoi(number);
                hasUvs = true;
            }
        }
        if (isOnLast)
            break;
    }
    f.numConfigs++;
    pos = line.find(" ");
    line = line.substr(pos + 1);
}
faces.push_back(f);
}

解决方案：基于顶点配置组合的哈希去重 #

核心思路 #

OBJ文件中，顶点的唯一性由位置索引、UV索引、法线索引的组合决定（即VertexConfig里的i[0],i[1],i[2]）。我们可以用这个组合作为unordered_map的键，存储该组合对应的已存在顶点索引，从而避免重复添加。

具体实现步骤 #

1. 替换哈希键类型：把原有的std::unordered_map<int, int>换成std::unordered_map<std::tuple<int, int, int>, unsigned int>，用三个索引的元组作为唯一键。
2. 遍历Face时检查重复：对每个VertexConfig生成索引组合，先查询map：
   • 若存在，直接使用已有的索引加入indices
   • 若不存在，添加顶点数据到vertices，记录新索引到map后再加入indices

修改后的LoadMeshData关键代码 #

// 替换原有的map定义
std::unordered_map<std::tuple<int, int, int>, unsigned int> vertexMap;
unsigned int currentIndex = 0;

for (int i = 0; i < faces.size(); i++ )
{
    for (int j = 0; j < faces[i].numConfigs; j++)
    {
        // 获取当前顶点的原始索引组合
        int posIdx = faces[i].configs[j].i[0];
        int uvIdx = faces[i].configs[j].i[1];
        int normalIdx = faces[i].configs[j].i[2];
        
        // 生成唯一键
        auto key = std::make_tuple(posIdx, uvIdx, normalIdx);
        
        // 检查是否已存在该顶点
        if (vertexMap.find(key) != vertexMap.end())
        {
            indices.push_back(vertexMap[key]);
            continue;
        }
        
        // 添加顶点数据（保留原有的越界判断）
        int baseIndex_Position = (posIdx - 1) * 3;
        vertices.push_back(vp[baseIndex_Position]);
        vertices.push_back(vp[baseIndex_Position + 1]);
        vertices.push_back(vp[baseIndex_Position + 2]);

        if (hasNormals)
        {
            int baseindex_Normals = (normalIdx -1) * 3;
            vertices.push_back(vn[baseindex_Normals]);
            vertices.push_back(vn[baseindex_Normals + 1]);
            vertices.push_back(vn[baseindex_Normals + 2]);
        }

        if (hasUvs)
        {
            int baseIndex_Texture = (uvIdx - 1) * 2;
            vertices.push_back(vt[baseIndex_Texture]);
            vertices.push_back(vt[baseIndex_Texture + 1]);
        }
        
        // 记录新索引
        vertexMap[key] = currentIndex;
        indices.push_back(currentIndex);
        currentIndex++;

        // 保留原有的三角面顺序修正逻辑
        if (j == 2)
        {
            std::swap(indices[currentIndex-1], indices[currentIndex-2]);
        }
    }       
}

兼容旧编译器的哈希函数（可选） #

如果你的编译器不支持tuple的默认哈希，可以自定义哈希函数：

struct VertexKeyHash {
    size_t operator()(const std::tuple<int, int, int>& k) const {
        auto [p, u, n] = k;
        // 简单的哈希组合逻辑，也可以使用更严谨的hash_combine实现
        return ((p * 313 + u) * 313 + n);
    }
};

// 使用时替换map定义：
std::unordered_map<std::tuple<int, int, int>, unsigned int, VertexKeyHash> vertexMap;

内容的提问来源于stack exchange，提问作者Filiplundbeerg