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

　　1、引言

　　1.1、三維布線技術(shù)

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

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

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

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

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

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

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

　　(1)“按面自動(dòng)布線”，即按幾何結(jié)構(gòu)的拓?fù)涿孀詣?dòng)生成布線路徑。

　　(2)“貼壁干涉自動(dòng)調(diào)整”，即按“貼壁面”自動(dòng)進(jìn)行干涉檢查并根據(jù)干涉檢查結(jié)果自動(dòng)進(jìn)行路徑調(diào)整。“貼壁面”是指生成布線路徑時(shí)作為主要參考的幾何模型的拓?fù)涿妗?/p>

　　其中，“按面自動(dòng)布線”保證了生成的布線路徑從工藝角度的合理性;而“貼壁干涉自動(dòng)調(diào)整”則使所布路徑不會(huì)與布線對(duì)象干涉，進(jìn)一步從工藝角度保證了布線路徑的實(shí)用性。

　　總結(jié)

　　本文提出的三維電氣自動(dòng)布線方法具有以下特點(diǎn)：

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

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

　　將來(lái)要進(jìn)行的工作包括：

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

　　(2)“貼壁干涉自動(dòng)調(diào)整”在處理復(fù)雜模型的路徑干涉問(wèn)題時(shí)，由于布線路徑多、幾何模型結(jié)構(gòu)復(fù)雜等原因，算法時(shí)耗高。這有待于設(shè)計(jì)高效的干涉檢查算法，或是通過(guò)干涉檢查前引入適當(dāng)人工預(yù)處理的方法來(lái)解決。