I am creating an "STL to OBJ" format converter. The program contains a header file that reads the data from an STL file. and the main program takes that data and writes it to a new OBJ file. everything works great but with large files the program takes so long. I know exactly which part makes the program slow and I can't find any alternative of it. It is in the part "// Create Array for the Faces" exactly in the For-Loop.
First I want to explain a bit about STL and OBJ files. In general, any 3D image in the STL format is created from a large number of triangles and each triangle has 3 vertices (each vertex has 3 points: x, y and z). But there are many repeated vertices because the triangles are connected to each other. But in the OBJ format, 2 parts are responsible for it: one is "List of Vertices" and here vertices are sorted one after another without repetition. the second part is "List of Faces" and it is the Numbers of Index of the vertices.
this is my main code:
#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(AllteVertex.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;
}
Your current code first maps all vertices in the STL to the OBJ string format of the vertex index they reference, then uses std::unique to reduce this list, then uses an O(n) lookup on each vertex to find the original index. This is O(n*m) and is very expensive if both n and m are large.
Instead, you can do the following:
tris, and for each referenced vertex idx use a std::map<std::tuple<float, float, float>, unsigned int> to deduplicate them.
obj_coords and overwrite tris[idx] with its new index.tris[idx] with the existing index.obj_coords as-is.coordsSo, in summary:
using Coord = std::tuple<float, float, float>;
std::map<Coord, int> coordToIndex;
std::vector<Coord> obj_coords;
for (auto &idx : tris) {
const Coord c = { coords[3*idx+0], coords[3*idx+1], coords[3*idx+2] };
if (auto it = coordToIndex.find(c); it != coordToIndex.end()) {
// We saw this vertex before
idx = it->second;
} else {
// New vertex.
obj_coords.push_back(c);
idx = obj_coords.size()-1;
coordToIndex[c] = idx; // Also create an entry in coordToIndex
}
}
Then, generating vertexes is simple: (not sure why you swapped z and x though)
for (const auto& coord : obj_coords) {
fileOBJ << "v " << std::get<2>(coord) << " " << std::get<1>(coord) << " " << std::get<0>(coord) << "\n";
}
And finally, the faces:
for (int tri = 0; tri < tris.size(); tri += 3) {
fileOBJ << "f " << tris[tri+0] << " " << tris[tri+1] << " " << tris[tri+2] << "\n"
}
You may have noticed I use "\n" instead of std::endl. This is because std::endl implies std::flush, which tries to ensure that data is written to disk. Calling this is as often as you will is wasteful.
Instead, you can just flush once manually, or trust that the destructor will do it for you:
fileOBJ << std::flush;