pcbnew: Zones->Fill All is became so slow for complex boards

[Eldar Khayrullin]

After some updates Zone filling for complex boards became so slow.

Application: kicad
Version: 5.0.0-rc2-dev-unknown-aeae32b~62~ubuntu17.10.1, release build
Libraries:
    wxWidgets 3.0.3
    libcurl/7.55.1 OpenSSL/1.0.2g zlib/1.2.11 libidn2/2.0.2 libpsl/0.18.0 (+libidn2/2.0.2) librtmp/2.3
Platform: Linux 4.13.0-36-generic x86_64, 64 bit, Little endian, wxGTK
Build Info:
    wxWidgets: 3.0.3 (wchar_t,wx containers,compatible with 2.8) GTK+ 2.24
    Boost: 1.62.0
    Curl: 7.55.1
    Compiler: GCC 7.2.0 with C++ ABI 1011

Build settings:
    USE_WX_GRAPHICS_CONTEXT=OFF
    USE_WX_OVERLAY=OFF
    KICAD_SCRIPTING=ON
    KICAD_SCRIPTING_MODULES=ON
    KICAD_SCRIPTING_WXPYTHON=ON
    KICAD_SCRIPTING_ACTION_MENU=ON
    BUILD_GITHUB_PLUGIN=ON
    KICAD_USE_OCE=ON
    KICAD_SPICE=ON

[Eldar Khayrullin (eldar)]

