slightly shifting an assembly causes excessive computation

Using SolveSpace master at 4465bc0, built with "cmake .. -DCMAKE_BUILD_TYPE=Release"

I originally observed this with a version where I had cherry-picked 9cf1a09 and a5ffd9d from https://github.com/whitequark/solvespace/issues/147 but the same problem also occurs in the "plain vanilla" version above.

It's the usual model, alt13/an-top.slvs from https://gitlab.com/anelok/mexp.git
this time at commit cb75c4a1.

I'm trying to shift an assembly a little, which affects various later groups. Unfortunately, this makes the computation time explode.

Here are the steps that lead to the problem. Cumulative CPU times (on Q6600 at 2.4 GHz) are according to "top".

solvespace an-top.slvs -> 13 s (Generate::ALL took 5322 ms, Generate::DIRTY took 5143 ms)
show occluded lines, select g019-aaa-minus, enable "show" -> 16 s
change 1.50 (lower left corner) to 1.25 -> 17 s
activate g027-an-screw-placement -> 25 s (DIRTY took 5182 ms)
activate g028-sk-boss -> 58 s (DIRTY took 33062 ms)
activate g029-boss -> ~340 s (DIRTY took 328456 ms), followed by
ALL (for bounding box) took 446 ms

But it continues calculating. Now I'm at 100 CPU-minutes and counting. Virtual memory size is increasing slowly, at about 4-5 kB/s. Physical memory size has increased by almost 50% over the time since activating g029-boss, suggesting that SolveSpace is indeed accessing the memory it has allocated.

@wpwrak

@wpwrak, Can you try with this: Evil-Spirit@a5ffd9d Evil-Spirit@9cf1a09?

@wpwrak

@wpwrak, oh, sorry, you already try it

@wpwrak

@wpwrak, you can also try to switch off edges completely. This can improve performance.

@Evil-Spirit

@Evil-Spirit this is nonsense, edges should not get generated for 285 minutes.

I stopped it at 704 CPU-minutes. Virtual size has been growing at about 12 kB/s over the last nine hours.

Now I built it with -DCMAKE_BUILD_TYPE=Debug
Set "Hide shaded view of solid model" and "Hide edges of solid model" and repeated the experiment:

g027-an-screw-placement -> 33 s (DIRTY took 7926 ms)
g028-sk-boss -> 78 s (DIRTY took 43583 ms)
activate g029-boss (or maybe it started calculating as the result of me rearranging windows) ->
at 16 CPU-minutes with no output yet

I interrupted it and got a stack trace:

Generate::DIRTY took 43583 ms
Generate::ALL (for bounding box) took 502 ms
^C
Thread 1 "solvespace" received signal SIGINT, Interrupt.
0x00005555557d5c2a in SolveSpace::SKdNode::SnapToVertex (this=0x555568745400, 
    v=..., extras=0x7fffffffdc90) at /home/3d/solvespace/src/mesh.cpp:583
583                     if((tr->a).Element(k) < v.Element(k) - KDTREE_EPS &&
(gdb) bt f
#0  0x00005555557d5c2a in SolveSpace::SKdNode::SnapToVertex (
    this=0x555568745400, v=..., extras=0x7fffffffdc90)
    at /home/3d/solvespace/src/mesh.cpp:583
        tr = 0x5555643d02a0
        k = 2
        mightHit = true
        ll = 0x5555686df910
#1  0x00005555557d5bb7 in SolveSpace::SKdNode::SnapToVertex (
    this=0x555568669e50, v=..., extras=0x7fffffffdc90)
    at /home/3d/solvespace/src/mesh.cpp:567
        vc = 5.3929016804811738
#2  0x00005555557d5b5e in SolveSpace::SKdNode::SnapToVertex (
    this=0x55556858c860, v=..., extras=0x7fffffffdc90)
    at /home/3d/solvespace/src/mesh.cpp:564
        vc = 1.0329352768770872
#3  0x00005555557d5b5e in SolveSpace::SKdNode::SnapToVertex (
    this=0x5555684908a0, v=..., extras=0x7fffffffdc90)
    at /home/3d/solvespace/src/mesh.cpp:564
        vc = 5.3929016804811738
#4  0x00005555557d5bb7 in SolveSpace::SKdNode::SnapToVertex (
    this=0x555564ae2e50, v=..., extras=0x7fffffffdc90)
    at /home/3d/solvespace/src/mesh.cpp:567
        vc = 5.3929016804811738
---Type <return> to continue, or q <return> to quit---
#5  0x00005555557d5b5e in SolveSpace::SKdNode::SnapToVertex (
    this=0x55556469ad50, v=..., extras=0x7fffffffdc90)
    at /home/3d/solvespace/src/mesh.cpp:564
        vc = 2.2500000000000009
