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

有效

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

本發明提供的一種面向3D場景的導航網格地圖表示方法，抽取3D場景中的可行走層次平面，得到可行走層次平面集合，將孤立的平面以及不可行走的平面去除；抽象可行走層次平面內尋路角色的初始不可通過區域，能夠實現將3D場景中的模型抽象為不可通過區域；對初始不可通過區域中的多邊形進行區域合并得到最終不可通過區域；合并初始不可通過區域中相交的區域，形成最終不可通過區域。對層次平面內的約束進行約束Delaunay三角形剖分，形成一個三角形集合；所有可行走層次平面內的三角形集合共同構成了最終的導航網格。最終的導航網格能夠將障礙物和可行走區域充分分離。本發明是應用在數字媒體技術領域中，有效地保證了障礙物與可行走區域的分離。

技術領域

本發明屬于數字媒體技術領域，特別涉及一種面向3D場景的導航網格地圖表示方法。

背景技術

3D大型場景給用戶帶來的視覺沖擊和體驗是2D場景難以比擬的，隨著近幾年顯卡等硬件的不斷升級，越來越多的大型3D場景游戲不斷涌現，與此同時，人工智能技術大量應用于游戲中，對提高游戲逼真性起著至關重要的作用，而智能尋路技術又是游戲人工智能的重要組成部分。然而，傳統的尋路技術無法適應3D場景的復雜性，迫切需要能夠在3D場景下高效完成智能尋路的相關技術。

3D場景是由一系列的美術模型組合而成，模型之間沒有特定關系，因而需要將場景用一種數據結構來抽象表示其相互之間的關系。搜索技術大都是基于圖的搜索，因而可以將場景抽象成圖結構，將一些模型抽象成圖中的結點，這樣便于之后的路徑搜索，場景地圖的表示方法是智能尋路技術中必不可少的一步。

目前的傳統的場景表示方法，分為柵格法、四叉樹法、八叉樹法、可見點法以及導航網格法。柵格法是最簡便的表示方法，但是僅能夠適應早期的二維場景，不能適應三維場景。四叉樹法是早期基于二維場景下的柵格法的改進，同樣不能適應三維場景。八叉樹法則是基于三維場景下的四叉樹法的推廣，該表示方法符合三維模型的空間結構，但是這種地圖表示方案對于復雜的三維場景會消耗較多的存儲空間。可見點法需要在場景中人工設置經過的路徑點，因為需要較多的人工操作，所以此方法適用于較小的室內場景，在大型的3D場景很難應用此方法。導航網格表示方法與可見點法的不同點在于，導航網格可以鋪滿整個場景的可行走區域，并且僅需要很少量的人工操作，行走路線更加逼真，增加游戲體驗，所以能夠適應3D場景。導航網格的表示方法采用凸多邊形集合，可以是三角形，也可以是六邊形等，但是目前的研究最多的就是三角形集合，因為三角形是邊數最少的凸多邊形，劃分粒度較小，能夠完全鋪滿整個行走區域，降低不規則凸多邊形的個數，但是導航網格表示也有一些缺點，一是需要消耗大量內存存儲結點。二是難以適應動態場景。可見上述的傳統的場景地圖表示方法僅僅能夠適應2D場景以及早期的簡單3D場景，不能適應大型3D場景。

發明內容

針對現有技術存在的問題，本發明提供一種面向3D場景的導航網格地圖表示方法。

本發明的技術方案如下：

一種面向3D場景的導航網格地圖表示方法，包括：

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

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

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

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

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

所述步驟1，包括：

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