周 健，王愛民，李周瑜

（北京理工大學(xué) 機(jī)械與車輛學(xué)院數(shù)字化制造研究所，北京 100081）

0 引言

在殼、舾、涂一體化作業(yè)的現(xiàn)代造船生產(chǎn)模式下，以中間產(chǎn)品為導(dǎo)向的船舶殼體建造已成為船舶建造的重要環(huán)節(jié)。作為船舶殼體的主要組成，曲面分段輪廓彎曲結(jié)構(gòu)復(fù)雜，重量體積龐大，建造工序復(fù)雜，生產(chǎn)周期從幾星期到幾個(gè)月不等，一般采用混合型號、批量分段、多塊場地和固定工位的手工作業(yè)模式。在目前船舶生產(chǎn)企業(yè)存在的相對有限建造場地資源與曲面分段中間產(chǎn)品大量需求的情況下，船舶建造中曲面分段建造所需的場地空間資源與整船交貨期時(shí)間節(jié)點(diǎn)相互制約，同時(shí)受制于生產(chǎn)管理手段的缺乏，導(dǎo)致船舶曲面分段生產(chǎn)已經(jīng)成為制約船舶高效生產(chǎn)的瓶頸［1］。

有序、協(xié)調(diào)、可控和高效的生產(chǎn)管理是提高船舶曲面分段建造水平的關(guān)鍵支撐技術(shù)，也是本文以提高船舶曲面分段生產(chǎn)規(guī)劃效率為目標(biāo)的切入重點(diǎn)。目前船舶曲面分段生產(chǎn)規(guī)劃主要有如下兩種形式：①依靠手工的經(jīng)驗(yàn)式管理，如通過掛墻式白板和裁減得到的紙質(zhì)曲面分段卡片，以手動粘貼的方式模擬分段的場地排布位置和生產(chǎn)作業(yè)計(jì)劃，這種方式的建模效率低下、分段外形粗略簡化，布局定位精確度難以得到保證；②依靠企業(yè)資源規(guī)劃（Enterprice Resource Planning，ERP）或日程管理系統(tǒng)實(shí)現(xiàn)“黑盒”方式管理［2］，即對曲面分段建造車間進(jìn)行任務(wù)進(jìn)入與完工輸出的宏觀管理，但其計(jì)劃與控制過程缺乏有效的交互性和沖突判斷力。隨著造船企業(yè)“轉(zhuǎn)?！毙枨蟮娜找嫫惹幸约捌髽I(yè)對精益化管理的日益重視，亟待開展以制造執(zhí)行系統(tǒng)（Manufacturing Execution System，MES）為核心的船舶曲面分段空間布局技術(shù)的研究。

在曲面分段生產(chǎn)模型建模研究方面，羅岱［3］通過eM-PLANT 仿真建模工具，建立了從設(shè)備層到生產(chǎn)線層最后到車間層自下而上的層次化車間仿真模型，通過模型仿真獲取船舶分段建造計(jì)劃的可視性分析結(jié)果；戰(zhàn)德臣［4］提出以里程碑計(jì)劃和分段吊裝計(jì)劃為主體的分層式船舶建造生產(chǎn)計(jì)劃體系模型，并從時(shí)間、任務(wù)、產(chǎn)品和資源粒度等角度，對作業(yè)方式、作業(yè)場地、資源組織和決策層次的生產(chǎn)活動進(jìn)行協(xié)調(diào)控制。張光發(fā)［5］通過對仿真控制類、生產(chǎn)線類、仿真數(shù)據(jù)類和用戶接口類進(jìn)行模塊定義，構(gòu)造了仿真系統(tǒng)的評價(jià)模型和優(yōu)化目標(biāo)，實(shí)現(xiàn)了船舶分段建造計(jì)劃的仿真和優(yōu)化。以上研究主要針對曲面分段建造業(yè)務(wù)和資源協(xié)調(diào)過程建模與仿真展開，缺少模型對空間布局與時(shí)間調(diào)配的有效支持。

在碰撞檢測算法方面，Chin等［6］研究了兩個(gè)凸多邊形的相交和最小距離問題，通過可視邊鏈和凸頂點(diǎn)相對其內(nèi)部點(diǎn)的單調(diào)性，提出了判斷凸多邊形和一個(gè)簡單非凸多邊形相交問題的最優(yōu)算法。覃中平［7］研究了平面內(nèi)兩個(gè)凸多邊形P和Q，若P沿給定方向移動時(shí)將與Q碰撞，采用折半搜索技術(shù)來確定P與Q相碰撞時(shí)兩者最初相碰撞的頂點(diǎn)和邊。汪嘉業(yè)［8］利用單調(diào)折線研究了在一個(gè)多邊形的凸包和另一個(gè)多邊形不相交的條件下，確定兩個(gè)多邊形是否碰撞，并在碰撞時(shí)確定全部碰撞部位的問題。算法的研究主要針對凸多邊形的實(shí)時(shí)碰撞檢測展開，缺少針對曲面分段存在的復(fù)雜多邊形及大批量運(yùn)算的特點(diǎn)展開的相關(guān)研究。

