柯愛心，周馳

(華南理工大學(xué)機械與汽車工程學(xué)院，廣東廣州 510640)

基于非線性規(guī)劃的干涉檢測與間隙優(yōu)化算法

柯愛心，周馳

(華南理工大學(xué)機械與汽車工程學(xué)院，廣東廣州 510640)

為應(yīng)對現(xiàn)代工業(yè)產(chǎn)品功能集成化程度日益提高對產(chǎn)品裝配設(shè)計的間隙控制提出的更高要求，針對虛擬裝配中的間隙控制問題，基于非線性規(guī)劃理論，采用干涉距離算法，通過自動調(diào)整得到產(chǎn)品零件在有限空間里的位置，獲得了二維平面內(nèi)既滿足間隙要求又使得零件布局緊湊的優(yōu)化結(jié)果，大大提高了裝配設(shè)計的效率。

干涉檢測;虛擬裝配;機構(gòu)運動;非線性規(guī)劃;間隙優(yōu)化

現(xiàn)代工業(yè)產(chǎn)品功能集成化程度日益提高，要求在更小的產(chǎn)品內(nèi)集成更多的功能，對產(chǎn)品裝配設(shè)計的間隙控制的要求越來越高。間隙對平面機構(gòu)運動的特性有著很大的影響［1］，間隙過小，由于制造、裝配和磨損等原因，容易造成干涉;間隙過大，容易使實際機構(gòu)和理想機構(gòu)的運動發(fā)生偏離，降低機構(gòu)運動精度，還容易引起沖擊動載荷，造成運動副的破壞和失效。目前的主流商業(yè)CAD軟件中均具有靜態(tài)和動態(tài)干涉檢查功能［2］，但其計算結(jié)果主要以干涉體積表示，不能提供準(zhǔn)確的分離和穿透距離，不利于零件相對位置的精確調(diào)整。此外，許多精密產(chǎn)品內(nèi)部排布緊密，為消除干涉所進行的位置調(diào)整可能又會帶來新的干涉，人工調(diào)整存在很大的困難。

碰撞檢測和干涉檢查的根本問題是求交和測試問題［3］，目前幾何模型間的碰撞檢測算法大致可分為空間分解法、層次包圍盒法和距離算法。其中空間分解法適用于稀疏的環(huán)境中分布比較均勻的幾何對象間的碰撞檢測，比如飛行模擬等場合［3］。層次包圍盒法應(yīng)用更為廣泛，適用復(fù)雜環(huán)境中的碰撞檢測，比較典型的包圍盒類型有沿坐標(biāo)軸的包圍盒AABB、包圍球、方向包圍盒OBB、固定方向凸包等［4］。層次包圍盒法要獲得較高的計算精度，必須提高包圍盒對原始模型的逼近緊密度，但是這又會降低其計算效率。距離算法是從距離求解的角度來判定物體之間是否發(fā)生干涉。和其他算法相比，距離算法的優(yōu)點在于除了可以用來判定物體之間的位置關(guān)系，還能提供間隙大小和穿透強度信息，有利于設(shè)計方案的調(diào)整。

鑒于本文針對的是平面機構(gòu)的間隙自動優(yōu)化，因此采用距離算法。凸多面體之間的最小間隙算法比較成熟［5］。Ma提出了一個凸多面體的距離算法［6］，但是當(dāng)兩多面體發(fā)生干涉時，該算法返回一個零距離值，不能提供穿透強度信息。文獻［7］通過各自頂點在公垂線上的投影計算得到兩凸多面體間的最短距離，其難點在于公垂線的確定。劉德全等人將多邊形分解為三角形，從而將多邊形的干涉問題轉(zhuǎn)換為三角形的干涉問題［8］，該方法適用于凸多邊形和凹多邊形。本文研究對象是基于同一平面上的若干零部件，需要對各個零部件之間的間隙進行優(yōu)化管理，因而采用基于距離求解的算法，直接利用頂點和質(zhì)心信息以及投影算法，當(dāng)發(fā)生干涉時計算其最大穿透距離，不發(fā)生干涉時計算其分離距離。

