基于非線性規劃的干涉檢測與間隙優化算法

柯愛心，周馳

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

基于非線性規劃的干涉檢測與間隙優化算法

柯愛心，周馳

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

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

干涉檢測;虛擬裝配;機構運動;非線性規劃;間隙優化

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

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

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

1 優化模型

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

不失一般性，假設該產品內部存在n個零件，以Pi(i=1，2，…，n)表示。每一個零件Pi的質心為S3(xi，yi)。系統間隙優化的目標在于保證零件間隙要求的前提下，使得各個相鄰零件之間的距離之和最小。其非線性規劃數學模型如下:

目標函數:minF(x)=∑Dist(Pi，Pj)

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

約束條件:

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

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

上述優化算法的重點在于分離和穿透距離的計算。對于任意形狀的零件，可用多邊形來逼近。當多邊形的頂點足夠多時，任意形狀零件的干涉距離計算就轉變為多邊形干涉距離計算?；趫D形分解的方法，又可進一步將任意平面多邊形分解成若干個三角形，多邊形之間的干涉計算則轉化成兩兩三角形之間的干涉計算［8］。

2.1 多邊形的三角形劃分

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

2.2 三角形的干涉頂點計算

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

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

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

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

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

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

2.3 距離算法

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

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

3 計算實例

實例優化模型的零件初始布局圖如圖1實線所示。3個圖形的質心坐標分別為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 初始零件布局

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

由本文算法編程計算得出的優化結果如圖2所示，此時三個零件的質心坐標分別為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 優化后零件布局

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

4 結束語

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

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

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

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

［4］黃松柏.一種改進的動態OBB層次結構碰撞算法［J］.北京石油化工學院學報，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］.蘇州科技學院學報，2003，20(2):11－16.

［8］劉德全，滕弘飛.不規則多邊形的干涉算法［J］.大連理工大學學報，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—)，男，湖北黃岡人，華南理工大學碩士研究生，主要從事CAD軟件二次開發方面的研究。