基于UG的三维电气自动布线技术研究
对三维电气布线的方法和技术进行了深入的研究。针对传统布线过程存在的预处理成本高、操作繁琐、干涉检测维护难等问题，通过综合“迷宫法”、“线搜索法”等搜索算法和路径干涉理论，提出了“按面自动布线”和“贴壁干涉自动调整”的方法。以UG为开发平台，实现了包括三维布线路径自动生成和路径干涉检查及自动调整在内的三维自动布线，并以UG布线实例验证了所提出的三维布线方法的有效性和实用性。
1、引言
1.1、三维布线技术
三维布线技术是指三维空间里终端器、接插件或接线柱之间线、缆的连接技术。它一般分为手工三维布线和计算机辅助三维布线。计算机辅助三维布线是通过计算机仿真的方法，完成整机的布线并形成钉板图等工程文件，以提高布线的准确性、可靠性、快速性，并利于检查与维修。
当前，三维商用CAD软件一般都提供布线模块，这些布线模块被广泛应用于航天航空和电信等电子设备设计中需要布线的场合。这些模块典型的代表是UG软件的UG/WIRING模块和Pro/E 软件的Pro/CABLING 模块。UG/ROUING 模块为电气布线设计员提供了对电气布线系统进行虚拟设计的能力，但该模块布线自动化程度低，体现在：人机交互繁琐、布线路径生成效率低、布线路径干涉检测维护困难等。Pro/CABLING模块提供了三维线扎相关的导线表等功能，使得接线图和线扎图更容易更改。但由于实际问题和操作的多样性，Pro/CABLING模块提供的自动布线实际上也是一种人工交互的半自动布线方法。
1.2、自动布线研究现状
自动布线关系到整个电路系统的性能，包括电路系统的合格率和可靠性。自1960 年Lee 提出“迷宫法”以来，许多学者对自动布线技术进行了研究。A*算法作为一种基于“迷宫法”的经典的启发式算法，在最佳航迹选择和电脑游戏的寻径计算等领域有着广泛的应用，但该方法针对二维应用，无法直接应用于三维布线。斯坦福大学的CDR实验室开发出了First-Link 布线系统，但布线对象仅限于平面物体。Sunand
、Sandukar 等开发的GAPRUS 系统，能够在存在障碍物的环境进行布线，但算法的复杂度较高。目前，实际应用中广泛采用的布线算法是“迷宫法”、“线探索法”。
“迷宫法”算法过程可以描述为波的传播过程的模拟。在一个存在障碍的湖面上，若需寻找连接A、B两点的最小路径，可以在A点投下一枚石子，然后观察所引起的水波传播情况。假定“水波”传播时能量无损失，当遇到障碍时，波产生反射，最先到达的目标点波前所经过的路径必定是一条最短距离。但利用“迷宫法”获得的最短路径可能不止一条，因而实际工程应用中需要引入人工交互来选择较优路径。目前该方法主要应用于二维PCB布线，并未在三维布线上得到广泛应用。
“线探索法”本质上是一种无网格布线算法。它按照从起点到终点逐步检查前方和两侧是否有障碍物阻碍探索线的扩展，直到到达目标节点。其探索过程主要包括前向探索、绕障探索、回溯和临界点处理。“线探索法”不用存储各网点信息，有效地节省了存储空间、提高了处理器的查询效率。“线探索法”局限性在于其时间花费高、绕障能力不强。国内外很多学者对此方法进行了改进，包括使用双向搜索法的Higtower 算法、基于最小树配置的OARSMT 算法和An-OARSMan 算法等。也有学者以此方法为基础提出无网格搜索方法并应用于二维布线。“线探索法”目前也主要应用于二维PCB布线。相对二维布线，三维布线空间自由度高、布线所针对的几何模型模型复杂，因为三维布线问题也更加复杂。实用的三维布线算法不仅应能自动生成布线路径，还应能对生成的布线路径自动调整，使布线路径满足工艺要求。本文针对某军工研究所工艺技术要求，提出以下三维自动布线方法：
(1)“按面自动布线”，即按几何结构的拓扑面自动生成布线路径。
(2)“贴壁干涉自动调整”，即按“贴壁面”自动进行干涉检查并根据干涉检查结果自动进行路径调整。“贴壁面”是指生成布线路径时作为主要参考的几何模型的拓扑面。
其中，“按面自动布线”保证了生成的布线路径从工艺角度的合理性;而“贴壁干涉自动调整”则使所布路径不会与布线对象干涉，进一步从工艺角度保证了布线路径的实用性。
总结
本文提出的三维电气自动布线方法具有以下特点：
(1)“按面自动布线”综合了“迷宫法”和“线探索法”的算法思想，首先根据三维布线模型的表面法矢通过预留适当距离的方式确定过渡点，进而自动生成布线路径。该方法简化了布线过程中的交互操作，提高了布线的效率，并保证了所生成布线路径的工艺可行性。
(2)“贴壁干涉自动调整”实现了对布线过程中线缆之间以及线缆和布线对象间的干涉信息的自动检查，并可以根据干涉量的大小自动调整发生干涉的路径，从而在“按面自动布线”基础上进一步简化了布线设计人员的人工交互操作，提高了布线的自动化程度。
将来要进行的工作包括：
(1)“按面自动布线”方法中，关于处理复杂的曲面的RCP的生成算法和路径生成方法，还有待进一步研究。此外，“按面自动布线”方法采用了预留线面距离的方式防止干涉。但是，由于布线路径半径不固定、路径空间交汇等，目前“按面自动布线”的结果仍可能存在干涉，这有待于通过适当的优化算法来解决。
(2)“贴壁干涉自动调整”在处理复杂模型的路径干涉问题时，由于布线路径多、几何模型结构复杂等原因，算法时耗高。这有待于设计高效的干涉检查算法，或是通过干涉检查前引入适当人工预处理的方法来解决。
