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

柯愛心，周馳

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

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

柯愛心，周馳

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

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

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

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

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

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

1 優(yōu)化模型

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

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

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

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

約束條件:

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

2 分離和穿透距離計(jì)算算法

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

2.1 多邊形的三角形劃分

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

2.2 三角形的干涉頂點(diǎn)計(jì)算

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

a．求解干涉多邊形的交點(diǎn)類頂點(diǎn)。

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

b．求解干涉多邊形的端點(diǎn)類頂點(diǎn)。

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

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

2.3 距離算法

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

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

3 計(jì)算實(shí)例

實(shí)例優(yōu)化模型的零件初始布局圖如圖1實(shí)線所示。3個(gè)圖形的質(zhì)心坐標(biāo)分別為S1(5．0，7．0)，S2(8．0，7．0)，S3(7．5，4．5)。S1的變動(dòng)范圍為［4≤x1≤6，6≤y1≤8］，S2的變動(dòng)范圍為［7≤x2≤9，6≤y2≤8］，S3的變動(dòng)范圍為［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 初始零件布局

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

由本文算法編程計(jì)算得出的優(yōu)化結(jié)果如圖2所示，此時(shí)三個(gè)零件的質(zhì)心坐標(biāo)分別為S1(5．103 5，6．719 6)，S2(7．556 3，7．097 9)，S3(7．660 5，5．162 8)，三個(gè)零件相互之間的間隙值分別為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ì)人員根據(jù)干涉量的大小、方向判斷，從而做出人工的調(diào)整，這種人工的調(diào)整準(zhǔn)確性較低，而且需要經(jīng)過多次調(diào)整，以達(dá)到滿意的間隙要求，工作量較大。在此計(jì)算實(shí)例中，有三個(gè)零件，當(dāng)調(diào)整P1和P2之間的間隙時(shí)，可能會(huì)造成P1和P3或者P2和P3之間發(fā)生干涉或者分離過大，產(chǎn)品零件越多時(shí)，間隙調(diào)整難度越大。而本文優(yōu)化方法，在給定各零件的中心移動(dòng)范圍和零件相互之間的目標(biāo)間隙值時(shí)，通過計(jì)算可以直接得到最優(yōu)間隙結(jié)果，一次調(diào)整即可滿足間隙要求。因此與普通方法相比較，本文的優(yōu)化方法有助于減輕設(shè)計(jì)人員對(duì)產(chǎn)品裝配設(shè)計(jì)的工作量，調(diào)整時(shí)間更短，工作效率更高，并且相比普通方法中的人工調(diào)整，可滿足更為精確的間隙控制要求。

4 結(jié)束語

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

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

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

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

［4］黃松柏.一種改進(jìn)的動(dòng)態(tài)OBB層次結(jié)構(gòu)碰撞算法［J］.北京石油化工學(xué)院學(xué)報(bào)，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ì)算兩個(gè)凸多面體間距離的一個(gè)新算法［J］.蘇州科技學(xué)院學(xué)報(bào)，2003，20(2):11－16.

［8］劉德全，滕弘飛.不規(guī)則多邊形的干涉算法［J］.大連理工大學(xué)學(xué)報(bào)，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

廣東省科技計(jì)劃項(xiàng)目(2008B010400042)

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