| ID: | 6318 |
| From: | rn...@igor2.repo.hu |
| Date: | Fri, 8 Mar 2024 15:50:15 +0100 (CET) |
| Subject: | [pcb-rnd] next cycle in pcb-rnd: polybool and rubber band stretch router |
| replies: | 6319 from John Griessen <jo...@cibolo.com> |
Hi all, after the minor bugfix release of pcb-rnd next week, I will turn my attention to pcb-rnd again. There will be a long develompent cycle, focusing on the following two things: 1. polybool (polygon clipping lib) lately I've been debugging the new polybool lib a lot and it's getting relatively bug-free. After the next release I will try to make this the compile-time default poly clipping lib in pcb-rnd. Let's put this in context. If you draw a layer with a whole-board polygon (GND, VCC, things alike) and you have 100 padstacks and 350 lines drawn into it, that means pcb-rnd has to do 450 polygon operations to get to the final clipped poly shape. Then it will take a few dozen more to get it clipped and hole-free for rendering - so 500 is a good estimation. If you have two such layers (typical on a 4 layer board), that's about 1000 polygon ops to get your board displayed after load. Of course it heavily varies from board to board, some will need only a few 100 ops, Gabriel's biggest boards will need 10k. But it's in this generic ballpark of 1000ish ops. However: the problematic pattern that typically causes the old poly lib to emit invalid output happens very rarely, so I'd say there are typically only about 10 of these ops per board are risky. With this 1000ish ops per board, from which 10 are risky, I typically got an unresolvable polygon clipping bugreports about every 15..18 months. Before even considering any pcb-rnd testing for the new polygon lib, I wrote a brute force tester. It generates a lot of random potato shaped polygons and makes a lot of operations between them, forming huge, complicated patterns. A single run of the test executes about 4000 operatios. But as I am doing these with small coords, all 4000 are risky ops. By now I've ran the tester for about 1150 different random seeds, that's 4.6 million ops. At the moment I need to run it for many hours as it finds anything problematic only every 80th..100th seed. (On the fastest computer I have access to, thanks to SnakesAndStuff, running one seed takes about 4.5 minutes) In contrast, the original poly lib, that produced those few related bugreports more than a year apart, using the same tester, fails on pretty much every single seed! I wanted to compare the speed of the old lib to the new lib using this tester and I had to decrease the number of ops from 4000 to 1000, and even then I had to try 5 different seeds before I found one that the old poly lib didn't choke on. So if that kind of buggy old poly lib caused that few bugreports, I have some hope that the new lib that performs much better on the same test will be much harder to trick into doing invalid output. And the speed comparison: at the moment the new lib is about 25% slower than the original. This is the price of being more accurate and more reliable. 2. RBSR: Rubber Band Stretch Router This will be an alternative, experimental way of drawin traces. It will live in an optional plugin and will reuse some code from route-rnd. It will be a different way of how we route boards, incompatible with drawing individual copper lines. I expect it won't perform well with kitchen-etched 1..2 layer boards but with modern 2..4 layer professionally fabbed boards it may offer a much more efficient way of routing tracks. This will also be our variant of push&shove. As per the current plans, it probably won't require any data model or file format version change. Depending on how the new poly lib performs, I plan to start on this plugin in the next development cycle too. After the next sch-rnd release (in April) that features hierarchic desing, will have a less turbulent period, with mainly minor bugfix releases while I am focusing on the above pcb-rnd features. Best regards, Igor2
Reply subtree:
6318 [pcb-rnd] next cycle in pcb-rnd: polybool and rubber band stretch router from rn...@igor2.repo.hu
6319 Re: [pcb-rnd] next cycle in pcb-rnd: polybool and rubber band stretch from John Griessen <jo...@cibolo.com>