在交互式布局技術(shù)研究方面，何良莉［9］針對復(fù)雜產(chǎn)品裝配與布局提出了綜合使用Neowand 和FOB（flock of birds）進(jìn)行人機(jī)交互的方法，將實(shí)物模型轉(zhuǎn)化為三維模型，在加入人機(jī)輸入信息后轉(zhuǎn)化為二維問題，最后生成優(yōu)化的布局結(jié)果，該交互布局的設(shè)計(jì)思路具有比較普適的參考價(jià)值，但該種方法在船舶曲面分段場地空間布局方面的研究與應(yīng)用還比較少；陳寧［10］提出利用DELMIA 工具的船舶建造計(jì)劃構(gòu)建仿真系統(tǒng)方法，通過對場地空間資源和建造時(shí)間約束的分析與優(yōu)化，得出了分段布局的可視化解決方案。以上研究都是從計(jì)劃結(jié)果的層面上對艦船分段的空間布局進(jìn)行可視化的構(gòu)建，缺乏對過程中建造計(jì)劃的調(diào)整和控制，尤其是復(fù)雜分段模型在有限空間資源約束下的布局調(diào)整與邏輯判斷問題還缺乏研究。

本文結(jié)合國內(nèi)外研究現(xiàn)狀以及企業(yè)的實(shí)際需求，針對曲面分段多品種、小批量和混合場地生產(chǎn)的業(yè)務(wù)特點(diǎn)，以實(shí)現(xiàn)船舶曲面分段空間布局的精細(xì)化、可視化、高效性的管理為目標(biāo)，提出基于實(shí)時(shí)碰撞檢測的曲面分段人機(jī)交互式空間布局技術(shù)。該技術(shù)以參數(shù)注入的空間布局建模為模型生成手段，以動態(tài)的實(shí)時(shí)碰撞檢測算法和布局干涉日程沖突的處理機(jī)制為核心，實(shí)現(xiàn)了人機(jī)交互式的曲面分段空間布局與生產(chǎn)計(jì)劃安排管理，提高了船舶曲面分段生產(chǎn)規(guī)劃的精益高效的控制能力，促進(jìn)了現(xiàn)代造船模式下的數(shù)字化、快速化執(zhí)行水平的提升。

1 問題描述

船舶曲面分段人機(jī)交互場地布局是實(shí)現(xiàn)曲面分段建造空間建造位置安排管理精細(xì)化、曲面分段建造過程可控化、曲面分段建造資源利用高效化的有效途徑。從相關(guān)技術(shù)的國內(nèi)外研究現(xiàn)狀來看，目前已經(jīng)取得了一些進(jìn)展，尤其MES 架構(gòu)方面具有豐富的成果。但就曲面分段空間布局方面的研究，還存在明顯不足，主要體現(xiàn)在以下幾個(gè)方面：

（1）基于生產(chǎn)作業(yè)表格式數(shù)據(jù)無法直觀提供空間布局展示與控制的有效手段

船舶曲面分段建造車間制定生產(chǎn)計(jì)劃的方式依然采用作業(yè)表格或甘特圖的方式，盡管這種計(jì)劃控制手段對曲面分段的建造日程可以加以控制，避免不必要的沖突和完工日期的拖延，但面向有限場地資源方面無法做到對不同形狀的曲面分段在場地中的空間布局做有效的控制和分析，更無法直觀地給予空間布局在建造時(shí)間變化過程中的動態(tài)作業(yè)模型展示。

（2）基于白板式的場地—分段監(jiān)控形式難以有效支持分段任務(wù)更換場地和日期的沖突處理要求

與傳統(tǒng)的機(jī)械加工類車間的制造執(zhí)行監(jiān)控偏重于按照工藝流程為主線進(jìn)行監(jiān)控不同，曲面分段建造執(zhí)行過程監(jiān)控涉及到分段的平面矢量化投影建模，即需要模擬分段在場地上的投影圖形以進(jìn)行平面布局。當(dāng)前曲面分段建造執(zhí)行中曲面分段場地布局的方式是以紙質(zhì)模型代表分段模型、在實(shí)物面板上實(shí)現(xiàn)的，不僅操作不方便而且精度差，無法適應(yīng)現(xiàn)代造船模式下的快速響應(yīng)和精益化制造的需求，解決這一問題的關(guān)鍵是在建立合理的分段建模與建造任務(wù)的定義手段的基礎(chǔ)上，實(shí)現(xiàn)圖形化的分段布局與交互界面，同時(shí)提供具有友好快捷操作的人工調(diào)整手段。

（3）曲面分段空間布局交互水平較低，無法滿足快節(jié)奏生產(chǎn)任務(wù)排布的需求

曲面分段的生產(chǎn)具有時(shí)間與空間雙重耦合的特點(diǎn)，為人機(jī)交互賦予了復(fù)雜的技術(shù)內(nèi)涵，主要體現(xiàn)在分段對場地的占用周期各不相同，當(dāng)對某個(gè)分段進(jìn)行調(diào)整時(shí)，不僅要避免當(dāng)天場地布局沖突，還要兼顧該分段在持續(xù)占用周期內(nèi)的其他天數(shù)場地布局沖突情況。當(dāng)任務(wù)比較頻繁，例如發(fā)生插入、延期等情況時(shí)，依靠經(jīng)驗(yàn)式的調(diào)整已經(jīng)難以滿足對場地利用情況實(shí)時(shí)查看及其沖突判斷的及時(shí)處理需求。

2 曲面分段空間布局交互技術(shù)方案

基于實(shí)時(shí)碰撞檢測的曲面分段場地布局技術(shù)方案如圖1所示，該技術(shù)通過對曲面分段產(chǎn)品設(shè)計(jì)模型、場地空間與功能區(qū)域二維描述、曲面分段建造訂單的數(shù)據(jù)解析，以實(shí)時(shí)高效的碰撞檢測為核心，以面向?qū)ο蟮姆侄巍龅啬Ｐ蜑殛P(guān)鍵對象，通過流程控制與協(xié)調(diào)配合，實(shí)現(xiàn)從建造計(jì)劃啟動、定制和調(diào)整到執(zhí)行的全過程空間布局控制，從而達(dá)到協(xié)調(diào)、可控、高效的曲面分段場地建造空間布局規(guī)劃效果。

