← Back to team overview

kicad-developers team mailing list archive

Re: Re: Zone fill issue

 

Magnus Beischer wrote:
--- In kicad-devel@xxxxxxxxxxxxxxx, Dick Hollenbeck <dick@...> wrote:

Magnus Beischer wrote:

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
smother edges)

Magnus



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,

instances
of class ZONE, a class derived from TRACK) until gerber file export

time.

Variations on this idea could be improvements, because then the PCBNEW use of zones would be more limited to the ZONE_CONTAINER instances.

We
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

the
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?

Dick



The 20% and 50% was just to be sure that the zone drawing speed is
much more important than the zone generation speed.
Some ideas:
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



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 reasonably low.

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:

http://mathworld.wolfram.com/Circle-CircleIntersection.html


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.


Dick








Follow ups

References