The early I refill my board in about 4 sec, now it is elapsed 10% about 2 min (I don't wait to the end).
The current process of Zone Fill: Calculating zone fills...

[Jeff Young (jeyjey)]

@Eldar, when you say "early" do you mean with earlier builds, or that during a single editing session it gets slower and slower the more times you fill?

[Eldar Khayrullin (eldar)]

@Jeff I mean earlier builds. Now I running the git bisect to detecting a buggy commit.
Soon I send the bisect log

[Eldar Khayrullin (eldar)]

$ git bisect log
git bisect start
# bad: [2da7199a3726baf35b59af4be57ba60e819f0d8e] GerbView: Fix active layer synchronization
git bisect bad 2da7199a3726baf35b59af4be57ba60e819f0d8e
# bad: [2da7199a3726baf35b59af4be57ba60e819f0d8e] GerbView: Fix active layer synchronization
git bisect bad 2da7199a3726baf35b59af4be57ba60e819f0d8e
# good: [2398d5ef8b90609068b61214e47095ae707398ff] DIALOG_EDIT_COMPONENTS_LIBID: enhancement in orphan automatic remap: add dialog to choose the right candidate when more than one is found
git bisect good 2398d5ef8b90609068b61214e47095ae707398ff
# good: [5d72aebd221d6d5108c6fdcf64d03ab19e3917e6] Fix code after renaming files
git bisect good 5d72aebd221d6d5108c6fdcf64d03ab19e3917e6
# good: [c3197a5906a799eb4e3cfacd4c4c900f36beebfe] CMakeLists: detect gtk3 using wx-config
git bisect good c3197a5906a799eb4e3cfacd4c4c900f36beebfe
# bad: [1ed7d5f8168a0b118edc78d545348333179be739] Clear out old layer data when loading on top of an existing image
git bisect bad 1ed7d5f8168a0b118edc78d545348333179be739
# good: [1013f8160885429ec68490e836de0c75439b0b80] Fix wxWidgets toolkit detection for msys2 builds
git bisect good 1013f8160885429ec68490e836de0c75439b0b80
# good: [7775f59eecab5e0ddfeed682185f88f7618dd489] Converted zone drawing tools to store points in a SHAPE_LINE_CHAIN
git bisect good 7775f59eecab5e0ddfeed682185f88f7618dd489
# good: [2e42d5c0065c2c0b4a537f48fca8746c4f61548a] Do not allow selecting tracks if they are hidden
git bisect good 2e42d5c0065c2c0b4a537f48fca8746c4f61548a
# bad: [e552c2fbff08be4f73b866ad335de53929459c5f] Remove confusing active library interactions with save.
git bisect bad e552c2fbff08be4f73b866ad335de53929459c5f
# bad: [80f36ce264a58ee176dde1ad724caa482112b41f] Scale up number of segments per polygon for larger features.
git bisect bad 80f36ce264a58ee176dde1ad724caa482112b41f
# good: [4dda8a39fe3826875550f46644bc39228cfc10f2] Add inc/dec current layer alpha to menus.
git bisect good 4dda8a39fe3826875550f46644bc39228cfc10f2
# first bad commit: [80f36ce264a58ee176dde1ad724caa482112b41f] Scale up number of segments per polygon for larger features.

[Eldar Khayrullin (eldar)]

From bisect first bad commit: [80f36ce264a58ee176dde1ad724caa482112b41f] Scale up number of segments per polygon for larger features.
For info: my board has some arcs in Edge.Cut.

[Jeff Young (jeyjey)]

Interesting.

@Tomasz, the cause of this is bumping up the number of segments in an arc. It used to always be 16 or 32 (because we mostly use them for zone corners, pad outlines, and other small features). But large arcs (drawn by the user on silk layers) plot poorly to gerber in outline mode because they still only have 16 or 32 segments.

Can we optimise zone filling to deal with a higher-segmented board outline, or do we need to figure out a way to make the patch gerber-plotting-specific?

> On 4 Mar 2018, at 15:06, Eldar Khayrullin <email address hidden> wrote:
>
>> From bisect first bad commit: [80f36ce264a58ee176dde1ad724caa482112b41f] Scale up number of segments per polygon for larger features.
> For info: my board has some arcs in Edge.Cut.
>
> --
> You received this bug notification because you are a member of KiCad Bug
> Squad, which is subscribed to KiCad.
> https://bugs.launchpad.net/bugs/1753224
>
> Title:
> pcbnew: Zones->Fill All is became so slow for complex boards
>
> Status in KiCad:
> New
>
> Bug description:
> After some updates Zone filling for complex boards became so slow.
>
> Application: kicad
> Version: 5.0.0-rc2-dev-unknown-aeae32b~62~ubuntu17.10.1, release build
> Libraries:
> wxWidgets 3.0.3
> libcurl/7.55.1 OpenSSL/1.0.2g zlib/1.2.11 libidn2/2.0.2 libpsl/0.18.0 (+libidn2/2.0.2) librtmp/2.3
> Platform: Linux 4.13.0-36-generic x86_64, 64 bit, Little endian, wxGTK
> Build Info:
> wxWidgets: 3.0.3 (wchar_t,wx containers,compatible with 2.8) GTK+ 2.24
> Boost: 1.62.0
> Curl: 7.55.1
> Compiler: GCC 7.2.0 with C++ ABI 1011
>
> Build settings:
> USE_WX_GRAPHICS_CONTEXT=OFF
> USE_WX_OVERLAY=OFF
> KICAD_SCRIPTING=ON
> KICAD_SCRIPTING_MODULES=ON
> KICAD_SCRIPTING_WXPYTHON=ON
> KICAD_SCRIPTING_ACTION_MENU=ON
> BUILD_GITHUB_PLUGIN=ON
> KICAD_USE_OCE=ON
> KICAD_SPICE=ON
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/kicad/+bug/1753224/+subscriptions

[Tomasz Wlostowski (twlostow)]

Hey,

I guess it was related to the change by Jeff (rewrite of ZONE_FILLER to use std::thread instead of OpenMP) where parallelization was list.

@Eldar: now that John brought back parallel threading, could you test the latest nightly and see if the speed is back?

@Jeff: Sure. Have a look at SHAPE_ARC::ConvertToPolyline(). It calculates the number of necessary segments based on the required accuracy (default = 1% = 0.01).

Tom

[Jeff Young (jeyjey)]

Hi Tom,

I think you perhaps misunderstood my comment.

I wasn’t asking how to bump up the number of segments; I’ve already done that in
DRAWSEGMENT::TransformShapeWithClearanceToPolygon()

Eldar’s bisect showed that the polygon change killed zone filling performance, not the parallelism issue.

(I did re-instate pooled-thread zone-filling, but my guess is that Eldar is going to find that it doesn’t help this case.)

Is there something order-n-squared in the zone filling for the number of segments in a polygon? It sounds like it’s gone from ~4 seconds to ~1000 seconds.

Hmm… it just occurs to me that the new segment-calculating algorithm assumes an arc with a substantial sweep. (It bases the number of segments on the arc radius.) A very flat (large radius) but short arc (small sweep) would end up with a whole lot of segments.

Eldar, what’s the radius on your board edge?

Cheers,
Jeff.

> On 5 Mar 2018, at 10:15, Tomasz Wlostowski <email address hidden> wrote:
>
> Hey,
>
> I guess it was related to the change by Jeff (rewrite of ZONE_FILLER to
> use std::thread instead of OpenMP) where parallelization was list.
>
> @Eldar: now that John brought back parallel threading, could you test
> the latest nightly and see if the speed is back?
>
> @Jeff: Sure. Have a look at SHAPE_ARC::ConvertToPolyline(). It
> calculates the number of necessary segments based on the required
> accuracy (default = 1% = 0.01).
>
> Tom
>
> --
> You received this bug notification because you are a member of KiCad Bug
> Squad, which is subscribed to KiCad.
> https://bugs.launchpad.net/bugs/1753224
>
> Title:
> pcbnew: Zones->Fill All is became so slow for complex boards
>
> Status in KiCad:
> New
>
> Bug description:
> After some updates Zone filling for complex boards became so slow.
>
> Application: kicad
> Version: 5.0.0-rc2-dev-unknown-aeae32b~62~ubuntu17.10.1, release build
> Libraries:
> wxWidgets 3.0.3
> libcurl/7.55.1 OpenSSL/1.0.2g zlib/1.2.11 libidn2/2.0.2 libpsl/0.18.0 (+libidn2/2.0.2) librtmp/2.3
> Platform: Linux 4.13.0-36-generic x86_64, 64 bit, Little endian, wxGTK
> Build Info:
> wxWidgets: 3.0.3 (wchar_t,wx containers,compatible with 2.8) GTK+ 2.24
> Boost: 1.62.0
> Curl: 7.55.1
> Compiler: GCC 7.2.0 with C++ ABI 1011
>
> Build settings:
> USE_WX_GRAPHICS_CONTEXT=OFF
> USE_WX_OVERLAY=OFF
> KICAD_SCRIPTING=ON
> KICAD_SCRIPTING_MODULES=ON
> KICAD_SCRIPTING_WXPYTHON=ON
> KICAD_SCRIPTING_ACTION_MENU=ON
> BUILD_GITHUB_PLUGIN=ON
> KICAD_USE_OCE=ON
> KICAD_SPICE=ON
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/kicad/+bug/1753224/+subscriptions

[Tomasz Wlostowski (twlostow)]

Eldar, can you send us the PCB that is very slow to fill?

Thanks
Tom

[Jeff Young (jeyjey)]

Disregard the earlier short-flat-arc comment. The calculated
number-of-segments is for a full circle, so it's divided by the
swept angle.

[Eldar Khayrullin (eldar)]

@Tomasz, I can't to send the original board. I only can send this one (I deleted footprints, tracks, vias and etc). The bug is reproduced yet.

[KiCad Janitor (kicad-janitor)]

Fixed in revision a164f7e2da0493a5503c35e38ebb4eadb877e57f
https://git.launchpad.net/kicad/patch/?id=a164f7e2da0493a5503c35e38ebb4eadb877e57f

[Jeff Young (jeyjey)]

@Tomasz, that equation is constant for r (they drop out of the numerator & denominator). It seems to be OK for larger arcs (78 segments in hi-res, 45 in low), but probably returns way more than necessary for smaller ones.

Is the 1% / 0.33% error based on circle area? Seems like the error needs to be based on mils or something not relative to the circle size.

[Tomasz Wlostowski (twlostow)]

@Jeff: True, I didn't notice that - for percentage accuracy the number of segments is independent from the radius. IMHO the right way to fix this is to define absolute (in mils) and relative (percentage) tolerances. This means changing the file format and the zone properties dialog - and I guess it's too late for that to be in V5.

@Wayne, any comments on that?

[jean-pierre charras (jp-charras)]

This issue also exists in SHAPE_ARC::ConvertToPolyline( double aAccuracy )

I also tested in DRAWSEGMENT::TransformShapeWithClearanceToPolygon a slightly different formula to calculate segments counts using an absolute error.

Using 0.05 mm for absolute max errors gives good results, without changing the file format.

I can commit this minor change.

[Jeff Young (jeyjey)]

I agree that we shouldn't change the file format.

But we've got the current 16/32 to go off. Since they were meant for features in the small-number-of-mm range, we can calculate an absolute error from 16 and 32 @ 1mm R, and then use that absolute error to calculate the number of segments for other R's.

I get absolute errors of 0.02mm and 0.005mm.

Our equation would then be:

count = pi / acos( ( r - abs_error ) / r )

Doing a sanity check, for the tighter tolerance (nominal 32 segments) I get:
0.5mm circle: 22 segments
5.0mm circle: 70 segments
50mm circle: 222 segments

all of which seem reasonable.

[Jeff Young (jeyjey)]

I see I cross-posted with JP. Is your formula similar?

[Jeff Young (jeyjey)]

(Note that abs_error would need to be 0.02 * IU_PER_MM or 0.005 * IU_PER_MM.)

[Wayne Stambaugh (stambaughw)]

If we can fix this without changing the file format for v5, that would
be my preference.

On 3/7/2018 5:57 AM, jean-pierre charras wrote:
> This issue also exists in SHAPE_ARC::ConvertToPolyline( double aAccuracy
> )
>
> I also tested in DRAWSEGMENT::TransformShapeWithClearanceToPolygon a
> slightly different formula to calculate segments counts using an
> absolute error.
>
> Using 0.05 mm for absolute max errors gives good results, without
> changing the file format.
>
> I can commit this minor change.
>

[jean-pierre charras (jp-charras)]

@Jeff,
Yes, of course.

[Tomasz Wlostowski (twlostow)]

On 07/03/18 13:49, Wayne Stambaugh wrote:
> If we can fix this without changing the file format for v5, that would
> be my preference.
>
> On 3/7/2018 5:57 AM, jean-pierre charras wrote:
>> This issue also exists in SHAPE_ARC::ConvertToPolyline( double aAccuracy
>> )
>>
>> I also tested in DRAWSEGMENT::TransformShapeWithClearanceToPolygon a
>> slightly different formula to calculate segments counts using an
>> absolute error.
>>
>> Using 0.05 mm for absolute max errors gives good results, without
>> changing the file format.
>>
>> I can commit this minor change.
>>
Please go for it, JP!

Thanks,
Tom
>

[jean-pierre charras (jp-charras)]

OK.
I committed my fix. The max error is fixed to 0.05 mm.
It should be suitable in most of cases.