3 關(guān)鍵技術(shù)

根據(jù)技術(shù)方案的設(shè)計(jì)，在布局業(yè)務(wù)與對象建模、實(shí)時(shí)碰撞檢測與圖形變換、交互式布局設(shè)計(jì)與建造日程規(guī)劃三個(gè)方面展開關(guān)鍵技術(shù)研究，并提出如下關(guān)鍵技術(shù)。

3.1 參數(shù)注入式曲面分段空間布局建模技術(shù)

曲面分段空間布局模型是船舶曲面分段在實(shí)際建造場地中，以固定的位置和姿態(tài)，在一段建造周期內(nèi)展開一系列作業(yè)任務(wù)的數(shù)字化、圖形化、可控化的客觀描述，同時(shí)也是完成交互式布局排產(chǎn)并指導(dǎo)生產(chǎn)作業(yè)的重要載體，因此應(yīng)滿足合理性和高效性的原則：①合理性原則，包括針對實(shí)際生產(chǎn)模式建立符合多車間—多場地—多分段的層次化模型；曲面分段的投影圖形與實(shí)際三維工程圖一致，能夠?yàn)榭臻g布局提供支持；曲面分段布局模型周圍應(yīng)保留一定的有效加工活動空間。②高效性原則，包括應(yīng)針對曲面分段大批量混場地的生產(chǎn)特點(diǎn)，提供批量處理高效生成的建模手段；在保證分段空間布局控制精度的基礎(chǔ)上實(shí)現(xiàn)模型間碰撞檢測的大數(shù)據(jù)量快速運(yùn)算；曲面分段的空間布局與建造日程計(jì)劃之間在時(shí)空上沖突的處理方式應(yīng)高效。根據(jù)上述原則，曲面分段空間布局模型采用參數(shù)注入式建模方法。該方法以具有模型元素及其關(guān)聯(lián)關(guān)系的層次化原始模型為基礎(chǔ)，通過參數(shù)接口逐層注入一系列參數(shù)和約束的數(shù)據(jù)，形成具有明確尺寸、位置和時(shí)間標(biāo)度的車間—場地—分段任務(wù)的結(jié)構(gòu)化布局模型。具體的原始模型元素構(gòu)成與關(guān)聯(lián)關(guān)系如表1所示，L1、L2、L3級的元素構(gòu)成了車間—場地—曲面分段的父子關(guān)系層級元素定義，L2、L3 通過L4 層的元素提供關(guān)聯(lián)關(guān)系的支撐。

表1 原始模型的元素構(gòu)成與關(guān)聯(lián)關(guān)系

各個(gè)參數(shù)與約束相互獨(dú)立，并留有對外接口，可分別進(jìn)行調(diào)整設(shè)置，從而實(shí)現(xiàn)曲面分段空間布局建模的合理性和高效性。

（1）基于點(diǎn)的參數(shù)（Point＿x&Point＿y）

主要用于定義二維圖形的邊界。一對Point＿x和Point＿y組成的坐標(biāo)用于表示邊界多邊形的頂點(diǎn)坐標(biāo)，一般由三對或三對以上組合在一起，用于定義不規(guī)則多邊形的頂點(diǎn)坐標(biāo)集合，這類參數(shù)用于場地的可用區(qū)域、胎架占地圖形、過道占地圖形、曲面分段投影圖形。

（2）基于位置的參數(shù)

主要用于定義模型間的相對物理位置。一對Layout＿x&和Layout＿y用于約束分段布局的空間坐標(biāo)位置，Rot＿Angle用于約束分段的擺放角度，這個(gè)參數(shù)是分段空間布局的重要控制對象。

（3）基于時(shí)間范圍的參數(shù)（TimeRange）

主要用于定義分段建造時(shí)間跨越范圍。由進(jìn)場時(shí)間StartTime和離場時(shí)間EndTime組成，是分段建造排產(chǎn)的重要控制對象。

（4）基于從屬關(guān)系的參數(shù)（Parent＿Id）

采用外鍵關(guān)聯(lián)方式，用于定義元素間的從屬關(guān)系。通過字符串的外鍵方式指定父級元素，高效處理分段和場地間的關(guān)系，是分段在場地間切換調(diào)整的主要控制對象。

在相應(yīng)的參數(shù)數(shù)據(jù)注入至原始模型后，參數(shù)數(shù)據(jù)逐層深入原始模型內(nèi)部：首先通過車間層控制器將車間參數(shù)P1-1、P1-2，P1-3分離，利用P1-1實(shí)現(xiàn)車間層模型的實(shí)例化，P1-3包含未分配場地的分段任務(wù)，隨后將P1-2的數(shù)據(jù)注入場地層控制器，形成若干具有胎架子模型P2-5、過道子模型P2-6、懸吊高度P2-3和可用工作范圍P2-4的場地模型，然后抽取P2-7注入曲面分段層控制器中，形成若干從屬與對應(yīng)場地的具有相應(yīng)投影多邊形圖形P3-3、建造時(shí)間區(qū)間P3-4和翻轉(zhuǎn)高度P3-8的曲面分段模型，建模過程如圖2所示。

