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

有效

• 申請?zhí)枺?/td>: 200910080030.7
• 申請日: 2009-03-17
• 公開（公告）號: CN101504776A
• 公開（公告）日: 2009-08-12
• 發(fā)明（設(shè)計）人: 董超
• 申請（專利權(quán)）人: 北京像素軟件科技股份有限公司
• 主分類號: G06T15/70
• 分類號: G06T15/70
• 代理公司: 北京德琦知識產(chǎn)權(quán)代理有限公司
• 代理人: 謝安昆;宋志強

1.一種3D場景的尋路方法，其特征在于，該方法包括：

根據(jù)預(yù)設(shè)的類型標(biāo)識識別路徑節(jié)點的區(qū)域類型，通過查詢預(yù)先建立的尋路數(shù)據(jù)得到與所述路徑節(jié)點的區(qū)域類型相同的同類鄰區(qū)信息；

根據(jù)預(yù)設(shè)的開關(guān)標(biāo)識識別路徑節(jié)點是否含有與自身的區(qū)域類型不同的異類鄰區(qū)，若有，則查找預(yù)先保存的包含與所述路徑節(jié)點的區(qū)域類型不同的異類鄰區(qū)信息的開關(guān)數(shù)據(jù)，得到所述異類鄰區(qū)信息；

根據(jù)所述同類鄰區(qū)信息確定同類鄰區(qū)標(biāo)識；根據(jù)所述異類鄰區(qū)信息確定異類鄰區(qū)標(biāo)識；根據(jù)所述同類鄰區(qū)標(biāo)識和異類鄰區(qū)標(biāo)識使用路徑搜索算法進行路徑搜索。

2.如權(quán)利要求1所述的3D場景的尋路方法，其特征在于，所述預(yù)設(shè)的類型標(biāo)識占用所述路徑節(jié)點的預(yù)設(shè)的唯一標(biāo)識中任意一個數(shù)據(jù)位。

3.如權(quán)利要求2所述的3D場景的尋路方法，其特征在于，所述預(yù)設(shè)的開關(guān)標(biāo)識占用所述路徑節(jié)點的預(yù)設(shè)的唯一標(biāo)識中與所述類型標(biāo)識不同的任意一個數(shù)據(jù)位。

4.如權(quán)利要求1、2或3所述的3D場景的尋路方法，其特征在于，所述同類鄰區(qū)信息包括：區(qū)域固有屬性信息。

5.如權(quán)利要求1、2或3所述的3D場景的尋路方法，其特征在于，所述異類鄰區(qū)信息包括：區(qū)域之間的連接關(guān)系。

6.一種3D場景的尋路裝置，其特征在于，該裝置包括：

區(qū)域信息模塊，根據(jù)預(yù)設(shè)的類型標(biāo)識識別路徑節(jié)點的區(qū)域類型，通過查詢預(yù)先建立的尋路數(shù)據(jù)得到與所述路徑節(jié)點的區(qū)域類型相同的同類鄰區(qū)信息；

根據(jù)預(yù)設(shè)的開關(guān)標(biāo)識識別路徑節(jié)點是否含有與自身的區(qū)域類型不同的異類鄰區(qū)，若有，則查找預(yù)先保存的包含與所述路徑節(jié)點的區(qū)域類型不同的異類鄰區(qū)信息的開關(guān)數(shù)據(jù)，得到所述異類鄰區(qū)信息；

路徑搜索模塊，與所述區(qū)域信息模塊相連，用于根據(jù)所述區(qū)域信息模塊提?供的所述同類鄰區(qū)信息確定同類鄰區(qū)標(biāo)識；根據(jù)所述異類鄰區(qū)信息確定異類鄰區(qū)標(biāo)識；根據(jù)所述同類鄰區(qū)標(biāo)識和異類鄰區(qū)標(biāo)識使用路徑搜索算法進行路徑搜索。

7.如權(quán)利要求6所述的3D場景的尋路裝置，其特征在于，所述區(qū)域信息模塊包括：

格子數(shù)據(jù)管理單元，用于管理格子方式尋路數(shù)據(jù)的鄰區(qū)信息；

導(dǎo)航網(wǎng)格管理單元，用于管理導(dǎo)航網(wǎng)格方式尋路數(shù)據(jù)的鄰區(qū)信息；

開關(guān)數(shù)據(jù)管理單元，用于管理包含與所述路徑節(jié)點的區(qū)域類型不同的鄰區(qū)信息的開關(guān)數(shù)據(jù)；

尋路數(shù)據(jù)管理單元，與所述格子數(shù)據(jù)管理單元、導(dǎo)航網(wǎng)格管理單元及開關(guān)數(shù)據(jù)管理單元分別相連，用于根據(jù)預(yù)設(shè)的類型標(biāo)識識別路徑節(jié)點的區(qū)域類型；通過查詢所述格子數(shù)據(jù)管理單元或?qū)Ш骄W(wǎng)格管理單元，得到與所述路徑節(jié)點的區(qū)域類型相同的同類鄰區(qū)信息；

根據(jù)預(yù)設(shè)的開關(guān)標(biāo)識識別路徑節(jié)點是否含有與自身的區(qū)域類型不同的鄰區(qū)，若有，則查詢所述開關(guān)數(shù)據(jù)管理單元管理的開關(guān)數(shù)據(jù)，得到與所述路徑節(jié)點的區(qū)域類型不同的異類鄰區(qū)信息。

8.如權(quán)利要求7所述的3D場景的尋路裝置，其特征在于，所述尋路數(shù)據(jù)管理單元包括：

標(biāo)識識別子單元，用于識別路徑節(jié)點的類型標(biāo)識和開關(guān)標(biāo)識；

格子搜索子單元，與所述標(biāo)識識別子單元相連，用于在所述標(biāo)識識別子單元識別出路徑節(jié)點的類型標(biāo)識為格子時，搜索所述格子數(shù)據(jù)管理單元，得到路徑節(jié)點的同類鄰區(qū)信息；

導(dǎo)航網(wǎng)格搜索子單元，與所述標(biāo)識識別子單元相連，用于在所述標(biāo)識識別子單元識別出路徑節(jié)點的類型標(biāo)識為導(dǎo)航網(wǎng)格時，搜索所述導(dǎo)航網(wǎng)格管理單元，得到路徑節(jié)點的同類鄰區(qū)信息；

開關(guān)搜索子單元，與所述標(biāo)識識別子單元相連，用于在所述標(biāo)識識別子單元識別出路徑節(jié)點的開關(guān)標(biāo)識為交換區(qū)域時，搜索所述開關(guān)數(shù)據(jù)管理單元，得到路?徑節(jié)點的異類鄰區(qū)信息。

9.如權(quán)利要求6～8中任一項權(quán)利要求所述的3D場景的尋路裝置，其特征在于，所述路徑搜索模塊包括：

接口單元，用于從所述區(qū)域信息模塊獲取所述同類鄰區(qū)信息和異類鄰區(qū)信息；根據(jù)同類鄰區(qū)信息確定同類鄰區(qū)標(biāo)識，根據(jù)異類鄰區(qū)信息確定異類鄰區(qū)標(biāo)識；

搜索單元，與所述接口單元相連，用于根據(jù)所述同類鄰區(qū)標(biāo)識和異類鄰區(qū)標(biāo)識進行路徑搜索。?