← Back to team overview

kicad-developers team mailing list archive

Re: zone fill with micro-vias


Dick Hollenbeck a écrit :
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?

Generaly speaking, what i said is always true...
But I was speaking mainly for ratsnest calculations.
DRC calculations also can take a lot of time when a general DRC is made (like before creating gerber files). But when designing a board, most of time only one item (the current track segment or edge zone) must be tested, and compared to alls items.
So the calculation time grows as n, for n items.

Let's talk about a suggestion I made 5 months ago.

I remember you mail.

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.


What you want to do look like an incremental algorithm.
(only what is changed is considered).
Such algorithms are powerfull, and give usually very good results.

This is a very interesting approach which must be tested (this is a lot of coding work).

The current code i wrote (which is fast, but uses only end point tests) cannot be enhanced to take in account crossing segments and overlapping vias and tracks. (it can be enhanced, i believe, only to take in account track segments overlapping pads) This is is because it cannot handle multiple connections (from a segment to more than 2 others segments : one for each end).

Your approach is more powerfull.


Jean-Pierre CHARRAS