3.2 曲面分段實(shí)時(shí)碰撞處理技術(shù)

基于曲面分段空間布局模型參數(shù)化設(shè)計(jì)，在分段位置安置、位置調(diào)整、場地遷移和建造日期變更的過程中，由于場地空間的有限性和分段任務(wù)數(shù)據(jù)量之多，會出現(xiàn)相應(yīng)的分段間干涉以及分段與場地邊界的干涉情況，分別對50，100，150，200，250個(gè)曲面分段模型進(jìn)行人工排布過程測試，得出完成全部布局發(fā)生的干涉次數(shù)，如圖3所示，其出現(xiàn)頻率隨分段任務(wù)數(shù)量的增加基本呈幾何倍數(shù)增長，另外其他因素對布局干涉次數(shù)的發(fā)生也有一定的影響，影響因素如圖4所示。

因此，解決曲面分段空間布局過程中的干涉問題成為布局算法中的研究重點(diǎn)。

（1）曲面分段碰撞的定義

曲面分段碰撞定義如圖5所示，分段p1和分段p2分別具有一定尺寸的加工活動范圍p′1和p′2，px表示間隙距離為分段模型中的P3-6值，當(dāng)p1和p2不干涉時(shí)，分段間處于a未碰撞狀態(tài)，當(dāng)p′1和p′2發(fā)生干涉且p1和p2不干涉時(shí)，分段間處于b緩沖碰撞狀態(tài)，b狀態(tài)的分段布局會影響分段的正常建造執(zhí)行，當(dāng)p1和p2發(fā)生干涉時(shí)，分段間處于碰撞狀態(tài)c，判定布局不合理。

研究針對解決大量不規(guī)則多邊形（包括凹多邊形）在二維平面上位置變化的過程中對碰撞現(xiàn)象的實(shí)時(shí)判斷和反饋問題，主要解決兩方面問題：①保證分段不規(guī)則多邊形碰撞檢測的精度要求；②提高面向大量多邊形群體碰撞檢測的計(jì)算效率。對此提出了基于動態(tài)采樣率和面向有效區(qū)域的曲面分段碰撞檢測算法流程，描述面向過程的實(shí)時(shí)批量碰撞計(jì)算流程如圖6所示。

（2）基于動態(tài)采樣率的碰撞檢測

采用對檢測對象的布局位置進(jìn)行周期性采樣檢測的方式解決多邊形在移動過程中碰撞檢測的問題，采樣周期其中：μ為布局精度，為設(shè)定的常量；ν為對象瞬時(shí)速率，為基于實(shí)時(shí)捕捉的模型變量。以此在分段未碰撞和緩沖碰撞時(shí)采樣兩種采樣率進(jìn)行碰撞檢測，檢測頻率如表2所示。

表2 碰撞檢測的動態(tài)采樣率表

通過對采樣頻率和布局精度之間的權(quán)衡，實(shí)現(xiàn)在滿足所需精度要求下計(jì)算量的壓縮，同時(shí)針對a、b狀態(tài)采用相差1／2的采樣率，實(shí)現(xiàn)過渡性的碰撞檢測計(jì)算。

（3）面向有效區(qū)域檢測的碰撞計(jì)算

由于同時(shí)處于同一建造場地的分段數(shù)量較多，而在實(shí)際可能與被測分段發(fā)生碰撞的分段只占總數(shù)量的一小部分，以高效性為原則的設(shè)計(jì)方式將有效檢測區(qū)域加以分離，通過計(jì)算進(jìn)入有效區(qū)域的分段與被測分段的碰撞情況，減少計(jì)算次數(shù)，從而提高運(yùn)算速率。如圖7 所示，設(shè)被檢測曲面分段多邊形Cb0在場地中的相對位置坐標(biāo)為

被檢測對象在瞬間的移動方向

由式（1）求得bA和bB值，進(jìn)而求得LA和LB直線方程，LA和LB如圖7所示，其與Cb0部分輪廓和場地邊界組成的閉合區(qū)域即為有效區(qū)域，在此區(qū)域中根據(jù)線段相交方程：

逐一判斷進(jìn)入LA和LB兩條射線之間的其他分段集合，如圖7中的Cb1，Cb2，Cb3，Cb4所示。

遍歷Cb0和Cb1，Cb2，Cb3，Cb4之間的碰撞判斷，一旦與某一分段發(fā)生緩沖碰撞，則發(fā)出提示并按照采樣頻率繼續(xù)檢測，若發(fā)生完全碰撞則終止計(jì)算，并將布局模型中的P3-9變量值由0置為1，將事件拋出至模型U2層。

（4）算法評測

基于有效區(qū)域判斷的原理，采用上述計(jì)算方式的曲面分段碰撞檢測中發(fā)生碰撞的次數(shù)，會隨計(jì)算多邊形數(shù)量的相對比例下降，通過累計(jì)測算，得到如表3所示的統(tǒng)計(jì)，另外考慮到算法對凹多邊形碰撞檢測的支持，算法在處理大數(shù)據(jù)量的復(fù)雜多邊形實(shí)時(shí)碰撞的方面實(shí)現(xiàn)了高效性和實(shí)效性的目標(biāo)，滿足曲面分段布局的業(yè)務(wù)需求。

表3 碰撞檢測算法評測統(tǒng)計(jì)

3.3 分段建造布局中的人機(jī)交互位姿調(diào)整技術(shù)

