外文原文及譯文--3d游戲開發(fā)技術研究與實現--游戲界面、圖形渲染、網絡功能

1、<p>　　畢業(yè)設計（論文）外文原文及譯文</p><p>　　題目： 3D游戲開發(fā)技術研究與實現--游戲界面、圖形渲染、網絡功能 </p><p><b>　　一、外文原文</b></p><p>　　Collision detection technology and artificial intelligent

2、 technology could be applied in the development of game, as well as the areas of education, virtual reality, historic preservation, geo-information system, scientific research, entertainment and business. So, the reinfor

3、cing for the research on 3D game technology has great practical significance. And the successful research and development of collision detection technology and artificial intelligent technology that are suitable for 3D g

4、ame</p><p>　　COLLISION DETECTION ALGORITHM</p><p>　　The BVH (bounding volume hierarchy) in collision detection algorithm is one of the most widely used collision detection methods. The crossing

5、test among BBB is simple, but the compactness of BBB collision detection algorithm is bad. This article makes improvement for bounding volume’s compactness and detection method of AABB collision detection algorithm.</

6、p><p>　　Improve the idea: the core of collision detection algorithm is real time and precision. Some game could sacrifice some precision to get real time. The system will adopt collision detection algorithm bas

7、ed on AABB, and improve the problem of bad compactness and large calculation amount existed in AABB collision detection algorithm to certain extent, with the purpose of making the improved collision detection algorithm s

8、imple, speedy and precise. Improvement idea mainly includes the following aspe</p><p>　　BSP decomposition scene: the precision and speed of collision detection is the important property of game. If we suppos

9、e there are 100 objects in world, for RPG game, system has to make collision detection for 100 objects and 1002 calculations of collision detection. If the are other objects existing in system, too large calculation amou

10、nt and too bad system performance are difficult to be accepted by players. So, it is necessary to promote the speed of collision detection. This article mainly p</p><p>　　Optimize bounding volume: in order t

11、o promote the precision of collision detection. But game scene includes dynamic role and static object, if the bounding volume of every object is updated real time, it will increase unnecessary time for calculation. Thus

12、, AABB bounding volume for the object in scene shall be bound in line with class when developing this game. For the static object in scene such as wall, house, tree and other objects with regular shape, only one bounding

13、 volume shall be bound, </p><p>　　Segment collision detection algorithm: game system has low requirement for the precision of collision detection, but has higher requirement for the running speed of game. Th

14、e static object in game scene do not need to take collision detection, and the collision would happen only between dynamic role and static object. The scene models of game are mostly regular object, so the adoption of AA

15、BB bounding volume is enough to express the object in scene approximately. The collision detection for two </p><p>　　OPTIMIZATION OF ALGORITHM</p><p>　　Large storage space and slow calculation s

16、peed is the biggest disadvantage of A* path search algorithm. This article adopts three methods to optimize and improve path search. With the method of grading for path search, A* algorithm embodies the intelligence of N

17、PC in path search, but has two defects: A* algorithm needs to maintain heuristic information, present node and expanding node, while, it needs inner storage with exponential quantity for worst situation, and objective po

18、int searched by A*</p><p>　　By observation，we find that all the optimal routes are the straight line between starting point and objective point in the condition of no obstacle. If there is obstacle, each tur

19、ning point must locate in the peak of convex polygon of obstacle. On the basis of the above idea for searching path, this system adopts grading path search method, which means that non-player role approach object at the

20、path without obstacle, A* algorithm shall be used for path search when the distance between non-playe</p><p>　　Figure 1: the sketch map of segment path search</p><p>　　The steps of improved algo

21、rithm: 1) let coordinate point S of non-player role as starting node and coordinate point G of player role as objective node; 2) calculate d=|G-S|; 3) if d<D( threshold set by people), NPC is activated, otherwise, tur

22、n back to 1); 4) path search in straight line, run after player role along the direction of ray; 5) if there is obstacle Q in path, calculate |Q-S|; if |Q-S|<k(( threshold set by people), call the improved A* algorit

23、hm; otherwise, turn back to 5); 6) turn</p><p>　　EXPERIMENTAL RESULT AND ANALYSIS</p><p>　　Collision detection algorithm: in this procedure, the action responding to collision is that virtual c

24、haracter slides along the edge of the object colliding so as to avoid obstacle. In this process, you have to pay attention to the situation that d is 0. This experiment adopts AABB collision detection algorithm and impro

25、ved algorithm. Then, compare the experimental data of storage’s calling time and game’s rendering frequency of two algorithms, where 100 groups of experimental data are collected</p><p><b>　　二、譯文</b

