leocad
leocad copied to clipboard
leozide
Loading pieces has exponential time increase
A "simple" ldr file like the following has already 56k vertices and takes 9.6 seconds to load on my desktop.
0 !LEOCAD SYNTH BEGIN
0 !LEOCAD SYNTH CONTROL_POINT 31 -39.5 78 0 0 -1 0 1 0 1 0 0 61.630905
0 !LEOCAD SYNTH CONTROL_POINT -31 39.5 -78 1 0 0 0 1 0 0 0 1 160.06398
1 0 -143.5 -96.5 -7 1 0 0 0 1 0 0 0 1 71923.dat
0 !LEOCAD SYNTH END
0 !LEOCAD SYNTH BEGIN
0 !LEOCAD SYNTH CONTROL_POINT 32.5 39.75 -74.25 1 0 0 0 1 0 0 0 1 143.503128
0 !LEOCAD SYNTH CONTROL_POINT -32.5 -39.75 74.25 0 0 1 0 1 0 -1 0 0 57.790966
1 0 119.5 -95.75 -10.25 1 0 0 0 1 0 0 0 1 71923.dat
0 !LEOCAD SYNTH END
The problem seems to be that the optimize step is called on each vertex insertion. See https://github.com/leozide/leocad/blob/590422a30af4923bbf591ea3b28054566f5820a8/common/lc_library.cpp#L2537 called by https://github.com/leozide/leocad/blob/590422a30af4923bbf591ea3b28054566f5820a8/common/lc_library.cpp#L2974 or https://github.com/leozide/leocad/blob/590422a30af4923bbf591ea3b28054566f5820a8/common/lc_library.cpp#L2980
Actually disabling this optimization doesn't seem to have any drawbacks and speeds up the loading significantly. Maybe we should use something like Blenders KDTree and in general remove doubles just once, see https://developer.blender.org/diffusion/B/browse/master/source/blender/bmesh/operators/bmo_removedoubles.c$635 https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/BLI_kdtree.h https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdtree.c
https://github.com/jlblancoc/nanoflann looks promising, I'll give it a try...
56k verts sounds excessive for this part but the problem could be that flexible hoses don't need to be optimized (at least outside of each subfile). Probably load the verts for 1 of the subsections and just copy into the final mesh with transforms.
Here is a patch to fix this issue:
0001-AddVertex-AddTexturedVertex-and-lcArray-performance-.patch.txt
And a test/demonstration:
AddVertex() & AddTexturedVertex() become O(log(v)) and lcArray<> adds become amortized O(log(n)). Before they were O(n); which resulted in O(n^2) overall work.