為了充分利用場地或者出于特殊工藝需求，曲面分段在場地中的布局還涉及其位置坐標(biāo)與姿態(tài)方向的確定。人機(jī)交互的位姿調(diào)整技術(shù)同樣以分段碰撞檢測算法為交互約束，以圖形平移與旋轉(zhuǎn)處理算法為交互操作的響應(yīng)處理方法，實(shí)現(xiàn)對分段場地位姿的人機(jī)交互位姿調(diào)整。技術(shù)示意圖如圖8所示。

（1）分段坐標(biāo)平移調(diào)整技術(shù)

分段相對場地的位置采用二維矢量表達(dá)，矢量值的原點(diǎn)為場地多邊形模型在數(shù)據(jù)庫中排序第一的頂點(diǎn)坐標(biāo)，指向分段多邊形的重心（xΦ，yΦ），分段平移即對二維矢量值的變化控制，坐標(biāo)平移調(diào)整采用的圖形變換如式（3）所示。

第一矩陣表示分段矢量模型相對分段重心的坐標(biāo)集合，第二矩陣中（xΦ，yΦ）為分段模型的重心坐標(biāo)，（x′1，y′1）為場地多邊形第一個(gè)坐標(biāo)點(diǎn)，第三個(gè)矩陣中的（xΔ，yΔ）為平移調(diào)整變化量，等號右側(cè)矩陣為平移后的多邊形頂點(diǎn)坐標(biāo)矩陣。

分段平移過程中不斷根據(jù)人機(jī)操作輸入的變量（xΔ，yΔ）的值計(jì)算等號右側(cè)的矩陣，然后將原有的分段圖形刪去，根據(jù)新的矩陣?yán)L制新位置的分段圖形，這個(gè)過程在不斷的重復(fù)過程中實(shí)現(xiàn)了分段圖形的實(shí)時(shí)變化，同時(shí)不斷累積產(chǎn)生的（xΔ，yΔ）值來計(jì)算分段場地相對位置矢量坐標(biāo)值這個(gè)矢量被作為最終分段場地相對矢量位置保存在數(shù)據(jù)庫中。

（2）消除累計(jì)誤差的分段角度調(diào)整技術(shù)

為滿足場地資源有限空間的最大利用，對于有些形狀特殊的分段，需要將其角度做合適的擺動才可嵌入場地之中，為此人機(jī)交互的分段旋轉(zhuǎn)采用拖動模型旋轉(zhuǎn)的交互方式，為保證圖形能夠根據(jù)交互操作呈現(xiàn)相應(yīng)的旋轉(zhuǎn)變化，需要對分段模型進(jìn)行重構(gòu)，即根據(jù)拖動產(chǎn)生的位移判斷需要的旋轉(zhuǎn)角度，再按照旋轉(zhuǎn)角度量對分段模型進(jìn)行相對其重心的圖形重構(gòu)，同時(shí)結(jié)合碰撞檢測準(zhǔn)則判斷分段的干涉情況并觸發(fā)處理機(jī)制。旋轉(zhuǎn)圖形重構(gòu)的具體算法如下。

假設(shè)n邊形圍繞重心點(diǎn)（xΦ，yΦ）旋轉(zhuǎn)angle°，本質(zhì)上相當(dāng)于將n邊形的每一個(gè)頂點(diǎn)的坐標(biāo)繞著點(diǎn)（xΦ，yΦ）旋轉(zhuǎn)angle°，旋轉(zhuǎn)后組合成新的n邊形即為所求。

首先判斷（x，y）和（xΦ，yΦ）是否重合，如果重合，（x，y）就為結(jié)果，如果不重合，則計(jì)算（x，y）和（xΦ，yΦ）間的直線距離：

計(jì)算當(dāng)前（x，x）和（x0，x0）連線與坐標(biāo)軸之間的夾角：

根據(jù)兩個(gè)角度與0 的關(guān)系判斷，旋轉(zhuǎn)后（x，y）和（xΦ，yΦ）連線與坐標(biāo)軸之間的夾角angleα如表4所示。

表4 旋轉(zhuǎn)角度判斷準(zhǔn)則與結(jié)果表

旋轉(zhuǎn)后的點(diǎn)坐標(biāo)（xα，yα）為：

遍歷多邊形的n個(gè)頂點(diǎn)，進(jìn)行上述運(yùn)算，即可求得旋轉(zhuǎn)后的新多邊形。為了實(shí)現(xiàn)分段圖形重構(gòu)能夠?qū)崟r(shí)的刷新變化，不可避免地要至少對每旋轉(zhuǎn)微小的角度（默認(rèn)為0.1°）進(jìn)行一次上述反正／余弦，然后進(jìn)行再正／余弦的運(yùn)算，如果每次運(yùn)算都以前一次運(yùn)算結(jié)果（xα，yα）作為參考，則大量的旋轉(zhuǎn)計(jì)算會因浮點(diǎn)運(yùn)算的精度限制而產(chǎn)生誤差，繪制的多邊形外形會發(fā)生畸變，造成分段坐標(biāo)碰撞判斷精度下降。因此采用絕對旋轉(zhuǎn)角度作為旋轉(zhuǎn)角度，不論分段如何被旋轉(zhuǎn)，角度始終從0°作為參考，如圖9所示，對比由相對旋轉(zhuǎn)角度和由絕對旋轉(zhuǎn)角度作為參數(shù)的計(jì)算流程，相對前者，后者可有效控制大量循環(huán)三角函數(shù)運(yùn)算帶來的累積誤差，實(shí)時(shí)修正多邊形外形，保證分段間碰撞檢測的精確性。

3.4 人機(jī)交互式分段空間布局的實(shí)現(xiàn)技術(shù)

