C++实现STL转OBJ转换器：如何提升大文件处理速度？

问题概述 #

开发STL转OBJ格式转换器时，小文件处理正常，但大文件在生成面索引的循环（标注为// Create Array for the Faces的部分）耗时极长。核心原因是：STL模型存在大量重复顶点，OBJ要求无重复顶点列表+索引化的面列表，当前代码采用嵌套遍历查找（对每个原始顶点，遍历去重后的顶点列表找匹配），时间复杂度为O(N*M)（示例中N=99030，M=16523），导致百万级别的无效比较，性能瓶颈显著。

原代码如下：

#include "Header.h"
using namespace std;
string inputFile = "Fidgit.stl";    //Import einen STL-Datei (1.6MB)

string outputFile = "Fidgit1.obj";  //Export einen OBJ-Datei (1.1MB)

int main(int argc, char** argv)
{
    auto t0 = std::chrono::system_clock::now();
    std::cout << "Lesen der STL-Datei" << std::endl;

    std::vector<float> coords, normals;
    std::vector<unsigned int> tris, solids;
    stl_reader::ReadStlFile(inputFile.c_str(), coords, normals, tris, solids);
    const size_t numTris = tris.size() / 3;
    std::cout << "  Numbers of Triangels: " << numTris << std::endl;
    auto t1 = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0);
    std::cout << "  duration: " << elapsed.count() << " ms" << std::endl;

    std::cout << "writing OBJ-File" << std::endl;

    std::ofstream fileOBJ(outputFile.c_str(), std::ios::out);

    std::cout << "  Erstelle Liste der Punkte" << std::endl;

    fileOBJ << "# Object name:" << std::endl;
    fileOBJ << outputFile << std::endl;
    fileOBJ << std::endl;
    fileOBJ << "# Begin list of vertices" << std::endl;
    vector<string> AllVertex;
    std::ifstream inFile(outputFile.c_str(), std::ios::in);
   ////////////////////////////////////////////////////////////////////////////
   // Find Vertiecs coordinates and write into OBJ file

    for (size_t itri = 0; itri < numTris; ++itri) {
        for (size_t icorner = 0; icorner < 3; ++icorner) {
            float* c = &coords[3 * tris[3 * itri + icorner]];
            std::string VerStr = "v " + to_string(c[2]) + " " + to_string(c[1]) + " " + to_string(c[0]) ;
            AllVertex.push_back(VerStr);
        }
    }

    // here is a vertices containing the vertices coordinates read from the STL file.
    // But there are many repeated vectors that we don't need in obj format,
    // so they have to be removed by next step
    vector <string> OldSTLVertex = AllVertex;

    //Copy of STL vectors before removing the repeated vertices
    // to be able to find the faces indexes
    sort(AllVertex.begin(), AllVertex.end());
    auto last = unique(AllVertex.begin(), AllVertex.end());
    AllVertex.erase(last, AllVertex.end());
    vector <string> OBJVertex = AllVertex;
    // here are the vectors without repetitions
    // ready to be able to save the vector coordinates in the created obj file:
    for (auto ind : OBJVertex)
    {
        fileOBJ << ind << endl;
    }
    fileOBJ << "# End list of vertices" << std::endl;
    fileOBJ << std::endl;

    auto t2 = std::chrono::system_clock::now();
    elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1);
    std::cout << "    duration: " << elapsed.count() << " ms" << std::endl;
    //////////////////////////////////////////////////////////////////////////////
    // Create Arry for the Faces
    std::cout << "  Create list of faces (triangles)" << std::endl;
    vector <int> OBJFaces(numTris * 3);
    fileOBJ << "# Begin list of faces" << std::endl;

    int iCounter = 0;
    int iPercent = 0;
    int vcounter = 0;

    // the point here is: which index in OBJVertiecs[] hat jeder vertiec in OldSTLVertex[]
    for (int i = 0; i < OldSTLVertex.size(); i++)   // in my example OldSTLVertex.size() have 99030 elements
    {
        bool bFound = false;
        int vertexIndex = 0;
        while (!bFound) // for (size_t vertexIndex = 0; vertexIndex < OBJVertex.size(); ++vertexIndex)
        {
            if (OldSTLVertex[i] == OBJVertex[vertexIndex])   // OBJVertex have 16523 elements
            {
                bFound = true;
                OBJFaces[vcounter] = vertexIndex;
                vcounter++;
            }
            vertexIndex++;
        }
        iCounter++;
        if (iCounter % (OldSTLVertex.size() / 100) == 0)    // every time 10% are done
        {
            iPercent = iPercent + 1;
            auto t3 = std::chrono::system_clock::now();
            elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2);
            std::cout << "    " << iPercent << "% done in " << elapsed.count() << " ms" << std::endl;
        }
    }
/////////////////////////////////////////////////////////////////////////////
// Write faces into OBJ file
    unsigned count = 0;
    for (auto ind : OBJFaces)
    {
        if (count++ % 3 == 0) fileOBJ << "f ";
        fileOBJ << ind + 1 << " ";
        if (count % 3 == 0) fileOBJ << std::endl;
    }
    fileOBJ << "# End list of faces" << std::endl;
    fileOBJ << std::endl;

    auto t4 = std::chrono::system_clock::now();
    elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t4 - t0);
    std::cout << "OBJ file written in " << elapsed.count() << " ms." << std::endl;

    return 0;
}

