kicad-developers team mailing list archive

[jean-pierre charras <jean-pierre.charras@...>]

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.
>
> Dick

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