kicad-developers team mailing list archive
Mailing list archive
Re: Re: Zone fill issue
Magnus Beischer wrote:
--- In kicad-devel@xxxxxxxxxxxxxxx, Dick Hollenbeck <dick@...> wrote:
Magnus Beischer wrote:
Yes, that would be an improvement.
The last time we talked about this, I mentioned the idea of using
polygon fills from within PCBNEW to show zones. And to postpone the
creation of the actual raster lines, (vertical and horizontal,
I guess that we have 2 separate speed problems here:
1) Generating the zone fill segments (done once for every zone)
2) Drawing the zone fill segments on screen (done all the time the
user move, zoom, redraw etc. on the screen.
Making changes that increase the drawing speed is not a good idea, but
I think a smarter sone fill algorithm could drastically speed up the
drawing on the screen. A question here for you Dick: If zone creation
time goes up by 20% and zone drawig on the screen goes down by 50%,
would you conider that to be an improvement? (if also generating
of class ZONE, a class derived from TRACK) until gerber file export
Variations on this idea could be improvements, because then the PCBNEW
use of zones would be more limited to the ZONE_CONTAINER instances.
all recognized that the visual presentation of the filled polygon used
like this in some competing software tools did not always correctly
present gaps around pads and such like the current raster lines do.
This just reinforces the need to always look at the final gerbers in
gerber viewer anyway, and this is not a new need.
Is what you are thinking similar to this general scheme? If so, I
suspect the numbers you offer of 20% and 50% are conservative, and
actual results might make folks scream for joy.
And this is not to say that only my idea could make folks scream for
joy. What do you have up your sleeve?
The 20% and 50% was just to be sure that the zone drawing speed is
much more important than the zone generation speed.
1. By comparing KiCAD and Supermax ECAD at
http://beischer.com/opencad/fillzone.htm I see that Supermax is just
using horizontal lines combined with a line follwing the border of a
zone. Just using horizontal lines will reduce the number of lines with
~50% but this method requires the patch not to distroy the smothness
of vertical zone borders. Adding the border like the patch does will
move the 50% up a bit, but I still think there will be much less lines
than in the current releas. Question: Is drawing time also dependent
on segment length?
2. I think that there is a great advantage to draw the zones
internally in KiCAD, on the screen and in the gerber files in the same
way, to have the bord review as simple as possibl. One way of keeping
this method but also increasing the speed is to:
- When drawing a border like the patch and for instance drawing the
zone with 8 mil tracks using 5 mill grid, if there are 3 tracks in
paralell, reduce the length of the segments 10 mill and replace them
by one ~24 mill segment. When using this method the number of segments
will be reduced heavily. The more simple the zone is to fill, the more
segments we can optimize. For rectagular or trapetsoid part of zones
the reduction of segments will be about 50%.
In total the 1 and 2 above will reduce the number of zone segments
down to minimum 25% + the extra zone edges. It's hard to do any real
claculations on this since the reduction is dependent on the bord. I
have just done some manual tests in KiCAD to get very rough estimates.
Note: Segment widths and zone grid has to be calculated and optimized
not to get small areas without any fill inside the zones...
Magnus and Gabriele,
These are some good ideas. Indeed, were all things equal regarding
speed, there is an advantage to using the zone segments in the zone,
rather than a polygon fill, namely DRC and visual preview of what the
gerbers will look like. It eliminates surprises which could otherwise
occur at gerber file generation time. (But these advantages cannot
overcome all speed shortcomings.)
The cost in time to experiment with these ideas that you mention is
Do you have any time to work on this? I know from a later posting that
Gabriele is offering to enhance her patch to incorporate some of your
ideas. But this is an area where successive refinement and
experimentation will pay off, and multiple eyes on the problem while it
is being solved could be useful.
Some of my ideas for you to consider:
The width of the border segment determines (or is dependent on):
1) How aggressively the zone can follow a non-straight contour.
2) How large two neighboring segments can be. See the diagram just
below line 17 here:
An algorithm can be developed which examines the gradients at each end
of each potential segment, this is a total of two gradients. Where a
gradient is the dx/dy with respect to the previous segment's endpoint
on the same end. Then maybe these two gradients can be compared to the
two gradients for the previous segment. This is like a 2nd
derivative. If the 2nd derivative is not changing, then any given edge
is straight and larger segments can be used. The more aggressively
changing 2nd derivative of the two ends dictates the segment width.
Another idea is that the segments used for the border do not all have to
be the same width.
There is a boundary case, and that is for example the segment which
comprises the corner of a rectangle. The width of that segment
determines the radius (=width/2) of the corner of the zone rectangle.
Seems like fun thing to experiment with, but I suspect it will require a
detailed understanding of the existing fill algorithm to take this into
the domain of variable width segments.
As you mentioned the elimination of vertical or horizontal segments
reduces the segments by half, then adding back in the perimeter defeats
only a portion of that reduction.
There are two potential avenues to be explored, single direction
parallel segments, and variable width segments, and the good news is
that they don't appear to be mutually exclusive.