曲面分段的空間布局指分段在建造場地中的相對位置與姿態(tài)，建造日程指分段進(jìn)入和離開建造場地的時(shí)間，兩者存在綜合空間和時(shí)間兩個(gè)維度的信息關(guān)聯(lián)約束。曲面分段的場地布局體現(xiàn)為多場地分段的協(xié)調(diào)布局以及某分段在特定場地內(nèi)沿著時(shí)間軸的位置確定。曲面分段在計(jì)劃階段以及建造過程中都需要依照現(xiàn)場實(shí)際執(zhí)行情況不斷做出空間布局規(guī)劃與調(diào)整，從而涉及在空間布局與建造日程兩個(gè)維度上的時(shí)空關(guān)聯(lián)協(xié)調(diào)。人機(jī)交互的場地空間布局技術(shù)以分段建造任務(wù)數(shù)據(jù)為驅(qū)動，基于矢量化分段投影建模技術(shù)，結(jié)合圖形變換與碰撞判斷算法，實(shí)現(xiàn)分段建造空間布局和日程計(jì)劃的多維度動態(tài)圖形化展示，以及人機(jī)交互式的分段場地相對位置和擺置方向（簡稱位姿）調(diào)整與建造場地／日程的遷移的人機(jī)交互。該技術(shù)解決了傳統(tǒng)的白板式分段任務(wù)布局處理模式的粗放和難以兼顧時(shí)間與空間雙重協(xié)調(diào)的問題，為曲面分段建造執(zhí)行過程監(jiān)控提供了高效便捷的規(guī)劃執(zhí)行與管理控制手段，其技術(shù)思路如圖10所示。

人機(jī)交互的模型數(shù)據(jù)來源于矢量化分段建模的基礎(chǔ)數(shù)據(jù)，以多場地—多分段—多天構(gòu)成的面板為人機(jī)界面，面板界面將用戶與底層數(shù)據(jù)庫之間建立連接，完成人機(jī)交互的曲面分段空間布局的業(yè)務(wù)協(xié)調(diào)配合過程，主要有以下三方面技術(shù)特點(diǎn)。

（1）分段建造布局與日程規(guī)劃動態(tài)顯示 涉及兩種展示方式：一是多場地動態(tài)展示，以時(shí)間軸為基礎(chǔ)，動態(tài)刷新分段的坐標(biāo)位置和角度，多個(gè)場地同時(shí)呈現(xiàn)在界面中，并按照分段建造的計(jì)劃任務(wù)數(shù)據(jù)不斷生成分段模型圖形并將其分布在計(jì)劃建造的位置；二是單場地多天展示，顯示某時(shí)間區(qū)間內(nèi)某個(gè)場地每一天的分段布局情況，支持快速觀察分段建造的整體規(guī)劃及其變化過程。

（2）分段遷移與布局調(diào)整 基于圖形變換和碰撞檢測算法，通過計(jì)算機(jī)輸入設(shè)備或者手持設(shè)備對人機(jī)交互界面中的曲面分段進(jìn)行時(shí)間和空間的調(diào)整，主要包括曲面分段建造日期整體遷移、曲面分段更換場地、分段任務(wù)移除和添加、分段布局位置調(diào)整和分段布局角度調(diào)整五方面的調(diào)整。

（3）結(jié)構(gòu)化數(shù)據(jù)組織 采用以場地的根節(jié)點(diǎn)的樹形數(shù)據(jù)結(jié)構(gòu)，每個(gè)場地?cái)?shù)據(jù)包含該場地上所有已經(jīng)部署的分段任務(wù)，分段任務(wù)包含分段矢量模型數(shù)據(jù)、布局位置數(shù)據(jù)、建造時(shí)間數(shù)據(jù)及所屬的場地模型數(shù)據(jù)，其中布局位置數(shù)據(jù)包含一個(gè)矢量坐標(biāo)和一個(gè)范圍在0°～360°的角度。這些結(jié)構(gòu)化的數(shù)據(jù)從數(shù)據(jù)庫中分散讀取出來后結(jié)構(gòu)化的整合為一個(gè)xml格式文件發(fā)送給交互界面，通過解析文件內(nèi)容實(shí)現(xiàn)模型界面顯示，用戶操作完后保存數(shù)據(jù)也會打包成xml文件發(fā)送給服務(wù)器保存到數(shù)據(jù)庫中。

人機(jī)交互的分段位姿調(diào)整技術(shù)有效地實(shí)現(xiàn)了分段在場地不變、建造日期不變情況下的布局調(diào)整，但分段任務(wù)經(jīng)常涉及更宏觀的建造場地更換與建造日期變遷的調(diào)整，因此引入分段任務(wù)場地與日期調(diào)整技術(shù)，該技術(shù)從業(yè)務(wù)角度綜合了分段布局碰撞與位姿調(diào)整技術(shù)的應(yīng)用，以場地—分段任務(wù)層級結(jié)構(gòu)樹為數(shù)據(jù)結(jié)構(gòu)，以分段碰撞檢測算法為交互約束，以可控化的場地—分段—時(shí)間軸雙維度模型為交互界面，實(shí)現(xiàn)包含場地間遷移與建造周期的分段綜合性布局調(diào)整，技術(shù)流程如圖11所示。

（1）分段場地間更換的處理流程