1 優(yōu)化模型

在裝配設(shè)計過程中必須首先保證各個零件之間的間隙。但由于產(chǎn)品的整體外形空間有限，因此本文算法是在滿足間隙的前提下，自動調(diào)整零件位置，使得零件布局最緊湊，達到優(yōu)化目的。優(yōu)化目標(biāo)是使各個相鄰零件之間的距離之和最小。

不失一般性，假設(shè)該產(chǎn)品內(nèi)部存在n個零件，以Pi(i=1，2，…，n)表示。每一個零件Pi的質(zhì)心為S3(xi，yi)。系統(tǒng)間隙優(yōu)化的目標(biāo)在于保證零件間隙要求的前提下，使得各個相鄰零件之間的距離之和最小。其非線性規(guī)劃數(shù)學(xué)模型如下:

目標(biāo)函數(shù):minF(x)=∑Dist(Pi，Pj)

(i，j=1，2，…，n，且i≠j)

約束條件:

出于實際工作環(huán)境考慮，每個零件的移動范圍都受到一定的限制，因此約束條件(1)、(2)限制了零件的移動范圍，約束條件(3)用于保證零件之間的間隙。當(dāng)間隙超過了范圍，分離或穿透距離可作為一個懲罰因子，給目標(biāo)函數(shù)一個較大的懲罰值，以此來保證間隙要求。

2 分離和穿透距離計算算法

上述優(yōu)化算法的重點在于分離和穿透距離的計算。對于任意形狀的零件，可用多邊形來逼近。當(dāng)多邊形的頂點足夠多時，任意形狀零件的干涉距離計算就轉(zhuǎn)變?yōu)槎噙呅胃缮婢嚯x計算?；趫D形分解的方法，又可進一步將任意平面多邊形分解成若干個三角形，多邊形之間的干涉計算則轉(zhuǎn)化成兩兩三角形之間的干涉計算［8］。

2.1 多邊形的三角形劃分

本文所采用的干涉算法是先將任意二維多邊形劃分成若干個凸多邊形，然后對每個凸多邊形進行三角剖分，再計算兩兩三角形對之間的干涉量，其干涉量總和即是原平面多邊形之間的最大干涉量。本文采用周培德［9］提出的算法進行多邊形凸劃分，其時間復(fù)雜度為O(n)。在此基礎(chǔ)上，將凸多邊形頂點按逆時針排列:p1，p2，…，pn，由于剖分無需進行任何優(yōu)化，可直接劃分成三角形p1p2p3，p1p3p4，…，p1pn－1pn這(n－2)個三角形。

2.2 三角形的干涉頂點計算

三角形也屬于凸多邊形，根據(jù)集合理論，兩個凸集的交集仍為凸集，因此兩三角形之間若存在干涉，則干涉圖形必定為凸多邊形，且干涉凸多邊形的頂點都可以分為兩類:一類是兩個三角形的邊線段產(chǎn)生的內(nèi)部交點，稱為交點類頂點(三角形的頂點為交點除外);一類是原三角形頂點，即一個三角形的頂點同時被另一個三角形所包含，稱為端點類頂點。

a．求解干涉多邊形的交點類頂點。

判斷兩條線段存在內(nèi)部交點的條件為:線段AB的兩個端點位于線段PQ的兩側(cè)，并且線段PQ的兩個端點也位于線段AB的兩側(cè)。即同時滿足: (AB×AP)·(AB×AQ)＜0，(PQ×PA)·(PQ× PB)＜0，按線段交點計算公式即可求得交點坐標(biāo)。分別對一個三角形的三條線段與另一個三角形的三條線段進行求交計算，則可以得到干涉多邊形的所有交點類頂點。

b．求解干涉多邊形的端點類頂點。

