FileOBJ export exorbitantly slow when exporting with face colors enabled
Problem
The export of small scale meshes (several ten thousands triangles) is noticably slow. Saving medium scale meshes (several hundred thousands triangles) is impossibly slow. Don't bother trying large scale meshes.
Reproduction
- Open any mesh
- Save as .obj with FileOBJ Plugin and all checkboxes enabled
- Wait forever
Dirty Workaround
Disable following export options:
- Save Face Colors
- Save Textures
- Copy Texture Files (Create Texture Folder)
Problem Analysis
The following is happening inside the export routine in two places:
#1 (closed): Writing material
Hot LoopInspect FileOBJT_impl.hh
@ Line 90:
// Time complexity of: O(#faces)
for (f_it = _mesh.faces_begin(); f_it != f_end; ++f_it){
getMaterial(/* stuff */);
}
getMaterial()
Inside Method starts at Line 137, relevant part starts at Line 194:
for (MaterialList::iterator it = materials_.begin(); it != materials_.end(); ++it) {
// jada, jada, early outs are possible
// however doesn't happen very often for .obj without materials
// example mesh of 50K triangles has +30K materials (however it is just a blank mesh, no colors, no .mtl files etc.)
}
// no early out taken
// ...
materials_.insert(/* stuff */);
// -> time complexity increases for (almost) every face, so we are in O(#faces^2)
// notice: materials_ is a map, map insertions/iterations are not super fast
return bla;
Assuming a small sized meshes (few 10K triangles), we will quickly reach the realm of several billion iterations, just gathering information. For medium sized meshes (few 100K triangles), we will just compute for hours at this point.
But wait! There is more.
#2 (closed): Write everything else
Hot LoopContinuing after gathering and writing the materials in FileOBJT_impl.hh
at Line 341:
for (f_it = _mesh.faces_begin(); f_it != _mesh.faces_end(); ++f_it) {
// ...
material = getMaterial(/* stuff */);
// ...
for(fh_it=_mesh.fh_iter(*f_it); fh_it.is_valid(); ++fh_it) {
// this will just take forever at this point
Remember what happend inside getMaterial()
before? However materials is already O(#faces)
large, it never gets cleared (can this be done without breaking everything else?). At this point things will get really slow.
Increasing number of triangles will cause super-quadratic slow-down.
Not enough insight, but possibly we want to somehow limit the #materials
for meshes that don't really have materials.