How does PCB software determine connectivity within a split

[Peter]

I have been struggling with a bizzare problem in Protel PCB.

It refuses to accept that some pads (with reliefs to an internal
plane) are actually connected.

This illustrates the issue

http://peter-ftp.co.uk/screenshots/20190922465295908.jpg

A connects to B but does not connect to C. This is obviously nonsense!

Protel requires that for a split plane to be DRC-correct, the split
must be done by placing a POLYGON PLANE onto the plane, without a
fill, so you get just the outline track. So obviously their algorithm
is a bit "simple". Yet, no matter how many times I re-do this process
of placing that polygon, I cannot make it see C as connected to A and
B. In the end I fixed it by connecting B-C with a track... The polygon
principle definitely works in other scenarios.

It raises the specific question of how PCB software handles split
planes. How does it determine which pads (with reliefs to the plane)
are actually connected to each other, if there is a weird geometry in
the split? (the above case has no weird geometry; it is blindingly
obvious that A B and C are connected!)

One obvious way to determine topological connectivity is by dividing
the whole plane into squares and "colouring in" each square around a
particular pad, and working outwards until you reach the external
boundary, and if there is a contiguous line of coloured-in squares
between two pads, then those two pads are connected.

That will break down if the grid used for the squares is bigger than a
narrow channel in a split plane.

I don't know if there are algorithms which can determine connectivity
without doing this i.e. which will pick up a conductive channel of any
width or complexity, no matter how narrow?

 

On Mon, 23 Sep 2019 08:58:07 +0100, Peter <nospam@nospam9876.com>
wrote:

I have been struggling with a bizzare problem in Protel PCB.

It refuses to accept that some pads (with reliefs to an internal
plane) are actually connected.

This illustrates the issue

http://peter-ftp.co.uk/screenshots/20190922465295908.jpg

A connects to B but does not connect to C. This is obviously nonsense!

Protel requires that for a split plane to be DRC-correct, the split
must be done by placing a POLYGON PLANE onto the plane, without a
fill, so you get just the outline track. So obviously their algorithm
is a bit "simple". Yet, no matter how many times I re-do this process
of placing that polygon, I cannot make it see C as connected to A and
B. In the end I fixed it by connecting B-C with a track... The polygon
principle definitely works in other scenarios.

It raises the specific question of how PCB software handles split
planes. How does it determine which pads (with reliefs to the plane)
are actually connected to each other, if there is a weird geometry in
the split? (the above case has no weird geometry; it is blindingly
obvious that A B and C are connected!)

I don't use "split/mixed planes" in PADS. It has too many corner
cases. I declare all planes to be standard routing planes, but add
copper patches and pours as needed. My ground plane is just one big
copper pour on a regular routing layer.

You might check the Gerbers to see what your software actually did.

One obvious way to determine topological connectivity is by dividing
the whole plane into squares and "colouring in" each square around a
particular pad, and working outwards until you reach the external
boundary, and if there is a contiguous line of coloured-in squares
between two pads, then those two pads are connected.

That will break down if the grid used for the squares is bigger than a
narrow channel in a split plane.

I don't know if there are algorithms which can determine connectivity
without doing this i.e. which will pick up a conductive channel of any
width or complexity, no matter how narrow?

You might also try pulling the nearby pads a little distance from the
vias.

PADS always shows at least two connectivity errors. Typically one is
real, and the other is a random connection to the same net, somewhere
on the board. Basically it flags both ends of the kinda random
no-connect rubber band. That took some getting used to.

Again, check the Gerbers.

 

[Tim Williams]

No idea how Protel does it, of course. For that matter, they've done a
number of algorithmically or optimizationally bizarre things over the years.
It was until a few years ago, Altium Designer's polygon fill algorithm was
possibly the slowest on the market. The plane region calculation doesn't
seem to be much better.

Anyway, for the general task, you need to:
1. Define an outer perimeter for the region
2. Determine if a given object is within that perimeter (necessary but not
sufficient)
3. Determine if a given object has been cut away from nearby objects

Step 1 starts with the [negative] shapes which subdivide the plane. Note
that a given shape has an outer perimeter. The union of all spaces outside
those shapes gives you the active regions.

Start by assuming the board area is one region, then subtract the shapes
from it. For each subtraction, intersecting lines/curves are broken and
connected to new lines/curves. The result is a disjoint set of connected
lines/curves, one closed curve for each region.

Actually, this is done already, if you've added all the pads and thermals
and stuff to the initial data.

I suspect Altium doesn't do this, hence the weirdness with thermals. I
would argue this is a bug.

If thermals are added later, then pay attention only to graphics on the
layer; we'll add the thermals in a later step.


