基于三維桌面操作系統(tǒng)的３Ｄ游戲設(shè)計(jì)與實(shí)現(xiàn)

（1.計(jì)算機(jī)科學(xué)聯(lián)合研究院，北京100037；2.首都師范大學(xué)，北京100037；3.中國(guó)科學(xué)院 自動(dòng)化所，北京 100088；4.中國(guó)科學(xué)院計(jì)算技術(shù)研究所， 北京 100190； 5.南昌大學(xué) 信息工程學(xué)院，南昌 330031）



摘 要：

為了實(shí)現(xiàn)內(nèi)嵌于三維桌面操作系統(tǒng)的一款3D益智小游戲，結(jié)合游戲具體的開(kāi)發(fā)過(guò)程，討論并解決了在設(shè)計(jì)中遇到的隨機(jī)切割、三維鼠標(biāo)拾取操作和碰撞檢測(cè)關(guān)鍵問(wèn)題。通過(guò)使用包圍盒檢測(cè)、相交檢測(cè)和方向向量檢測(cè)方法加速了游戲的碰撞檢測(cè)處理，使渲染速度提升了34.8%，最終游戲能夠以31 fps的速度流暢地運(yùn)行。

關(guān)鍵詞：三維桌面操作系統(tǒng)； 三維鼠標(biāo)； 切割算法； 碰撞檢測(cè)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2008)12382603



Design and realization of 3D game based on 3D desktop OS



TIAN Zixiao1，2， HUANG Haiming1， 2，3， LIU Yungen1，4，5， LIU Jingang1， 2，4

(1. Joint Faculty of Computer Scientific Research， Beijing 100037， China；2.Capital Normal University， Beijing 100037， China；3.Institute of Automation， Chinese Academy of Sciences， Beijing 100088， China；4. Institute of Computing Technology， Chinese Academy of Sciences， Beijing 100190， China; 5.College of Information Engineering， Nanchang University， Nanchang 330031， China)



Abstract:In order to realize a threedimensionalpuzzle game embedded in the 3D desktop OS， this paper took the actual development of this game for example， and resolved several designed problems， which included the random cutting， the threedimensional mousepickup operation and the collision detection. The algorithm based on bounding box the intersection detectionand the direction vector detection， accelerates the computation speed of collision detection. The experimental result shows abovemethod gets 34.8% performance promotion. In final， the game runs smoothlyat the rendering speed of 31 frames per second.

Key words：3D desktop OS; 3Dmouse; random cutting algorithm; collision detection



三維應(yīng)用是近年來(lái)的熱門(mén)領(lǐng)域。當(dāng)前，三維領(lǐng)域的各個(gè)方面均在蓬勃發(fā)展，為滿足大多數(shù)人的虛擬現(xiàn)實(shí)的需求，中國(guó)科學(xué)院計(jì)算所與首都師范大學(xué)計(jì)算機(jī)科學(xué)聯(lián)合研究院自主開(kāi)發(fā)的三維操作系統(tǒng)真正實(shí)現(xiàn)了桌面的三維化^[1]。而基于此操作系統(tǒng)的三維游戲開(kāi)發(fā)目前還處于空白，本游戲的研發(fā)正好填補(bǔ)了此空白，并為今后以此操作系統(tǒng)作為三維游戲開(kāi)發(fā)平臺(tái)提供理論和實(shí)踐基礎(chǔ)。

目前，三維游戲開(kāi)發(fā)呈現(xiàn)出百花齊放的局面，但是裝箱游戲是市面上還不曾見(jiàn)到的一款游戲，它讓玩家能充分發(fā)揮空間想象力去組織各種形狀積木的擺放和處理碰撞問(wèn)題，并且游戲中使用三維光標(biāo)來(lái)控制游戲，顯得生動(dòng)逼真，因而該款游戲富有挑戰(zhàn)性和趣味性。基于上述需求，本文將介紹一款內(nèi)嵌于三維桌面操作系統(tǒng)的三維裝箱游戲的設(shè)計(jì)與實(shí)現(xiàn)。