在數(shù)據(jù)層面，分段X從場地A遷移到場地B分為兩部分：第一部分是分段任務(wù)被移出場地A，即場地A節(jié)點(diǎn)包含的分段任務(wù)X被刪除，同時(shí)在人為創(chuàng)建的“未歸屬場地”虛擬節(jié)點(diǎn)下暫時(shí)創(chuàng)建分段任務(wù)X數(shù)據(jù)；第二部分相反，將“未歸屬場地”下的分段任務(wù)X刪除，在場地B節(jié)點(diǎn)下創(chuàng)建分段任務(wù)X。

在交互層面，首先根據(jù)分段碰撞檢測算法判斷分段是否在場地內(nèi)存在干涉，如果無干涉則清除場地A中的分段X模型，創(chuàng)建一個(gè)臨時(shí)的過渡分段模型，用于完成從場地A到場地B的遷入與新位置的布局，然后隨著過渡分段模型完全進(jìn)入場地B的范圍并完成位姿布局定位，在場地B中按照過渡分段模型的位姿布局創(chuàng)建分段模型X，最后則銷毀過渡分段模型，整個(gè)過程兩次同步刷新分段任務(wù)樹數(shù)據(jù)，分別是過渡分段模型創(chuàng)建時(shí)與銷毀時(shí)。

（2）分段建造日期遷移的處理流程

在數(shù)據(jù)層面上，以建造周期延續(xù)前期為依據(jù)，分段X從T1～T2變更為T3～T4，則需保證T1-T2=T3-T4，日期精確到天，則只需對T3或T4中的任意一個(gè)做遷移，則另外一個(gè)可通過等式求得，每次變更時(shí)刷新分段任務(wù)數(shù)據(jù)中的時(shí)間屬性即可，另外分段任務(wù)有一屬性存儲計(jì)劃建造周期，這一數(shù)據(jù)在T1-T2 未知的情況下用于代替等式左邊的天數(shù)值。

在交互層面上，采用一個(gè)分段任務(wù)對應(yīng)多個(gè)分段模型的方式，分段任務(wù)建造周期為幾天，場地上的不同日期內(nèi)就會包含幾個(gè)分段模型，每個(gè)分段模型都有不同的時(shí)間值屬性對應(yīng)本身所代表的日期，同時(shí)也保存統(tǒng)一的分段任務(wù)起止日期，隨著時(shí)間軸的變化而選擇性地顯示，調(diào)整周期可以對任何一天的分段模型進(jìn)行調(diào)整，調(diào)整結(jié)果都會反饋給分段任務(wù)，然后將若干分段模型的時(shí)間值屬性重新設(shè)定，最后刷新場地模型顯示即可。

因?yàn)閳龅剡w移一般會同時(shí)伴隨著日期遷移，所以采用場地模型時(shí)間軸獨(dú)立設(shè)計(jì)的方法，每個(gè)場地模型都有自己獨(dú)立的時(shí)間軸，不同場地可以顯示不同的目標(biāo)日期，從而實(shí)現(xiàn)獨(dú)立處理。然后完成場地更換與日期遷移的同步執(zhí)行，盡管操作同步，但其業(yè)務(wù)處理基于兩個(gè)并行流程，互不干涉，只是對布局干涉的判斷做合并處理：以雙循環(huán)嵌套方式遍歷分段在新建造日期范圍內(nèi)的每一天中與新場地中其他分段的干涉情況，將發(fā)生干涉的分段數(shù)據(jù)集合以列表的形式給予提示，以便后續(xù)的分段位姿微調(diào)來排除干涉。

5 技術(shù)實(shí)現(xiàn)與驗(yàn)證

以上海某造船廠曲面分段生產(chǎn)為背景，基于上述關(guān)鍵技術(shù)，采用.Net平臺下的ASP.Net AJAX框架和Silverlight富客戶端開發(fā)技術(shù)，開發(fā)了“曲面分段建造執(zhí)行系統(tǒng)（CBCES）”，通過實(shí)際測試與使用，驗(yàn)證了本文上述所提各項(xiàng)技術(shù)的有效性。下面按照業(yè)務(wù)應(yīng)用順序，對主要系統(tǒng)界面及操作進(jìn)行說明。

（1）曲面分段空間布局建模

通過對xml格式的結(jié)構(gòu)化數(shù)據(jù)模板文件的編輯，錄入車間、場地、分段的模型數(shù)據(jù)，導(dǎo)入系統(tǒng)完成參數(shù)化建模。如圖12所示。

（2）場地空間布局看板

多場地分段空間布局調(diào)整看板如圖13所示，看板左側(cè)為場地—分段任務(wù)樹，右側(cè)為人機(jī)交互的場地面板，選中下方場地A，則彈出場地控制臺，在控制臺中拖動時(shí)間軸滑塊，將場地日期調(diào)整至某一天T，選中上方場地B的分段z拖動移除該場地，隨后立刻拖入場地A中，這樣便同時(shí)完成了一次場地更換（從B遷移至A）與日期遷移（從原建造日期遷移至以T為開工時(shí)間的建造日期）的操作。此時(shí)左側(cè)分段任務(wù)樹中的分段z圖標(biāo)也會從B節(jié)點(diǎn)下移至A節(jié)點(diǎn)下。

分段任務(wù)多天布局調(diào)整看板如圖14所示，該看板用于展示某個(gè)場地在連續(xù)一段時(shí)間區(qū)間內(nèi)每一天的分段空間布局，并提供分段布局位置的調(diào)整和建造日期的遷移。雙擊點(diǎn)開某一天的場地模型，在彈出子窗口中拖動分段，如果發(fā)生干涉，則分段會變成紅色邊框（如圖14的鼠標(biāo)箭頭所在的半透明分段）提示用戶，另外可以點(diǎn)擊分段的按鈕執(zhí)行移除、微調(diào)、旋轉(zhuǎn)／拖動切換操作。

