[發明專利]一種3D場景的尋路方法和尋路裝置

有效

• 申請號: 200910080030.7
• 申請日: 2009-03-17
• 公開（公告）號: CN101504776A
• 公開（公告）日: 2009-08-12
• 發明（設計）人: 董超
• 申請（專利權）人: 北京像素軟件科技股份有限公司
• 主分類號: G06T15/70
• 分類號: G06T15/70
• 代理公司: 北京德琦知識產權代理有限公司
• 代理人: 謝安昆;宋志強

技術領域

本發明涉及三維(3D)技術領域，特別涉及一種3D場景的尋路方法和尋路裝置。?

背景技術

尋路是實現在3D場景中移動的一個前提，尋路實際上是在尋路數據中的可走區域中搜索從某一點到另一點的路徑，尋路算法很多，例如廣度優先搜索(BFS，Breadth?First?Search)，深度優先搜索(DFS，Depth?First?Search)，啟發式搜索算法等等。不管什么算法，其基礎都是尋路數據，任何的尋路算法都是應用于尋路數據之上的。?

尋路數據按照其數據形式分為兩種，一種是以平面正方形格子做為區域單位，以下簡稱格子方式，另一種是以空間三角形作為區域單位，是3D數據，以下稱為導航網格方式。每一個區域我們稱為一個路徑節點，尋路算法依靠節點之間的關系，搜索起始節點的相鄰節點，再搜索相鄰節點的相鄰節點，直至搜索到終止節點，從而得到從某一個節點到另一個節點的完整路徑。?

其中，格子方式是將場景地形切分成若干個相同大小的平面方格，每個方格代表一個區域，可走的區域和不可走的區域可用不同標記區分開來，由于方格區域是規則的，因此不同區域之間的相鄰關系可以通過區域編號隱含地表示出來。在路徑搜索的時候，根據區域編號就可以間接得到該區域的鄰區信息。格子方式編輯簡單，對于一般的場景編輯器，無需單獨制作尋路數據，在編輯場景的時候就可以隱含的產生尋路數據，常用于二維場景中。圖1為格子方式的尋路數據示意圖，如圖1所示，有斜線覆蓋的格子為不可走區域，其它格子為可走區域。?

導航網格方式是由美工根據場景地形制作的，由三角形組成具有3D空間坐標和層次關系的3D尋路數據，適合于3D空間的路徑搜索。由于三角形區域不規則，其區域之間的相鄰關系可以通過三角形的頂點編號，根據擁有同一邊，即兩個相同編號頂點的三角形必為相鄰三角形的原理，隱含地得到。在路徑搜索時，根據頂點編號就可以間接得到該區域的鄰區信息。雖然導航網格的靈活性很高，可以制作各種各樣的可走區域，但其制作非常繁瑣，需要和場景地形嚴格對應。圖2為導航網格方式的尋路數據示意圖，如圖2所示，只有三角形組成的區域才是可走區域。?

目前的3D場景規模越來越大，并且要求無縫連接，即整個3D世界所有可達到的地方都在一個場景中，不需要不停的在多個場景中來回切換。對于大規模的3D場景來說，雖然導航網格方式的靈活性很高，具有天然的空間層次感，具備路徑準確、真實感強的優點，但是全場景都采用導航網格方式生成尋路數據的工作量非常巨大，制作非常復雜，后期維護成本很高，而且對于導航網格來說，由于可走區域不規則，且形態各異，數量龐大，其進行路徑搜索所需的計算量也相當大；同時，由于制作導航網格的復雜性，不容易修改，使得場景地形以及場景中的各種元素、建筑的布置也要事先考慮到導航網格的制作，因此也會使3D場景的設計受到一定的限制。而采用格子的方式來生成尋路數據雖然簡單方便，修改容易，但由于格子是2維的平面，沒有層次感，不易模擬出在3D空間中移動的效果，尤其在室內等復雜3D場景中，更加難以表現出真實的移動路徑，使得整個3D場景的真實感大打折扣。?

兩種尋路數據類型各有優缺點，但是目前還沒有一個在3D場景中將兩種尋路數據混用的實現方法。?

發明內容

本發明實施例提供一種3D場景的尋路數據管理方法，可以實現在3D場景中混用格子類型的尋路數據和導航網格類型尋路數據。?

本發明實施例提供一種3D場景的尋路數據管理裝置，可以實現在3D場景中混用格子類型的尋路數據和導航網格類型尋路數據。?

為達到上述目的，本發明的技術方案具體是這樣實現的：?

一種3D場景的尋路方法，該方法包括：?

根據預設的類型標識識別路徑節點的區域類型，通過查詢預先建立的尋路數據得到與所述路徑節點的區域類型相同的同類鄰區信息；?

根據預設的開關標識識別路徑節點是否含有與自身的區域類型不同的異類鄰區，若有，則查找預先保存的包含與所述路徑節點的區域類型不同的異類鄰區信息的開關數據，得到所述異類鄰區信息；?

根據所述同類鄰區信息確定同類鄰區標識；根據所述異類鄰區信息確定異類鄰區標識；根據所述同類鄰區標識和異類鄰區標識使用路徑搜索算法進行路徑搜索。?

一種3D場景的尋路裝置，該裝置包括：?

區域信息模塊，根據預設的類型標識識別路徑節點的區域類型，通過查詢預先建立的尋路數據得到與所述路徑節點的區域類型相同的同類鄰區信息；?