1 游戲概述

由于本游戲要編譯運(yùn)行于三維桌面操作系統(tǒng)，本文選用了SDL＋OpenGL以及標(biāo)準(zhǔn)C++作為開(kāi)發(fā)工具。Simple DirectMedia Layer（SDL）是一個(gè)自由的跨平臺(tái)的多媒體開(kāi)發(fā)包。OpenGL是開(kāi)放圖形API庫(kù)，其跨平臺(tái)性正是其最大優(yōu)勢(shì)。SDL本身是針對(duì)2D圖像編程的，如果想應(yīng)用于3D編程，需將SDL與OpenGL結(jié)合使用，本游戲正是基于SDL和OpenGL聯(lián)合開(kāi)發(fā)的。

游戲的主要思想是在游戲開(kāi)始時(shí)自動(dòng)生成若干積木塊（根據(jù)用戶設(shè)定等級(jí)決定積木塊的數(shù)量，如初級(jí)為8塊，中級(jí)為27塊），利用三維鼠標(biāo)通過(guò)各個(gè)視角觀察積木塊，進(jìn)行旋轉(zhuǎn)、平移等操作，通過(guò)空間想象力將積木塊放于空箱子中的正確位置，最終完全裝滿箱子游戲結(jié)束。

游戲按功能劃分為游戲初始化、鼠標(biāo)操作、碰撞檢測(cè)和處理三部分。游戲初始化部分包括SDL初始化、OpenGL初始化、隨機(jī)生成積木塊、隨機(jī)擺放積木；鼠標(biāo)操作部分，就是用三維鼠標(biāo)操作對(duì)積木塊進(jìn)行旋轉(zhuǎn)平移；碰撞檢測(cè)和處理部分，是對(duì)積木塊移動(dòng)及裝箱過(guò)程中的碰撞進(jìn)行檢測(cè)并進(jìn)行碰撞后的處理。游戲整體設(shè)計(jì)流程如圖1所示。

2 隨機(jī)切割算法