（3）算法與布局效果驗(yàn)證

根據(jù)船廠提供的160個(gè)分段三維模型，通過參數(shù)化自動建模，全部處理為二維平面投影多邊形模型，將全部曲面分段布局在兩塊場地的兩個(gè)月建造時(shí)間內(nèi)，布局用時(shí)和場地利用率如表5所示。

表5 算法與布局效果驗(yàn)證的實(shí)例數(shù)據(jù)

最終實(shí)現(xiàn)場地利用率達(dá)到80.15%，大于目前普遍的曲面分段布局的60%場地利用率的水平；另外，平均每個(gè)曲面分段所需的布局時(shí)間也達(dá)到21.75s，實(shí)現(xiàn)了高效快速的布局過程管理。

6 結(jié)束語

本文建立了曲面分段空間布局交互技術(shù)方案，該方案綜合了輸入數(shù)據(jù)的結(jié)構(gòu)化解析，在場地和分段顯示模型的基礎(chǔ)上，以碰撞檢測與處理算法為核心，支持了人機(jī)交互位姿以及綜合更換場地、更換日程等調(diào)整。進(jìn)行了參數(shù)注入式曲面分段布局調(diào)整問題的建模，在基于交互調(diào)整過程中的實(shí)時(shí)移動碰撞檢測方面，提出了基于采樣率的實(shí)施干涉檢查算法，形成了基于重心法的平移與旋轉(zhuǎn)處理機(jī)制，實(shí)現(xiàn)了對場地布局和日程計(jì)劃的綜合調(diào)整支持。結(jié)合實(shí)際需求進(jìn)行了系統(tǒng)開發(fā)，并結(jié)合案例進(jìn)行了驗(yàn)證演示。

［1］ZHANG Zhiying，LI Chuan，LI Zhen.Forming and scheduling of virtual flow lines for hull manufacturing in shipbuilding［J］.Industrial Engine1ering Journal，2010，13（1）：58-63（in Chinese）.［張志英，李 川，李 珍.面向船體曲面分段建造的虛擬流水線生產(chǎn)調(diào)度［J］.工業(yè)工程，2010，13（1）：58-63.］

［2］CAO Jiangxin.Study of production management system for shipbuilding based on the ERP［D］.Dalian：Dalian University of Technology，2008（in Chinese）.［曹絳欣.基于ERP的船舶建造生產(chǎn)管理系統(tǒng)研究［D］.大連：大連理工大學(xué)，2008.］

［3］LUO Dai，LIU Cungen，ZHANG Dian.A shipbuilding simulation system based on workshop units［J］.Shipbuilding of China，2011，52（3）：204-215（in Chinese）.［羅 岱，柳存根，張 滇.基于車間單元的船舶建造系統(tǒng)仿真［J］.中國造船，2011，52（3）：204-215.］［4］ZHAN Dechen，YU Xiaoguang，NIE Lanshun，et al.Ship-buiding layered production plan system［J］.Computer Intergrated Manufacturing Systems，2012，18（3）：498-506（in Chinese）.［戰(zhàn)德臣，喻小光，聶蘭順，等.船舶建造分層生產(chǎn)計(jì)劃體系［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（3）：498-506.］

［5］ZHANG Guangfa，LIU Yujun，JI Zhuoshang.Simluation and optimization of ship block-building planning［J］.Computer Intergrated Manufacturing Systems，2011，17（12）：2644-2651（in Chinese）.［張光發(fā)，劉玉君，紀(jì)卓尚.船舶分段建造計(jì)劃仿真與優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（12）：2644-2651.］

［6］CHIN F，WANG C A.Optimal algorithms for the intersection and the minimum distance problems between planar polygons［J］.IEEE Transactions on Computers，1983，32（12）：1203-1207.

［7］QIN Zhongping，ZHANG Huanguo.An optimal algorithm of determining the touch parts between tow colliding convex polygons［J］.Chinese Journal of Computers，1992，14（3）：171-177（in Chineses）.［覃中平，張煥國.確定凸多邊形平移時(shí)最初碰撞部位的最優(yōu)算法［J］.計(jì)算機(jī)學(xué)報(bào)，1992，14（3）：171-177.］

［8］WANG Jiaye.An optimal algorithm of finding first contact between translating polygons［J］.Chinese Journal of Computers，1992，14（3）：583-588（in Chinese）.［汪嘉業(yè).平面上簡單多邊形平移時(shí)確定碰撞部位的最優(yōu)算法［J］.計(jì)算機(jī)學(xué)報(bào)，1992，14（3）：583-588.］

［9］HE Liangli，WEI Fayuan，WANG Fengjun.Human-computer interaction in virtual layout／assembly environment［J］.Journal of Machine Design，2010，27（5）：86-89（in Chinese）.［何良莉，魏發(fā)遠(yuǎn)，王峰軍.虛擬布局／裝配環(huán)境下的人機(jī)交互技術(shù)研究［J］.機(jī)械設(shè)計(jì)，2010，27（5）：86-89.］

［10］CHEN Ning，LIU Wei，ZHANG Dan.Research on visual simulation method of ship construction scheduling［J］.Marine Energy Saving，2011（1）：21-26（in Chinese）.［陳 寧，劉 煒，張 丹.船舶建造計(jì)劃可視化仿真方法的研究［J］.交通與環(huán)保，2011（1）：21-26.］