A GRIDLESS LINE SEARCH ROUTING ALGORITHM

In this paper, we propose an efficient and fast gridless line search routing algorithm . This algorithm can be applied to connection routing in PCBs and MCMs with various pad geometry and pad sizes, with different wire widths and variable distances between wires. The routing efficiency is guaranteed by delicately designed data structures and by the ability of searching around obstacles. The routing paths are improved by multi-phase multi-pass refinements. The algorithm is successfully applied in our versatile PCB design system MPCB with satisfactory results.