三角形的頂點是否屬于另一個三角形的判別條件為:設(shè)P為三角形的一個頂點，若P屬于另一個三角形△ABC上的頂點，則同時滿足:AB× AP≥0;BC×BP≥0;CA×CP≥0，由此可確定兩三角形的頂點中的所有端點類頂點。

若求得干涉多邊形的頂點總數(shù)n小于3，則不存在干涉;若求得干涉多邊形的頂點總數(shù)n大于3，則說明原兩三角形存在干涉。

2.3 距離算法

a．穿透距離，即最大干涉距離。兩個零件的最大干涉距離定義為干涉多邊形的所有頂點在兩個零件質(zhì)心連線上的投影點集之間的最大距離。以上平面多邊形之間的干涉算法已經(jīng)計算出干涉多邊形的所有頂點坐標(biāo)，通過投影計算獲取所有頂點在兩零件質(zhì)心連線上的投影坐標(biāo)，然后經(jīng)由距離公式計算兩兩投影點之間的距離，其中最大距離值即為兩個零件之間的最大干涉距離。

b．分離距離。兩個多邊形之間的分離距離也可通過投影算法計算，分別將兩個多邊形的頂點都投影到兩個質(zhì)心連線上，然后計算兩個投影點集之間的最小距離，該最小距離即為兩個零件之間的分離距離。

3 計算實例

實例優(yōu)化模型的零件初始布局圖如圖1實線所示。3個圖形的質(zhì)心坐標(biāo)分別為S1(5．0，7．0)，S2(8．0，7．0)，S3(7．5，4．5)。S1的變動范圍為［4≤x1≤6，6≤y1≤8］，S2的變動范圍為［7≤x2≤9，6≤y2≤8］，S3的變動范圍為［6．5≤x3≤8．5，3．5≤y3≤5．5］。要求保證三者相互之間的間隙值Gap(P1，P2)的限定范圍為［0，0．1］，Gap(P2，P3)的限定范圍為［0．2，0．3］，Gap(P1，P3)的限定范圍為［0.1，0.2］。

圖1 初始零件布局

首先進行零件的凸多邊形劃分，劃分結(jié)果如圖1中虛線所示。然后進行三角形剖分，將每個多邊形都剖分為10個三角形，兩個相鄰零件之間做干涉檢測時，兩個多邊形的所有剖分三角形兩兩計算得到所有干涉頂點，運用前文所述投影算法得到穿透或分離距離，作為非線性規(guī)劃算法的約束條件(3)的懲罰因子。

由本文算法編程計算得出的優(yōu)化結(jié)果如圖2所示，此時三個零件的質(zhì)心坐標(biāo)分別為S1(5．103 5，6．719 6)，S2(7．556 3，7．097 9)，S3(7．660 5，5．162 8)，三個零件相互之間的間隙值分別為Gap(P1，P2)=0．068 0，Gap(P2，P3)=0．240 2，Gap(P1，P3)=0.101 4。

圖2 優(yōu)化后零件布局

在傳統(tǒng)的普通方法中，需要依賴設(shè)計人員根據(jù)干涉量的大小、方向判斷，從而做出人工的調(diào)整，這種人工的調(diào)整準(zhǔn)確性較低，而且需要經(jīng)過多次調(diào)整，以達到滿意的間隙要求，工作量較大。在此計算實例中，有三個零件，當(dāng)調(diào)整P1和P2之間的間隙時，可能會造成P1和P3或者P2和P3之間發(fā)生干涉或者分離過大，產(chǎn)品零件越多時，間隙調(diào)整難度越大。而本文優(yōu)化方法，在給定各零件的中心移動范圍和零件相互之間的目標(biāo)間隙值時，通過計算可以直接得到最優(yōu)間隙結(jié)果，一次調(diào)整即可滿足間隙要求。因此與普通方法相比較，本文的優(yōu)化方法有助于減輕設(shè)計人員對產(chǎn)品裝配設(shè)計的工作量，調(diào)整時間更短，工作效率更高，并且相比普通方法中的人工調(diào)整，可滿足更為精確的間隙控制要求。