26、></p><p>　　碰撞檢測技術和人工智能技術可以被應用在游戲發(fā)展以及教育、虛擬現實、歷史保護、地理信息系統(tǒng)、科研、娛樂和商業(yè)領域中。因此，加強對3D游戲技術的研究具有重要的現實意義。并且適用于3D游戲的碰撞檢測技術和人工智能技術的成功研發(fā)將具有十分重要的理論意義和實現意義，具有廣泛的應用前景。隨著使用平臺開發(fā)3D游戲，本文深入研究了碰撞檢測算法和人工智能技術在游戲中的應用，以龐大的計算量，使用結合類保

27、衛(wèi)盒和空間分割段檢測法來提高碰撞檢測算法的速度慢、碰撞檢測計算不精確，可以有效地提高碰撞算法的精確度和速度。此外，本文完善了游戲路徑搜索算法，提高了長時間的搜索問題，搜索速度慢在A*路徑搜索算法的改進A*算法的路徑搜索方法，限制搜索范圍和加重的啟發(fā)函數數量。</p><p><b>　　碰撞檢測算法</b></p><p>　　BVH（層次包圍盒的碰撞算法）是一種最為

28、廣泛使用的碰撞檢測法。BBB的交叉實驗是很簡單，但是緊密的BBB碰撞測試卻很復雜。本文對包圍體的密實度和AABB包圍盒的碰撞檢測算法的檢測方法進行了改進。</p><p>　　改進思想：提高碰撞檢測算法的核心是實時性和精確度。有些游戲會犧牲一些精確度來的得到實時。該系統(tǒng)采用基于AABB包圍盒的碰撞算法，并且使用提高目的碰撞檢測算法簡單、快速和精確的方法，一定程度的提高了在AABB包圍盒碰撞檢測算法中密實度差、計算

29、量大的問題。改進思想主要包括以下幾個方面：1）應用BSP分解空間場景來減少碰撞檢測的計算量；2）優(yōu)化包圍盒；3）提出了段的碰撞檢測算法，來提高AABB碰撞檢測的速度。</p><p>　　BSP分解場景：精確度和碰撞檢測速度是游戲的重要屬性。假設在RPG游戲視圖中有100個物體，則系統(tǒng)要做出100個碰撞測試和1002個碰撞測試計算。如果還有其他的對象存在系統(tǒng)中，大量的計算和糟糕的系統(tǒng)是很難被玩家接受的。因此，提高

30、碰撞檢測的速度是很有必要的。本文主要提出了一下兩種方法來提高碰撞檢測的速度。首先，如上所述，如果游戲場景中不分解，碰撞測試就要對每一個對象進行碰撞，但是在這些檢測中，大部分的碰撞測試時無用的，一次，寶貴的時間和資源就在這些工作上浪費掉了。那么要如何減緩這種現象呢？從數據結構方面考慮，二叉樹的理念可以應用到場景的分解中。二叉樹法不僅可以應用在管理場景中，還可以應用到碰撞檢測里。二叉樹法可以分為不同的區(qū)域對象。每個區(qū)域由小的對象組成，碰撞測

31、試可以以區(qū)域為單位進行。遍歷BSP樹具有三維空間的優(yōu)勢。對于每次的循環(huán)，50%的對象不可能在對象的中心節(jié)點找到符合對象時才被樹維空間沖突排除掉。該方法快速簡單，它只需要log2N一個公式哪怕N是一個很復雜的數字，就能完成碰撞測試。因此，在分解場景采用BSP樹有利于碰撞檢測，并且在很大程度上減少了碰撞檢測的計算量。其次，可以從空間的</p><p>　　優(yōu)化包圍盒：來提高碰撞檢測的精確度。但是，游戲場景中包括動態(tài)和

32、靜態(tài)對象，如果每個物體的包圍盒都實時更新，這將增加不必要的時間來計算。因此，開發(fā)此游戲時使用AABB包圍盒對場景中的對象進行測試比較適宜。對于場景中的靜態(tài)對象如墻、房子、樹和其他規(guī)則形狀的對象只屬于一個包圍盒，并不會實時更新，這樣游戲中的碰撞檢測將會受到很大的影響。該系統(tǒng)只實時更新動態(tài)對象的包圍盒。包圍體的寬度應設為對象動作的最大跨度。如果邊界體積太小，碰撞檢測是不夠精確的，碰撞顯示也會有失真的現象；如果邊界體積過大，碰撞實時將會過長，

