kicad-developers team mailing list archive

[Tomasz Wlostowski <tomasz.wlostowski@xxxxxxx>]

On 18/05/18 20:49, Seth Hillbrand wrote:
> Gentle ping here.  If this doesn't interfere with your connectivity
> algorithm work Tom, I'd like to merge these as they make routing the
> board I'm working on now manageable (at least on my old machine).

Hi Seth,

I'm OK with patches 1, 2 and 5, feel free to merge them. 3 and 4 are
risky, as they reduce the number of collision checks. The issue with the
current collision check function(s) is that they are not commutative -
so intersect(itemA, itemB) may not always be equal to intersect(itemB,
itemA). That's why some of the dirty item checks were disabled, since
searching only for dirty items' collisions may not find all colliding
item pairs.

This happens for instance where zone A has only a single vertex inside
zone B. Same thing may happen when searching for via/track collisions. I
would like to definitively fix this in V6 by doing full collision search
(SHAPE_INDEX-based, as in the P&S code), but this means changing class
BOARD to use R-trees and quite a lot of refactoring of existing code.

Cheers,
Tom

PS. I have an early version of background thread connectivity branch (it
also includes other speed optimizations). Have a look if you want:

https://github.com/twlostow/kicad-dev/tree/tom-background-connectivity