kicad-developers team mailing list archive

Thread
Date
3D viewer is unusably slow (> 30 minutes) to open this board

To: kicad-developers@xxxxxxxxxxxxxxxxxxx
From: Kristian Nielsen <knielsen@xxxxxxxxxxxxxxx>
Date: Fri, 14 Aug 2015 23:27:46 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4 (gnu/linux)
I discovered that for one of my boards, the 3d viewer has become basically
unusably slow:

  https://github.com/knielsen/pcb_pov3d

I reproduced this on bzr revision 6091 as follows:

  git clone git@xxxxxxxxxx:knielsen/pcb_pov3d.git
  cd pcb_pov3d/
  pcbnew pcb_pov3d.kicad_pcb

Choose "View" -> "3D Viewer". This makes KiCAD hang for more than 30 minutes
for me (window completely unresponsive) before the 3D view pops up and
things start working again. This used to take only around 2-3 seconds.

This makes the viewer mostly unusable for this board. The board is of medium
complexity, I wonder if the problem will also show on other boards.

I tracked down the two commits that caused this performance regression:

1. http://bazaar.launchpad.net/~kicad-product-committers/kicad/product/revision/5889

-----------------------------------------------------------------------
Bzr revision 5889
commit 24170f558816f9661e9e198ecdc40f84772f583b
Author: Tomasz Włostowski <tomasz.wlostowski@xxxxxxx>
Date:   Mon Jul 6 15:15:48 2015 +0200

    Fixes to SHAPE_POLY_SET slitting/fracturing algo, some speed optimization.
-----------------------------------------------------------------------

Before this commit, the viewer comes up in seconds. After this commit, it
takes more than one minute.

2. http://bazaar.launchpad.net/~kicad-product-committers/kicad/product/revision/5999

-----------------------------------------------------------------------
Bzr revision 5999
commit 63b35f40a7210a8240a609888ac7e28606c44172
Author: Tomasz Wlostowski <tomasz.wlostowski@xxxxxxx>
Date:   Mon Jul 27 21:45:57 2015 +0200

    Removed all dependencies on boost::polygon except for bitmap2component. Replaced almost all instances of CPOLYGONS_LIST with SHAPE_POLY_SET.
-----------------------------------------------------------------------

With this commit, the time to open the 3D viewer for this board goes up to
more than 30 minutes.

The code seems to spend most of its time in this stack trace (abbreviated;
full trace at the end of the mail):

  Thread 1 (Thread 0x7fe966833a80 (LWP 16451)):
  #0  0x00007fe9521ed483 in ClipperLib::PointInPolygon(ClipperLib::IntPoint const&, ClipperLib::OutPt*) () from /kvm/kicad/bin/_pcbnew.kiface
  #1  0x00007fe9521ed5f5 in ClipperLib::Poly2ContainsPoly1(ClipperLib::OutPt*, ClipperLib::OutPt*) () from /kvm/kicad/bin/_pcbnew.kiface
  #2  0x00007fe9521f475e in ClipperLib::Clipper::JoinCommonEdges() () from /kvm/kicad/bin/_pcbnew.kiface
  #3  0x00007fe9521f92ea in ClipperLib::Clipper::ExecuteInternal() () from /kvm/kicad/bin/_pcbnew.kiface
  #4  0x00007fe9521f31ce in ClipperLib::Clipper::Execute(ClipperLib::ClipType, ClipperLib::PolyTree&, ClipperLib::PolyFillType, ClipperLib::PolyFillType) [clone .part.287] () from /kvm/kicad/bin/_pcbnew.kiface
  #5  0x00007fe9521a3649 in SHAPE_POLY_SET::booleanOp(ClipperLib::ClipType, SHAPE_POLY_SET const&) () from /kvm/kicad/bin/_pcbnew.kiface
  #6  0x00007fe951ed68ec in EDA_3D_CANVAS::buildBoard3DView(unsigned int, unsigned int, REPORTER*, REPORTER*) () from /kvm/kicad/bin/_pcbnew.kiface
  #7  0x00007fe951ed3ba6 in EDA_3D_CANVAS::CreateDrawGL_List(REPORTER*, REPORTER*) () from /kvm/kicad/bin/_pcbnew.kiface
  #8  0x00007fe951ed4823 in EDA_3D_CANVAS::Redraw() () from /kvm/kicad/bin/_pcbnew.kiface

It seems this code is looping over very large vectors. Eg. I saw
m_Joins.size()==14207 in the outer loop of Clipper::JoinCommonEdges() and
m_PolyOuts.size()==9756 in the inner loop (and then a third nested loop
within that in Poly2ContainsPoly1()). I wonder if something in my board
causes excessive long lists to be generated? Or if it is hitting some case
that causes an O(n**3) complexity from three nested loops?