33、所以設計一個合理的包圍體會使碰撞檢測得到事半功倍的效果。動態(tài)對象的活動范圍也影響著碰撞檢測的精確度。如果對象的活動范圍過大，可能會發(fā)生以下情況：當前的幀沒有碰撞到對象，而下一幀又錯過了該對象，這意味著很容易出現對象小于活動范圍的現象。為了防止漏過，在創(chuàng)建對象動畫的過程中應為對象的活動范圍制定一個適當的值。</p><p>　　分段的碰撞檢測算法：游戲系統(tǒng)對碰撞檢測的要求不高，但對游戲的運行速度有著較高的要求。在游

34、戲場景中，靜態(tài)對象不需要碰撞檢測，碰撞只是發(fā)生在動態(tài)對象和靜態(tài)對象間。游戲的場景模型大多是普通的對象，因此，采用AABB包圍盒足以表達場景中對象的近似。兩個AABB包圍盒之間的碰撞檢測需要計算6次，如果在做碰撞之前有M個碰撞檢測，則在AABB包圍盒需要6M次的計算。這樣不僅計算量大，而且浪費時間，因為如果沒有碰撞只需要計算M即可。解決方案是在射線和靜態(tài)AABB兩個物體碰撞之前做交叉測試。在這過程中，AABB測發(fā)生沖突是無疑的，不改變動態(tài)

35、和靜態(tài)AABB是可能發(fā)生碰撞的，知道兩個物體將要碰撞時才會有碰撞檢測。然而，機會決定AABB包圍盒的移動射線從射線和靜態(tài)對象AABB包圍盒中獲得的距離。用改進的碰撞檢測算法計算量能減少近一半。該算法描述如下：1）選擇玩家角色包圍盒的中心點S和移動距離的矢量V并且以（S,V）作為參照做一個射線；2）利用BSP樹分解法很快就會發(fā)現可能是帶碰撞檢測的區(qū)域；帶碰撞檢測的射線和靜態(tài)AABB對象：估計出射線和靜態(tài)AABB對象之間的距離和AABB包圍

36、盒可能發(fā)生碰撞，消除不可能發(fā)生，</p><p><b>　　優(yōu)化算法</b></p><p>　　大面積的空間和緩慢的計算速度是A*尋路算法的最大不足。本文采用了三種方法來優(yōu)化和提高路徑搜索。隨著路徑搜索分級法，A*算法體現了NPC在路徑搜索的智能，但有兩個缺陷：A*算法需要保持啟發(fā)式信息，現節(jié)點和擴充節(jié)點，它需要擴大，為最壞情況下的指數數量的內存，目的節(jié)點的A*算

37、法的搜索都是靜態(tài)的，但在這個系統(tǒng)中的玩家角色是動態(tài)的，這顯然增加了路徑搜索的復雜性。A*路徑的搜索難以實現。因此，有必要改進A*尋路算法。通過觀察，我們發(fā)現，所有的路線在沒有障礙物的情況下，起始點和終點是直線的。如果有障礙物，每個轉折點必須在障礙物的凸多邊形的峰值。在上述尋路思想的基礎上，本系統(tǒng)采用分級路徑搜索方法，即非玩家在沒有障礙物的路徑上接近對象時，A*算法應用于尋路時在非玩家角色和障礙物范圍之間設置一個臨界值d ，然后使最有節(jié)點

38、應該選擇實時改變路徑。對于另一個點間的直線運動而言，延長節(jié)點是非常小計算量也會很小。圖1是分級尋路法即本文采用的示意圖，其中起點顯示NPC，終點表示玩家的角色。U是NPC的移動方向，V是玩家的移動方向。從NPC出發(fā)點到節(jié)點采用直線路徑運動。當NPC和障礙物之間的距離是臨界值d時，改進好的A</p><p>　　圖1：段路徑搜索示意圖</p><p>　　改進算法的步驟：1）讓非玩家角色的調

39、節(jié)點S作為起始節(jié)點，調節(jié)玩家角色的G點作為目標節(jié)點；2）計算d= | G-S |；3）如果d＜D（人為設定的臨界值），NPC被激活，否則，返回到1）；4）按直線進行路徑搜索，玩家角色行動沿著射線方向；5）如果在路徑遇到障礙物Q，計算| Q-S |；如果| Q-S |＜k（人為設定的臨界值）即為改進的A*算法；否則，返回5）；6）返回到4）。重復操作。</p><p><b>　　實驗結果和分析</

40、b></p><p>　　碰撞檢測算法：在這一過程中的作用，行動對碰撞作出反應是虛擬角色沿著該物體的邊緣避免碰撞障礙物。在這個過程中要注意的是D是0. 本實驗采用AABB包圍盒的碰撞檢測算法及改進算法。比較存儲的調用時間和2種算法的游戲編譯頻率的實驗數據，其中100組實驗數據進行規(guī)定和10組隨機選擇平均值進行了比較。實驗結果的比較如圖2和圖3所示。</p><p>　　圖2 算法訪問