pcb-rnd knowledge pool
Self intersecting polygons (polygon lib assertion)
poly_bug1 by Tibor 'Igor2' Palinkas on 2018-01-01
Tags: insight, polygon, self intersecting, intersecting, assert, bug
Abstract: Explanation for the famous 'self intesecting polygon' assert in --debug mode, and a method for debugging and fixing the offending board file.
Configure pcb-rnd with --debug, compile, open t21.lht (test case contributed by Karl Hammar), hover the cursor over connector X6, press del -> assert.
This is a relatively typical case of triggering the bug. Reading the details below will help understanding how to detect and work around the problem.
The rule of thumb: self intersecting polygons are always invalid in pcb-rnd. There's no exception, there is no "but". Doesn't matter how long it seems to work, an invalid construction is just invalid and will cause a problem sooner or later. May be an assertion, may be a wrong render. Therefore you should never keep invalid objects, but fix them as soon as you detect them.
What goes wrong
This is a typical polygon self intersection problem, this time triggered by the clearance corner-case adrC4 , the SMD cap on the bottom side has. When X6 is removed (or rather any element on the polygon moved or removed), the actual as-drawn shape of the polygon, which is called the clipped polygon, has to be recalculated because of the changes in the clearances. When doing so, the code reaches adrC4 , where the edges of the two clearance cutouts of the pads are exactly on the same line.
This is easy to detect on such a small test case. When the code generates the error message at the assert, it also creates an animator dump. This part of the log, marked with "!!!animator", can be copied to a new file, which is a valid animator script . In turn this can be displayed by animator . The above example gives the following drawing after running as animator -H -d dump < dump.nim :
We should have distinct closed loops with no lines overlap or cross (see below). The round clearance cutouts of the DIP pins merged properly with the rounded rectangle SMD pad clearances and formed a continous contour. But the two rounded rectangle SMD pad clearances have a long, horizontal edge that overlap! That causes the assert.
Why it happens on the first reclipping and not on load? Most probably this corner case also depends on what order the clearances are created (or removed). Nevertheless
Once you see the drawing, it's relatively easy to identify what goes wrong. The workaround is trivial too: either increase or decrease the clearance on the offending SMD pads so the corner case can be avoided.
The proper solution would be to fix up the polygon code. Unfortunately this more or less needs a full rewrite (for other reasons too). It is planned, but it's a real huge task, will not happen any time soon.
Do not compile pbc-rnd with --debug; the checks that figure you have an invalid polygon are enabled only with --debig. However, this will not solve the problem, only suppress the message that helps you working around it . Please remember: not having the assert doesn't make your polygon valid. It will have a good chance to break on-screen or on any export (including gerber!).
But gEDA/PCB doesn't have this problem!
Wrong, it does. You just don't configure it with the same checks enabled, in debug mode. Please reconfigure it with debug, save your bord in the old .pcb format and load it there - you will get the same assert when it needs to reclip the polygon.
The only real difference is that many more pcb-rnd users use --debug version than gEDA/PCB users do, which means many more bugs and problems are captured by the early warning system by pcb-rnd users than pcb users.
Why self-intersection is bad
The polygon code is designed so that it maintains polygons that comply with a few simple rules. This makes the code a bit more complicated on a smaller part, e.g. when new polygons are created or polygons have to be checked against these rules, but makes the vast majority of the code much simpler as they can assume well behaved polygons. This is an optimization - not inly in the code, but in the overall design, making the resulting code smaller, simpler and run faster.
Our current polygon lib applies at least the following assumptions:
- polygon contours are closed loops with no self-intersection
- the corners of the loop are sorted in a specific direction
- polygon holes do not touch other holes or the contour
More on the polygons
The polygon lib problem is a long standing one, there will be a longer article written about the background of why it's so hard to solve it.