一種三維虛擬場景快速路徑規劃的橡皮筋算法的製作方法

2023-06-12 03:41:46 1

專利名稱：一種三維虛擬場景快速路徑規劃的橡皮筋算法的製作方法
技術領域：
本發明屬於虛擬實境技術和計算機動畫領域，具體涉及一種三維虛擬場景快速路徑規劃的橡皮筋算法。
龍魷
三維虛擬場景是虛擬實境、計算機動畫等領域的重要組成部分，是在計算機上對現實世界的重建。在 三維虛擬場景中，通過漫遊的方式可以使用戶從不同的角度觀察和研究由三維數據建立的三維形體，以便 獲取更多的有用信息[11。
在虛擬場景中漫遊的方式主要有兩種 一種是交互式漫遊，這種漫遊方式比較靈活，完全由用戶操作 滑鼠或者鍵盤等其他的交互設備，按照自己的意圖來控制漫遊位置和視點方向，但是當用戶處於一個不熟 悉的虛擬環境時，容易迷失方向；另外一種方式是按路徑漫遊，用戶按設定好的路線，在虛擬場景中漫遊。
路線的設定，可以是由製作者預先錄製並保存好的，這種方法實現簡單但不靈活，在場景複雜，用戶目的 不能預知的情況下，很難完成任務。
路徑規劃問題又稱避障路徑規劃，是指在具有障礙物的環境中，按照某個評價標準(如最短路徑長度)， 規劃一條從起點到達目標結點的無障礙路徑[2]。目前，三維場景漫遊中的自動生成漫遊路徑主要是參考機 器人學的路徑規划算法和地理信息系統中的路徑搜索方法。
路徑規劃問題是機器人學中的一個重要課題。自從20世紀40年代後期，美國研製出世界上第一臺"主 從式"機械手至今，機器人的研製和應用在歐美和日本快速發展起來，機器人的路徑規劃及相關算法的形 容也相應的興起。為了解決路徑規劃問題，人們已探索出很多有效的求解方法，這些方法包括幾何法、單 元分解法、人工勢場法和數學分析法及衍生出來的其它方法。由於機器人研究領域希望能藉助於各種傳感 器，對部分未知或完全未知的環境進行探索，利用獲得的信息進行行進路線及方面的決策，所以其所關注 的路徑規劃問題往往是以未知或部分未知環境作為前提的[3—71。
路徑規劃問題也是地理信息系統(GIS)的一個研究熱點，研究最短路徑問題通常將它們抽象為圖論 意義下的網絡問題，問題的核心就變成了網絡圖中的最短路徑問題。這種方法比較適合大區域和固定道路 的情況，對於3D虛擬場景中的大塊無障礙區域，這種方法反而將問題複雜化了。
和機器人學、GIS的路徑規劃問題明顯不同的是，計算機學科中的虛擬實境、動畫、遊戲、建築群漫 遊、駕駛訓練等面對的路徑規劃問題求解初始條件要簡單得多。由於繪製的需要，場景中所有物體的信息 對系統來說都是已知的，如靜止物體的大小、位置以及運動物體的初始位置、運動速度、作用於其上的外 力等。所以，3D場景中的路徑規劃問題的主要任務是，在己知完全的環境信息條件下，獲得一條從起始點 到目標點的最優(次優)的避障路徑。參考文獻 Jansen-0smann, Petra. Using desktop virtual environments to investigate the role of landmarks [J]. Computers in Human Behavior (S0747-5632) ， 2002, 18(4): 427-436. Lato油e J C. Robot Motion Planning[M]. Boston: Kluwer Academic Publishers, 1991: 143-176. Schwartz J T, Shair M Shair. A Survey of Motion Planning and Related Geometric Algorithms [J]. Artificial Intelligence (S0004-3702) ， 1998, 37(1): 55_67. Brooks R A, Lazano-Perez T. A Subdivision Algorithm in Configuration Space for Find Path with Rotation [C]〃 Proc. Of the 8th Int. Conf on Artificial Intelligence. Karlsruhe, FRG, 1983: 366-380. Hwang Y K， Ahuja N. A Potential field approach to path planning [J]. IEEE Trans, on Robotics and Automation (S1070-9932) ， 1992， 8(1): 23-32.馬兆青.基於柵格方法的移動機器人實時導航避障[J].機器人，19恥，18(6): 344-348.袁曾任，高明.在動態環境中移動機器人導航和避碰的一種新方法[J].機器人，2000, 22(2): 81-88.

發明內容
本發明的目的在於提出一種實現在三維虛擬場景中自動漫遊的快速路徑規划算法，稱為橡皮筋算法。 該算法可用於複雜形體和運動物體的實時避障問題，具有穩定性好、求解實際問題效率高的特點。
本發明的技術方案，三維虛擬場景快速路徑規劃的橡皮筋算法，包括如下步驟
1) 對場景投影圖矩陣中的障礙物進行處理，獲得其繞障包圍路線；
2) 生成基本路徑，並將其存放於基本路徑鍊表中；
3) 採用橡皮筋算法進行優化處理，獲得從起始點到結束點的最優路徑。
在現實世界中行走時，如果不知道確定路線時，運動者會朝著目的地的方向走，如圖la中的S-〉T; 如果中途碰到障礙物，就試圖繞過障礙物，再重新朝向目的地的方向行走，如圖所示S-〉A-〉B->C-〉D-〉T， 其中圓點S表示出發點，圓點T表示目的地。實際上，如果視覺上沒有障礙，運動者會選擇較近的直切障 礙物邊沿的行走路線，如圖lb所示S-〉B-〉C-〉T。以上所得形狀，就像在出發點和目的地之間拉了根橡皮 筋，由於障礙物的存在，橡皮筋不能橫穿過去，所以沿障礙物邊沿拉伸，而正是因為橡皮筋具有的彈性， 使得路徑趨於最短。根據這種思路，提出了自動漫遊路徑生成的橡皮筋算法。
本發明的有益效果在於由於自動漫遊路徑生成的橡皮筋算法是對場景投影圖處理的，所以適應性強； 生成避障路徑是通過對場景投影圖矩陣的搜索實現的，充分利用了障礙物投影圖中柵格之間的相鄰關係， 並通過直接讀取預先處理生成的繞障包圍路線來求得局部避障路徑，因而極大地提高了算法的效率。 一般而言，因為該算法是通過對場景投影圖矩陣的搜索實現的，在障礙物小而多的場景中效率優於其他算法。
W,月
圖la基本路徑 圖lb優化後的路徑 圖2三維虛擬場景投影圖 圖3顏色值填充後的場景投影圖 圖4繞障包圍路線示意圖 圖5基本路徑生成示意圖 圖6複雜障礙物處理示意圖 圖7橡皮筋算法示意圖
具體實施例方式
下面結合說明書附圖
給出本發明的具體實施方式
。
1. 基於柵格的環境信息表示
在三維場景建模時，為了保證建模的精確，常常要用到總體建築規劃圖。三維虛擬場景投影圖就是在 此基礎上處理而成的。以規則矩形柵格為組織形式，將場景中不能穿越的障礙物投影到2D平面，圖2為 一個三維場景的投影平面圖，範圍為1024X800，左上角為坐標原點，沿水平方向向右為X軸遞增，沿豎 直方向向下為Y軸遞增。
對於靜態環境，這種離散化只需執行一次。
2. 障礙物的表示
為了區分三維場景的不同障礙物，將圖中的各障礙物用不同的顏色值填充，如圖3所示。該投影圖在 後續的算法中用一個數組矩陣表示，稱為場景投影圖矩陣(其中u為矩陣中的行數，v為矩陣中的列數)。
,、f。鵬導點
,"叫c障歐
定義l:障礙結點和非障礙結點。
場景投影圖矩陣Map(m, n)中，若Map(u, v)=0，表示該點對應的三維場景中沒有障礙物，該點為非 障礙結點；否則為障礙結點，Map(u， v)中存儲的值對應三維場景中的一個障礙物。
3. 繞障包圍路線生成
定義2:繞障包圍路線和邊界點。
繞障包圍路線由各障礙物的邊界點以循環鍊表的形式逐點存儲而成的繞障包圍圈，邊界點是指有且至少有一個鄰近單元是表示障礙物的結點，如圖4中的外圍環。
繞障包圍路線可以通過對場景投影圖矩陣進行掃描獲得，完成後按顏色值將繞障包圍路線以循環連結 表的形式存放。這樣，如果有一段預定路線穿越障礙物時，可以通過掃描得到的顏色值找到對應的繞障包 圍路線，再由穿越障礙區域的進出兩個點，在循環連結表中求得兩條繞過障礙物的初始路徑，選擇其中的 一條，作為繞過該障礙物的初始路徑。
4. 基本路徑生成
基本路徑生成算法的主要任務是，在場景投影圖矩陣中找到一條基本的繞障路徑，如圖5所示中的 S-〉A-〉B->C->D-〉T，以便後續優化處理。
基本思想是在出發點到目的地之間拉一條直線，沿該直線從出發點開始，逐點讀取場景投影圖矩陣 中對應點的值，如果是障礙物點，找到穿越該障礙物的兩個邊界點，按顏色值從其循環連結表中讀取繞過 該障礙物的局部路徑，加入到路徑鍊表；如果是非障礙物點，則不作處理，讀取下一個點繼續；如果是目 的地點，則算法結束。
算法如下
步驟l:讀取起始點S、結束點T，把起始點S添加到初始為空的路徑鍊表PL末尾。
步驟2:沿直線S-T在場景投影圖矩陣中讀取下一個結點，如果不是結束點T,轉步驟3;否則轉步驟5。
步驟3:檢査該結點值，如果為0(非障礙點)則轉步驟2。
步驟4:如果是障礙點，找到穿越該障礙物的兩個邊界點(如圖中的A、 D)，根據其顏色值從其循環鏈 接表中讀取繞過該障礙物的局部路徑(如圖中的ABCD，實際上組成局部路徑的點是場景投影圖矩陣中連接 ABCD的各像素點)，加入到路徑鍊表PL。
步驟5:把結束點T添加到路徑鍊表PL末尾，算法結束。
需要注意的是，要依據場景投影圖中，表示障礙物的投影圖內填充的顏色值而不是邊界的顏色來求該 障礙物的繞障包圍線路。釆用這種處理的原因是，障礙物通過離散化處理，在場景投影圖矩陣中表示出來。 在表示複雜形體時，可能會出現如圖6所示的情況，當漫遊者從S向T行走時，在複雜形體的斜邊處(鋸 齒狀)不會對邊界進行檢測，而是直接進入到表示障礙物的色塊內部。
5.橡皮筋算法
通過上面算法生成的基本路徑可以達到避開障礙物的目的，但並不是我們所期望的優化路徑，而且部 分路徑鍊表PL中的結點是按場景投影圖逐像素點生成的，應該進行簡化。橡皮筋算法就是實現這個目的 的。
基本思想是在已經生成的基本路徑SABCDT中，ABCD是逐像素點組成的局部路徑，將SA沿A-〉B拉伸，當碰到另一障礙物點(圖7中的F點)，SF進入路徑鍊表PL,從F點開始，FE沿E-〉B拉伸，如此處 理，直到T點，算法結束。
算法如下
步驟l:讀取路徑鍊表PL的前兩個結點，前結點front、中間點mid，如果mid為結束點end，算法 結束，轉步驟6;
步驟2:讀取路徑鍊表PL的下一個結點，如果該點為結束點end，算法結束，轉步驟6;否則將該結 點賦給back;
步驟3:如果mid位於front和back的連線上，則在路徑鍊表PL中刪除mid，把back的值賦給mid, 轉步驟2;
步驟4:如果mid沒有位於front和back的連線上，且front和back的連線中沒有障礙物，則在路 徑鍊表PL中刪除mid,把back的值賦給mid，轉步驟2;
步驟5:如果mid沒有位於front和back的連線上，且front和back的連線中有障礙物，則將該障 礙物對應的邊界點加入路徑鍊表PL的front和mid之間，並將該邊界點的值賦給front,轉步驟2;
步驟6:結束。
至此，實現了自動漫遊路徑生成的橡皮筋算法。
權利要求
1. 一種三維虛擬場景快速路徑規劃的橡皮筋算法，包括以下步驟1)對場景投影圖矩陣中的障礙物進行處理，獲得其繞障包圍路線；2)生成基本路徑，並將其存放於基本路徑鍊表中；3)採用橡皮筋算法進行優化處理，獲得從起始點到結束點的最優路徑。
2. 根據權利要求1所述的三維虛擬場景快速路徑規劃的橡皮筋算法，其特徵在於橡皮筋算法的基礎是 繞障包圍線路；繞障包圍線路是在場景投影圖矩陣中進行掃描獲得；場景投影矩陣中，各障礙物需要 用不同的顏色填充。
全文摘要
本發明屬於虛擬實境技術和計算機動畫領域，具體涉及一種三維虛擬場景快速路徑規劃的橡皮筋算法。本發明首先建立基於柵格的環境信息表示，通過場景中障礙物在場景投影圖矩陣中的不同顏色值表示，求得繞障包圍路線，在此基礎上來求得局部避障路徑，生成基本路徑後用橡皮筋算法進行優化處理，求得從起始點到結束點的一條最優路徑。該算法可用於複雜形體和運動物體的實時避障，具有穩定性好、求解實際問題效率高的特點。
文檔編號G06T15/70GK101430797SQ200710094209
公開日2009年5月13日 申請日期2007年11月7日 優先權日2007年11月7日
發明者棟 王, 勇 陳, 戈 陳 申請人:上海蘭基斯軟體有限公司