Probably, step 2 is not required (it's certainly not sufficient alone), but
it should greatly reduce the number of checks needed. It's straightforward
to check, given a perimeter curve:
https://en.wikipedia.org/wiki/Point_in_polygon

Step 3 is the hard one, and is where you would involve constraints like
minimum neck width. There are other well-known algorithms concerning
connectivity, expansion or contraction of curves, etc. that can be used to
test and modify these accordingly.
https://en.wikipedia.org/wiki/Straight_skeleton

In particular, you'd probably shrink all regions by (neck width)/2 and check
where new regions have been created (i.e., have come disconnected from the
whole). Then, find the location of the closest approach between those two
regions, and create a violation object there.

If thermals are added at a late stage such as this, something funny will
happen, from neck width violations (or unchecked ones!) to disconnected
copper to connectivity errors.

This is... probably not the algorithm Protel is using, as it should air on
the side of correct connectivity, and not make obvious mistakes like you
saw. (I mean, you're welcome to debug/disassemble Protel itself and figure
out what it's doing, license conditions notwithstanding (not that they would
care on such an old product?). But that's another matter unto itself...)


Note that PCBs generally use vector graphics, so the approach should be
geometrically based, not raster based. Grids /can/ be used to simplify
problems -- along the lines of what you were thinking -- but they aren't
reasonable to use for arbitrary resolution graphics. (You could however
use, say, a quadtree to subdivide the region into squares of nested sizes,
until each square contains only one edge, say. It would probably take up
more memory than a pure geometric approach, but may be easier to code, and
that may be reason enough to choose such an approach...)

Tim

--
Seven Transistor Labs, LLC
Electrical Engineering Consultation and Design
Website: https://www.seventransistorlabs.com/

"Peter" <nospam@nospam9876.com> wrote in message
news:qm9tuf$92j$1@dont-email.me...

I have been struggling with a bizzare problem in Protel PCB.

It refuses to accept that some pads (with reliefs to an internal
plane) are actually connected.

This illustrates the issue

http://peter-ftp.co.uk/screenshots/20190922465295908.jpg

A connects to B but does not connect to C. This is obviously nonsense!

Protel requires that for a split plane to be DRC-correct, the split
must be done by placing a POLYGON PLANE onto the plane, without a
fill, so you get just the outline track. So obviously their algorithm
is a bit "simple". Yet, no matter how many times I re-do this process
of placing that polygon, I cannot make it see C as connected to A and
B. In the end I fixed it by connecting B-C with a track... The polygon
principle definitely works in other scenarios.

It raises the specific question of how PCB software handles split
planes. How does it determine which pads (with reliefs to the plane)
are actually connected to each other, if there is a weird geometry in
the split? (the above case has no weird geometry; it is blindingly
obvious that A B and C are connected!)

One obvious way to determine topological connectivity is by dividing
the whole plane into squares and "colouring in" each square around a
particular pad, and working outwards until you reach the external
boundary, and if there is a contiguous line of coloured-in squares
between two pads, then those two pads are connected.

That will break down if the grid used for the squares is bigger than a
narrow channel in a split plane.

I don't know if there are algorithms which can determine connectivity
without doing this i.e. which will pick up a conductive channel of any
width or complexity, no matter how narrow?

 

[Jon Elson]

On Mon, 23 Sep 2019 08:58:07 +0100, Peter wrote:

I have been struggling with a bizzare problem in Protel PCB.

It refuses to accept that some pads (with reliefs to an internal plane)
are actually connected.

This illustrates the issue

http://peter-ftp.co.uk/screenshots/20190922465295908.jpg

A connects to B but does not connect to C. This is obviously nonsense!

Protel requires that for a split plane to be DRC-correct, the split must
be done by placing a POLYGON PLANE onto the plane, without a fill, so
you get just the outline track. So obviously their algorithm is a bit
"simple". Yet, no matter how many times I re-do this process of placing
that polygon, I cannot make it see C as connected to A and B. In the end
I fixed it by connecting B-C with a track... The polygon principle
definitely works in other scenarios.

What version of Protel are you using? I've been using Protel 99 SE with
SP6 for many years. It does split planes quite well. You don't need a
polygon plane, but the split plane borders cannot overlap, or it gives an
error. other than that, it handles split planes very well.

I'm guessing that you are NOT using Protel 99 SE.

Jon

 

[Peter]

Thank you Tim. That is a really interesting read. The references are,
too.

No idea how Protel does it, and I agree it is some kind of a bug.



"Tim Williams" <tiwill@seventransistorlabs.com> wrote

No idea how Protel does it, of course. For that matter, they've done a
number of algorithmically or optimizationally bizarre things over the years.
It was until a few years ago, Altium Designer's polygon fill algorithm was
possibly the slowest on the market. The plane region calculation doesn't
seem to be much better.

Anyway, for the general task, you need to:
1. Define an outer perimeter for the region
2. Determine if a given object is within that perimeter (necessary but not
sufficient)
3. Determine if a given object has been cut away from nearby objects

Step 1 starts with the [negative] shapes which subdivide the plane. Note
that a given shape has an outer perimeter. The union of all spaces outside
those shapes gives you the active regions.

Start by assuming the board area is one region, then subtract the shapes
from it. For each subtraction, intersecting lines/curves are broken and
connected to new lines/curves. The result is a disjoint set of connected
lines/curves, one closed curve for each region.

Actually, this is done already, if you've added all the pads and thermals
and stuff to the initial data.

I suspect Altium doesn't do this, hence the weirdness with thermals. I
would argue this is a bug.

If thermals are added later, then pay attention only to graphics on the
layer; we'll add the thermals in a later step.


Probably, step 2 is not required (it's certainly not sufficient alone), but
it should greatly reduce the number of checks needed. It's straightforward
to check, given a perimeter curve:
https://en.wikipedia.org/wiki/Point_in_polygon

Step 3 is the hard one, and is where you would involve constraints like
minimum neck width. There are other well-known algorithms concerning
connectivity, expansion or contraction of curves, etc. that can be used to
test and modify these accordingly.
https://en.wikipedia.org/wiki/Straight_skeleton

In particular, you'd probably shrink all regions by (neck width)/2 and check
where new regions have been created (i.e., have come disconnected from the
whole). Then, find the location of the closest approach between those two
regions, and create a violation object there.

If thermals are added at a late stage such as this, something funny will
happen, from neck width violations (or unchecked ones!) to disconnected
copper to connectivity errors.

This is... probably not the algorithm Protel is using, as it should air on
the side of correct connectivity, and not make obvious mistakes like you
saw. (I mean, you're welcome to debug/disassemble Protel itself and figure
out what it's doing, license conditions notwithstanding (not that they would
care on such an old product?). But that's another matter unto itself...)


Note that PCBs generally use vector graphics, so the approach should be
geometrically based, not raster based. Grids /can/ be used to simplify
problems -- along the lines of what you were thinking -- but they aren't
reasonable to use for arbitrary resolution graphics. (You could however
use, say, a quadtree to subdivide the region into squares of nested sizes,
until each square contains only one edge, say. It would probably take up
more memory than a pure geometric approach, but may be easier to code, and
that may be reason enough to choose such an approach...)

Tim

 

[Peter]

Jon Elson <elson@pico-systems.com> wrote

On Mon, 23 Sep 2019 08:58:07 +0100, Peter wrote:

I have been struggling with a bizzare problem in Protel PCB.

It refuses to accept that some pads (with reliefs to an internal plane)
are actually connected.

This illustrates the issue

http://peter-ftp.co.uk/screenshots/20190922465295908.jpg

A connects to B but does not connect to C. This is obviously nonsense!

Protel requires that for a split plane to be DRC-correct, the split must
be done by placing a POLYGON PLANE onto the plane, without a fill, so
you get just the outline track. So obviously their algorithm is a bit
"simple". Yet, no matter how many times I re-do this process of placing
that polygon, I cannot make it see C as connected to A and B. In the end
I fixed it by connecting B-C with a track... The polygon principle
definitely works in other scenarios.


What version of Protel are you using? I've been using Protel 99 SE with
SP6 for many years. It does split planes quite well. You don't need a
polygon plane, but the split plane borders cannot overlap, or it gives an
error. other than that, it handles split planes very well.

I'm guessing that you are NOT using Protel 99 SE.

Jon

I am using Protel PCB 2.8, dating from about 1995. I bought the
original program and had it upgraded up to v2.8, after which Protel
"disintegrated" and the prices went through the roof.

I "borrowed" 99SE, which opens the design well enough (no obvious
artefacts) but it generated the same DRC errors so the bug would
appear to be there also.

Interesting that you report 99SE works with SP6. I might give it
another try... 99SE seems to be very popular.

 

[Winfield Hill]

Peter wrote...

Interesting that you report 99SE works with SP6. ...

My PCB tech used 99SE, but we had already migrated
to Altium Designer.** I now use version 17, since
the newer 18 and 19 are disasters. At any rate,
the 99SE-to-Designer version rewrites incorporated
15 to 20-years of upgrades, with many improvements.

** I imported his files, to finish the editing.


--
Thanks,
- Win