← Back to team overview

kicad-developers team mailing list archive

Re: zone fill with micro-vias

 

jean-pierre charras - INPG wrote:
Dick Hollenbeck a écrit :



To use the zone filling in connectivity calculations, only a volunteer
is needed to create 2 or 3 functions which test zone segments
connectivity.

Tim, currently, you cannot be this volunteer because you have work
about

eeschema.
Dick i believe you are not volunteer (am I right ?)
And i am busy...

But if a volunteer exists, i could help it to start the work.


Jean-Pierre,

It is good that you are communicating well. I had the impression that
you were working on the whole group of continuity testing primitives.
So we are making progress in learning that you are willing to let
someone else move into that role.


This is true.

As we discussed, currently the "end point" matching on tracks is an
inadequate test of electrical continuity. What is your starting
point? Please put a list together and summarize which functions are
the building blocks if any that you have, so that no duplication of work
takes place. I would like to look at that before I make any commitments.

Once we have those continuity testing primitives, then we can experiment
with how to employ them.

The primitives work on following objects:

tracks, pads, via, and zones. Allow me to use "zone" in an abstract
sense for a moment.

So we have to test continuity between:

track to track (present test is inadequate)
track to pad (present test is inadequate)
track to via (present test is inadequate)
track to zone (no test exists)

pad to pad (no test exists)
pad to via (no test exists, but log is same as pad to pad)
pad to zone (no test exists)

via to via (no test exists, but like pad to pad)
via to zone (no test exists, but like pad to zone)

zone to zone (test exists in polygon library, needs wrapper)

anything missed here?

I had made some remarks earlier about having a series of BOARD_ITEM
functions, such as

bool TRACK::ConnectsTo( TRACK* )
bool TRACK::ConnectsTo( PAD* )

bool ZONE::ConnectsTo( TRACK* ) (remember ZONE is abstract here!)

etc.

If we had those, we could re-arrange the current code to use them
immediately. Client code and test primitive implementation could be
done by two different people, concurrently. In fact for track to track
testing, the old endpoint tests could be used for a short term, wrapped
in the new wrapper: bool TRACK::ConnectsTo( TRACK*) . And in that
short term, the client code can be architected to sit on top of
TRACK::ConnectsTo( TRACK*) rather than

if track1.start == track2.start || track1.start == track2.end ||
track1.end == track2.start || track1.end == track2.end

This becomes:

if( track1.ConnectsTo( track2 ) )

In addition to the ConnectsTo() family of primitives, we might need a
function which returns the nearest point of a polygon:

wxPoint ZONE::GetNearestPoi nt( wxPoint fromHere )

This one would help in the ratsnest drawing and give the shortest path.


Obviously, current test need to be enhanced.
Be careful.
In these applications, time calculation is a problem.
there are 2 classes of algorithms (assuming we must test n items):
Algos which increase time as nlog(n)
Algos which increase time as n*n (compare each item which each other)

** Only nlog(n) algos are useable. **
Often they use sorted lists.
the track to pad test uses a sorted by increasing x value list of pads and a dichotomy search.
this is easy when testing only track end points
Enhanced dichotomy search using the track end points and whole pad shape is not so complex. (one can search before, and after the better pad candidate, restricted to its neighbour (from x - bigger pad size to x + bigger pad size) )
Enhanced dichotomy search using the entire track ot pad must be possible,
using 2 sorted pad list (sorted by X and sorted by Y) and using the best list for horizontal and vertical tracks. This is more tricky for other tracks (but 45 degrees (or other) tracks are less numerous, and usually short)

Track to track is more difficult.
An exhaustive test (n*n algo) could cost hours of computing time on large designs. Faster PC do not solve the problem because PC and faster and faster, but designs are more and more complex!


Your offer to give direction is being accepted by me, but before you
have a volunteer.

Thanks,

Dick



Your offer is accepted.



Are you speaking of ratsnest calculations, DRC, or both? Let's talk about a suggestion I made 5 months ago. That is to maintain a list within each item of the other items that it touches. This way the compute time is paid for when a track is moved, but not each time you want to know what it is touching. I came to the idea some months ago. I think it is a good one. Having said that, after the fact I now see it is being used elsewhere.

There is strong evidence that this is what freerouter is doing. Just select a connected track *segment*, then press 'i' for info, you see on the far right that there is a hotlink telling the number of "contacts" that any track has. This could simply be a non-memory-owning vector of BOARD_ITEM*. In such a design the speed of some of these tests becomes mostly moot, because they are only performed under one of two circumstances: when an item is moved, or when an item I am connected to is moved.

Dick








Follow ups

References