I can take a closer look at the code or run some profiling, but I wanted to
provide this info now, in case someone who knows the code has some idea. I
saw there was already some discussion around these commits and elimiation of
boost::polygon. Hopefully some way can be found to improve the performance
of the new code to something a bit closer to what it was before.

I suppose if KiCAD can get stuck for many minutes opening the 3D viewer,
most users would think it has gotten completely stuck (I know I did, at
first), which is not very good, obviously.

Hope this helps,

 - Kristian.


Full GDB stack trace of where the code seemed to be spending its time, for
completeness:

Thread 1 (Thread 0x7fe966833a80 (LWP 16451)):
#0  0x00007fe9521ed483 in ClipperLib::PointInPolygon(ClipperLib::IntPoint const&, ClipperLib::OutPt*) () from /kvm/kicad/bin/_pcbnew.kiface
#1  0x00007fe9521ed5f5 in ClipperLib::Poly2ContainsPoly1(ClipperLib::OutPt*, ClipperLib::OutPt*) () from /kvm/kicad/bin/_pcbnew.kiface
#2  0x00007fe9521f475e in ClipperLib::Clipper::JoinCommonEdges() () from /kvm/kicad/bin/_pcbnew.kiface
#3  0x00007fe9521f92ea in ClipperLib::Clipper::ExecuteInternal() () from /kvm/kicad/bin/_pcbnew.kiface
#4  0x00007fe9521f31ce in ClipperLib::Clipper::Execute(ClipperLib::ClipType, ClipperLib::PolyTree&, ClipperLib::PolyFillType, ClipperLib::PolyFillType) [clone .part.287] () from /kvm/kicad/bin/_pcbnew.kiface
#5  0x00007fe9521a3649 in SHAPE_POLY_SET::booleanOp(ClipperLib::ClipType, SHAPE_POLY_SET const&) () from /kvm/kicad/bin/_pcbnew.kiface
#6  0x00007fe951ed68ec in EDA_3D_CANVAS::buildBoard3DView(unsigned int, unsigned int, REPORTER*, REPORTER*) () from /kvm/kicad/bin/_pcbnew.kiface
#7  0x00007fe951ed3ba6 in EDA_3D_CANVAS::CreateDrawGL_List(REPORTER*, REPORTER*) () from /kvm/kicad/bin/_pcbnew.kiface
#8  0x00007fe951ed4823 in EDA_3D_CANVAS::Redraw() () from /kvm/kicad/bin/_pcbnew.kiface
#9  0x00007fe951ec9664 in EDA_3D_CANVAS::OnPaint(wxPaintEvent&) () from /kvm/kicad/bin/_pcbnew.kiface
#10 0x00007fe964af1d5e in wxAppConsoleBase::CallEventHandler(wxEvtHandler*, wxEventFunctor&, wxEvent&) const () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#11 0x00007fe964c8d4c8 in wxEvtHandler::ProcessEventIfMatchesId(wxEventTableEntryBase const&, wxEvtHandler*, wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#12 0x00007fe964c8d5cb in wxEventHashTable::HandleEvent(wxEvent&, wxEvtHandler*) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#13 0x00007fe964c8d978 in wxEvtHandler::TryHereOnly(wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#14 0x00007fe964c8da03 in wxEvtHandler::ProcessEventLocally(wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#15 0x00007fe964c8da65 in wxEvtHandler::ProcessEvent(wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#16 0x00007fe964c8d7d7 in wxEvtHandler::SafelyProcessEvent(wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#17 0x00007fe96645447f in ?? () from /usr/lib/x86_64-linux-gnu/libwx_gtk2u_gl-3.0.so.0
#18 0x00007fe9628e8245 in g_closure_invoke () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#19 0x00007fe9628f9f6c in ?? () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#20 0x00007fe962902778 in g_signal_emit_valist () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#21 0x00007fe9629029df in g_signal_emit () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#22 0x00007fe96303022e in gtk_widget_map () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#23 0x00007fe962ed0218 in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#24 0x00007fe962e96d7f in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#25 0x00007fe9628e83c2 in ?? () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#26 0x00007fe962902087 in g_signal_emit_valist () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#27 0x00007fe9629029df in g_signal_emit () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#28 0x00007fe96303022e in gtk_widget_map () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#29 0x00007fe962e6375a in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#30 0x00007fe962e96d7f in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#31 0x00007fe9628e83c2 in ?? () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#32 0x00007fe962902087 in g_signal_emit_valist () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#33 0x00007fe9629029df in g_signal_emit () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#34 0x00007fe96303022e in gtk_widget_map () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#35 0x00007fe9630406f2 in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#36 0x00007fe9628e8474 in ?? () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#37 0x00007fe962902087 in g_signal_emit_valist () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#38 0x00007fe9629029df in g_signal_emit () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#39 0x00007fe96303022e in gtk_widget_map () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#40 0x00007fe96303a6ee in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#41 0x00007fe9628e8474 in ?? () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#42 0x00007fe962902087 in g_signal_emit_valist () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#43 0x00007fe9629029df in g_signal_emit () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#44 0x00007fe96302f7c6 in gtk_widget_show () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#45 0x00007fe965464875 in wxWindow::Show(bool) () from /usr/lib/x86_64-linux-gnu/libwx_gtk2u_core-3.0.so.0
#46 0x00007fe9654529d5 in wxTopLevelWindowGTK::Show(bool) () from /usr/lib/x86_64-linux-gnu/libwx_gtk2u_core-3.0.so.0
#47 0x00007fe951ada86e in PCB_EDIT_FRAME::Show3D_Frame(wxCommandEvent&) () from /kvm/kicad/bin/_pcbnew.kiface
#48 0x00007fe964af1d5e in wxAppConsoleBase::CallEventHandler(wxEvtHandler*, wxEventFunctor&, wxEvent&) const () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#49 0x00007fe964c8d4c8 in wxEvtHandler::ProcessEventIfMatchesId(wxEventTableEntryBase const&, wxEvtHandler*, wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#50 0x00007fe964c8d5cb in wxEventHashTable::HandleEvent(wxEvent&, wxEvtHandler*) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#51 0x00007fe964c8d978 in wxEvtHandler::TryHereOnly(wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#52 0x00007fe9520fccc9 in EDA_BASE_FRAME::ProcessEvent(wxEvent&) () from /kvm/kicad/bin/_pcbnew.kiface
#53 0x00007fe964c8d783 in wxEvtHandler::DoTryChain(wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#54 0x00007fe964c8da65 in wxEvtHandler::ProcessEvent(wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#55 0x00007fe96566f608 in wxWindowBase::TryAfter(wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_gtk2u_core-3.0.so.0
#56 0x00007fe964c8d7d7 in wxEvtHandler::SafelyProcessEvent(wxEvent&) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#57 0x00007fe96560a3b1 in wxMenuBase::SendEvent(int, int) () from /usr/lib/x86_64-linux-gnu/libwx_gtk2u_core-3.0.so.0
#58 0x00007fe9654ded69 in ?? () from /usr/lib/x86_64-linux-gnu/libwx_gtk2u_core-3.0.so.0
#59 0x00007fe9628e8245 in g_closure_invoke () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#60 0x00007fe9628f9f6c in ?? () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#61 0x00007fe962902778 in g_signal_emit_valist () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#62 0x00007fe9629029df in g_signal_emit () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#63 0x00007fe963028af6 in gtk_widget_activate () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#64 0x00007fe962f2494d in gtk_menu_shell_activate_item () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#65 0x00007fe962f24ceb in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#66 0x00007fe962f12a3f in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#67 0x00007fe9628e8245 in g_closure_invoke () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#68 0x00007fe9628f9e62 in ?? () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#69 0x00007fe962902285 in g_signal_emit_valist () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#70 0x00007fe9629029df in g_signal_emit () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#71 0x00007fe963029d6c in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#72 0x00007fe962f11184 in gtk_propagate_event () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#73 0x00007fe962f1161b in gtk_main_do_event () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#74 0x00007fe962b84b5c in ?? () from /usr/lib/x86_64-linux-gnu/libgdk-x11-2.0.so.0
#75 0x00007fe961bc5c5d in g_main_context_dispatch () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#76 0x00007fe961bc5f48 in ?? () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#77 0x00007fe961bc6272 in g_main_loop_run () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#78 0x00007fe962f10597 in gtk_main () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#79 0x00007fe9654308a5 in wxGUIEventLoop::DoRun() () from /usr/lib/x86_64-linux-gnu/libwx_gtk2u_core-3.0.so.0
#80 0x00007fe964b37d50 in wxEventLoopBase::Run() () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#81 0x00007fe964af4086 in wxAppConsoleBase::MainLoop() () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#82 0x0000000000441d36 in ?? ()
#83 0x00007fe964b8ec20 in wxEntry(int&, wchar_t**) () from /usr/lib/x86_64-linux-gnu/libwx_baseu-3.0.so.0
#84 0x0000000000421a6e in ?? ()
#85 0x00007fe96344fb45 in __libc_start_main (main=0x421a40, argc=2, argv=0x7ffd814dd3f8, init=<optimized out>, fini=<optimized out>, rtld_fini=<optimized out>, stack_end=0x7ffd814dd3e8) at libc-start.c:287
#86 0x0000000000425f27 in _start ()
Follow ups

Re: 3D viewer is unusably slow (> 30 minutes) to open this board
From: easyw, 2015-08-15