[發明專利]一種面向3D場景的導航網格地圖表示方法

有效

• 申請號: 201611143856.X
• 申請日: 2016-12-13
• 公開（公告）號: CN106600697B
• 公開（公告）日: 2019-10-11
• 發明（設計）人: 高天寒;劉文成
• 申請（專利權）人: 東北大學
• 主分類號: G06T17/30
• 分類號: G06T17/30
• 代理公司: 沈陽東大知識產權代理有限公司 21109
• 代理人: 胡曉男

1.一種面向3D場景的導航網格地圖表示方法，其特征在于，包括：

步驟1、抽取3D場景中的可行走層次平面，得到可行走層次平面集合；

步驟2、抽象可行走層次平面內尋路角色的初始不可通過區域；

步驟3、對初始不可通過區域中相交區域進行區域合并得到最終不可通過區域；

步驟4、對層次平面內的約束進行約束Delaunay三角剖分；

步驟5、層次平面集合內所有層次平面的三角形構成了最終的3D場景導航網格；

所述步驟3中采用Weiler-Atherton多邊形裁剪算法對初始不可通過區域中的多邊形進行區域合并得到最終不可通過區域，包括：

步驟3.1、將初始不可通過區域中的多邊形的頂點順時針處理，保證相鄰頂點的連線為多邊形的邊；

步驟3.2、從初始不可通過區域中的多邊形P1中的任一不在多邊形P2內的頂點A出發，沿著多邊形P1的頂點A順時針方向檢測多邊形P1每一條邊：如果頂點A與下一頂點B所構成的邊是與多邊形P2不相交的，則頂點B作為合并后的區域中一個頂點；如果頂點B與下一頂點C所構成的邊是與多邊形P2相交的，則交點V1為合并后的區域中一個頂點；然后順時針方向繼續檢測多邊形P2的約束邊，直至返回到多邊形P1中的頂點A，找到的所有合并后的區域中的頂點，依次連接形成最終不可通過區域。

2.根據權利要求1所述的方法，其特征在于，所述步驟1，包括：

步驟1.1、將3D場景中Y軸為0的層次平面F₀作為初始可行走層次平面，將層次平面F₀添加到可行走層次平面集合F中，接著執行步驟1.2；

步驟1.2、選擇可行走層次平面集合F中第一個未遍歷的層次平面F_i，循環遍歷與層次平面F_i相連的未加入層次平面集合F的層次平面：若存在滿足距離層次平面F_i的高度小于尋路角色能夠跨過的最大高度H或者坡度β小于尋路角色能夠行走的最大坡度α的層次平面F_j，并且層次平面F_j的寬度和長度均大于2R時，層次平面F_j為可行走層次平面，初始化層次平面F_j的邊界，并將可行走層次平面F_j添加到可行走層次平面集合F中，接著執行步驟1.3；R為尋路角色能夠通過的最小狹窄區域的寬度；

步驟1.3、不斷循環執行步驟1.2，直至所有層次平面被遍歷，遍歷結束后，執行步驟1.4；

步驟1.4、輸出可行走層次平面集合F={F₀，F₁，...，F_i}。

3.根據權利要求1所述的方法，其特征在于，所述步驟2，包括：

步驟2.1、抽象出可行走層次平面內的靜態障礙物不可通過區域：將3D場景中靜態障礙物模型與可行走層次平面進行交運算得到多個交點，這些交點組成的閉合多邊形區域即是障礙物不可通過區域；

步驟2.2、抽象出可行走層次平面內的低門洞不可通過區域：可行走層次平面與靜態障礙物模型相交得到多個交點，再將層次平面向上平移一個閾值H得到新的層次平面，將新的層次平面與當前靜態障礙物模型的交點向平移前的層次平面投影得到投影點，平移前的層次平面與靜態障礙物模型得到的交點與所述投影點組成的閉合多邊形區域即低門洞不可通過區域；

步驟2.3、抽象出可行走層次平面內的狹窄不可通過區域：通過作垂線計算兩個不可通過區域中的一個不可通過區域的每個頂點到另一個不可通過區域的各邊的距離，當距離的最小值小于尋路角色能夠通過的最小狹窄區域的寬度R時，則此時這兩個不可通過區域之間的兩個最短距離對應的垂線與兩條邊組成的閉合多邊形區域作為狹窄不可通過區域；

步驟2.4、可行走層次平面內的靜態障礙物不可通過區域、低門洞不可通過區域、狹窄不可通過區域共同構成了初始不可通過區域。