Our goal is to lower the total number of segments needed to fully cover
a zone area like those:
http://www.naustech .com/kicad/ fig_0a.png
<http://www.naustech.com/kicad/fig_0a.png>
http://www.naustech .com/kicad/ fig_0b.png
<http://www.naustech.com/kicad/fig_0b.png>
http://www.naustech .com/kicad/ fig_0c.png
<http://www.naustech.com/kicad/fig_0c.png>
http://www.naustech .com/kicad/ fig_0d.png
<http://www.naustech.com/kicad/fig_0d.png>
As Dick stated, there are at least two (non mutually exclusive) methods
do achieve this: augment segment width and/or decimate segments in of a
certain direction.
I've explored the second path, choosing to decimate the vertical
segments (because i suppose that horizontal segments are drawn quickly).
I tested two approaches:
First approach:
1. decimate ALL the vertical segments which cover areas already
covered by horizontal segments.
This will obviously worsen the rendering of the vertical sides of the
filled zone and the circular regions around pads/etc too:
http://www.naustech .com/kicad/ fig_1a.png
<http://www.naustech.com/kicad/fig_1a.png>
http://www.naustech .com/kicad/ fig_1b.png
<http://www.naustech.com/kicad/fig_1b.png>
2. use my first patch (smooth algorithm) to connect together every
endpoint nearer than (gGridRoutingSize * sqrt(2)) using new segments.
This will produce
smooth vertical and oblique margins in all the regions (and smoothing in
the circular/square regions around pads/thermal/ etc).
But will also add a LOT of new short segments and introduce oblique zone
segments (which where absent before):
http://www.naustech .com/kicad/ fig_2a.png
<http://www.naustech.com/kicad/fig_2a.png>
http://www.naustech .com/kicad/ fig_2b.png
<http://www.naustech.com/kicad/fig_2b.png>
3. use an algorithm to merge together all the consecutive vertical
segments in one long segment (and all the oblique segments with the same
slope into one long segment), therefore decimating all the small
segments introduced in step 2:
http://www.naustech .com/kicad/ fig_3a.png
<http://www.naustech.com/kicad/fig_3a.png>
http://www.naustech .com/kicad/ fig_3b.png
<http://www.naustech.com/kicad/fig_3b.png>
4. with step 2, you can not eliminate 'damages' introduced by step 1
around pads/etc because the smoothing algorithm smooths by connecting
segments endpoints and so is useless situations like this:
http://www.naustech .com/kicad/ fig_4a.png
<http://www.naustech.com/kicad/fig_4a.png>
http://www.naustech .com/kicad/ fig_4b.png
<http://www.naustech.com/kicad/fig_4b.png>
So I developed an algorithm to try to resolve this issue. The results
are good:
http://www.naustech .com/kicad/ fig_5a.png
<http://www.naustech.com/kicad/fig_5a.png>
http://www.naustech .com/kicad/ fig_5b.png
<http://www.naustech.com/kicad/fig_5b.png>
but it reintroduces a lot of short segments, so even if the visual
result is good, the complexity introduced is definitely too much...
PROS:
- we get smooth sides on vertical and oblique sides of the filled zone
- the overall numbers of segments is slightly reduced for small boards
CONS:
- this approach is slooow: for every step you have nested iterations
through the zone segment list (i.e. for every segment you have to check
all the other segments against some rule), therefore the complexity is
O(n^2)
(This is not completely true for step 2, because for every segments you
need to iterate only forward in the list thanks to the way segments
endpoint are connected. So O() it's something less than O(n^2))
- the overall numbers of segments is incremented for big boards
Second approach:
1. delete all the vertical segments which do NOT cover any another
segment endpoints. In this way you do not introduce the awful
aberrations introduced by step 1 of the first approach.
So you'll eliminate all the vertical segments which start and end INSIDE
an horizontal segment and which do not pass through other segments
endpoints
2. shorten remaining vertical segments which starts INSIDE an horizontal
segment but ends on another horizontal segment endpoint, to a 2 unit
segment (Please see images, way better than my explanation)
http://www.naustech .com/kicad/ fig_11.png
<http://www.naustech.com/kicad/fig_11.png>
http://www.naustech .com/kicad/ fig_12a.png
<http://www.naustech.com/kicad/fig_12a.png>
http://www.naustech .com/kicad/ fig_12b.png
<http://www.naustech.com/kicad/fig_12b.png>
http://www.naustech .com/kicad/ fig_13.png
<http://www.naustech.com/kicad/fig_13.png>
PROS:
- the overall number of vertical segments is highly reduced and many non
deleted segments are reduced to minimum length
- relatively fast: step 1 and 2 are done in the same time (but
complexity is still O(n^2))
- the visual result of the filled zone is identical to the one obtained
with the original method (or at least it should be...)
CONS:
- slower than original fill method
- does not improve zone beautifulness :-)
I guess that with the second approach, the increased computational time
for zone filling is worth the obtained faster redrawing on the screen,
but this could not be true for big and complicated zones.
Note that we can still apply the smoothing algorithm and the merging
algorithm after the second approach only to the oblique sides of the
zones to obtain smooth lines. I'm still investigating the best way to
obtain the best from the two methods applied together.
Some results applying the above methods to two demo boards:
pic_programmer. brd, video.brd
for both fill grid 0.0050, clearance 0.0200
Note that times are highly approximative !!!
(PC is a Dell Latitude D820, Core Duo 2 T7200@2GHz, Ubuntu 8.04)
*********** pic_programmer ************ ****
Initial zone segments (added by original fill): 13536
time to fill: 2 secs
First approach:
(1) Delete vertical segments: -6925
(2) Smooth added segments: 12514
(3) Collinear optimized: vertical= -8280, oblique= -2318
(4 Heal damages) Added segments: 4127
Final zone segments: 12654 (-6%)
time to fill: 5 secs
Second approach:
(1) Deleted vertical segments: -3801
(2) Shortened vertical segments: -1884
Final zone segments*: 9735 (-28%)
time to fill: 3 secs
************ * video ************ ********
Initial zone segments (added by original fill): 41891
time to fill: 4 secs
First approach:
(1) Delete vertical segments: -23288
(2) Smooth added segments: 32983
(3) Collinear optimized vertical= -15074, oblique= -5907
(4 Heal damages) Added segments: 16469
Final zone segments: 47074 (+12%)
time to fill: 60
Second approach:
(1) Deleted vertical segments: -10839
(2) Shortened vertical segments: -5969
Final zone segments*: 31052 (-25%)
time to fill: 22 secs
*note: we do not consider shortened segments because they are still
there, but since their length has been shortened a lot, we could take
them into account too
Conclusions:
the second approach seems worth including in the zone filling source.
The others approach must be optimized and refined. I'll post to the list
only the second approach patch (because it's the only useful for now),
but everyone interested could email me directly and I'll be glad to
share all the other algorithm code.
Dick (or anyone interested), may you please try the attached patch
against your big board or send me your board for performance testing? I
think that if you send it to me without all the modules/labels/ etc, i.e.
tracks and zones only, that should be ok for you about everything
concerning privacy/security/ copyrights/ etc. Am I right?
Question:
At this time deleted zone segments are not removed from the screen until
you force a refresh (zooming in or out for example).
The relative function is commented out in source because I've not yet
figured out what to put as DrawPanel (The kicad class hierarchy is not
yet completely clear to me :-) )
Can someone please give some advice? Thanks