#6  0x00005555557d6304 in SolveSpace::SKdNode::SnapToMesh (
    this=0x55556469ad50, m=0x7fffffffde70)
    at /home/3d/solvespace/src/mesh.cpp:639
        v = {x = 2.2500000000000009, y = 1.0329352768770872, 
          z = 5.3929016804811738}
        extra = {l = {elem = 0x5555687d2560, n = 1, elemsAllocated = 64}, 
          flipNormal = false, keepCoplanar = false, 
          atLeastOneDiscarded = false, isTransparent = false}
        tr = 0x555563f6bfe0
        i = 18962
        j = 1
        k = 1
#7  0x00005555557bb8f6 in SolveSpace::Group::GenerateShellAndMesh (
    this=0x55555672a9c0) at /home/3d/solvespace/src/groupmesh.cpp:351
        prevm = {l = {elem = 0x55556195d790, n = 21606, 
            elemsAllocated = 32704}, flipNormal = false, keepCoplanar = false, 
          atLeastOneDiscarded = false, isTransparent = false}
        thism = {l = {elem = 0x55556a807800, n = 120, elemsAllocated = 192}, 
          flipNormal = false, keepCoplanar = false, 
---Type <return> to continue, or q <return> to quit---
          atLeastOneDiscarded = false, isTransparent = false}
        outm = {l = {elem = 0x555563c874a0, n = 21903, 
            elemsAllocated = 32704}, flipNormal = false, keepCoplanar = true, 
          atLeastOneDiscarded = false, isTransparent = false}
        root = 0x55556469ad50
        prevBooleanFailed = false
        srcg = 0x5555566caa20
        haveSrc = true
        prevg = 0x5555566b7700
#8  0x00005555557aa942 in SolveSpace::SolveSpaceUI::GenerateAll (
    this=0x555555cbabe0 <SolveSpace::SS>, 
    type=SolveSpace::SolveSpaceUI::Generate::ALL, andFindFree=false, 
    genForBBox=false) at /home/3d/solvespace/src/generate.cpp:280
        g = 0x55555672a9c0
        first = 0
        last = 2147483647
        i = 40
        j = 723
        startMillis = 4110986232
        endMillis = 140737488346968
        prev = {elem = 0x555556f35b10, n = 741, elemsAllocated = 741}
        oldEntityCount = 9389
#9  0x000055555579e912 in SolveSpace::SolveSpaceUI::SaveToFile (
---Type <return> to continue, or q <return> to quit---
    this=0x555555cbabe0 <SolveSpace::SS>, filename="an-top.slvs~")
    at /home/3d/solvespace/src/file.cpp:264
        i = -7904
        j = 32767
        g = 0x7fffffffe100
        m = 0x7ffff47f0284 <std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::append(char const*)+20>
        s = 0x0
        srf = 0xb
        sc = 0x7fffffffe100
#10 0x000055555571eeb7 in SolveSpace::SolveSpaceUI::Autosave (
    this=0x555555cbabe0 <SolveSpace::SS>)
    at /home/3d/solvespace/src/solvespace.cpp:392
No locals.
#11 0x0000555555725798 in SolveSpace::AutosaveTimerCallback ()
    at /home/3d/solvespace/src/platform/gtkmain.cpp:202
No locals.
#12 0x0000555555734f75 in sigc::pointer_functor0<bool>::operator() (
    this=0x5555563ccab8)
    at /usr/include/sigc++-2.0/sigc++/functors/ptr_fun.h:77
No locals.
#13 0x0000555555734002 in sigc::adaptor_functor<sigc::pointer_functor0<bool> >::operator() (this=0x5555563ccab0)
---Type <return> to continue, or q <return> to quit---
    at /usr/include/sigc++-2.0/sigc++/adaptors/adaptor_trait.h:256
No locals.
#14 0x00005555557327e5 in sigc::internal::slot_call0<bool (*)(), bool>::call_it
    (rep=0x5555563cca80) at /usr/include/sigc++-2.0/sigc++/functors/slot.h:115
        typed_rep = 0x5555563cca80
#15 0x00007ffff5d5b552 in ?? ()
   from /usr/lib/x86_64-linux-gnu/libglibmm-2.4.so.1
No symbol table info available.
#16 0x00007ffff55e5103 in ?? () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
No symbol table info available.
#17 0x00007ffff55e468a in g_main_context_dispatch ()
   from /lib/x86_64-linux-gnu/libglib-2.0.so.0
No symbol table info available.
#18 0x00007ffff55e4a40 in ?? () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
No symbol table info available.
#19 0x00007ffff55e4d62 in g_main_loop_run ()
   from /lib/x86_64-linux-gnu/libglib-2.0.so.0
No symbol table info available.
#20 0x00007ffff66b6cf5 in gtk_main ()
   from /usr/lib/x86_64-linux-gnu/libgtk-3.so.0
No symbol table info available.
#21 0x00007ffff75575c1 in Gtk::Main::run(Gtk::Window&) ()
   from /usr/lib/x86_64-linux-gnu/libgtkmm-3.0.so.1
