kicad-developers team mailing list archive

[jp charras <jp.charras@xxxxxxxxxx>]

Le 16/10/2013 16:32, Maciej Sumiński a écrit :
> On 10/16/2013 02:59 PM, Dick Hollenbeck wrote:
>>
>> On Oct 16, 2013 7:53 AM, "Dick Hollenbeck" <dick@xxxxxxxxxxx
>> <mailto:dick@xxxxxxxxxxx>> wrote:
>>  >
>>  > Looks promising, and super job on the presentation.
>>  >
>>  > Once you have it working, give some thought to using a special
>> purpose allocator for the elements of your container.   A memory pool
>> scheme, anchored on the container, might pay dividends if it removes the
>> size test for element allocations.  If you want the pool anchored on the
>> container, then overloading operator new is not best, but rather have a
>> container function do the allocations of its elements (from a pool it
>> owns.)
>>
>> Invariably
>> this means having an "in place" new operator for the element, not a
>> normal new operator overload.
>>
>> Such anchoring of pool in container is a separate decision from deciding
>> to use a fixed block allocator at all.  The fixed block allocator will
>> be worth it regardless of where the pool lives.  If you have to move
>> elements from one container to another, then anchoring the pool on the
>> container is not appropriate.  But you could then have a class that held
>> all your containers and a pool common to those containers.  I bring this
>> up because when instantiating hundreds of thousands of elements, memory
>> heap calls can be the bottleneck.
> 
> Thanks for the suggestion - I like the idea. I have briefly read the
> boost::pool project page and initially it seems to be an easy solution
> to the problem. Especially that nodes are very likely going to be POD
> structures with fixed size.
> I guess it is already included in C++11 as the emplace() function that
> is available for many std containers.
> 
> Regards,
> Orson

Seems there are some good ideas about ratsnest enhancements.

Strangely, I missed the fact some times the ratsnest removed was not the
shorter...

Here are some info about the current ratsnest and connectivity calculations:

- The first minimum spanning tree code to calculate the full basic
ratsnest was not very fast, and this is the reason why only the pads
were used to build the ratsnest (avoid to calculate it each time a track
was changed).

- The current minimum spanning tree code is very fast ( 1 to 2 order of
magnitude for large boards: more than 5000 pads and 30000 tracks) and
perhaps could handle the pads + tracks.

- to avoid very long calculation time to detect track to pad and track
to track connections, there are some limitations: Only track ends are
considered:
- a track is connected to an other track if the 2 ends are "near". (near
means here the distance between ends is smaller than the half track width)
- a track is connected to a pad if one end is inside the pad.

- This allows using fast binary search between tracks and pads, which
uses a list of all points candidates sorted by X coordinate value.

- But therefore some connections can be missed ( for instance a track
crossing an other track or a pad)


-currently, most of calculation time (90%) is spent in calculations
relative to find tracks and pads connections by copper zone areas.
(By the way, www.codeproject.com/Tips/84226/Is-a-Point-inside-a-Polygon
is the code used in Kicad to find if a point is inside a polygon)
I did not found yet a fast algorithm to really speed up this calculation
(because most of times a copper zone covers the full board area).

Thanks for all your great work on GAL and now the ratsnest calculations.

-- 
Jean-Pierre CHARRAS