核心问题分析 #

1. 字符串存储顶点的弊端：将float坐标转成字符串存储，不仅增加内存开销，还可能因浮点数转字符串的精度差异（如1.0和1.0000000001）导致原本相同的顶点被误判为不同，同时字符串比较的速度远慢于数值比较。
2. 线性查找的低效：对每个原始顶点，遍历去重后的顶点列表找匹配，时间复杂度为O(N*M)，数据量越大，性能下降越明显。

优化方案 #

方案1：用哈希表建立顶点到索引的映射（推荐） #

直接用数值类型存储顶点，通过unordered_map建立顶点与索引的映射，将查找时间复杂度降至O(1)（平均情况）。

修改步骤：

1. 替换字符串存储为数值类型（如std::tuple<float, float, float>），避免精度损失和字符串比较开销。
2. 在生成去重顶点列表时，同步构建哈希映射表。
3. 生成面索引时直接查表获取顶点索引，无需遍历。

修改后的关键代码片段：

// 替换字符串存储为tuple<float, float, float>
vector<tuple<float, float, float>> AllVertex;
for (size_t itri = 0; itri < numTris; ++itri) {
    for (size_t icorner = 0; icorner < 3; ++icorner) {
        float* c = &coords[3 * tris[3 * itri + icorner]];
        AllVertex.emplace_back(c[2], c[1], c[0]); // 按OBJ的坐标顺序存储
    }
}

vector<tuple<float, float, float>> OldSTLVertex = AllVertex;

// 排序去重
sort(AllVertex.begin(), AllVertex.end());
auto last = unique(AllVertex.begin(), AllVertex.end());
AllVertex.erase(last, AllVertex.end());
vector<tuple<float, float, float>> OBJVertex = AllVertex;

// 构建顶点到索引的哈希映射
unordered_map<tuple<float, float, float>, int> vertexIndexMap;
int idx = 0;
fileOBJ << "# Begin list of vertices" << std::endl;
for (auto& v : OBJVertex) {
    vertexIndexMap[v] = idx;
    // 写入OBJ文件时转成字符串
    fileOBJ << "v " << get<0>(v) << " " << get<1>(v) << " " << get<2>(v) << endl;
    idx++;
}
fileOBJ << "# End list of vertices" << std::endl;

// 生成面索引（直接查表）
std::cout << "  Create list of faces (triangles)" << std::endl;
vector<int> OBJFaces(numTris * 3);
fileOBJ << "# Begin list of faces" << std::endl;

int iCounter = 0;
int iPercent = 0;
int vcounter = 0;

for (auto& v : OldSTLVertex) {
    OBJFaces[vcounter++] = vertexIndexMap[v];
    
    // 进度统计保留
    iCounter++;
    if (iCounter % (OldSTLVertex.size() / 100) == 0) {
        iPercent++;
        auto t3 = std::chrono::system_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2);
        std::cout << "    " << iPercent << "% done in " << elapsed.count() << " ms" << std::endl;
    }
}

方案2：利用排序后的顶点列表做二分查找 #

如果不想引入哈希表的开销，可利用OBJVertex已排序的特性，用std::lower_bound做二分查找，将时间复杂度降至O(N*logM)，比线性查找效率提升数倍。

关键修改片段：

// 生成面索引时用二分查找
for (auto& v : OldSTLVertex) {
    // 二分查找找到顶点位置
    auto it = lower_bound(OBJVertex.begin(), OBJVertex.end(), v);
    int index = it - OBJVertex.begin();
    OBJFaces[vcounter++] = index;
    
    // 进度统计保留
    iCounter++;
    if (iCounter % (OldSTLVertex.size() / 100) == 0) {
        iPercent++;
        auto t3 = std::chrono::system_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2);
        std::cout << "    " << iPercent << "% done in " << elapsed.count() << " ms" << std::endl;
    }
}

额外优化：处理浮点数精度问题 #

由于STL文件中的顶点可能因浮点精度误差导致微小差异，可自定义比较逻辑（允许一定误差范围），或把浮点数放大后转成整数存储，避免误判：

// 自定义顶点结构体，带误差容忍的比较
struct Vertex {
    float x, y, z;
    bool operator==(const Vertex& other) const {
        const float eps = 1e-6;
        return fabs(x - other.x) < eps && fabs(y - other.y) < eps && fabs(z - other.z) < eps;
    }
};

// 为结构体实现哈希函数（用于unordered_map）
namespace std {
    template<> struct hash<Vertex> {
        size_t operator()(const Vertex& v) const {
            // 简单哈希实现，可根据需求优化
            size_t h1 = hash<float>()(v.x);
            size_t h2 = hash<float>()(v.y);
            size_t h3 = hash<float>()(v.z);
            return h1 ^ (h2 << 1) ^ (h3 << 2);
        }
    };
}

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