積木的生成是游戲初始化的關(guān)鍵部分，由于最終要用積木把箱子裝滿，本文采取了對(duì)與箱子同樣大小的積木進(jìn)行切割來(lái)生成小積木塊的方法。隨機(jī)切割則可以保證每次游戲的不重復(fù)性。針對(duì)初級(jí)游戲，本文設(shè)計(jì)為切割兩層，每層四塊積木，具體切割算法設(shè)計(jì)為切三刀，切面方程最簡(jiǎn)單的設(shè)計(jì)為AX+BY+CZ =0（其中(A，B，C為平面法向量）；且兩條切面的交線要落在整塊積木的內(nèi)部（判斷算法）。這樣實(shí)現(xiàn)任意切割時(shí)，不會(huì)出現(xiàn)積木塊達(dá)不到四塊或超出四塊的情況。

切割面與原被切割正方體擬相交的四條棱上隨機(jī)取點(diǎn)，利用這三個(gè)點(diǎn)組成面方程，與擬相交的第四條棱相交，如果交點(diǎn)符合條件（即交點(diǎn)在原被切割正方體的棱上）即作為第一個(gè)切面，否則重新找點(diǎn)和切面方程；同理，找到第二個(gè)切面。為簡(jiǎn)化起見(jiàn)，第三個(gè)切面用水平面切割。其中，求面方程，利用點(diǎn)法式方程，需首先求出所求平面的一個(gè)法向量n。

n=P1P2×P1P3=ijk

x1y1z1x2y2z2=

(y1×z2-y2×z1)i-(x1×z2-x2×z1)j+(x1×y2-x2×y1)k

(1)

dotn=P1P2×P1P3=(P2#8226;x-P1#8226;x)×

(P3#8226;x-P1#8226;x)+

(P2#8226;y-P1#8226;y)×(P3#8226;y-P1#8226;y)+

(P2#8226;z-P1#8226;z)×(P3#8226;z-P1#8226;z)

(2)

|n|=(n#8226;x×n#8226;x)+(n#8226;y×n#8226;y)+(n#8226;z×n#8226;z)

(3)



由式(1)(2)以及點(diǎn)法式方程得出所求平面方程為

(x-x1)(y1-y2)(z1-z3)+(x1-x2)(y1-y3)(z-z1)+

(x1-x3)(y-y1)(z1-z2)-(z-z1)(y1-y2)(x1-x3)-

(z1-z2)(y1-y3)(x-x1)-(z1-z3)(y-y1)(x1-x2)=0(4)



求平面的法線向量和平面常數(shù)項(xiàng)：

由式（4）得d = -(a×x1+b×y1+c×z1)。

其中：



a = (y2-y1)×(z3-z1)-(z2-z1)×(y3-y1)；

b = (z2-z1)×(x3-x1)-(x2-x1)×(z3-z1)；

c = (x2-x1)×(y3-y1)-(y2-y1)×(x3-x1)。



此外，算法中應(yīng)避免找不到切面而出現(xiàn)的死循環(huán)，解決辦法是srand((time( t2)+ (i++)))控制隨機(jī)種子生成，避免重復(fù)，這樣最多循環(huán)兩次就可以找到所需平面方程。其流程如圖2所示。

3 三維鼠標(biāo)

3. 1 三維鼠標(biāo)及其移動(dòng)

與傳統(tǒng)的二維鼠標(biāo)操作相比，三維實(shí)體光標(biāo)除了可以在屏幕上左右移動(dòng)之外還可以沿屏幕縱深法線方向移動(dòng)，并顯示出透視投影的效果。這里用鼠標(biāo)滾輪作為沿縱深移動(dòng)的鍵，使玩家可以往屏幕里面推物體，讓操作更加接近現(xiàn)實(shí)。此功能是三維鼠標(biāo)的一個(gè)應(yīng)用^[2]。

三維鼠標(biāo)由兩部分組成，即拾取的熱點(diǎn)M和鼠標(biāo)的外形。拾取熱點(diǎn)是供系統(tǒng)拾取時(shí)使用的；鼠標(biāo)的外形就是一個(gè)3D光標(biāo)模型，讓用戶知道光標(biāo)的位置。如下是定義的光標(biāo)類class Mouse，其繼承于class Object。

Class Mouse{

void Draw();//渲染

void DrawHotPoint();//渲染熱點(diǎn)

void Draw3DCursor();//渲染3D光標(biāo)模型

public:

void TranslateAlong(Matrix4x4 cord， Matrix4x4 T);

//該函數(shù)功能使得光標(biāo)在坐標(biāo)系cord下進(jìn)行T變換；

void TranslateAlongX(float dis);/*該函數(shù)表示光標(biāo)在攝像機(jī)坐標(biāo)系下沿?cái)z像機(jī)的X軸平移dis個(gè)單位*/

……}



在三維鼠標(biāo)操作中拾取射線L的方向是指從攝像機(jī)向光標(biāo)位置看的方向，三維光標(biāo)縱深移動(dòng)是以拾取射線L的方向作為光標(biāo)前移方向的。其計(jì)算公式為

其中，pCamera為攝像機(jī)的空間位置；pMouse為三維光標(biāo)的空間位置。

式(6)用于判斷光標(biāo)的前后移動(dòng)方向。假設(shè)當(dāng)前幀的三維光標(biāo)位置為pMouse1，上一幀的三維光標(biāo)位置為pMouse2，令v1= pMouse1- pMouse2，v2=n可以通過(guò)系統(tǒng)函數(shù)獲取。

3. 2 三維鼠標(biāo)拾取與操作方式

三維鼠標(biāo)的拾取中筆者利用了OpenGL的選擇與反饋機(jī)制。在OpenGL的拾取機(jī)制中，glSelectBuffer(BUFSIZE， buffer)指定用于返回選擇數(shù)據(jù)的數(shù)組，參數(shù)buffer是指向無(wú)符號(hào)整數(shù)(unsigned integer)數(shù)組的指針，返回的數(shù)據(jù)就存在于這個(gè)數(shù)組中。其中包括當(dāng)前被射線L穿過(guò)的所有物體。本文將撿選區(qū)R設(shè)定在屏幕光標(biāo)熱點(diǎn)處，就可以保證是光標(biāo)所選取的物體集合S。但是在真三維光標(biāo)的拾取操作中，筆者認(rèn)為光標(biāo)熱點(diǎn)M在某物體obj內(nèi)部時(shí)才認(rèn)為拾取到了obj，這樣更符合三維空間的習(xí)慣。而對(duì)于被光標(biāo)所選取的物體集合S中每個(gè)物體的最近點(diǎn)p1與最遠(yuǎn)點(diǎn)p2和M均在同一條射線上（即射線L），所以，判斷M是否在obj內(nèi)部的問(wèn)題，就轉(zhuǎn)換為M是否在線段p1p2上，即判斷式（7）是否成立：

(buffer[i×4+1]≤buffer[1])(buffer[1]≤

buffer[i×4+2])(7)

其中：buffer[1]是M的深度值；i是obj在buffer中的索引。這樣就準(zhǔn)確實(shí)現(xiàn)了用三維光標(biāo)對(duì)空間物體的拾取。

具體三維操作方式為：移動(dòng)光標(biāo)（不滾動(dòng)滾輪）用于控制三維光標(biāo)在與屏幕平行平面上移動(dòng)；滾動(dòng)滑輪用于控制三維光標(biāo)在縱深方向的移動(dòng)（如果此時(shí)沒(méi)有選中物體，則移動(dòng)三維光標(biāo)，否則同時(shí)移動(dòng)三維光標(biāo)和物體）；單擊鼠標(biāo)左鍵用于執(zhí)行當(dāng)前已選中物體的打開(kāi)操作；鼠標(biāo)左鍵并移動(dòng)鼠標(biāo)用于移動(dòng)攝像機(jī)（如果此時(shí)沒(méi)有選中物體）或者移動(dòng)物體和三維光標(biāo)（如果此時(shí)選中了物體）；右鍵按下并移動(dòng)鼠標(biāo)用于旋轉(zhuǎn)攝像機(jī)；左/右鍵抬起用于標(biāo)志相應(yīng)的操作結(jié)束。

4 碰撞檢測(cè)

虛擬環(huán)境中的碰撞檢測(cè)具體工作包括兩個(gè)部分，即檢測(cè)是否有碰撞發(fā)生和計(jì)算出碰撞發(fā)生的位置^[3]。在本游戲中，碰撞檢測(cè)同樣也遵循這個(gè)原則，檢測(cè)碰撞發(fā)生的方法同樣采用包圍盒先粗略檢測(cè)，再進(jìn)行相交精確檢測(cè)。

4. 1 包圍盒檢測(cè)

在碰撞檢測(cè)的研究歷史中，粗略檢測(cè)方法有這樣幾類包圍盒方法：沿坐標(biāo)軸的包圍盒 AABB(axis aligned bounding boxes)^[4]、包圍球 (Sphere)、沿任意方向包圍盒OBB(oriented bounding box)、固定方向包圍盒FDH(fixed directions hulls)，和一種具有更廣泛意義kdop包圍盒。

目前有很多方法可實(shí)現(xiàn)碰撞檢測(cè)技術(shù)^[3]，根據(jù)本游戲的積木塊特點(diǎn)，采用廣泛使用的沿坐標(biāo)軸的包圍盒(AABB)。對(duì)象的包圍盒被定義為包含該對(duì)象且各邊平行于坐標(biāo)軸的最小的六面體，那么分別計(jì)算對(duì)象的頂點(diǎn)的x坐標(biāo)、y坐標(biāo)和z坐標(biāo)的最大值以及最小值即可得到包圍盒；AABB間的相交測(cè)試也比較簡(jiǎn)單，兩個(gè)AABB相交判斷可用一個(gè)AABB的六個(gè)最大值和最小值坐標(biāo)是否均在另一個(gè)AABB的x、y、z的相應(yīng)區(qū)間內(nèi)。因此，AABB包圍盒的相交測(cè)試最多只需要六次比較運(yùn)算^[5]。

4. 2 精確檢測(cè)算法

在計(jì)算機(jī)圖形學(xué)中，相交測(cè)試是最經(jīng)常使用的方法。判斷兩個(gè)物體是否相交可轉(zhuǎn)換為判斷一個(gè)物體的頂點(diǎn)在另一個(gè)物體的點(diǎn)、面或者在另一個(gè)物體所有的面包圍的空間內(nèi)部即可。

假設(shè)一個(gè)凸多面體由N個(gè)平面惟一確定。其中每一個(gè)平面的方程為

A×x+B×y+C×z+D=0 ，N#8226;P+D=0(8)

其中:N=(A，B，C)為平面的法向量，P=(x， y， z)為平面中的點(diǎn)。如果定義平面的法向指向前面，那么N#8226;P+D>0 表示P點(diǎn)在平面前，N#8226;P+D≤0表示P點(diǎn)在平面后。如果對(duì)于構(gòu)成凸多面體的所有平面，P點(diǎn)均在其后，那么P在這個(gè)多面體內(nèi)部，反之，P點(diǎn)在其外部；若P點(diǎn)在物體內(nèi)部時(shí)視為碰撞。

在上述檢測(cè)算法中，積木塊的頂點(diǎn)沒(méi)有在另一個(gè)積木塊的內(nèi)部，但其中一積木塊的棱穿入另一個(gè)積木塊中的碰撞情況，如圖3(a)所示。仍然會(huì)造成失真。本游戲通過(guò)增加積木塊的中心點(diǎn)向量很好地解決了這個(gè)問(wèn)題，中心點(diǎn)向量是指以積木塊的中心為向量始點(diǎn)，方向向外，以與自身各面的交點(diǎn)的距離為大小。如圖3(b)所示。每當(dāng)移動(dòng)一個(gè)積木塊時(shí)，而頂點(diǎn)判斷未碰撞時(shí)，就判斷中心點(diǎn)向量是否和其他積木的面相交；而把中心點(diǎn)和各個(gè)頂點(diǎn)連線的向量作為中心點(diǎn)向量時(shí)，還是不夠精確，此時(shí)的圖3（b）只用四個(gè)頂點(diǎn)和中心點(diǎn)的四條連線向量仍然沒(méi)有檢測(cè)到碰撞。

實(shí)踐證明，方向向量增加到36時(shí)，不會(huì)出現(xiàn)碰撞檢測(cè)失誤，但是這樣做的缺點(diǎn)也很明顯，就是增加了算法的運(yùn)算復(fù)雜度，大大降低了運(yùn)行速度^[6]。當(dāng)積木塊的頂點(diǎn)太多或者積木塊太多時(shí)，運(yùn)行量大得驚人，此時(shí)，選用適當(dāng)?shù)姆较蛳蛄坑葹橹匾Ｈ舴e木塊數(shù)為八塊，每塊選取方向向量為8（即以中心為向量原點(diǎn)，與各個(gè)棱的方向平行的向量和其反方向?yàn)榉较蛳蛄抗舶藗€(gè)方向），則增加3 fps。

此時(shí)，投影圖如圖4所示（投影圖取最大投影）。假設(shè)方向向量op與面CD的交點(diǎn)為q，并設(shè)距離為oq；假設(shè)方向向量op與面ab的交點(diǎn)為p，并設(shè)距離為op；若此時(shí)將積木塊abcd沿po方向后退op~oq的距離，調(diào)用碰撞處理函數(shù)，則可避免積木塊間的粘連。

4. 3 碰撞檢測(cè)算法的優(yōu)化

本游戲先經(jīng)包圍盒粗略計(jì)算，快速排除明顯不相交的物體，再經(jīng)過(guò)精確檢測(cè)，速度提高明顯。但是精確相交檢測(cè)的算法還可以從多個(gè)方面進(jìn)行修正，進(jìn)一步提高準(zhǔn)確性和速度，其思想是增加每一個(gè)積木塊的運(yùn)動(dòng)方向檢測(cè)。大致分兩種情況：

a）在包圍盒檢測(cè)到碰撞后，檢測(cè)相碰撞的兩個(gè)物體的運(yùn)動(dòng)方向，如果兩運(yùn)動(dòng)方向（不運(yùn)動(dòng)的物體的面法線作為運(yùn)動(dòng)方向）平行且反向或者兩方向垂直且方向夾角是90°，則不可能再碰撞，不再進(jìn)行準(zhǔn)確檢測(cè)。

b）當(dāng)擺放積木時(shí)只執(zhí)行準(zhǔn)確檢測(cè)。限制箱子周圍一定空間內(nèi)（如箱子的半徑加上最大積木塊的半徑）的積木的碰撞，此時(shí)無(wú)須進(jìn)行粗略檢測(cè)，只進(jìn)行準(zhǔn)確檢測(cè)。

4. 4 碰撞后的處理

當(dāng)精確檢測(cè)時(shí)檢測(cè)到兩個(gè)物體相碰撞后，如果是頂點(diǎn)相交碰撞，進(jìn)行回退，回退的距離小于原擬移動(dòng)的距離，其算法用折半逐步減小距離法實(shí)現(xiàn)；再進(jìn)行檢測(cè)，若仍碰撞，則繼續(xù)后退。如此循環(huán)，直到兩個(gè)積木塊的距離達(dá)到設(shè)定的檢測(cè)值，并進(jìn)行自動(dòng)矯正貼緊。若頂點(diǎn)相交檢測(cè)不碰撞，則進(jìn)行方向向量檢測(cè)，后退op~oq的距離再進(jìn)行檢測(cè)。經(jīng)過(guò)上述的綜合優(yōu)化處理后，顯示的幀率由原來(lái)的23 fps加速到31 fps，性能提升了34.8%，達(dá)到了可以流暢地運(yùn)行該款游戲的目標(biāo)。

初級(jí)游戲效果截圖如圖5、6所示。

5 結(jié)束語(yǔ)

本文基于SDL和OpenGL，設(shè)計(jì)并實(shí)現(xiàn)了三維桌面操作系統(tǒng)下的一款積木裝箱子游戲。游戲以眾人熟悉的積木為基礎(chǔ)，以訓(xùn)練三維空間想象能力為目標(biāo)，運(yùn)用多種OpenGL技術(shù)及其優(yōu)化技術(shù)，為今后以三維桌面操作系統(tǒng)作為3D游戲開(kāi)發(fā)平臺(tái)提供理論和實(shí)踐基礎(chǔ)。由于目前真正的三維操作系統(tǒng)正處于完善階段，其配套系統(tǒng)還需進(jìn)一步完善，下一步將對(duì)游戲添加智能的虛擬人來(lái)操作搬運(yùn)積木塊，并實(shí)現(xiàn)自動(dòng)路徑避障，使游戲更加有趣、生動(dòng)。

參考文獻(xiàn)：

[1]黃海明.基于空間多點(diǎn)信息采集的虛擬現(xiàn)實(shí)人景合成關(guān)鍵技術(shù)研究[D].北京：中國(guó)科學(xué)院計(jì)算技術(shù)研究所，2005.

[2]姚延嗣.虛擬環(huán)境鼠標(biāo)三維操作的研究與實(shí)現(xiàn)[D].北京：首都師范大學(xué)，2007.

[3]王志強(qiáng)，洪嘉振，楊輝.碰撞檢測(cè)問(wèn)題研究綜述[J].軟件學(xué)報(bào)，1999，10(5)：545551.

[4]BERGEN van den， BERGEN G. Efficient collision detection of complex deformable models using AABB trees[J].Journal of Graphic Tools，1997，2(4)：113.

[5]和莉，劉惠義.碰撞檢測(cè)技術(shù)在三維交互漫游系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16(6)：9293.

[6]鄧桂英.OpenGL制作三維游戲的研究[J].計(jì)算機(jī)與現(xiàn)代化，2005(11)：2427.