4 結(jié)束語

本文針對產(chǎn)品設(shè)計中的間隙控制要求，建立了一套間隙自動優(yōu)化的算法，并在Pro/E中得到實現(xiàn)。該算法有助于減輕設(shè)計人員產(chǎn)品裝配設(shè)計的工作量，相比人工調(diào)整可滿足更為精確的間隙控制要求。本算法具有以下幾個特點:(1)所建立的干涉檢測算法，可以精確計算出分離距離和最大穿透距離。相比一般CAD軟件計算的干涉體積，對于設(shè)計方案的修改提供了更為準(zhǔn)確的參考。(2)基于非線性規(guī)劃理論，提出了間隙處理的優(yōu)化算法，可以通過自動調(diào)整得到產(chǎn)品最合理的零件布局。(3)文中介紹的是靜態(tài)干涉的計算，通過改變零件的旋轉(zhuǎn)角度，本算法可以方便地擴展到動態(tài)間隙控制。

［1］田浩，寇偉，白爭鋒.間隙對平面機構(gòu)運動特性的影響分析［J］.機械設(shè)計與制造，2010(2):17－18.

［2］康文利，陳曉明.UG二次開發(fā)技術(shù)在虛擬裝配干涉檢驗中的應(yīng)用［J］.機械工程與自動化，2011(3):43－45.

［3］黃娟，顧寄南.裝配仿真中碰撞干涉檢查研究的綜述［J］.江蘇大學(xué)學(xué)報，2002，23(2):17－21.

［4］黃松柏.一種改進的動態(tài)OBB層次結(jié)構(gòu)碰撞算法［J］.北京石油化工學(xué)院學(xué)報，2011，19(1):16－21.

［5］Chakraborty N，Peng J，Akella S，et al.Proximity queries between convex objects:An interior point approach for implicit surfaces［J］.IEEE Transactions on Robotics，2008，24(1):211－222.

［6］Ma，Nahon M.A general method for computing the distance between convex polyhedra［C］//proceedings of ASME Conference on Advances in Design and Automation，Pheonix:Arizona，1992: 109－117.

［7］周水生，容曉鋒，周利華.計算兩個凸多面體間距離的一個新算法［J］.蘇州科技學(xué)院學(xué)報，2003，20(2):11－16.

［8］劉德全，滕弘飛.不規(guī)則多邊形的干涉算法［J］.大連理工大學(xué)學(xué)報，1999，39(5):597－600.

［9］ZHOU Peide.An algorithm for partitioning polygons into convex parts［J］.Journal of Beijing Institute of Technology，1997，6(4): 363－368.

An Algorithm of Interference Detection and Clearance Optimization Based on Nonlinear Programming

KE Aixin，ZHOU Chi

(South China University of Technology，Guangdong Guangzhou，510640，China)

Because more functions of modern industrial products are integrated in a limited space，it has a much higher requirement on the controlling of the clearance between assembled parts.This paper proposes an algorithm focused on the clearance controlling in virtual assembly.Based on the theory of nonlinear programming，it uses the distance algorithm of interference to automatically adjust the location of the parts to have an optimized layout of parts.This layout can meet the requirement of clearance and also make parts most compact.The algorithm improves the efficiency of assembly design.

Interference Detection;Virtual Assembly;Mechanism Motion;Nonlinear Programming;Clearance Optimization

TH16;TP399

A

2095－509X(2013)10－0022－03

10.3969/j.issn.2095－509X.2013.10.006

2013－07－18

廣東省科技計劃項目(2008B010400042)

柯愛心(1988—)，男，湖北黃岡人，華南理工大學(xué)碩士研究生，主要從事CAD軟件二次開發(fā)方面的研究。