---Type <return> to continue, or q <return> to quit---
No symbol table info available.
#22 0x000055555572a282 in main (argc=2, argv=0x7fffffffe618)
    at /home/3d/solvespace/src/platform/gtkmain.cpp:1468
        main = <incomplete type>
        icon = std::shared_ptr (count 1, weak 0) 0x555555dd3340
        icon_gdk = {pCppObject_ = 0x555555dd6600}
        langNames = 0x555555de0330
(gdb) cont
Continuing.

@wpwrak

@wpwrak please never post bare backtraces like this bare in github. Either surround them with ``` ``` or add a pastebin link. When you post a comment containing #1, #2, ..., GitHub back-links these issues to the current one, which is just annoying noise.

I've edited your comment for now (which unfortunately won't fix that).

@wpwrak

@wpwrak, @whitequark may be generation takes more time than autosave period and this is stuck in autosave-regen-autosave-regen infinite loop...

@Evil-Spirit

@Evil-Spirit well 60 seconds is too much too.

@whitequark

@whitequark, to much but finite. just switching off edges can improve this

@Evil-Spirit

@Evil-Spirit doesn't matter that it's finite. it's unusable. why is it so slow exactly?

@whitequark

@whitequark, this is because of SnapToMesh. This function performs edges splitting by vetices (this is probably for correct working of MakeCertainEdgesInto and so on). So, this function somehow perform extra subdivision and probably goes into infinite loop or just getting some big number of triangles and just calculate it very long time. Each group increases the triangles count.

SnapToMesh m->l.n = 2612
SnapToMesh m->l.n = 2716
SnapToMesh m->l.n = 3026
SnapToMesh m->l.n = 4058
SnapToMesh m->l.n = 6948
SnapToMesh m->l.n = 15336 (very long time)
SnapToMesh m->l.n = 40592 (almost? infinite)
.....

nomally generation looks like:

SnapToMesh 934
SnapToMesh 944
SnapToMesh 991
SnapToMesh 1034
SnapToMesh 1075
... many groups ...
SnapToMesh 3722
SnapToMesh 3774
SnapToMesh 3855
SnapToMesh 3929

@Evil-Spirit

@Evil-Spirit thanks. What is the root cause of that?

@whitequark

@whitequark, I don't know at the moment, but I am going to export mesh for each group and look at this in some 3d editor to figure out what's went wrong way.

@whitequark

@whitequark: I see what you mean (stack trace). Sorry about that.

Meanwhile, at 247 CPU-minutes, SolveSpace still seems to be stuck at the same point.
https://0bin.net/paste/pJmXSYbruVlfKyW0#p7fmjZjIi1TIE7QEQkfM78E53g7eeVi1AWlORlvzt92
Note that it didn't print anything on the console since the first interruption.

With this model, delays after operations in 3D are now normally in the order of maybe 3-5 seconds, and I would have noticed anything greatly exceeding that. Only things like mesh creation could take much longer.

By the way, regarding Evil-Spirit@a5ffd9d and Evil-Spirit@9cf1a09, I had used them for a day or two, and they did make SolveSpace feel more responsive.

solvespace#186: Remove bad zero-area triangles.

@wpwrak

@wpwrak, @whitequark updated here.
The problem was in zero-area triangles where vertex "a" lays on the edge "bc". When two such triangles overlaps in some especial way, this causes generation of a big number of the same triangles which generate more the same... However, this is not reason for infinite loops but just for fast growing of triangles count because SKdNode::SnapToMesh is not adding new split triangle into (SMesh *m), just adding it into SKd tree itself. This causes polynomial triangles count growing for the each next group during generation. I am not sure whether it safe or not to remove such triangles, but this helps and causes no additional problems. Also this removes some problem of non-watertight mesh reporting for an-top.slvs.

@Evil-Spirit

@Evil-Spirit: you rock ! It works great, also for a similar change I made for the other battery contact. Thanks a lot !

solvespace#186: Some more attempts to avoid triangle mesh problems.

Merged in master.

What about the last commit? This also improves.

It's for a different issue. And I'm not convinced it's the correct way, yet.

Navigation Menu

Repository navigation

slightly shifting an assembly causes excessive computation #186

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

slightly shifting an assembly causes excessive computation #186

Description

Activity

Evil-Spirit commented on Feb 3, 2017

Evil-Spirit commented on Feb 3, 2017

Evil-Spirit commented on Feb 3, 2017

whitequark commented on Feb 3, 2017

wpwrak commented on Feb 3, 2017

whitequark commented on Feb 3, 2017

Evil-Spirit commented on Feb 3, 2017

whitequark commented on Feb 3, 2017

Evil-Spirit commented on Feb 3, 2017

whitequark commented on Feb 3, 2017

Evil-Spirit commented on Feb 3, 2017

whitequark commented on Feb 3, 2017

Evil-Spirit commented on Feb 3, 2017

wpwrak commented on Feb 3, 2017

Evil-Spirit commented on Feb 4, 2017

wpwrak commented on Feb 4, 2017

whitequark commented on Feb 5, 2017

Evil-Spirit commented on Feb 5, 2017

whitequark commented on Feb 5, 2017

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions