18130Re: [kicad-users] Zuken threatens FreeRouting
- Jun 11, 2014To bring more clarity into the matter here is a history of my Autorouter
In 1987 I started working on Autorouters in the Munich department of the Computervision company.
They had worldwide the first Autorouter and interactive Router using a push and shove algorithm.
That Router could push just a single trace.
I rewrote the Autorouter, which was written in Pascal, completely in C++,
so that it could push very efficiently traces and also vias recursively at any recursion depth.
This Autorouter was grid based, as almost all professional Autorouters at that time and may have been the best grid based Autorouter ever.
It clearly created a better board layout than the Bartels Autorouter, which was famous at that time.
But when the gridless Autorouters Bloodhound of Racal-Redac and SPECCTRA of Cooper and Chyan appeared on the market,
grid based Autorouters were no more good enough and came out fashion.
So I had to develop a new gridless Autorouter for the Theda printed circuit design software of Computervision.
That turned out to be much more difficult than creating a grid based Autorouter.
Nevertheless I succeeded in developing such an Autorouter, which could compete with the SPECCTRA Autorouter.
The big advantage of this from me developed Theda Autorouter was, that it had full 45 degree capabilities,
whereas the 45 degree capabilities of the Redac and SPECCTRA Autorouters were quite poor.
The disadvantage the Theda Autorouter was, that it needed computers with very much RAM storage on big board designs.
In the mean time another gridless Autorouter Veribest of Intergraph appeared on the market, which also had full 45-degree capabilities
and was quite fast. In my opinion that was the best gridless Autorouter at that time.
After Computervision sold the Theda part of their company to the Nixdorf heritage around the year 2000 that company part changed its name to Incases.
When Incases had to dismiss part of the staff I changed my full time job to a part time job because I did not need that much money.
Zuken finally acquired Incases around the Millennium change, dismissed most of the Incases staff
and kept only a few people for a minimal Theda maintenance including me.
Some years earlier Zuken had acquired the Redac part of Racal, a PCB design software company based in Bristol in southwest England.
I was sent to Bristol around Easter 2000 to bring Autorouter knowledge, especially 45-degree routing knowledge to the Zuken-Redac developer team.
There I met Alan Finch in the Router team, who showed me his article
"A METHOD FOR GRIDLESS ROUTING OF PRINTED CIRCUIT BOARDS", which was published at the 1985 Design Automation Conference,
and which can be found at http://www.cs.york.ac.uk/rts/docs/DAC-1964-2006/PAPERS/1985/DAC85_509.PDF.
He claimed that this article was the basis of the gridless Autorouters of all big competitors including the SPECCTRA and the Veribest Autorouters.
Indeed the routing results of the SPECCTRA and Redac Autorouters looked very similar.
At the same time Zuken hired in Bristol a lot of new young talented mathematicians for the Autorouter team.
So when I came to Bristol I was highly enthusiastic that we together could easily create the world best gridless Autorouter for Zuken.
But the German product manager of the routing team was very conservative and allowed only to port the 45-degree capabilities
of the Theda Router into the Zuken Router.
Together with a young Zuken software developer with name Chris I had to do the port.
That porting of the 45-degree capabilities turned soon into a night mare because the code of the Redac router was far from modular and contained
many unnecessary data-structures, which caused huge maintenance problems. The biggest mess was their data structure, which maintained the
connectivity of electric objects on a routing board.
In fact this whole data-structure was not necessary at all because the electrical contacts can be calculated fast enough when needed
without storing them, as I proved easily in my FreeRouting Router.
Chris and I used about 85% of ouer working time with keeping this unnecessary data structure consistent.
This was just the worst example of the mess in the Zuken Router code.
Therefore I demanded very hard that while just maintaining the old Zuken Autorouter a complete new Autorouter should be developed from scratch.
The situation for this could hardly have been better with the combined router experience of Alan Finch and me and the freshly recruited young
mathematicians. But the German manager did not allow this.
Especially he pulled down the blinds completely when I proposed to write the new Autorouter in Java,
a save programming language not allowing pointers and many other insecure operations, which are possible in C++.
Also one of the old established Zuken Router staff members did not admit the mess of their code and blocked me completely off.
In this bad situation I decided to start writing privately a new free angle Autorouter in Java on my own.
Because I worked only part time at Zuken I had a lot of free time for this big challenge.
I read the paper of Alan Finch mentioned before and discovered, that his and my Autorouter algorithm's were quite similar.
The main difference was, that Alan created the main Autorouter data base on the fly when searching a single connection,
whereas I retained and maintained this data base through the whole Autorouting process.
That was the reason why the Theda Autorouter needed so much more RAM memory on big board designs.
But the advantage of my algorithm was, that it worked for any convex polygons,
whereas the algorithm of Alan Finch worked only for orthogonal rectangles.
Therefore Alan Finch's algorithm was suitable only for routing 90 degree traces.
But my algorithm could route also 45 degree traces and even free angle traces.
So I decided to combine the advantages of both algorithms in my new Autorouter.
At the same time the porting of the Theda 45 degree Router into the Zuken Router got more and more difficult.
Just Porting the interactive 45-degree Router took us more than a year.
Porting the 45-degree Autorouter capabilities was completely out of question.
More and more people of the Router staff recognized the bad situation and left the company.
The first to leave where the technical leader of the Router team and my workmate Chris.
When the port of the interactive 45 router was finished I asked again that Zuken should start developing a new Autorouter,
now based on the Java code, which I had written at home in my free time.
When that was again denied, I demanded in this hopeless situation to return to the Munich Zuken department.
where I had to maintain the old Theda software.
After a lot of time I was to my surprise allowed to bring now my private Java free angle Autorouter project into the Zuken company,
and I hoped once more for a big Autorouter future in the Zuken company.
That was shortly before I was dismissed to every bodies surprise in July 2002.
Perhaps it was naive from me to believe that the big Zuken company would allow a single isolated developer alone create a complete Router.
I believe, that Zuken might have been from the beginning only been interested in getting my Java Router code under their control,
which I had written privately at home.
In the mean time Allen Finch had retired early, and most of the new hired young mathematicians in Bristol had left the company.
Because I was at that time over 50 years old and my working experience was very specialized, it would have been very difficult
for me to get another job.
Since I had saved a lot of money, I decided to continue developing my free angle Java Autorouter now self employed.
For the next 7 years I worked almost every single day exclusively on developing and enhancing this Router.
But then I got also interested in classical music and singing, so that the time I spent working on the Router decreased.
I started to visit almost every evening the concerts of the Munich University of Music.
Around that time I had also made a modest inheritance so that I could now financially bridge the time until my retirement age
without getting any money out of the Router project.
The final blow to my Router development came in October 2010, when my Computer environment was infected by a Trojan virus,
which I was unable to remove.
No Antivirus software could detect the virus and also restoring the initial delivery state of my machine
or bringing it back to my customer did not help.
I suspected that it was a big organization of the Chinese government, who had overtaken my computer environment
and might have infected every single file.
Getting almost a nervous breakdown, I did not dare to do any Internet programming any more because I feared that I might only spread the virus.
The Router as it is can be used for free as a Java web application on my website www.freerouting.net.
It has a 45-degree mode and a free angle mode. The 45-degree Router mode is quite stable,
but the work on the free angle Autorouter I got not completed so that this part is still in a quite unstable and slow state.
A few months ago my FreeRouting Internet site, which was written in PHP3 by Chris, did not work any more
because my Internet provider stopped supporting older versions of PHP.
After having some trouble I found a makeshift to restore the web site somehow.
At the same time my Java web Router started with the message, that future versions of Java will not support it any more, because it is not signed.
Because I am not maintaining my Router any more, I decided in this situation to donate my whole Router project to the public
and to open the sources under the GNU public license.
Otherwise this valuable piece of culture might get lost forever to the public, because I am already in retirement age. That would be really a pity.
- << Previous post in topic Next post in topic >>