對三維電氣布線的方法和技術進行了深入的研究。針對傳統(tǒng)布線過程存在的預處理成本高、操作繁瑣、干涉檢測維護難等問題，通過綜合“迷宮法”、“線搜索法”等搜索算法和路徑干涉理論，提出了“按面自動布線”和“貼壁干涉自動調整”的方法。以UG為開發(fā)平臺，實現(xiàn)了包括三維布線路徑自動生成和路徑干涉檢查及自動調整在內的三維自動布線，并以UG布線實例驗證了所提出的三維布線方法的有效性和實用性。

　　1、引言

　　1.1、三維布線技術

　　三維布線技術是指三維空間里終端器、接插件或接線柱之間線、纜的連接技術。它一般分為手工三維布線和計算機輔助三維布線。計算機輔助三維布線是通過計算機仿真的方法，完成整機的布線并形成釘板圖等工程文件，以提高布線的準確性、可靠性、快速性，并利于檢查與維修。

　　當前，三維商用CAD軟件一般都提供布線模塊，這些布線模塊被廣泛應用于航天航空和電信等電子設備設計中需要布線的場合。這些模塊典型的代表是UG軟件的UG/WIRING模塊和Pro/E 軟件的Pro/CABLING 模塊。UG/ROUING 模塊為電氣布線設計員提供了對電氣布線系統(tǒng)進行虛擬設計的能力，但該模塊布線自動化程度低，體現(xiàn)在：人機交互繁瑣、布線路徑生成效率低、布線路徑干涉檢測維護困難等。Pro/CABLING模塊提供了三維線扎相關的導線表等功能，使得接線圖和線扎圖更容易更改。但由于實際問題和操作的多樣性，Pro/CABLING模塊提供的自動布線實際上也是一種人工交互的半自動布線方法。

　　1.2、自動布線研究現(xiàn)狀

　　自動布線關系到整個電路系統(tǒng)的性能，包括電路系統(tǒng)的合格率和可靠性。自1960 年Lee 提出“迷宮法”以來，許多學者對自動布線技術進行了研究。A*算法作為一種基于“迷宮法”的經典的啟發(fā)式算法，在最佳航跡選擇和電腦游戲的尋徑計算等領域有著廣泛的應用，但該方法針對二維應用，無法直接應用于三維布線。斯坦福大學的CDR實驗室開發(fā)出了First-Link 布線系統(tǒng)，但布線對象僅限于平面物體。Sunand

　　、Sandukar 等開發(fā)的GAPRUS 系統(tǒng)，能夠在存在障礙物的環(huán)境進行布線，但算法的復雜度較高。目前，實際應用中廣泛采用的布線算法是“迷宮法”、“線探索法”。

　　“迷宮法”算法過程可以描述為波的傳播過程的模擬。在一個存在障礙的湖面上，若需尋找連接A、B兩點的最小路徑，可以在A點投下一枚石子，然后觀察所引起的水波傳播情況。假定“水波”傳播時能量無損失，當遇到障礙時，波產生反射，最先到達的目標點波前所經過的路徑必定是一條最短距離。但利用“迷宮法”獲得的最短路徑可能不止一條，因而實際工程應用中需要引入人工交互來選擇較優(yōu)路徑。目前該方法主要應用于二維PCB布線，并未在三維布線上得到廣泛應用。

　　“線探索法”本質上是一種無網格布線算法。它按照從起點到終點逐步檢查前方和兩側是否有障礙物阻礙探索線的擴展，直到到達目標節(jié)點。其探索過程主要包括前向探索、繞障探索、回溯和臨界點處理。“線探索法”不用存儲各網點信息，有效地節(jié)省了存儲空間、提高了處理器的查詢效率。“線探索法”局限性在于其時間花費高、繞障能力不強。國內外很多學者對此方法進行了改進，包括使用雙向搜索法的Higtower 算法、基于最小樹配置的OARSMT 算法和An-OARSMan 算法等。也有學者以此方法為基礎提出無網格搜索方法并應用于二維布線。“線探索法”目前也主要應用于二維PCB布線。相對二維布線，三維布線空間自由度高、布線所針對的幾何模型模型復雜，因為三維布線問題也更加復雜。實用的三維布線算法不僅應能自動生成布線路徑，還應能對生成的布線路徑自動調整，使布線路徑滿足工藝要求。本文針對某軍工研究所工藝技術要求，提出以下三維自動布線方法：

　　(1)“按面自動布線”，即按幾何結構的拓撲面自動生成布線路徑。

　　(2)“貼壁干涉自動調整”，即按“貼壁面”自動進行干涉檢查并根據干涉檢查結果自動進行路徑調整。“貼壁面”是指生成布線路徑時作為主要參考的幾何模型的拓撲面。

　　其中，“按面自動布線”保證了生成的布線路徑從工藝角度的合理性;而“貼壁干涉自動調整”則使所布路徑不會與布線對象干涉，進一步從工藝角度保證了布線路徑的實用性。

　　總結

　　本文提出的三維電氣自動布線方法具有以下特點：

　　(1)“按面自動布線”綜合了“迷宮法”和“線探索法”的算法思想，首先根據三維布線模型的表面法矢通過預留適當距離的方式確定過渡點，進而自動生成布線路徑。該方法簡化了布線過程中的交互操作，提高了布線的效率，并保證了所生成布線路徑的工藝可行性。

　　(2)“貼壁干涉自動調整”實現(xiàn)了對布線過程中線纜之間以及線纜和布線對象間的干涉信息的自動檢查，并可以根據干涉量的大小自動調整發(fā)生干涉的路徑，從而在“按面自動布線”基礎上進一步簡化了布線設計人員的人工交互操作，提高了布線的自動化程度。

　　將來要進行的工作包括：

　　(1)“按面自動布線”方法中，關于處理復雜的曲面的RCP的生成算法和路徑生成方法，還有待進一步研究。此外，“按面自動布線”方法采用了預留線面距離的方式防止干涉。但是，由于布線路徑半徑不固定、路徑空間交匯等，目前“按面自動布線”的結果仍可能存在干涉，這有待于通過適當的優(yōu)化算法來解決。

　　(2)“貼壁干涉自動調整”在處理復雜模型的路徑干涉問題時，由于布線路徑多、幾何模型結構復雜等原因，算法時耗高。這有待于設計高效的干涉檢查算法，或是通過干涉檢查前引入適當人工預處理的方法來解決。